TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents
Jinwei Gan at Nanjing University introduces TIGPO, which keeps a persistent per-task transition graph across policy updates so that credit assignment for long-horizon agents can draw on transitions discovered by earlier policy versions rather than only the current batch.
Ask this paper
The defect it targets: existing graph-based credit assignment rebuilds the state-transition graph inside each update and discards everything earlier policies found, which confines advantage estimation to small batch-local rollout groups.
Persistent transition graph: valid transitions from any policy version jointly determine credit for current rollouts, so the reference set for advantage estimation grows over training instead of resetting.
Split rollout budget: a fixed budget is divided between Exploration slots for ordinary sampling and Revisit slots that retry previously explored tasks, and each revisit pairs its rollout group with the matching earlier Exploration group.
Historical data never enters the loss: past transitions and scores act only as structural and detached statistical references, which avoids the off-policy correction problems that replay normally introduces.
Results: TIGPO outperforms prior group-based methods on ALFWorld and WebShop, the two standard long-horizon agent environments.
Abstract
Graph-based policy optimization improves credit assignment for long-horizon LLM agents by organizing rollout trajectories into state-transition graphs. However, existing methods construct graphs independently within each policy update, discarding transitions discovered by earlier policies and limiting advantage estimation to small, batch-local rollout groups. We propose \emph{Temporal Instance-Graph Policy Optimization} (TIGPO), which extends graph-based credit assignment across policy updates. TIGPO maintains a persistent transition graph for each task, allowing valid transitions discovered by different policy versions to jointly determine credit for current rollouts. To actively reconnect current exploration with historical experience, TIGPO allocates a fixed rollout budget between Exploration slots for ordinary task sampling and Revisit slots for delayed reattempts of previously explored tasks. For each revisit, TIGPO pairs the current rollout group with its corresponding earlier Exploration group to construct a cross-temporal reference. The enlarged reference is designed to stabilize relative advantage estimation under small rollout groups, while comparison on the same task directly captures policy improvement across training stages. Historical transitions and scores serve only as structural and detached statistical references and are never replayed in the policy loss. Experiments on ALFWorld and WebShop demonstrate that TIGPO consistently outperforms prior group-based and graph-based policy optimization methods.