Provably efficient RL with Rich Observations via Latent State Decoding

Abstract

We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps -- where previously decoded latent states provide labels for later regression problems -- and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over $Q$-learning with naïve exploration, even when $Q$-learning has cheating access to latent states.

The ICML 2019 version omitted the second constraint on $\epsilon$ in Theorem 4.1. We thank Yonathan Efroni for calling this to our attention

Cited by in corpus (40)

• A Survey of Zero-shot Generalisation in Deep Reinforcement Learning
• Learning Invariant Representations for Reinforcement Learning without Reconstruction
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• Contrastive learning, multi-view redundancy, and linear models
• $Q$-learning with Logarithmic Regret
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Domain Adversarial Reinforcement Learning
• Learning Markov State Abstractions for Deep Reinforcement Learning
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Representation Learning for Online and Offline RL in Low-rank MDPs
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Towards General Function Approximation in Zero-Sum Markov Games
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• CARL: A Benchmark for Contextual and Adaptive Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Block Contextual MDPs for Continual Learning
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning
• Randomized Value Functions via Posterior State-Abstraction Sampling
• A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning
• A First-Occupancy Representation for Reinforcement Learning
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Learning the Linear Quadratic Regulator from Nonlinear Observations
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Online Learning in Unknown Markov Games
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Reinforcement Learning in Reward-Mixing MDPs
• Explore and Control with Adversarial Surprise
• Component Transfer Learning for Deep RL Based on Abstract Representations