最小见证强化学习 Minimal Witness Reinforcement Learning

完整流程如下，输入为 ground set $E$、谓词 $s_c$、策略 $\pi_\theta$、组大小 $K$、测度 $\mu$。(1) 采样：每次更新对上下文 $c$ 独立采 $K$ 条轨迹得终端子集 $S_1,\ldots,S_K$（MaxSAT 从空集加变量，horizon 12；电路从全集删组件，horizon 等于组件数）。(2) 验证：每个终端调用一次验证器得 $y_i = s_c(S_i)$，此外不再调用。(3) 证域：$U_K = \bigcup_{j: y_j = 1} \uparrow S_j$，$U_{-i}$ 为去掉第 $i$ 条后的证域。(4) 删除信用：$A_i = R(U_K) - R(U_{-i})$；当组最小成功数超过 12 时，用共享样本蒙特卡洛替代指数级容斥：从 $\mu$ 抽 $N$ 个集合 $T^{(m)}$，$\hat{A}_i = \frac{1}{N} \sum_m \mathbf{1}[T^{(m)} \supseteq S_i] \prod_{x \in D_i} \mathbf{1}[T^{(m)} \not\supseteq x]$，单个提案开销 $O(N|D_i|)$ 且无额外验证器调用；$N = 20000$ 时信用向量与精确枚举的余弦达 0.998。(5) 基线与缩放：l2o 基线 $b_i = R(U_{-i}) - \frac{1}{K-1} \sum_{j \ne i} R(U_{-i,-j})$，$\tilde{A}_i = A_i - b_i$，再按组均值绝对值缩放。(6) 梯度上升：最大化 $J_K(\theta) = \mathbb{E}[R(U_K)]$，$\nabla_\theta J = \mathbb{E}[\sum_i \tilde{A}_i \sum_t \nabla_\theta \log \pi_\theta(a_{i,t} \mid x_{i,t})]$。可枚举小实例上用值迭代替代学习：在 $(F, b)$ 上回溯 $V_b^*(F) = \max_{s(S)=1} [\Delta R(S \mid F) + V_{b-1}^*(F \cup {\uparrow}S)]$，不固定预算执行至最大边际为零，命题 1 保证每步选中一个新的反链成员、$|\mathcal{M}(c)|$ 步收敛。部署时冻结策略采 $B$ 个提案，去重统计恢复的见证数。

技术新颖性体现在四个层面。第一，问题层面：首次把“从验证器位恢复最小见证反链”形式化为可学习的 RL 目标，把强化学习从单解优化扩展到“解族学习”，并给出十余类可套用同一接口的现实设置（Table 17）。第二，理论层面：一组完整刻画——定理 1 证明三大类现有目标必然失败；定理 2 给出组值表示定理（任何忽略重复/冗余成功的对称组值必是证域函数）；定理 3 证明覆盖回报本质不可分离；命题 2 刻画几何测度是唯一秩均匀精炼的测度族；定理 5 证明计数测度在有限预算 $K$ 下唯一最优分布是反链上的均匀分布 $p_m^* = 1/L$；定理 6 给出渐近恢复条件（每个见证质量 $\ge \epsilon$ 时，$K$ 组以概率 $\ge 1 - L e^{-K\epsilon}$ 含完整反链）。第三，算法层面：删除信用等价于次模覆盖函数的边际增益，共享样本蒙特卡洛把指数级容斥降为 $O(NK)$ 且不增加验证器调用；l1o/l2o 估计器的偏差分析表明组均值中心化有有限 $K$ 偏置而 l2o 无偏。第四，概念联系层面：证明几何测度下覆盖回报与多目标优化中的超体积指标（hypervolume）在子集格上等价（差一个常数），把“独占贡献”概念迁移到验证器学习场景。

