PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Multi-Goal Exploration

Jean Tarbouriech, Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Michal Valko, Alessandro Lazaric

arXiv:2111.12045v2cs.LGstat.ML

TL;DR

Goal-conditioned reinforcement learning has deep methods but limited theoretical guarantees, even in tabular settings. This paper introduces AdaGoal, which selects goals using uncertainty in reaching them, and derives exploration guarantees for tabular and linear-mixture MDPs. The tabular algorithm has a stated exploration bound of eO(L^3SAε^-2 + L^3S^2Aε^-1).

  • Problem

    Deep goal-conditioned reinforcement-learning methods often lack substantial theoretical understanding and guarantees, even in the tabular setting.

    Source: §1 · p. 2

  • Method

    AdaGoal selects goals by maximizing distance-prediction error subject to an estimated reachability constraint, and is instantiated for tabular and linear-mixture MDPs.

    Source: Design a strategy for unsupervised… · p. 2

  • Results

    The tabular algorithm stops in eO(L^3SAε^-2 + L^3S^2Aε^-1) steps, while the linear-mixture algorithm stops in eO(L^4d^2ε^-2) steps, with high probability.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The paper provides a goal-oriented PAC guarantee with linear function approximation and connects uncertain-goal selection to maximizing value-ensemble disagreement in deep goal-conditioned RL.

    Source: Design a strategy for unsupervised… · p. 2

    The analysis still assumes a finite state space, and AdaGoal-UCRL·VTR's computational complexity scales with the number of goals G.

    Source: §4 · p. 7

Abstract

from arXiv · show

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 S A \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.

1 INTRODUCTION

Unsupervised goal-conditioned RL requires agents to choose goals and learn policies without extrinsic rewards, but deep methods lack substantial theoretical guarantees and theoretical approaches can be hard to interpret. The paper formalizes multi-goal exploration and introduces AdaGoal to connect interpretable goal selection with theoretical guarantees and deep-RL practice.

1 INTRODUCTION

  • Deep goal-conditioned methods lack substantial theoretical understanding and guarantees, while existing theoretical approaches can be involved and difficult to adapt to deep RL.The paper identifies a gap between the deep and theoretical branches of goal-conditioned RL.Source: §1 · p. 2

Design a strategy for unsupervised goal-conditioned RL

  • The paper seeks a strategy for unsupervised goal-conditioned RL that combines an interpretable structure adaptable to deep RL with strong guarantees under suitable assumptions.The proposed design goals include tabular and linear settings.Source: Design a strategy for unsupervised… · p. 2
  • AdaGoal adaptively selects intermediate-difficulty goals, supports a stopping rule, and underlies tabular and linear-mixture algorithms with theoretical guarantees.The paper also connects uncertain-goal selection to maximizing value-ensemble disagreement in deep goal-conditioned RL.Source: Design a strategy for unsupervised… · p. 2

1.1 Additional Related Work

  • Reward-free exploration and task-agnostic exploration address other exploration settings, but do not extend to stochastic-shortest-path goal-reaching tasks.The paper also notes that standard regret-to-PAC conversion does not generally apply to single-goal stochastic shortest-path learning.Source: §1.1 · p. 3

2 MULTI-GOAL EXPLORATION

Multi-goal exploration seeks an accurate goal-conditioned policy for goals whose expected shortest-path distance from a reference state is within a chosen radius. The paper formalizes this objective, motivates reset-to-start access, and establishes complexity bounds and a linear-mixture extension.

