# Two-Fidelity Best-Action Identification for Stochastic Minimax Tree

arXiv: https://arxiv.org/abs/2606.01708 · HTML: https://mlsanity.com/paper/2606.01708/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 30 of 30)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [A System for Massively Parallel Hyperparameter Tuning](https://mlsanity.com/paper/1810.05934/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Multi-Fidelity Bayesian Optimization via Deep Neural Networks](https://mlsanity.com/paper/2007.03117/) (2020)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Exploration vs Exploitation: Rethinking RLVR through Clipping, Entropy, and Spurious Reward](https://mlsanity.com/paper/2512.16912/) (2025)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Stepwise Guided Policy Optimization: Coloring your Incorrect Reasoning in GRPO](https://mlsanity.com/paper/2505.11595/) (2025)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Monte-Carlo Tree Search by Best Arm Identification](https://mlsanity.com/paper/1706.02986/) (2017)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups](https://mlsanity.com/paper/1406.0486/) (2014)
- [Reward-free Alignment for Conflicting Objectives](https://mlsanity.com/paper/2602.02495/) (2026)
- [Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach](https://mlsanity.com/paper/1810.10482/) (2018)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Post-Training LLMs as Better Decision-Making Agents: A Regret-Minimization Approach](https://mlsanity.com/paper/2511.04393/) (2025)
- [Adaptive multi-fidelity optimization with fast learning rates](https://mlsanity.com/paper/2604.16239/) (2026)

## Built on by (most cited first, 1 of 1)

- [A Zeroth-Order Paradigm for LLM Preference Alignment](https://mlsanity.com/paper/2609.19144/) (2026)

## Abstract (arXiv)

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.