RUDDER: Return Decomposition for Delayed Rewards

Abstract

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}.

arXiv comment9 Pages plus appendix. For videos https://goo.gl/EQerZV

References in corpus (20)

• Deep Learning in Neural Networks: An Overview
• Sequence to Sequence Learning with Neural Networks
• LSTM: A Search Space Odyssey
• Playing Atari with Deep Reinforcement Learning
• Trust Region Policy Optimization
• Axiomatic Attribution for Deep Networks
• Methods for Interpreting and Understanding Deep Neural Networks
• Recurrent Neural Network Regularization
• Prioritized Experience Replay
• Dueling Network Architectures for Deep Reinforcement Learning
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Explaining NonLinear Classification Decisions with Deep Taylor Decomposition
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• BEGAN: Boundary Equilibrium Generative Adversarial Networks
• Noisy Networks for Exploration
• Learning and Transfer of Modulated Locomotor Controllers
• Learning Robust Rewards with Adversarial Inverse Reinforcement Learning
• The Uncertainty Bellman Equation and Exploration
• Recall Traces: Backtracking Models for Efficient Reinforcement Learning
• Forward-Backward Reinforcement Learning

Cited by in corpus (26)

• Explaining Deep Neural Networks and Beyond: A Review of Methods and Applications
• A Survey and Critique of Multiagent Deep Reinforcement Learning
• SNAS: Stochastic Neural Architecture Search
• Agent57: Outperforming the Atari Human Benchmark
• An empirical investigation of the challenges of real-world reinforcement learning
• DQN-TAMER: Human-in-the-Loop Reinforcement Learning with Intractable Feedback
• Off-Policy Evaluation via Off-Policy Classification
• Sample-Efficient Deep Reinforcement Learning via Episodic Backward Update
• Training Agents using Upside-Down Reinforcement Learning
• Self-Attentional Credit Assignment for Transfer in Reinforcement Learning
• Feature construction using explanations of individual predictions
• Reinforcement Learning Upside Down: Don't Predict Rewards -- Just Map Them to Actions
• Towards Fairness in Personalized Ads Using Impression Variance Aware Reinforcement Learning
• Counterfactual Credit Assignment in Model-Free Reinforcement Learning
• Learning Long-Term Reward Redistribution via Randomized Return Decomposition
• Learning Guidance Rewards with Trajectory-space Smoothing
• Adversarial Intrinsic Motivation for Reinforcement Learning
• Multi-Agent Reinforcement Learning for Long-Term Network Resource Allocation through Auction: a V2X Application
• The Actor-Advisor: Policy Gradient With Off-Policy Advice
• Economic Battery Storage Dispatch with Deep Reinforcement Learning from Rule-Based Demonstrations
• Beyond Exponentially Discounted Sum: Automatic Learning of Return Function
• Search in Imperfect Information Games
• MDP Playground: An Analysis and Debug Testbed for Reinforcement Learning
• Delayed Rewards Calibration via Reward Empirical Sufficiency
• Zero-shot Policy Learning with Spatial Temporal RewardDecomposition on Contingency-aware Observation
• Towards Practical Credit Assignment for Deep Reinforcement Learning