PTGPO: Prefix Tree Group Policy Optimization

arXiv:2610.14737v1 Announce Type: new 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.

Related

• Matched-Context Group Policy Optimization for LLM Agent Training
• Progress-conditioned Group Policy Optimization for Long-Horizon Agentic Tasks
• GAGPO: Generalized Advantage Grouped Policy Optimization

Source: arXiv cs.LG | 2026-10-14