MARS2: Scaling Multi-Agent Tree Search via Reinforcement Learning for Code Generation

Idea

MARS2 将多个独立优化的 code-generation agents 放入同一 tree-search 环境，让不同 policy priors 在候选生成与修订中协作。训练不仅比较整棵树的节点分数，还奖励子节点相对父节点及兄弟节点的改进，使 structured search 本身成为学习过程。

Research Problem

普通 GRPO 的独立采样受单一策略先验限制，训练后探索容易集中到少数高概率路径；单 agent tree search 虽有结构，也难逃同源偏好。已有 multi-agent 方法常与搜索训练分离，且直接全局标准化节点奖励忽略父子依赖，无法充分分配协作贡献。

Insight

不同模型提供互补探索分布，树结构又记录每次候选的生成与修订关系。奖励既应承认最终测试表现，也应体现相同上下文中的相对提升；这样各 agent 能在共享搜索反馈下学习，而无需共享全部参数或只模仿最强模型。

Method

1. 以完整候选代码为 tree node，用 AB-MCTS-style Beta priors 和两级 Thompson sampling 先选 agent、再选其 expandable node。generation option 扩展新候选，refinement option 沿已有方案继续修订，并读取执行反馈。
2. 对非根节点构造父奖励与其他兄弟均值的 mixed baseline，将节点相对该基线的增益加入原始 task reward；无兄弟时退化为与父节点比较。再对全树 shaped rewards 做 group-relative normalization。
3. 采用 GRPO-style clipped objective 与 KL 项，各 agent 仅用自己生成节点的 token likelihood 独立更新。以过滤掉全对和全错问题后的 7,992 个 DeepCoder prompts 训练，比较单 policy、单 agent tree search 和多 agent 版本。
4. 区分单次采样 Pass@1 与搜索推理：统一 MCTS 推理 budget 为 60 nodes，public tests 引导测试时搜索，private tests 评最终效果，在 LiveCodeBench 上分析训练协作与推理组合的独立贡献。