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

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

## 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 (most cited first, 30 of 31)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [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)
- [On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operators](https://mlsanity.com/paper/1311.2776/) (2013)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Improved Regret Bound and Experience Replay in Regularized Policy Iteration](https://mlsanity.com/paper/2102.12611/) (2021)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Block Policy Mirror Descent](https://mlsanity.com/paper/2201.05756/) (2022)
- [Optimal oracle inequalities for solving projected fixed-point equations](https://mlsanity.com/paper/2012.05299/) (2020)

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

- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Policy Optimization over General State and Action Spaces](https://mlsanity.com/paper/2211.16715/) (2022)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints](https://mlsanity.com/paper/2212.13861/) (2022)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Inverse Reinforcement Learning with the Average Reward Criterion](https://mlsanity.com/paper/2305.14608/) (2023)
- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [Average-Reward Soft Actor-Critic](https://mlsanity.com/paper/2501.09080/) (2025)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Infer and Adapt: Bipedal Locomotion Reward Learning from Demonstrations via Inverse Reinforcement Learning](https://mlsanity.com/paper/2309.16074/) (2023)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs](https://mlsanity.com/paper/2510.18340/) (2025)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Towards Optimal Offline Reinforcement Learning](https://mlsanity.com/paper/2503.12283/) (2025)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Policy Mirror Descent with Temporal Difference Learning: Sample Complexity under Online Markov Data](https://mlsanity.com/paper/2512.24056/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)

## 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.