NeurIPS2026（任务队列标注；缓存正文未提供录用信息）学习理论强化学习最优动作识别双保真评估极小极大树固定置信度预算分配

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

会议: NeurIPS2026（任务队列标注；缓存正文未提供录用信息）
arXiv: 2606.01708
代码: https://github.com/PeterLauLukChen/2FFS
领域: 学习理论 / 强化学习
关键词: 最优动作识别、双保真评估、极小极大树、固定置信度、预算分配

一句话总结¶

2FFS 在已知快评估偏差包络、慢评估对节点真实 minimax 值无偏的模型下，用端点证书和递归预算自适应选择扩树或采样，在合成树上保持高准确率并显著减少节点访问，而停止与成本保证需要额外正则条件。

研究背景与动机¶

在交替 Max/Min 的对抗搜索树中，根动作好不好，取决于后续双方最优应对，而不只是一次随机轨迹的收益。传统 minimax 搜索通过廉价启发式评估向深处展开；MCTS 与 BAI-MCTS 则依靠反复随机采样控制不确定性。前者扩得快，但对有偏点估计做极值传播可能选错动作；后者有统计依据，却可能把大量预算花在昂贵的叶节点采样上。

多保真 bandit 已经研究“便宜但有偏”和“昂贵但准确”的评估分配，但平坦臂集合没有树中的交替极值传播。同一个子节点的不确定性是否重要，要同时看它在父节点中的作用和它能否改变根动作比较。本文要解决的不是训练一个更好的 critic，而是给定两类 oracle 后，判断某个决策关键节点应该继续向下展开，还是就地购买更可靠的信息。

作者把两条路线都保留下来：扩过的节点仍能接受慢采样，已经收集的本地证据也不会因扩树而丢失。核心 idea：用有效置信区间保证推荐可靠，再以尺度受限的端点证书和递归预算，将计算集中到仍可能改变根动作的分支，并在扩树不划算时回退到本地慢采样。

方法详解¶

整体框架¶

输入是一棵有限、等终止深度的 minimax 树、两类节点评估 oracle、已知快评估偏差包络、节点置信度分配和目标误差。根为 Max，内部节点交替 Max/Min；输出是一个通过区间分离检验的根动作，而不是整棵树的精确值函数。

2FFS 首先快评估所有根孩子，维护由本地信息和孩子信息共同约束的区间。随后通过“有效区间融合 → 根端点调度 → 预算双路线求解”循环，决定在哪个节点、哪个端点、哪个精度尺度上增加证据。这里没有教师网络或梯度训练；图中的 oracle 边是搜索时的观测信息，不是训练监督。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    T["有限 minimax 树"] --> I["有效区间融合"]
    F["快 oracle<br/>确定值与偏差包络"] -.->|搜索观测，非训练监督| I
    S["慢 oracle<br/>节点值随机观测"] -.->|搜索观测，非训练监督| I
    I --> R["根端点调度"]
    R -->|尚未分离| Q["预算双路线求解"]
    Q -->|扩树快评估或本地慢采样| I
    R -->|区间分离| O["推荐根动作"]

关键设计¶

1. 有效区间融合：让偏差约束和统计证据共同限制节点值

快 oracle 在任意已暴露非根节点返回确定性估计，其误差不超过剩余深度对应的已知包络。包络随剩余深度非递减，并且满足 \(B(0)=0\)，所以叶节点一旦暴露，快评估就揭露真实叶均值。这是模型假设，不是一般神经启发式自然拥有的性质。慢 oracle 则可以直接查询任意已暴露非根节点，重复观测独立、次高斯，均值等于该节点真实 minimax 值。普通策略 rollout 的均值通常是策略价值，不能直接当作这种 oracle。

快区间与慢置信区间不是做加权平均，而是取交集。慢区间本身是历次时间一致置信区间的运行交集，因此有效证据随时间收缩。给每个非根节点分配 \(\delta_v\)，总和不超过 \(\delta\)，便能用联合界控制所有节点、所有采样时刻同时失效的概率。

