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