PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

Haodong Zhu, Yangyang Ren, Changbai Li, Sheng Xu, Linlin Yang, haiguang liu, Baochang Zhang

arXiv:2609.35084v1cs.LG

TL;DR

Sparse terminal rewards leave long-horizon agent actions without direct credit, while existing hindsight credit assignment requires costly estimation of an outcome-conditioned action distribution. GraphHCA derives a state-wise success potential and estimates it from pooled rollout graphs. It outperforms compared baselines across language and vision-language benchmarks, with reported ALFWorld gains of up to 24.6 points over GRPO and 4.7 points over the strongest step-level baseline.

  • Problem

    Sparse terminal rewards leave intermediate actions without direct supervision, while existing step-level methods do not explicitly model an action's retrospective relation to the realized outcome and HCA estimation requires an auxiliary model or extra pass.

    Source: §1 · p. 1

  • Method

    For deterministic terminal-goal tasks, GraphHCA derives hindsight credit from state-wise success probabilities and estimates their log potential through a discounted recursion on pooled rollout graphs.

    Source: §1 · pp. 2–3

  • Results

    GraphHCA achieves the best performance among compared baselines across ALFWorld, WebShop, and 6 × 6 Sokoban settings; on ALFWorld, it improves success by up to 24.6 points over GRPO and 4.7 points over the strongest step-level baseline.

    Source: §1 · p. 3, §6 · p. 10

  • Takeaways & Limitations

    GraphHCA extracts finer-grained supervision from rollouts already collected for policy optimization without an auxiliary hindsight model or additional outcome-conditioned policy evaluation.

    Source: §1 · p. 3, §6 · p. 10

    The exact analysis assumes that under q, eventual-success probability depends only on the current environment state, independently of preceding history and time step; its closed-form result also assumes deterministic transitions.

    Source: §1 · p. 2, §4.1 · p. 5

Abstract

from arXiv · show

Group-based reinforcement learning (RL) has advanced large language models (LLMs) and is increasingly extending to agentic tasks, where sparse terminal rewards make step-level credit assignment essential. Existing methods assign credit from what follows an action in sampled rollouts, but do not explicitly capture its retrospective relation to the realized outcome. Hindsight credit assignment (HCA) instead attributes credit through the ratio of hindsight to behavior-policy probabilities, but estimating the hindsight distribution requires an auxiliary model or an extra pass. To address this estimation bottleneck, we propose GraphHCA, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation. For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to a ratio of behavior-policy success probabilities at consecutive states. Taking logs yields a state-wise success potential, whose increment across a transition provides step-level credit. GraphHCA estimates this potential from pooled rollouts through a discounted recursion on the induced transition graph, which admits a unique fixed point on any directed graph. The resulting step-level signal is combined with the trajectory-level advantage, requiring neither a learned hindsight model nor an extra forward pass and recovering GRPO when the step-level weight is zero. Among all compared baselines, GraphHCA achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent. For example, on ALFWorld it improves overall success rate by up to 24.6 points over GRPO and by up to 4.7 points over the strongest step-level baseline.

1 INTRODUCTION

Sparse terminal rewards leave intermediate actions without direct supervision, making credit assignment difficult in long-horizon agent tasks. GraphHCA derives hindsight credit from state-wise success probabilities and estimates it from pooled rollouts, with consistent empirical gains across benchmarks.

1 INTRODUCTION

  • Sparse terminal rewards provide no direct supervision for intermediate actions, making attribution of outcomes harder as horizons and action spaces grow.The paper frames this as the credit assignment problem.Source: §1 · p. 1
  • GRPO shares one trajectory-level advantage across a rollout, while other step-level methods rely on sampled continuations or shortest-path progress; estimating HCA's hindsight distribution adds a model or policy pass.A failed rollout can contain useful decisions, and a successful one can contain redundant or erroneous decisions.Source: §1 · p. 2
  • For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to successor- and current-state success probabilities, whose log difference gives step-level credit.This replaces estimation over an action-space distribution with one scalar per state.Source: §1 · pp. 2–3
  • GraphHCA standardizes potential increments among transitions sharing a source state and combines the resulting step-level signal with trajectory-level advantage; disabling the step-level weight recovers GRPO.It uses already collected training rollouts without an auxiliary hindsight model or extra outcome-conditioned pass.Source: §1 · p. 3, Figure 2 · p. 3
  • GraphHCA merges identical states across pooled rollouts and uses empirical action frequencies in a discounted recursion to estimate success potentials with a unique fixed point on directed graphs.The propagation discount restores path-length sensitivity after state merging and makes the backup contractive.Source: §1 · pp. 2–3, Figure 2 · p. 3
  • GraphHCA achieves the best performance among compared baselines across ALFWorld, WebShop, and 6 × 6 Sokoban settings; on ALFWorld, it improves success by up to 24.6 points over GRPO and 4.7 points over the strongest step-level baseline.The comparison spans both LLM scales and a vision-language setting.Source: §1 · p. 3

