Regularization and Two Time Scales for Convergence of Reinforcement Learning

Abstract Reinforcement learning algorithms aim at solving discrete time stochastic control problems with unknown underlying dynamical systems by an iterative process of interaction. The process is formalized as a Markov decision process, where at each time step, a control action is given, the system provides a reward, and the state changes stochastically. The objective of the controller is the expected sum of rewards obtained throughout the interaction. When the set of states and or actions is large, it is necessary to use some form of function approximation. But even if the function approximation set is simply a linear span of fixed features, the reinforcement learning algorithms may diverge. In this work, we propose and analyze regularized two-time-scale variations of the algorithms, and prove that they are guaranteed to converge almost-surely to a unique solution to the reinforcement learning problem.