Gap-Dependent Unsupervised Exploration for Reinforcement Learning

Abstract

For the problem of task-agnostic reinforcement learning (RL), an agent first collects samples from an unknown environment without the supervision of reward signals, then is revealed with a reward and is asked to compute a corresponding near-optimal policy. Existing approaches mainly concern the worst-case scenarios, in which no structural information of the reward/transition-dynamics is utilized. Therefore the best sample upper bound is $\propto \tilde{\mathcal{O}}(1/{\epsilon }^2)$, where $\epsilon >0$ is the target accuracy of the obtained policy, and can be overly pessimistic. To tackle this issue, we provide an efficient algorithm that utilizes a gap parameter, $\rho >0$, to reduce the amount of exploration. In particular, for an unknown finite-horizon Markov decision process, the algorithm takes only $\tilde{\mathcal{O}}(1/\epsilon \cdot (H^{3}SA/\rho +H^4{S}^{2}A))$ episodes of exploration, and is able to obtain an $\epsilon$-optimal policy for a post-revealed reward with sub-optimality gap at least $\rho$, where $S$ is the number of states, $A$ is the number of actions, and $H$ is the length of the horizon, obtaining a nearly \emph{quadratic saving} in terms of $\epsilon$. We show that, information-theoretically, this bound is nearly tight for $\rho <\Theta (1/(HS))$ and $H>1$. We further show that $\propto \tilde{\mathcal{O}}(1)$ sample bound is possible for $H=1$ (i.e., multi-armed bandit) or with a sampling simulator, establishing a stark separation between those settings and the RL setting.

AISTATS 2022 camera ready version

References in corpus (15)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Provably Efficient Maximum Entropy Exploration
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Fast active learning for pure exploration in reinforcement learning
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Reward-Free Exploration for Reinforcement Learning
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• $Q$-learning with Logarithmic Regret
• Task-agnostic Exploration in Reinforcement Learning
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Adaptive Reward-Free Exploration
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity

Cited by in corpus (2)

• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Adaptive Multi-Goal Exploration