Provable Rich Observation Reinforcement Learning with Combinatorial Latent States

Dipendra Misra, Qinghua Liu, Chi Jin, John LangfordICLR 2021 · OpenReview

Most reinforcement learning (RL) algorithms struggle with the "curse of dimensionality." Consider a room with 100 items that can each be in two states; the total state space is $2^{100}$, which is far too large to explore naively. While Factored MDPs can handle this by assuming the state is composed of independent factors, they usually require the agent to have direct access to those underlying factors.

In the real world, however, agents typically receive "rich observations" (like megapixel camera images) where the underlying state factors are hidden. Previous work on Block MDPs addressed rich observations but failed to exploit factored structures, meaning their complexity still exploded as the number of latent factors grew.

This paper introduces FactoRL (pronounced "Fact-o-Rel"), the first RL algorithm with provable guarantees for environments featuring both high-dimensional rich observations and a combinatorial latent state space. By discovering how raw observation "atoms" (like pixels) map to underlying latent factors, FactoRL achieves a sample complexity that scales polynomially with the number of factors, rather than exponentially with the state space size.

The Factored Block MDP Framework

To tackle this problem, the authors propose a new framework called the Factored Block MDP. In this setting, the agent receives observations generated stochastically from a "latent" factored state.

The Factored Block MDP generative process, where latent state factors transition and emit disjoint observation atoms.

A key technical assumption enabling this framework is disjointness: each observation atom is generated by exactly one latent factor. This ensures that the latent state is theoretically decodable from the rich observation, removing partial observability concerns.

FactoRL: A Four-Stage Algorithm

FactoRL uses an inductive process executed at each timestep to decode the environment and learn an optimal policy. It operates in four main stages:

  1. Identify Emission Structure: The agent must figure out which "atoms" of an observation belong to which latent factor. It achieves this using noise-contrastive learning to perform independence tests. If two atoms become independent when certain previous factors are fixed, they likely belong to different factors. This insight—using conditional independence to isolate causal roots—is central to the algorithm's success.
  2. Learn State Decoder: Once atoms are successfully grouped, the agent trains a decoder model to map these groups to binary latent factor values.
The decoder model maps grouped observation atoms back to binary latent factor values.
  1. Estimate Model: The agent identifies the "parents" of each factor (i.e., which factors influence its next state) and estimates the transition probabilities.
  2. Learn Policy Cover: Finally, the agent uses a planning oracle to find a set of policies capable of reaching all possible reachable values of the latent factors. To perform the earlier independence tests accurately, the agent uses rejection sampling to "force" the distribution into required states, overcoming the difficulty of low-probability transitions in a combinatorial space.

Key Results and Guarantees

The authors prove that FactoRL returns a near-optimal transition function and decoder with high probability. Crucially, the sample complexity is polynomial in the number of factors ($d^{16\kappa}$, where $\kappa$ is the max number of parents per factor) and only logarithmically dependent on the number of observation atoms ($m$). This means doubling a camera's resolution has almost no impact on the learning difficulty.

In proof-of-concept synthetic experiments ($d=10$ factors, $H=10$ horizon), FactoRL perfectly detected the latent child functions and estimated the model with an error of less than 0.01 using 20,000 samples per timestep. The environment was specifically designed to shuffle the mapping from factors to atoms at each timestep, proving the agent could not simply rely on spatial pixel ordering.

Limitations and Future Work

While a significant theoretical step forward, FactoRL has limitations that pave the way for future research:

  • The Disjointness Assumption: The model assumes each pixel/atom is controlled by only one factor. In complex visual scenes with occlusion or transparency, a single pixel might be influenced by multiple factors. Relaxing this is a major direction for future work.
  • Planning Complexity: While the learning is efficient, planning in factored MDPs is known to be EXPTIME-complete in the worst case. The algorithm relies on an "efficient planning oracle," which may not exist for all types of factored dynamics.
  • Binary Factors: The current theory focuses on discrete (specifically binary) factors. Extending this framework to continuous latent factors will be necessary for many real-world robotics applications.

Summary updated

Abstract

We propose a novel setting for reinforcement learning that combines two common real-world difficulties: presence of observations (such as camera images) and factored states (such as location of objects). In our setting, the agent receives observations generated stochastically from a "latent" factored state. These observations are "rich enough" to enable decoding of the latent state and remove partial observability concerns. Since the latent state is combinatorial, the size of state space is exponential in the number of latent factors. We create a learning algorithm FactoRL (Fact-o-Rel) for this setting, which uses noise-contrastive learning to identify latent structures in emission processes and discover a factorized state space. We derive polynomial sample complexity guarantees for FactoRL which polynomially depend upon the number factors, and very weakly depend on the size of the observation space. We also provide a guarantee of polynomial time complexity when given access to an efficient planning algorithm.
BibTeX
@inproceedings{misra2021provable,
  author = {Dipendra Misra and Qinghua Liu and Chi Jin and John Langford},
  title = {{Provable Rich Observation Reinforcement Learning with Combinatorial Latent States}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=hx1IXFHAw7R},
}
Figure