# Truncated Variance Reduced Value Iteration

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 21 May 2024.

## Builds on (most cited first, 15 of 15)

- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time](https://mlsanity.com/paper/1704.01869/) (2017)
- [Approximate Value Iteration for Risk-aware Markov Decision Processes](https://mlsanity.com/paper/1701.01290/) (2017)
- [Empirical Q-Value Iteration](https://mlsanity.com/paper/1412.0180/) (2014)
- [Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs](https://mlsanity.com/paper/1911.00954/) (2019)

## Built on by (most cited first, 8 of 8)

- [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024)
- [Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model](https://mlsanity.com/paper/2506.00286/) (2025)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026)
- [On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2605.21763/) (2026)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)
- [Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2610.06931/) (2026)

## Abstract (arXiv)

We provide faster randomized algorithms for computing an ε-optimal policy in a discounted Markov decision process with Atot-state-action pairs, bounded rewards, and discount factor γ. We provide an tildeO(Atot[(1 - γ)-3ε-2 + (1 - γ)-2])-time algorithm in the sampling setting, where the probability transition matrix is unknown but accessible through a generative model which can be queried in tildeO(1)-time, and an tildeO(s + (1-γ)-2)-time algorithm in the offline setting where the probability transition matrix is known and s-sparse. These results improve upon the prior state-of-the-art which either ran in tildeO(Atot[(1 - γ)-3ε-2 + (1 - γ)-3]) time [Sidford, Wang, Wu, Ye 2018] in the sampling setting, tildeO(s + Atot (1-γ)-3) time [Sidford, Wang, Wu, Yang, Ye 2018] in the offline setting, or time at least quadratic in the number of states using interior point methods for linear programming. We achieve our results by building upon prior stochastic variance-reduced value iteration methods [Sidford, Wang, Wu, Yang, Ye 2018]. We provide a variant that carefully truncates the progress of its iterates to improve the variance of new variance-reduced sampling procedures that we introduce to implement the steps. Our method is essentially model-free and can be implemented in tildeO(Atot)-space when given generative model access. Consequently, our results take a step in closing the sample-complexity gap between model-free and model-based methods.