On the role of overparameterization in off-policy Temporal Difference learning with linear function approximation

Valentin ThomasNeurIPS 2022 · OpenReview

Introduction

In supervised learning, the phenomenon of "double descent" has reshaped our understanding of model capacity: as models become vastly overparameterized, their performance often improves even after perfectly fitting the training data. However, Reinforcement Learning (RL) presents a uniquely hostile environment for this dynamic. RL agents face the "deadly triad"—the dangerous combination of off-policy learning, function approximation, and bootstrapping—which can cause training to become highly unstable or diverge entirely.

While predictive theories for overparameterization are well-established in supervised tasks, the RL setting has remained largely a black box. This paper takes a theoretical approach to open that box, investigating how the number of parameters ($p$) relative to the number of states ($n$) affects the stability and convergence of Temporal Difference (TD) learning with linear function approximation.

Methodology: A Theoretical Lens

To dissect the optimization dynamics of TD learning, the author leverages two powerful mathematical frameworks:

  1. Random Matrix Theory (RMT): The study utilizes Wishart matrices and the Marchenko-Pastur distribution to model the random features used by the RL agent.
  2. Random Graph Theory: To model the environment's transition dynamics ($P^\pi$), the author introduces a class of "asymptotically well-connected" random graphs.

By combining these tools, the paper derives a precise analytical characterization of the spectrum (eigenvalues) of the TD operator. Because the eigenvalues of this operator dictate whether the learning process converges or explodes, this spectral characterization allows for direct predictions about the agent's optimization dynamics. The theoretical predictions are then validated against synthetic random features and small Gridworld Markov Decision Processes (MDPs), such as the standard "4 rooms" domain.

Key Insights

The "Spiked" Spectrum

A central finding of the paper is that the TD operator's spectrum follows a "spiked" Marchenko-Pastur distribution. The eigenvalues form a main "bulk," but a specific "spiked" eigenvalue separates from the rest. This isolated spike is the primary governor of the algorithm's stability.

Density of eigenvalues showing the 'spiked' Marchenko-Pastur distribution.

The RL-Specific Peak and Double Descent

The paper confirms that Mean Square Bellman Error (MSBE) exhibits a double descent curve in RL. However, unlike supervised learning—where error typically drops smoothly after the interpolation threshold ($p=n$)—RL exhibits a unique and dangerous "peaking behavior." The residual error contains a term that can blow up near the threshold, especially when the discount factor ($\gamma$) is high, due to the bootstrapping nature of TD learning.

Bellman error exhibiting a pronounced 'double descent' peak at the interpolation threshold.

Non-stationarity as a Divergence Trigger

In RL, the policy changes over time, inherently altering the distribution of visited states. The paper proves that if the number of visited states drops too low relative to the number of parameters, a previously stable step size can suddenly cause the model to diverge. This highlights a critical vulnerability in off-policy learning.

Vast Overparameterization Mimics Tabular RL

Interestingly, the paper suggests that when models are vastly overparameterized ($p \gg n$), the optimization dynamics of linear function approximation begin to behave similarly to "tabular" RL, where every state is tracked individually. This provides a compelling theoretical justification for why massive models are often easier to tune and stabilize.

Key Results and Limitations

The theoretical framework yields highly accurate analytical predictions. The derived formulas for the largest and smallest eigenvalues of the TD operator match empirical results on the 4-rooms gridworld with relative errors as low as 0.3%. Furthermore, the author derives explicit stability bounds, defining the minimum number of states an agent must visit to remain stable given a fixed step size and parameter count.

Limitations and Future Directions: While groundbreaking, the analysis is currently restricted to linear function approximation with random features. This serves as an excellent theoretical sandbox but does not fully capture the complexities of deep neural networks where features are actively learned. Additionally, the random graph model assumes "well-connected" environments, which may not hold for real-world tasks with severe bottlenecks or sparse rewards.

Future work aims to extend these findings to the Neural Tangent Kernel (NTK) regime, bridging the gap between linear models and deep RL, and exploring how these spectral properties evolve during active policy optimization.

Summary updated

Abstract

Much of the recent successes of deep learning can be attributed to scaling up the size of the networks to the point where they often are vastly overparameterized. Thus, understanding the role of overparameterization is of increasing importance. While predictive theories have been developed for supervised learning, little is known about the Reinforcement Learning case. In this work, we take a theoretical approach and study the role of overparameterization for off-policy Temporal Difference (TD) learning in the linear setting. We leverage tools from Random Matrix Theory and random graph theory to obtain a characterization of the spectrum of the TD operator. We use this result to study the stability and optimization dynamics of TD learning as a function of the number of parameters.
BibTeX
@inproceedings{thomas2022role,
  author = {Valentin Thomas},
  title = {{On the role of overparameterization in off-policy Temporal Difference learning with linear function approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=g-H3oNARs2},
}
Figure