Introduction
Contrastive self-supervised learning has emerged as a cornerstone of sample-efficient Deep Reinforcement Learning (RL). By training agents to distinguish between related and unrelated state-action pairs, researchers have successfully enabled agents to learn complex representations from high-dimensional inputs like raw pixels. However, despite the empirical success of these methods, a significant theoretical gap has persisted: we have lacked a formal understanding of why contrastive learning works in online RL settings and how it can be rigorously integrated with principled exploration.
This paper introduces Contrastive UCB, the first algorithm to provide theoretical guarantees for online RL using contrastive representation learning. The framework demonstrates how agents can discover environment structures and achieve optimal performance in both single-agent and competitive multi-agent environments.
The Problem: Bridging Representation and Exploration
Deep RL agents often require millions of environment interactions to learn effective policies, a limitation that renders them impractical for real-world applications like autonomous driving or healthcare. While contrastive learning—where an agent learns to identify "positive" transitions versus "negative" noise—has improved efficiency in practice, two primary challenges remained:
- The Theory Gap: There was no formal proof that contrastive objectives could recover the true underlying features of an environment during online interaction.
- The Exploration Gap: It was unclear how to combine learned representations with Upper Confidence Bound (UCB) strategies, which require a measure of uncertainty to incentivize the exploration of unknown states.
The Contrastive UCB Framework
The authors address these gaps by focusing on Low-Rank Markov Decision Processes (MDPs) and Markov Games (MGs). In these models, complex transition dynamics are governed by a low-dimensional set of latent features. The Contrastive UCB framework operates through a four-step cycle:
1. Contrastive Representation Learning
As the agent interacts with the environment, it minimizes a temporal contrastive loss. The objective is to assign high probability to actual transitions $(s, a \to s')$ and low probability to fake transitions $(s, a \to s_{noise})$. This process allows the agent to "discover" the hidden features of the environment without prior knowledge.
2. Feature Extraction
From the minimized loss, the agent extracts learned feature maps (denoted as $\phi$ and $\psi$). The authors provide a mathematical proof that these maps eventually converge to the true underlying transition dynamics of the low-rank MDP.
3. Principled Exploration
Rather than using these features solely for value estimation, the agent utilizes them to construct a UCB bonus. This bonus is proportional to the agent's uncertainty within the learned feature space. By doing so, the agent is incentivized to visit state-action pairs that it has not yet represented accurately.
4. Extension to Competitive Games
For two-player zero-sum games, the framework employs ULCB (Upper and Lower Confidence Bounds). This allows the agent to maintain optimism for itself and pessimism regarding its opponent, facilitating the discovery of a Nash Equilibrium in complex competitive settings.
Key Theoretical Insights
The paper’s core contribution is the proof that a simple temporal contrastive objective is sufficient to recover the transition kernel of a low-rank MDP.
- Near-Optimism: In traditional RL theory, features are often assumed to be known. In this framework, features are learned, which introduces a temporary bias in the UCB bonus. The authors demonstrate that this bias decays at a rate of $1/\sqrt{k}$, meaning the agent remains "near-optimistic" and is guaranteed to converge to the optimal policy.
- Sample Complexity: The algorithm achieves a sample complexity of $\tilde{O}(1/\epsilon^2)$ to reach an $\epsilon$-optimal policy, matching the gold standard for efficiency in online RL.
Empirical Results: Atari 100K
To validate the theory, the authors developed a practical implementation called SPR-UCB, which integrates the UCB bonus into the existing "Self-Predictive Representations" (SPR) method. They tested this on the Atari 100K benchmark, a rigorous testbed where agents are limited to only 100,000 steps (roughly two hours of gameplay).
- Performance: SPR-UCB achieved a mean human-normalized score of 0.69, significantly outperforming the base SPR (0.62) and other prominent baselines like DrQ (0.37) and CURL (0.26).
- Hard Exploration: The UCB bonus proved particularly effective in "hard exploration" games such as PrivateEye, Frostbite, and Freeway, where standard random exploration typically fails to make progress.
Limitations and Future Directions
While a major step forward, the authors note several areas for future research:
- Function Classes: The current theory assumes a finite function class for representations; future work could extend this to infinite classes using covering number arguments.
- Reward Learning: The study assumed a known reward function to isolate the difficulty of learning transitions. Simultaneous learning of rewards and transitions is a natural next step.
- Negative Sampling: The theoretical model requires a negative sampling distribution, whereas the practical SPR-UCB uses a cosine-similarity trick. Reconciling these two approaches remains an open theoretical challenge.
Conclusion
Contrastive UCB provides a vital theoretical bridge between self-supervised representation learning and regret analysis in online RL. By proving that contrastive objectives can recover environment structures and drive efficient exploration, this work lays the groundwork for more robust and provably efficient RL agents in the real world.
Summary updated