mlsanityData to 14 Oct 2026

Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning

arXiv 1911.05815 ↗First posted 13 Nov 2019cs.LG stat.MLcited by 114

Not on the map. Why?

Abstract (arXiv)

We present an algorithm, HOMER, for exploration and reinforcement learning in rich observation environments that are summarizable by an unknown latent state space. The algorithm interleaves representation learning to identify a new notion of kinematic state abstraction with strategic exploration to reach new states using the learned abstraction. The algorithm provably explores the environment with sample complexity scaling polynomially in the number of latent states and the time horizon, and, crucially, with no dependence on the size of the observation space, which could be infinitely large. This exploration guarantee further enables sample-efficient global policy optimization for any reward function. On the computational side, we show that the algorithm can be implemented efficiently whenever certain supervised learning problems are tractable. Empirically, we evaluate HOMER on a challenging exploration problem, where we show that the algorithm is exponentially more sample efficient than standard reinforcement learning baselines.

Key facts. Cited by 114 papers in the map (data through 14 Oct 2026). First posted on arXiv 13 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 27; 2022: 41; 2023: 22; 2024: 17; 2025: 4; 2026: 3.

114 papers.

Sort:

By area:

  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  2. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  3. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  4. 2021Rapid Exploration for Open-World Navigation with Latent Goal Modelscited by 121
  5. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  6. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  7. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  8. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  9. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  10. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  11. 2022Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Modelscited by 45
  12. 2021Learning Markov State Abstractions for Deep Reinforcement Learningcited by 44
38 more
  1. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  2. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  3. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  4. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  5. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  6. 2021The Information Geometry of Unsupervised Reinforcement Learningcited by 37
  7. 2021Return-Based Contrastive Representation Learning for Reinforcement Learningcited by 36
  8. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 36
  9. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  10. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  11. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  12. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  13. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  14. 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?cited by 29
  15. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  16. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  17. 2022Simplifying Model-based RL: Learning Representations, Latent-space Models, and Policies with One Objectivecited by 28
  18. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  19. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  20. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  21. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  22. 2021MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learningcited by 24
  23. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  24. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  25. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  26. 2021Cross-Trajectory Representation Learning for Zero-Shot Generalization in RLcited by 20
  27. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 20
  28. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  29. 2021Model-Invariant State Abstractions for Model-Based Reinforcement Learningcited by 18
  30. 2022Pretraining in Deep Reinforcement Learning: A Surveycited by 18
  31. 2021Improving Zero-shot Generalization in Offline Reinforcement Learning using Generalized Similarity Functionscited by 17
  32. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 17
  33. 2022Agent-Controller Representations: Principled Offline RL with Rich Exogenous Informationcited by 16
  34. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  35. 2022Latent Variable Representation for Reinforcement Learningcited by 15
  36. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  37. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  38. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 14

50 most cited of 114 All 114 (JSON)