SPARK: Strategic Policy-Aware Exploration via Dynamic Branching for Long-Horizon Agentic Learning

Idea

SPARK 把 long-horizon agent RL 的 rollout 从互不共享的完整 chains 改为在关键状态分叉的 trajectory forest。模型通过 reasoning 中的 <explore> tag 表达需要额外探索的时机，采样器据此扩展多个 continuations，并在固定 leaf budget 内收集完整 trajectories，再使用 GRPO 风格目标更新 policy。

Research Problem

长程任务成功轨迹稀疏，但直接增加独立 rollouts 会反复计算大量例行步骤，未必在决定任务成败的分岔处尝试足够多的行动。问题是如何让有限采样预算集中于值得探索的状态，同时避免依赖人为列出的关键步骤，并保持与现有 agent RL training pipeline 兼容。

Insight

在同一历史状态之后采样多个 alternatives，可以更直接地比较关键决策，而共享 prefix 减少了重复执行。SPARK 的核心改动是 exploration allocation，并未引入新的 dense reward 或独立 value model。<explore> 是通过 cold-start SFT 和后续 RL 学到的显式信号，不能视作经过校准的 epistemic uncertainty 测量；理论覆盖分析也依赖关键状态和采样概率等简化条件。

Method

1. Cold start 与 roots：先用 300 条 trajectories 做 SFT，使模型具备生成 <explore> 的初始能力；每个任务从初始状态采样多个不同 reasoning-action roots，建立探索多样性。
2. Dynamic branching：每步检查 reasoning trace 是否出现 <explore>；存在时从当前更新后的 history 采样 B 个 continuations，否则沿单一 chain 继续，所有 child trajectories 共享此前 prefix。
3. Budget enforcement：根据当前 active leaves 与总 budget 调整有效 branching factor；到达 terminal state 或最大 horizon 后结束。正文默认 rollout budget 为 8、initial roots 为 4、branching factor 为 2。
4. Policy update：把同一任务的 completed leaf trajectories 组成 group，按 binary terminal reward 计算 group-normalized advantages，以 clipped objective 和 reference-policy KL 训练。实验在 ALFWorld、ScienceWorld 与 WebShop 比较成功率、采样效率及未见场景表现。