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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfeng2020provably

Related papers

• Gap-dependent Unsupervised Exploration For Reinforcement Learning (2021)0.00
• Minimax-optimal Reward-agnostic Exploration In Reinforcement Learning (2023)0.00
• Strategically Efficient Exploration In Competitive Multi-agent Reinforcement Learning (2021)0.00
• When Simple Exploration Is Sample Efficient: Identifying Sufficient Conditions For Random Exploration To Yield PAC RL Algorithms (2018)0.00
• Provably Efficient Exploration In Policy Optimization (2019)0.00
• Exploration In Feature Space For Reinforcement Learning (2017)0.00
• Probabilistic Insights For Efficient Exploration Strategies In Reinforcement Learning (2025)0.00
• Smart Exploration In Reinforcement Learning Using Bounded Uncertainty Models (2025)0.00