RUDDER: Return Decomposition for Delayed Rewards

1 Introduction

• Delayed rewards worsen TD bias and MC variance: TD may need exponentially many updates, while the states affected by a reward can grow exponentially with delay.When rewards, transitions, or policies are probabilistic, MC must average over possible future trajectories.Source: §1 · p. 1
• RUDDER combines reward redistribution toward zero expected future rewards with return decomposition via contribution analysis to learn redistributions.The target is a return-equivalent sequence-Markov decision process (SDP), where Q-value estimation reduces to the mean of immediate rewards while Q-values or advantages can still support optimal-policy learning.Source: §1 · p. 2
• Contribution analysis predicts return from completed state-action sequences and identifies pairs to receive redistributed rewards, avoiding reliance on unknown future trajectories.The introduction illustrates this with supervised pattern recognition that identifies delivery-cost patterns from completed deliveries.Source: §1 · p. 2
• Unlike fixed shaping methods, RUDDER learns redistribution gradually; unlike sensitivity-analysis approaches, it uses contribution analysis over whole sequences.The introduction also notes that potential-based shaping keeps original rewards and may remain exponentially slow, while TVT [59] neither guarantees preserved optimal policies nor near-zero expected future rewards.Source: §1 · p. 2

Reward Redistribution

• Return-equivalent SDPs preserve optimal policies, and reward redistribution constructs strictly return-equivalent processes by redistributing sequence-associated returns.Strict return equivalence means expected return is unchanged for every episode and policy.Source: §2 · p. 3

Optimal Reward Redistribution with Expected Future Rewards Equal to Zero

• Optimal redistribution makes expected future rewards zero, reducing Q-value estimation to the mean immediate reward; it may violate Markov assumptions, motivating the use of SDPs.For a delayed-reward MDP, the proposed optimal redistribution is second-order Markov and return-equivalent to the original process.Source: §2 · pp. 3–4
• For a specific policy, optimal second-order Markov redistribution is equivalent to making each expected redistributed reward the difference between consecutive original Q-values, eliminating delayed rewards.The redistributed reward has zero expected future contribution, so no state-action pair can increase or decrease the expectation of a future reward.Source: §2 · p. 4
• With optimal redistribution, the redistributed Q-value is its expected immediate reward and differs from the original Q-value by a state-dependent offset; both processes have the same advantage function.When redistribution is non-optimal, the expected future rewards measure the deviation of Q-values from the immediate reward.Source: §2 · p. 4

Novel Learning Algorithms Based on Reward Redistributions

• For γ = 1 finite-horizon or absorbing tasks, proposed algorithms gradually change redistributions and use Q-value estimation, policy gradients, or Q-learning with redistributed rewards.Learning combines an LSTM and Q-value update; convergence under standard assumptions follows two-time-scale stochastic approximation, though locally stable attractors can complicate convergence to an optimal policy. Policy-gradient offsets reduce variance like baseline normalization, and Q-learning is justified when immediate and future rewards are drawn together.Source: §2 · pp. 4–5

Reinforcement Learning as Pattern Recognition

• RUDDER targets the largest Q-value differences because redistributions closer to those differences are more optimal and can speed learning.The method frames sequence-wide return prediction and identifying contributing state-action transitions as a pattern-recognition task.Source: §3 · p. 5

Return Decomposition

• Contribution analysis assigns each state-action pair its contribution to predicted return; RUDDER considers prediction differences, integrated gradients [125], and layer-wise relevance propagation.Prediction differences are preferred because shared past and future contributions cancel between consecutive predictions; integrated gradients and relevance propagation can use later sequence information, introducing non-Markov, high-variance rewards. Sensitivity analysis misses action relevance and can suffer local minima, instability, exploding or vanishing gradients, and exploration problems.Source: §3 · p. 5

Explaining Away Problem

• To prevent later states from explaining away earlier reward-causing actions, RUDDER defines differences between consecutive state-action pairs and redistributes contributions across the sequence.A compensating terminal reward accounts for the difference between realized return and the sum of contributions, preserving strict return equivalence.Source: §3 · pp. 5–6

Return Decomposition

• Zero return-prediction error yields an optimal reward redistribution, while small errors yield a redistribution close to optimal.The redistribution includes a compensating reward at time T + 2 to preserve strict return equivalence when the prediction is imperfect.Source: §3 · p. 6

RUDDER: Return Decomposition using LSTM

