mlsanityData to 7 Oct 2026

Learning and Planning in Average-Reward Markov Decision Processes

arXiv 2006.16318 ↗First posted 29 Jun 2020cs.LG cs.AIcited by 54

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 7; 2022: 6; 2023: 8; 2024: 10; 2025: 11; 2026: 11.

54 papers.

Sort:

By area:

  1. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  2. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
  3. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 30
  4. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  5. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 29
  6. 2022Markovian Interference in Experimentscited by 22
  7. 2023Robust Average-Reward Markov Decision Processescited by 22
  8. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  9. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  10. 2021Average-Reward Reinforcement Learning with Trust Region Methodscited by 18
  11. 2022Influencing Long-Term Behavior in Multiagent Reinforcement Learningcited by 18
  12. 2024Reward Centeringcited by 16
38 more
  1. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  2. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  3. 2021Continual Learning In Environments With Polynomial Mixing Timescited by 13
  4. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 13
  5. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  6. 2021Average-Reward Learning and Planning with Optionscited by 8
  7. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 6
  8. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processescited by 6
  9. 2024Ornstein-Uhlenbeck Adaptation as a Mechanism for Learning in Brains and Machinescited by 6
  10. 2025Average-Reward Soft Actor-Criticcited by 6
  11. 2022On Convergence of Average-Reward Off-Policy Control Algorithms in Weakly Communicating MDPscited by 5
  12. 2023Full Gradient Deep Reinforcement Learning for Average-Reward Criterioncited by 5
  13. 2024RVI-SAC: Average Reward Off-Policy Deep Reinforcement Learningcited by 5
  14. 2025A Differential Perspective on Distributional Reinforcement Learningcited by 5
  15. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  16. 2023ACPO: A Policy Optimization Algorithm for Average MDPs with Constraintscited by 4
  17. 2022Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learningcited by 2
  18. 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learningcited by 2
  19. 2024Burning RED: Unlocking Subtask-Driven Reinforcement Learning and Risk-Awareness in Average-Reward Markov Decision Processescited by 2
  20. 2025Planning and Learning in Average Risk-aware MDPscited by 2
  21. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  22. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  23. 2025Implicit Updates for Average-Reward Temporal Difference Learningcited by 2
  24. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  25. 2022Reinforcement Teachingcited by 1
  26. 2024Why Online Reinforcement Learning is Causalcited by 1
  27. 2024Hierarchical Average-Reward Linearly-solvable Markov Decision Processescited by 1
  28. 2025An Empirical Study of Deep Reinforcement Learning in Continuing Taskscited by 1
  29. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  30. 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iterationcited by 1
  31. 2026Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotientscited by 1
  32. 2026Maximum Entropy Exploration Without the Rolloutscited by 1
  33. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  34. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  35. 2023Learning to Stabilize Online Reinforcement Learning in Unbounded State Spacescited by 0
  36. 2025Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectivescited by 0
  37. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  38. 2026Deep Reinforcement Learning and The Tale of Two Temporal Difference Errorscited by 0

50 most cited of 54 All 54 (JSON)