2 RELATED WORK

Prior work moves from learned critics toward group-based rollout statistics, then refines step-level credit through dense shaping, sampled futures, or hindsight conditioning. GraphHCA targets the cost of hindsight estimation by deriving a closed-form ratio for deterministic terminal-goal tasks.

2 RELATED WORK

  • At LLM scale, critic training is costly and unstable under sparse terminal rewards, motivating critic-free advantage estimates from sampled rollouts.Earlier interactive-agent approaches often used learned critics, including PPO-style and hierarchical or search-augmented methods.Source: §2 · pp. 3–4
  • Group-based methods avoid learned critics, but GRPO broadcasts a trajectory advantage while dense shaping and rollout-based methods use supervision, surrogate objectives, shared-state outcomes, or shortest-path progress.GiGPO compares transitions from shared states; GraphGPO scores shortest-path progress on pooled rollout graphs.Source: §2 · p. 4
  • HCA defines outcome-conditioned credit through a hindsight-to-policy ratio, but estimating the hindsight distribution typically needs an auxiliary model or an extra outcome-conditioned policy pass.GraphHCA derives the ratio in closed form for deterministic terminal-goal tasks and estimates its state-wise success potential from pooled rollouts.Source: §2 · p. 4

3 PRELIMINARIES

The preliminaries model an agent rollout as sequential actions under a behavior policy with a terminal success-or-failure reward. They contrast group-based advantages with retrospective hindsight credit, whose practical bottleneck is estimating the outcome-conditioned action distribution.

3 PRELIMINARIES

  • The task is a finite-horizon decision process in which the LLM samples actions under behavior policy q and receives a binary terminal reward for reaching the goal set.The task instruction is shared across rollouts in a group.Source: §3 · p. 4
  • A per-step advantage is needed although terminal reward identifies only success, not which decisions deserve credit; GRPO assigns a standardized group return to every step, while GiGPO and GraphGPO refine credit from sampled futures.The latter methods use shared-state rollout outcomes or shortest-path progress, respectively.Source: §3 · p. 4
  • HCA defines a hindsight action distribution conditioned on a later outcome and compares it with the behavior policy, but practical estimation requires an auxiliary action-space model or an extra outcome-conditioned LLM pass.The ratio upweights actions made more probable by outcome conditioning and downweights those made less probable.Source: §3 · p. 4

4 METHOD

GraphHCA derives step-level hindsight credit from state-wise success probabilities, estimates those probabilities on a pooled rollout graph, and combines the resulting credit with trajectory-level advantages. Its graph backup has a unique fixed point on directed graphs, while its credit has a log-likelihood-ratio interpretation under stated conditions and differs from GraphGPO in its aggregation rule.

4.1 THE SUCCESS POTENTIAL FROM BAYESIAN HINDSIGHT

  • For terminal-goal tasks with binary outcomes and deterministic transitions, Bayes’ rule reduces hindsight credit to state-wise success probabilities and their potential differences.The success-conditioned posterior uses the successor state's success probability; when the potential floor is inactive, the step credit is a log-likelihood ratio to the hindsight posterior.Source: §4.1 · p. 5

4.2 MODEL-FREE ESTIMATION ON THE ROLLOUT GRAPH

  • Pooling rollouts merges identical states and weights observed actions by empirical frequency; a propagation discount restores path-length sensitivity after merging.The discounted expectation recursion has a unique fixed point on any directed graph, including cyclic graphs.Source: §4.2 · p. 6

4.3 POLICY OPTIMIZATION

  • GraphHCA standardizes transition credit among actions leaving the same state and combines it with trajectory-level advantage for policy optimization.The trajectory-level term anchors updates to task success and remains defined at singleton states; setting the step-level weight to zero recovers GRPO exactly.Source: §4.3 · p. 6

4.4 PROPERTIES OF THE GRAPHHCA CREDIT

  • When the potential floor is inactive, exact step credit is the log-likelihood ratio between the hindsight posterior and behavior policy.GraphHCA evaluates successors through empirical expected continuation values, whereas GraphGPO uses shortest-path distance as a best-case continuation, so GraphHCA remains sensitive to transition frequencies.Source: §4.4 · p. 7

5 EXPERIMENTS

