# RUDDER: Return Decomposition for Delayed Rewards

arXiv: https://arxiv.org/abs/1806.07857 · HTML: https://mlsanity.com/paper/1806.07857/

## Key facts

- Cited by 173 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2018.

## Built on by (most cited first, 30 of 173)

- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Guided Motion Diffusion for Controllable Human Motion Synthesis](https://mlsanity.com/paper/2305.12577/) (2023)
- [DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search](https://mlsanity.com/paper/2408.08152/) (2024)
- [Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPs](https://mlsanity.com/paper/2110.05038/) (2021)
- [AgenTracer: Who Is Inducing Failure in the LLM Agentic Systems?](https://mlsanity.com/paper/2509.03312/) (2025)
- [Preference Transformer: Modeling Human Preferences using Transformers for RL](https://mlsanity.com/paper/2303.00957/) (2023)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment](https://mlsanity.com/paper/2307.03864/) (2023)
- [Retrieval-Augmented Reinforcement Learning](https://mlsanity.com/paper/2202.08417/) (2022)
- [DQN-TAMER: Human-in-the-Loop Reinforcement Learning with Intractable Feedback](https://mlsanity.com/paper/1810.11748/) (2018)
- [LLMs are Greedy Agents: Effects of RL Fine-tuning on Decision-Making Abilities](https://mlsanity.com/paper/2504.16078/) (2025)
- [Adversarial Intrinsic Motivation for Reinforcement Learning](https://mlsanity.com/paper/2105.13345/) (2021)
- [Mastering Memory Tasks with World Models](https://mlsanity.com/paper/2403.04253/) (2024)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [SEED: Self-Evolving On-Policy Distillation for Agentic Reinforcement Learning](https://mlsanity.com/paper/2607.14777/) (2026)
- [Mirror Learning: A Unifying Framework of Policy Optimisation](https://mlsanity.com/paper/2201.02373/) (2022)
- [Learning to Modulate pre-trained Models in RL](https://mlsanity.com/paper/2306.14884/) (2023)
- [Synthetic Returns for Long-Term Credit Assignment](https://mlsanity.com/paper/2102.12425/) (2021)
- [A Dataset Perspective on Offline Reinforcement Learning](https://mlsanity.com/paper/2111.04714/) (2021)
- [Off-Policy Reinforcement Learning with Delayed Rewards](https://mlsanity.com/paper/2106.11854/) (2021)
- [Learning Energy Decompositions for Partial Inference of GFlowNets](https://mlsanity.com/paper/2310.03301/) (2023)
- [TIPS: Turn-Level Information-Potential Reward Shaping for Search-Augmented LLMs](https://mlsanity.com/paper/2603.22293/) (2026)
- [Retrieval-Augmented Decision Transformer: External Memory for In-context RL](https://mlsanity.com/paper/2410.07071/) (2024)
- [An Information-Theoretic Perspective on Credit Assignment in Reinforcement Learning](https://mlsanity.com/paper/2103.06224/) (2021)
- [Hypernetworks for Zero-shot Transfer in Reinforcement Learning](https://mlsanity.com/paper/2211.15457/) (2022)
- [Interpretable Reward Redistribution in Reinforcement Learning: A Causal Approach](https://mlsanity.com/paper/2305.18427/) (2023)
- [A Survey on Deep Reinforcement Learning for Audio-Based Applications](https://mlsanity.com/paper/2101.00240/) (2021)
- [Semantic HELM: A Human-Readable Memory for Reinforcement Learning](https://mlsanity.com/paper/2306.09312/) (2023)
- [SymbolicAI: A framework for logic-based approaches combining generative models and solvers](https://mlsanity.com/paper/2402.00854/) (2024)
- [TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents](https://mlsanity.com/paper/2607.13988/) (2026)

## Abstract (arXiv)

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 urlhttps://github.com/ml-jku/rudder and demonstration videos at urlhttps://goo.gl/EQerZV.