mlsanityData to 7 Oct 2026

Model-free Representation Learning and Exploration in Low-rank MDPs

arXiv 2102.07035 ↗First posted 14 Feb 2021cs.LG stat.MLcited by 82

Not on the map. Why?

Abstract (arXiv)

The low rank MDP has emerged as an important model for studying representation learning and exploration in reinforcement learning. With a known representation, several model-free exploration strategies exist. In contrast, all algorithms for the unknown representation setting are model-based, thereby requiring the ability to model the full dynamics. In this work, we present the first model-free representation learning algorithms for low rank MDPs. The key algorithmic contribution is a new minimax representation learning objective, for which we provide variants with differing tradeoffs in their statistical and computational properties. We interleave this representation learning step with an exploration strategy to cover the state space in a reward-free manner. The resulting algorithms are provably sample efficient and can accommodate general function approximation to scale to complex environments.

Key facts. Cited by 82 papers in the map (data through 7 Oct 2026). Builds on 30 of its 38 references that are in the map. First posted on arXiv 14 Feb 2021.

Builds on

30 of 38 references.

References · 30

  1. 2018Learning Latent Dynamics for Planning from Pixelscited by 1,221
  2. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  3. 2020Learning Invariant Representations for Reinforcement Learning without Reconstructioncited by 424
  4. 2020Planning to Explore via Self-Supervised World Modelscited by 365
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  9. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 204
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
18 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  3. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  4. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  5. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  6. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  7. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  8. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  9. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  12. 2019A Geometric Perspective on Optimal Representations for Reinforcement Learningcited by 54
  13. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
  14. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  15. 2020Online Model Selection for Reinforcement Learning with Function Approximationcited by 28
  16. 2020Online Sparse Reinforcement Learningcited by 25
  17. 2020The Elliptical Potential Lemma Revisitedcited by 23
  18. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 29; 2023: 22; 2024: 12; 2025: 6; 2026: 5.

82 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  2. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  3. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  4. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
  5. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  6. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  7. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  8. 2023Proto-Value Networks: Scaling Representation Learning with Auxiliary Taskscited by 41
  9. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  10. 2021The Information Geometry of Unsupervised Reinforcement Learningcited by 36
  11. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  12. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
38 more
  1. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  2. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  3. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  4. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  5. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  6. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  7. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  8. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  9. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  10. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  11. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  12. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  13. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  14. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  15. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  16. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  17. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  18. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  19. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  20. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  21. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  22. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
  23. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  24. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  25. 2022Learning General World Models in a Handful of Reward-Free Deploymentscited by 12
  26. 2022Behavior Prior Representation learning for Offline Reinforcement Learningcited by 12
  27. 2023The Virtues of Laziness in Model-based RL: A Unified Objective and Algorithmscited by 12
  28. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  29. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  30. 2023Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networkscited by 9
  31. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  32. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  33. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  34. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  35. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  36. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  37. 2021Learning Good State and Action Representations via Tensor Decompositioncited by 7
  38. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7

50 most cited of 82 All 82 (JSON)