# Learning and Planning in Average-Reward Markov Decision Processes

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

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

- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [On-Policy Deep Reinforcement Learning for the Average-Reward Criterion](https://mlsanity.com/paper/2106.07329/) (2021)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Markovian Interference in Experiments](https://mlsanity.com/paper/2206.02371/) (2022)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Average-Reward Reinforcement Learning with Trust Region Methods](https://mlsanity.com/paper/2106.03442/) (2021)
- [Influencing Long-Term Behavior in Multiagent Reinforcement Learning](https://mlsanity.com/paper/2203.03535/) (2022)
- [Single-Trajectory Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2301.11721/) (2023)
- [Reward Centering](https://mlsanity.com/paper/2405.09999/) (2024)
- [Continual Learning In Environments With Polynomial Mixing Times](https://mlsanity.com/paper/2112.07066/) (2021)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Average-Reward Learning and Planning with Options](https://mlsanity.com/paper/2110.13855/) (2021)
- [Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms](https://mlsanity.com/paper/2302.01450/) (2023)
- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly Communicating MDPs](https://mlsanity.com/paper/2209.15141/) (2022)
- [RVI-SAC: Average Reward Off-Policy Deep Reinforcement Learning](https://mlsanity.com/paper/2408.01972/) (2024)
- [Ornstein-Uhlenbeck Adaptation as a Mechanism for Learning in Brains and Machines](https://mlsanity.com/paper/2410.13563/) (2024)
- [Average-Reward Soft Actor-Critic](https://mlsanity.com/paper/2501.09080/) (2025)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)
- [A Differential Perspective on Distributional Reinforcement Learning](https://mlsanity.com/paper/2506.03333/) (2025)
- [ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints](https://mlsanity.com/paper/2302.00808/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)

## Abstract (arXiv)

We introduce learning and planning algorithms for average-reward MDPs, including 1) the first general proven-convergent off-policy model-free control algorithm without reference states, 2) the first proven-convergent off-policy model-free prediction algorithm, and 3) the first off-policy learning algorithm that converges to the actual value function rather than to the value function plus an offset. All of our algorithms are based on using the temporal-difference error rather than the conventional error when updating the estimate of the average reward. Our proof techniques are a slight generalization of those by Abounadi, Bertsekas, and Borkar (2001). In experiments with an Access-Control Queuing Task, we show some of the difficulties that can arise when using methods that rely on reference states and argue that our new algorithms can be significantly easier to use.