Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning
It provides incremental theoretical foundations for reinforcement learning methods, addressing stability issues in asynchronous settings.
The paper tackles the stability and convergence of asynchronous stochastic approximation algorithms, extending theoretical guarantees to broader noise conditions and analyzing shadowing properties, with applications to average-reeward reinforcement learning algorithms.
This paper investigates the stability and convergence properties of asynchronous stochastic approximation (SA) algorithms, with a focus on extensions relevant to average-reward reinforcement learning. We first extend a stability proof method of Borkar and Meyn to accommodate more general noise conditions than previously considered, thereby yielding broader convergence guarantees for asynchronous SA. To sharpen the convergence analysis, we further examine the shadowing properties of asynchronous SA, building on a dynamical systems approach of Hirsch and Benaïm. These results provide a theoretical foundation for a class of relative value iteration-based reinforcement learning algorithms -- developed and analyzed in a companion paper -- for solving average-reward Markov and semi-Markov decision processes.