Research map / Learning theory and algorithms / Matrix and tensor methods
Rank-One Modified Value Iteration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Rank-One Modified Value Iteration (R1-VI) and Rank-One Q-learning (R1-QL), which replace the PI matrix gain (I - γP_k)^{-1} with a rank-one approximation 1d^T using the stationary distribution estimated by a single power-method step, keeping VI/QL per-iteration cost.
Problem
Value iteration converges only linearly while policy iteration is faster but has cubic per-iteration cost from policy evaluation; the paper seeks a method with PI-like speed at VI/Q-learning per-iteration cost for planning and learning in discounted MDPs.
Approach
Use a rank-one approximation of the greedy policy's transition matrix, P_k ≈ 1 d_k^T where d_k is its stationary distribution estimated by a single power-method iteration (warm-started across iterations), so the PI-type gain (I-γP_k)^{-1} is applied in closed form via Woodbury; the sampled analogue gives R1-QL.
Key results
- On Garnet and Graph MDPs, R1-VI reaches error thresholds in fewer iterations than VI, Nesterov-VI and Anderson-VI, with the gap largest when the discount factor is close to 1, and its convergence is comparable to PI.
- R1-QL achieves comparable or lower final error than QL, Speedy QL and Zap QL after 5000 synchronous iterations, and stays robust as the discount factor increases to 0.999.
- Theory: R1-VI converges linearly at rate gamma (same as VI) and R1-QL converges almost surely to q* at least as fast as QL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use rank-one stationary-distribution correction in place of standard VI updates | Value iteration · Garnet MDPs | iterations to reach error threshold | Helped |
| Use rank-one stationary-distribution correction in place of standard VI updates | Value iteration · Graph MDPs | value and Bellman errors | Helped |
| Use rank-one stationary-distribution correction in place of standard VI updates | Value iteration · Garnet and Graph MDPs | convergence performance | Mixed |
| Use rank-one stationary-distribution correction in place of standard Q-learning updates | Q-learning · Garnet and Graph MDPs | final error | Helped |
| Use rank-one stationary-distribution correction in place of standard Q-learning updates | Q-learning · Garnet and Graph MDPs, lower discount factors | error | No clear effect |
| Use rank-one stationary-distribution correction in place of standard Q-learning updates | Q-learning · Garnet and Graph MDPs, higher discount factors | error | Helped |
| Use rank-one stationary-distribution correction in place of standard Q-learning updates | Q-learning · Garnet and Graph MDPs | error variance | Helped |
| Use rank-one stationary-distribution correction in place of standard VI updates | Value iteration · Absorbing Gridworld with positive-reward absorbing state | value and Bellman errors | Helped |
| Use rank-one stationary-distribution correction in place of standard VI updates | Value iteration · Terminal Gridworld with zero-reward absorbing state | value and Bellman errors | Hurt |
Surprising findings
- Convergence proofs hold for any distribution d_k, so the stationary-distribution accuracy is not needed for the guarantee, and the theory does not explain the empirical speedup.
- In a Terminal Gridworld whose absorbing state has zero reward, R1-VI performs slightly worse than accelerated baselines because the rank-one correction term vanishes.
Limitations
- Theoretical guarantees match only the rate of VI/QL; the empirical speedup is not explained by the proof.
- Relies on the transition matrix structure, hindering extension to general function approximation and continuous state-action spaces.
- Only the synchronous R1-QL is analyzed; asynchronous extension is left open and costs O(nm) per update.
Experimental setup
Datasets: Garnet MDPs Graph MDPs Gridworld
Benchmarks: Garnet MDP (n=200, m=5) Graph MDP Gridworld
Metrics: Bellman error (infinity norm) value error (infinity norm) iterations to error threshold
Baselines: Policy iteration Value iteration Nesterov-VI Anderson-VI Q-learning Speedy Q-learning Zap Q-learning
Builds on: value iteration policy iteration Q-learning Anderson acceleration Nesterov acceleration
Closest papers by meaning
- Sketched Newton Value Iteration for Large-Scale Markov Decision Processes (AAAI 2024 · similarity 0.87)
- Confident Approximate Policy Iteration for Efficient Local Planning in $q^\pi$-realizable MDPs (NeurIPS 2022 · similarity 0.86)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
- Learning and Planning in Average-Reward Markov Decision Processes (ICML 2021 · similarity 0.86)
- Planning and Learning in Average Risk-aware MDPs (NeurIPS 2025 · similarity 0.86)
- Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.