mlsanityData to 14 Oct 2026

Rank-One Modified Value Iteration

arXiv 2505.01828 ↗First posted 3 May 2025math.OC cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, which is approximated using the power method. We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 13 of its 35 references that are in the map. First posted on arXiv 3 May 2025.

Builds on

13 of 35 references.

References · 13

  1. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  2. 2018Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterationscited by 25
  3. 2021Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Controlcited by 25
  4. 2019A First-Order Approach To Accelerated Value Iterationcited by 17
  5. 2018Anderson Acceleration for Reinforcement Learningcited by 15
  6. 2019Zap Q-Learning With Nonlinear Function Approximationcited by 13
  7. 2023Accelerating Value Iteration with Anchoringcited by 11
  8. 2021From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPscited by 9
  9. 2022Operator Splitting Value Iterationcited by 8
  10. 2022Dynamic Programming Through the Lens of Semismooth Newton-Type Methods (Extended Version)cited by 7
  11. 2019Generalized Second Order Value Iteration in Markov Decision Processescited by 5
  12. 2024Deflated Dynamics Value Iterationcited by 5
1 more
  1. 2023From Optimization to Control: Quasi Policy Iterationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

3 papers.

  1. 2026Switching-Geometry Analysis of Deflated Q-Value Iterationcited by 1
  2. 2025Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspectivecited by 0
  3. 2026Limiting-Kernel Q(λ): Bridging Short and Long Horizonscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation
  2. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
  3. 2025Non-stationary and Varying-discounting Markov Decision Processes for Reinforcement Learning
  4. 2026Markov Decision Processes of the Third Kind: Learning Distributions by Policy Gradient Descent
  5. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  6. 2026Towards Optimal Policy Improvement
  7. 2026Reinforcement Learning with Function Approximation for Non-Markov Processes
  8. 2025Planning and Learning in Average Risk-aware MDPs