0 \leq t \leq T$.
For the redistributed rewards $R_{t+1}$, we ensure 
$\EXP \left[ R_{t+1} \mid s_{t-1},a_{t-1},s_t,a_t \right]  =  h_t$.
The reward $\tilde{R}_{T+1}$ of $\tilde{\cP}$
is probabilistic and 
the function $g$ might not be perfect,
therefore neither $g(\Delta_{0:T}) = \tilde{r}_{T+1}$ for the return
realization $\tilde{r}_{T+1}$ nor
$g(\Delta_{0:T}) = \tilde{r}(s_T,a_T)$ for the expected return
holds.
Therefore, we need to introduce the compensation
$\tilde{r}_{T+1} \ - \ 
  \sum_{\tau=0}^T h(\Delta(s_{\tau-1},a_{\tau-1},s_{\tau},a_{\tau}))$
as an extra reward $R_{T+2}$ at time $T+2$
to ensure strictly return-equivalent SDPs.
If $g$ was perfect, then it would predict the expected return which
could be redistributed.
The new redistributed rewards
$R_{t+1}$ are based on the return decomposition, since they 
must have the contributions $h_t$ as mean:\newline
$\EXP \left[ R_1 \mid s_0,a_0 \right]   =  h_0$, 
$\EXP \left[ R_{t+1} \mid s_{t-1},a_{t-1},s_t,a_t \right] 
   =  h_t, 0 < t \leq T$ , 
$R_{T+2}  = \tilde{R}_{T+1}  -  \sum_{t=0}^T h_t$,
where the realization $\tilde{r}_{T+1}$ is replaced by its
random variable $\tilde{R}_{T+1}$.
If the prediction of $g$ is perfect, then we can
redistribute the expected return via the prediction.
Theorem~\ref{th:zeroExp} holds also for
the correction $R_{T+2}$ (see Theorem~\ref{th:AzeroExpCorr} in the appendix). 
A $g$ with zero prediction errors 
results in an optimal reward redistribution.
Small prediction errors lead to reward redistributions 
close to an optimal one.

\paragraph{RUDDER: Return Decomposition using LSTM.}
RUDDER uses a Long Short-Term Memory (LSTM) network for 
return decomposition and the resulting reward redistribution.
RUDDER consists of three phases. 
{\bf (I) Safe exploration.}
Exploration sequences should generate LSTM training samples 
with delayed rewards by avoiding 
low $Q$-values during a particular time interval. 
Low $Q$-values hint at states where the agent gets stuck. 
Parameters comprise starting time, length, and $Q$-value threshold.
{\bf (II) Lessons replay buffer for training the LSTM.}
If RUDDER's safe exploration discovers 
an episode with unseen delayed rewards,
it is secured in a lessons replay buffer \cite{Lin:93}. 
Unexpected rewards are indicated by a large prediction error of the LSTM.
For LSTM training, episodes with larger errors are sampled more often 
from the buffer, similar to prioritized
experience replay \cite{Schaul:15}.
{\bf (III) LSTM and return decomposition.}
An LSTM learns to predict sequence-wide return at 
every time step and, thereafter, 
return decomposition uses differences of return predictions
(contribution analysis method (A)) to construct a reward redistribution. 
For more details see Section~\ref{sec:ALSTMadjust} in the appendix.


