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
Out-Of-The-Loop Multi-Fidelity Bayesian Optimization
The paper tackles multi-fidelity Bayesian optimization where the highest-fidelity function is too expensive to be part of the optimization loop, and proposes incorporating historical high-fidelity data with task descriptors. The method is demonstrated on synthetic functions, chemistry, and hyperparameter optimization tasks.
Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing
Introduces Tree-Coupled A/B Testing (TCAB), an exact feedback-sharing design for comparing multiple adaptive policies with fewer reward queries while preserving each policy's trajectory law.
Exploit More, Explore Smarter for Budget-Constrained Agentic Search
This paper introduces ExTS, a tree-search policy for budget-constrained agentic search in LLM agents that improves over standard baselines in tasks like prompt optimization and code generation with an average +5.5% gain.
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.