A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms
This work provides a foundational theoretical framework for analyzing RL algorithms, which is incremental as it builds on existing methods but offers new insights into convergence properties.
The paper tackles the theoretical analysis of reinforcement learning algorithms with constant step-sizes by introducing a distributional approach, resulting in unified proofs of convergence for methods like TD(λ) and Q-Learning, showing exponentially fast convergence to a stationary distribution with mean equal to the true value function.
We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We demonstrate its effectiveness by presenting simple and unified proofs of convergence for a variety of commonly-used methods. We show that value-based methods such as TD($λ$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions, thus establishing their exponentially fast convergence to a stationary distribution. We demonstrate that the stationary distribution obtained by any algorithm whose target is an expected Bellman update has a mean which is equal to the true value function. Furthermore, we establish that the distributions concentrate around their mean as the step-size shrinks. We further analyse the optimistic policy iteration algorithm, for which the contraction property does not hold, and formulate a probabilistic policy improvement property which entails the convergence of the algorithm.