by Haytham ElFadeel - hfadeelm@gmail.com

2024

1. Introduction

Unlike behavior cloning, which copies the average demonstration as-is, reinforcement learning aims to reinforce good actions and discourage bad ones. To do that effectively, we need to know which actions were good, which were bad, and which were irrelevant. This essentially is the credit assignment problem (CAP).

Formally:

Given a return signal, assign blame or credit to the right state-action choices that caused it.

The term was coined by Minsky (1961), who observed that "each ultimate success is associated with a vast number of internal decisions" and that identifying which decisions mattered is a fundamental bottleneck. Six decades later, the CAP remains one of the deepest open problems in RL. It is, arguably, the reason we need RL at all: if we could perfectly decompose an outcome into per-action contributions, policy optimization would reduce to supervised learning.

2. The Three Dimensions of Uncertainty

To make a progress we need to understand the problem, the difficulty comes from three types of uncertainty:

1. Depth - Temporal uncertainty
2. Breadth - Causal uncertainty
3. Density - Signal uncertainty

2.1 Depth — Temporal Uncertainty

When did the decisive action happen?

Depth captures the temporal distance between a consequential action and the reward that eventually reveals its value.

Example. A robot must open a locked door. The trajectory looks like: robot walk to the key location → pick up the key → walk 100 steps to the door → insert the key → receive a reward. The action "pick up the key" was decisive, yet it occurred far before the reward signal. That distance is the depth.

This is hard because the reward signal must propagate backward through a long chain, and this propagation typically degrades. Think of vanishing gradients in backpropagation through time, or the discount factor $γ$ shrinking contributions exponentially. With a discount of $γ = 0.99$ and a delay of 500 steps, the effective credit reaching the decisive action is $0.99^{500} ≈ 0.0066$ — less than 1% of the original signal. Small value or Q-function estimation errors compound when bootstrapped repeatedly over long horizons, further eroding the signal.

2.2 Breadth — Structural / Causal Uncertainty

Which actions mattered versus which were irrelevant?

Breadth captures how many actions or decisions were made, and which subset actually influenced the outcome. In other words, how many paths exist to reach the goal, and which path components were causally responsible.

Example. In a strategy game, an agent builds 50 units, researches 10 technologies, and positions troops across 20 locations before winning a battle. Only 3 of those decisions — building a specific counter-unit, researching armor upgrades, and flanking from the east — actually determined victory. The other 77 decisions were neutral or irrelevant. Identifying the critical 3 among 80 is the breadth problem.

This is hard because correlation does not imply causation: many actions co-occur with success but did not cause it. The agent might learn spurious associations ("I won when I built barracks first" even if that was coincidental). With many concurrent actions, the space of possible credit assignments grows combinatorically, and confounding factors abound — did the agent win because of action A, or because action A enabled action B to succeed?

2.3 Density — Signal Uncertainty

Is there enough learning signal to even infer causality?

Density captures how often the agent receives informative feedback about its performance.

Example. In a maze with only a reward at the exit, the agent might take 10,000 steps across 100 episodes before accidentally stumbling upon the goal once. From that single success, it must somehow learn which of the 10,000 actions were good. With 1 reward signal for 10,000 actions, the density of feedback is extremely low.

This is hard because of statistical insufficiency — with few reward events, there is not enough data to reliably distinguish signal from noise. The agent must discover rewarding states before it can learn from them (the exploration burden), and TD bootstrapping methods fail when most states have near-zero estimated value, leaving nothing meaningful to bootstrap from.

3. Why Standard Methods Struggle

Before diving into solutions, it is worth understanding why the tools most practitioners reach for first — GAE, n-step returns, discount tuning — run into fundamental limits on the CAP.

The Discount Dilemma

Consider an LLM being trained with RLVR or RLHF. The model generates a chain-of-thought response of, say, 1,000 tokens, and receives a single outcome reward at the end (correct/incorrect). Standard temporal-difference methods like n-step returns or GAE attempt to propagate that terminal reward backward.

With a typical discount factor ($γ = 0.999$), the reward decays rapidly before reaching early tokens. The effective credit arriving at token 1 is $γ^{999} ≈ 0.00043$ of the terminal reward — effectively vanishing due to the episode length. Early decisions that set up the entire reasoning strategy receive negligible gradient signal.

The Dilution Dilemma

