BPO algorithm boosts LLM agent training with 38% fewer updates

Reinforcement learning (RL) has become the standard for training large language model (LLM) agents that operate in executable sandboxes. Current algorithms like PPO, RLOO, and GRPO sample N independent trajectories per prompt and compute advantages using group baselines. This design ignores a key property of agent sandboxes: they are deterministic, snapshottable, and resumable from any intermediate state. A new paper from researchers Bowei He, Yankai Chen, Xiaokun Zhang, and Xue Liu (accepted at WAIC Academic 2026) introduces Branching Policy Optimization (BPO), which exploits this property. Instead of independent rollouts, BPO constructs a single tree where sibling trajectories share prefixes. It adaptively snapshots the sandbox at high-entropy decision points, forks K alternative actions per branch point, and computes per-step advantages from sibling returns rather than from independent prompts. The authors prove this estimator is unbiased and has strictly lower variance than trajectory-level baselines, with the reduction equal to the prefix-explained portion of return variance.

In experiments on three challenging benchmarks—WebShop, ALFWorld, and SWE-bench Verified—BPO was tested with Qwen2.5-7B and Llama-3.1-8B backbones. It improved absolute success rates by 3.6 to 6.1 percentage points over GRPO and RLOO at matched compute budgets. Gradient-norm variance was halved, indicating more stable training. Remarkably, BPO matched the best baseline performance using 38% fewer policy updates, offering significant computational savings. The approach is particularly well-suited for sandboxed environments where rollouts can be resumed from saved states. By sharing prefix variance among siblings, BPO provides a more sample-efficient and principled alternative to existing RL algorithms for training LLM agents, potentially accelerating progress in web navigation, household tasks, and code repair.