Adaptive Multi-Goal Exploration

Abstract

We introduce a generic strategy for provably efficient multi-goal exploration. It relies on AdaGoal, a novel goal selection scheme that leverages a measure of uncertainty in reaching states to adaptively target goals that are neither too difficult nor too easy. We show how AdaGoal can be used to tackle the objective of learning an $\epsilon$-optimal goal-conditioned policy for the (initially unknown) set of goal states that are reachable within $L$ steps in expectation from a reference state $s_0$ in a reward-free Markov decision process. In the tabular case with $S$ states and $A$ actions, our algorithm requires $\tilde{O}(L^{3}SA{\epsilon }^{-2})$ exploration steps, which is nearly minimax optimal. We also readily instantiate AdaGoal in linear mixture Markov decision processes, yielding the first goal-oriented PAC guarantee with linear function approximation. Beyond its strong theoretical guarantees, we anchor AdaGoal in goal-conditioned deep reinforcement learning, both conceptually and empirically, by connecting its idea of selecting "uncertain" goals to maximizing value ensemble disagreement.

arXiv commentAISTATS 2022

References in corpus (23)

• Visual Reinforcement Learning with Imagined Goals
• Provably Efficient Maximum Entropy Exploration
• Maximum Entropy-Regularized Multi-Goal Reinforcement Learning
• Conservative Contextual Linear Bandits
• Unsupervised Control Through Non-Parametric Discriminative Rewards
• Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning
• Fast active learning for pure exploration in reinforcement learning
• Reward-Free Exploration for Reinforcement Learning
• Active Exploration in Markov Decision Processes
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Minimax Regret for Stochastic Shortest Path
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Learning Stochastic Shortest Path with Linear Function Approximation