The obvious fix is to push γ toward 1.0, which is exactly what most LLM RL methods do. This preserves signal magnitude, but introduces a different problem: reward dilution. By indiscriminately assigning credit to all 1000 tokens for a single binary outcome, we obscure the specific causal link between early decisions and the final result. Every token — filler words, formatting, genuinely critical reasoning steps — receives the same advantage estimate. The result is high-variance gradient estimates that wash out the signal from the few tokens that actually mattered.

This is the core tension: discount too aggressively and the signal vanishes; discount too little and the signal gets diluted across irrelevant actions. Neither extreme solves the CAP. We need methods that can identify which actions mattered, not just propagate a blanket signal backward.

4. A Taxonomy of Solutions

Solutions to the CAP can be organized into several broad families.

• Time-Centric Methods
• Backward-Looking / Hindsight Methods
• Goal-Conditioned RL / Auxiliary goals.
• Backward / Reverse Planning
• LLM-Specific Credit Assignment Methods

4.1 Time-Centric Methods — Reducing the Effective Depth

These methods directly attack the temporal credit assignment problem: how to propagate a delayed reward backward to the early actions that caused it.

4.1.1 Multi-Step Bootstrapping and Eligibility Traces

Instead of bootstrapping from the immediate next state (1-step TD) or waiting for the full return (Monte Carlo), these methods mix returns at different horizons. n-step returns use the actual rewards for n steps and then bootstrap from a value estimate. TD(λ) and GAE blend all n-step returns together using an exponentially decaying weight λ.

By looking further ahead before bootstrapping, multi-step methods reduce the bias that comes from inaccurate value estimates at nearby states. The λ parameter controls the bias-variance tradeoff: λ = 0 gives 1-step TD (low variance, high bias), λ = 1 gives Monte Carlo (high variance, zero bias), and intermediate values balance the two. GAE (Generalized Advantage Estimation) is the most widely used version and is the default in PPO, GRPO, and most modern policy gradient methods.

These methods treat all actions within the n-step or λ-decay window equally — they have no mechanism to distinguish a decisive action from an irrelevant one that happened to be temporally proximate. The exponential decay in λ still uses temporal distance as a proxy for relevance, which is only a heuristic. In LLM training with γ = 1 (common in GRPO, RLOO), GAE with any λ reduces to the Monte Carlo return — no actual credit shaping occurs.

Methods: TD(λ), n-step SARSA, n-step Q-learning, GAE (Schulman et al. 2016), V-trace (Espeholt et al. 2018).

4.1.2 Reward Decomposition and Credit Redistribution

These methods take a single delayed reward and decompose it into a sequence of per-step credits that sum to the original return but are temporally aligned with the decisive actions. The resulting "redistributed reward" defines a new MDP with the same optimal policy but much denser feedback.

If the redistribution is optimal (each step receives credit proportional to its causal contribution), then TD methods become unbiased in the new MDP and MC methods have minimal variance. The key events get concentrated reward signal while irrelevant steps get near-zero signal, solving both the depth problem (no long-range propagation needed) and partially the breadth problem (irrelevant actions are filtered out).

