# A First-Order Approach To Accelerated Value Iteration

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

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

- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Deflated Dynamics Value Iteration](https://mlsanity.com/paper/2407.10454/) (2024)
- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [Rank-One Modified Value Iteration](https://mlsanity.com/paper/2505.01828/) (2025)
- [PID Accelerated Temporal Difference Algorithms](https://mlsanity.com/paper/2407.08803/) (2024)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [A Switching System Theory of Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2605.11021/) (2026)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Switching-Geometry Analysis of Deflated Q-Value Iteration](https://mlsanity.com/paper/2605.10811/) (2026)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)
- [Heavy-Ball Q-Learning with Residual Weighting Correction](https://mlsanity.com/paper/2606.27112/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) are used to model stochastic systems in many applications. Several efficient algorithms to compute optimal policies have been studied in the literature, including value iteration (VI) and policy iteration. However, these do not scale well especially when the discount factor for the infinite horizon discounted reward, λ, gets close to 1. In particular, the running time scales as O left( 1/(1-λ) right) for these algorithms. In this paper, our goal is to design new algorithms that scale better than previous approaches when λ approaches 1. Our main contribution is to present a connection between VI and gradient descent and adapt the ideas of acceleration and momentum in convex optimization to design faster algorithms for MDPs. We prove theoretical guarantees of a faster convergence of our algorithms for the computation of the value function of a policy, where the running times of our algorithms scale as O left( 1/√1-λ right) for reversible MDP instances. The improvement is quite analogous to Nesterov's acceleration and momentum in convex optimization. We also provide a lower bound on the convergence properties of any first-order algorithm for solving MDPs, presenting a family of MDPs instances for which no algorithm can converge faster than VI when the number of iterations is smaller than the number of states. We introduce a Safe Accelerated Value Iteration (S-AVI), which alternates between accelerated updates and value iteration updates. Our algorithm S-AVI is worst-case optimal and retains the theoretical convergence properties of VI while exhibiting strong empirical performances, providing significant speedups compared to classical approaches (up to one order of magnitude in many cases) for a large test bed of MDP instances.