RUDDER: Return Decomposition for Delayed Rewards

By José Antonio Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Sepp Hochreiter. 2018

277 citations recorded by the source corpus.

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{this https URL} and demonstration videos at \url{this https URL}.

Subfields: Artificial Intelligence, Hardware and Architecture, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Reinforcement Learning

Citations in the corpus

Decision Transformer: Reinforcement Learning via Sequence Modeling (2021, neutral): “Similar to our long-term setting, some works have specifically shown such state-associative architectures can perform better in delayed reward settings (Arjona-Medina et al., 2018; Hung et al., 2019; Liu et al., 2019; Raposo et al., 2021).”
SNAS: Stochastic Neural Architecture Search (2018, background): “Details are given in Appendix E. Arjona-Medina et al. (2018) prove that decomposing delayed reward to each step with gradients could resolve the delayed bias since no delayed reward exists.”
Ray Interference: a Source of Plateaus in Deep Reinforcement Learning (2019, background): “…oﬀ-policy learning that dilutes the coupled data distribution with exploratory experience (or experience from other agents), rebalancing the data distribution with a suitable form of prioritized replay [35] or ﬁtness sharing [33], or by reward shaping that makes the learning signal less sparse [2].”
A survey and critique of multiagent deep reinforcement learning (2018, background): “6] uses hand-crafted intermediate rewards to accelerate the learning and FTW [66] lets the agents learn their internal rewards by a hierarchical two-tier optimization. In single agent domains, RUDDER [115] has been recently proposed for such delayed sparse reward problems. RUDDER generates a new MDP”
Training Agents using Upside-Down Reinforcement Learning (2019, neutral): “RUDDER [Arjona-Medina et al., 2019] uses gradient-based SL in recurrent networks to perform contribution analysis in order to map rewards to state-action pairs.”
Reinforcement Learning Upside Down: Don't Predict Rewards - Just Map Them to Actions (2019, methodology): “What is the difference to RUDDER [3] which also uses gradient-based SL in RNNs to perform contribution analysis, mapping rewards to state-action pairs? Unlike R L , RUDDER does not use desired rewards as command input for an SL model.”
Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewards (2019, methodology): “Learned models have also been applied to perform reward shaping to overcome challenges related to delayed rewards (Arjona-Medina et al., 2019).”
DQN-TAMER: Human-in-the-Loop Reinforcement Learning with Intractable Feedback (2018, background): “The estimated values of actions in given states are modiﬁed exponentially slowly over the number of remaining intervals until the future reward is received [4].”
Challenges of real-world reinforcement learning: definitions, benchmarks and analysis (2021, methodology): “Arjona-Medina et al. (2018) introduce the RUDDER algorithm, which uses a backwards-view of a task to generate a return-equivalent MDP where the delayed rewards are re-distributed more evenly throughout time.”
Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update (2018, methodology): “RUDDER [1] introduces an LSTM network with contribution analysis for an efficient return decomposition.”
Physically Embedded Planning Problems: New Challenges for Reinforcement Learning (2020, background): “These problems are notoriously diﬃcult for RL algorithms because of the wide variety of situations that can be encountered, the diﬃculty of ﬁnding successful plays by chance, and the long delay between actions and rewards (Arjona-Medina et al., 2019; Hung et al., 2019; Sutton and Barto, 2018).”
Differentiable Architecture Search with Ensemble Gumbel-Softmax (2019, background): “As a result, the reward in NAS will only be observable until the architecture is chosen and the network is tested for accuracy, which is always subject to delayed rewards in temporal-difference learning (Arjona-Medina et al., 2018).”
Agent57: Outperforming the Atari Human Benchmark (2020, background): “…two types: ensuring that gradients correctly assign credit (Ke et al., 2017; Weber et al., 2019; Fortunato et al., 2019) and using values or targets to ensure correct credit is assigned (Arjona-Medina et al., 2019; Hung et al., 2019; Liu et al., 2019; Harutyunyan et al., 2019; Ferret et al., 2020).”
Self-Attentional Credit Assignment for Transfer in Reinforcement Learning (2019, unknown): “RUDDER [Arjona-Medina et al., 2019] is an online method for credit assignment based on return decomposition.”
Sequence Modeling of Temporal Credit Assignment for Episodic Reinforcement Learning (2019, background): “As one most related work, RUDDER [3] could be viewed as a special case of our work in which consecutive time-steps were used.”