Adaptive Multi-Goal Exploration

arXiv 2111.12045 ↗First posted 23 Nov 2021cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

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 ε-optimal goal-conditioned policy for the (initially unknown) set of goal states that are reachable within L steps in expectation from a reference state s0 in a reward-free Markov decision process. In the tabular case with S states and A actions, our algorithm requires tildeO(L3 S A ε-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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 49 of its 75 references that are in the map. First posted on arXiv 23 Nov 2021.

Builds on

49 of 75 references.

References · 49

2015Continuous control with deep reinforcement learningcited by 3,279
2017Hindsight Experience Replaycited by 1,096
2018Exploration by Random Network Distillationcited by 966
2016Deep Exploration via Bootstrapped DQNcited by 518
2017Minimax Regret Bounds for Reinforcement Learningcited by 500
2018Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Researchcited by 256
2020First return, then explorecited by 256
2017Automatic Goal Generation for Reinforcement Learning Agentscited by 252
2018Visual Reinforcement Learning with Imagined Goalscited by 248
2018Provably Efficient Maximum Entropy Explorationcited by 240
2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199

37 more

2019Search on the Replay Buffer: Bridging Planning and Reinforcement Learningcited by 188
2020Reward-Free Exploration for Reinforcement Learningcited by 177
2019Skew-Fit: State-Covering Self-Supervised Reinforcement Learningcited by 171
2020SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learningcited by 150
2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
2018Unsupervised Control Through Non-Parametric Discriminative Rewardscited by 102
2020Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learningcited by 100
2020Fast active learning for pure exploration in reinforcement learningcited by 92
2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
2020Automatic Curriculum Learning through Value Disagreementcited by 86
2020Autotelic Agents with Intrinsically Motivated Goal-Conditioned Reinforcement Learning: a Short Surveycited by 83
2018CURIOUS: Intrinsically Motivated Modular Multi-Goal Reinforcement Learningcited by 78
2020Adaptive Reward-Free Explorationcited by 77
2019Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discoverycited by 65
2016Conservative Contextual Linear Banditscited by 56
2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
2019Maximum Entropy-Regularized Multi-Goal Reinforcement Learningcited by 39
2020Task-agnostic Exploration in Reinforcement Learningcited by 37
2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
2021Minimax Regret for Stochastic Shortest Pathcited by 30
2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
2019Active Exploration in Markov Decision Processescited by 27
2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
2020Active Model Estimation in Markov Decision Processescited by 20
2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
2020Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learningcited by 11
2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
2020Improved Sample Complexity for Incremental Autonomous Exploration in MDPscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 1; 2026: 1.

4 papers.

2025DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learningcited by 11
2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
2023Layered State Discovery for Incremental Autonomous Explorationcited by 0
2026SUN: Reaching for Novelty in Reinforcement Learningcited by 0