A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms

Abstract

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($\lambda$) 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.

arXiv commentAISTATS 2020

References in corpus (6)

• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• A Comparative Analysis of Expected and Distributional Reinforcement Learning
• Free complete Wasserstein algebras
• Linear Stochastic Approximation: Constant Step-Size and Iterate Averaging

Cited by in corpus (1)

• A Study of Policy Gradient on a Class of Exactly Solvable Models