Timezone: »

 
Poster
Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning
Dipendra Kumar Misra · Mikael Henaff · Akshay Krishnamurthy · John Langford

Thu Jul 16 07:00 AM -- 07:45 AM & Thu Jul 16 08:00 PM -- 08:45 PM (PDT) @
in Poster Session 42 »

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 more sample efficient than standard reinforcement learning baselines.

Keywords: Reinforcement Learning · Reinforcement Learning Theory · Reinforcement Learning - Theory

Author Information

Dipendra Kumar Misra (Microsoft Research)

Work -> Microsoft Research (2019 - ) PhD -> Cornell University (2019) in AI B-Tech -> IIT Kanpur (2013)

Mikael Henaff (Microsoft)
Akshay Krishnamurthy (Microsoft Research)
John Langford (Microsoft Research)

More from the Same Authors