Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward MDPs
Jongmin Lee, Ernest K. Ryu · 2025
Read Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward MDPs by Jongmin Lee, Ernest K. Ryu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09913.txt.
Description
Jongmin Lee and Ernest K Ryu sharpen the theory of a classic learning algorithm for long-run average rewards, in a 2025 paper. Value iteration updates value guesses step by step. Most past theory covers the discounted case, where near rewards count more, while the average case had only loose bounds.
The authors give fresh finite-step bounds for the average-reward case. A fixed-up form of the algorithm shrinks error at a steady one-over-steps rate in the general multi-chain setup. They also prove a matching lower bound, tight up to a small constant factor, for simpler setups. The pair of results closes much of the gap in knowing how fast the method settles. Code-free proofs anchor the claims.
Catalog record
| CREATOR | Jongmin Lee, Ernest K. Ryu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 127 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-09913