# Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2025.

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

- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotients](https://mlsanity.com/paper/2602.00474/) (2026)

## Abstract (arXiv)

While there is an extensive body of research on the analysis of Value Iteration (VI) for discounted cumulative-reward MDPs, prior work on analyzing VI for (undiscounted) average-reward MDPs has been limited, and most prior results focus on asymptotic rates in terms of Bellman error. In this work, we conduct refined non-asymptotic analyses of average-reward MDPs, obtaining a collection of convergence results that advance our understanding of the setup. Among our new results, most notable are the O(1/k)-rates of Anchored Value Iteration on the Bellman error under the multichain setup and the span-based complexity lower bound that matches the O(1/k) upper bound up to a constant factor of 8 in the weakly communicating and unichain setups