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

We study the fixed-budget max–min action identification problem in depth-2 max–min trees, which is an important special case of Monte Carlo Tree Search (MCTS). In this problem, a learner sequentially and adaptively selects $T$ reward samples from leaves (depth-2 nodes) and then must recommend a subtree (depth-1 node) with the largest min-value among its children nodes. Motivated by approximate planning, we focus on \emph{$\varepsilon$-good subtree identification}, where any subtree whose min value is within $\varepsilon$ of optimal maximin value is acceptable. Our main contribution is an \emph{$\varepsilon$-agnostic} algorithm—requiring no knowledge of $\varepsilon$—that nevertheless achieves error bounds with explicit instance-dependent dependence on $\varepsilon$. We show that, for every meaningful $\varepsilon$, the misidentification probability decays as $\exp\big(-\tilde\Theta(\frac{T}{H_2(\varepsilon)} )\big)$, where $H_2(\varepsilon)$ captures both cross-subtree and within-subtree gaps. In the special case where each subtree has a single leaf, the model reduces to standard multi-armed bandit identification, and our bounds recover (up to accelerating factors) the best-known $\varepsilon$-good guarantees associated with halving-style methods, while providing a new $\varepsilon$-good analysis and guarantee for the Successive Rejects algorithm in fixed budget best arm identification. On the lower-bound side, we present complementary positive and negative results. While there is a gap between the upper and lower bounds, we discuss the main technical challenges in obtaining a tighter lower bound, which tells us that the maximin action identification problem is quite different from the standard $K$-armed bandits. To our knowledge, this is the first provable algorithmic guarantee for fixed-budget maximin action identification.