Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
This addresses a critical bottleneck in real-world RL applications like robotics, where noise can disrupt state representation learning, though it is incremental as it builds on prior representation learning frameworks.
The paper tackles the problem of reinforcement learning with high-dimensional observations in the presence of temporally correlated exogenous noise, introducing the Exogenous Block MDP model and proposing the Predictive Path Elimination algorithm that provably achieves sample and computational efficiency under near-deterministic dynamics, with experiments showing empirical success.
Many real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from a megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations and subsequently plan efficiently. However, such approaches can fail in the presence of temporally correlated noise in the observations, a phenomenon that is common in practice. We initiate the formal study of latent state discovery in the presence of such exogenous noise sources by proposing a new model, the Exogenous Block MDP (EX-BMDP), for rich observation RL. We start by establishing several negative results, by highlighting failure cases of prior representation learning based approaches. Then, we introduce the Predictive Path Elimination (PPE) algorithm, that learns a generalization of inverse dynamics and is provably sample and computationally efficient in EX-BMDPs when the endogenous state dynamics are near deterministic. The sample complexity of PPE depends polynomially on the size of the latent endogenous state space while not directly depending on the size of the observation space, nor the exogenous state space. We provide experiments on challenging exploration problems which show that our approach works empirically.