\[ I_v(t)=\underbrace{[V_F(v)-B(h(v)),\,V_F(v)+B(h(v))]\cap I_v^S(t)}_{I_v^{\mathrm{loc}}(t)}\cap I_v^{\mathrm{ch}}(t). \]

孩子信息向上传播时，Max 节点分别对下界、上界取最大值，Min 节点分别取最小值。未扩展节点的孩子区间视为无限区间。扩树后仍把原有本地证据与孩子回传取交集，既不丢掉此前慢采样，也允许父节点直接证据比孩子信息更紧。极值回传保持区间有效，不会像逐层累加误差那样扩大宽度。

附录 B.3 还规定空交集时立即返回预设默认动作，以定义失败路径上的行为。有效置信事件内不会发生这种退出；它不能被当成正常的最优性证书，错误概率已包含在置信失败事件中。

2. 根端点调度：只精化还可能改变推荐的单侧证书

根处以最大下界动作作为 leader，以其余动作中最大上界者作为 challenger。停止条件是某个动作的下界已经超过所有竞争动作的上界减去容许误差：

\[ L_{\hat a_t}(t)\geq\max_{a\neq\hat a_t}U_a(t)-\varepsilon. \]

未分离时，算法比较 leader 下侧与 challenger 最粗未完成侧的尺度，优先处理更粗的义务。challenger 既可能被排除，也可能成为 leader，因此不能永远只精化它的上界。精度网格从初始根孩子最大区间宽度出发，每次减半；尺度 \(\rho_k\) 的单侧证书保证对应端点误差至多 \(\rho_k/2\)，不要求整段区间都同时达到这个宽度。

子树内部有两类规则。Min 的下侧与 Max 的上侧属于 selector：沿当前决定回传端点的孩子继续处理。Max 的下侧与 Min 的上侧属于 comparison：只保留仍阻碍尺度证书的孩子，每次处理端点最极端的 blocker。Max 下侧可以通过孩子上界落到“最大孩子下界加 \(\rho_k/2\)”以内而排除它，也可以通过孩子同侧证书使它完成；Min 上侧是对偶情况。

比较型 blocker 优先处理用于排除它的反侧端点，反侧已在允许尺度内完成后才处理同侧。孩子调用不得进入比父义务更细的尺度。证书一旦成立就锁存为完成标志，而区间单调收缩保证已获得的端点精度持续有效；因此不会因 blocker 切换而重复支付同一节点、同一侧、同一尺度的工作。

这种调度对应分析中的“有效间隙”：根设为最优与次优动作差，此后沿路径取已继承间隙与父子真实值差的最大值。大间隙意味着分支只需粗估就足以支撑根决策，而不是要求每个节点都精确到自身最小兄弟差。

\[ \Delta_r^{\mathrm{eff}}=\Delta_*,\qquad \Delta_v^{\mathrm{eff}}=\max\{\Delta_{p(v)}^{\mathrm{eff}},\,|V^*(v)-V^*(p(v))|\}. \]

真实间隙只用于分析，算法不预先知道它。附录证明实际活跃调用满足 \(\Delta_v^{\mathrm{eff}}\leq2\rho_k\)，且常数 2 不随深度增加；关键是递归不强迫孩子做比当前父任务更细的无关工作。

3. 预算双路线求解：保留就地认证，限制递归试探的损失

求解器在节点与尺度上先尝试递归路线：未扩展时暴露所有孩子并快评估，已扩展时按上述规则处理一个活跃孩子。它不是遍历全部孩子直到精确，也不是扩树之后永久放弃本地采样。慢采样的就地路线始终保留，用来在继续递归太贵时完成认证。

定义 \(\Gamma_v(\rho,\delta_v)\) 为节点已暴露之后的本地认证成本：若 \(B(h(v))\leq\rho/4\)，快区间已足够窄，成本为零；否则为 \(c\) 乘以慢置信半径首次降到 \(\rho/4\) 所需样本数。快查询单价为 1，慢查询单价为 \(c\geq1\)。节点在尺度上的递归消费上限为

\[ \mathsf B_{v,k}^{\mathrm{rec}}=\alpha_{h(v)}\Gamma_v(\rho_k,\delta_v),\qquad \alpha_h=(h+1)^2. \]

本节点递归预算不足以扩展或继续取得进展时，回退到一次本地慢查询。若只是祖先继承的调用上限不足，则返回 blocked，而不是擅自在孩子处改走会突破祖先预算的路线。每次调用最多执行一次正成本 oracle 动作，随后更新区间、端点和证书，再重新选择。这些区分是附录成本记账能成立的前提。

理论比较对象 \(J_v^*\) 在每个内部节点取两种参考成本的较小者：按真实有效间隙就地认证，或者支付所有孩子快暴露成本再加孩子参考成本。根参考复杂度 \(H(\boldsymbol\delta)\) 是根孩子初始化成本加各子树 \(J_a^*\)；\(H^*\) 是它在可行置信度分配上的下确界。它们是假设知道真实间隙的分析参考，并非信息论下界，也不是算法可直接读取的预算。

成本定理还要求本地双进尺度成本的前缀和受最后尺度成本控制，以及有效间隙缩小一半不会导致本地成本无限倍跳变。在有效置信事件、唯一最优根动作和这些正则条件下，精确识别有限停止，且加权 oracle 成本满足

\[ C_\tau=N^F(\tau)+c\sum_vN_v^S(\tau) \leq P_DH(\boldsymbol\delta),\qquad P_D=O_{\Lambda_{\mathrm{pre}},\Lambda_{\mathrm{gap}}}(D^2). \]

这里多项式的是相对于参考复杂度的深度开销；\(H\) 本身仍依赖树规模与间隙，不能说总搜索成本对指数大小的树自动变成多项式。改写成 \(H^*\) 量级还要求近最优置信度分配保持统一正则常数，并不意味着任意实用分配都达到该界。

一个完整示例¶

以下是解释两路线协作的自设数值示例，不是论文实验轨迹。考虑深度 3 的树，根有两个 Min 动作 A、B，真实值分别为 0.65、0.50。初始快区间为 A 的 \([0.45,0.85]\)、B 的 \([0.40,0.80]\)，此时 A 是 leader，但下界 0.45 不能压过 B 上界 0.80。

假设选中 A 下侧，且其递归预算允许暴露两个 Max 孩子。两个孩子真实值为 0.65、0.80，快区间分别为 \([0.55,0.75]\) 和 \([0.70,0.90]\)。Min 回传后，A 有效区间变为 \([0.55,0.75]\)；下侧 selector 会关注下界为 0.55 的孩子，而不是盲目继续认证第二个孩子。

B 的区间仍更粗。假设 B 孩子很多，在当前尺度下全部暴露的成本超过 B 自身剩余递归预算，求解器于是购买 B 的本地慢样本。经若干次查询，假设其运行慢区间收缩到 \([0.48,0.52]\)，与快区间相交后 B 上界变为 0.52。这里没有指定样本数，因为它取决于噪声、置信度及实际观测。

根随即有 \(0.55\geq0.52\)，在 \(\varepsilon=0\) 下推荐 A。算法并未求出 A 的精确值，也未展开 B 全部后代；“精确识别”指动作选对，不是每个节点值都精确。若 B 只受祖先调用上限阻塞，则应向上返回 blocked，不能套用本例的本节点预算回退。

损失函数 / 训练策略¶

本文没有可训练模型、优化损失或 policy-gradient 实验，核心是搜索时的置信度与预算调度。置信半径必须时间一致、随样本数不增并趋于零；只在某个固定采样数上成立的普通置信区间不足以覆盖自适应停止。

