Research map / Reinforcement learning / MDPs and planning
Sketched Newton Value Iteration for Large-Scale Markov Decision Processes
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 Newton Value Iteration (NVI) on a smoothed (log-sum-exp) Bellman operator and a sketched variant (SNVI) that reduces the Newton linear-system cost from O(|S|^3) to O(k^3) for solving large-scale MDPs with full model information.
Problem
Value iteration is a first-order method that needs many iterations to converge on MDPs, while Newton-type second-order methods are computationally too expensive for large state and action spaces.
Approach
Apply Newton-Raphson to a smooth log-sum-exp Bellman operator on the V-function (instead of the Q-function) so the Jacobian is |S|x|S| and action dimension drops out, then sketch the Newton system with random sketching matrices computed via Jacobian-vector products to reduce cost further.
Key results
- NVI consistently outperforms G-SOVI and VI on 12 Garnet MDP instances, with the running-time gap to G-SOVI growing as action dimension increases.
- SNVI shows faster convergence than NVI with an appropriate sketch size on Forest MDP instances, and both NVI and SNVI converge much faster than VI.
- NVI is proven to converge globally with quadratic rate; SNVI has a sublinear convergence guarantee under star-convexity-type assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply Newton-Raphson to the smooth V-Bellman operator instead of the smooth Q-Bellman operator | G-SOVI · MDPs | computational complexity: O(|S|3|A|3) to O(|S|3) | Helped |
| use a sketch of size k to reduce the Newton system dimension | NVI · MDPs | computational complexity for solving linear systems: O(|S|3) to O(k3) | Helped |
| use NVI instead of VI | MDPs with large action spaces · Garnet MDPs | running time to convergence | Helped |
| use SNVI instead of VI | Forest MDPs · Forest MDPs | running time to convergence | Helped |
| use SNVI with an appropriate sketch size instead of NVI | NVI · Forest MDPs | running time to convergence | Helped |
| use SNVI instead of VI | MDPs · MDPs | convergence rate | Hurt |
Surprising findings
- NVI's Newton update is independent of the successive relaxation parameter w, since w cancels on both sides of the linear system.
Limitations
- SNVI's theoretical convergence is only sublinear, slower than VI's linear rate in theory.
- Key assumptions (star-convexity of the sketched objective) are not derived theoretically and only verified empirically.
- Experiments are on small synthetic MDPs run on a laptop CPU, with softmax parameter increased gradually for stability.
Experimental setup
Datasets: Garnet MDPs Forest MDP Machine Replacement MDP
Benchmarks: Garnet MDPs Forest MDP Machine Replacement MDP
Metrics: running time to reach error threshold sup-norm error to optimal value
Baselines: Value Iteration G-SOVI NVI
Builds on: G-SOVI Sketched Newton-Raphson Sketch-and-project Newton (Gower et al. 2019) Successive relaxation Bellman operator (Reetz 1973) Garnet MDPs
Closest papers by meaning
- Faster Fixed-Point Methods for Multichain MDPs (NeurIPS 2025 · similarity 0.87)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.87)
- Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases (NeurIPS 2026 · similarity 0.87)
- Rank-One Modified Value Iteration (ICML 2025 · similarity 0.87)
- A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs (ICML 2025 · similarity 0.87)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.86)
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.