Research map / Bandits and online learning / Multi-armed bandits

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

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Pure exploration algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies fixed-budget epsilon-good subtree identification in depth-2 max-min trees (MCTS) with an epsilon-agnostic Successive-Rejects-style algorithm with tree-aware subtree elimination, giving an exponential error bound in H_2(epsilon) and a lower bound for exact identification.

Problem

Fixed-budget identification of a subtree with largest min-value (max-min value) in depth-2 max-min trees, where any epsilon-near-optimal subtree is acceptable; motivated by approximate planning in MCTS.

Approach

An epsilon-agnostic Successive-Rejects-style phase algorithm using empirical max-min gaps per leaf, and a subtree-level elimination rule that removes an entire subtree when all its active leaves share the largest empirical gap, avoiding distortion of a subtree's surviving minimum from removing a single leaf.

Key results

• Failure probability of the algorithm for epsilon-good identification is at most 2K^2L^2 exp(-(T-KL)/(128 log-bar(KL) H_2(epsilon))), epsilon-agnostic.
• For exact identification, a lower bound of c1 exp(-c2 T/H_lb(nu)) holds for some instance in the class with H(nu) at most 4H(nu), with H_lb the subtree-min and within-optimal-subtree gap complexity.
• With L=1 the bound specializes to a Successive Rejects epsilon-good guarantee for K-armed bandits.

Surprising findings

• A permutation-style lower bound route cannot yield an H_2-type lower bound for max-min trees even for K=2, L=2.

Limitations

• Gap between upper and lower bounds remains open.
• Analysis restricted to depth-2 trees and unique optimal subtree.
• Upper bound is order-wise, with logarithmic factors and constants; not shown to be minimax optimal.

Experimental setup

Metrics: misidentification probability upper bound lower bound exponent

Baselines: Successive Rejects applied to all leaves bottom-up multi-bandit BAI Successive Halving

Builds on: Successive Rejects Successive Halving Track-and-Stop / GLR tracking for maximin trees

Closest papers by meaning

• Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.87)
• An Efficient Algorithm for Thresholding Monte Carlo Tree Search (NeurIPS 2026 · similarity 0.87)
• Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.86)
• Fixed-Budget Differentially Private Best Arm Identification (ICLR 2024 · similarity 0.86)
• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.86)
• Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.85)