mlsanityData to 14 Oct 2026

Stochastic first-order methods for average-reward Markov decision processes

arXiv 2205.05800 ↗First posted 11 May 2022cs.LG math.OC stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

We study average-reward Markov decision processes (AMDPs) and develop novel first-order methods with strong theoretical guarantees for both policy optimization and policy evaluation. Compared with intensive research efforts in finite sample analysis of policy gradient methods for discounted MDPs, existing studies on policy gradient methods for AMDPs mostly focus on regret bounds under restrictive assumptions, and they often lack guarantees on the overall sample complexities. Towards this end, we develop an average-reward stochastic policy mirror descent (SPMD) method for solving AMDPs with and without regularizers and provide convergence guarantees in terms of the long-term average reward. For policy evaluation, existing on-policy methods suffer from sub-optimal convergence rates as well as failure in handling insufficiently random policies due to the lack of exploration in the action space. To remedy these issues, we develop a variance-reduced temporal difference (VRTD) method with linear function approximation for randomized policies along with optimal convergence guarantees, and design an exploratory VRTD method that resolves the exploration issue and provides comparable convergence guarantees. By combining the policy evaluation and policy optimization parts, we establish sample complexity results for solving AMDPs under both generative and Markovian noise models. It is worth noting that when linear function approximation is utilized, our algorithm only needs to update in the low-dimensional parameter space and thus can handle MDPs with large state and action spaces.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). Builds on 31 of its 66 references that are in the map. First posted on arXiv 11 May 2022.

Builds on

31 of 66 references.

References · 31

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  5. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  7. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  9. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  10. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  11. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  12. 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
19 more
  1. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  2. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  3. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  4. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  5. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  6. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  7. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 31
  8. 2021On-Policy Deep Reinforcement Learning for the Average-Reward Criterioncited by 30
  9. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  10. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 27
  11. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  12. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 23
  13. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  14. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  15. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 17
  16. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  17. 2022Block Policy Mirror Descentcited by 11
  18. 2020Optimal oracle inequalities for solving projected fixed-point equationscited by 10
  19. 2016Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and Morecited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 4; 2025: 10; 2026: 8.

32 papers.

Sort:

By area:

  1. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  2. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  3. 2022Policy Optimization over General State and Action Spacescited by 23
  4. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  5. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  7. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 13
  8. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  9. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  10. 2023Accelerated stochastic approximation with state-dependent noisecited by 11
  11. 2023Inverse Reinforcement Learning with the Average Reward Criterioncited by 8
  12. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
20 more
  1. 2025Average-Reward Soft Actor-Criticcited by 6
  2. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  3. 2023Infer and Adapt: Bipedal Locomotion Reward Learning from Demonstrations via Inverse Reinforcement Learningcited by 5
  4. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  5. 2025Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPscited by 4
  6. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  7. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  8. 2025On the Convergence of Policy Mirror Descent with Temporal Difference Evaluationcited by 3
  9. 2025Auto-exploration for online reinforcement learningcited by 3
  10. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
  11. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  12. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  13. 2025Towards Optimal Offline Reinforcement Learningcited by 2
  14. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  15. 2025Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Datacited by 2
  16. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 2
  17. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  18. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  19. 2026Bridging the Gap Between Average and Discounted TD Learningcited by 0
  20. 2026Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPscited by 0