Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning

TD learning is the most widely studied algorithm for evaluating the performance of a given policy from data in Markov Decision Processes[1]. The convergence of TD learning with decaying stepsizes was proved in [2]. Over the last few years, there has been a resurgent interest in understanding the non-asymptotic convergence behavior of TD learning and further using it to study other other reinforcement algorithms which use TD learning within their framework. The first result of this type was obtained in [3] who used a projection step in their version of the TD learning algorithm. The first finite-time bounds for unprojected TD learning were obtained in [4], who studied both fixed step-sizes and decaying step-sizes.