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

arXiv: https://arxiv.org/abs/2510.23914 · HTML: https://mlsanity.com/paper/2510.23914/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 27 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 5 of 5)

- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Average-Reward Soft Actor-Critic](https://mlsanity.com/paper/2501.09080/) (2025)
- [The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming](https://mlsanity.com/paper/1312.6832/) (2013)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [Logarithmic Regret of Exploration in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2502.06480/) (2025)

## Built on by (most cited first, 1 of 1)

- [Ergodicity in reinforcement learning](https://mlsanity.com/paper/2603.10895/) (2026)

## Abstract (arXiv)

While Value Iteration (VI) is one of the most fundamental algorithms in Reinforcement Learning, its theoretical convergence guarantees still exhibit a persistent mismatch with empirical behavior. In the discounted-reward case, classical theory guarantees geometric convergence with rate γ, while in the average-reward case recent work suggests that only sublinear convergence can be expected. In practice, however, VI is often observed to converge significantly faster. In this work, we show through a unified geometry-based analysis that, under an assumption of a unique and unichain optimal policy, (i) convergence is geometric in both the discounted- and average-reward settings and (ii) the convergence rate is faster than previous analyses suggest.