\paragraph{Feedforward Neural Networks (FFNs) vs.\ LSTMs.}
In contrast to LSTMs, 
FNNs are not suited for processing sequences. 
Nevertheless, FNNs can learn a action-value function, which 
enables contribution analysis by 
differences of predictions. 
However, this leads to serious problems by spurious contributions
that hinder learning.
For example, any contributions would be incorrect
if the true expectation of the return did not change. 
Therefore, prediction errors might falsely cause contributions 
leading to spurious rewards. 
FNNs are prone to such prediction errors since they
have to predict the expected return
again and again from each different state-action pair and 
cannot use stored information.
In contrast, the LSTM is less prone to produce spurious 
rewards:
(i) The LSTM will only learn to store information 
if a state-action pair has a strong evidence 
for a change in the expected return. 
If information is stored, then internal states and,
therefore, also the predictions change, otherwise the predictions
stay unchanged.
Hence, storing events receives a contribution and
a corresponding reward, while by default nothing is stored and 
no contribution is given.
(ii) The LSTM tends to have smaller prediction errors since it can 
reuse past information for predicting the expected return. 
For example, key events can be stored.
(iii) Prediction errors of LSTMs are much more likely to cancel 
via prediction differences than those of FNNs. 
Since consecutive predictions of LSTMs rely on the same
internal states, they usually have highly correlated errors.

\paragraph{Human Expert Episodes.} They are an alternative to 
exploration and can 
serve to fill the lessons replay buffer.
Learning can be sped up considerably when LSTM identifies
human key actions.
Return decomposition will reward human key actions even for episodes
with low return since other actions that thwart high
returns receive negative reward.
Using human demonstrations in reinforcement learning
led to a huge improvement on some Atari
games like Montezuma's Revenge \cite{Pohlen:18,Aytar:18}.


\paragraph{Limitations.}
In all of the experiments reported in this manuscript, we show that RUDDER significantly outperforms other methods for delayed reward problems. However, RUDDER might not be effective when the reward is not delayed since LSTM learning takes extra time and has problems with very long sequences. Furthermore, reward redistribution may introduce disturbing spurious reward signals.

\section{Experiments}
\label{sec:Mexperiments}
RUDDER is evaluated on three artificial tasks with delayed rewards.
These tasks are designed to show problems of TD, MC, 
and potential-based reward shaping.
RUDDER overcomes these problems.
Next, we demonstrate that RUDDER also works for more complex tasks
with delayed rewards.
Therefore, we compare RUDDER with 
a Proximal Policy Optimization (PPO) baseline
on 52 Atari games. 
All experiments use finite time horizon or 
absorbing states MDPs with $\gamma=1$ and reward at episode end.
For more information see Section~\ref{sec:Aexp} in the appendix.

{\bf Artificial Tasks (I)--(III).} 
Task (I) shows that TD methods have problems with vanishing information 
for delayed rewards.
Goal is to learn that a delayed reward is
larger than a distracting immediate reward.
Therefore, the correct expected future reward must be  
assigned to many state-action pairs. 
Task (II) is a variation of the introductory pocket watch example
with delayed rewards.
It shows that MC methods have problems with the 
high variance of future unrelated rewards.
The expected future reward that is caused by the first action
has to be estimated.
Large future rewards that are not associated 
with the first action impede MC estimations. 
Task (III) shows that potential-based reward shaping methods have
problems with delayed rewards.
For this task, only the first two actions are relevant, to which
the delayed reward has to be propagated back.

The tasks have different delays, 
are tabular ($Q$-table),
and use an $\epsilon$-greedy policy with $\epsilon = 0.2$.
We compare RUDDER, MC, and TD($\lambda$) 
on all tasks, and Monte Carlo Tree Search (MCTS) on task (I).
Additionally, on task (III),
SARSA($\lambda$) and reward shaping are compared.
We use $\lambda=0.9$ as suggested \cite{Sutton:18book}.
Reward shaping methods are the original method, look-forward advice,
and look-back advice with three different potential functions.
RUDDER uses an LSTM without output and forget gates,
no lessons buffer, and no safe exploration. 
For all tasks contribution analysis is performed 
with difference of return predictions.  
A $Q$-table is learned 
by an exponential moving average of 
the redistributed reward (RUDDER's $Q$-value estimation) 
or by $Q$-learning. 
Performance is measured by 
the learning time to achieve 90\% of the maximal expected return.
A Wilcoxon signed-rank test determines 
the significance of performance differences between R