Provable RL with Exogenous Distractors via Multistep Inverse Dynamics

Abstract

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.

ICLR 2022

References in corpus (9)

• Learning Latent Dynamics for Planning from Pixels
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Learning Invariant Representations for Reinforcement Learning without Reconstruction
• DeepMDP: Learning Continuous Latent Space Models for Representation Learning
• Information-Theoretic Considerations in Batch Reinforcement Learning
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning