cs.LGOct 16, 2026

Visual Causal-chain Bookmarking: Retrieval-Weighted Credit Assignment for Reinforcement Learning from Delayed Reward

Authors: Prathap Selvakumar

Organizations: University of Manchester

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

RL agents trained on a single trajectory-level return face a credit-assignment problem: when a reward arrives many steps after the decision that caused it, every action gets the same signal regardless of causal responsibility. This paper studies Visual Causal-chain Bookmarking (VCBM), which concentrates credit on the decision points that determine an episode's return, via two instantiations. The first targets a fully observed, low-dimensional MDP (a delayed-reward watch-repair task), where VCBM statistically discovers which state components the agent causally controls and estimates per-decision-point action values directly, evaluated against ground truth and RUDDER, an LSTM-based baseline. VCBM converges to 95.07% correct decisions in a mean of 1,532.3 episodes across 20 seeds, versus RUDDER's slower, more variable convergence (mean 3,327.1 episodes; p<0.001); VCBM's discovered causal structure exactly matches ground truth in all seeds. The second targets a partially observed, language-based setting: an LLM agent trained with Leave-One-Out PPO (LOOP) in AppWorld, where causal discovery is intractable and a structural heuristic (state-mutating tool calls) substitutes for it, with credit distributed via retrieval over episodic memory and blended with LOOP's advantage. Over 200 iterations on identical Qwen2.5-7B-Instruct/LoRA/FSDP2 configurations, VCBM-blended LOOP improves task success over plain LOOP (0.354 vs. 0.458), reduces final-step max importance weight, and improves token efficiency, with a small KL exception favouring LOOP. The watch-repair result supports the claim that weighting causally relevant steps is more sample-efficient than an undifferentiated baseline or a learned return-redistribution network; the AppWorld result, limited to one seed per arm by a 2-GPU budget, is a compute-limited demonstration at a harder, natural-language scale, not a statistical confirmation.

Figures & tables

AspectTabularAppWorld/LLM
Bookmark detectionStatistical causal-role test (Eq. ( 9 ))Structural rule (state-mutating tool call)
Memory contentWelford (μ,σ2)(\mu,\sigma^{2}) per (key, action)Raw (index, embedding, return) tuples
Retrieval mechanismExact key matchCosine-similarity top- kk (Eq. ( 13 ))
Underlying policyTabular QQ -style controllerLoRA-adapted LLM, PPO-clipped (Eq. ( 8 ))
Fallback when scarceBalanced random samplingFlat floor weight α\alpha
TABLE I: Mechanistic comparison of the two VCBM instantiations.
MethodRangeMean ±\pm stdFinal %
RUDDER1,603–10,9363,327.1 ±\pm 2,010.995.07%
VCBM1,196–7,7571,532.3 ±\pm 1,428.095.07 ±\pm 0.00%
TABLE II: Watch-repair environment: episodes to reach 95% correct first-decisions, 20 seeds each.
Fig. 1: Episodes to converge, RUDDER vs. VCBM, 20 seeds each (log-scale axis). Each row shows the full min–max range (light band) and the mean ±\pm 1 standard deviation (dark segment, marker at the mean). Excluding a single outlier seed (seed 11, 7,757 episodes), the remaining 19 VCBM seeds converge within a 25-episode band (1,196–1,221), against RUDDER’s far wider spread across all 20 seeds.
MetricLOOPVCBMChange
Mean return0.66820.7300+9.3%
Success, all diff.0.35420.4583+29.4%
Success, diff.-avg.0.25690.3333+29.7%
Success, difficulty 10.58330.5000−- 14.3%
Success, difficulty 20.18750.5000+166.7%
Success, difficulty 30.00000.0000no change
TABLE III: AppWorld task performance, final logged training step.
Fig. 2: Mean rollout return per training iteration, single seed each. Left: plain LOOP. Right: VCBM-blended LOOP. Both trend upward over training; VCBM’s later-training returns cluster higher and its trace extends further in logged iterations. Raw W&B panels, not independently smoothed.
MetricLOOPVCBMChange
Max imp. wt., final3.973.09−- 22.2%
Max imp. wt., peak∼\sim 49∼\sim 14∼−\sim- 71%
Max log-prob. diff., peak∼\sim 12.5∼\sim 5.5∼−\sim- 56%
KL estimate, final0.5610.583+4.1%
KL estimate, peak∼\sim 18.5∼\sim 18.5∼\sim tied
Outlier-grad. events22tied
TABLE IV: AppWorld off-policy drift and stability indicators.
MetricLOOPVCBMChange
Output tokens / rollout2,001.61,625.2−- 18.8%
Return / 1,000 tokens0.3340.449+34.6%
TABLE V: AppWorld generation efficiency, final logged training step.
More in this topic

