# Deflated Dynamics Value Iteration

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 21 of its 74 references that are in the map.
- First posted on arXiv 15 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Momentum in Reinforcement Learning](https://mlsanity.com/paper/1910.09322/) (2019)
- [Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation](https://mlsanity.com/paper/2002.02584/) (2020)
- [A First-Order Approach To Accelerated Value Iteration](https://mlsanity.com/paper/1905.09963/) (2019)
- [Anderson Acceleration for Reinforcement Learning](https://mlsanity.com/paper/1809.09501/) (2018)
- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning](https://mlsanity.com/paper/2002.10301/) (2020)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Regularized Anderson Acceleration for Off-Policy Deep Reinforcement Learning](https://mlsanity.com/paper/1909.03245/) (2019)
- [From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs](https://mlsanity.com/paper/2104.10677/) (2021)
- [Damped Anderson Mixing for Deep Reinforcement Learning: Acceleration, Convergence, and Stabilization](https://mlsanity.com/paper/2110.08896/) (2021)
- [Operator Splitting Value Iteration](https://mlsanity.com/paper/2211.13937/) (2022)
- [On Anderson acceleration for partially observable Markov decision processes](https://mlsanity.com/paper/2103.15275/) (2021)
- [Anderson Acceleration for Partially Observable Markov Decision Processes: A Maximum Entropy Approach](https://mlsanity.com/paper/2211.14998/) (2022)
- [A Matrix Splitting Perspective on Planning with Options](https://mlsanity.com/paper/1612.00916/) (2016)
- [Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processes](https://mlsanity.com/paper/2009.10427/) (2020)
- [PID Accelerated Temporal Difference Algorithms](https://mlsanity.com/paper/2407.08803/) (2024)

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

- [Rank-One Modified Value Iteration](https://mlsanity.com/paper/2505.01828/) (2025)
- [Switching-Geometry Analysis of Deflated Q-Value Iteration](https://mlsanity.com/paper/2605.10811/) (2026)
- [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)
- [Limiting-Kernel Q(λ): Bridging Short and Long Horizons](https://mlsanity.com/paper/2609.27741/) (2026)

## Abstract (arXiv)

The Value Iteration (VI) algorithm is an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithms as well. As the error convergence rate of VI as a function of iteration k is O(γk), it is slow when the discount factor γ is close to 1. To accelerate the computation of the value function, we propose Deflated Dynamics Value Iteration (DDVI). DDVI uses matrix splitting and matrix deflation techniques to effectively remove (deflate) the top s dominant eigen-structure of the transition matrix Pπ. We prove that this leads to a tildeO(γk |λs+1|k) convergence rate, where λs+1is (s+1)-th largest eigenvalue of the dynamics matrix. We then extend DDVI to the RL setting and present Deflated Dynamics Temporal Difference (DDTD) algorithm. We empirically show the effectiveness of the proposed algorithms.