# Multi-Agent Reinforcement Learning with Reward Delays

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2022.

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

- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward](https://mlsanity.com/paper/2305.02527/) (2023)
- [Highway Reinforcement Learning](https://mlsanity.com/paper/2405.18289/) (2024)
- [TrafficGamer: Reliable and Flexible Traffic Simulation for Safety-Critical Scenarios with Game-Theoretic Oracles](https://mlsanity.com/paper/2408.15538/) (2024)
- [Belief-Based Offline Reinforcement Learning for Delay-Robust Policy Optimization](https://mlsanity.com/paper/2506.00131/) (2025)
- [Inverse Delayed Reinforcement Learning](https://mlsanity.com/paper/2412.02931/) (2024)
- [Rainbow Delay Compensation: A Multi-Agent Reinforcement Learning Framework for Mitigating Delayed Observation](https://mlsanity.com/paper/2505.03586/) (2025)
- [Cooperative Multi-agent RL with Communication Constraints](https://mlsanity.com/paper/2601.12518/) (2026)
- [Retroactive Advantage Correction: Closed-Form V-Trace Bias Correction for Delay-Aware RLHF](https://mlsanity.com/paper/2606.27580/) (2026)

## Abstract (arXiv)

This paper considers multi-agent reinforcement learning (MARL) where the rewards are received after delays and the delay time varies across agents and across time steps. Based on the V-learning framework, this paper proposes MARL algorithms that efficiently deal with reward delays. When the delays are finite, our algorithm reaches a coarse correlated equilibrium (CCE) with rate tildeO(fracH3√STKK+fracH3√SA√K) where K is the number of episodes, H is the planning horizon, S is the size of the state space, A is the size of the largest action space, and TK is the measure of total delay formally defined in the paper. Moreover, our algorithm is extended to cases with infinite delays through a reward skipping scheme. It achieves convergence rate similar to the finite delay case.