Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
This work addresses the challenge of exploration in RL for problems with high-dimensional observations, offering a provably efficient solution that is incremental based on existing paradigms.
The paper tackles the problem of efficient exploration in reinforcement learning with rich observations by proposing a framework combining unsupervised learning and tabular RL, proving that it achieves near-optimal policies with sample complexity polynomial in the number of latent states, which is smaller than the number of observations.
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.