用低成本高偏差与高成本低偏差评估结合，高效找到最优动作。
Two-Fidelity Best-Action Identification for Stochastic Minimax Tree
- 结合快速展开与随机采样，动态选择使用廉价评估或昂贵验证。
- 在有限样本下实现精确最优动作识别，计算开销仅为基线的一小部分。
- 适合需要高效规划的AI系统，如语言模型驱动的博弈决策场景。
我们研究随机极小极大树中的固定置信度最优动作识别（BAI）问题。该问题在现代AI规划中日益重要：深度极小极大搜索与基于语言模型长轨迹的蒙特卡洛树搜索面临根本权衡——启发式评估廉价但有偏，而准确轨迹代价高昂。本文提出2FFS算法，将多保真度平坦贝叶斯优化思想引入树结构。该算法结合极小极大风格的快速扩展与MCTS风格的随机采样，自适应决定何时利用廉价有偏评估，何时调用昂贵可靠评估进行局部验证。我们证明了固定置信度正确性，建立了精确识别的有限停止性，并给出了通用深度树的多项式深度代价上界。在多个数值随机树实验中，2FFS相比现有BAI-MCTS基线显著减少采样次数与计算量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。