AT²PO: Agentic Turn-based Policy Optimization via Tree Search

Idea

AT²PO 将 agentic RL 的采样、credit assignment 与优化粒度统一到 interaction turn：在不确定轮次分支生成轨迹，用树中后继结果估计每轮价值，再以 turn-level importance ratio 更新策略。ATPO 目标本身可独立于树搜索用于其他多轮训练流程。

Research Problem

普通独立 rollout 难以在固定预算下探索有价值的中间决策；只把最终结果奖励分配给整段轨迹，会掩盖不同工具调用的贡献。逐 token 更新又可能具有高方差，而全序列 ratio 会忽略多轮交互中的局部变化，导致监督与决策结构不匹配。

Insight

一个 reasoning-plus-tool-call turn 是自然的代理决策单元。共享前缀的树不仅节省重采样，也为同一状态的多种后续提供对照；把终局证据沿树回传后，使用相同粒度的 importance weighting 可使局部信用与局部更新对齐。

Method

1. 每个 prompt 先生成 M 条完整链作为树分支，每个节点存储该轮状态与动作。用本轮生成 tokens 的平均负 log-probability 估计 entropy，按 entropy 减去重复分支惩罚选 top-K 节点。
2. 从选中状态保留完整前缀重新 rollout 后续，重复 L 次扩展，在相近 token 预算下得到更多终局分支，避免在单个节点过度分叉。
3. 叶节点以 GRPO 方式归一化终局奖励；内部节点按 policy probability 归一化加权聚合 child values，将估计出的 turn-wise advantage 赋给该轮生成 tokens。
4. ATPO 采用长度归一化的 turn-level probability ratio 和 clipping，通过 stop-gradient 构造保持 token 梯度，同时屏蔽工具响应 tokens；在单跳与多跳搜索 QA 上比较策略质量及训练稳定性，无额外 SFT 阶段。