# Accelerating Value Iteration with Anchoring

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 105 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 30 of 48)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Increasing the Action Gap: New Operators for Reinforcement Learning](https://mlsanity.com/paper/1512.04860/) (2015)
- [Is the Policy Gradient a Gradient?](https://mlsanity.com/paper/1906.07073/) (2019)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations](https://mlsanity.com/paper/1808.03971/) (2018)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [Momentum in Reinforcement Learning](https://mlsanity.com/paper/1910.09322/) (2019)
- [Optimized first-order methods for smooth convex minimization](https://mlsanity.com/paper/1406.5468/) (2014)
- [Regularized Nonlinear Acceleration](https://mlsanity.com/paper/1606.04133/) (2016)
- [ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems](https://mlsanity.com/paper/1905.10899/) (2019)
- [Value Iteration in Continuous Actions, States and Time](https://mlsanity.com/paper/2105.04682/) (2021)
- [A First-Order Approach To Accelerated Value Iteration](https://mlsanity.com/paper/1905.09963/) (2019)
- [Multi-Agent Routing Value Iteration Network](https://mlsanity.com/paper/2007.05096/) (2020)
- [Generalized Value Iteration Networks: Life Beyond Lattices](https://mlsanity.com/paper/1706.02416/) (2017)
- [Bayesian Bellman Operators](https://mlsanity.com/paper/2106.05012/) (2021)
- [Anderson Acceleration for Reinforcement Learning](https://mlsanity.com/paper/1809.09501/) (2018)
- [Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions](https://mlsanity.com/paper/1803.06600/) (2018)
- [Primal-dual accelerated gradient methods with small-dimensional relaxation oracle](https://mlsanity.com/paper/1809.05895/) (2018)
- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [Optimal error bounds for nonexpansive fixed-point iterations in normed spaces](https://mlsanity.com/paper/2108.10969/) (2021)
- [Regularized Anderson Acceleration for Off-Policy Deep Reinforcement Learning](https://mlsanity.com/paper/1909.03245/) (2019)

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

- [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)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [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)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective](https://mlsanity.com/paper/2512.07377/) (2025)
- [Accelerated and Stable Convergence with Anchored Generalized Optimistic Method](https://mlsanity.com/paper/2606.21528/) (2026)
- [Heavy-Ball Q-Learning with Residual Weighting Correction](https://mlsanity.com/paper/2606.27112/) (2026)

## Abstract (arXiv)

Value Iteration (VI) is foundational to the theory and practice of modern reinforcement learning, and it is known to converge at a O(γk)-rate, where γ is the discount factor. Surprisingly, however, the optimal rate for the VI setup was not known, and finding a general acceleration mechanism has been an open problem. In this paper, we present the first accelerated VI for both the Bellman consistency and optimality operators. Our method, called Anc-VI, is based on an anchoring mechanism (distinct from Nesterov's acceleration), and it reduces the Bellman error faster than standard VI. In particular, Anc-VI exhibits a O(1/k)-rate for γ≈ 1 or even γ=1, while standard VI has rate O(1) for γ≥ 1-1/k, where k is the iteration count. We also provide a complexity lower bound matching the upper bound up to a constant factor of 4, thereby establishing optimality of the accelerated rate of Anc-VI. Finally, we show that the anchoring mechanism provides the same benefit in the approximate VI and Gauss--Seidel VI setups as well.