Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
This work addresses a gap in reinforcement learning theory for average reward settings, offering incremental theoretical advancements with specific applications.
The paper tackles the problem of analyzing stochastic approximation algorithms with nonexpansive operators under Markovian noise, which is not covered by prior contractive operator analyses, and provides both asymptotic and finite sample analysis, including proving convergence of tabular average reward temporal difference learning to a sample-path dependent fixed point for the first time.
Stochastic approximation is a powerful class of algorithms with celebrated success. However, a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings like the average reward setting. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are novel bounds of noise terms resulting from the Poisson equation. As an application, we prove for the first time that classical tabular average reward temporal difference learning converges to a sample-path dependent fixed point.