PTGPO: Prefix Tree Group Policy Optimization

Ruolin Chen; Yang Li; Jihang Wang; Zhuoya Zhao; Yuchen Liu; Jiaming Xu; Qian Zhang

cs.LGOct 10, 2026

PTGPO: Prefix Tree Group Policy Optimization

Authors: Ruolin Chen, Yang Li, Jihang Wang, Zhuoya Zhao, Yuchen Liu, Jiaming Xu, Qian Zhang

Organizations: 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 · University of Ottawa

Abstract

Training language agents on long-horizon interactive tasks is challenging because sparse terminal rewards provide weak credit signals for intermediate actions. Existing group-based methods either assign a shared trajectory-level advantage or estimate step-level advantages from state groups, which may conflate the current action with subsequent decisions. We propose Prefix Tree Group Policy Optimization (PTGPO), a critic-free method that constructs prefix trees over trajectory suffixes within anchor-state groups. PTGPO assigns each tree edge a credit given by the difference between its child and parent empirical mean returns, capturing the conditional return change revealed by each additional action. These prefix-tree credits provide fine-grained learning signals without requiring a critic or additional rollouts. Experiments on interactive benchmarks ALFWorld, WebShop and Sokoban show that PTGPO consistently improves over RL baselines, demonstrating its effectiveness.

Figures & tables

Figure 1: Comparison of state-group and prefix-tree credit assignment under the undiscounted setting ( $\gamma=1$ ). Identical actions may receive conflicting advantages when their subsequent actions lead to different returns. PTGPO recursively groups trajectory suffixes by action prefix, where node values denote empirical mean returns and edge labels denote child-parent mean differences. Colors indicate identical actions.

Figure 2: Illustration of PTGPO advantage decomposition under the undiscounted setting $(\gamma=1)$ . Episode-level advantages are shared by all actions in the same trajectory, while prefix-tree credits redistribute return residuals to branching decisions that change the conditional mean return. “End” marks the termination of a prefix decomposition.

Closed-Source Model
Type	Method	ALFWorld							WebShop
Type	Method	Pick	Look	Clean	Heat	Cool	Pick2	All	Score	Succ.
Prompting	GPT-4o	75.3	60.8	31.2	56.7	21.6	49.8	48.0	31.8	23.7
Prompting	Gemini-2.5-Pro	92.8	63.3	62.1	69.0	26.6	58.7	60.3	42.5	35.9
Qwen2.5-1.5B-Instruct
Prompting	Direct Prompt	5.9	5.5	3.3	9.7	4.2	0.0	4.1	23.1	5.2

Table 1: Performance on ALFWorld and WebShop. We train each RL method with 3 random seeds and report the mean and standard deviation. The best performances are highlighted in bold.

Type	Method	Sokoban [6 $\times$ 6]
Prompting	Direct Prompt	11.7
RL Training	GRPO	73.9 ±1.6
RL Training	GiGPO	77.6 ±2.5
RL Training	PTGPO	85.2 ±1.6

Table 2: Performance on Sokoban. We train each RL method with 3 random seeds and report the mean and standard deviation. The best performances are highlighted in bold.

Advantage Composition
Variant	ALFWorld	WebShop	Sokoban
PTGPO	92.6 ±2.5	74.3 ±1.5	85.2 ±1.6
w/o Episode-level Adv	92.4 ±1.1	71.8 ±3.9	81.5 ±4.4
w/o Prefix-tree Adv	72.8 ±3.6	56.8 ±3.8	73.9 ±1.6
Aggregation Strategy
Mean	84.3 ±1.6	71.4 ±2.1	82.3 ±2.3

Table 3: Ablation study of PTGPO on ALFWorld and WebShop using Qwen2.5-1.5B-Instruct, and on Sokoban using Qwen2.5-VL-3B-Instruct. The best performances are highlighted in bold.

Figure 3: (a) Episode Success Rate during Training on ALFWorld. (b) Distribution of maximum expanded tree depth at epoch 160 on ALFWorld.

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 612 papers

Learning from All-Failed Groups via First-Visit Coverage in Long-Horizon Agentic Tasks
Jul 22, 2026Kaibing Yang, Guangfeng Cai, Shengtian Yang +6Group Relative Policy Optimization RL Exploration
Southeast University · Kuaishou Technology · Meituan
Matched-Context Group Policy Optimization for LLM Agent Training
Oct 9, 2026Chenxu Zhang, Yaorui Shi, Wenlong Zhang +3RL for LLM Agents Preference-Based RL
Imperial College London · Meituan · University of Science and Technology of China +1
Hierarchy-of-Groups Policy Optimization for Long-Horizon Agentic Tasks
Feb 26, 2026Shuo He, Lang Feng, Qi Wei +3Agentic RL RL for LLM Agents
Nanyang Technological University · Southeast University

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

Learning from All-Failed Groups via First-Visit Coverage in Long-Horizon Agentic Tasks

Kaibing Yang, Guangfeng Cai, Shengtian Yang, Shuo He+5

Southeast University · Kuaishou Technology · Meituan

Group Relative Policy Optimization RL Exploration Sparse-Reward RL Long-Horizon Agent Tasks Policy Learning RL for LLM Agents

Open paper AskPDF arXiv

Group-based policy optimization has been increasingly used to train large language model (LLM) agents from sparse outcome rewards by comparing trajectories or steps within a group. However, on difficult long-horizon agentic tasks, we found this comparison suffers from a sampling imbalance: repeated or low-effect actions dominate the high-probability region of the policy, leaving useful state-changing actions under-sampled. This imbalance produces many all-failed rollout groups, where the relative advantages within such a group provide no direction for updating the policy. Consequently, the sampling imbalance and the all-failed groups collapse into a self-perpetuating credit trap: failure-dominated sampling yields no learning signal, allowing repeated low-effect actions to persist. To break this trap, we propose Coverage-conditioned Group Policy Optimization (CovGPO), which uses first-visit observation coverage only when all samples in a group receive zero outcome reward. Specifically, within such groups, CovGPO assigns higher relative advantages to state-exploring actions without corrupting the original reward signal, as reaching new observations is a prerequisite for task success. Experiments on two challenging agentic benchmarks, ALFWorld and WebShop, show that CovGPO consistently improves over group-based baselines, with particularly large gains on hard tasks.

Abstract

RL for LLM Agents

Explore similar work

Learning from All-Failed Groups via First-Visit Coverage in Long-Horizon Agentic Tasks

Matched-Context Group Policy Optimization for LLM Agent Training

Hierarchy-of-Groups Policy Optimization for Long-Horizon Agentic Tasks