Jun 2026· arXiv.org· Vol abs/2606.01708· 1 citation· 47 references
Computer Science
TL;DR
2FFS is proposed, a two-fidelity tree-search algorithm that brings multi-fidelity flat bandit ideas into trees and proves fixed-confidence correctness, establish finite stopping for exact identification, and give a polynomial-depth cost upper bound for general-depth trees.
Abstract
We study fixed-confidence best-action identification (BAI) in stochastic minimax trees. This problem is increasingly relevant in modern AI planning, where deep minimax search and Monte Carlo Tree Search (MCTS) with language model long rollouts face a fundamental tradeoff: heuristic evaluations are cheap but biased, while accurate rollouts are reliable but prohibitively expensive. We propose 2FFS, a two-fidelity tree-search algorithm that brings multi-fidelity flat bandit ideas into trees. The algorithm combines minimax-style fast expansion with MCTS-style stochastic sampling, adaptively deciding when to exploit cheap biased evaluations and when to invoke expensive accurate evaluations for local certification. We prove fixed-confidence correctness, establish finite stopping for exact identification, and give a polynomial-depth cost upper bound for general-depth trees. Across numerical stochastic-tree experiments, 2FFS uses substantially fewer samples and computational operations comparing to existing BAI-MCTS baseline.
Experiments on stochastic planning benchmarks show that distributional Q-edges improve lower-tail return and reduce catastrophic outcomes when mean-optimal and risk-sensitive behavior differ, and two distributional MCTS algorithms that maintain finite-support empirical backup laws at Q-edges are introduced.
Q. Trinh, T. Nguyen, N. Nguyen et al.· 0 citations
A new robust variant of MCTS that mitigates dynamical model ambiguities to bridge the gap between simulation-based planning and real-world deployment and empirical evidence is provided that this method achieves robust performance in planning problems even under significant ambiguity in the underlying reward distributio...
Tuan Dam, Kishan Panaganti, Brahim Driss et al.· International Conference on...· 6 citations· ⚡1
Decoupled Marginal Sharpening (DMS) is proposed, which separately controls how strongly the model favors particular reasoning paths and how strongly it favors final answers after aggregating support across those paths.
Wei-Xin Wang, Wei Deng, Anderson Schneider et al.· 0 citations
Modern LLM training increasingly relies on heterogeneous data sources spanning different domains, tasks, preference distributions, and difficulty levels. We study dynamic minimax regret for group-distributionally robust LLM post-training under instantaneous mini-batch-only bandit feedback. The framework views the train...
Cheng-Bo Zang, Hao-Yu Dong, Mehmet Kerem Türkcan et al.· 0 citations
Conformal Interval-Driven Self-Evolution (CISE) is proposed, which constructs candidate-specific reward intervals using conditional conformal inference and iteration-wise online density-ratio estimation and returns candidates only when all required property intervals lie entirely within their respective feasible region...
This work proves instance-dependent, finite-budget exponential bounds on posterior-failure probability that capture both separation from unfavorable arms and the presence of multiple favorable arms and establishes an asymptotic sample-complexity lower bound that HTG matches up to a logarithmic factor.
Yi-Nan Li, Kwang-Sung Jun, Kapilan Balagopalan et al.· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduOct 13, 2026
Machine-learning networks can learn without detailed instructions from a designer. Those that do may offer insight into how the brain reorganizes itself during learning.
MIT News · Artificial Intelligence· news.mit.eduSep 29, 2026
Professor Sherry Turkle’s new book, “Artificial Intimacy,” offers a withering critique of chatbots and the antisocial dynamics she believes they encourage.