Fast active learning for pure exploration in reinforcement learning

Abstract

Realistic environments often provide agents with very limited feedback. When the environment is initially unknown, the feedback, in the beginning, can be completely absent, and the agents may first choose to devote all their effort on exploring efficiently. The exploration remains a challenge while it has been addressed with many hand-tuned heuristics with different levels of generality on one side, and a few theoretically-backed exploration strategies on the other. Many of them are incarnated by intrinsic motivation and in particular explorations bonuses. A common rule of thumb for exploration bonuses is to use $1/\sqrt{n}$ bonus that is added to the empirical estimates of the reward, where $n$ is a number of times this particular state (or a state-action pair) was visited. We show that, surprisingly, for a pure-exploration objective of reward-free exploration, bonuses that scale with $1/n$ bring faster learning rates, improving the known upper bounds with respect to the dependence on the horizon $H$. Furthermore, we show that with an improved analysis of the stopping time, we can improve by a factor $H$ the sample complexity in the best-policy identification setting, which is another pure-exploration objective, where the environment provides rewards but the agent is not penalized for its behavior during the exploration phase.

References in corpus (10)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• 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
• Adaptive Reward-Free Exploration
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity

Cited by in corpus (19)

• Exploration in Deep Reinforcement Learning: A Survey
• Active learning for data streams: a survey
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Practical Active Learning with Model Selection for Small Data
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Navigating to the Best Policy in Markov Decision Processes
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Task-Optimal Exploration in Linear Dynamical Systems
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge
• Adaptive Multi-Goal Exploration
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings