arepsilon-Good Action Identification in Fixed-Budget Monte Carlo Tree Search

arXiv:2605.11324v1 Announce Type: new 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 arepsilon-good subtree identification, where any subtree whose min value is within arepsilon of the optimal maximin value is acceptable. Our main contribution is an arepsilon-agnostic algorithm: it does not require arepsilon as input, but achieves instance-dependent error bounds for every meaningful arepsilon. We show that the misidentification probability decays as exp(-widetilde{Theta}(T/H_2(arepsilon))), where H_2(arepsilon) 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 arepsilon-good guarantees for halving-style methods while giving a new arepsilon-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.

Source: arXiv cs.LG | 2026-05-13