Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning

Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, John Langford

The "Chicken-and-Egg" Problem of Rich Observations

In modern reinforcement learning (RL), agents frequently operate in environments with "rich observations," such as high-resolution, megapixel images. While these images contain a wealth of information, they make exploration incredibly difficult. If an agent doesn't know which pixels are important, it cannot effectively map the environment.

This creates a circular dependency: to learn a good state decoder (a method to summarize complex pixels into meaningful, discrete states), the agent needs to observe a diverse set of data from the environment. However, to explore the environment and gather that diverse data in the first place, the agent needs a good decoder to know where it has already been.

The authors focus on Block Markov Decision Processes (Block MDPs), where many different high-dimensional observations (like different camera angles of the same room) actually map back to a small number of unobserved "latent" states. The goal is to find a provably efficient way to decode these states and explore the environment without needing hand-engineered features or dense rewards.

Introducing HOMER: Interleaving Exploration and Abstraction

To solve this, the authors introduce a new algorithm called HOMER. Its core innovation is interleaving representation learning with strategic exploration to systematically conquer the environment.

HOMER iteratively interleaves exploration to reach new states with representation learning to update its state abstraction.

HOMER operates on several key mechanisms:

  1. Kinematic Inseparability (KI): This is a novel form of state abstraction. Two observations are considered "kinematically inseparable" if they share the same forward dynamics (what happens next) and backward dynamics (how the agent got there).
  2. Contrastive Learning: To identify these states, HOMER solves a supervised learning problem. It trains a regressor to distinguish between "real" transitions (actual sequences of observations) and "imposter" transitions (observations paired with random previous states). The "bottleneck" layer of this regressor naturally learns to group observations into abstract states.
  3. Policy Covers: HOMER maintains a "policy cover"—a set of policies specifically designed to reach every discovered abstract state.
  4. The Loop: HOMER works inductively. It uses its current policies to reach the "frontier" of its knowledge, collects new data, uses contrastive learning to refine its state abstraction, and then trains new policies to reach the newly discovered states.

Unlike standard RL, which often relies on predicting the next frame (forward dynamics), HOMER’s use of backward dynamics is key to grouping observations that can be reached by the same exploration policy.

Key Insights: Why Pixel Prediction Fails

Standard exploration methods often try to predict the next frame to measure "curiosity." However, in rich-observation environments, this forces the model to memorize irrelevant noise.

Unlike standard autoencoders that often memorize noisy bits, HOMER's state abstraction model isolates the underlying state information.
  • The Power of "Fake" Data: By training a model to tell the difference between a real transition and a fake one (contrastive estimation), the agent learns the underlying structure of the world much more robustly than by trying to reconstruct every pixel of the next frame.
  • Backward Dynamics for Exploration: While forward dynamics help an agent plan, backward dynamics help it group. If two different images share the same "history," they can likely be reached by the same policy, making them a single unit for exploration purposes.
  • Provable Polynomial Complexity: The paper provides a mathematical guarantee that the number of samples needed scales polynomially with the number of latent states and the time horizon, but not the size of the observation space. This is a major theoretical milestone for rich-observation RL.

Evaluating on the "Diabolical Combination Lock"

The paper evaluates HOMER on a custom-designed benchmark called the Diabolical Combination Lock. This is a synthetic but extremely difficult MDP with a long horizon ($H=100$) and a large action space ($K=10$). It features high-dimensional, noisy observations and "precarious dynamics"—one wrong move sends the agent to a "bad" state from which it can never reach the goal.

Furthermore, the environment provides small negative rewards for moving toward the goal, which tricks standard "curiosity" or "entropy-based" exploration methods into giving up. The probability of reaching the goal by random actions is $10^{-100}$ (less than the number of atoms in the universe).

Results

  • Solving the Unsolvable: HOMER successfully solved the $H=100$ combination lock.
  • Baseline Failure: Popular RL algorithms like PPO and DQN failed at horizons as short as $H=3$ and $H=6$, respectively. Even PPO + RND (a state-of-the-art exploration method) failed once the horizon reached $H=50$.
  • State Recovery: Qualitative analysis showed that HOMER accurately recovered the "canonical" form of the environment, correctly separating the "good" states from the "bad" states despite the noisy, high-dimensional input.

Limitations and Future Work

The theory relies on the "disjoint emission" assumption—the idea that two different latent states can never produce the exact same observation. While common in theory, real-world sensors might have more overlap. Additionally, the algorithm assumes access to "oracles" for solving supervised learning and contextual bandit problems. In practice, these are replaced by neural networks, which may not always find the global optimum.

While the "combination lock" is a fantastic stress test for exploration, the next step for this line of research is applying HOMER to more "natural" rich-observation tasks, such as complex robotics simulations or video games with sparse rewards.

Summary updated

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 more sample efficient than standard reinforcement learning baselines.
BibTeX
@inproceedings{misra2020kinematic,
  author = {Dipendra Misra and Mikael Henaff and Akshay Krishnamurthy and John Langford},
  title = {{Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=GyhGEgjdQn},
}
Figure