• RUDDER uses safe exploration, a lessons replay buffer, and an LSTM trained to predict sequence-wide return at every time step; prediction differences then construct the redistribution.Episodes with unseen delayed rewards are saved, and those with larger LSTM prediction errors are sampled more often for training.Source: §3 · p. 6

Feedforward Neural Networks (FFNs) vs. LSTMs

• LSTMs are less prone than feedforward networks to produce spurious rewards because they reuse stored information and their correlated prediction errors are more likely to cancel.Feedforward networks repeatedly predict expected return from each state-action pair without stored information, so prediction errors can generate false contributions.Source: §3 · p. 6

Human Expert Episodes

• Human expert episodes can fill the lessons buffer, and return decomposition can reward human key actions even in low-return episodes.Other actions that thwart high returns receive negative reward; human demonstrations have improved some Atari games, including Montezuma’s Revenge [93] [2].Source: §3 · p. 6

Limitations

• RUDDER may be less effective without delayed rewards because LSTM training adds time and struggles with very long sequences, and redistribution can create spurious rewards.Source: §3 · p. 7

Artificial Tasks (I)–(III)

• With p-values < 10^-12, RUDDER significantly outperformed all other methods on Grid World, with speed-ups versus MC and MCTS suggesting exponential growth with delay.The task tests whether the agent learns that defusing the bomb before running away yields higher expected reward than immediately running away.Source: §4 · p. 7, Figure 1 · p. 8
• With p-values < 10^-8, RUDDER significantly outperformed all other methods on The Choice; its speed-up versus MC suggests exponential growth with delay.MC struggles because large future rewards unrelated to the first action impede estimation of the expected future reward caused by that action.Source: §4 · pp. 7–8, Figure 1 · p. 8
• With p-values < 10^-17, RUDDER was exponentially faster than all other methods on Trace-Back, significantly outperforming reward shaping, SARSA(λ), and Q(λ).Only the first two actions affect return, but the optimal action at t = 2 receives an immediate reward of −50 while other actions receive 50.Source: §4 · pp. 7–8, Figure 1 · p. 8

Atari Games

• 32 games (RUDDER) versus 20 (baseline) learned faster on average, and 29 (RUDDER) versus 23 (baseline) had higher average scores in the last 10 training games.For Bowling, Solaris, Venture, and Seaquest—selected for their delayed rewards—RUDDER considerably increased scores over the PPO baseline. The baseline used reward scaling and RUDDER’s safe-exploration strategy; the Table 1 caption identifies the delayed-reward games but does not provide individual score values here.Source: §4 · pp. 8–9, Table 1 · p. 9

A1 Definition of Finite Markov Decision Processes

• A finite MDP is P = (S, A, R, p, γ), with finite state, action, and reward sets, transition and reward distributions conditioned on state-action pairs, and a Markov policy π(a|s).Source: A1 Definition of Finite Markov… · p. 12
• At each step, the policy selects an action in the current state, prompting a transition to the next state and a reward; together these form an alternating state-action-reward sequence.Source: A1 Definition of Finite Markov… · p. 12
• The return accumulates rewards from t + 1, and γ controls delay preference: γ = 0 values immediate reward, while γ = 1 sums future rewards if the sum exists.Source: A1 Definition of Finite Markov… · p. 12
• The action-value qπ(s, a) is expected return given state s and action a, while q*(s, a) equals expected immediate reward plus γ times the optimal next-state value.Source: A1 Definition of Finite Markov… · p. 13
• The finite-horizon setting considers episodes of length T, permits a reward at T + 1, and uses γ = 1, so returns sum rewards through the episode.Source: A1 Definition of Finite Markov… · p. 13
• Monte Carlo estimates qπ by averaging observed returns for a state-action pair; for a changing policy it uses an exponentially weighted mean, called constant-α MC.Source: A1 Definition of Finite Markov… · p. 14
• Temporal-difference methods update Q-values using the Bellman equation, combining an estimated immediate reward with an estimated expected next action-value.Source: A1 Definition of Finite Markov… · p. 14
• Off-policy Q-learning converges with probability 1 to q* when all state-action pairs are visited and updated infinitely often; its learned action-values do not depend on the behavior policy.Source: A1 Definition of Finite Markov… · p. 15

A2.1 State Enriched MDPs

