Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
On the map: Offline RL and imitation learning from data → Offline RL algorithms
Abstract (arXiv)
The success of deep reinforcement learning (DRL) lies in its ability to learn a representation that is well-suited for the exploration and exploitation task. To understand how the choice of representation can improve the efficiency of reinforcement learning (RL), we study representation selection for a class of low-rank Markov Decision Processes (MDPs) where the transition kernel can be represented in a bilinear form. We propose an efficient algorithm, called ReLEX, for representation learning in both online and offline RL. Specifically, we show that the online version of ReLEX, called ReLEX-UCB, always performs no worse than the state-of-the-art algorithm without representation selection, and achieves a strictly better constant regret if the representation function class has a "coverage" property over the entire state-action space. For the offline counterpart, ReLEX-LCB, we show that the algorithm can find the optimal policy if the representation class can cover the state-action space and achieves gap-dependent sample complexity. This is the first result with constant sample complexity for representation learning in offline RL.
Key facts. Cited by 12 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 37 of its 64 references that are in the map. First posted on arXiv 22 Jun 2021.
Builds on
37 of 64 references.
Closest ancestors · 4
Same direction, newest first
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
- 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
- 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
- 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
Other references · 33
- 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2020Decoupling Representation Learning from Reinforcement Learningcited by 263
- 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
- 2019Provably Efficient Exploration in Policy Optimizationcited by 203
- 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
- 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
21 more
- 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
- 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
- 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
- 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2016Corralling a Band of Bandit Algorithmscited by 99
- 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
- 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
- 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
- 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
- 2017Near Optimal Behavior via Approximate State Abstractioncited by 63
- 2019Model selection for contextual banditscited by 60
- 2020Q-learning with Logarithmic Regretcited by 59
- 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
- 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
- 2020Offline Policy Selection under Uncertaintycited by 31
- 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
- 2019OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual banditscited by 28
- 2020Problem-Complexity Adaptive Model Selection for Stochastic Linear Banditscited by 26
- 2020Regret Balancing for Bandit and RL Model Selectioncited by 20
- 2020Open Problem: Model Selection for Contextual Banditscited by 12
Built on by
Citing papers per year: 2021: 3; 2022: 3; 2023: 1; 2024: 2; 2025: 2; 2026: 1.
12 papers.
- 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
- 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
- 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
- 2022Learning Bellman Complete Representations for Offline Policy Evaluationcited by 17
- 2021Model Selection in Batch Policy Optimizationcited by 11
- 2024Adaptive Regularization of Representation Rank as an Implicit Constraint of Bellman Equationcited by 7
- 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
- 2024BECAUSE: Bilinear Causal Representation for Generalizable Offline Model-based Reinforcement Learningcited by 3
- 2025Provable Zero-Shot Generalization in Offline Reinforcement Learningcited by 3
- 2023Eigensubspace of Temporal-Difference Dynamics and How It Improves Value Approximation in Reinforcement Learningcited by 2
- 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximationcited by 1
- 2026Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representationscited by 0
- 2026Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representations26 Aug 2026
- 2025Provable Zero-Shot Generalization in Offline Reinforcement Learning11 Mar 2025
- 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation17 Jan 2025
- 2024BECAUSE: Bilinear Causal Representation for Generalizable Offline Model-based Reinforcement Learning15 Jul 2024
- 2024Adaptive Regularization of Representation Rank as an Implicit Constraint of Bellman Equation19 Apr 2024
- 2023Eigensubspace of Temporal-Difference Dynamics and How It Improves Value Approximation in Reinforcement Learning29 Jun 2023
- 2022Learning Bellman Complete Representations for Offline Policy Evaluation12 Jul 2022
- 2022Provable Benefits of Representational Transfer in Reinforcement Learning29 May 2022
- 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach31 Jan 2022
- 2021Model Selection in Batch Policy Optimization23 Dec 2021
- 2021Universal and data-adaptive algorithms for model selection in linear contextual bandits8 Nov 2021
- 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct 2021
Similar, not cited
Close in wording, no citation either way
- 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
- 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learning
- 2021Representation Matters: Offline Pretraining for Sequential Decision Making
- 2025Statistical and Algorithmic Foundations of Reinforcement Learning
- 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learning
- 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
- 2024Offline RL via Feature-Occupancy Gradient Ascent
- 2022Behavior Prior Representation learning for Offline Reinforcement Learning