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.
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