Kinematic State Abstraction And Provably Efficient Rich-observation Reinforcement Learning

Abstract

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 th

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymisra2019kinematic

Related papers

• Provably Efficient Exploration For Reinforcement Learning Using Unsupervised Learning (2020)0.00
• Low-dimensional State And Action Representation Learning With MDP Homomorphism Metrics (2021)0.00
• On Oracle-efficient PAC RL With Rich Observations (2018)0.00
• Extracting Latent State Representations With Linear Dynamics From Rich Observations (2020)0.00
• Goal Space Abstraction In Hierarchical Reinforcement Learning Via Reachability Analysis (2023)0.00
• Exploration In Approximate Hyper-state Space For Meta Reinforcement Learning (2020)0.00
• Reinforcement Learning In Rich-observation Mdps Using Spectral Methods (2016)0.00
• Time-myopic Go-explore: Learning A State Representation For The Go-explore Paradigm (2023)0.00