Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases
Poster B: Monday -- 16:00 - 18:00
Arsenii Mustafin, Xinyi Sheng, Dominik Baumann
Keywords: Reinforcement Learning Theory, Markov Decision Processes, Algorithm Convergence Analysis
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 $\gamma$, 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.