# Off-Policy Reinforcement Learning with Delayed Rewards

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 22 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Molecular De Novo Design through Deep Reinforcement Learning](https://mlsanity.com/paper/1704.07555/) (2017)
- [RUDDER: Return Decomposition for Delayed Rewards](https://mlsanity.com/paper/1806.07857/) (2018)
- [On Learning Intrinsic Rewards for Policy Gradient Methods](https://mlsanity.com/paper/1804.06459/) (2018)
- [A Benchmark Environment Motivated by Industrial Control Problems](https://mlsanity.com/paper/1709.09480/) (2017)
- [Acting in Delayed Environments with Non-Stationary Markov Policies](https://mlsanity.com/paper/2101.11992/) (2021)
- [Learning Guidance Rewards with Trajectory-space Smoothing](https://mlsanity.com/paper/2010.12718/) (2020)
- [Learning Self-Imitating Diverse Policies](https://mlsanity.com/paper/1805.10309/) (2018)
- [Sequence Modeling of Temporal Credit Assignment for Episodic Reinforcement Learning](https://mlsanity.com/paper/1905.13420/) (2019)
- [Self-Imitation Learning by Planning](https://mlsanity.com/paper/2103.13834/) (2021)
- [Generative Adversarial Self-Imitation Learning](https://mlsanity.com/paper/1812.00950/) (2018)
- [Reward Propagation Using Graph Convolutional Networks](https://mlsanity.com/paper/2010.02474/) (2020)

## Built on by (most cited first, 25 of 25)

- [Dense Reward for Free in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2402.00782/) (2024)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [Latent Reward: LLM-Empowered Credit Assignment in Episodic Reinforcement Learning](https://mlsanity.com/paper/2412.11120/) (2024)
- [Stable Gradients for Stable Learning at Scale in Deep Reinforcement Learning](https://mlsanity.com/paper/2506.15544/) (2025)
- [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)
- [Boosting Reinforcement Learning with Strongly Delayed Feedback Through Auxiliary Short Delays](https://mlsanity.com/paper/2402.03141/) (2024)
- [Off-Policy Evaluation for Human Feedback](https://mlsanity.com/paper/2310.07123/) (2023)
- [STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2304.07520/) (2023)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Episodic Return Decomposition by Difference of Implicitly Assigned Sub-Trajectory Reward](https://mlsanity.com/paper/2312.10642/) (2023)
- [Highway Reinforcement Learning](https://mlsanity.com/paper/2405.18289/) (2024)
- [Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning](https://mlsanity.com/paper/2410.20176/) (2024)
- [Off-Beat Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2205.13718/) (2022)
- [Agent-Temporal Credit Assignment for Optimal Policy Preservation in Sparse Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.14779/) (2024)
- [Belief-Based Offline Reinforcement Learning for Delay-Robust Policy Optimization](https://mlsanity.com/paper/2506.00131/) (2025)
- [Synthetic POMDPs to Challenge Memory-Augmented RL: Memory Demand Structure Modeling](https://mlsanity.com/paper/2508.04282/) (2025)
- [Reinforcement Learning from Bagged Reward](https://mlsanity.com/paper/2402.03771/) (2024)
- [Inverse Delayed Reinforcement Learning](https://mlsanity.com/paper/2412.02931/) (2024)
- [PYTHALAB-MERA: Validation-Grounded Memory, Retrieval, and Acceptance Control for Frozen-LLM Coding Agents](https://mlsanity.com/paper/2605.08468/) (2026)
- [Delay-Empowered Causal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2605.12261/) (2026)
- [Retroactive Advantage Correction: Closed-Form V-Trace Bias Correction for Delay-Aware RLHF](https://mlsanity.com/paper/2606.27580/) (2026)
- [Explore Beyond the Boundary Using Entropic Information](https://mlsanity.com/paper/2607.29419/) (2026)
- [Learning Reliable Parking Policies via Offline Reinforcement Learning with Quantized Action Representations](https://mlsanity.com/paper/2609.19894/) (2026)
- [SpikeCredit: Temporal Credit Carrier for Reinforcement Learning with Sparse Rewards](https://mlsanity.com/paper/2609.35268/) (2026)

## Abstract (arXiv)

We study deep reinforcement learning (RL) algorithms with delayed rewards. In many real-world tasks, instant rewards are often not readily accessible or even defined immediately after the agent performs actions. In this work, we first formally define the environment with delayed rewards and discuss the challenges raised due to the non-Markovian nature of such environments. Then, we introduce a general off-policy RL framework with a new Q-function formulation that can handle the delayed rewards with theoretical convergence guarantees. For practical tasks with high dimensional state spaces, we further introduce the HC-decomposition rule of the Q-function in our framework which naturally leads to an approximation scheme that helps boost the training efficiency and stability. We finally conduct extensive experiments to demonstrate the superior performance of our algorithms over the existing work and their variants.