2 MULTI-GOAL EXPLORATION

  • The objective is to learn an accurate goal-conditioned policy for the initially unknown set of goals whose expected shortest-path distance from s0 is at most L.L is the exploration radius of interest around s0.Source: §2 · p. 3
  • A known reset action returning every state to s0 supports the objective; without it, some instances require exponentially more steps than the reset-enabled setting.With reset, MGE can be solved in polynomial steps in S, L, ε^-1, and A.Source: §2 · pp. 3–4
  • Any PAC algorithm for MGE requires at least Ω(L^3SAε^-2) exploration steps in some instances.The lower bound is stated in expectation.Source: §2 · p. 4
  • Linear-mixture MDPs model transitions as mixtures of d signed basis measures, motivating analysis beyond sample-complexity bounds that scale with SA.The paper focuses its function-approximation analysis on this model.Source: §2 · p. 4

3 OUR AdaGoal APPROACH

AdaGoal alternates between selecting a goal and executing an optimistic goal-conditioned policy, using distance and error estimates to target goals with high uncertainty that remain within the exploration radius. It stops when candidate-goal errors meet the accuracy threshold, and its grid-world illustration shows it targeting the reliably reachable frontier.

3 OUR AdaGoal APPROACH

  • The distance estimate D and error bound E guide selection toward uncertain goals, while goals judged too easy or too hard receive low prediction error.The selection objective adaptively samples the frontier of learning.Source: §3 · pp. 5–6
  • AdaGoal selects a goal maximizing its distance-prediction error among states whose estimated distance from s0 is no greater than L.The algorithm alternates goal selection with H-step optimistic policy execution, then resets to s0.Source: §3 · pp. 4–5
  • The algorithm stops when every goal satisfying the AdaGoal distance constraint has prediction error below ε, then outputs those candidate goals and their optimistic policies.The output candidate goals are paired with associated goal-reaching policies.Source: §3 · p. 6
  • In the two-room grid world, AdaGoal discards the rarely accessible second room and targets first-room states furthest from s0, at the reliable-reachability fringe.The figure tracks goal-sampling frequency over 1000 episodes of length H = 50 with L = 40; access to the second room from s0 has probability η = 0.001.Source: §3 · p. 6, Figure 1 · p. 6

4 SAMPLE COMPLEXITY GUARANTEES

The paper proves sample-complexity guarantees for AdaGoal in tabular and linear mixture MDPs, including a nearly minimax-optimal tabular bound and the first goal-oriented PAC guarantee with linear function approximation.

Guarantee for AdaGoal-UCBVI

  • For ε ∈ (0, 1/S], AdaGoal-UCBVI has sample complexity eO(L^3SAε^-2) with probability at least 1−δ, and is nearly minimax optimal for small enough ε up to logarithmic terms.The theorem covers the full state space as the goal space; the results extend to any G ⊆ S.Source: §4 · p. 6

Curriculum for unknown L

  • Without a pre-specified exploration radius L, an increasing-L curriculum has sample complexity, up to a logarithmic factor, matching AdaGoal-UCBVI run at the final L.The paper states this for successive executions over an increasing sequence of L values.Source: §4 · p. 6

Guarantee for AdaGoal-UCRL·VTR

  • AdaGoal-UCRL·VTR provides the first goal-oriented PAC guarantee with linear function approximation for linear mixture MDPs.Its sample-complexity bound is stated in Theorem 11, with d denoting the feature-mapping dimension.Source: §4 · p. 7

Limitations

  • The linear-mixture result still assumes a finite state space, and its computational complexity scales with the goal-space size G.The stated bound also contains a log(G) factor; the authors identify learning beyond finite state spaces as future work.Source: §4 · p. 7

5 ANALYSIS OVERVIEW

The analysis turns finite-horizon exploration guarantees into guarantees for the original goal-reaching objective. It combines optimistic estimates and error bounds with AdaGoal’s test for candidate-goal membership and a reset action.

Optimism and gap bounds

  • With high probability, the estimates D are optimistic for finite-horizon goal-conditioned values, while E upper-bounds the corresponding gaps.These properties are the stated starting point for proving the guarantees for both AdaGoal-UCBVI and AdaGoal-UCRL·VTR.Source: §5 · pp. 7–8

