mlsanityData to 14 Oct 2026

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

arXiv 1710.09988 ↗First posted 27 Oct 2017cs.DS cs.LG math.OCcited by 57

Not on the map. Why?

Abstract (arXiv)

In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes. Given a discounted Markov Decision Process (DMDP) with |S| states, |A| actions, discount factor γ∈(0,1), and rewards in the range [-M, M], we show how to compute an ε-optimal policy, with probability 1 - δ in time [ tildeOleft( left(|S|2 |A| + frac|S| |A|(1 - γ)3 right) logleft( fracMε right) logleft( frac1δ right) right) ~ . ] This contribution reflects the first nearly linear time, nearly linearly convergent algorithm for solving DMDPs for intermediate values of γ. We also show how to obtain improved sublinear time algorithms provided we can sample from the transition function in O(1) time. Under this assumption we provide an algorithm which computes an ε-optimal policy with probability 1 - δ in time [ tildeO left(frac|S| |A| M2(1 - γ)4 ε2 log left(frac1δright) right) ~. ] Lastly, we extend both these algorithms to solve finite horizon MDPs. Our algorithms improve upon the previous best for approximately computing optimal policies for fixed-horizon MDPs in multiple parameter regimes. Interestingly, we obtain our results by a careful modification of approximate value iteration. We show how to combine classic approximate value iteration analysis with new techniques in variance reduction. Our fastest algorithms leverage further insights to ensure that our algorithms make monotonic progress towards the optimal value. This paper is one of few instances in using sampling to obtain a linearly convergent linear programming algorithm and we hope that the analysis may be useful more broadly.

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Oct 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

57 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  3. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  4. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  5. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  6. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  8. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  9. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  10. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  11. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  12. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
38 more
  1. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  2. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  3. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  4. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  5. 2023Replicability in Reinforcement Learningcited by 21
  6. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  7. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
  8. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  9. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  10. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  11. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  12. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  13. 2024Truncated Variance Reduced Value Iterationcited by 8
  14. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  15. 2023The complexity of non-stationary reinforcement learningcited by 7
  16. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  17. 2022Instance-Dependent Confidence and Early Stopping for Reinforcement Learningcited by 5
  18. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  19. 2024Deflated Dynamics Value Iterationcited by 5
  20. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Modelcited by 5
  21. 2022A Note on Target Q-learning For Solving Finite MDPs with A Generative Oraclecited by 4
  22. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  23. 2022Planning to the Information Horizon of BAMDPs via Epistemic State Abstractioncited by 4
  24. 2021Primal-Dual Stochastic Mirror Descent for MDPscited by 3
  25. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 3
  26. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  27. 2021An Adaptive State Aggregation Algorithm for Markov Decision Processescited by 2
  28. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  29. 2024Faster Q-Learning Algorithms for Restless Banditscited by 2
  30. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  31. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  32. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2
  33. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  34. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  35. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  36. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  37. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  38. 2026Sample Complexity Bounds for Stochastic Shortest Path with a Generative Modelcited by 1

50 most cited of 57 All 57 (JSON)