# Rank-One Modified Value Iteration

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

## 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 (most cited first, 13 of 13)

- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations](https://mlsanity.com/paper/1808.03971/) (2018)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [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)
- [Zap Q-Learning With Nonlinear Function Approximation](https://mlsanity.com/paper/1910.05405/) (2019)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [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)
- [Operator Splitting Value Iteration](https://mlsanity.com/paper/2211.13937/) (2022)
- [Dynamic Programming Through the Lens of Semismooth Newton-Type Methods (Extended Version)](https://mlsanity.com/paper/2203.08678/) (2022)
- [Generalized Second Order Value Iteration in Markov Decision Processes](https://mlsanity.com/paper/1905.03927/) (2019)
- [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)

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

- [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)
- [Limiting-Kernel Q(λ): Bridging Short and Long Horizons](https://mlsanity.com/paper/2609.27741/) (2026)

## 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.