Research map / Bandits and online learning / RL theory and MDPs
Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward 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.
Gives non-asymptotic rates for relaxed and anchored value iteration on average-reward MDPs, including O(1/k) Bellman-error rates for anchored VI in multichain MDPs and a matching span-based lower bound for weakly communicating and unichain MDPs.
Problem
Convergence rates of value iteration for average-reward MDPs were largely asymptotic and measured in Bellman error; non-asymptotic rates, especially for multichain MDPs, were open.
Approach
Analyzes relaxed VI (convex averaging with the current iterate) and anchored VI (convex averaging with the initial point) for average-reward MDPs, showing anchoring yields O(1/k) Bellman-error rates in multichain MDPs, and proves a span-condition complexity lower bound showing near-optimality (factor 8) for weakly communicating and unichain MDPs.
Key results
- Anchored VI with lambda_k=2/(k+2) achieves Bellman and policy error bounds of 8||V^0-h*||/(k+1) for weakly communicating and unichain MDPs, and bounds of this form with an additional K-dependent term for general multichain MDPs.
- A unichain MDP lower bound shows any span-condition method has Bellman error at least ||V^0-h*||/(k+1), matching the upper bound up to a factor of 8.
- Standard VI's normalized iterates are shown to be exactly optimal for multichain MDPs, with a lower bound of 2||V^0-h*||/(k+1) matching the classical upper bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an anchor at the starting value with λ_k=2/(k+2), rather than relaxed iteration with λ_k=1/2 | Value iteration on average-reward MDPs · MDP (Bellman error; theorem gives a general multichain bound for k>K) | Bellman error: \frac{4\infn{V^0-h^{\star}}}{\sqrt{(3.141592\dots)(k-K)}} -> \frac{8}{k+1}\infn{V^0-h^{\star}} | Helped |
| Use anchored rather than relaxed relative value iteration | Relative value iteration · Weakly communicating MDP | Bellman error: \frac{4}{\sqrt{(3.141592\dots) k}}\infn{h^0-h^{\star}} -> \frac{8}{k+1}\infn{h^0-h^{\star}} | Helped |
| Use standard value iteration with uniform averaging of iterates for the normalized-iterate bound | Value iteration on multichain MDPs · Multichain MDP | Normalized iterate error: \frac{2}{k}\infn{V^0-h^{\star}}; lower bound: \frac{2}{k+1}\infn{V^0-h^{\star}} | No clear effect |
Surprising findings
- Standard VI's normalized iterates attain the exactly matching lower bound in multichain MDPs, and the Bellman error (not just policy error) bounds the policy error after a finite threshold K even in multichain MDPs.
Limitations
- Multichain Bellman-error upper bound has a K-dependent term not matching the lower bound.
- Lower bound holds only for methods satisfying the span condition.
- Purely theoretical; no experiments.
Experimental setup
Metrics: bellman error policy error normalized iterate error span seminorm
Baselines: standard value iteration relative value iteration Halpern iteration
Builds on: Krasnoselskii-Mann iteration Halpern iteration relative value iteration value iteration
Closest papers by meaning
- Faster Fixed-Point Methods for Multichain MDPs (NeurIPS 2025 · similarity 0.92)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.90)
- Finite-Time Bounds for Average-Reward Fitted Q-Iteration (NeurIPS 2025 · similarity 0.90)
- Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.89)
- A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs (ICML 2025 · similarity 0.89)
- Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret (NeurIPS 2026 · similarity 0.88)
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.