mlsanityData to 7 Oct 2026

Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach

arXiv 2202.00063 ↗First posted 31 Jan 2022cs.LG cs.AIcited by 51

Not on the map. Why?

Abstract (arXiv)

We present BRIEE (Block-structured Representation learning with Interleaved Explore Exploit), an algorithm for efficient reinforcement learning in Markov Decision Processes with block-structured dynamics (i.e., Block MDPs), where rich observations are generated from a set of unknown latent states. BRIEE interleaves latent states discovery, exploration, and exploitation together, and can provably learn a near-optimal policy with sample complexity scaling polynomially in the number of latent states, actions, and the time horizon, with no dependence on the size of the potentially infinite observation space. Empirically, we show that BRIEE is more sample efficient than the state-of-art Block MDP algorithm HOMER and other empirical RL baselines on challenging rich-observation combination lock problems that require deep exploration.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). Builds on 29 of its 43 references that are in the map. First posted on arXiv 31 Jan 2022.

Builds on

29 of 43 references.

References · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  3. 2018Exploration by Random Network Distillationcited by 966
  4. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 745
  5. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  7. 2020Planning to Explore via Self-Supervised World Modelscited by 365
  8. 2020Data-Efficient Reinforcement Learning with Self-Predictive Representationscited by 309
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  10. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  12. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
17 more
  1. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  3. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  4. 2018Count-Based Exploration with the Successor Representationcited by 112
  5. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  6. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  7. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  8. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  9. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  10. 2019A Geometric Perspective on Optimal Representations for Reinforcement Learningcited by 54
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2021Block Contextual MDPs for Continual Learningcited by 25
  13. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  14. 2018State Aggregation Learning from Markov Transition Datacited by 20
  15. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  16. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  17. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 14; 2023: 22; 2024: 11; 2025: 2; 2026: 2.

51 papers.

Sort:

By area:

  1. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  2. 2023Proto-Value Networks: Scaling Representation Learning with Auxiliary Taskscited by 41
  3. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  4. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  5. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  6. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  7. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  8. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  9. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  10. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  11. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 19
  12. 2022Pretraining in Deep Reinforcement Learning: A Surveycited by 18
38 more
  1. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  2. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
  3. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  4. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  5. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  6. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  7. 2023The Virtues of Laziness in Model-based RL: A Unified Objective and Algorithmscited by 12
  8. 2023Offline Data Enhanced On-Policy Policy Gradient with Provable Guaranteescited by 11
  9. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  10. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  11. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  12. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  13. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  14. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  15. 2022Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guaranteescited by 5
  16. 2023The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensionscited by 5
  17. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  18. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  19. 2023Prospective Side Information for Latent MDPscited by 4
  20. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  21. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  22. 2024Primal-Dual Spectral Representation for Off-policy Evaluationcited by 4
  23. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  24. 2023Context-lumpable stochastic banditscited by 3
  25. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  26. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  27. 2022CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Controlcited by 1
  28. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  29. 2023Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Groupingcited by 1
  30. 2023State Representations as Incentives for Reinforcement Learning Agents: A Sim2Real Analysis on Robotic Graspingcited by 1
  31. 2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
  32. 2024Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimationcited by 1
  33. 2025Accelerating Multi-Task Temporal Difference Learning under Low-Rank Representationcited by 1
  34. 2023Fast exploration and learning of latent graphs with aliased observationscited by 0
  35. 2023On the Benefits of Leveraging Structural Information in Planning Over the Learned Modelcited by 0
  36. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  37. 2024Disentangling Recognition and Decision Regrets in Image-Based Reinforcement Learningcited by 0
  38. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0

50 most cited of 51 All 51 (JSON)