Search papers, labs, and topics across Lattice.
This paper addresses the challenge of best-action identification in stochastic minimax trees, a critical area in AI planning that balances the tradeoff between cheap but biased heuristic evaluations and costly yet accurate rollouts. The authors introduce 2FFS, a two-fidelity tree-search algorithm that integrates multi-fidelity flat bandit concepts, enabling adaptive decision-making on when to utilize fast expansions versus accurate evaluations. Experimental results demonstrate that 2FFS significantly reduces the number of samples and computational operations required compared to existing BAI-MCTS methods, while maintaining fixed-confidence correctness and polynomial-depth cost efficiency.
2FFS slashes the sample complexity of best-action identification in stochastic minimax trees, proving that efficiency and accuracy can coexist in AI planning.
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.
