​​​ 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

CREATORJongmin Lee, Ernest K. Ryu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-09913

Browse the full library · About the Tower of Babel