Credit Assignment in RL

Credit assignment in reinforcement learning studies how to trace rewards and failures back to the actions, states, or agents that caused them.

See all 212 papers

Explore similar work

CardsList
Apr 10, 2026

From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models

Reinforcement learning (RL) for large language models (LLMs) increasingly relies on sparse outcome rewards, yet such rewards say little about which token, reasoning step, tool call, memory operation, or agent caused an outcome. This credit assignment (CA) problem spans reasoning RL and becomes sharper in agentic RL, where environment interaction introduces transition non-closure, partial observability, limited replay, heterogeneous actions, weak intermediate verifiability, and agent coupling. We synthesize a unified corpus of 69 papers published from January 2024 through July 31, 2026: 56 core CA methods and 13 adjacent or boundary enablers, selected from 92 deduplicated screening records. We retain the original granularity-by-methodology taxonomy and add a six-diagnostic framework mapping assumption breaks to identification barriers, estimators, and evaluation controls. A source-located full-text audit covers a fixed 42-core-paper subset. Two algorithm researchers independently and blindly cross-coded 252 diagnostic cells, agreeing on 223 (88.5%); per-diagnostic Cohen's kappa ranges from .543 to .909, and principal-family agreement is 42/42 (kappa=1.000). Beyond taxonomy, we establish when restored-state comparisons identify a protocol-specific causal contrast, show that text-only histories can leave even the sign of credit unidentified, and introduce a reusable CA-ID Card linking each claim to its estimand, evidence provenance, and falsification test. An atomic reporting audit describes comparator, budget parity, ablation, overhead, uncertainty, and replay coverage without constructing a cross-paper leaderboard. The companion repository hosts a living catalog and decision aids; a dated release of the frozen audit bundle is planned there separately from the minimal arXiv source.

Chenchen Zhang

Independent Researcher

Credit Assignment in RLRL for Language ModelsFine-Grained Credit AssignmentRL for LLM AgentsCausal RLCounterfactual Credit Assignment
AskPDF
Sep 28, 2026

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

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.

Haodong Zhu, Yangyang Ren, Changbai Li +4

Beihang University · Zhongguancun Academy · Communication University of China +1

Credit Assignment in RLStep-Level Credit Assignment in RLModel-Free RLLong-Horizon LLM AgentsPolicy LearningRL for LLM Agents
AskPDF
Aug 28, 2026

VICT: Verifier-Instrumented Credit Tracing for Long-Horizon LLM Agent Reinforcement Learning

Fine-grained credit assignment is a central challenge in reinforcement learning for long horizon LLM agents. Standard objectives often train from programmatically verifiable terminal rewards by broadcasting each sparse outcome to every action in a trajectory. Existing methods typically seek finer credit from the rollout side, constructing auxiliary trajectory signals or additional comparisons to estimate action importance. Although useful, these approaches still treat the verifier that judged success as a scalar reward, discarding its internal task structure. Our key insight is that many verifiable tasks already encode the relevant checks inside their terminal verifier. We propose VICT (VerifierInstrumented Credit Tracing), a training-time interface that exposes executable or evidence backed atoms and traces them back to actions through dependency-valid proof edges. VICT redistributes group-relative advantage only along those edges, shifting credit assignment from rollout-side inference to verifierside tracing. It preserves the original terminal reward, abstains when evidence is incomplete or ambiguous, and changes only the training-time advantage tensor, requiring no learned critic, process labels, branch rollouts, or inference-time verifier access. On ALFWorld and WebShop, VICT improves substantially over outcome-only training and achieves strong performance alongside recent fine-grained credit methods; ablations rule out dense atom rewards, final-commit credit, temporal proximity, and sparsity as sufficient explanations.

Pengcheng Li, Zhengyang Zhang, Dongxu Zhang +2

Tsinghua University · Xi’an Jiaotong University · Jiaxing Nanhu University

Fine-Grained Credit AssignmentRL for LLM AgentsStep-Level Credit AssignmentReinforcement Learning with Verifiable Rewards
AskPDF