How they differ from reward shaping. Classical potential-based reward shaping (Ng et al. 1999) adds a shaped reward Φ(s') − Φ(s) that preserves the optimal policy. Reward redistribution is more general: it rewrites the entire reward sequence while preserving the return, allowing for non-potential-based credit that can adapt to the specific trajectory. RUDDER shows that optimal redistribution makes the expected future reward zero everywhere, which is a stronger property than potential-based shaping provides.

Methods: RUDDER (Arjona-Medina et al. 2019), Align-RUDDER (Patil et al. 2020), IRCR (Gangwani et al. 2020), AREL (Xiao et al. 2022), Sequence Modeling of Temporal Credit Assignment (Liu et al. 2019).

4.1.3 Temporal Abstraction and Hierarchical RL

Instead of making decisions at every time step, temporal abstraction compresses long-horizon problems into fewer high-level decisions. A hierarchical policy selects "options" (temporally extended actions, each running a sub-policy for multiple steps), and credit only needs to be assigned among the small number of option-level decisions rather than among thousands of primitive actions.

If a 1000-step episode can be decomposed into 5 option-level decisions, the effective depth drops from 1000 to 5. Within each option, the sub-task reward is typically denser and the horizon shorter, making credit assignment tractable at both levels. This is analogous to how humans plan: we decide to "go to the grocery store" rather than planning each individual muscle movement.

Discovering the right abstraction is itself a difficult learning problem. If the option boundaries don't align with the causal structure of the task, hierarchical RL can actually make credit assignment harder (the wrong sub-goal decomposition introduces new credit assignment problems at the option level). Most hierarchical methods require domain knowledge to define the option set or sub-goal space, though recent work on unsupervised option discovery partially addresses this.

Methods: Options framework (Sutton, Precup, Singh 1999), MAXQ (Dietterich 2000), Feudal Networks (Vezhnevets et al. 2017), HAM (Parr & Russell 1998), h-DQN (Kulkarni et al. 2016).

4.1.4 Reward Transport

These methods use attention mechanisms to identify which past state-action pairs were decisive, then "transport" or "splice" the distant future reward back to those moments. Rather than relying on discounted propagation through the entire chain, they jump directly from the reward event to the causal action.

Transport bypasses the exponential decay of discounting entirely. A decisive action at time step 10 that enabled a reward at time step 500 receives the full transported reward, regardless of the 490-step gap. The attention mechanism provides a data-driven (rather than purely temporal) measure of relevance.

How they differ from redistribution. Redistribution methods (RUDDER) retrain a full return predictor and redistribute the entire return across all steps. Transport methods are lighter: they identify a small number of critical steps via attention, augment those steps' rewards, and leave the rest unchanged. This makes them modular add-ons to existing RL algorithms.

Methods: Temporal Value Transport (Hung et al. 2019), TRT (Patil et al. 2020).

4.1.5 Notes

Reward Transport - Temporal Value Transport (Hung et al. 2019), TRT (Patil et al. 2020) have been the most successful methods due to the ability of attention to look back and relevant actions, followed by RUDDER (Arjona-Medina et al. 2019). Time-Centric Methods are closely related to LLM specific methods like progress reward models.

4.2 Backward-Looking / Hindsight Methods — Inverting the Credit Question

These methods flip the direction of credit assignment. Instead of asking "given this action, what reward should I expect?" (the forward view), they ask "given this outcome, which actions were responsible?" (the backward view). This inversion can be more efficient when the forward path is noisy but the backward path is clear.

4.2.1 Hindsight Credit Assignment (HCA)

HCA learns a hindsight distribution h(a | x, z) — the probability that action a was taken in state x, given that outcome z was observed. By comparing this to the policy π(a | x), the hindsight ratio h/π reveals which actions were unusually associated with the observed outcome. Actions with high hindsight ratios are credited; actions with ratios near 1.0 are deemed irrelevant.

HCA directly tackles the breadth problem. In a trajectory where 77 out of 80 actions are irrelevant, the hindsight distribution for those 77 actions will be nearly identical to the policy distribution (the outcome doesn't tell you anything about which irrelevant action was taken), so their hindsight ratios are close to 1. Only the 3 decisive actions will have significantly elevated ratios. This filtering happens automatically, without requiring explicit causal modeling.

Methods: HCA (Harutyunyan et al. 2019), COCOA (Meulemans et al. 2023), H-DICE (Velu et al. 2023).

4.2.2 Hindsight Experience Relabeling (HER)

When the agent fails its intended goal, these methods treat what the agent did achieve as an alternative goal, creating a successful experience from a failure. This is not about assigning credit within a trajectory but about manufacturing signal from trajectories that would otherwise be wasted.

HER directly attacks the density problem. In sparse-reward environments, the agent might go thousands of episodes without a single success. Goal relabeling converts every episode into a useful training signal by asking "what goal would this trajectory have achieved?" The answer is always at least one goal (the actual terminal state), giving the agent a steady stream of positive examples to learn from.

Methods: HER (Andrychowicz et al. 2017), DHER for dynamic goals (Fang et al. 2019), Hindsight Task Relabelling for meta-RL (Eysenbach et al. 2021).

4.3 Goal-Conditioned RL and Auxiliary Goals

4.3.1 Universal Value Functions

Instead of learning a single value function V(s) for one task, Universal Value Function Approximators (UVFAs) learn V(s, g) — a value function conditioned on the goal g. This means a single model captures the value of every state under every possible goal, turning the RL problem into something closer to supervised learning across a distribution of goals.

With a UVFA, the agent can generalize across goals: learning to reach goal A provides information about how to reach nearby goal B. This improves sample efficiency by sharing credit information across tasks. Combined with HER (which provides a curriculum of achieved goals), UVFAs enable learning in environments where no single goal would provide enough signal on its own.

Methods: UVFAs (Schaul et al. 2015), goal-conditioned policies (Kaelbling 1993, Schaul et al. 2015), RIG (Nair et al. 2018).

4.3.2 General Value Functions (GVFs)

GVFs predict many "future signals" beyond the task reward. A signal can be any signal derivable from the state: the rate of change of a sensor, whether a particular object is nearby, the agent's velocity, etc. Each signal defines its own value function, and the agent learns all of them simultaneously.

GVFs provide auxiliary learning signal that helps the agent build a rich internal model of the environment dynamics. Even when the task reward is sparse, the GVF predictions are dense and informative, helping learn useful state representations. When a GVF prediction suddenly changes, it signals that something important happened — providing a form of implicit credit assignment.

Methods: GVFs (Sutton et al. 2011), Horde architecture (Sutton et al. 2011), UNREAL (Jaderberg et al. 2017).

4.4 Backward Planning

4.4.1 Backward / Reverse Planning

Instead of planning forward from the current state, these methods learn to plan backward from the goal or reward state. A backward model or backward policy answers "what state likely preceded this one?" Starting from the reward state and chaining backward identifies the sequence of states (and therefore actions) that led to success.

For environments where the reward state is known but the path to it is unknown, backward planning can be more efficient. Forward search fans out into many branches, most of which are dead ends. Backward search from the known goal state narrows the search space because there are typically fewer predecessors of the goal than successors of the start state.

Methods: Recall Traces (Goyal et al. 2019), Expected Eligibility Traces (van Hasselt et al. 2021), backward model learning approaches.

4.5 LLM-Specific Credit Assignment Methods

The rise of RL for language models (RLHF, RLVR) has created a new instantiation of the CAP with distinctive features: the "trajectory" is a token sequence, "actions" are token choices, the action space is enormous (vocabulary size ~100K), rewards are typically binary and terminal, and the policy is a pre-trained language model with strong priors. These features have motivated a family of methods tailored to the LLM setting.

4.5.1 Outcome Reward Models (ORMs)

An ORM provides a single scalar reward for a complete response. In RLHF, this is a preference score; in RLVR, it is a binary correctness signal. The reward is assigned at the EOS token, and all preceding tokens receive zero intermediate reward.

ORMs create the maximal depth problem: the entire response is one long episode with terminal-only reward. Methods like GRPO and RLOO handle this by using group-relative advantages (comparing multiple responses to the same prompt), but all tokens in a response share the same advantage, providing zero within-trajectory credit information. This is reward dilution.

4.5.2 Process Reward Models (PRMs)

PRMs provide a correctness score at every reasoning step boundary (typically newlines or other delimiters). Each step is labeled as correct, neutral, or incorrect.

PRMs reduce the depth from "entire response" to "one step," which is a significant improvement. However, within each step (which may contain dozens of tokens), all tokens receive the same credit. PRMs also do not distinguish between correct but irrelevant steps and correct and decisive steps — they measure step-level correctness, not step-level causal contribution to the outcome.

Key challenges: Step-level labels are expensive. Automatic labeling via Monte Carlo rollouts (Math-Shepherd, MCTS-based methods) is computationally intensive and is noisy — a step might be labeled "correct" because a lucky rollout happened to reach the right answer, not because the step was logically sound.

4.5.3 Progress Reward Models

Instead of measuring correctness at each step, progress models measure progress — the change in the probability of eventually reaching a correct answer. A step that is correct but unhelpful (e.g., restating the problem) receives near-zero progress reward. A step that dramatically simplifies the remaining problem receives high progress reward.

Credit assignment implications: Progress models address the depth problem and offer benefits to breadth more directly than PRMs: they distinguish between steps that are correct-but-irrelevant and steps that are correct-and-decisive. The "progress" signal is essentially a step-level advantage function estimated via a prover policy (i.e. another policy).

4.5.4 Token-Level Reward Models and Q-Function Methods

These push the granularity to individual tokens. Q-RM learns token-level Q-functions from preference data via a discriminative (non-generative) policy. DPO-implicit reward models extract per-token rewards from the log-probability ratios of DPO-trained models. GRPO-λ applies eligibility traces with token-level log-probabilities to approximate λ-returns within GRPO.

Credit assignment implications: Token-level methods provide the finest possible granularity of credit in the LLM setting. They can identify that the token "0.05" in a math solution is critical while the token "the" is irrelevant. However, they face the breadth problem acutely: with hundreds of tokens per response, distinguishing the 5 decisive tokens from the 495 irrelevant ones requires strong inductive biases or large amounts of comparative data (e.g., many rollouts per prompt to build informative prefix trees).

Methods: Q-RM, GRPO-λ, GTPO.

4.6 Summary: Which Methods for Which Problems?

In practice, the most effective approaches combine methods from multiple families. For example, RUDDER (redistribution) can be combined with PPO (bootstrapping + eligibility traces); HER (density) can be paired with UVFAs (future-conditioning); and in LLM training, Q-RM (token-level credit) can replace GAE within PPO. The choice of method depends on which dimensions of the CAP dominate in your specific problem.

5. RUDDER — Return Decomposition for Delayed Rewards

Arjona-Medina et al., "RUDDER: Return Decomposition for Delayed Rewards" (NeurIPS 2019)

Core Idea

RUDDER proposes that rather than propagating a delayed reward backward through value functions (which introduces bias via TD or variance via MC), redistribute the reward so that it arrives at the time steps where the decisive actions happened. The key insight is that if we can decompose the return into per-step contributions that sum to the original return and are temporally aligned with the actions that caused them, we create a new MDP with the same optimal policy but no delayed rewards. In this transformed MDP, TD methods are unbiased and MC methods have minimal variance.

How It Works

RUDDER trains an LSTM to predict the episode return from the sequence of state-action pairs. The LSTM reads the trajectory $(s₁, a₁), (s₂, a₂), ..., (sₜ, aₜ)$ and at each step outputs a running prediction of the final return. If the LSTM's return prediction is accurate, then the differences between consecutive predictions — $Δₜ = ĝ(t) − ĝ(t−1)$ — represent how much each state-action pair contributed to the return.

These differences become the redistributed reward: $r̃ₜ = Δₜ$. When a key event happens (e.g., the agent picks up the key), the LSTM's return prediction jumps, producing a large positive Δ at that time step. During irrelevant steps, the prediction barely changes and the redistributed reward is near zero. Critically, the redistributed rewards sum to the original return (by telescoping), preserving the optimal policy.

RUDDER uses contribution analysis methods from deep learning — specifically layer-wise relevance propagation and integrated gradients applied to the LSTM — to perform the "backward analysis" that decomposes predictions into per-input contributions. An auxiliary "monotonic LSTM" variant is introduced to ensure the return prediction increases monotonically over the episode, which simplifies the decomposition.

Theoretical Guarantees

RUDDER proves that TD methods take time exponential in the length of the delay to remove bias in their Q-value estimates under delayed rewards. MC methods, while unbiased, suffer from variance that scales with the trajectory length. RUDDER's optimal reward redistribution makes TD unbiased and reduces MC variance simultaneously, since the expected future redistributed reward from any state is zero.

Results

On artificial tasks with varying reward delays, RUDDER is exponentially faster than TD, MC, and MC Tree Search. On Atari games with heavily delayed rewards (Venture, Bowling), RUDDER augmenting PPO set new state-of-the-art results in a fraction of the training time required by Rainbow, A3C, and other deep RL methods.

Limitations

RUDDER is aimed at problems with delayed rewards, no distracting intermediate rewards, and no complex skills to be learned en route to the delayed reward. When sporadic intermediate rewards exist, the improvements may be limited. The LSTM return predictor adds computational overhead, and the quality of the redistribution depends on the LSTM's ability to identify key events.

6. Temporal Reward Transport (TRT)

Hung et al., "Temporal Value Transport" (DeepMind, 2019); Patil et al., TRT variant (2020)

Core Idea

Temporal Reward Transport uses an attention mechanism to identify which past state-action pairs were critical for later rewards, then "transports" (splices) the distant future reward back to those critical moments. Instead of relying on discounted propagation — which exponentially attenuates the signal — TRT directly augments the immediate reward of important early actions with the distant reward they enabled.

How It Works

TRT operates as a modular add-on to a standard actor-critic algorithm (e.g., A2C). A separate binary classifier with a self-attention layer is trained to predict whether the undiscounted return for an episode exceeds a threshold. The attention weights of this classifier reveal which state-action pairs the model considers most predictive of high returns.

At each time step t, if the attention weight is high (indicating the classifier considers (sₜ, aₜ) to be decisive), TRT augments the immediate reward rₜ by splicing in a portion of the rewards-to-go from later in the episode. Specifically, the transported reward is drawn from a future time step t' where a significant reward occurred, and is added to the reward at time t. This bridges the temporal gap without requiring discounted propagation.

The key distinction from RUDDER is architectural: TRT does not retrain a full return predictor; instead, it uses a lightweight attention-based classifier to identify transport candidates, and directly modifies the reward stream seen by the base RL algorithm. The decoupled design means TRT can increase the classifier's learning rate without destabilizing the actor-critic, and can be plugged into any RL algorithm as a reward-shaping module.

Results

In gridworld experiments with long delays between action and effect (e.g., picking up a key in phase 1, receiving a distant reward in phase 3, with a variable-length distractor phase in between), A2C+TRT consistently outperforms baseline A2C. The improvement is most pronounced when the delay exceeds the discount factor timescale $τ_γ = \frac{1}{(1−γ)}$, precisely the regime where standard discounting fails.

Limitations

TRT is a heuristic — the attention weights provide a proxy for causal relevance, not a principled causal analysis. In environments where many actions are weakly correlated with the reward, the attention mechanism may distribute weight too broadly, reducing the effectiveness of the transport. TRT also requires episodic data and a clearly identifiable "reward event" to transport from.

7. Hindsight Experience Replay (HER)

Andrychowicz et al., "Hindsight Experience Replay" (NeurIPS 2017)

Core Idea

HER addresses the density dimension of the CAP: when rewards are sparse and binary ("did you reach the goal? yes/no"), the agent almost never encounters positive reward, leaving it with no useful gradient signal. HER's insight is inspired by human learning: even when you fail at your intended goal, you still learn something about the world. If you tried to throw a ball into a specific basket and missed, you still learned how to throw a ball to the location where it actually landed.

How It Works

HER operates within a goal-conditioned RL framework, where the agent receives as input both the current state and a desired goal g, and the reward function is $r(s, a, g) = 1$ if the achieved state matches the goal, $0$ otherwise. Standard RL with this sparse binary reward fails catastrophically — the agent almost never achieves the intended goal through random exploration.

HER modifies the experience replay buffer. After collecting a trajectory with the original goal g, HER also stores the same trajectory replayed with substitute goals — most commonly, the state actually achieved at the end of the episode, $g' = m(sₜ)$. Under this substitute goal, the trajectory is successful (the agent did reach the state it reached), so the reward is now 1 instead of 0. The agent learns "how to reach state g'" from these relabeled experiences, building a general understanding of how its actions affect the environment. Over time, this understanding transfers to the original goals.

Several goal-sampling strategies exist: "final" (use the achieved final state), "future" (use a state achieved later in the same episode), "episode" (sample from any state in the episode), and "random" (sample from the entire replay buffer). In practice, the "future" strategy — sampling goals from states visited later in the same episode — tends to work best.

Why It Works (Credit Assignment Perspective)

HER changes the reward density. Without HER, the agent in a robotic manipulation task might go thousands of episodes without a single positive reward. With HER, every episode generates useful training signal because every trajectory is a success under some goal. This converts a near-zero density signal into a dense one. The credit assignment problem becomes tractable because the agent no longer has to wait for rare successes to learn from — it learns from every experience by reframing what counts as success.

HER can be combined with any off-policy RL algorithm (DQN, DDPG, SAG, etc.) and may be viewed as a form of implicit curriculum: the agent first learns to reach easily achievable states, then progressively learns to reach more distant goals as its policy improves.

Results

In robotic manipulation tasks (pushing, sliding, pick-and-place), vanilla DDPG with sparse binary rewards completely fails to learn. DDPG+HER successfully learns all three tasks and the learned policies transfer to a physical robot without fine-tuning. Ablation studies confirm that HER is the crucial ingredient enabling learning in these environments.

Limitations

HER requires a goal-conditioned setup with a known goal-reward mapping, which limits its applicability to environments where you can define goals in terms of achieved states. It also requires an off-policy algorithm, since the relabeled experiences have different goals than the one actually pursued during data collection. HER primarily addresses the density problem; it does not directly reduce depth or breadth difficulties, though the denser reward signal indirectly helps with both.

8. Hindsight Credit Assignment (HCA)

Harutyunyan et al., "Hindsight Credit Assignment" (NeurIPS 2019)

Core Idea

While HER relabels goals, HCA relabels credit. The standard forward-looking view of credit assignment asks: "given that I took action a in state x, what return can I expect?" HCA inverts this into a backward-looking question: "given that I observed outcome z, how likely is it that action a was responsible?"

The key insight is that value functions can be rewritten through a hindsight lens, yielding a new family of estimators that assign credit to past actions based on the likelihood of those actions having led to the observed outcome.

How It Works

HCA introduces the concept of a hindsight distribution h(a | x, z), which represents the probability that action a was taken in state x, given that outcome z was later observed. This is contrasted with the policy π(a | x), which represents the probability of taking action a without knowledge of the future.

The hindsight ratio — $\frac{h(a | x, z)}{π(a | x)}$ — captures how much more or less likely action a was, given that outcome z occurred. If a particular action is much more likely under the hindsight distribution than under the policy (ratio >> 1), that action is strongly associated with the outcome. If the ratio is near 1, the action was irrelevant to the outcome.

HCA shows that the Q-value can be rewritten as:

$Q(x, a) = E_z [ \frac{h(a|x,z) }{ π(a|x)} · z ]$

This reformulation replaces the standard forward sum over future rewards with a backward weighted average over outcomes, where the weights are hindsight ratios. The advantage of this formulation is that it can ignore irrelevant parts of the trajectory: if an action at time 0 has no causal influence on what happens between times 1 and T−1, the hindsight ratio filters out the noise from those irrelevant steps.

Two variants are studied: state-conditional HCA, where the future conditioning is on a particular future state s', and return-conditional HCA, where the conditioning is directly on the observed return z. Return-conditional HCA is more appealing because instead of conditioning on high-dimensional states, it conditions on a scalar outcome.

Why It Matters

HCA addresses issues that TD and MC both struggle with. TD methods use temporal proximity as a proxy for relevance, which is only a heuristic — a temporally distant action can be more relevant than a proximate one. MC methods incorporate all trajectory noise into the credit estimate. HCA can directly determine the relevance of a past action to a particular outcome, regardless of temporal distance.

Limitations and Extensions

HCA requires learning the hindsight distribution, which can be challenging. Measuring contributions with respect to rewarding states (as in the original HCA) can produce spurious estimates — an action might influence reaching a state without influencing the reward at that state. COCOA (Counterfactual Contribution Analysis, Meulemans et al. 2023) addresses this by measuring contributions with respect to rewards directly, asking: "would the agent still have received this reward if it had taken another action?" This reduces the variance and eliminates the spurious contributions that cause HCA to degrade toward the REINFORCE estimator.

9. LLM-Specific — The Q-function Reward Model (Q-RM)

Chen et al., "Discriminative Policy Optimization for Token-Level Reward Models" (ICML 2025)

Motivation

In LLM alignment and reasoning, the standard reward model (ORM) provides a single scalar at the end of a complete response. This is a pure credit assignment problem: a 500-token chain-of-thought receives one binary signal, and every token gets the same advantage estimate under GRPO or similar methods. Process reward models (PRMs) improve on this by providing step-level scores, but "steps" are coarse (typically separated by newlines), and recent work extending PRMs to token-level granularity has conflated reward modeling with language generation, causing instability.

Core Idea

Q-RM decouples reward modeling from language generation entirely. Instead of deriving token-level rewards from the generation probabilities of a generative model (which creates a conflict between the language modeling objective and the reward modeling objective), Q-RM optimizes a discriminative policy — a model that does not generate text but instead assigns a Q-value to each token position in a given trajectory.

How It Works

Starting from the Bradley-Terry preference model and the maximum entropy RL framework, Q-RM shows that the logits of an optimally trained discriminative policy correspond to token-level Q-functions. Specifically, for a response trajectory τ, the token-level Q-value at position t is derived from the discriminative model's logit for the actual token at that position.

Training proceeds on standard preference data (chosen/rejected pairs) without requiring any fine-grained per-step annotations. The discriminative model learns to assign high Q-values to tokens in the chosen trajectory that are genuinely credit-worthy (e.g., correct intermediate computations like "0.05" in a math problem) and low Q-values to tokens in the rejected trajectory that caused failure (e.g., an incorrect value like "$135"). In contrast, DPO-derived reward models (DPO-RM) tend to assign high rewards to structural tokens like line breaks, which carry no causal information about correctness.

Q-RM integrates directly with PG (e.g. PPO, REINFORCE) as a token-level advantage signal, potentially can replace GAE entirely. Because the Q-function provides per-token advantages, it eliminates the need for a separate critic network.

Results

When integrated with PPO/REINFORCE, Q-RM improves average Pass@1 scores by approximately 5 points on mathematical reasoning tasks compared to ORM baselines, and by approximately 4-5 points compared to token-level PRM counterparts. Most strikingly, RL training with Q-RM converges 12× faster than ORM on GSM8K and 11× faster than step-level PRM on MATH, demonstrating that precise credit assignment translates directly into training efficiency.

10. LLM-Specific — Process Reward Models (PRMs)

Lightman et al., "Let's Verify Step by Step" (ICLR 2024); Uesato et al. (2022); Wang et al. "Math-Shepherd" (ACL 2024)

Core Idea

A Process Reward Model provides supervision not just at the end of a response, but at every reasoning step. Where an Outcome Reward Model (ORM) says "the final answer is correct/incorrect," a PRM says "step 1 is correct, step 2 is correct, step 3 is wrong." This directly addresses the credit assignment problem by localizing error to the step where reasoning went astray.

How It Works

PRMs are trained to output a score at the boundary of each reasoning step (typically identified by newline tokens or other delimiters). Each step receives one of three labels: correct (+1), neutral (0), or incorrect (-1). The PRM is trained with a cross-entropy loss at step boundaries, with all other tokens masked during training.

The key challenge is obtaining step-level annotations. The original "Let's Verify Step by Step" work used human annotators (resulting in the PRM800K dataset), which is accurate but expensive and unscalable. Subsequent work has explored automatic labeling strategies. Math-Shepherd uses the policy model to generate completions from each intermediate step and checks if any completion reaches the correct answer — if so, the step is labeled correct. MCTS-based approaches (ReST-MCTS*, AgentPro) use Monte Carlo Tree Search to simulate forward from each step and assign labels based on the success rate of simulations.

Usage

PRMs serve two main purposes. At inference time, they enable best-of-N search: generate N candidate solutions and select the one whose worst step score is highest (the "min" aggregation strategy tends to outperform mean aggregation because it catches the first error). At training time, PRMs provide dense rewards for RL: instead of a single terminal reward, each step receives a reward from the PRM, giving the policy gradient much finer-grained credit.

Limitations

PRMs require step boundaries to be well-defined, which works for structured math reasoning but is less natural for open-ended generation. The step-level granularity is still coarse — within a step, all tokens receive the same credit. Human labels are expensive, and automatic labeling methods introduce noise (a step might be labeled "correct" because a lucky completion happened to reach the right answer, not because the step was logically sound). PRMs also tend to be domain-specific: a PRM trained on math may not transfer to code or general reasoning.

Open Problems and Future Directions

Several fundamental challenges remain.

Compositional credit is largely unsolved: in multi-step reasoning, one step might be correct in isolation but redundant given a previous step, or incorrect in isolation but useful as a stepping stone. Current methods evaluate steps independently, missing these interactions.

Cross-domain transfer of credit assignment is underexplored. A PRM trained on math does not help with code; a Q-RM trained on preference data for helpfulness may not transfer to safety. Learning domain-agnostic credit assignment — identifying structural properties of decisive actions — remains open.

Finally, the relationship between credit assignment and exploration deserves more attention. Better credit assignment helps the agent learn from the data it has, but the agent also needs to explore to find informative experiences. HER showed that creative relabeling can convert uninformative experiences into informative ones; extending this idea to LLM training (where "exploration" means generating diverse reasoning strategies) is a promising but largely untapped direction.

References

• Andrychowicz, M. et al. (2017). Hindsight Experience Replay. NeurIPS.
• Arjona-Medina, J.A. et al. (2019). RUDDER: Return Decomposition for Delayed Rewards. NeurIPS.
• Chen, H. et al. (2025). Discriminative Policy Optimization for Token-Level Reward Models (Q-RM). ICML.
• Harutyunyan, A. et al. (2019). Hindsight Credit Assignment. NeurIPS.
• Hung, C.C. et al. (2019). Optimizing Agent Behavior over Long Time Scales by Transporting Value. Nature Communications.
• Lightman, H. et al. (2024). Let's Verify Step by Step. ICLR.
• Mesnard, T. (2023). Credit Assignment in Deep Reinforcement Learning. PhD Thesis, Institut Polytechnique de Paris.
• Meulemans, A. et al. (2023). Would I Have Gotten That Reward? Long-term Credit Assignment by Counterfactual Contribution Analysis. NeurIPS.
• Minsky, M. (1961). Steps Toward Artificial Intelligence. Proceedings of the IRE.
• Patil, V. et al. (2020). Align-RUDDER: Learning from Few Demonstrations by Reward Redistribution.
• Pignatelli, E. et al. (2023). A Survey of Temporal Credit Assignment in Deep Reinforcement Learning.
• Wang, P. et al. (2024). Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. ACL.