Two-Fidelity Best-Action Identification for Stochastic Minimax Tree
Summary
The paper proposes 2FFS, a two-fidelity tree-search algorithm that adaptively balances cheap biased evaluations with expensive accurate evaluations in stochastic minimax trees for fixed-confidence best-action identification, with theoretical guarantees and experimental efficiency gains.
View Cached Full Text
Cached at: 06/15/26, 09:00 PM
Paper page - Two-Fidelity Best-Action Identification for Stochastic Minimax Tree
Source: https://huggingface.co/papers/2606.01708
Abstract
A two-fidelity tree-search algorithm is proposed that adaptively balances cheap biased evaluations with expensive accurate evaluations in stochastic minimax trees for fixed-confidence best-action identification.
We study fixed-confidencebest-action identification(BAI) instochastic minimax trees. This problem is increasingly relevant in modern AI planning, where deep minimax search andMonte 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 bringsmulti-fidelity flat banditideas 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 provefixed-confidence correctness, establishfinite stoppingfor exact identification, and give apolynomial-depth costupper 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 arXiv pageView PDFAdd to collection
Get this paper in your agent:
hf papers read 2606\.01708
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2606.01708 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2606.01708 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2606.01708 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
Improvise, Adapt, Overcome: An On-The-Fly Multifidelity Algorithm for Efficient Machine Learning
This paper introduces an adaptive on-the-fly multifidelity machine learning algorithm for quantum chemistry that autonomously determines training data composition across fidelities, reducing data generation costs by up to 30x compared to single-fidelity methods and up to 5x compared to standard multifidelity methods.
Optimal Top-$k$ Identification from Pairwise Comparisons
This paper addresses the fixed-confidence top-k identification problem from noisy pairwise comparisons, and develops an asymptotically optimal algorithm that minimizes the expected number of comparisons.
Measuring AI Faithfulness-For Better or For Worse
This article discusses the importance of faithfulness in LLM optimization, introducing a Structural Fidelity Score that measures drift across word overlap, constraint survival, and task-type match to ensure prompt optimization does not sacrifice intent.
@lateinteraction: very cool work !!
Guowei Xu discusses limitations of Best-of-N and tree search methods for LLMs on hard reasoning problems, noting sparse verification signals and that candidates remain within the model's distribution.
Look Before You Leap: Distilling Tree Search into Action Evaluation for Frozen VLA Models
Introduces SVA, a framework that decouples action generation from consequence evaluation in frozen VLA models using Monte-Carlo tree search and distillation into a lightweight Q-value model, improving generalization and task success rates while reducing computational costs.