GraphHCA is evaluated on two LLM-agent benchmarks and one vision-language benchmark, where it leads the compared methods. An ablation shows that expectation-based aggregation outperforms increasingly best-case aggregation.

5.1 EXPERIMENTAL SETUP

  • Evaluation covers ALFWorld and WebShop with LLM agents and 6×6 Sokoban with a VLM agent; RL results are averaged over three seeds.The LLMs are Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct, and the VLM is Qwen2.5-VL-3B-Instruct.Source: §5.1 · p. 7

5.2 MAIN RESULTS

  • 24.6 and 23.5 points of overall ALFWorld success over GRPO at 1.5B and 7B, respectively; GraphHCA also leads both WebShop metrics at both scales.It converges faster and reaches higher final success than fine-grained credit-assignment baselines across ALFWorld, WebShop, and Sokoban.Source: §5.2 · pp. 7–8, Table 1 · p. 8, Figure 3 · p. 8
  • 84.0% Sokoban success, exceeding GRPO by 12.9 points, GiGPO by 5.0, and GraphGPO by 2.4.Its across-seed standard deviation is 1.2, versus 3.1 or more for every RL baseline.Source: Table 2 · p. 9, §5.2 · p. 9

5.3 ABLATION STUDY

  • Overall success falls from 95.7% at ω = 1 to 90.1% under max aggregation; the max variant closely matches GraphGPO at 91.0%.The authors conclude that expectation-based propagation retains empirical transition frequencies and provides more informative credit than selecting the best observed continuation.Source: Table 3 · p. 9, §5.3 · pp. 9–10

6 CONCLUSION

GraphHCA derives dense step-level credit from hindsight ratios and estimates it from pooled rollout graphs. Its training procedure combines that signal with episode-level advantages without requiring an auxiliary hindsight model or extra outcome-conditioned evaluation.

6 CONCLUSION

  • GraphHCA derives dense step-level credit from the HCA hindsight ratio and estimates it directly from pooled rollout graphs.The conclusion reports consistent improvements over GRPO and existing step-level baselines across language- and vision-language settings.Source: §6 · p. 10

A ALGRITHOM

  • Each training iteration pools rollouts into a transition graph, computes discounted graph values and transition-level credit, then combines same-state and episode-level advantages for policy optimization.Graph operations add negligible overhead compared with rollout generation and policy optimization.Source: A ALGRITHOM · p. 13

B PROOFS

The appendix outlines proofs for GraphHCA’s closed-form hindsight ratio and graph backup properties. The ratio result relies on deterministic transitions and state sufficiency.

B PROOFS

  • The proof appendix covers the closed-form hindsight ratio, graph-backup contraction and convergence, a hindsight-KL identity and bounded credit, and expectation-versus-best-case aggregation.It establishes notation before presenting these proofs.Source: B PROOFS · p. 13

B.1 CLOSED-FORM HINDSIGHT RATIO (PROPOSITION 4.1)

  • Under deterministic transitions and state sufficiency, Proposition 4.1 derives a closed-form hindsight ratio, while log-potential differences telescope along realized trajectories.The successor-state identity supports the derivation of the proposition’s result.Source: §B.1 · p. 14

B.2 CONTRACTION AND CONVERGENCE (PROPOSITION 4.2)

The discounted backup is a contraction on the graph, so iteration converges geometrically to a unique fixed point even when the graph has cycles. That fixed point is the discounted expected terminal success under the empirical graph policy.

B.2 CONTRACTION AND CONVERGENCE (PROPOSITION 4.2)

  • The backup operator is a contraction, guaranteeing geometric convergence to a unique fixed point even on graphs with cycles.The fixed point equals the discounted expected terminal success under the empirical graph policy.Source: §B.2 · p. 15

B.3 HINDSIGHT KL IDENTITY AND BOUNDED STEP CREDIT (PROPOSITION 4.3)

The proposition relates expected log hindsight likelihood to agreement between the behavior and hindsight policies, and establishes that graph credit is bounded.

B.3 HINDSIGHT KL IDENTITY AND BOUNDED STEP CREDIT (PROPOSITION 4.3)

  • The expected log hindsight likelihood under q has equality in the stated identity exactly when q(· | s) equals h(· | s, G) almost everywhere.The supplied passage identifies the expectation term as q(a | s) log h(a | s, G).Source: §B.3 · p. 15
  • The empirical graph potential lies between 0 and 1 at every node, and the resulting credit is bounded for every observed transition.The passages establish boundedness but do not provide the bound's explicit value.Source: §B.3 · p. 15

