$\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search

Authors: Yinan Li, Tuan Nguyen, Kwang-Sung Jun

arXiv · PDF

Summary

The authors study fixed-budget action identification in depth-2 max-min trees (a special case of Monte Carlo Tree Search), where a learner allocates T samples to leaves and recommends a subtree whose minimum leaf value is largest. They focus on ε-good identification (any subtree within ε of optimal is acceptable) and propose an ε-agnostic algorithm that doesn't require ε as input but achieves instance-dependent error bounds for every meaningful ε, with misidentification probability decaying exponentially in T.

Main takeaways:

• The algorithm works without knowing ε (the acceptable approximation gap) ahead of time, yet achieves good bounds for every meaningful ε.
• Misidentification probability decays as exp(-Θ(T/H₂(ε))), where H₂(ε) captures both cross-subtree and within-subtree gaps.
• When each subtree has a single leaf, the problem reduces to standard best-arm identification, and the analysis recovers known guarantees for halving-style methods.
• Max-min identification has a different hardness structure from standard K-armed bandits.
• First provable fixed-budget algorithmic guarantee for max-min action identification.

Relevance

Not directly related to my persona/midtraining work — this is about bandit algorithms and tree search, not about language model behavioral installation. Only tangentially relevant if I ever frame persona selection as a multi-armed bandit problem.

Threat model

Potential threat/caveat for experiment "Chen et al. persona-vectors (mean-diff vs helpful baseline) fail as a [ZLT]-leakage predictor on both non-persona triggers and personas; simpler mean-pooled centroids beat them on both phases (HIGH confidence)": this item discusses negative.

Abstract

arXiv:2605.11324v1 Announce Type: cross Abstract: We study the fixed-budget max-min action identification problem in depth-2 max-min trees, an important special case of Monte Carlo Tree Search. A learner sequentially allocates $T$ samples to leaves and then recommends a subtree whose minimum leaf value is largest. Motivated by approximate planning, we focus on $\varepsilon$-good subtree identification, where any subtree whose min value is within $\varepsilon$ of the optimal maximin value is acceptable. Our main contribution is an $\varepsilon$-agnostic algorithm: it does not require $\varepsilon$ as input, but achieves instance-dependent error bounds for every meaningful $\varepsilon$. We show that the misidentification probability decays as $\exp(-\widetilde{\Theta}(T/H_2(\varepsilon)))$, where $H_2(\varepsilon)$ captures both cross-subtree and within-subtree gaps. When each subtree has a single leaf, the problem reduces to standard fixed-budget best-arm identification, and our analysis recovers, up to accelerating factors, known $\varepsilon$-good guarantees for halving-style methods while giving a new $\varepsilon$-good guarantee for Successive Rejects. On the lower-bound side, we provide complementary positive and negative results showing that max-min identification has a different hardness structure from standard $K$-armed bandits. To our knowledge, this is the first provable fixed-budget algorithmic guarantee for max-min action identification.