Introduction
Standard representation learning in Reinforcement Learning (RL) often fails when observations contain "exogenous noise"—complex, temporally correlated distractors like moving clouds, background traffic, or other elements that the agent cannot control. In "rich-observation" RL, agents must map high-dimensional inputs (like megapixel camera images) to a small latent state (like the agent's coordinates) to plan effectively.
However, the real world is full of these exogenous distractors. Existing methods often fall into two traps:
- Under-abstraction: Treating every unique combination of agent position and distractor state as a different state, leading to an exponential explosion in the data needed to explore.
- Over-abstraction: Ignoring the agent's position entirely if it's "smaller" than the noise, failing to learn a useful policy.
To address this, the authors introduce the Exogenous Block MDP (EX-BMDP) framework and a novel algorithm, Predictive Path Elimination (PPE), which uses multistep inverse dynamics to provably filter out these distractors and learn sample-efficiently based only on relevant state information.
The EX-BMDP Model and Predictive Path Elimination
The authors propose a new model to formalize the environment by splitting the latent state into two components: an endogenous state (affected by actions and rewards) and an exogenous state (independent dynamics).
To solve this, they introduce Predictive Path Elimination (PPE). Instead of trying to predict the next observation (which would require modeling the distractors), PPE learns a multistep inverse dynamics model.
- It asks: "Given this current observation, which sequence of actions (path) did I take to get here?"
- If the algorithm cannot statistically distinguish between two different paths based on the resulting observations, it concludes those paths lead to the same endogenous state.
- It iteratively builds a "policy cover"—a set of action sequences that reach every reachable endogenous state—while eliminating redundant paths.
Key Insights
- The Power of Multistep Inverse Dynamics: Standard inverse dynamics (predicting the last action) can fail if the starting state is random. By predicting the entire path from the start, the agent isolates endogenous changes from exogenous noise.
- Factorization is the Filter: Because the exogenous state is independent of the agent's actions, the probability of reaching a specific exogenous state is the same regardless of the path taken. This mathematical symmetry allows the classifier to "cancel out" the noise.
- Provable Efficiency: The number of samples needed scales polynomially with the size of the endogenous state space, regardless of how large or complex the exogenous distractors are.
Experiments and Results
The authors evaluated PPE on simulated environments designed to highlight the distractor problem: a Combination Lock with Noise (a difficult exploration task with 100-dimensional temporally correlated noise) and a Visual Grid World (a navigation task with moving, random ellipses as distractors).
- Superior Exploration: In the Combination Lock task, PPE successfully solved the problem for horizons up to $H=40$. Baselines like PPO, RND (Random Network Distillation), and HOMER failed even at much shorter horizons ($H=5$ or $10$) because they were distracted by the noise.
- Robust State Decoding: In the Visual Grid World, PPE maintained high accuracy in decoding the agent's true position from the image, even as distractor complexity increased. Contrastive methods like HOMER saw their accuracy plummet.
- Computational Efficiency: PPE reduces the complex RL problem to a series of standard multi-class classification problems, making it highly practical compared to previous theoretical algorithms.
Limitations and Future Work
- Determinism: The current theoretical proof for PPE assumes that the endogenous dynamics are "near-deterministic." Extending this to highly stochastic environments remains an open challenge.
- Discrete Latent States: The model assumes the endogenous state space is discrete. Adapting path elimination to continuous state spaces is a direction for future work.
- Function Class Realizability: The theory assumes the chosen function class (e.g., neural network architecture) is powerful enough to represent the "true" path predictor, which is a common but strong assumption in RL theory.
Summary updated