mlsanityData to 7 Oct 2026

Deflated Dynamics Value Iteration

arXiv 2407.10454 ↗First posted 15 Jul 2024cs.LG math.OCcited by 4

Not on the map. Why?

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 21 of its 74 references that are in the map. First posted on arXiv 15 Jul 2024.

Builds on

21 of 74 references.

References · 21

  1. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  4. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  5. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  6. 2019Momentum in Reinforcement Learningcited by 19
  7. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  8. 2019A First-Order Approach To Accelerated Value Iterationcited by 16
  9. 2018Anderson Acceleration for Reinforcement Learningcited by 14
  10. 2014Topological Value Iteration Algorithmscited by 13
  11. 2020Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learningcited by 13
  12. 2023Accelerating Value Iteration with Anchoringcited by 10
9 more
  1. 2019Regularized Anderson Acceleration for Off-Policy Deep Reinforcement Learningcited by 8
  2. 2021From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPscited by 8
  3. 2022Operator Splitting Value Iterationcited by 8
  4. 2021Damped Anderson Mixing for Deep Reinforcement Learning: Acceleration, Convergence, and Stabilizationcited by 7
  5. 2021On Anderson acceleration for partially observable Markov decision processescited by 3
  6. 2022Anderson Acceleration for Partially Observable Markov Decision Processes: A Maximum Entropy Approachcited by 3
  7. 2016A Matrix Splitting Perspective on Planning with Optionscited by 2
  8. 2020Multiply Accelerated Value Iteration for Non-Symmetric Affine Fixed Point Problems and application to Markov Decision Processescited by 2
  9. 2024PID Accelerated Temporal Difference Algorithmscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Rank-One Modified Value Iterationcited by 2
  2. 2026Switching-Geometry Analysis of Deflated Q-Value Iterationcited by 1
  3. 2026Heavy-Ball Q-Learning with Residual Weighting Correctioncited by 0
  4. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizonscited by 0