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 than standard reinforcement learning baselines.
Introduction
Modern reinforcement learning (RL) agents frequently operate in environments characterized by "rich observations," such as high-resolution camera feeds or complex sensor arrays. While informative, these high-dimensional inputs pose a significant challenge for exploration. Traditional RL algorithms, which rely on counting visits to specific states, fail in these settings because the agent rarely encounters the exact same observation twice.
This creates a fundamental circular dependency: effective exploration requires a compact representation to group similar observations, but learning such a representation requires sufficient exploration to understand the relationships between observations. This paper introduces HOMER, an algorithm designed to break this cycle in Block MDPs, where a large observation space maps to a small, unobserved latent state space.
The HOMER Algorithm
HOMER addresses the exploration problem by interleaving representation learning with strategic exploration. The algorithm maintains a "policy cover"—a set of policies designed to reach every discovered abstract state with maximum probability.
The core loop involves:
- Exploration: Using the current abstraction to reach the frontier of the explored environment.
- Abstraction Learning: Collecting new observations and updating the latent state model.
- Policy Update: Using Policy Search by Dynamic Programming (PSDP) to build new "homing" policies for newly discovered states.
Kinematic State Abstraction
A key contribution of this work is the definition of kinematic inseparability. Two observations are considered kinematically inseparable if they share identical backward dynamics (the probability of arriving at them from a prior state/action) and forward dynamics (the probability of transitioning to future states).
To learn this abstraction without pixel reconstruction, HOMER employs contrastive estimation. It trains a model to distinguish between real transitions $(x_t, a_t, x_{t+1})$ and "imposter" transitions where the next observation is sampled randomly from history. This bottleneck forces the model to capture the underlying latent structure necessary to predict valid transitions.
Empirical Evaluation
The authors evaluate HOMER on a "Diabolical Combination Lock" benchmark. This synthetic environment is a worst-case scenario for RL, featuring a long horizon ($H=100$), sparse rewards, and high-dimensional observations with Gaussian noise.
Key Results: * Success on Sparse Rewards: HOMER consistently solved the 100-step lock, whereas standard baselines like PPO and A2C (even with RND curiosity) failed once the horizon exceeded 25 steps. * Sample Efficiency: The algorithm demonstrated exponential gains in sample efficiency. By focusing on dynamics rather than appearance, HOMER avoids being distracted by visual noise or "anti-shaped" rewards that lead other agents into local optima. * Provable Guarantees: Mathematically, HOMER's sample complexity is polynomial in the number of latent states and the time horizon, with zero dependence on the observation space's size.
Conclusion
HOMER provides a theoretically grounded and empirically robust framework for RL in rich-observation environments. By prioritizing "how a state behaves" over "what a state looks like," it achieves provably efficient exploration. While the computational cost of solving multiple supervised learning problems in a loop remains a challenge, the shift toward kinematic abstractions marks a significant step forward for autonomous agents in complex, real-world-like domains.
Reference: Misra, D., Henaff, M., Krishnamurthy, A., & Langford, J. (2019). Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning. arXiv:1911.05815.
Summary updated