Bounding the sample complexity

  • The sample-complexity proof bounds the terminating episode count by combining cumulative gap bounds with the stopping condition; the resulting high-probability costs are eO(L^3SAε^-2 + L^3S^2Aε^-1) for AdaGoal-UCBVI and eO(L^4d^2ε^-2) for AdaGoal-UCRL·VTR.The episode horizon is H = eO(L), and total interaction steps are (H + 1) times the episode count.Source: §5 · pp. 7–8

Connecting to the original MGE objective

  • The finite-horizon candidate policy is expanded into an infinite-horizon policy by using the reset action every H steps.For goals in GL+ε, the construction begins with a near-optimal policy from the finite-horizon reduction.Source: §5 · p. 8
  • A goal satisfying Dk(g) ≤ L and Ek(g) ≤ ε belongs to GL+ε with probability at least 1−δ, providing a computable test for the unknown relevant-goal set.The analysis uses this condition to ensure that its finite-horizon-to-goal-reaching argument applies to candidate goals.Source: §5 · p. 8

6 OPERATIONALIZING AdaGoal IN DEEP RL

In deep goal-conditioned RL, AdaGoal’s uncertainty-based selection is approximated with disagreement among goal-conditioned Q-functions. Experiments report better learning than HER’s uniform goal sampling, especially when the training goal space exceeds the test goal space.

6 OPERATIONALIZING AdaGoal IN DEEP RL

  • Adaptive goal sampling outperforms HER’s uniform sampling on FetchPush and FetchPickAndPlace, especially when Gtrain is larger than Gtest.Figure 2 reports success rate on Gtest using the latest policy trained on Gtrain; shaded regions show confidence over five random seeds.Source: Figure 2 · p. 9, §6 · p. 9
  • The deep-RL approximation measures E(g) as the standard deviation of an ensemble of randomly initialized goal-conditioned Q-function values.Because maximizing over a large G is expensive, the procedure first uniformly samples candidate goals.Source: §6 · pp. 8–9
  • Approximating H ≈ L makes AdaGoal’s constraint always valid and recovers the goal-sampling scheme of VDS, paired with HER’s uniform sampling.The experiment models misspecification by expanding Gtrain while leaving Gtest unchanged.Source: §6 · p. 9
  • In the misspecified-space experiment, adaptive sampling can discard goals in Gtrain \ Gtest that cannot be reached and would hinder learning when conditioned on.The authors present this result as empirical corroboration of AdaGoal’s ability to adapt to an unknown target goal set.Source: §6 · p. 9

A SHORTCOMINGS OF ALGORITHMIC DESIGNS OF EXISTING THEORETICAL GC-RL METHODS

The section identifies three design shortcomings in existing theoretical GC-RL methods: cumbersome policy execution, a potentially eliminatory goal-selection rule, and non-adaptive stopping. AdaGoal contrasts these with a single fixed-length rollout, implicit targeting of intermediate-difficulty goals, and adaptive goal selection and termination.

A SHORTCOMINGS OF ALGORITHMIC DESIGNS OF EXISTING THEORETICAL GC-RL METHODS

  • Existing methods may run repeated candidate-policy executions with empirical checks after each one, whereas AdaGoal uses one fixed-length rollout before resetting.The next goal may be a different, more relevant candidate.Source: A SHORTCOMINGS OF ALGORITHMIC DESIGNS… · p. 13
  • Some methods permanently exclude goals once deemed reliably reachable, while AdaGoal implicitly targets intermediate-difficulty goals without a formal fringe or border.Avoiding an explicit fringe or border may make AdaGoal more amenable to implementation.Source: A SHORTCOMINGS OF ALGORITHMIC DESIGNS… · p. 13
  • Some methods use preset stopping requirements that adapt poorly or not at all to collected samples; AdaGoal instead selects goals and terminates adaptively using data.Examples include minimum sample counts for every state-action pair of interest or minimum counts for selecting a candidate goal.Source: A SHORTCOMINGS OF ALGORITHMIC DESIGNS… · p. 13

