Source-linked AI summary
TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents
Jinwei Gan
TL;DR
Existing graph-based credit assignment is batch-local, limiting the use of transitions discovered by earlier policies. TIGPO retains task-specific graphs across updates, schedules revisits, and compares current attempts with earlier same-task scores; it consistently outperforms prior group-based and graph-based methods on ALFWorld and WebShop.
Problem
Existing graph-based methods discard transitions after each policy update, preventing connections across training stages and limiting relative advantage estimation to small, batch-local rollout groups.
Source: §1 · pp. 1–2Method
TIGPO maintains persistent task-specific transition graphs, schedules delayed revisits within a fixed rollout budget, and pairs current revisit scores with detached scores from earlier same-task exploration groups.
Source: §1 · p. 2Results
TIGPO consistently outperforms prior group-based and graph-based policy optimization methods on ALFWorld and WebShop.
Source: §1 · p. 2Takeaways & Limitations
Persistent graph memory, scheduled revisitation, and cross-temporal comparison provide complementary benefits for long-horizon credit assignment.
Source: §6 · p. 9
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Long-horizon LLM agents face sparse, delayed rewards, while existing graph-based credit assignment is limited to transitions in each rollout batch. TIGPO carries task-specific graph structure across updates, schedules revisits, and compares current attempts with earlier same-task scores; it consistently outperforms prior group-based and graph-based methods on ALFWorld and WebShop.
1 INTRODUCTION
- Existing graph-based credit assignment is batch-local, so it cannot connect an early promising trajectory fragment with a later successful continuation from an overlapping state.This limitation is especially pronounced with small rollout groups, where sparse graph coverage makes relative advantages sensitive to individual outcomes.Source: §1 · pp. 1–2
- Directly replaying earlier-policy trajectories in the current policy loss can introduce distribution mismatch because their actions and log-probabilities are stale.This motivates using historical experience to improve credit for current-policy rollouts without giving historical trajectories gradients.Source: §1 · p. 2
- Persistent task-specific graphs combine valid historical and current transitions to provide step-level credit for current rollouts, without putting historical actions or log-probabilities in the policy loss.Transitions discovered by different policy versions can form complete paths to success and denser credit signals for current behavior.Source: §1 · p. 2
- Exploration–Revisit scheduling divides a fixed task-group budget between ordinary sampling and delayed reattempts of previously explored tasks.Revisits let the current policy extend or complete paths discovered earlier without increasing the per-update rollout budget.Source: §1 · p. 2
- For each revisit, TIGPO pairs current episode scores with detached scores from the earlier same-task Exploration group to enlarge the reference set and compare policy stages.The enlarged reference is designed to stabilize relative advantage estimates under small rollout groups; only current Revisit trajectories receive gradients.Source: §1 · p. 2
- TIGPO consistently outperforms prior group-based and graph-based policy optimization methods on ALFWorld and WebShop.The conclusion also reports that persistent graph memory, scheduled revisitation, and cross-temporal comparison provide complementary benefits.Source: §1 · p. 2
2 RELATED WORK
Prior work addresses long-horizon credit assignment with value-free group comparisons and graph-derived step-level credit. TIGPO differs by retaining task-conditioned graph structure across policy stages while optimizing only on current-policy trajectories.
2 RELATED WORK
- GraphGPO derives step-level credit from a state-transition graph built from the current rollout batch, while TIGPO adds persistent task-conditioned graph memory, scheduled revisitation, and cross-temporal comparison.The related-work overview describes GiGPO's episode-level and anchor-state-level groups and GraphGPO's graph-based step credit.Source: §2 · p. 3
- TIGPO retains historical transitions as graph structure and earlier rollout scores as detached reference statistics, but does not replay historical trajectories in the policy objective.All trajectories receiving gradients are newly generated by the current policy.Source: §2 · p. 3
3 PRELIMINARIES
Group-based policy optimization samples multiple rollouts per task and uses episode outcomes for relative advantage estimation. Graph-based methods add step-level credit from distances to success, while TIGPO's overview carries task graphs across updates and pairs Exploration and Revisit outcomes.
3 PRELIMINARIES
- Each policy update samples B task instances and generates K rollouts per task, for a total rollout budget of N = BK.The K rollouts for one task form a task group; GRPO assigns each rollout a within-group episode advantage.Source: §3 · p. 3
- Graph-based step credit uses the successor state's shortest-path distance to success, assigning larger returns to transitions that lead closer to the goal.Transition returns are normalized among transitions sharing the same source state to obtain step-level graph advantage.Source: §3 · p. 3
- Current-batch graphs and comparison statistics cannot inform later attempts at the same task; TIGPO carries task-level graph structure and comparison information across updates.This is the stated limitation of constructing graph and comparison statistics from only the current rollout group.Source: §3 · p. 3
- TIGPO divides a fixed task-group budget into Exploration and Revisit slots, combines historical and current graphs for revisited tasks, and derives step-level graph credit plus a cross-temporal episode advantage.Historical experience informs credit assignment, while the policy objective uses only current-policy rollouts.Source: Figure 1 · p. 4
4 METHOD
TIGPO carries task-specific transition structure across policy updates and schedules revisits within a fixed rollout budget. It uses historical structure and task-matched scores to improve credit for current-policy rollouts while keeping historical trajectories out of the policy loss.
4 METHOD
- TIGPO combines graph-based credit with cross-temporal episode comparison to optimize current-policy trajectories without replaying historical experience in the policy loss.Its temporal graph advantage and cross-temporal episode advantage supply the two learning signals.Source: §4 · p. 4, §4.3 · p. 6
4.1 TEMPORAL INSTANCE GRAPH
- Task-specific graphs accumulate across updates, joining historical and current transitions so trajectory fragments can form paths to success.Shortest-path distances on the temporal graph provide advantages for current transitions.Source: §4.1 · pp. 4–5
4.2 EXPLORATION–REVISIT SAMPLING
- Exploration–Revisit scheduling assigns revisits to previously explored tasks after a delay, while keeping each update at the same rollout budget.If too few tasks are eligible, unused Revisit groups return to Exploration.Source: §4.2 · p. 5
4.3 CROSS-TEMPORAL POLICY OPTIMIZATION
- For each Revisit group, TIGPO compares current outcomes with detached scores from its earlier Exploration group on the same task, enlarging the reference set.The comparison is designed to stabilize relative advantage estimation; only current Revisit trajectories receive gradients.Source: §4.3 · pp. 5–6
5 EXPERIMENTS
Experiments on ALFWorld and WebShop find that TIGPO achieves the best aggregate performance among the compared methods. Ablations and historical-use diagnostics examine the roles of persistent graph memory, scheduled revisitation, and cross-temporal comparison, while runtime measurements show no observable overhead relative to GraphGPO.
5.1 EXPERIMENTAL SETUP
- TIGPO is evaluated on 3,827 ALFWorld task instances across six categories and WebShop product-search-and-purchase tasks, reporting ALFWorld success rates and WebShop average task scores plus success rates.Both methods sample 64 current-policy trajectories per update; evaluation uses the checkpoint at update 250 over 512 episodes for each of three seeds (123, 456, 789).Source: §5.1 · pp. 6–7
5.2 EXPERIMENTAL RESULTS
- TIGPO achieves the best aggregate performance on both benchmarks: ALFWorld overall success is 91.28%, while WebShop average task score is 88.65 and success rate is 77.54%.On ALFWorld, TIGPO exceeds GiGPO and GraphGPO by 0.26 and 1.96 percentage points; on WebShop, its score and success rate exceed GiGPO by 0.71 and 3.71 points and GraphGPO by 1.31 and 1.17 points.Source: Table 1 · p. 7, §5.2 · p. 7
- Persistent task-specific graph memory raises ALFWorld overall success from 89.32% to 90.69% versus a graph rebuilt at each update.The Persistent Graph variant improves five of six task categories, including Look by 3.34 percentage points and Pick2 by 6.56 points.Source: §5.2 · p. 7, Table 2 · p. 8
- Scheduled revisitation without cross-temporal comparison reaches 89.58% overall success, while full TIGPO reaches 91.28%, a 1.70-point gain over that variant.Full TIGPO improves the current-update graph baseline by 1.96 percentage points; the ablation results describe persistent memory and cross-temporal comparison as complementary.Source: Table 2 · p. 8, §5.2 · p. 8
- TIGPO and the Persistent Graph ablation accumulate comparable task-specific records, but TIGPO has higher task-memory and exact-state hit rates.The higher exact-state hit rate indicates that retrieved graph structure overlaps with states encountered by the current policy; the diagnostics are shown in Figure 2.Source: Figure 2 · p. 8, §5.2 · pp. 8–9
- TIGPO takes 247.08 seconds per update versus GraphGPO’s 258.32 seconds, with comparable core LLM computation time and peak GPU memory.Because timing IQRs largely overlap, the authors interpret the differences as comparable runtime rather than evidence of speedup; Table 3 reports median and IQR over updates 11–250.Source: Table 3 · p. 9, §5.2 · p. 9
6 CONCLUSION
TIGPO extends graph-based agent learning across policy updates through persistent task-specific graphs, scheduled revisitation, and cross-temporal references. Experiments show gains across ALFWorld and WebShop, while the paper identifies larger models, more environments, and graph compression and retrieval as future directions.
6 CONCLUSION
- TIGPO combines persistent task-specific transition graphs, Exploration–Revisit rollouts, and cross-temporal reference groups for advantage estimation.Historical transitions and scores serve as references rather than being replayed in the policy loss.Source: §6 · p. 9
- Experiments show consistent improvements over GRPO, GiGPO, and GraphGPO, with complementary benefits from graph memory, scheduled revisitation, and cross-temporal comparison.Under the same rollout budget, TIGPO shows no observable end-to-end training-time or GPU-memory overhead relative to GraphGPO.Source: §6 · p. 9
- Future work may scale TIGPO to larger models and more diverse environments and develop adaptive graph compression and retrieval for longer training horizons.Source: §6 · p. 9