独立分析四个弱点。一、非单调验证器下的理论缺口：当验证器以 0.56–0.83 的概率拒绝已接受集合的超集时，“一次接受等于证书整个上闭集”的解释坍塌，删除信用比较的只是原始验证位的包含关系，恢复的集合可能只是 1-minimal 而非真正最小。改进方向：训练时引入存在闭包 $s_\exists(S) = \mathbf{1}[\exists Q \subseteq S: s(Q)=1]$ 的采样修正，或学习验证器的单调代理模型并对残余违反率给出置信界。二、信用视野限于单个组：删除信用只在同一组 $K$ 个样本间比较，跨更新没有记忆，发现慢且要求大 $K$。改进方向：引入持久 archive（如 MAP-Elites 式保存历史证书区域），把历史成功并入 $U$ 再计算新样本的信用，等效组大小可放大数个量级。三、验证成本：每个终端提案一次完整验证（电路验证需 $P$ 次模型前向；湿实验室对应真实实验），且失败样本的排除信息（失败排除 $\downarrow S$）完全未被目标函数利用。改进方向：对失败也建模（覆盖-排除双目标）、验证器缓存与跨上下文迁移、训练廉价代理验证器并定期用真实验证器校准。四、$\mu$ 的先验依赖：不同 $\mu$ 给出不同的恢复优先序，可能把领域无关偏置注入“解释”，论文只扫了一维参数 $p$。改进方向：报告对完整测度族的敏感性，或在多个 $\mu$ 下取恢复结果的稳健交集作为高置信见证。

作者提出的方向：把 MWRL 部署到 Table 17 列出的领域——攻击图中防御者需要封堵全部最小攻击路径、最小权限分析需要枚举让集成测试通过的全部最小权限集、RAG/长上下文的证据最小化、训练数据归因（哪些样本子集足以诱导某行为，验证靠重训）、代谢设计（FBA 基因敲除）、联合用药与生物标志物面板；湿实验室部署时把查表验证器换成贝叶斯优化加真实实验测量；把 8B 实验的三层层级搜索推广到更深的任务分类。基于成果可延伸的方向：把删除信用作为辅助目标加进 RLVR/GRPO 训练，使 LLM 在可验证任务上学习“充分答案的反链”而非单一答案，与 pass@k 与多样性文献直接对接；在机制可解释性中把反链作为“解释的多重性”的正式对象，回应可识别性争议（Méloux et al. 2025）；用 MWRL 的组值替代局部奖励训练 GFlowNet，兼得比例采样与关系信用；用领域先验（组件失效率、检索概率）设定 $\mu$ 或跨上下文元学习 $\mu$；理论上把定理 1 推广到近似单调与非平稳验证器，并研究反链规模随上下文增长的样本复杂度。

复现条件较好。代码开源：github.com/TSUITUENYUE/MWRL。三个实验的数据与配置均有详细说明。MaxSAT 基准完全可枚举（$n=14$、8 个公式、全部 $2^{14}$ 状态可遍历验证；训练配置 Table 8：每公式 57,600 次验证调用 = 150 更新 × 8 组 × $K=48$，Adam lr $3\times10^{-3}$，评估 128 提案），最容易复现。Suzuki 基准随文释放：1024 个任务、每任务 2879 行、共 2,948,096 行的闭世界反应表、33 维底物指纹、明确的发布验收标准（反链 2–80 个成员、popularity audit ≤ 0.45）与训练协议（4,800 更新，评估存储 128 rollouts 使任何预算下的指标可重算）；依赖 ChemRANG 目录 commit dc0a14b 与机理模拟器，作者明确标注增强数据是“锚定真实反应的模拟输出”而非实测产率，完整重建基准生成过程比跑训练更费劲。LM 实验用公开的 Qwen3-1.7B/8B 与 MMLU：1.7B 配置为 476 组件、每主题 $K=12$、10 组 × 40 更新 = 4,800 次验证调用，单张 NVIDIA L40 即可完成，算力门槛低是明显优点；8B 层级实验需要三轮 warm-start 训练（每轮 $K=10$、3 组 × 8 更新）。难点在于工程实现：子集格 MDP、共享样本蒙特卡洛信用、激活修补验证器、以及 EAP 归因与 ACDC 等 interpretability 基线的工具链。