• Ravindran and Barto define an MDP homomorphism through surjections mapping states and admissible actions to a homomorphic image.Source: A2.1 State Enriched MDPs · p. 15
• Delayed-reward states must encode reward information, but immediate-reward states can be made more compact by removing it.The paper introduces homomorphic MDPs to compare such state representations.Source: A2.1 State Enriched MDPs · p. 15
• A state-enriched MDP has additional state information, while retaining the original states, actions, transition probabilities, and reward probabilities.It is defined so that the original MDP is a homomorphic image of the enriched MDP.Source: A2.1 State Enriched MDPs · p. 15
• A homomorphic image preserves optimal Q-values and policies, so the original MDP can be solved by solving that image.An optimal policy in the image can be transformed into an optimal policy in the original by normalizing the number of actions mapped to the same action.Source: A2.1 State Enriched MDPs · p. 15
• State-enriched and original MDPs have the same optimal Q-values and optimal policies.State enrichment is defined by a non-bijective state mapping from the enriched MDP to the original.Source: A2.1 State Enriched MDPs · p. 15
• Every optimal policy in the original MDP corresponds to at least one optimal policy in the state-enriched MDP, and vice versa.Source: A2.1 State Enriched MDPs · p. 16

A2.2 Return-Equivalent Sequence-Markov Decision Processes (SDPs)

• Return-equivalent processes differ only in their non-Markov reward distributions but have the same expected return for each policy at t = 0 or for every episode.This is the equivalence used to compare delayed-reward MDPs with decision processes without delayed rewards.Source: A2.2 Return-Equivalent Sequence-Markov… · p. 16

A2.2.1 Sequence-Markov Decision Processes (SDPs)

• An SDP is a finite decision process with a Markov policy and Markov transitions, while its reward distribution need not be Markov.Source: A2.2.1 Sequence-Markov Decision… · p. 16
• Every Markov decision process is also a sequence-Markov decision process.Source: A2.2.1 Sequence-Markov Decision… · p. 16
• Sequence-equivalent SDPs share transition probabilities and a policy, so they generate state-action sequences with the same probabilities.Sequence generation depends only on the transition probabilities and policy.Source: A2.2.1 Sequence-Markov Decision… · p. 16

• Return-equivalent sequence-MDPs differ only in reward and share each policy’s expected return; MDPs analogously differ only in reward distributions.Source: A2.2.2 Return-Equivalent SDPs · pp. 16–17
• Return-equivalent sequence-MDPs and MDPs have the same optimal policies.Source: A2.2.2 Return-Equivalent SDPs · pp. 16–17
• Strict return-equivalence preserves expected return conditional on any state-action prefix in both sequence-MDPs and MDPs.Source: A2.2.2 Return-Equivalent SDPs · p. 17

A2.3 Reward Redistribution for Strictly Return-Equivalent SDPs

• Reward redistribution constructs strictly return-equivalent SDPs.Source: A2.3 Reward Redistribution for… · p. 17

A2.3.1 Reward Redistribution

• A reward redistribution reallocates the return associated with each state-action sequence across that sequence, defining a new SDP with redistributed rewards and a corresponding return variable.The procedure ensures that the original and redistributed returns are equal, or that the original return equals the policy-conditional expectation of the redistributed return given the sequence.Source: A2.3.1 Reward Redistribution · p. 17
• A redistribution is causal when each redistributed reward’s expectation conditioned on the full trajectory equals its expectation conditioned only on the sequence up to that time.This captures the special case where the return can be deduced from the past sequence.Source: A2.3.1 Reward Redistribution · p. 18
• RUDDER uses causal redistributions that are second-order Markov, so expected redistributed rewards depend only on the two most recent state-action pairs.The defining condition equates conditioning on the history through the current state-action pair with conditioning on the preceding and current state-action pairs.Source: A2.3.1 Reward Redistribution · p. 18

A2.4 Reward Redistribution Constructs Strictly Return-Equivalent SDPs

• Reward redistribution yields a strictly return-equivalent SDP, preserving the return for each state-action sequence.The proof uses equality of returns for each sequence and the resulting equality of expected returns that defines strict return-equivalence.Source: A2.4 Reward Redistribution Constructs… · p. 18
• The original and reward-redistributed SDPs have the same optimal policies.Source: A2.4 Reward Redistribution Constructs… · p. 18

A2.4.1 Special Cases of Strictly Return-Equivalent Decision Processes: Reward Shaping, Look-Ahead Advice, and Look-Back Advice

• Reward shaping, look-ahead advice, and look-back advice can redistribute rewards while producing an MDP strictly return-equivalent to the original.For reward shaping, the additional rewards telescope to the difference between discounted terminal and initial potentials.Source: A2.4.1 Special Cases of Strictly… · p. 18
• Subtracting c = (Φ(s0, a0) − γ^T Φ(sT, aT))/(1 − γ^T) from every potential makes the total added reward zero; for infinite horizons with γ < 1, c = Φ(s0, a0) suffices.Alternatively, strict return equivalence holds when Φ(s0, a0) = 0 and γ^T Φ(sT, aT) = 0; adding new initial and final states can satisfy these assumptions.Source: A2.4.1 Special Cases of Strictly… · pp. 18–19
• Potential-based reward shaping preserves return but generally is not an optimal reward redistribution, and TD-based shaping can remain exponentially slow for delayed rewards.Subtracting a constant from the potential shifts every Q-value by that constant without changing general learning behavior; shaping methods rely on the original reward’s Markov property.Source: A2.4.1 Special Cases of Strictly… · pp. 18–19
• Look-ahead advice depends on future states and actions, making its reward non-causal and unusable directly for choosing the current optimal action; it also does not satisfy the Bellman equation.These advice methods rely on the Markov property of the original reward, unlike an optimal redistribution, which is generally non-Markov and does not comply with the Bellman equation.Source: A2.4.1 Special Cases of Strictly… · p. 19
• Look-back advice introduces a second-order Markov reward, like the optimal reward redistribution.Source: A2.4.1 Special Cases of Strictly… · p. 19

A2.5 Transforming an Immediate Reward MDP to a Delayed Reward MDP

• Reward is moved to sequence end, and augmenting states with accumulated reward makes the delayed-reward process an MDP.The accumulated reward is ρ_t = Σ_{k=0}^{t−1} r_{k+1}.Source: A2.5 Transforming an Immediate Reward… · pp. 19–20
• The construction assumes finite-valued accumulated reward precise enough to distinguish optimal from suboptimal deterministic policies, with episode time available to identify sequence end.For bounded continuous rewards and finite sequence length T, ρ can represent accumulated reward at any desired precision.Source: A2.5 Transforming an Immediate Reward… · p. 19
• The transformed MDP preserves optimal policies and is strictly return-equivalent to the state-enriched intermediate process.The policy in the enriched state is defined to choose actions as the original policy does in the corresponding state.Source: A2.5 Transforming an Immediate Reward… · pp. 19–20

• For episodic delayed-reward MDPs, the final reward realization—or its expectation—can be redistributed to earlier steps; redistributing the expectation reduces estimator variance.Source: A2.6 Transforming an Delayed Reward… · pp. 21–22

A2.6.1 Optimal Reward Redistribution

• With optimal reward redistribution, expected future rewards are zero, so Q-value estimation reduces to estimating the mean immediate reward for each state-action pair.The resulting SDP has no delayed rewards.Source: A2.6 Transforming an Delayed Reward… · pp. 22, 25
• In general, zero expected future reward conflicts with the MDP Markov reward assumption, but a return-equivalent SDP with second-order Markov redistribution can achieve it for a specific policy.For that policy, optimality is equivalent to the expected redistributed reward being the difference between consecutive original Q-values.Source: A2.6 Transforming an Delayed Reward… · p. 23
• An optimal redistribution makes the SDP Q-value equal to the original Q-value minus a state-dependent offset, while preserving the original MDP’s advantage function.The offset depends only on the state, so estimating the expected immediate redistributed reward suffices to estimate the original Q-value up to that offset.Source: A2.6 Transforming an Delayed Reward… · pp. 26–27

A2.7 Novel Learning Algorithms based on Reward Redistributions

• With γ = 1 and a finite horizon or absorbing state, a state-only offset lets Q-values be estimated from expected immediate redistributed rewards, also enabling advantage computation.The passage states that reinforcement-learning methods using action-wise maximization of Q-values or the advantage function can be used.Source: A2.7 Novel Learning Algorithms based… · p. 27

A2.7.1 Q-Value Estimation

• Q-value methods use offset estimates under optimal redistribution, κ-corrected estimates under non-optimal redistribution, or eligibility traces; reward correction preserves sequence returns and optimal policies.The offset estimates can be on-policy Q-value estimates or off-policy immediate-reward estimates.Source: A2.7.1 Q-Value Estimation · pp. 28, 30

A2.7.2 Policy Gradients

• Policy gradients replace q-values with immediate-reward estimates or redistributed-reward samples, and convergence to optimal policies is guaranteed even with the state-dependent offset.Eligibility traces can also be used to form new returns for the policy-gradient update.Source: A2.7.2 Policy Gradients · p. 30

A2.7.3 Q-Learning

• Q-learning and other temporal-difference methods are justified with redistributed rewards when immediate and future rewards are drawn together.Source: A2.7.3 Q-Learning · p. 30

A2.8 Return Decomposition to construct a Reward Redistribution

• Return decomposition predicts sequence return and attributes it to state-action transitions, using the largest Q-value differences to identify contributions for redistribution.Because Q-value differences telescope to the difference in expected returns at the sequence endpoints, the task can be treated as pattern recognition.Source: A2.8 Return Decomposition to construct… · p. 31

A2.8.1 Return Decomposition Idea

• A deterministic return predictor removes sampling variance; contribution analysis can use prediction differences, integrated gradients, or LRP, while later-state information can explain away earlier reward-causing actions.The authors prefer prediction differences because integrated gradients and LRP use later sequence information and introduce non-Markov rewards.Source: A2.8.1 Return Decomposition Idea · pp. 31–32

A2.8.2 Reward Redistribution

• Redistributed rewards have contribution means; an extra terminal reward corrects for stochastic rewards and imperfect predictions, preserving strict return equivalence while moving return-sampling variance to the correction.With a perfect return predictor, the correction can be zero, yielding an optimal redistribution.Source: A2.8.2 Reward Redistribution · pp. 32–33

A2.9.1 Return Decomposition for Binary Reward

• For binary terminal rewards, redistributed reward tracks changes in success probability, rewarding actions that raise it and penalizing actions that lower it.The success probability represents the expected return for a state or state-action pair.Source: A2.9.1 Return Decomposition for Binary… · p. 34

A2.9.2 Optimal Reward Redistribution

• An optimal reward redistribution reduces the MDP to a stochastic contextual bandit problem, assuming conditionally subgaussian noise.Bounded rewards yield bounded, subgaussian noise; a Bernoulli variable is 0.5-subgaussian.Source: A2.9.2 Optimal Reward Redistribution · p. 34

A2.9.3 Relation to ”Backpropagation through a Model´´

• Replacing the model gradient with action contributions in backpropagation through a model yields reward redistribution applied to policy gradients.The passage relates the methods through their respective gradients over action sequences and contributions.Source: A2.9.3 Relation to ”Backpropagation… · p. 35

A3 Bias-Variance Analysis of MDP Q-Value Estimators

• The bias-variance analysis frames Q-value estimation as estimating the expected return from episode data, with estimator error assessed by mean squared error.The analysis defines bias and variance by taking expectations over the episode dataset.Source: A3 Bias-Variance Analysis of MDP… · p. 35

A3.1 Bias-Variance for MC and TD Estimates of the Expected Return

• MC estimates expected return with an arithmetic mean, whereas TD uses an exponentially weighted mean and is biased by its next-state value estimates.The arithmetic-mean estimator’s variance depends on the sample variance; the exponentially weighted estimator also has variance proportional to sample variance.Source: A3.1 Bias-Variance for MC and TD… · pp. 36–37

A3.2 Mean and Variance of an MDP Sample of the Return

• The return-sample variance combines immediate reward variance, transition-and-action variance, and expected future variance; TD variance is smaller than MC variance because it does not propagate future variance.For delayed rewards, TD information propagates backward through estimates, producing large bias over a long period; MC return variance increases with delayed rewards.Source: A3.2 Mean and Variance of an MDP… · pp. 38, 40

A3.3 TD corrects Bias exponentially slowly with Respect to Reward Delay

• TD requires exponentially many updates to correct bias under delayed rewards, with eligibility traces also decaying exponentially with delay.For eligibility traces with λ < 1, reward propagated k steps decays as (γλ)^k.Source: A3.3 TD corrects Bias exponentially… · p. 41
• With α < 1, online updates exhibit exponential decay backward in time; α = 1 would erase previous estimates and prevent averaging across episodes.Source: A3.3 TD corrects Bias exponentially… · p. 42

A3.4 MC affects the Variance of Exponentially Many Estimates with Delayed Reward

• Monte Carlo on-site variance propagates to earlier action-values; the number of affected states grows exponentially for small k, then linearly for large k.The analysis motivates providing rewards as early as possible to reduce the variance associated with late rewards.Source: A3.4 MC affects the Variance of… · pp. 45, 47, 48

A4.1 Artificial Tasks

• The artificial-task appendix adds deterministic task (IV) and policy-gradient task (V) to the three artificial tasks covered in the main paper.Source: A4.1 Artificial Tasks · p. 49

A4.1.1 Task (I): Grid World

• Grid World models a bomb that may reward the agent at episode end for visiting it, while immediate movement rewards can misleadingly favor running away.The 31 × 31 environment varies reward and transition determinism, with delayed-reward probability 0.5.Source: A4.1.1 Task (I): Grid World · p. 49
• Under fixed-policy Grid World evaluation, optimal reward redistribution corrected TD bias exponentially faster and left MC with fewer high-variance action-values than the original MDP.The experiments also found that estimators for the redistributed MDP learned faster; in the original MDP, action-values above a variance threshold increased exponentially with delay.Source: A4.1.1 Task (I): Grid World · p. 49, Figure A3 · p. 50
• For Grid World, RUDDER used optimal reward redistribution with return decomposition, and each method-delay condition was evaluated over 300 seeded runs.The supplied passages describe the setup but do not provide the Grid World results.Source: A4.1.1 Task (I): Grid World · p. 50

A4.1.2 Task (II): The Choice

• In The Choice, RUDDER with reward redistribution learned significantly faster than all other methods (p-values < 10^-8).Only the first action determines the agent’s charged-state type; accumulated reward and a first-action bonus are delivered at episode end.Source: A4.1.2 Task (II): The Choice · pp. 50–51, Table A1 · p. 52

A4.1.3 Task(III): Trace-Back

• RUDDER with reward redistribution solved Trace-Back significantly faster than all compared methods (Wilcoxon p-values < 10^-17).The task rewards a particular early action despite an immediate-reward distraction; Table A2 reports mean learning episodes and standard deviations over 100 trials.Source: A4.1.3 Task(III): Trace-Back · pp. 53–54, Table A2 · p. 55

A4.1.4 Task (IV): Charge-Discharge

• The Charge-Discharge task tests whether learning can distinguish a small immediate reward from a larger delayed reward accumulated by alternating charge and discharge actions.The delayed reward is provided at episode end; the optimal policy accumulates 10 every other time step, while the immediate reward is 1.Source: A4.1.4 Task (IV): Charge-Discharge · p. 57, Figure A5 · p. 57

A4.1.5 Task (V): Solving Trace-Back using policy gradient methods

• On Trace-Back using policy-gradient methods, RUDDER was exponentially faster than PPO, and RUDDER with GAE was slightly better than without GAE.The comparison included RUDDER on top of PPO with and without GAE, and a PPO baseline using GAE.Source: A4.1.5 Task (V): Solving Trace-Back… · p. 57, Figure A6 · p. 58

A4.2 Atari Games

• The Atari implementation considered 52 compatible games and treated a lost life or 108k frames as an episode boundary without resetting the environment.Standard input processing included skipping 3 frames and stacking 4 frames.Source: A4.2 Atari Games · p. 57

A4.2.1 Architecture

• The Atari reward-redistribution model uses a 64-cell LSTM without output or forget gates, receives PPO vision features, actions, and approximate in-game time, and does not send gradients back to PPO.Its output predicts the return realization and includes four additional auxiliary-task outputs.Source: A4.2.1 Architecture · p. 58, Figure A7 · p. 59

A4.2.2 Lessons Replay Buffer

• The lessons replay buffer retains up to 128 high-priority samples, ranked equally by redistribution-model error and return deviation, then sampled by a softmax over loss.Each sample is a sequence of 512 consecutive transitions.Source: A4.2.2 Lessons Replay Buffer · p. 60

A4.2.3 Game Processing, Update Design, and Target Design

• RUDDER redistributes reward online as differences between consecutive LSTM return predictions, while training the model separately on lessons-buffer samples.The model combines terminal, continuous, earlier-prediction, and auxiliary-task losses; it trains on 512-step chunks with truncated backpropagation every 128 steps.Source: A4.2.3 Game Processing, Update Design,… · pp. 60–62

A4.2.4 Exploration

• Safe exploration activates once per sequence for a random duration, and its transitions train the reward redistribution model but not PPO.Two of eight parallel actors use thresholds 0.001 and 0.5, respectively.Source: A4.2.4 Exploration · p. 62

A4.2.5 Results

• In Bowling and Venture, RUDDER redistributes delayed rewards to key events, shortening reward delays and enriching sparse sequences with denser feedback.In Bowling it identifies actions that guide the ball toward the pins; in Venture it rewards entering a treasure room and increasingly rewards approaching the treasure.Source: Figure A9 · p. 65, A4.2.5 Results · p. 65

A5 Discussion and Frequent Questions

• RUDDER’s return decomposition supports unbiased Q-value estimation under optimal decomposition, while correction by learned κ addresses cases where optimality is not assured.The discussion also notes that RUDDER may be less effective without delayed rewards, can struggle with very long sequences, and may produce spurious reward signals; the sign function may simplify learning but change the optimal policy.Source: A5 Discussion and Frequent Questions · pp. 66–67

A6 Additional Related Work

• Reward redistribution differs from reward shaping and look-ahead/look-back advice because it can replace original rewards and is not limited to potential differences.Those approaches retain original rewards, which can leave delayed-reward learning slow; state-only shaping also cannot identify relevant actions without the original reward.Source: A6 Additional Related Work · pp. 68–69

A7 Markov Decision Processes with Undiscounted Rewards

• The discussion focuses on undiscounted-reward MDPs, which are finite-horizon or have absorbing states without reward; finite-horizon problems can be represented by the latter.Discounting reduces delayed-reward bias correction in TD and variance in MC exponentially with delay.Source: A7 Markov Decision Processes with… · p. 70

A7.1 Properties of the Bellman Operator in MDPs with Undiscounted Rewards

• The Bellman operator is defined for state-action functions without requiring them to be Q-values or its reward input to be the actual reward.It maps an action-value function using the transition and reward distribution under policy π.Source: A7.1 Properties of the Bellman… · p. 70

A7.1.1 Monotonically Increasing and Continuous

• The Bellman operator is monotone, non-expansive, and continuous; its vector form is Tπ[q] = g + Pq, with P row-stochastic.The appendix assumes zero long-term average reward for finite-horizon MDPs and absorbing-state MDPs with zero reward.Source: A7.1.1 Monotonically Increasing and… · p. 71, A7.1.5 t-fold Composition of the… · p. 73

A7.1.2 Contraction for Undiscounted Finite Horizon

• For finite horizons, a time-aware norm makes the Bellman operator a contraction; for infinite horizons, a weighted sup-norm contraction holds when all stationary policies are proper and terminal states are absorbing and reward-free.Finite-horizon backward induction computes values from the terminal time, while its policy-specific version is policy evaluation.Source: A7.1.2 Contraction for Undiscounted… · pp. 71–72, A7.1.3 Contraction for Undiscounted… · p. 72

A7.1.4 Fixed Point of Contraction is Continuous wrt Parameters

• A contraction’s unique fixed point varies continuously with parameters under a shared Lipschitz constant, and local compactness permits different constants.The parameters may include the policy, reward distribution, and transition probabilities.Source: A7.1.4 Fixed Point of Contraction is… · pp. 72–73

A7.1.5 t-fold Composition of the Operator

• The appendix states qπ + ḡ1 = g + Pq, with 1 the vector of ones and ḡ the long-term average reward or stationary-distribution expected reward; P is row-stochastic.It assumes ḡ = 0 for finite-horizon MDPs or absorbing-state MDPs with zero reward, because the agent eventually receives no further reward.Source: A7.1.5 t-fold Composition of the… · p. 73

A7.2 Q-value Transformations: Shaping Reward, Baseline, and Normalization

• Subtracting a baseline from the terminal reward shifts Q-values without changing TD errors, while potential-based shaping preserves optimal policies and can normalize intermediate Q-values.Normalization leaves the first and last Q-values unchanged; one described form sets maximal intermediate Q-values to zero and non-optimal values negative.Source: A7.2 Q-value Transformations: Shaping… · pp. 74–75

A7.3 Alternative Definition of State Enrichment

• State enrichment adds deterministic information computable from the current state, action, and reward, while preserving optimal policies and optimal return.Equivalent policies map between the enriched and original processes.Source: A7.3 Alternative Definition of State… · p. 75

A7.4 Variance of the Weighted Sum of a Multinomial Distribution

• The variance of the expected next-state Q-value depends on transition-distribution variance, and estimating a multinomial linear combination requires its component variances and covariances.For multinomial counts, Var[Xi] = n pi and Cov[Xi, Xj] = −n pi pj for i ≠ j.Source: A7.4 Variance of the Weighted Sum of a… · pp. 76–77

A8.1 LSTM Introduction

• LSTM memory cells maintain constant error flow to avoid vanishing gradients, supporting uniform credit assignment to events whose effects may be delayed.The appendix connects this property to LSTM’s success in speech and language tasks.Source: A8.1 LSTM Introduction · pp. 77–78

A8.2 LSTM in a Nutshell

• The usual LSTM memory cell uses forget gates and peepholes, but cited assessments report peepholes can be removed without performance decrease.LSTM memory cells also avoid vanishing gradients and allow uniform credit assignment.Source: A8.2 LSTM in a Nutshell · p. 78

