mlsanityData to 7 Oct 2026

Efficiently Solving MDPs with Stochastic Mirror Descent

arXiv 2008.12776 ↗First posted 28 Aug 2020cs.LG cs.DS math.OCcited by 52

Not on the map. Why?

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.

Key facts. Cited by 52 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

52 papers.

Sort:

By area:

  1. 2021Reward is enough for convex MDPscited by 82
  2. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  3. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  4. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  5. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  6. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  7. 2022Proximal Point Imitation Learningcited by 25
  8. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  9. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  10. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  11. 2021Bregman Gradient Policy Optimizationcited by 15
  12. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
38 more
  1. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  2. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  3. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
  4. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  5. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  6. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  7. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  8. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  9. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  10. 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 9
  11. 2021Distributed Saddle-Point Problems Under Similaritycited by 8
  12. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  13. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  14. 2021Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environmentcited by 6
  15. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 6
  16. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  17. 2024Truncated Variance Reduced Value Iterationcited by 6
  18. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  19. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  20. 2021Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solvingcited by 4
  21. 2021Distributionally Robust Optimization with Markovian Datacited by 4
  22. 2021Decentralized Personalized Federated Learning for Min-Max Problemscited by 4
  23. 2022Solving optimization problems with Blackwell approachabilitycited by 4
  24. 2024Computing Optimal Regularizers for Online Linear Optimizationcited by 4
  25. 2021Primal-Dual Stochastic Mirror Descent for MDPscited by 3
  26. 2022Algorithm for Constrained Markov Decision Process with Linear Convergencecited by 3
  27. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  28. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  29. 2021Near Optimal Policy Optimization via REPScited by 1
  30. 2023Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chainscited by 1
  31. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  32. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  33. 2026Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioningcited by 1
  34. 2026Gaussian Approximation for Asynchronous Q-learningcited by 1
  35. 2026Safe, Scalable, and Accurate Bayes Posterior Sampling for Large-Data Generalized Linear Mixed Modelscited by 1
  36. 2025Apprenticeship learning with prior beliefs using inverse optimizationcited by 0
  37. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  38. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0

50 most cited of 52 All 52 (JSON)