Research map / Learning theory and algorithms / Combinatorial and search optimization

An Efficient Algorithm for Thresholding Monte Carlo Tree Search

NeurIPS 2026 · Learning theory and algorithms › Combinatorial and search optimization · approach: Monte Carlo tree search · 0 citations (OpenAlex)

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.

Proposes RD-Tracking-TMCTS, a ratio-based D-Tracking Track-and-Stop algorithm for thresholding MCTS that is asymptotically optimal and runs in O(D log K) per round.

Problem

Thresholding Monte Carlo Tree Search: decide whether the root value of a MIN/MAX tree with stochastic leaf rewards is at least a threshold θ, with δ-correctness and minimal expected sample complexity.

Approach

Replace D-Tracking's arg max of t·w − N with a ratio criterion arg max w/N, avoiding oversampling after convergence, and exploit the recursive tree structure of the optimal allocation to update the sampling choice along a single root-to-leaf path in logarithmic time.

Key results

• RD-Tracking-TMCTS converges to the asymptotic lower bound significantly faster than D-Tracking, C-Tracking, UGapE-MCTS, LUCB-micro and round-robin on 3-ary trees of depths 2-5.
• The ratio-based draw reduces empirical sample complexity by several factors compared with the original D-Tracking rule.
• No incorrect outputs were observed in 1000 trials per setting across delta from 1e-5 to 1e-60.

Surprising findings

• The original D-Tracking can keep oversampling a leaf well beyond its optimal allocation even after the empirical means have converged.

Limitations

• Theoretical guarantees rely on the assumption that the optimal weight vector is unique and that V_{s0}(mu) differs from theta.
• The O(D log K) time bound holds for balanced trees where leaves are Theta(K^D).
• Experiments are limited to synthetic complete 3-ary trees with a fixed threshold setting.

Experimental setup

Benchmarks: randomly generated complete 3-ary trees of depth 2-5

Metrics: ratio of average stopping time to asymptotic lower bound empirical correctness rate

Baselines: D-Tracking C-Tracking UGapE-MCTS LUCB-micro round-robin

Builds on: Track-and-Stop D-Tracking GLR stopping rule UGapE LUCB

Closest papers by meaning

• Monte-Carlo Tree Search by Best Arm Identification (NeurIPS 2017 · similarity 0.91)
• Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction (NeurIPS 2023 · similarity 0.89)
• Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.87)
• $\epsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search (NeurIPS 2026 · similarity 0.87)
• Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.85)
• Sample-and-Bound for Non-convex Optimization (AAAI 2024 · similarity 0.85)