B PROOFS

The proofs establish inclusions relating the candidate set X_k to the reachable-goal sets, then use AdaGoal's uncertainty bounds and a decreasing function f_M to bound its termination episode.

B PROOFS

  • For the first set inclusion, every g in G_L lies in X_k because D_k(g) is at most the optimal expected reaching time, which is at most L.The proof takes the limit H → +∞ and invokes Property 1.Source: B PROOFS · p. 14
  • For the second inclusion, every g in X_k has optimal expected reaching time at most L + ε_k, so X_k is contained in G_{L+ε_k}.This follows from Property 2 and the definition of ε_k.Source: B PROOFS · p. 14
  • Before termination, AdaGoal's design ensures ε ≤ E_k(g_k); summing these bounds yields ε ≤ f_M(κ′) for the finite episode index κ′.Because f_M is strictly decreasing, the proof bounds the termination index κ using its inverse.Source: B PROOFS · p. 14

B.1 Proof of Lemma 5

The proof constructs a reset-free MDP family in which learning an ε-optimal policy can require time proportional to the diameter, even when the goal is reliably L-reachable. Its lower bound shows that the diameter can be exponentially larger than L, S, A, and ε^-1.

B.1 Proof of Lemma 5

  • The construction uses a communicating five-state MDP family with goal set {g}, where g is reliably L-reachable from s_0 and the favorable action a† is unknown.The family is parameterized by a†, and the proof considers learning an ε-optimal goal-reaching policy for g.Source: §B.1 · p. 14
  • Until the agent visits e_s, it cannot know which action is favorable there; a policy missing a† can have suboptimality greater than ε.The proof also extends the argument from deterministic to stochastic candidate policies.Source: §B.1 · pp. 14–15
  • The proof bounds the time to visit e_s using its reach probability η and concludes that the required steps are at least 1/(9η) = Ω(D).The construction makes η arbitrarily small while retaining a reliably L-reachable goal.Source: §B.1 · pp. 14–15
  • For L ≥ 2, S ≥ 5, A ≥ 4, and ε ∈ (0, 1], some reset-free MGE instances require Ω(D) steps, with D exponentially larger than L, S, A, and ε^-1.Thus no algorithm can solve these instances in poly(L) steps with overwhelming probability.Source: §B.1 · pp. 14–15

B.2 Proof of Lemma 6

This section proves Lemma 6 for AdaGoal-UCBVI, deriving the multi-goal lower bound from a single-goal SSP identification lower bound and outlining the goal-conditioned models and proof tools. It establishes optimism and gap bounds, controls cumulative gaps, and uses them to derive a high-probability MGE sample-complexity guarantee.

B.2 Proof of Lemma 6

  • A lower bound for identifying an ε-optimal policy for one reliably L-reachable goal transfers to the multi-goal exploration objective with a singleton goal set.The proof constructs a hard SSP family and extends it to S states to obtain the state-dependent sample-complexity factor.Source: §B.2 · pp. 15, 17
  • The hard SSP construction uses an anytime reset, and its per-step unit cost lets absorption at s0 compound errors to produce L^3 rather than L^2 dependence.The proof also converts episode counts to time steps using Wald’s equation.Source: §B.2 · pp. 16–17

C.1 Notation

  • For each goal, the analysis defines a unit-cost SSP model with a self-loop at that goal and a finite-horizon version in which the goal is absorbing.The goal-conditioned costs are known, while the transitions are unknown and differ from the original MDP by the goal-specific self-loop.Source: §C.1 · p. 18

C.2 Algorithmic Choices of D, E, Q for AdaGoal-UCBVI

  • AdaGoal-UCBVI generalizes BPI-UCBVI estimates to goal-conditioned models, using optimistic and pessimistic value estimates to define its distance and error estimates.The estimates are constructed in finite-horizon models for each goal.Source: §C.2 · p. 19

