Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning

Abstract

Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems [tang2017exploration,bellemare2016unifying], we investigate when this paradigm is provably efficient. We study episodic Markov decision processes with rich observations generated from a small number of latent states. We present a general algorithmic framework that is built upon two components: an unsupervised learning algorithm and a no-regret tabular RL algorithm. Theoretically, we prove that as long as the unsupervised learning algorithm enjoys a polynomial sample complexity guarantee, we can find a near-optimal policy with sample complexity polynomial in the number of latent states, which is significantly smaller than the number of observations. Empirically, we instantiate our framework on a class of hard exploration problems to demonstrate the practicality of our theory.

References in corpus (18)

• Noisy Networks for Exploration
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A Two-round Variant of EM for Gaussian Mixtures
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• A Theoretical Analysis of Deep Q-Learning
• A Theory of Regularized Markov Decision Processes
• BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Provably efficient RL with Rich Observations via Latent State Decoding
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Clustering and variable selection for categorical multivariate data
• Variance Reduction Methods for Sublinear Reinforcement Learning
• On Oracle-Efficient PAC RL with Rich Observations