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

arXiv: https://arxiv.org/abs/1906.06781 · HTML: https://mlsanity.com/paper/1906.06781/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2019.

## Built on by (most cited first, 17 of 17)

- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [Global Convergence Using Policy Gradient Methods for Model-free Markovian Jump Linear Quadratic Control](https://mlsanity.com/paper/2111.15228/) (2021)
- [Finite-Time Analysis of Asynchronous Q-learning under Diminishing Step-Size from Control-Theoretic View](https://mlsanity.com/paper/2207.12217/) (2022)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method](https://mlsanity.com/paper/2110.06906/) (2021)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Finite-Time Analysis of Temporal Difference Learning with Experience Replay](https://mlsanity.com/paper/2306.09746/) (2023)
- [Control Theoretic Analysis of Temporal Difference Learning](https://mlsanity.com/paper/2112.14417/) (2021)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)
- [Finite-Time Accuracy of Temporal-Difference Learning Under Schur-Stable Recursions](https://mlsanity.com/paper/2204.10479/) (2022)

## Abstract (arXiv)

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.