C.3 Proof of Theorem 8

  • The proof extends finite-horizon BPI analysis to goal-conditioned exploration, while its technical novelty is the AdaGoal goal-selection step.Because value vectors vanish at the goal, the analysis can use the original MDP’s transition probabilities rather than goal-conditioned transition probabilities.Source: §C.3 · pp. 19–20

C.3.1 Proof of “key step x”

  • The concentration proof combines events for transition estimates, pseudo-counts, and optimal goal-conditioned value estimates to obtain a joint event U with probability at least 1 − δ.It applies a union bound over goals when concentrating the optimal goal-conditioned values.Source: §C.3.1 · p. 20
  • The proof establishes that eV g,1 are optimistic estimates of optimal goal-conditioned finite-horizon values and U g,1 upper-bound goal-conditioned finite-horizon gaps.Source: §C.3.1 · p. 21

C.3.2 Proof of “key step y”

  • Lemma 21 controls cumulative gap bounds; stationary transition probabilities and cost functions allow shaving a factor H from the main order term versus Ménard et al. (2021a).Source: §C.3.2 · p. 24

C.3.3 Proof of “key step z”

  • Lemma 23 gives a high-probability MGE sample-complexity bound for AdaGoal-UCBVI, converting the episode bound using τ ≤ (H + 1)κ.The proof uses the horizon choice H ≜ ⌈5(L + 2) log / log(2)⌉.Source: §C.3.3 · pp. 25–26

