# Making Linear MDPs Practical via Contrastive Representation Learning

arXiv: https://arxiv.org/abs/2207.07150 · HTML: https://mlsanity.com/paper/2207.07150/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 69 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 30 of 44)

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Learning Latent Dynamics for Planning from Pixels](https://mlsanity.com/paper/1811.04551/) (2018)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [Behavior Regularized Offline Reinforcement Learning](https://mlsanity.com/paper/1911.11361/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Successor Features for Transfer in Reinforcement Learning](https://mlsanity.com/paper/1606.05312/) (2016)
- [Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Images](https://mlsanity.com/paper/1506.07365/) (2015)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Model-Ensemble Trust-Region Policy Optimization](https://mlsanity.com/paper/1802.10592/) (2018)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Bridging the Gap Between Value and Policy Based Reinforcement Learning](https://mlsanity.com/paper/1702.08892/) (2017)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Benchmarking Model-Based Reinforcement Learning](https://mlsanity.com/paper/1907.02057/) (2019)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Noise Contrastive Estimation and Negative Sampling for Conditional Models: Consistency and Statistical Efficiency](https://mlsanity.com/paper/1809.01812/) (2018)

## Built on by (most cited first, 30 of 52)

- [Learning Universal Policies via Text-Guided Video Generation](https://mlsanity.com/paper/2302.00111/) (2023)
- [Foundation Models for Decision Making: Problems, Methods, and Opportunities](https://mlsanity.com/paper/2303.04129/) (2023)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Feedback Efficient Online Fine-Tuning of Diffusion Models](https://mlsanity.com/paper/2402.16359/) (2024)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Towards General-Purpose Model-Free Reinforcement Learning](https://mlsanity.com/paper/2501.16142/) (2025)
- [Spectral Decomposition Representation for Reinforcement Learning](https://mlsanity.com/paper/2208.09515/) (2022)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learning](https://mlsanity.com/paper/2207.14800/) (2022)
- [Bridging Model-Based Optimization and Generative Modeling via Conservative Fine-Tuning of Diffusion Models](https://mlsanity.com/paper/2405.19673/) (2024)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL](https://mlsanity.com/paper/2304.05889/) (2023)
- [Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RL](https://mlsanity.com/paper/2410.20254/) (2024)
- [Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization](https://mlsanity.com/paper/2209.15382/) (2022)
- [From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systems](https://mlsanity.com/paper/2405.19883/) (2024)
- [Efficient Model-Free Exploration in Low-Rank MDPs](https://mlsanity.com/paper/2307.03997/) (2023)
- [Latent Variable Representation for Reinforcement Learning](https://mlsanity.com/paper/2212.08765/) (2022)
- [Contrastive Imitation Learning for Language-guided Multi-Task Robotic Manipulation](https://mlsanity.com/paper/2406.09738/) (2024)
- [Diffusion Spectral Representation for Reinforcement Learning](https://mlsanity.com/paper/2406.16121/) (2024)
- [Spectral Representation Learning for Conditional Moment Models](https://mlsanity.com/paper/2210.16525/) (2022)
- [Spectral Representation for Causal Estimation with Hidden Confounders](https://mlsanity.com/paper/2407.10448/) (2024)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning](https://mlsanity.com/paper/2311.12244/) (2023)
- [Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP](https://mlsanity.com/paper/2306.12356/) (2023)
- [Distributional Successor Features Enable Zero-Shot Policy Optimization](https://mlsanity.com/paper/2403.06328/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Skill Transfer and Discovery for Sim-to-Real Learning: A Representation-Based Viewpoint](https://mlsanity.com/paper/2404.05051/) (2024)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)

## Abstract (arXiv)

It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. This motivates much of the recent theoretical study on linear MDPs. However, most approaches require a given representation under unrealistic assumptions about the normalization of the decomposition or introduce unresolved computational challenges in practice. Instead, we consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning via contrastive estimation. The framework also admits confidence-adjusted index algorithms, enabling an efficient and principled approach to incorporating optimism or pessimism in the face of uncertainty. To the best of our knowledge, this provides the first practical representation learning method for linear MDPs that achieves both strong theoretical guarantees and empirical performance. Theoretically, we prove that the proposed algorithm is sample efficient in both the online and offline settings. Empirically, we demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.