While most Reinforcement Learning (RL) theory focuses on whether an algorithm will eventually converge, understanding how it gets there is equally crucial. This paper provides the mathematical tools to derive analytical expressions for the bias and variance of Temporal Difference (TD) learning. By doing so, the authors allow researchers to plot exact learning curves and optimize parameters like step-size ($\alpha$) and eligibility traces ($\lambda$) without needing millions of slow, noisy simulations.
The Problem: Finite-Term Behavior in RL
In the mid-90s, the RL community had a solid grasp of asymptotic convergence—the "infinite time" behavior of algorithms. However, there was a distinct lack of formal theory for "finite-term" behavior: the learning curve itself.
When training an agent, researchers need to know how fast it will learn and which parameters will minimize error early on. Traditionally, answering these questions required running thousands of empirical simulations and averaging the results to get a "smooth" curve. This approach is computationally expensive and often misleading due to the high variance inherent in stochastic environments. Singh and Dayan sought to replace these noisy empirical plots with exact, deterministic equations.
Methodology: Analytical MSE Curves
The authors focus on absorbing Markov chains (tasks with a clear beginning and end) using lookup table representations. Their primary contribution is the derivation of recursive update equations for the two components of Mean Squared Error (MSE):
- Bias ($b$): The difference between the expected estimate and the true value.
- Variance ($C$): The "spread" or noise in the estimates.
They demonstrate that both bias and covariance can be updated trial-by-trial using matrix algebra. Specifically, the bias at trial $t$ is a linear function of the bias at $t-1$, and the covariance is a function of the previous covariance and bias.
With these formulas, they developed a method to:
- Calculate exact MSE curves in $O(|states|^3 \times Trials)$ time.
- Compute "Greedy" Parameters: Mathematically determine the optimal step-size ($\alpha$) or eligibility trace ($\lambda$) that minimizes error for the very next step.
- Perform Stability Analysis: Use eigenvalues to find the maximum possible learning rate before the algorithm diverges.
Key Insights and Results
The "Long Tail" Trap
Empirical simulations are often "spiky" and unreliable. The authors found that the distribution of MSE can have extremely long tails, representing rare but massive errors. In one case, an empirical curve failed to match the true analytical curve even after 15 million runs. This highlights exactly why analytical solutions are superior to simulation for theoretical work.
The $\lambda$ Trade-off and Optimal Schedules
The parameter $\lambda$ (eligibility traces) acts as a bridge between TD learning ($\lambda=0$) and Monte Carlo methods ($\lambda=1$). The paper confirms that $\lambda < 1$ is usually superior because it balances the low variance of TD with the low bias of Monte Carlo.
Furthermore, the authors demonstrated that the "optimal" $\lambda$ is not a single static number but a schedule that should change over time. If initial guesses are very wrong (high initial bias), it is best to start with a high $\lambda$. As the bias drops, $\lambda$ should be decreased to reduce variance.
Stability Limits and TD Superiority
Counter-intuitively, decreasing $\lambda$ can actually shrink the range of stable step-sizes ($\alpha$). This happens because lower $\lambda$ values can lead to high correlations between the value estimates of neighboring states, potentially causing "runaway" variance. Despite this, eigenvalue analysis showed that the fastest possible rate of bias reduction is achieved when $\lambda < 1$, providing a theoretical "win" for Temporal Difference learning over pure Monte Carlo methods.
Limitations and Future Work
While groundbreaking for its time, the paper's scope has specific boundaries:
- Lookup Tables Only: The derivations assume a lookup table where every state is tracked individually. Modern RL heavily relies on function approximation (like Neural Networks), which this framework does not cover.
- Offline Updates: The mathematics assume weights are updated only at the end of a trial, rather than at every single step (online updates).
- Prediction vs. Control: The paper focuses on evaluating a fixed policy (prediction) rather than finding an optimal policy (control/Q-learning).
Because the results depend on the specific structure of the Markov chain, the authors note it is difficult to formulate universal "laws" applicable to every environment. They suggest future work should investigate "large deviation rates" to better understand the extreme variance observed in their simulations.
Summary updated