Skip to content

Two-Fidelity Best-Action Identification for Stochastic Minimax Tree

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.

View source

Similar papers

#machine learning Preprint Oct 2026

Beyond Expected Values: Risk-Sensitive Planning with Distributional Monte-Carlo Tree Search

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
#artificial intelligence Conference Sep 2026

Online Robust Reinforcement Learning Through Monte-Carlo Planning

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. · 6 citations · ⚡1
#machine learning Preprint Oct 2026

Decoupled Marginal Sharpening for Training-Free Inference-Time Scaling

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
#machine learning Preprint Oct 2026

Dynamic Minimax Regret Optimization for Robust LLM Post-Training

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
#small language model Preprint Oct 2026

Reliable Self-Evolution with Imperfect Proxy Rewards

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...

Kangjun Noh, Soyu Kim, Kyungwoo Song · 0 citations
#machine learning Preprint Oct 2026

Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

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 Sep 29, 2026

Who we become when we talk to machines

Professor Sherry Turkle’s new book, “Artificial Intimacy,” offers a withering critique of chatbots and the antisocial dynamics she believes they encourage.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.