Research map / Learning theory and algorithms / Sample complexity
Accelerating Value Iteration with Anchoring
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add an anchor toward the initial iterate | Value Iteration with Bellman consistency or optimality operators · Bellman error, γ approximately 1 | Bellman error rate: Anc-VI: \mathcal{O}(1/k); standard VI: \mathcal{O}(1) | Helped |
| Add an anchor toward the initial iterate | Value Iteration with Bellman consistency or optimality operators · Bellman error, γ = 1 | Bellman error rate: \frac{1}{k+1} | Helped |
| Use the anchored update for Bellman optimality rather than only Bellman consistency | Anc-VI · Bellman optimality operator | Bellman error rate: \mathcal{O}(1/k) versus standard VI's \mathcal{O}(1) | Helped |
| Use the anchored update for approximate Bellman evaluations | Approximate Anc-VI · Bellman error with evaluation errors | Dependence on evaluation error: no worse than that of Approximate VI | No clear effect |
| Combine anchoring with Gauss–Seidel updates | Gauss–Seidel VI · Finite state-action spaces | Bellman error rate: \mathcal{O}(1/k) when γ \approx 1 | Helped |
| Measure performance by distance to solution instead of Bellman error | Anc-VI versus standard VI · Discounted Bellman operators, γ < 1 | Distance to solution: This \mathcal{O}(\gamma^k) rate is worse than the rate of (classical) VI by a constant factor. | Hurt |
| Use the full anchored method under the span condition | Anc-VI · Worst-case Bellman error | Bellman error lower-bound comparison: up to a constant of factor 4 | Helped |
Closest papers by meaning
- Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases (NeurIPS 2026 · similarity 0.88)
- Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.87)
- Parameterized Projected Bellman Operator (AAAI 2024 · similarity 0.87)
- Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework (NeurIPS 2026 · similarity 0.86)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.85)
- Accelerated Policy Gradient: On the Convergence Rates of the Nesterov Momentum for Reinforcement Learning (ICML 2024 · 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.