mlsanityData to 7 Oct 2026

Making Linear MDPs Practical via Contrastive Representation Learning

arXiv 2207.07150 ↗First posted 14 Jul 2022cs.LG stat.MLcited by 49

Not on the map. Why?

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.

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

Builds on

44 of 69 references.

References · 44

  1. 2018Representation Learning with Contrastive Predictive Codingcited by 7,662
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  4. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,406
  5. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  6. 2018Learning Latent Dynamics for Planning from Pixelscited by 1,221
  7. 2018DeepMind Control Suitecited by 935
  8. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  9. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  10. 2018Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Modelscited by 748
  11. 2019Behavior Regularized Offline Reinforcement Learningcited by 654
  12. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
32 more
  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  4. 2016Successor Features for Transfer in Reinforcement Learningcited by 331
  5. 2015Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Imagescited by 266
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2018Model-Ensemble Trust-Region Policy Optimizationcited by 214
  8. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 204
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2017Bridging the Gap Between Value and Policy Based Reinforcement Learningcited by 178
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2019Benchmarking Model-Based Reinforcement Learningcited by 158
  13. 2020Contrastive learning, multi-view redundancy, and linear modelscited by 146
  14. 2019Scalable methods for computing state similarity in deterministic Markov Decision Processescited by 133
  15. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  16. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  17. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  18. 2020Invariant Causal Prediction for Block MDPscited by 104
  19. 2018Noise Contrastive Estimation and Negative Sampling for Conditional Models: Consistency and Statistical Efficiencycited by 103
  20. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  21. 2018The Laplacian in RL: Learning Representations with Efficient Approximationscited by 83
  22. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  23. 2020Generalized Energy Based Modelscited by 73
  24. 2016Deep Successor Reinforcement Learningcited by 72
  25. 2019Learning Compositional Koopman Operators for Model-Based Controlcited by 67
  26. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  27. 2021TRAIL: Near-Optimal Imitation Learning with Suboptimal Datacited by 39
  28. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  29. 2019Exponential Family Estimation via Adversarial Dynamics Embeddingcited by 30
  30. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  31. 2020Plan2Vec: Unsupervised Representation Learning by Latent Planscited by 21
  32. 2018State Aggregation Learning from Markov Transition Datacited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 10; 2024: 18; 2025: 7; 2026: 6.

49 papers.

Sort:

By area:

  1. 2023Learning Universal Policies via Text-Guided Video Generationcited by 506
  2. 2023Foundation Models for Decision Making: Problems, Methods, and Opportunitiescited by 160
  3. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  4. 2024Feedback Efficient Online Fine-Tuning of Diffusion Modelscited by 52
  5. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  6. 2025Towards General-Purpose Model-Free Reinforcement Learningcited by 40
  7. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  8. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  9. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  10. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  11. 2024Bridging Model-Based Optimization and Generative Modeling via Conservative Fine-Tuning of Diffusion Modelscited by 24
  12. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
37 more
  1. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  2. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  3. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  4. 2024From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systemscited by 17
  5. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  6. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  7. 2024Contrastive Imitation Learning for Language-guided Multi-Task Robotic Manipulationcited by 15
  8. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  9. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  10. 2022Spectral Representation Learning for Conditional Moment Modelscited by 12
  11. 2024Spectral Representation for Causal Estimation with Hidden Confounderscited by 12
  12. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  13. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  14. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  15. 2024Distributional Successor Features Enable Zero-Shot Policy Optimizationcited by 8
  16. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  17. 2025Replicable Reinforcement Learning with Linear Function Approximationcited by 6
  18. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  19. 2024Primal-Dual Spectral Representation for Off-policy Evaluationcited by 4
  20. 2024Skill Transfer and Discovery for Sim-to-Real Learning: A Representation-Based Viewpointcited by 3
  21. 2025Spectral Bellman Method: Unifying Representation and Exploration in RLcited by 3
  22. 2025Offline Imitation Learning upon Arbitrary Demonstrations by Pre-Training Dynamics Representationscited by 3
  23. 2025Spectral Representation-based Reinforcement Learningcited by 3
  24. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  25. 2024Provable Interactive Learning with Hindsight Instruction Feedbackcited by 1
  26. 2024Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimationcited by 1
  27. 2025Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representationcited by 1
  28. 2025Learning Task-Agnostic Motifs to Capture the Continuous Nature of Animal Behaviorcited by 1
  29. 2023A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Gamescited by 0
  30. 2024Towards Provable Log Density Policy Gradientcited by 0
  31. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  32. 2026Spectral Ghost in Representation Learning: from Component Analysis to Self-Supervised Learningcited by 0
  33. 2026When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPscited by 0
  34. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPscited by 0
  35. 2026Factorized Spectral Representations for Reinforcement Learningcited by 0
  36. 2026Learning Conditional Expectation Operators via Functional Newton Updatescited by 0
  37. 2026Learning Expressive and Compositional Motion Representation via Spectral Skillscited by 0