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

arXiv: https://arxiv.org/abs/2605.11324 · HTML: https://mlsanity.com/paper/2605.11324/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 12 of 12)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [On the Existence of a Complexity in Fixed Budget Bandit Identification](https://mlsanity.com/paper/2303.09468/) (2023)
- [Monte-Carlo Tree Search by Best Arm Identification](https://mlsanity.com/paper/1706.02986/) (2017)
- [Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups](https://mlsanity.com/paper/1406.0486/) (2014)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [Maximin Action Identification: A New Bandit Framework for Games](https://mlsanity.com/paper/1602.04676/) (2016)

## Abstract (arXiv)

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(-widetildeTheta(T/H2(varepsilon))), where H2(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.