Analysis of Temporal Difference Learning: Linear System Approach

The goal of this technical note is to introduce a new finitetime analysis of tabular temporal difference (TD) learning based on discrete-time stochastic linear system models. TD-learning is a fundamental reinforcement learning (RL) algorithm to evaluate a given policy by estimating the corresponding value function for a Markov decision process. While there has been a series of successful works in theoretical analysis of TD-learning, it was not until recently that researchers found some guarantees on its statistical efficiency by developing finite-time error bounds. In this paper, we propose a unique control theoretic finitetime analysis of tabular TD-learning, which directly exploits discrete-time linear system models and standard notions in control communities. The proposed work provides new simple templates and additional insights for analysis of TD-learning and RL algorithms.