mlsanityData to 14 Oct 2026

Efficient Model-Free Exploration in Low-Rank MDPs

arXiv 2307.03997 ↗First posted 8 Jul 2023cs.LG math.OCcited by 16

Not on the map. Why?

Abstract (arXiv)

A major challenge in reinforcement learning is to develop practical, sample-efficient algorithms for exploration in high-dimensional domains where generalization and function approximation is required. Low-Rank Markov Decision Processes -- where transition probabilities admit a low-rank factorization based on an unknown feature embedding -- offer a simple, yet expressive framework for RL with function approximation, but existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions such as latent variable structure, access to model-based function approximation, or reachability. In this work, we propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs that is both computationally efficient and model-free, allowing for general function approximation and requiring no additional structural assumptions. Our algorithm, VoX, uses the notion of a barycentric spanner for the feature embedding as an efficiently computable basis for exploration, performing efficient barycentric spanner computation by interleaving representation learning and policy optimization. Our analysis -- which is appealingly simple and modular -- carefully combines several techniques, including a new approach to error-tolerant barycentric spanner computation and an improved analysis of a certain minimax representation learning objective found in prior work.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 32 of its 46 references that are in the map. First posted on arXiv 8 Jul 2023.

Builds on

32 of 46 references.

References · 32

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2016Deep Reinforcement Learning for Dialogue Generationcited by 288
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  8. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
20 more
  1. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  2. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  3. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  4. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  5. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  6. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  7. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  8. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  9. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  10. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  11. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  12. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  13. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  14. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  15. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  16. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  17. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  18. 2020Learning the Linear Quadratic Regulator from Nonlinear Observationscited by 21
  19. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18
  20. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 9; 2025: 2; 2026: 4.

16 papers.

Sort:

By area:

  1. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 21
  2. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  3. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  4. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 6
  5. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  6. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  7. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  8. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPscited by 5
  9. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  10. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  11. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  12. 2025Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representationcited by 1
4 more
  1. 2026Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Explorationcited by 1
  2. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  3. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  4. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPscited by 0