# Efficiently Solving MDPs with Stochastic Mirror Descent

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2020.

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

- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Optimal Algorithms for Decentralized Stochastic Variational Inequalities](https://mlsanity.com/paper/2202.02771/) (2022)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (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)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment](https://mlsanity.com/paper/2102.07120/) (2021)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)

## Abstract (arXiv)

We present a unified framework based on primal-dual stochastic mirror descent for approximately solving infinite-horizon Markov decision processes (MDPs) given a generative model. When applied to an average-reward MDP with Atot total state-action pairs and mixing time bound tmix our method computes an ε-optimal policy with an expected widetildeO(tmix2 Atot ε-2) samples from the state-transition matrix, removing the ergodicity dependence of prior art. When applied to a γ-discounted MDP with Atot total state-action pairs our method computes an ε-optimal policy with an expected widetildeO((1-γ)-4 Atot ε-2) samples, matching the previous state-of-the-art up to a (1-γ)-1 factor. Both methods are model-free, update state values and policies simultaneously, and run in time linear in the number of samples taken. We achieve these results through a more general stochastic mirror descent framework for solving bilinear saddle-point problems with simplex and box domains and we demonstrate the flexibility of this framework by providing further applications to constrained MDPs.