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.