Tree based learning improves long task performance for llm agents
Hindsight Credit Assignment over Trees for Agentic RL
Machine LearningArtificial Intelligence
Summary
Long, complex tasks are hard for AI agents because they rarely find successful ways to complete them, making it tough to learn from trial and error. The authors propose a method called TriGRPO that builds a branching tree of possible actions, using successful steps found in one part of the tree to explore other options more efficiently. By comparing similar decisions and using past successes on related tasks, the approach helps the agent learn useful strategies even when success is rare. Tests showed this method improved the agent's ability to complete tasks and made learning more efficient.
What this means in practice
- •For ai developers: Design improved training methods for LLM-based agents to handle complex tasks with sparse success signals more effectively.
- •For robotics engineers: Enhance autonomous decision-making policies in robots performing extended multi-step operations with limited feedback.
Authors
Penghong Zhao, Yihao Chen, Maoheng Yuan, Yunjian Zhang, Abudukelimu Wuerkaixi, Haoran Xu, Man Lv, Yaolong Wang, Zhijie Sun, Guohua Liu, Yuewei Zhang
Abstract
Reinforcement learning for long-horizon LLM agents faces a fundamental dilemma: successful experiences are essential for policy improvement, yet limited policy capabilities make such experiences difficult to discover. Sparse outcome rewards compound this challenge, leaving sampled trajectories with little relative feedback for learning. In this paper, we propose TriGRPO, a tree-based reinforcement learning framework that turns scarce successes into exploration and learning signals through hindsight credit assignment within and across rollout trees. TriGRPO constructs rollout trees through hindsight-guided branching: when an ongoing trajectory reaches a matched decision state, a successful action discovered during rollout initiates a sibling branch that continues autonomously, enabling further exploration and parent-sibling comparisons. Three complementary groups organize policy optimization over these trees: root groups capture within-prompt relative returns, node groups assign credit from parent-sibling outcome differences, and cross groups supplement sparse feedback with historical performance on related tasks. Experimental results demonstrate consistent gains in task performance and rollout efficiency across model scales, highlighting structured hindsight credit assignment as an effective approach to long-horizon agent learning.