Abstract
We present an algorithm, HOMER, for exploration and reinforcement learning inrich observation environments that are summarizable by an unknown latent statespace. The algorithm interleaves representation learning to identify a newnotion of kinematic state abstraction with strategic exploration to reach newstates using the learned abstraction. The algorithm provably explores theenvironment with sample complexity scaling polynomially in the number of latentstates and the time horizon, and, crucially, with no dependence on the size ofthe observation space, which could be infinitely large. This explorationguarantee further enables sample-efficient global policy optimization for anyreward function. On the computational side, we show that the algorithm can beimplemented efficiently whenever certain supervised learning problems aretractable. Empirically, we evaluate HOMER on a challenging exploration problem,where we show that the algorithm is exponentially more sample efficient thanstandard reinforcement learning baselines.