A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation: Mean-Square Convergence Bounds for Contractive SA under Markovian and Martingale NoiseResearch Paper
Many reinforcement-learning algorithms are instances of one recursion: stochastic approximation (SA) for a fixed-point equation , where the operator is only observed through samples drawn along a Markov chain. Asynchronous Q-learning, off-policy V-trace, -step TD and TD() all fit this template, and in each the expected operator is a…