Adaptive Reward-Free Exploration

Abstract

Reward-free exploration is a reinforcement learning setting studied by Jin et al. (2020), who address it by running several algorithms with regret guarantees in parallel. In our work, we instead give a more natural adaptive approach for reward-free exploration which directly reduces upper bounds on the maximum MDP estimation error. We show that, interestingly, our reward-free UCRL algorithm can be seen as a variant of an algorithm of Fiechter from 1994, originally proposed for a different objective that we call best-policy identification. We prove that RF-UCRL needs of order $(SA{H}^4/{\epsilon }^2)(\log (1/\delta )+S)$ episodes to output, with probability $1-\delta$, an $\epsilon$-approximation of the optimal policy for any reward function. This bound improves over existing sample-complexity bounds in both the small $\epsilon$ and the small $\delta$ regimes. We further investigate the relative complexities of reward-free exploration and best-policy identification.

References in corpus (14)

• Count-Based Exploration with Neural Density Models
• #Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
• Variational Information Maximisation for Intrinsically Motivated Reinforcement Learning
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Provably Efficient Maximum Entropy Exploration
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Reward-Free Exploration for Reinforcement Learning
• Task-agnostic Exploration in Reinforcement Learning
• Information Theoretically Aided Reinforcement Learning for Embodied Agents
• Autonomous exploration for navigating in non-stationary CMPs
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity
• Near-optimal Regret Bounds for Stochastic Shortest Path

Cited by in corpus (8)

• Fast active learning for pure exploration in reinforcement learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings