Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory

Abstract

In this paper, we provide a unified analysis of temporal difference learning algorithms with linear function approximators by exploiting their connections to Markov jump linear systems (MJLS). We tailor the MJLS theory developed in the control community to characterize the exact behaviors of the first and second order moments of a large family of temporal difference learning algorithms. For both the IID and Markov noise cases, we show that the evolution of some augmented versions of the mean and covariance matrix of the TD estimation error exactly follows the trajectory of a deterministic linear time-invariant (LTI) dynamical system. Applying the well-known LTI system theory, we obtain closed-form expressions for the mean and covariance matrix of the TD estimation error at any time step. We provide a tight matrix spectral radius condition to guarantee the convergence of the covariance matrix of the TD estimation error, and perform a perturbation analysis to characterize the dependence of the TD behaviors on learning rate. For the IID case, we provide an exact formula characterizing how the mean and covariance matrix of the TD estimation error converge to the steady state values. For the Markov case, we use our formulas to explain how the behaviors of TD learning algorithms are affected by learning rate and the underlying Markov chain. For both cases, upper and lower bounds for the mean square TD error are provided. The mean square TD error is shown to converge linearly to an exact limit.

arXiv commentTo appear in NeurIPS 2019

References in corpus (11)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• Dissipativity Theory for Nesterov's Accelerated Method
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Target-Based Temporal Difference Learning
• Systematic Design of Decentralized Algorithms for Consensus Optimization

Cited by in corpus (12)

• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• The Mean-Squared Error of Double Q-Learning
• Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control