Theorem 3.1 控制的是“算法有限停止且返回超过 \(\varepsilon\) 误差动作”的无条件概率不超过 \(\delta\)。它单独不保证停止，也不能解释成给定停止条件后的错误概率一定不超过 \(\delta\)。有限停止与成本属于 Theorem 3.6 的附条件结论。

偏置慢 oracle 的理论扩展用已知点态偏差上界 \(\xi\) 扩大置信半径为 \(\beta_v+\xi\)，minimax 回传无需逐层再加 \(\xi\)；但半径不再必然趋零，原停止与成本证明不能直接沿用。快包络代理也必须逐深度覆盖真实包络；某个随深度变化的公式本身不能证明已完成校准。相同查询历史下更松包络只会放宽区间，但实际自适应运行可能改变路径，不能据此排序两次运行的成本。

实验关键数据¶

主实验¶

每种配置独立生成 100 棵平衡合成随机 minimax 树。慢 oracle 在真实 minimax 值上加噪声，因此直接实现了理论 oracle，而非通过真实游戏 rollout 验证其可获得性。下表来自原文 Table 1，计数为均值 ± 标准差。

深度 D / 分支 b / 总节点	方法	停止率	准确率	采样/访问计数	操作计数
5 / 8 / 37,449	2FFS	1.00	1.00	\(5.39\times10^3\pm1.27\times10^3\)	\(8.38\times10^7\pm4.05\times10^7\)
5 / 8 / 37,449	BAI-MCTS	1.00	0.99	\(8.80\times10^5\pm3.39\times10^5\)	\(2.38\times10^8\pm9.49\times10^7\)
7 / 6 / 335,923	2FFS	1.00	1.00	\(1.77\times10^4\pm2.64\times10^3\)	\(1.06\times10^9\pm3.02\times10^8\)
7 / 6 / 335,923	BAI-MCTS	0.98	0.98	\(1.75\times10^7\pm6.71\times10^6\)	\(4.85\times10^9\pm1.87\times10^9\)
10 / 3 / 88,573	2FFS	1.00	1.00	\(1.31\times10^4\pm2.34\times10^3\)	\(2.49\times10^9\pm8.64\times10^8\)
10 / 3 / 88,573	BAI-MCTS	0.98	0.98	\(1.91\times10^7\pm4.19\times10^6\)	\(4.62\times10^9\pm9.34\times10^8\)

sampling count 是总采样与节点访问计数，不是去重后的节点数量，也不是理论上按 \(c\) 加权的 \(C_\tau\)。operation count 以一次常数时间标量状态读写或比较为单位，衡量包含区间与证书维护的记账工作，不等于实测 wall-clock 时间。

消融实验¶

同一 Table 1 的控制基线分别去掉慢认证，或预先固定扩展深度后仅在 frontier 慢采样。它们检验双路线自适应的必要性，不是训练网络的模块移除实验。

深度 D / 分支 b	配置	停止率	准确率	采样/访问计数	操作计数
5 / 8	Minimax-fast	1.00	0.91	\(1.49\times10^4\pm3.35\times10^3\)	\(8.20\times10^5\pm1.91\times10^5\)
5 / 8	Slow-only	0.47	0.47	\(5.87\times10^5\pm4.86\times10^5\)	\(8.62\times10^7\pm7.15\times10^7\)
7 / 6	Minimax-fast	1.00	0.88	\(5.52\times10^4\pm7.08\times10^3\)	\(3.48\times10^6\pm4.59\times10^5\)
7 / 6	Slow-only	0.73	0.70	\(4.22\times10^6\pm9.16\times10^6\)	\(1.49\times10^9\pm4.13\times10^8\)
10 / 3	Minimax-fast	1.00	0.90	\(4.69\times10^4\pm5.67\times10^3\)	\(4.56\times10^6\pm5.81\times10^5\)
10 / 3	Slow-only	0.77	0.77	\(5.60\times10^6\pm8.98\times10^6\)	\(1.63\times10^9\pm4.22\times10^8\)

