Dynamics of Temporal Difference Learning

Andreas WendemuthIJCAI 2007

Abstract

This paper provides a rigorous mathematical foundation for the dynamics of Temporal Difference (TD) learning, specifically the Sutton-Barto rule used in Pavlovian conditioning models. By reformulating the update rule as a discrete-time linear dynamical system, the author derives a closed-form formula for reward prediction over successive trials. Using the properties of Toeplitz matrices, the study proves that these predictions are guaranteed to converge to the true rewards and identifies a mathematically optimal learning rate for the fastest possible convergence.

Introduction

Temporal Difference (TD) learning is a cornerstone of reinforcement learning and computational neuroscience, famously used to model how dopamine neurons in the brain predict rewards. While the Sutton-Barto rule is widely accepted, much of the existing literature treats its convergence stochastically or through general approximations. This paper addresses the gap in providing a direct, constructive proof of convergence for specific stimulus-reward patterns. By analyzing trial-by-trial dynamics as a linear system, the research moves beyond heuristic choices for the learning rate ($\epsilon$) to a formal optimization framework.

Methods and Mathematical Framework

The core of the analysis involves reformulating the standard TD update rule into a discrete-time linear dynamical system. The prediction updates are represented as a recursive matrix equation:

$$v^{n+1} = (\mathbf{E} - \epsilon \mathbf{GA})v^n + \epsilon \mathbf{Gr}$$

where $v^n$ is the prediction at trial $n$, $\mathbf{G}$ is the stimulus correlation matrix, and $\mathbf{A}$ is the temporal difference operator.

Stability Analysis

To prove convergence, the author demonstrates that the matrix $(-\mathbf{GA})$ is a Hurwitz matrix, meaning all its eigenvalues have negative real parts. This property ensures that the prediction error decays toward zero as the number of trials ($n$) increases. The proof hinges on showing that if $\mathbf{G}$ is positive definite and $(\mathbf{A}^T + \mathbf{A})$ is positive definite, the whole system is guaranteed to converge.

Toeplitz Matrix Theory

The stimulus correlations are represented using Toeplitz matrices. The paper proves a significant general property: symmetric Toeplitz matrices formed from correlation entries are positive definite. This mathematical result is crucial for ensuring the stability of the learning system.

Optimization of the Learning Rate

A key contribution of this work is the identification of the optimal learning rate $\epsilon^*$. The author proposes a line-search algorithm to find $\epsilon^*$ by minimizing the maximum modulus of the system's eigenvalues.

Optimization of the learning rate $\epsilon$ by minimizing the maximum modulus $m(\epsilon)$ of the system's eigenvalues.
A second example showing how different stimulus configurations shift the optimal learning rate.

As shown in the figures, the "speed" of learning is dictated by the eigenvalues of the matrix $\mathbf{GA}$. In these examples, the optimal learning rate achieves a significantly lower maximum modulus (approximately 0.96), which translates to faster error reduction per trial compared to non-optimal settings.

Key Results

  • Closed-Form Expression: The paper provides an explicit formula for the prediction $v^n(t)$ at any trial $n$, showing it converges to the total remaining reward $R(t)$ as $n \to \infty$.
  • Finite Convergence: In the special case of a single stimulus, the system can reach total convergence in exactly $T$ steps (the duration of a trial) with a perfectly tuned learning rate.
  • Mathematical Proof: A formal proof that symmetric Toeplitz matrices with correlation entries are positive definite, contributing to linear algebra independently of TD learning.

Limitations and Future Work

The current proof assumes that stimuli and rewards do not overlap in time ($t_{r,min} > t_{u,max}$), a common but not universal condition in Pavlovian experiments. Furthermore, the focus is on TD(0); extending this constructive proof to TD($\lambda$)—which includes exponential weighting for past events—remains a direction for future research. Finally, for complex stimuli where the matrix $\mathbf{G}$ has many bands, numerical methods are required as closed-form solutions for such Toeplitz matrices are generally unavailable.

Summary updated

BibTeX
@inproceedings{wendemuth2007dynamics,
  author = {Andreas Wendemuth},
  title = {{Dynamics of Temporal Difference Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure