RUDDER: Return Decomposition for Delayed Rewards

Jose A. Arjona-Medina; Michael Gillhofer; Michael Widrich; Thomas Unterthiner; Johannes Brandstetter; Sepp Hochreiter

Source-linked AI summary

RUDDER: Return Decomposition for Delayed Rewards

Jose A. Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brandstetter, Sepp Hochreiter

arXiv:1806.07857v3Jun 20, 2018cs.LGcs.AImath.OCstat.ML

TL;DR

Delayed rewards create credit-assignment difficulties and exacerbate TD bias and MC variance. RUDDER uses return decomposition to learn reward redistributions that preserve optimal policies while driving expected future rewards toward zero. It significantly outperforms comparison methods on artificial delayed-reward tasks and improves PPO scores on Atari, especially for long delays.

Problem
Delayed rewards make long-term credit assignment difficult and intensify bias in TD learning and variance in MC learning.
Method
RUDDER combines return-equivalent reward redistribution with LSTM-based return decomposition to assign sequence returns to contributing state-action events.
Results
RUDDER significantly outperforms TD(λ), MC, MCTS, and reward shaping on artificial delayed-reward tasks and improves a PPO baseline on Atari games, especially with long delays.
Takeaways & Limitations
Driving expected future rewards toward zero simplifies Q-value estimation to computing mean immediate rewards while retaining optimal policies.
Takeaways & Limitations
RUDDER may be ineffective for nondelayed rewards or very long sequences, and reward redistribution may introduce spurious reward signals.

Abstract

from arXiv · show

We propose RUDDER, a novel reinforcement learning approach for delayed rewards in finite Markov decision processes (MDPs). In MDPs the Q-values are equal to the expected immediate reward plus the expected future rewards. The latter are related to bias problems in temporal difference (TD) learning and to high variance problems in Monte Carlo (MC) learning. Both problems are even more severe when rewards are delayed. RUDDER aims at making the expected future rewards zero, which simplifies Q-value estimation to computing the mean of the immediate reward. We propose the following two new concepts to push the expected future rewards toward zero. (i) Reward redistribution that leads to return-equivalent decision processes with the same optimal policies and, when optimal, zero expected future rewards. (ii) Return decomposition via contribution analysis which transforms the reinforcement learning task into a regression task at which deep learning excels. On artificial tasks with delayed rewards, RUDDER is significantly faster than MC and exponentially faster than Monte Carlo Tree Search (MCTS), TD(λ), and reward shaping approaches. At Atari games, RUDDER on top of a Proximal Policy Optimization (PPO) baseline improves the scores, which is most prominent at games with delayed rewards. Source code is available at \url{https://github.com/ml-jku/rudder} and demonstration videos at \url{https://goo.gl/EQerZV}.

1 Introduction

RUDDER addresses delayed-reward credit assignment by redistributing rewards so expected future rewards approach zero. It combines return-equivalent reward redistribution with return decomposition to improve learning under delayed rewards.

Motivation: Delayed rewards make credit assignment difficult and intensify bias in TD learning and variance in MC learning.For TD, correcting delayed-reward bias can require exponentially many updates as delay increases.
Core idea: RUDDER targets zero expected future rewards, reducing Q-value estimation to computing the mean immediate reward.Its reward redistribution preserves the same optimal policies when it produces a return-equivalent decision process.
Core idea: Return decomposition uses contribution analysis to redistribute a sequence return across its contributing state-action events.The approach is motivated by recognizing reward-relevant patterns in sequences.
Related work: Unlike fixed reward-shaping methods, RUDDER gradually changes reward redistribution during learning.The cited related methods generally retain the original reward and may remain exponentially slow.

2 Reward Redistribution and Novel Learning Algorithms

This section formalizes reward redistribution through return-equivalent sequence-Markov decision processes. An optimal redistribution eliminates expected future rewards, simplifying value estimation while preserving optimal policies.

Definitions: A finite MDP specifies states, actions, rewards, transition-reward distributions, and a discount factor; an SDP relaxes the Markov requirement on rewards.Return-equivalent SDPs differ in reward distribution but preserve expected returns and therefore optimal policies.
Reward redistribution: Reward redistribution changes sequence-associated returns while preserving strict return equivalence between the original and redistributed processes.Second-order Markov redistribution depends only on the preceding and current state-action pairs.
Optimal redistribution: An optimal redistribution satisfies κ(T −t −1, t) = 0, making the expected future reward after each state-action pair zero.Under this condition, Q-value estimation reduces to estimating expected immediate rewards.
Optimal redistribution: For an optimal redistribution, each redistributed reward is tied to the difference between consecutive Q-values of the original delayed-reward process.This relation ensures no state-action pair changes the expectation of a future reward.
Learning algorithms: The redistributed SDP and original MDP have the same advantage function, while an offset depending only on the current state supports Q-value estimation.Non-optimal redistributions still preserve optimal policies, but optimal ones can substantially accelerate learning.
Learning algorithms: RUDDER-based variants apply redistributed rewards to Q-value estimation, policy gradients, and Q-learning, including extensions to PPO.The state-dependent offset reduces variance similarly to baseline normalization in policy-gradient methods.

3 Constructing Reward Redistributions by Return Decomposition

RUDDER constructs reward redistributions by decomposing sequence returns into contributions learned from patterns. LSTM-based prediction supports this decomposition, while the method has stated limits for nondelayed rewards, long sequences, and spurious signals.

Constructing redistributions: Optimal redistributions correspond to expected differences between consecutive Q-values, so identifying large Q-value differences helps construct them.Redistributions farther from these differences have larger expected future-reward deviations.
Return decomposition: Return decomposition trains a function g to predict a sequence’s expected return and distributes that prediction through contribution terms.The contribution terms determine the expected redistributed reward assigned to each state-action transition.
Return decomposition: The explaining-away problem occurs when later states used for return prediction obscure earlier reward-causing actions.A difference function between consecutive state-action pairs is introduced to avoid this problem.
Return decomposition: A perfect return predictor produces an optimal reward redistribution, while small prediction errors produce redistributions close to optimal.The redistributed rewards are based on predicted contributions, with a correction term preserving return equivalence.
RUDDER implementation: RUDDER uses an LSTM for return decomposition and organizes learning around safe exploration, replayed lessons, and sequence-based training.Human expert episodes can alternatively fill the lessons replay buffer and highlight key actions.
Limitations: RUDDER may be ineffective for nondelayed rewards, very long sequences, or settings where redistribution introduces spurious reward signals.The authors identify extra LSTM learning time and long-sequence difficulties as practical limitations.

4 Experiments

RUDDER is evaluated on artificial delayed-reward tasks and Atari games, where it is compared with established learning methods and a PPO baseline. Across these experiments, RUDDER learns faster on artificial tasks and improves PPO performance, especially for delayed rewards.

Artificial Tasks: RUDDER is compared with MC, TD(λ), MCTS, SARSA(λ), and potential-based reward shaping on three artificial delayed-reward tasks.The tasks target vanishing information, high variance, and slow reward propagation.
Atari Games: On Atari, RUDDER is evaluated on 52 games on top of a PPO baseline using finite-horizon or absorbing-state MDPs with γ = 1.Training uses 200M game frames, every fourth frame, and episodes ending after a lost life or 108K frames.
Artificial Tasks: RUDDER significantly outperforms all other methods across the artificial tasks.Figure 1 reports median learning time over 100 trials, with shadow bands showing the 40% and 60% quantiles.
Artificial Tasks: For all delays, RUDDER solves The Choice significantly faster than all other methods, with p-values < 10^-8.Its speed-up versus MC suggests exponential growth with delay, and it is exponentially faster than Q(λ) as delay increases.
Atari Games: RUDDER learns faster on average in 32 games versus 20 for the baseline and has higher last-10-game scores in 29 games versus 23.The majority of games show improved scores, with the comparison focused on Bowling, Solaris, Venture, and Seaquest for delayed rewards.
Atari Games: In Bowling, RUDDER redistributes delayed episode-end rewards to key actions that steer the ball toward hitting all pins.The figure shows the first 120 of 200 episode frames.

A1 Definition of Finite Markov Decision Processes

This section defines finite MDPs, their value functions, finite-horizon undiscounted returns, and the MC and TD approaches used to estimate Q-values. It also states the standard Bellman-based representations and learning objectives.

MDP Definitions: A finite MDP is a 5-tuple P = (S, A, R, p, γ) containing finite states, actions, rewards, transition-reward distributions, and a discount factor.The transition-reward distribution is conditioned on state-action pairs.
Finite Horizon: The discount factor γ controls the relative weighting of immediate and delayed rewards; γ = 1 yields the expected sum of future rewards when it exists.The appendix considers finite horizons with no discounting.
Value Functions: The action-value qπ(s, a) is the expected return after starting at state s, taking action a, and then following policy π.The optimal action value satisfies q∗(s, a) = E[Rt+1 + γv∗(St+1) | St = s, At = a].
Finite Horizon: For finite-horizon undiscounted episodes, the return Gt is the sum of rewards from time t through the terminal time.Episodes may receive RT+1 at the end of a horizon T.
Learning: MC estimates qπ(s, a) by averaging observed returns for each state-action pair, while TD updates estimates using the Bellman equation.TD estimates the immediate reward and expected next-state action value, then applies a learning update.
Learning: Q-learning approximates q∗ independently of the followed policy, provided all state-action pairs are visited and updated infinitely often.The cited result states convergence with probability 1 to the optimal q∗ under that visitation condition.

A2.1 State Enriched MDPs

State enrichment and homomorphic mappings allow MDP representations to change while preserving optimal Q-values and policies. Consequently, solving a suitable homomorphic image can solve the original MDP.

Motivation: Homomorphic MDPs are introduced to compare delayed-reward MDPs with more compact immediate-reward representations.Delayed-reward states may encode reward memory that can be removed in an immediate-reward representation.
Homomorphic Images: A homomorphic image preserves optimal Q-values and allows an optimal policy in the image to be transformed into an optimal policy in the original MDP.The policy transformation normalizes actions mapped to the same image action.
State Enrichment: State enrichment does not change optimal Q-values or optimal policies.The proposition follows because the original MDP is a homomorphic image of the state-enriched MDP.
State Enrichment: Each optimal policy of the original MDP corresponds to at least one optimal policy of the state-enriched MDP, and enriched policies can be transformed back.This establishes policy correspondence in both directions, subject to the stated transformation.

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

Return-equivalent sequence-Markov decision processes may differ in their non-Markov reward distributions while preserving each policy’s expected episode return. This provides the basis for comparing delayed and non-delayed reward processes.

Return Equivalence: The paper compares delayed-reward MDPs with decision processes without delayed rewards.The latter need not be Markov in their rewards.
Return Equivalence: Two processes are return-equivalent when every policy has the same expected return at t = 0, or the same expected return for every episode.The processes differ only in their non-Markov reward distributions.

A2.2.1 Sequence-Markov Decision Processes (SDPs)

Sequence-Markov decision processes retain Markov policies and transitions while allowing reward distributions to depend on the full sequence. Ordinary Markov decision processes are therefore a special case.

An SDP has a finite decision process with a Markov policy, Markov transition probabilities, and a reward distribution that need not be Markov.
An MDP is an SDP because it has Markov transition probabilities and Markov policies.

A2.2.2 Return-Equivalent SDPs

Return-equivalent decision processes may differ in reward distributions while preserving policy returns and optimal policies. Strict return-equivalence additionally preserves expected returns for every episode and state-action subsequence.

Return-equivalent SDPs differ only in reward and have the same expected return for every policy.
Strict return-equivalence can be generalized through strictly monotonic transformations because they preserve the ordering of returns.
Return-equivalent SDPs have the same optimal policies because every policy retains the same expected return at time t = 0.
Strictly return-equivalent SDPs have the same expected return for each state-action subsequence.
For MDPs, return-equivalence means differing only in reward distributions while preserving each policy’s expected return.
Strictly return-equivalent MDPs are return-equivalent, and return-equivalent MDPs have the same optimal policies.

A2.3 Reward Redistribution for Strictly Return-Equivalent SDPs

Reward redistribution can construct strictly return-equivalent sequence-Markov decision processes, preserving the decision process’s return structure.

Strictly return-equivalent SDPs can be constructed by redistributing rewards along state-action sequences.

A2.3.1 Reward Redistribution

A reward redistribution reallocates sequence-associated returns across time while preserving returns, and may be causal or second-order Markov under additional conditional-expectation constraints.

A reward redistribution redistributes the realization of a sequence-associated return across the sequence and defines a new cumulative return from the redistributed rewards.
The redistribution preserves the original return exactly for each sequence or preserves its conditional expected return along the sequence.
A redistribution is causal when the conditional expectation of each redistributed reward depends only on the sequence through the current state-action pair.
A causal redistribution is second-order Markov when its conditional expected reward depends only on (s_t−1, a_t−1, s_t, a_t).

A2.4 Reward Redistribution Constructs Strictly Return-Equivalent SDPs

Reward redistribution constructs strictly return-equivalent sequence-Markov decision processes, preserving expected returns for every policy and therefore preserving optimal policies.

Reward redistribution preserves the return for each state-action sequence.The redistributed and original returns are equal for every sequence, establishing strict return equivalence.
Strictly return-equivalent decision processes have the same optimal policies.The result follows from strict return equivalence and the stated propositions connecting equivalence to policy optimality.

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 are special cases of reward redistribution, but they differ in return preservation, causality, and temporal structure.

Reward shaping: Reward shaping is a strictly return-equivalent reward redistribution under appropriate potential-function assumptions.The assumptions are γ^TΦ(s_T,a_T)=0 and Φ(s_0,a_0)=0; for infinite horizons with γ<1, only the initial-potential condition is needed.
Reward shaping: Reward shaping can remain exponentially slow for delayed rewards because TD-based methods keep the original reward.It generally does not produce the optimal reward redistribution.
Look-ahead advice: Look-ahead advice produces a non-causal reward that depends on future states and future actions, so it cannot directly select the current action.Its expected redistributed reward depends especially on the future action a_{t+1}.
Look-back advice: Look-back advice introduces a second-order Markov reward resembling the optimal reward redistribution.

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

An immediate-reward MDP can be transformed into a delayed-reward MDP by enriching states with accumulated rewards and redistributing rewards while preserving policy-relevant values.

Transformation: The transformation creates a state-enriched delayed-reward MDP in which the reward is given at sequence end.State enrichment ensures that the delayed-reward process remains an MDP.
State enrichment: The enriched state records the accumulated reward, ρ_t = Σ_{k=0}^{t−1} r_{k+1}.The accumulated reward is assumed sufficiently precise to distinguish optimal deterministic policies from sub-optimal deterministic policies.
Policy preservation: The intermediate state-enriched MDP preserves the optimal Q-values and optimal policies of the original MDP.This preservation is followed by redistribution of the original reward in the construction of the delayed-reward process.
Redistributed dynamics: For t < T, the transformed process uses zero redistributed reward and updates the accumulated reward as ρ′ = r + ρ.The transformed transition distribution is computed from the original reward, accumulated reward, and next state.
Value equivalence: The transformed action-value function satisfies the Bellman equation, making it the action-value function for the corresponding policy.

A2.6 Transforming an Delayed Reward MDP to an Immediate Reward SDP

The paper transforms delayed-reward MDPs into return-equivalent decision processes by redistributing rewards so expected future rewards approach zero. This simplifies Q-value estimation while preserving optimal policies, and addresses the bias and variance amplification caused by delayed rewards.

Reward redistribution: Final episodic rewards or their expectations are redistributed to earlier time steps to construct an immediate-reward SDP with the same expected returns and optimal policies.The construction can redistribute the realized final reward or its expectation across preceding state-action pairs.
Optimal redistribution: Zero expected future rewards reduce Q-value estimation to estimating the average immediate reward for each state-action pair.When κ(T −t −1, t) = 0, qπ(st, at) = r(st, at), so learning reduces to computing the mean immediate reward.
Policy preservation: An optimal redistribution preserves the advantage function and permits Q-value estimation with an offset depending only on the state.The paper states that the redistributed process and the original MDP have the same advantage function.
Return decomposition: Return decomposition uses a function g to predict sequence return and contribution analysis to distribute that prediction across state-action pairs.A perfect prediction can set later corrective rewards to zero, while an imperfect predictor leaves correction and sampling variance in later rewards.
Delayed-reward effects: Monte Carlo methods propagate future-reward variance backward, and the number of affected estimates can initially grow exponentially with delay.The affected-state count later becomes linear after transition overlap saturates the preceding state layer.
Delayed-reward effects: Delayed rewards make TD updates exponentially small, while eligibility traces propagate rewards backward with exponential decay in the number of delay steps.The decay is stronger for Watkins’ Q(λ), and online updates also decay exponentially when the learning rate is below one.