随机极小极大树中双保真度最优动作辨识算法 Two-Fidelity Best-Action Identification for Stochastic Minimax Tree
提出2FFS算法，统一极小极大扩展与MCTS采样以高效辨识最优动作。
前置知识
极小极大树（Minimax Tree）
一棵内部节点交替承担 MAX 与 MIN 角色的有限根树，叶子有均值收益 $\mu_\ell$，节点价值通过 $V^*(v) = \max_{u\in Ch(v)}V^*(u)$（MAX）或 $\min_{u\in Ch(v)}V^*(u)$（MIN）逐层向上传播，常用于双人零和博弈规划。
极小极大树是 $\alpha\text{-}\beta$ 剪枝搜索与 MCTS 的共同抽象，2FFS 算法就在该树结构上同时复用快速启发式和精确采样，是后续算法伪码的基础。
固定置信度最佳动作辨识（BAI）
在给定 $(\epsilon, \delta)$ 的设定下，算法必须以 $\geq 1-\delta$ 的概率输出与最优动作价值差不超过 $\epsilon$ 的根动作，同时最小化总采样代价，是 bandit 文献中的标准框架。
本文沿用 BAI 的 $(\epsilon, \delta)\text{-PAC}$ 准则与同时有效性事件 $E_\delta$，Theorem 3.1 的正确性证明完全建立在 $\max_a \underline V_a \geq \max_{b\neq a}\overline V_b - \epsilon$ 的根停止规则之上。
多保真度老虎机（Multi-Fidelity Bandit）
为每个臂提供多个保真度查询接口，廉价保真度样本便宜但有偏，昂贵保真度样本准却开销高，算法需自适应决定何时调用哪个保真度以最小化辨识代价 $H^*$。
本文将平坦动作空间下的多保真度思想首次推广到树结构，使快速 oracle 的有偏估值与慢速 oracle 的 $\sigma$-sub-Gaussian 样本在节点层面统一为两个查询源。
蒙特卡洛树搜索（MCTS）
通过反复对叶节点随机 rollout 后用 UCB 类策略在树上分配仿真次数的搜索范式，可在确定性估值难以获得时获得无偏动作价值估计，BAI-MCTS 是其固定置信度对应版本。
2FFS 与 BAI-MCTS 都是用随机采样替代确定性评估的搜索范式，对比基准中 BAI-MCTS 显示 2FFS 比单纯采样型树搜索节省 $160$–$1450\times$ 采样量。
同时置信区间与二进位尺度（Dyadic Scale）
同时有效性（simultaneous validity）保证所有节点的有效区间同时包含真值，二进位尺度 $\rho_{k+1}=2\rho_k$ 用倍增递增的精度网格在不预知 $H^*$ 时按精度档分层精化节点。
2FFS 在不知道有效缺口 $\Delta_v^{eff}$ 的情况下，依赖二进位网格 $\rho_k$ 与 scale-$k$ 安全的比较/选择子规则 $Comp^L_u$、$Comp^U_u$ 来决定何时停止。
研究动机
在两人零和规划、多智能体强化学习以及大语言模型长链推理（long chain-of-thought）中，决策者面临经典的预算分配权衡：是花算力把搜索树沿极小极大方向推得更深，还是在已暴露的前沿节点上反复精确化价值估计？极小极大风格搜索（如 $\alpha\text{-}\beta$）依靠快速启发式深扩但估值有偏；MCTS 风格搜索（如 BAI-MCTS）通过对叶节点的不偏采样换取收敛性却带宽很高。两端单边极端化都不可取：当 BAI-MCTS 在深度 $3$、分支 $10$ 的 $1111$ 节点小树上已需要约 $10^5$ 级样本时，慢采样会成为不可承受的成本；而纯快速估值（Minimax-fast）在多组实验中精度仅 $0.88$–$0.91$，因为快速 oracle 的偏差由 $B(h(v))$ 包络给出且随深度放大。
本文的目标是本文目标是在随机极小极大树上提出 $(\epsilon, \delta)\text{-PAC}$ 的最优动作辨识算法 2FFS：让算法自适应比较两条路径——以廉价但有偏的快速 oracle 沿树递归展开，或直接调用昂贵但无偏的慢速 oracle 对当前暴露节点做局部认证——并在固定预算 $\delta$ 下使总成本 $C_\tau = N_F(\tau) + c\sum_v N_v^S(\tau)$ 与理想递归 oracle 复杂度 $H^*$ 同量级。
与已有工作不同的是，已有工作分别在平坦动作空间下研究多保真度 bandit（MF-MAB 文献 $[1\text{–}4]$）和在树上研究单 oracle 的 BAI-MCTS $[5]$，但把两种保真度信息源放进极小极大树的统一框架仍是空白。本文首次把多保真度 bandit 思想与 minimax/MCTS 树搜索融合，给出一个既不假设知道有效缺口也不预知便宜路径、最终代价上界为 $O_{\Lambda}(D^2 H^*)$ 的算法。
核心方法
2FFS 是一个把多保真度思想嵌入 minimax 树的双保真度固定置信度搜索算法。直觉上，对每个已暴露的非根节点 $v$，算法并存两种估值：确定性快速区间 $I_v^F = [V_F(v)-B(h(v)), V_F(v)+B(h(v))]$ 与基于 $\sigma$-sub-Gaussian 慢样本的运行交集 $I_v^S(t)$，二者相乘得直接局域区间 $I_v^{loc}$；再与子节点 minimax 回溯得到的 $I_v^{ch}$ 取交，形成同时有效的有效区间 $I_v(t) = I_v^{loc}(t) \cap I_v^{ch}(t)$。算法在不知道有效缺口 $\Delta_v^{eff}$ 与便宜路线的前提下，通过倍增精度网格 $\rho_0, \rho_1=2\rho_0,\ldots$ 与递归求解器 RESOLVE$(v,s,k)$ 在两条路线间调度，递归预算被夹在 $B_{recv,k}=\alpha_{h(v)}\Gamma_v^{(k)}(\delta_v)$ 内，$\alpha_h=(h+1)^2$ 保证深度只带来多项式级开销。
核心创新是「局域可逆 + 倍增尺度」设计：在已经扩展的节点上 2FFS 仍可对 $v$ 取慢样本，使算法不需事前承诺哪条路线便宜；通过倍增尺度 $\rho_k$ 与比较/选择子规则（Figure 1 右栏四个子情形），算法在 $(v,s,k)$ 上做「比较时让孩子离开」式的懒惰剥离，只继续精化当前最影响父节点证书 $\sigma\text{-}\beta_v(n, \delta_v)$ 的活孩子，从而把递归调用的 scale 不超过父节点的 $k$，整体开销在 Lemma 3.5 的 $P_D$ 递归下被压成 $O_{\Lambda}(D^2)$，比单 oracle BAI-MCTS 节省了 $160$–$1450\times$ 采样。
方法步骤详情
初始化时对根的全部子节点发快速查询并回溯得到初始有效区间，若 $\rho_0=0$ 立即停。主循环（Algorithm 1 第 $3\text{–}8$ 行）检查是否存在 $\hat a$ 满足 $L_{\hat a}\geq \max_{a\neq\hat a} U_a - \epsilon$，不满足则令领导 $a_t = \arg\max_a L_a$ 与挑战者 $b_t = \arg\max_{a\neq a_t}U_a$，选取二者中较粗的未决根端后转入 RESOLVE$(x,s,k)$。RESOLVE 先判端点证书 $Comp^s(v,k,t)$ 是否成立：是则直接返回；若 $v$ 为叶或递归预算耗尽则取一次慢样本；若 $v$ 未展开且展开后仍可在剩余预算内则展开、对其子发快速查询；否则按图 1 右栏四子情形选活孩子，在不超过 $k$ 的 scale 上递归调用，孩子因父 cap 被挡则上抛，被 $v$ 自身预算挡住则在 $v$ 处取一次慢样本。
技术新颖性
技术上，本文是首次在 minimax 树结构中给出多保真度 bandit 的理论框架：在 Lemma 2.3 用 $\beta_v(n,\delta_v)$ 浓度不等式构造同时有效性事件 $E_\delta$，在 Definition 2.4 递归定义有效缺口 $\Delta_v^{eff}$ 而非常规的 sibling gap，避免在不会影响根决策的子树上过度精化，并以 Eq. (7)–(8) 给出理想递归 oracle 复杂度 $H^*$ 作为分析参照。Theorem 3.6 用三步计费（证书可信、仅精化影响父证书的活孩子、每个 $(v,s,k)$ 一次性计费）将实际开销归约到 $P_D H(\delta)$，再用 $\alpha_h=(h+1)^2$ 把 Lemma 3.5 中 $P_D$ 的递归封闭为 $O_{\Lambda}(D^2)$，从而得到 $C_\tau \leq O_{\Lambda}(D^2)(H^*+\eta)$，这是树结构多保真度设置下的首个一般深度代价上界。
实验结果
在 (D=5, b=8)、(D=7, b=6)、(D=10, b=3) 三种平衡 $b$-叉随机极小极大树上各生成 $100$ 棵测试，2FFS 三组均取得 stopping$=1.00$、accuracy$=1.00$，相比 BAI-MCTS 把采样数从 $8.80\times 10^5/1.75\times 10^7/1.91\times 10^7$ 降到 $5.39\times 10^3/1.77\times 10^4/1.31\times 10^4$，减少 $163\times/989\times/1458\times$，操作数减少 $2.8\times/4.6\times/1.9\times$。Minimax-fast 精度仅 $0.88$–$0.91$，Slow-only 停止率仅 $0.47$–$0.77$，两侧消融证实自适应路线选择的必要性。图 2 显示在快速偏差 $0.30\to 0.60$、慢噪声 $0.005\to 0.050$ 区间内 2FFS 的采样与操作数均平稳波动，证实算法对中等 oracle 误差不敏感。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| D=5, b=8 stochastic minimax tree (37,449 节点) | Sampling count (均值±标准差) | $5.39\times 10^3 \pm 1.27\times 10^3$ | BAI-MCTS $8.80\times 10^5 \pm 3.39\times 10^5$ | 约 $163\times$ 采样数下降，accuracy 同时由 $0.99$ 升到 $1.00$ |
| D=7, b=6 stochastic minimax tree (335,923 节点) | Sampling count | $1.77\times 10^4 \pm 2.64\times 10^3$ | BAI-MCTS $1.75\times 10^7 \pm 6.71\times 10^6$ | 约 $989\times$ 采样数下降，stopping 由 $0.98$ 提升到 $1.00$ |
| D=10, b=3 stochastic minimax tree (88,573 节点) | Sampling count | $1.31\times 10^4 \pm 2.34\times 10^3$ | BAI-MCTS $1.91\times 10^7 \pm 4.19\times 10^6$ | 约 $1458\times$ 采样数下降，accuracy 由 $0.98$ 升到 $1.00$ |
| 三组设置平均 Operation count | Operation count | $8.38\times 10^7 / 1.06\times 10^9 / 2.49\times 10^9$ | BAI-MCTS $2.38\times 10^8 / 4.85\times 10^9 / 4.62\times 10^9$ | $2.8\times / 4.6\times / 1.9\times$ 计算开销减少 |
| Minimax-fast 与 Slow-only 消融对照组 | Stopping / Accuracy | 2FFS 三组均为 $1.00 / 1.00$ | Minimax-fast 精度仅 $0.91/0.88/0.90$；Slow-only 停止率仅 $0.47/0.73/0.77$ | 同时优于两个极端基线，体现快-慢路线自适应选择的必要 |
局限与改进
作者明示的限制包括：(1) Assumption 3.3 需要节点 $v$ 满足局部二进位规则性 $\Lambda_{pre}\geq 1$、$\Lambda_{gap}\geq 1$，在快速 oracle 偏差刚好跨过 $\rho/4$ 边界时 knife-edge 情况被排除；(2) 代价上界含 $O_{\Lambda}(D^2)$ 的深度因子，对非常深或非常浅且高度不平衡的树仍可能保守；(3) 实验只在合成随机极小极大树上评估，没有把 LLM 推理、围棋等真实两方博弈作为外部验证；(4) 当 $| ext{Ch}(r)|=1$ 平凡设定被显式排除。本文额外的观察是：论文并未报告单次实验的墙上时间，$5\text{–}6\text{–}7$ 阶节点上操作计数差距虽然只有 $1.9$–$4.6\times$ 但实际常数实现仍有优化空间，且 BAI-MCTS、UGapE-MCTS、LUCB-MCTS 等的复现实现没有开源，可能影响对比公平性。
独立分析的弱点
独立观察到的可改进点：(1) 工程实现层面，算法对小树的 $\rho_k$ 初始化只用根子快速查询的 spread，对快速 oracle 偏差较大或非平衡分支场景下初始 $\rho_0$ 可能太大，从而浪费前期尺度档，建议用一次预热慢样本校正 $\rho_0$；(2) $\alpha_h=(h+1)^2$ 的 $O(D^2)$ 因子在 $D$ 显著大于 $b$ 时仍偏高，可以探索与分支因子 $b$ 解耦的预算分配，例如 $\alpha_h = b^{\eta h}$ 配合 $b^{h}\rho_k$ 的几何化尺度；(3) 当前递归 RESOLVE 中孩子调用受父 cap 阻塞时只能向上传播 blocked 状态，无法局部换路线修复，可改为「按需降一档 scale」以减少向上反弹；(4) 比较基线只对比采样型 BAI，没有把多保真度平坦 bandit（如 MF-UCB、MF-Successive Elimination）放进同一 minimax 树上评估 $H^*$，无法直接验证上界的紧度。
未来方向
作者在 Conclusion 与 Appendix A 中讨论的可拓展方向：把 2FFS 推广到超过两个保真度（多保真度 bandit 在树中），直接嵌入 LLM 长 chain-of-thought rollout 与多智能体强化学习博弈；后续研究也可以基于本文 $(\epsilon, \delta)\text{-PAC}$ 框架转向 $(\epsilon, \delta)$ 之外的 budgeted 或 Bayesian 设定；理论层面，$\Lambda_{pre}\Lambda_{gap}$ 是问题相关的常数，进一步工作是给出与节点缺口 $\Delta_v^{eff}$ 解耦、依赖 $H^*$ 自身结构信息（如信息论 characteristic time）的紧上界；从经验上，把同一管线放到 9 路围棋、Liu 等开源博弈或 AlphaProof 风格的程序化对手上，验证「cheap heuristic + expensive rollout」在真实长链推理任务上的收益。
复现评估
本文为 arXiv 预印本「Under review」，未提供公开代码仓与 seed。算法骨架由 Definition 2.1–2.3 完全可重建：$(D,b)\in\{(5,8),(7,6),(10,3)\}$ 各 $100$ 棵合成树，慢 oracle 用 $\sigma$-sub-Gaussian 噪声注入真实 minimax 值即可重现表 1 数量级；Theorem 3.6 中 $P_D = O_{\Lambda}(D^2)$ 由 Lemma 3.5 闭式给出，可符号计算重建。BAI-MCTS、UGapE-MCTS、LUCB-MCTS、FindTopWinner 没有官方实现，需自行实现并假定慢/快 oracle 比例 $c$ 与 concentration radius $\beta_v(n,\delta_v)$ 与原文一致，操作常数差异可能使操作数与作者报告差 $1\text{–}2\times$。总体而言算法逻辑可复现但缺开源代码与细节，第一方验证难度较高。
论文图表
