Research map / Reinforcement learning / Policy gradient and actor-critic

Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases

NeurIPS 2026 · Reinforcement learning › Policy gradient and actor-critic · approach: Temporal-difference and discounting theory

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.

Shows via a unified geometric (action-space) analysis that, under a unique unichain optimal policy, value iteration converges geometrically in span seminorm in both discounted and average-reward MDPs, faster than prior analyses suggested.

Problem

Value iteration's theoretical convergence guarantees mismatch empirical behavior: discounted theory gives rate gamma, while average-reward theory suggests only sublinear convergence.

Approach

Reinterprets values on the outer vertical lines of the geometric action-space picture with a new MDP-constant-normalized value vector, making discounted and average-reward VI share the same dynamics, then proves a span-seminorm contraction over n^2 steps.

Key results

• Theorem: after T=n^2 steps the normalized span satisfies span(v_T) <= gamma^T * iota * span(v_0) with iota in (0,1), giving geometric convergence in both discounted and average-reward cases.
• Discounted iteration complexity O((log(1/eps)+log(1/(1-gamma)))/(log(1/gamma)+log(1/iota)/n^2)) improves on the gamma-rate.
• Average-reward complexity O(log(1/eps)/(log(1/iota)/n^2)) gives geometric rate, contradicting prior sublinear lower-bound claims under the stated assumption.

Surprising findings

• Average-reward VI converges geometrically under a unique unichain optimal policy, contrary to the sublinear optimality suggested by prior lower bounds.
• The prior sublinear lower bound is reconciled by its use of l-infinity norm and iteration counts below n-2, not by a technical error.

Limitations

• Requires a unique optimal policy that is unichain (Assumption).
• Multichain case with isolated classes is not covered and left to future work.
• Iota constant is not explicitly quantified; rate depends on n^2 window and the minimal nonzero transition probability.

Experimental setup

Metrics: normalized span seminorm of error vs iteration

Baselines: classical discounted VI analysis (rate gamma) lower bound of prior average-reward VI analysis

Builds on: geometric interpretation of MDPs relative value iteration Bellman-style lower bound analysis of value iteration (Theorem 3 from prior work

Closest papers by meaning

• Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.88)
• A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs (ICML 2025 · similarity 0.88)
• A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning (NeurIPS 2026 · similarity 0.87)
• Sketched Newton Value Iteration for Large-Scale Markov Decision Processes (AAAI 2024 · similarity 0.87)
• On the Convergence of Success Conditioning for Policy Optimization (NeurIPS 2026 · similarity 0.87)
• A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.87)