Towards a Better Understanding of Representation Dynamics under TD-learning

Yunhao Tang, Rémi Munos

Introduction

Temporal Difference (TD) learning is a cornerstone of modern reinforcement learning (RL), enabling agents to predict future rewards by bootstrapping from existing estimates. In deep RL, this process is typically "end-to-end," meaning the agent simultaneously learns a state representation (features) and a value function (weights) from raw input. While this approach has driven major successes like DQN, the mathematical understanding of how TD updates shape internal representations has remained elusive. This paper investigates the "representation dynamics" of TD-learning to determine if these joint updates consistently improve value predictions and what specific environmental structures they capture.

Theoretical Framework

The researchers analyze a bi-linear approximation of TD-learning, where the value function is defined as $V = \Phi w$ (with $\Phi$ representing the feature matrix and $w$ the weight vector). To study the evolution of these components, they employ Ordinary Differential Equations (ODEs) to model continuous-time updates.

A critical aspect of their analysis is the two-time-scale regime, a theoretical proxy for deep learning where the weights ($w$) are updated much faster than the representations ($\Phi$). This allows the researchers to isolate how the representation evolves as it attempts to support the most accurate possible value predictions.

Key Theoretical Insights

TD as Gradient Descent

The authors prove that in "reversible" environments—where the flow between states is balanced—end-to-end TD-learning is mathematically equivalent to performing gradient descent on the value approximation error. This provides a formal guarantee that joint updates move the system toward better predictions rather than causing instability. Furthermore, they identify a "non-collapse" property: under two-time-scale dynamics, the representation matrix $\Phi$ undergoes rotations rather than shrinking, preventing the common failure mode where features become identical and lose information.

Spectral Decomposition and Random Rewards

One of the paper's most significant findings is the connection between TD-learning and the spectral properties of the environment's transition matrix. The authors demonstrate that fitting value functions for multiple randomly generated rewards forces the representation to perform a spectral decomposition of the transition matrix. Essentially, by attempting to predict "noise" across time, the agent is forced to learn the fundamental structural features of how states transition to one another. As the number of these random reward signals ($h$) increases, the learned features converge toward the top eigenvectors of the environment.

Empirical Validation

Tabular MDPs

Using randomly generated Markov Decision Processes (MDPs) with 30 states, the authors verified that the weighted value error consistently decays over time, even when the strict mathematical assumption of reversibility is violated. They also confirmed that as the number of random reward tasks increases, the representation captures the environment's transition dynamics with near-optimal precision.

Atari 2600 Benchmarks

To test these ideas in a deep learning context, the researchers introduced a "Random Reward Auxiliary Task" to a standard DQN agent across 15 classic Atari games. The results showed that the agent using random rewards outperformed both the baseline DQN and a version of DQN with a specifically tuned learning rate. This suggests that the performance boost is a direct result of superior representation learning rather than mere optimization improvements.

Conclusion and Future Work

This work provides a rigorous foundation for understanding how TD-learning shapes representations. By showing that TD-learning naturally acts as a spectral decomposer—especially when paired with random reward prediction—the authors offer a new perspective on why auxiliary tasks are so effective in deep RL.

While the current analysis focuses on linear parameterization and policy evaluation, it sets the stage for future research into non-linear architectures (like ReLU networks) and the more complex dynamics of "control," where the agent's policy changes alongside its representation.

Summary updated

Abstract

TD-learning is a foundation reinforcement learning (RL) algorithm for value prediction. Critical to the accuracy of value predictions is the quality of state representations. In this work, we consider the question: how does end-to-end TD-learning impact the representation over time? Complementary to prior work, we provide a set of analysis that sheds further light on the representation dynamics under TD-learning. We first show that when the environments are reversible, end-to-end TD-learning strictly decreases the value approximation error over time. Under further assumptions on the environments, we can connect the representation dynamics with spectral decomposition over the transition matrix. This latter finding establishes fitting multiple value functions from randomly generated rewards as a useful auxiliary task for representation learning, as we empirically validate on both tabular and Atari game suites.
BibTeX
@inproceedings{tang2023towards,
  author = {Yunhao Tang and Rémi Munos},
  title = {{Towards a Better Understanding of Representation Dynamics under TD-learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=6iUsPMrQDE},
}
Figure