RUDDER: Return Decomposition for Delayed Rewards
  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({\lambda}), 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}.
