# Adaptive Multi-Goal Exploration

arXiv: https://arxiv.org/abs/2111.12045 · HTML: https://mlsanity.com/paper/2111.12045/

## Key facts

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

## Builds on (most cited first, 30 of 49)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research](https://mlsanity.com/paper/1802.09464/) (2018)
- [Automatic Goal Generation for Reinforcement Learning Agents](https://mlsanity.com/paper/1705.06366/) (2017)
- [Visual Reinforcement Learning with Imagined Goals](https://mlsanity.com/paper/1807.04742/) (2018)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Skew-Fit: State-Covering Self-Supervised Reinforcement Learning](https://mlsanity.com/paper/1903.03698/) (2019)
- [SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning](https://mlsanity.com/paper/2007.04938/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Unsupervised Control Through Non-Parametric Discriminative Rewards](https://mlsanity.com/paper/1811.11359/) (2018)
- [Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning](https://mlsanity.com/paper/2007.02832/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Automatic Curriculum Learning through Value Disagreement](https://mlsanity.com/paper/2006.09641/) (2020)
- [Autotelic Agents with Intrinsically Motivated Goal-Conditioned Reinforcement Learning: a Short Survey](https://mlsanity.com/paper/2012.09830/) (2020)
- [CURIOUS: Intrinsically Motivated Modular Multi-Goal Reinforcement Learning](https://mlsanity.com/paper/1810.06284/) (2018)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Dynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery](https://mlsanity.com/paper/1907.08225/) (2019)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)

## Built on by (most cited first, 4 of 4)

- [DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning](https://mlsanity.com/paper/2505.19850/) (2025)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)
- [SUN: Reaching for Novelty in Reinforcement Learning](https://mlsanity.com/paper/2609.08642/) (2026)

## 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.