Figure 2 另报告深度 5、8 叉树的快偏差与慢噪声敏感性；正文给出的参数均值分别为 0.45、0.01，并定性称中等范围内较稳定。缓存没有可读取的曲线逐点数字，因此不补造扫描端点或误差条。

关键发现¶

按表中均值，2FFS 相对 BAI-MCTS 的采样/访问减少约 163、989、1,458 倍，操作减少约 2.84、4.58、1.86 倍；原文概述为约 160–1450 倍与 1.9–4.6 倍。后者是舍入摘要，不是额外实验。
少采样不等于同比例省算力。2FFS 每次观测还需维护快慢交集、尺度证书及比较集合，所以访问收益远大于操作收益。
Minimax-fast 的操作计数反而远低于 2FFS，但准确率仅为 0.88–0.91。不能将结果总结成“2FFS 对所有方法都计算更少”，其优势是可靠性与自适应效率的组合。
Slow-only 经常在有限预算内不停止；停止率与准确率分开报告，不能把 0.70 准确率直接当作“已停止样本中的 70% 正确”。正文未完整说明预算阈值及准确率分母处理。

亮点与洞察¶

双保真不只是混合两个分数，而是保留两种可认证证据并取交集。便宜信息即使有偏，只要偏差上界有效，也可以成为确定性的排除工具。
单侧证书比整区间认证更贴近决策需求。根选择只需 leader 下侧足够高、竞争者相关信息足够明确，无需将整棵树都估到统一精度。
局部可逆性避免过早押注扩树。已经投入递归的预算不会禁止之后就地慢认证，预算竞争限制了错误路线上的过度试探。
深度因子来自尺度同步和可累加预算记账，而非宣称树结构不再昂贵。这样的分析思路可启发其他层次化证书搜索，但必须重新证明任务自己的区间传播性质。

局限与展望¶

任意暴露节点的真实 minimax 无偏慢 oracle 是强假设；真实策略 rollout、神经 critic 或 LLM 评分通常不能直接满足。需要同时校准偏差与评估成本，而非只把它们重命名为 fast/slow。
已知快包络且叶端 \(B(0)=0\) 带来特殊信息优势。不同基线的 oracle 接口也不同：BAI-MCTS 使用随机叶采样，2FFS 可以在内部节点直接查询，因而实验并未隔离全部收益来源。
本地正则性在快偏差截止处可能失败。附录 B.8 明确指出，当 \(\Delta_v^{\mathrm{eff}}/8<B(h(v))\leq\Delta_v^{\mathrm{eff}}/4\) 时，间隙处成本为零而半间隙处为正，不能仅靠慢采样成本呈多项式增长证明条件成立。
§3.2 的 MARL 内容是偏置 oracle 与代理包络的理论鲁棒性扩展，附录 A 明确真实 MARL、policy-gradient 或神经引导 MCTS 实验不在本文范围内。没有真实游戏、LLM 或 MARL 实验支持部署结论。
原文将三类对比方案统称 fixed-confidence baselines，但 fast-only 的观测准确率低于 2FFS，且未展示它与 2FFS 同等的 PAC 认证；笔记保留该边界，不把 baseline 标签当成等价保证。
可探索动态树、progressive widening、未知包络在线校准以及更弱正则条件。不过未知校准失误如何进入总失败概率，需要独立分析，不能直接沿用本文定理。

评分¶

新颖性: 4/5 — 将双保真分配引入 minimax 端点认证，并提供递归预算分析。
实验充分度: 2/5 — 每配置 100 棵合成树及控制消融有依据，但缺真实环境与运行时间验证。
写作质量: 4/5 — 附录清楚区分正确性、停止与复杂度；实验预算和统计口径仍不够完整。
价值: 4/5 — 为成本敏感树搜索提供可复用的证书框架，实际价值取决于 oracle 与包络能否获得。