TSBPO: Tree-Structured Branching for Policy Optimization in Interactive Language Agents

Rui Yu; Chong Mu; Jinchuan Zhang

cs.AIOct 30, 2026

TSBPO: Tree-Structured Branching for Policy Optimization in Interactive Language Agents

Authors: Rui Yu, Chong Mu, Jinchuan Zhang

Organizations: University of Electronic Science and Technology of China

Abstract

Terminal feedback in multi-turn agent training leaves both rollout allocation and local credit underdetermined. Dynamics-Predictive Sampling (DPS) [9] provides a task-level predictive sampling reference, but interactive agents also need to choose which visited states merit further continuations. We introduce TSBPO with two method components. A lightweight, fine-grained Root/Branch budget allocator distributes factual rollouts across tasks and additional suffixes across replayable states using likelihood-fitted estimates of terminal-outcome contrast. On the resulting physical rollout trees, a tree-aware step-level credit assignment algorithm compares immediate sibling segments and assigns their local outcome contrasts to the turns they contain. Exact task/observation groups provide a complementary step term. The allocator selects what to sample; observed outcomes determine the subsequent credit. With a Qwen2.5-1.5B actor, fixed checkpoints attain 97.79% seen and 96.64% unseen stochastic success on ALFWorld, and an 81.07% per-episode success rate over six stochastic episodes for each of the 500 WebShop test goals. At the WebShop update-100 checkpoint, removing the observation-group step term yields 75.93% under the same evaluation. These results describe the evaluated training configurations on two interactive benchmarks.

RL for LLM Agents

Reinforcement learning for large language model agents trains models to plan, use tools, and adapt through feedback from interactive tasks.

See all 637 papers

Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning
Jul 15, 2026Bowei He, Yankai Chen, Xiaokun Zhang +1Reinforcement Learning Policy Gradient Methods
Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE · McGill Univeristy, Montreal, Canada · City University of Hong Kong, Hong Kong SAR.
PTGPO: Prefix Tree Group Policy Optimization
Oct 10, 2026Ruolin Chen, Yang Li, Jihang Wang +4RL for LLM Agents Temporal Credit Assignment
Brain-inspired Cognitive AI Lab, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · HyperAI Team, Xiaomi Corporation +1
Contrastive Branch Policy Optimization
Aug 25, 2026Ying Wang, Changlin Qiu, Bang Lin +4RL for Language Model Reasoning Step-Level Credit Assignment in RL
Alibaba Group, Hangzhou, China · Harbin Institute of Technology, Harbin, China

Jul 15, 2026J/K move · Enter open · S save

Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning

Bowei He, Yankai Chen, Xiaokun Zhang, Xue Liu

Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE · McGill Univeristy, Montreal, Canada · City University of Hong Kong, Hong Kong SAR.

Reinforcement Learning Policy Gradient Methods Policy Learning Sample-Efficient RL RL for LLM Agents

Open paper AskPDF arXiv

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.

Abstract

RL for LLM Agents

Explore similar work

Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning

PTGPO: Prefix Tree Group Policy Optimization

Contrastive Branch Policy Optimization