cs.LGMay 11, 2026

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

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

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 TT 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⁡(−Θ~(T/H2(ε)))\exp(-\widetildeΘ(T/H_2(\varepsilon))), where H2(ε)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 KK-armed bandits. To our knowledge, this is the first provable fixed-budget algorithmic guarantee for max-min action identification.

Explore similar work

CardsList
Jun 1, 2026cs.LG

Two-Fidelity Best-Action Identification for Stochastic Minimax Tree

We study fixed-confidence best-action identification (BAI) in stochastic minimax trees. This problem is increasingly relevant in modern AI planning, where deep minimax search and Monte Carlo Tree Search (MCTS) with language model long rollouts face a fundamental tradeoff: heuristic evaluations are cheap but biased, while accurate rollouts are reliable but prohibitively expensive. We propose 2FFS, a two-fidelity tree-search algorithm that brings multi-fidelity flat bandit ideas into trees. The algorithm combines minimax-style fast expansion with MCTS-style stochastic sampling, adaptively deciding when to exploit cheap biased evaluations and when to invoke expensive accurate evaluations for local certification. We prove fixed-confidence correctness, establish finite stopping for exact identification, and give a polynomial-depth cost upper bound for general-depth trees. Across numerical stochastic-tree experiments, 2FFS uses substantially fewer samples and computational operations comparing to existing BAI-MCTS baseline.
Peter Chen, Xi Chen
Monte Carlo Tree SearchTree SearchMinimaxStochasticTrees
AskPDF
Jul 13, 2026cs.LG

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across KK arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any K≥3K\ge 3 and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most (1+log⁡(K)8)−1\left(1 + \frac{\log(K)}{8}\right)^{-1} times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.
Motti Goldberger
Generalized Linear BanditBudgetsFundamental LimitsExponential Family
AskPDF
May 15, 2026cs.LG

On the Power of Adaptivity for \varepsilon-Best Arm Identification in Linear Bandits

We study the minimax sample complexity of ε\varepsilon-best arm identification in linear bandits. Given a compact action set X\mathcal{X} that spans Rd\mathbb{R}^d and an unknown reward vector θ∈Rdθ\in\mathbb{R}^d, the goal is to output an arm x^∈X\widehat{x}\in\mathcal{X} such that ⟨x^,θ⟩≥max⁡x∈X⟨x,θ⟩−ε\langle \widehat{x},θ\rangle \ge \max_{x\in\mathcal{X}} \langle x,θ\rangle - \varepsilon with probability at least 1−δ1-δ, using as few samples as possible. First, we present a non-adaptive fixed-design method with sample complexity O ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right), where w(X)w(\mathcal{X}) is a Gaussian width term dependent on X\mathcal{X}, and we prove a matching lower bound Ω ⁣(dlog⁡(1/δ)ε2+w(X)2ε2)Ω\!\left(\frac{d\log(1/δ)}{\varepsilon^2}+\frac{w(\mathcal{X})^2}{\varepsilon^2}\right) for all non-adaptive fixed-design methods. We then turn to adaptive sampling. We raise an important structural question: beyond the canonical basis, are there structured action sets for which adaptivity yields only logarithmic-factor improvements over the optimal non-adaptive rate? We answer in the affirmative for several natural action sets, namely the hypercube, the ℓ2\ell_2 ball, mm-sets, and multi-task multi-armed bandits. Finally, we provide the first construction of an action set X\mathcal{X} for which adaptivity yields a polynomial-factor improvement over every non-adaptive algorithm. A key ingredient behind this separation is an ℓ2\ell_2-norm estimation subroutine: we design an adaptive algorithm that uses O ⁣(dlog⁡(1/δ)ε2)\mathcal{O}\!\left(\frac{d\log(1/δ)}{\varepsilon^2}\right) samples from the unit ℓ2\ell_2 ball in Rd\mathbb{R}^d and outputs an estimate r^\widehat r satisfying ∣r^−∥θ∥2∣≤ε|\widehat r-\|θ\|_2|\le \varepsilon with probability at least 1−δ1-δ, where θθ is the unknown reward vector.
Arnab Maiti, Yunbei Xu, Kevin Jamieson
Generalized Linear BanditOptimal Sample ComplexityArms
AskPDF