A8.3 Long-Term Dependencies vs. Uniform Credit Assignment

• LSTM memory cells support uniform credit assignment, while sequence-level contribution analysis can measure each input’s change to the predicted final target.The section also describes attribution-specific LSTM variants, including ones with gates fixed or removed.Source: A8.3 Long-Term Dependencies vs.… · p. 79, A9.1 Difference of Consecutive… · p. 86
• With the forget gate near 1, LSTM cells propagate the same error to each sequence input; standard recurrent networks favor recent inputs, potentially trapping learning in local optima.Uniform credit matters when useful information occurs anywhere in the sequence, including at its beginning.Source: A8.3 Long-Term Dependencies vs.… · p. 79

A8.4.1 LSTM for Integrated Gradients

• For Integrated Gradients with LSTM, the forget and output gates are fixed at 1 because later gate changes can make cell dynamics highly nonlinear.The described setup also assumes uniform credit assignment and initializes cell content to zero.Source: A8.4.1 LSTM for Integrated Gradients · pp. 79–80, Figure A11 · p. 80

A8.4.2 LSTM for LRP

• For LRP, external input enters through cell inputs z while gates receive only recurrent input; terminal relevance is distributed across z_t, though used gates may receive no relevance.The passage notes that this can lead to inconsistencies.Source: A8.4.2 LSTM for LRP · pp. 81–82, Figure A12 · p. 82

A8.4.3 LSTM for Nondecreasing Memory Cells

• Nondecreasing LSTM memory cells keep contributions positive and well-defined, avoiding cancellation between positive and negative inputs.The described architecture ensures cell states are positive and nondecreasing.Source: A8.4.3 LSTM for Nondecreasing Memory… · pp. 82–83

A8.4.4 LSTM without Gates

• The simplest LSTM architecture for contribution analysis removes gates to avoid complex dynamics and is described as perfectly distributing relevance across inputs.Its assumptions include positive cell inputs and zero-initialized memory.Source: A8.4.4 LSTM without Gates · p. 83, Figure A14 · p. 85

A9.1 Difference of Consecutive Predictions for Sequences

• For sequences with a final-step target, differences between consecutive prefix predictions represent each time step’s information gain about that target.If the model cannot be ensured to predict at every time step, the section says other contribution-analysis methods are needed.Source: A9.1 Difference of Consecutive… · p. 86
• The information gain from adding z is the squared correlation between target y and prediction error e, measuring information in z about y not contained in x.The theorem expresses z's increase in R2 through its correlation with y after accounting for x.Source: A9.1 Difference of Consecutive… · pp. 88–89

A9.2 Input Zeroing

• Input Zeroing estimates an input’s contribution by setting it to zero, but requires d additional evaluations and misses redundant inputs that Integrated Gradients and LRP detect.Each input component must be zeroed separately.Source: A9.2 Input Zeroing · p. 89

A9.3 Integrated Gradients

• Integrated Gradients decomposes the output difference from a baseline while evaluating the network and its derivative only m times, with m < d [125].The method attributes the difference between F(x) and F(˜x).Source: A9.3 Integrated Gradients · p. 89

A9.4 Layer-Wise Relevance Propagation

• LRP recursively propagates output relevance to input contributions while conserving relevance, and the decomposition also applies to recurrent networks across sequence elements.Relevance is redistributed from each layer to the preceding layer.Source: A9.4 Layer-Wise Relevance Propagation · p. 90

A9.4.1 New Variants of LRP

• New LRP variants define contributions using activations relative to their sample mean or minimum; the preferred minimum-offset definition keeps contributions nonnegative and permits negative-valued activations.The mean-centered definition can produce negative contributions even with positive weights.Source: A9.4.1 New Variants of LRP · p. 91

A9.4.2 LRP for Products

• For a product z = x1x2 with positive inputs, LRP divides relevance between the units; a preferred deep-Taylor alternative scales inputs to [0, 1] and allocates contributions by their distance from the minimum and maximum.As the Taylor reference a approaches zero, contributions are proportional to x1/(x1 + x2) and x2/(x1 + x2).Source: A9.4.2 LRP for Products · pp. 91–92

A10 Reproducibility Checklist

• The reproducibility checklist points to descriptions of methods, data and evaluation procedures, hyperparameters, reported statistics, and computing infrastructure; Atari runs used two CPUs per run and one GPU per four runs and took about 10 days.The listed GPUs include GTX 1080 Ti, TITAN X, and TITAN V.Source: A10 Reproducibility Checklist · p. 94