mlsanityData to 7 Oct 2026

Representation Learning for Online and Offline RL in Low-rank MDPs

arXiv 2110.04652 ↗First posted 9 Oct 2021cs.LG cs.AI stat.MLcited by 128

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

This work studies the question of Representation Learning in RL: how can we learn a compact low-dimensional representation such that on top of the representation we can perform RL procedures such as exploration and exploitation, in a sample efficient manner. We focus on the low-rank Markov Decision Processes (MDPs) where the transition dynamics correspond to a low-rank transition matrix. Unlike prior works that assume the representation is known (e.g., linear MDPs), here we need to learn the representation for the low-rank MDP. We study both the online RL and offline RL settings. For the online setting, operating with the same computational oracles used in FLAMBE (Agarwal et.al), the state-of-art algorithm for learning representations in low-rank MDPs, we propose an algorithm REP-UCB Upper Confidence Bound driven Representation learning for RL), which significantly improves the sample complexity from widetildeO( A9 d7 / (ε10 (1-γ)22)) for FLAMBE to widetildeO( A2 d4 / (ε2 (1-γ)5) ) with d being the rank of the transition matrix (or dimension of the ground truth representation), A being the number of actions, and γ being the discounted factor. Notably, REP-UCB is simpler than FLAMBE, as it directly balances the interplay between representation learning, exploration, and exploitation, while FLAMBE is an explore-then-commit style approach and has to perform reward-free exploration step-by-step forward in time. For the offline RL setting, we develop an algorithm that leverages pessimism to learn under a partial coverage condition: our algorithm is able to compete against any policy as long as it is covered by the offline distribution.

Key facts. Cited by 128 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 49 of its 63 references that are in the map. First posted on arXiv 9 Oct 2021.

Builds on

49 of 63 references.

Closest ancestors · 13

Same direction, newest first

  1. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  2. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL22 Jun
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  4. 2021Corruption-Robust Offline Reinforcement Learning11 Jun
  5. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  6. 2021Representation Matters: Offline Pretraining for Sequential Decision Making11 Feb
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  8. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  9. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient8 Nov
  10. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  11. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  12. 2020MOPO: Model-based Offline Policy Optimization27 May
1 more
  1. 2020MOReL : Model-Based Offline Reinforcement Learning12 May

Other references · 36

  1. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 745
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  5. 2020Decoupling Representation Learning from Reinforcement Learningcited by 263
  6. 2013Learning to Optimize Via Posterior Samplingcited by 253
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  8. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  9. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  10. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  11. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  12. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
24 more
  1. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  2. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  3. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  4. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  5. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  6. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 83
  7. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  8. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  9. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  10. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  11. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  12. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  13. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  14. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  15. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
  16. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  17. 2021On the Power of Multitask Representation Learning in Linear MDPcited by 30
  18. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  19. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  20. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  21. 2020Online Sparse Reinforcement Learningcited by 25
  22. 2021PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Explorationcited by 14
  23. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  24. 2021Learning Good State and Action Representations via Tensor Decompositioncited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 36; 2023: 32; 2024: 39; 2025: 14; 2026: 6.

128 papers.

Sort:

By area:

  1. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  2. 2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
  3. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  4. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  6. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 71
  7. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  9. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  10. 2022On the Principles of Parsimony and Self-Consistency for the Emergence of Intelligencecited by 50
  11. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  12. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
38 more
  1. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  2. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  5. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  6. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  7. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  8. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  9. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  10. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  11. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  12. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  13. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  14. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  15. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  16. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  17. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 19
  18. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  19. 2023Look Beneath the Surface: Exploiting Fundamental Symmetry for Sample-Efficient Offline RLcited by 18
  20. 2024Contrastive Representation for Data Filtering in Cross-Domain Offline Reinforcement Learningcited by 18
  21. 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
  22. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  23. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  24. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  25. 2022Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learningcited by 16
  26. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  27. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  28. 2022Agent-Controller Representations: Principled Offline RL with Rich Exogenous Informationcited by 15
  29. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  30. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  31. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  32. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  33. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  34. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  35. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  36. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  37. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  38. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13

50 most cited of 128 All 128 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Learning Abstract World Models with a Group-Structured Latent Space
  2. 2022Representation Learning in Deep RL via Discrete Information Bottleneck
  3. 2021Instabilities of Offline RL with Pre-Trained Neural Representation
  4. 2024Offline RL via Feature-Occupancy Gradient Ascent
  5. 2026General Flexible f-divergence for Challenging Offline RL Datasets with Low Stochasticity and Diverse Behavior Policies
  6. 2022Offline RL Policies Should be Trained to be Adaptive
  7. 2020Offline Reinforcement Learning from Images with Latent Space Models
  8. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes