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

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

## Key facts

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

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

- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Provable Benefit of Multitask Representation Learning in Reinforcement Learning](https://mlsanity.com/paper/2206.05900/) (2022)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation](https://mlsanity.com/paper/2202.00308/) (2022)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Gap-Dependent Bounds for Two-Player Markov Games](https://mlsanity.com/paper/2107.00685/) (2021)
- [Instance-Dependent Confidence and Early Stopping for Reinforcement Learning](https://mlsanity.com/paper/2201.08536/) (2022)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)

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