Gap-Dependent Unsupervised Exploration for Reinforcement Learning

2021/08/11 by Jingfeng Wu, Wu, Jingfeng, Vladimir Braverman +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems #Reinforcement Learning in Robotics #cs.LG

paper · pdf · doi:10.48550/arxiv.2108.05439

AISTATS 2022 camera ready version

openalex publication_date 2021/08/11 · arxiv created 2022/03/14 · arxiv updated 2022/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ∝\widetildeO(1/ε²), where ε>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, ρ>0, to reduce the amount of exploration. In particular, for an unknown finite-horizon Markov decision process, the algorithm takes only \widetildeO (1/ε⋅ (H³SA / ρ+ H⁴ S² A) ) episodes of exploration, and is able to obtain an ε-optimal policy for a post-revealed reward with sub-optimality gap at least ρ, where S is the number of states, A is the number of actions, and H is the length of the horizon, obtaining a nearly quadratic saving in terms of ε. We show that, information-theoretically, this bound is nearly tight for ρ< Θ(1/(HS)) and H>1. We further show that ∝\widetildeO(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.

Citations

• Empirical Bernstein Bounds and Sample Variance Penalization
• Exploration in Structured Reinforcement Learning
• Provably efficient RL with Rich Observations via Latent State Decoding
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Q-learning with Logarithmic Regret
• Adaptive Reward-Free Exploration
• Task-agnostic Exploration in Reinforcement Learning
• 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
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

Cited by

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

Related

• Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning
• On Gap-dependent Bounds for Offline Reinforcement Learning
• Reward-Free Exploration for Reinforcement Learning
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Task-agnostic Exploration in Reinforcement Learning