C.3.4 Proof of “key step {”

The proof connects finite-horizon goal-conditioned planning to goal-reaching policies through resetting, then establishes AdaGoal-UCBVI’s PAC guarantee. The later analysis gives its tabular sample-complexity bound and describes the linear-mixture estimators.

C.3.4 Proof of “key step {”

  • Resetting a near-optimal finite-horizon policy yields a near-optimal goal-reaching policy in M_g when g∈G_O(L+ε) and H is large enough.The resetting policy executes the original policy for H steps, then takes the reset action if the goal has not been reached.Source: §C.3.4 · p. 27
  • With probability at least 1−δ, any goal with D_k(g)≤L and E_k(g)≤ε belongs to G_L+ε, supporting the algorithm’s termination guarantee.At termination, the candidate set is bracketed between G_L and G_L+ε, and candidate policies are ε-optimal for the original SSP objective.Source: §C.3.4 · pp. 28–29

C.4 Putting everything together

  • With probability at least 1−δ, AdaGoal-UCBVI is (ε, δ, L, S)-PAC with MGE sample complexity eO(L^3SAε^-2) for ε∈(0,1/S].The eO notation hides poly-logarithmic terms in ε^-1, S, A, L, and δ^-1.Source: §C.4 · p. 29

D DETAILS OF AdaGoal-UCRL·VTR AND ANALYSIS

D.1 Overview of AdaGoal-UCRL·VTR and Choice of E, D, Q in line 14 of Algorithm 1

  • AdaGoal-UCRL·VTR uses value-targeted ridge regression for D and Q, and a novel error-targeted regression for E.The second regression targets computable upper bounds on goal-conditioned gaps.Source: §D.1 · p. 30

D.2 Proof sketch of Theorem 11

The proof follows the key steps of the tabular analysis for AdaGoal-UCBVI, establishing confidence events, optimism and gap bounds before using the stopping rule to bound sample complexity. It then connects that bound to the original multi-goal exploration objective.

D.2 Proof sketch of Theorem 11

  • The AdaGoal-UCRL·VTR analysis follows the key steps used for AdaGoal-UCBVI, with the proof of its connection to the original MGE objective identical to the tabular case.The stopping episode κ yields a sample-complexity bound of κ(H + 1), with H = eO(L).Source: §D.2 · pp. 31, 33
  • High-probability self-normalized concentration events place the goal-specific parameters in confidence ellipsoids, with a union bound over goals.The events hold with probability at least 1 − 2δ/3.Source: §D.2 · pp. 31–32
  • Under those events, optimism bounds Qg,k,h(s, a) by Q⋆g,h(s), and induction establishes Wg,k,h(s) ≤ Ug,k,h(s).The induction uses monotonicity of the transition operator, Cauchy–Schwarz, and the stated event.Source: §D.2 · p. 32
  • The cumulative gap bounds use telescoping, Cauchy–Schwarz, the elliptical potential lemma, and an Azuma–Hoeffding bound for a martingale-difference term.The proof bounds Z1 and Z2 using the elliptical potential lemma and Z3 using Azuma–Hoeffding.Source: §D.2 · pp. 32–33
  • The stopping rule terminates at episode κ, and bounding exploration steps by κ(H + 1) gives the stated sample-complexity conversion.The proof uses H = eO(L).Source: §D.2 · p. 33

E ABLATION OF THE GOAL SELECTION SCHEME & PROOF OF CONCEPT EXPERIMENT

The ablation contrasts uniform and rarity-based goal sampling with AdaGoal, while the grid-world experiment illustrates how their goal choices differ as learning proceeds. The comparisons highlight the cost of sampling goals that are too easy or too difficult and the challenge of varying reachability.

E ABLATION OF THE GOAL SELECTION SCHEME & PROOF OF CONCEPT EXPERIMENT

  • UniGoal samples uniformly from states other than s0, whereas RareGoal samples in proportion to goal rarity, represented in the tabular case by inverse visitation count.The related deep-RL examples include uniform goal sampling and Skew-Fit's rarity-weighted sampling.Source: E ABLATION OF THE GOAL SELECTION… · pp. 34–35
  • UniGoal has sample complexity at most eO(L^3 S^2 A ε^-2), paying an extra S because goals may be too easy or too hard to inform learning.In the worst case, there may be S − 2 such non-informative goals.Source: E ABLATION OF THE GOAL SELECTION… · p. 35
  • RareGoal relies on a communicating assumption and can waste samples prioritizing very hard-to-reach goals when goal reachability varies.The passage notes a possible poly(S, A, D, ε^-1) sample requirement and identifies high stochasticity as an example of varying reachability.Source: E ABLATION OF THE GOAL SELECTION… · p. 35
  • Over learning, AdaGoal discards goals in the extremely hard-to-reach bottom-right room and targets the furthest reliably reachable states in the first room.The comparison tracks goal-sampling frequencies across 1000 episodes in three episode windows.Source: E ABLATION OF THE GOAL SELECTION… · p. 35

F IMPLEMENTATION DETAILS OF SECTION 6

The implementation approximates AdaGoal with goal-conditioned Q-function ensemble disagreement and uses a separate policy module for goal-conditioned execution. It also specifies the ensemble training setup and key hyperparameters.

F IMPLEMENTATION DETAILS OF SECTION 6

  • AdaGoal is approximated by selecting among N uniformly sampled goals in proportion to the standard deviation of an ensemble of J goal-conditioned Q-functions.This procedure recovers the VDS algorithm; the ensemble module is separate from policy optimization.Source: F IMPLEMENTATION DETAILS OF SECTION 6 · p. 35
  • Each ensemble Q-function receives Bellman updates from independently sampled mini-batches, while the goal-conditioned policy is updated with DDPG.Each Q-function uses a target network.Source: F IMPLEMENTATION DETAILS OF SECTION 6 · p. 35
  • The ensemble uses J = 3 and N = 1000, with learning rate 1e-3, Polyak coefficient 0.95, buffer size 1e6, and batch size 1000.The policy executes each selected goal for an episode of length H = 50.Source: F IMPLEMENTATION DETAILS OF SECTION 6 · p. 35
Loading 2111.12045v2…