# Learning Long-Term Reward Redistribution via Randomized Return Decomposition

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 87 references that are in the map.
- First posted on arXiv 26 Nov 2021.

## Builds on (most cited first, 30 of 47)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Learning Robust Rewards with Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1710.11248/) (2017)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training](https://mlsanity.com/paper/2106.05091/) (2021)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [Optimization of Molecules via Deep Reinforcement Learning](https://mlsanity.com/paper/1810.08678/) (2018)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [Deep Reinforcement Learning for De-Novo Drug Design](https://mlsanity.com/paper/1711.10907/) (2017)
- [Meta-Gradient Reinforcement Learning](https://mlsanity.com/paper/1805.09801/) (2018)
- [Dopamine: A Research Framework for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.06110/) (2018)
- [On Learning Intrinsic Rewards for Policy Gradient Methods](https://mlsanity.com/paper/1804.06459/) (2018)
- [Deep Coordination Graphs](https://mlsanity.com/paper/1910.00091/) (2019)
- [Hindsight Credit Assignment](https://mlsanity.com/paper/1912.02503/) (2019)
- [Simple random search provides a competitive approach to reinforcement learning](https://mlsanity.com/paper/1803.07055/) (2018)
- [Shapley Q-value: A Local Reward Approach to Solve Global Reward Games](https://mlsanity.com/paper/1907.05707/) (2019)
- [On the Expressivity of Markov Reward](https://mlsanity.com/paper/2111.00876/) (2021)
- [Hyperbolic Discounting and Learning over Multiple Horizons](https://mlsanity.com/paper/1902.06865/) (2019)
- [Reinforcement Learning with Random Delays](https://mlsanity.com/paper/2010.02966/) (2020)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [Deep Reinforcement Learning for Autonomous Internet of Things: Model, Applications and Challenges](https://mlsanity.com/paper/1907.09059/) (2019)

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

- [Better Training of GFlowNets with Local Credit and Incomplete Trajectories](https://mlsanity.com/paper/2302.01687/) (2023)
- [Preference Transformer: Modeling Human Preferences using Transformers for RL](https://mlsanity.com/paper/2303.00957/) (2023)
- [Dense Reward for Free in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2402.00782/) (2024)
- [When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment](https://mlsanity.com/paper/2307.03864/) (2023)
- [Learning Energy Decompositions for Partial Inference of GFlowNets](https://mlsanity.com/paper/2310.03301/) (2023)
- [Latent Reward: LLM-Empowered Credit Assignment in Episodic Reinforcement Learning](https://mlsanity.com/paper/2412.11120/) (2024)
- [Interpretable Reward Redistribution in Reinforcement Learning: A Causal Approach](https://mlsanity.com/paper/2305.18427/) (2023)
- [Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward](https://mlsanity.com/paper/2206.06426/) (2022)
- [Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysis](https://mlsanity.com/paper/2306.16803/) (2023)
- [Hindsight PRIORs for Reward Learning from Human Preferences](https://mlsanity.com/paper/2404.08828/) (2024)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [Inverse Reinforcement Learning Meets Large Language Model Post-Training: Basics, Advances, and Opportunities](https://mlsanity.com/paper/2507.13158/) (2025)
- [Seq2Seq Imitation Learning for Tactile Feedback-based Manipulation](https://mlsanity.com/paper/2303.02646/) (2023)
- [Towards Fairness in Personalized Ads Using Impression Variance Aware Reinforcement Learning](https://mlsanity.com/paper/2306.03293/) (2023)
- [STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2304.07520/) (2023)
- [Attention-Based Reward Shaping for Sparse and Delayed Rewards](https://mlsanity.com/paper/2505.10802/) (2025)
- [Efficient Meta Reinforcement Learning for Preference-based Fast Adaptation](https://mlsanity.com/paper/2211.10861/) (2022)
- [Hindsight-DICE: Stable Credit Assignment for Deep Reinforcement Learning](https://mlsanity.com/paper/2307.11897/) (2023)
- [Self-evolving LLM agents with in-distribution Optimization](https://mlsanity.com/paper/2606.07367/) (2026)
- [Episodic Return Decomposition by Difference of Implicitly Assigned Sub-Trajectory Reward](https://mlsanity.com/paper/2312.10642/) (2023)
- [Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning](https://mlsanity.com/paper/2410.20176/) (2024)
- [ELEMENT: Episodic and Lifelong Exploration via Maximum Entropy](https://mlsanity.com/paper/2412.03800/) (2024)
- [Aligning Dialogue Agents with Global Feedback via Large Language Model Multimodal Reward Decomposition](https://mlsanity.com/paper/2505.15922/) (2025)
- [Preference-Guided Learning for Sparse-Reward Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21828/) (2025)
- [Off-Beat Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.13718/) (2022)
- [Improving Dialogue Agents by Decomposing One Global Explicit Annotation with Local Implicit Multimodal Feedback](https://mlsanity.com/paper/2403.11330/) (2024)
- [ELO-Rated Sequence Rewards: Advancing Reinforcement Learning Models](https://mlsanity.com/paper/2409.03301/) (2024)
- [Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.14779/) (2024)
- [PRISM: Parallel Reward Integration with Symmetry for MORL](https://mlsanity.com/paper/2602.18277/) (2026)
- [Reinforcement Learning from Bagged Reward](https://mlsanity.com/paper/2402.03771/) (2024)

## Abstract (arXiv)

Many practical applications of reinforcement learning require agents to learn from sparse and delayed rewards. It challenges the ability of agents to attribute their actions to future outcomes. In this paper, we consider the problem formulation of episodic reinforcement learning with trajectory feedback. It refers to an extreme delay of reward signals, in which the agent can only obtain one reward signal at the end of each trajectory. A popular paradigm for this problem setting is learning with a designed auxiliary dense reward function, namely proxy reward, instead of sparse environmental signals. Based on this framework, this paper proposes a novel reward redistribution algorithm, randomized return decomposition (RRD), to learn a proxy reward function for episodic reinforcement learning. We establish a surrogate problem by Monte-Carlo sampling that scales up least-squares-based reward redistribution to long-horizon problems. We analyze our surrogate loss function by connection with existing methods in the literature, which illustrates the algorithmic properties of our approach. In experiments, we extensively evaluate our proposed method on a variety of benchmark tasks with episodic rewards and demonstrate substantial improvement over baseline algorithms.