Search papers, labs, and topics across Lattice.
This paper introduces Branching Policy Optimization (BPO), a novel reinforcement learning algorithm tailored for large language model agents operating within deterministic sandboxes. By leveraging the unique properties of these environments, BPO constructs a single tree of trajectories that share prefixes, allowing for reduced variance in advantage computation compared to traditional methods. The results demonstrate that BPO outperforms existing algorithms like GRPO and RLOO by improving success rates by 3.6–6.1 points while requiring fewer policy updates and reducing gradient-norm variance by half.
BPO achieves up to 6.1% higher success rates in sandbox-native RL tasks while cutting down on the number of required policy updates by 38%.
Reinforcement learning has emerged as the dominant paradigm for training large language model (LLM) agents that interact with executable sandboxes. State-of-the-art algorithms such as PPO, RLOO, and GRPO inherit their rollout topology from RLHF: for each prompt, N independent trajectories are sampled from the initial state, and an advantage is computed by subtracting a group baseline. This design ignores a defining property of agent sandboxes. They are deterministic, snapshottable, and resumable from any intermediate state. We argue that this property enables a fundamentally different rollout topology: rather than N independent trees of depth T, one can construct a single tree of N leaves whose siblings share prefixes, and therefore share variance. We instantiate this idea as Branching Policy Optimization (BPO), a sandbox-native RL algorithm that (i) adaptively snapshots the sandbox at high-entropy decision points along a backbone trajectory, (ii) forks K alternative actions per branch point and rolls out each to termination, and (iii) computes per-step advantages from sibling returns rather than from independent prompts. We prove this estimator is unbiased and has strictly lower variance than the trajectory-level baseline, with the reduction equal to the prefix-explained portion of return variance. On WebShop, ALFWorld, and SWE-bench Verified with Qwen2.5-7B and Llama-3.1-8B backbones, BPO improves success by 3.6--6.1 absolute points over GRPO and RLOO at matched compute, halves gradient-norm variance, and matches the best baseline using 38% fewer policy updates.
