Stochastic approximation in a Markovian framework revisited: Lipschitz continuity of the Poisson equation

Abstract In this paper, we revisit a fundamental technical issue within the theory of stochastic approximation (SA) in a Markovian framework, first proposed in the book by Derevitskii and Fradkov (Applied theory of discrete adaptive control systems, Nauka, 1981), and further developed in much detail in the book by Benveniste, Métivier, and Priouret (Adaptive algorithms and stochastic approximations, Springer, Berlin, 1990). This theory is instrumental in many application areas such as the statistical analysis of Hidden Markov Models arising in telecommunication, quantized linear stochastic systems, and reinforcement learning. The problem at hand is the verification of the existence, uniqueness, and Lipschitz continuity of the solution of a parameter-dependent Poisson equation, in an appropriate weighted sup-norm, associated with a collection of Markov chains on general state spaces. Verification of the above facts is vital in the analysis of SA processes presented in the cited book via the ODE (ordinary differential equations) method, requiring substantial technical effort. The motivation and focus of the paper is to address this technical issue, by presenting a simple set of conditions, under which the above properties of the Poisson equation at hand can be conveniently established. A distinctive feature of our work is that it is based on a remarkable result of Hairer and Mattingly (2011), proving that by tilting standard conditions of mainstream stability theory for Markov chains, the transition kernels prove to be contractions in the space of differences of probability measures in a suitable metric. To demonstrate the applicability of our results, the proposed conditions are verified for a class of queuing system with open-loop control.