mlsanityData to 14 Oct 2026

Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

arXiv 1910.07072 ↗First posted 15 Oct 2019cs.LG cs.AI stat.MLcited by 82

Not on the map. Why?

Cited by 26 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-reward version and achieves O(T2/3) regret after T steps, under the minimal assumption of weakly communicating MDPs. To our knowledge, this is the first model-free algorithm for general MDPs in this setting. The second algorithm makes use of recent advances in adaptive algorithms for adversarial multi-armed bandits and improves the regret to O(√T), albeit with a stronger ergodic assumption. This result significantly improves over the O(T3/4) regret achieved by the only existing model-free algorithm by Abbasi-Yadkori et al. (2019a) for ergodic MDPs in the infinite-horizon average-reward setting.

Key facts. Cited by 82 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 15; 2022: 9; 2023: 18; 2024: 17; 2025: 11; 2026: 11.

82 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  2. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 80
  3. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  4. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  5. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 43
  6. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  7. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 30
  8. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  9. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  10. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  11. 2022You Only Live Once: Single-Life Reinforcement Learningcited by 24
  12. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
38 more
  1. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
  2. 2023Robust Average-Reward Markov Decision Processescited by 22
  3. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  4. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  5. 2022Influencing Long-Term Behavior in Multiagent Reinforcement Learningcited by 18
  6. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  7. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  8. 2023Best of Both Worlds Policy Optimizationcited by 17
  9. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  10. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  11. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  12. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 15
  13. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  14. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 14
  15. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  16. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  17. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 8
  18. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 8
  19. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  20. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  21. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 7
  22. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  23. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  24. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  25. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  26. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  27. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  28. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  29. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  30. 2024Provable Domain Adaptation for Offline Reinforcement Learning with Limited Samplescited by 5
  31. 2024How to Find the Exact Pareto Front for Multi-Objective MDPs?cited by 5
  32. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  33. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 4
  34. 2022Posterior Sampling for Continuing Environmentscited by 4
  35. 2023Reinforcement Learning with Non-Cumulative Objectivecited by 4
  36. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
  37. 2022Hardness in Markov Decision Processes: Theory and Practicecited by 3
  38. 2023Provable Reset-free Reinforcement Learning by No-Regret Reductioncited by 3

50 most cited of 82 All 82 (JSON)