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

Jongmin Lee, Ernest K. Ryu

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-re…