B.4 EXPECTATION VERSUS BEST-CASE AGGREGATION (PROPOSITION 4.4)

The max-aggregation backup has a unique fixed point that corresponds to discounted shortest-path distance to a goal. Compared with GraphHCA's empirical expectation, this best-case aggregation scores successors differently.

B.4 EXPECTATION VERSUS BEST-CASE AGGREGATION (PROPOSITION 4.4)

  • The max-aggregation operator is a contraction and therefore has a unique fixed point.Its fixed point is γ̄^d(s) for goal-reachable states and 0 otherwise, where d(s) is shortest-path distance to a goal.Source: §B.4 · p. 16
  • The max-aggregation fixed point is at least the empirical-expectation fixed point at every state.The result follows by monotonicity of both operators from a shared initialization.Source: §B.4 · p. 16
  • The aggregation gap is zero only when the empirical policy selects maximizing successors and this condition continues along its reachable paths.The stated equality condition applies at the state and along its q̂-reachable continuation.Source: §B.4 · p. 16
  • GraphHCA evaluates successors by empirical expectation under q̂, whereas GraphGPO uses best-case aggregation and a shortest-path score under unit transition cost.The two scores are ranking-equivalent under that unit-cost convention.Source: §B.4 · p. 16

C BENCHMARK DETAILS AND COMPARED METHODS

The paper evaluates interactive text-based household and shopping tasks alongside image-based Sokoban, and compares GraphHCA with language-model, prompting, and RL baselines. Training uses 150 steps across benchmarks and model configurations.

C BENCHMARK DETAILS AND COMPARED METHODS

  • ALFWorld evaluates terminal-reward household tasks across 3,827 instances and six activity categories using textual observations and template actions.The categories vary in subgoal count and decision-chain length; success requires satisfying the full instruction.Source: C BENCHMARK DETAILS AND COMPARED METHODS · p. 17
  • WebShop tests shopping instructions over more than 1.1 million product pages, scoring attribute match and success when the score is maximal.The benchmark contains approximately 12,000 human-written instructions.Source: C BENCHMARK DETAILS AND COMPARED METHODS · p. 17
  • Sokoban uses rendered 6 × 6 puzzles with irreversible box pushes and terminal-only feedback, evaluated by average success rate.The agent is a vision-language model that plans from pixels.Source: C BENCHMARK DETAILS AND COMPARED METHODS · p. 17
  • GraphHCA is compared with closed-source LLMs, prompting agents, critic-based PPO, and group-based RL methods, with step-credit methods providing the closest comparisons.On Sokoban, comparisons are limited to GRPO, GiGPO, and GraphGPO.Source: C BENCHMARK DETAILS AND COMPARED METHODS · p. 17

D.1 TRAINING CONFIGURATION

  • All benchmarks and model configurations use 150 training steps; the 1.5B and vision-language runs use four A100 GPUs, while 7B runs use eight.Each GPU has 80 GB memory.Source: §D.1 · p. 17

D.2 MORE ABLATIONS

The ablations support combining trajectory- and state-level advantages, favor a high propagation discount, and find limited sensitivity to the numerical floor. The prompt templates share a common interaction schema, with Sokoban-specific controls.

D.2 MORE ABLATIONS

  • Overall success is 71.1% with w_s=0 (GRPO), 92.5% with A_s alone, and 95.7% with the default mixed objective; w_s=0.7 reaches 94.9%.The mixed settings rise from 93.4% at w_s=0.5 to 94.9% at w_s=0.7 and peak at 95.7% with w_s=1.Source: §D.2 · pp. 17–18, Table 4 · p. 18
  • Overall success rises from 90.7% to 93.3% and 95.7% as the propagation discount increases from 0.55 to 0.75 and 0.95.A higher discount reduces distance bias and propagation-depth clipping while retaining the contraction guarantee; small discounts can favor shorter, less reliable routes.Source: Table 5 · p. 18, §D.2 · p. 18
  • Overall success is 95.7%, 94.1%, and 94.9% at ε=10^-2, 10^-4, and 10^-6; the at-most 1.6-point variation is comparable to seed variation.With γ=0.95 and T=50, the floor binds for continuations that rarely or never reach the goal, rather than because of propagation depth.Source: §D.2 · p. 18, Table 6 · p. 19

E PROMPT TEMPLATES

  • All three prompts provide the task, step count, up to two recent observation-action pairs, current observation, and admissible actions before requesting reasoning and one action.Sokoban adds a symbol legend and irreversible-push warning, and offers four fixed moves rather than a state-dependent action set.Source: E PROMPT TEMPLATES · pp. 18–19
Loading 2609.35084v1…