DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning
Authors: Leander Diaz-Bone
Marco Bagatella
Jonas Hübotter
Andreas Krause
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning
test-time training
test-time reinforcement learning
sparse-reward reinforcement learning
goal selection
goal-conditioned reinforcement learning
exploration
exploration-exploitation
upper confidence bound
Primary area: reinforcement_learning
TL;DR: We develop DISCOVER, which enables RL agents to solve substantially more challenging tasks than previous exploration strategies in RL.

Abstract: Sparse-reward reinforcement learning (RL) can model a wide range of highly complex tasks.
Solving sparse-reward tasks is RL's core premise — requiring efficient exploration coupled with long-horizon credit assignment — and overcoming these challenges is key for building self-improving agents with superhuman ability.
We argue that solving complex and high-dimensional tasks requires solving simpler tasks that are *relevant* to the target task.
In contrast, most prior work designs strategies for selecting exploratory tasks with the objective of solving *any* task, making exploration of challenging high-dimensional, long-horizon tasks intractable.
We find that the sense of direction, necessary for effective exploration, can be extracted from existing reinforcement learning algorithms, without needing any prior information.
Based on this finding, we propose a method for _**di**rected **s**parse-reward goal-**co**nditioned **ve**ry long-horizon **R**L_ (DISCOVER), which selects exploratory goals in the direction of the target task.
We connect DISCOVER to principled exploration in bandits, formally bounding the time until the target task becomes achievable in terms of the agent's initial distance to the target, but independent of the volume of the space of all tasks.
Empirically, we perform a thorough evaluation in high-dimensional simulated environments. We find that the directed goal selection of DISCOVER solves exploration problems that are beyond the reach of prior state-of-the-art exploration methods in RL.

DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning
Leander Diaz-Bone"
Marco Bagatella*1z
Jonas Hübotter*' Andreas Krause'
'ETH Zürich, Switzerland
Max Planck Institute for Intelligent Systems, Germany
Abstract
Sparse-reward reinforcement learning (RL) can model wide range of highly com- plex tasks. Solving sparse-reward tasks is RL's core premise-requiring efficient exploration coupled with long horizon credit assignment- and overcoming these challenges is key for building self improving agents with superhuman ability. Prior work commonly explores with the objective of solving many sparse-reward tasks, making exploration of individual high-dimensional, long-horizon tasks intractable. We argue that solving such challenging tasks requires solving simpler tasks that are relevant to the target task, i.c., whose achieval will teach the agent skills required for solving the target task. We demonstrate that this sense of direction, necessary for effective exploration, can be extracted from existing RL algorithms, without leveraging any prior information. To this end, we propose method for directed sparse-rewad reward noal-conditioned very long-hooe ang-horizon RL (DISCOVER), which selects exploratory goals in the direction of the target task. We connect DISCOVER to principled exploration in bandits, formally bounding the time until the target task becomes achievable in terms of the agent's initial distance the target, but independent of the volume of the space of all tasks. We then perform thorough evaluation high nigh-dimensional environments. We find that the directed goal selection of DISCOVER solves exploration problems that are beyond the reach of prior state-of-the-an art exploration methods RL.
Average success rate simple
Average
hard
Success Rate
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.4
0.6
1.0
0.0
0.2
0.4
0.6
1.0
Normalized environment interactions
Normalized cavironment interactions
Standard RL Curiosity
Direction
Achievability Novelty
DISCOVER
Figure 1: Given hard task, compare agents learning to solve this target task by learning from the experience on simpler exploratory tasks. DISCOVER uses a bootstrapped sense of direction to design curriculum of achievable and novel exploratory tasks that are relevant to the target task. In this way, the agent bootstraps to solve much harder tasks than if using other methods for selecting exploratory tasks, such considering only direction only achievability and novelty. State-of-the-an standard RI. algorithms using intrinsic curiosity for exploration fail to achieve our target tasks at all.
'Equal contribution. Correspondence to Leander Diaz-Bone <ldiazbone@@elle @tth
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Reinforcement learning (RL) provides a general framework in which agents have to learn complex tasks by interacting with their environment to maximize rewards [75]. Although RL has led to breakthroughs in many domains such Atari games [45], board games [e.g.. 66], and reasoning [26], sparse-reward problems, in which a reward is only observed once the task is completed, remain very challenging [38, 80]. These sparse-reward tasks hard to solve as the agent needs gain deep understanding of the environment without ever observing a reward. As such, and since they are natu- rally defined without any human supervision, solving sparse-reward tasks is one of the core premises of RL. We focus on the setting where the agent is given single sparse-reward problem to solve. In sparse-reward RL, traditional methods from RL fail as they need to randomly observe the reward signal to make progress, which becomes exceedingly unlikely in long-horizon tasks [e.g., 49, 87J.
One technique for overcoming this challenge is to frame sparse- reward tasks as multi-goal problems, which enables the agent to learn about harder goals by generalizing from already learned simpler goals [63, 5]. In this framework, a goal needs to be specified for the policy in each episode. This goal selection step plays a crucial role in guiding the exploration of the agent [53]]. Choosing a goal essentially presents its own exploration-exllotatio dilemma the agent try to pursue its final goal or rather aim to reach novel, but achievable intermediate goals, expanding its horizon of expertise? Previously introduced goal selection strategies have focused largely on either exploration [e.g.. 53] or exploitation [5].
higher level of abstraction: should
In this work, we argue that goal selection should naturally address this trade-off, considering both the novelty of commanded goals, and thus their exploration potential, as well as their relevance to the final objective, while considering their achievability. We propose DISCOVER, method for effectively balancing achievability, relevance, and novelty during goal selection. We find that these quantities can be estimated by commonly used critic networks in standard deep RL algorithms. We learn an ensemble of critics to estimate the agent's uncertainty about the direction of the final task. Intuitively, DISCOVER leverages these value estimates to determine which intermediate goals most useful towards learning to solve the final task. We find that DISCOVER enables RL agents to solve substantially more challenging tasks than previous exploration strategies in RL.
We further provide a formal analysis of DISCOVER, showing that it is closely linked to upper confidence bound (UCB) sampling [68]. method for balancing exploration and exploitation in sequential decision-making We use this connection to prove bounds on the number of episodes until the final task becomes achievable. Unlike bounds in prior work, our bound for DISCOVER is independent of the volume of the space of all goals and depends linearly on the "shortest distance" between the agent's initial state and the state at which the final task is achieved. We follow this formal discussion by an extensive evaluation of DISCOVER in three complex sparse-reward environments, ranging from loco-navigation to manipulation. We observe significant improvements in sample efficiency compared to previous state-of-the-art exploration strategies in RL.
Our contributions are:
1. We propose DISCOVER, a novel goal selection strategy for solving hard tasks. By leveraging its connections to UCB, we theoretically analyze the time until the final task becomes achievable.
2. We evaluate the empirical performance of DISCOVER on various complex control tasks and show substantially improved performance compared to state-of-the-as goal selection strategies.
3. We perform range of ablation studies, including on the utilization of prior knowledge and on the importance of balancing achievability, novelty, and relevance in goal selection.
2 Related Work
Exploration in RL Exploration has been central challenge in reinforcement learning since its inception. Uninformed exploration strategies, such as c-greedy [44] or uncorrelated noise injection [24], are crucial to the success of most practical algorithms. Further improvements can be obtained by leveraging temporally extended strategies [19], or informed criteria, such as curios- ity [52, 27, 61, 70, 71]. diversity [21], count-based strategies [77, 10]. unsupervised environment design [82, 17]. These strategies are normally applied without any extrinsic signal [43, 61, 70, 51], or in linear combination with specific reward signal as defined by the MDP [10, 71]; in the latter

---

case, balancing the two terms is often complex. This work focuses instead on setting in which exploration instead achieved by attempting to solve different goals than the target goal, i.c., through exploitation with respect to a different reward, as specified in the next paragraph.
Finding solvable subgoals for exploration Solving many sparse-reward problems with RL has often been formalized goal-conditioned [22, 58] goal-reaching [83] RL, where we jointly learn a policy for all tasks. A key contribution can be traced back to Schaul et al. [63], which introduces universal value function estimators, capable of estimating returns for multiple goals. To learn these functions efficiently. Andrychowicz et al. [5] proposes a goal relabeling scheme to provide signal for goals that achieved in hindsight. Further works have explored emerging properties of goal- conditioned value functions, introducing contrastive [22, 9] or quasimetric [83, 18, 3] approaches. Interestingly, conlicondi approaches enable the design of nuanced exploration strategies. as the policy can be controlled through its coalionnitioning [56, 85, 53, 23, 69, 86, 35, 43, These methods strategically select goal from the previously achieved goals. After the goal achieved, the methods enter pure exploration phase, in line with the successful exploration strategy proposed by Ecoffet et al. [20]. However, previous methods are generally not directed towards a particular target goal, with some exceptions relying on strong assumptions on the distance metric [57], or on additional costly components such as generative [40, 62] or discriminative [12, 11] models. In contrast, DISCOVER introduces a notion of relevance during exploration, which is fully bootstrapped from the agent's own estimates and experience, leading to deep exploration. We further discuss the connection of DISCOVER to other work such as self-play in Appendix A.
Test-time training We consider the setting where the agent's 'sss objective is to solve a single, chal- lenging target task provided at "test-time", potentially starting from a pre-trained prior. This is form of test-time training (TTT) [73]. where an agent is trained specifically for the target task at test-time. TTT on (self-) supervisue signals over few gradient updates has shown success in domains such as control [32], language modeling [33, 36, 74, 8], abstract reasoning [4], and video generation [15]. More recently, test-time reinforcement learning (TTRL) [88] has used RI iteratively self-improve an agent's policy for initially unsolvable tasks, using its own experience on simpler tasks. To our knowledge, DISCOVER is the first method demonstrating effective TTRL with extensive self-supervised exploration (millions of steps), thereby enabling agents to solve highly difficult tasks.
3 Problem Setting
We consider the sparse-reward reinforcement learning setting and adopt the goal-conditioned formula- tion [75, 63], formally described by multi-goal Markov decision process M = (S, A, p. un, G.g") Here S, and G S S denote the set of states, actions, and goals. respectively. Additionally, P x A + A(S) are the transition probabilities and μo is the initial state distribution. In the following, we denote by so a random initial state sampled from po. The target goal, denoted by g*. is the only goal we evaluate on and therefore aim to learn. The sparse goal-conditioned reward implicitly defined as r(s, a; = (ss & Sy} [54], where Sg S is the subset of the states, for which the goal g is achieved. We consider the general case, where this subset is defined as d(s, g) S c). Here, d defines standard distance metric. possibly only considering some parts of the state, such as position. A goal is considered achieved during training if we have previously observed a non-negative reward for this goal. We keep track of the set of achieved goals Gach, which contains all previously achieved goals (initially Gach {sn)). In practice, this is implemented by maintaining a replay buffer of observed states. We consider a fixed episode length H, with the episode terminating once the target goal is reached. The objective of the agent is to learn goal-conditioned policy π : :S x G + (AA) that maximizes its value function V (50. g²).
S, fs
(s* = E, - ΣHT' H-1 1sse & Syyt' st]] sty
We denote the optimal policy by n'' S (AA) and use Tg 8 A(A) denote the policy conditioned on
3.1 Goal Selection for Sparse- RL.
The standard non-goal-conditione online RI. loop collects data according to the current policy, often with noise injection [19]. In the goal-conditioned framework, the agent can additionally control
3

---

Gach
acch
acch
guch
50
50
g
g
HER
Uniform (DISCERN)
MEGA
DISCOVER
Illustration of the goal selection of DISCOVER compared to prior goal selection strategies. The white cross represents the initial state of the agent, the red cross represents the target goal. The blue shaded area symbolizes the set of achieved goals Gach- lighter blue corresponds to harder to reach goals. Finally, the black crosses represent the kinds of goals selected by each strategy.
Figure 2:
the coaliiondiii of the policy, i.e., it may pursue arbitrary goals for data collection. We adopt the framework of Pitis et al. [53], and summarize its main steps in Algorithm 1. In each episode, SelectGoal commands a goal to the agent, based on prior experience, the current state of the agent and the final target goal g². We then roll out the policy conditioned on gr until Øe is achieved. After achieving the goal It, the agent enters random exploration phase, during which it selects actions uniformly at random until the end of the episode. We add the resulting trajectory to the replay buffer. Finally, update the agent's ' parameters / using off-policy RL algorithm, by sampling from the replay buffer and relabeling goals, as proposed by Andrychowicz et al. [5]. The focus of this work is SelectGoal, which designs the agent's currieulum. Next, introduce DISCOVER, which selects a curriculum specifically targeted to g"
Algorithm 1 Goal-conditioned Reinforcement Learning
1: Initialize: replay buffer: Bo 0, actor-critic parameters: 0o
2: for = 2.... do
select goal ge for episode > add trajectory to replay buffer 5: 0, f- Upcatteflalbbollo11ss$sspp(((111 0,-1) using off-policy RL (e.g., TD3 [24])
3: 9t f- SBllectGoa
4: B, f B (oollot(ooll
4 DISCOVER
We introduce DISCOVER, method for solving hard tasks that require deep exploration. We focus on the problem of finding intermediate, solvable goals that the agent should attempt to acquire skills, eventually enabling it to achieve the target goal. We begin by presenting an intuitive explanation of the DISCOVER objective, followed by discussion of its tight connection the exploration-exploitttoo exploitation dilemma. We argue that, to efficiently learn to solve hard tasks, agent must adhere to the following three fundamental principles:
Goal utility- = Achievability + Novelty + Relevance
(2)
Each of these principles is necessary to efficiently learn to solve a hard task. First, achievability ensures that task is not "too hard" for the agent ever achieve hence, representing meaningful ex- perience. Second, novelty ensures that task is not "too easy", such that the agent's 's new experience on this task a useful learning signal increase the policy's 's capabilities. Finally, relevance ensures that experience on task is useful for eventually solving the target task (cf. Figure 2). Prior methods [e.g.. 53) have successfully combined achievability and novelty, are aiming achieve all possible tasks.
After providing an intuitive discussion of the principles relevant to efficiently learning hard tasks, the question remains: how can they be quantified in practice? We propose the DISCOVER objective, which quantifies each of the discussed principles via the value estimate under the current policy, In each exploration episode, select a goal from the achieved ones (Gach) according to
9t arg max as V($0.9) 9) + 3, (50. 9) + (1 - an) V(g.g") + 3.o
(3)
gE9ach Achievability
Novelty
Relevance

---

where og and B, are schedulable coefficients, V is the mean of an ensemble of the optimal value function defined in Equation I, and o² its variance. 2 A high value V( 9) indicates that the policy can reach the goal g from the starting state so, therefore promoting achievability. In contrast, large uncertainty a (8o.g) indicates that the agent not reliably reaching the goal g. Hence, attempting such goals prioritizes novel experiences. Finally, a high value V(g, g") indicates that g is "closely related" to the target goal g². The relevance term of DISCOVER prioritizes goals that might be closely related to the target goal, either since they already have high value V (g. g²) or because the agent is still uncertain about this value. The relevance term can also be viewed as directing the goal selection towards the final target g". Note that while we focus is easily extended to distributions over targets by maximizing Equation (3) in expectation.
single target 9", DISCOVER
We emphasize that all terms in Equation (3) are estimated by the critic and do not rely on any prior information. In particular, the relevance estimates are entirely bootstrapped from the agent's 's current knowledge. While the above gives an intuitive introduction, DISCOVER can be interpreted as an agent seeking to maximize the likelihood of reaching the target goal g". as we describe in Appendix B.
4.1 Automatic Online Parameter Adaptation
Prior work has explored adapting the parameters online to meet predefined metrics, such as the entropy of the policy [28, 71J. In the same spirit, we propose simple online parameter adaptation strategy that adjusts a and Bg to maintain a fixed target goal achievement rate p", similarly to the cutoff strategy proposed in Pitis et al. [53]. This approach aligns with the previously discussed intuition, as it ensures that the agent neither selects goals that are "too easy" nor ones that are "too hard", We find that it is sufficient to linearly increase a when the agent achieved too few of its previously selected goals, and linearly decrease 0g, when the agent achieved too many, while setting 3r = 1:
0t++1 [ + Tppp p)))-
Here, Pt denotes the average goal achievement rate over the last kintapt episodes, [a clips the output value to the interval (a, bj, and > 0 is the adaptation step size, which we set to 0.01. We ablate the effects of our adaptation strategy in Figure 10 in the appendix, and find that the optimal target goal achievement rate p" is approximately 50%, consistent with findings in prior work [53].
4.2 Connection to the Esploration-Exploitaaee
Dilemma
Balancing exploration and exploitation is key when proposing tasks such that the resulting experience is valuable toward solving the target task. DISCOVER balances exploration and exploitation in two ways. First, in its estimate of (( g). which leads to a trade-off between selecting achievable and novel goals. Second, in its estimate of V(g, g²), where exploitation leads to directing goal selection toward the target goal while exploration prevents the agent from overfitting to an overconfident estimate of direction.
To illustrate the underlying off, we consider a simplified setting and use the link between DISCOVER and UCB to prove rates for the number of episodes until the DISCOVER agent can achieve the target goal. We make the following simplifying regularity assumptions, analogously to the linear bandit setting [see, e.g. 2, 13]:
Theoretical guarantee for DISCOVER
trade-
Informal Assumption 4.1 (formalized in Assumptions C.1 to C.5).
1. Optimal value functions are linear in latent features: Among the set of achievable* goals g. the value functions V* V=0,, g) and V* ((gg9 .g") are linear in a known d-dimensional feature space. Note that the above only needs to hold for currently achievable goals.
2. Noisy feedback: In episode selecting any achievable gt, the agent receives noisy feedback of the optimal value functions, with the noise being conditionally sub-Gaussian.
3. Goal space contains optimal paths: For any goal g, the optimal path from g to the target goal g* is contained in the goal space g.
4. Goal achievability: Based on our previous observation that a controls the rate of goal-achieval, we let the probability of achieving any achievable goal g be at least Any goal g is considered
2Sec Appendix E.
"The set of achievable goals is defined in Assumption 4.
'That is. G is 9* geodesically convex under the forward quasimetric induced by the optimal value function.
5

---

achievable in episode & if the agent previously achieved a goal 9v (t' < t) which is within distance (1 - a of g (under the optimal value function). Here, & > 0 is a rate of expansion.
Assumptions and 2 are standard in the literature on linear bandits, Note, however, that in our setting this feedhack model implicitly assumes feedback on V ("(tt which can be thought of as a gener- alization condition: If the agent cannot generalize from its experience from so to about the relation of g and g". then may never reach the target goal g". Another implicit consequence of the linearity assumption is that the bias and -on-stationarity of the value function estimates is controlled, which is not commonly the case when learning value functions with neural networks via bootstrapping. As- sumption 3 is a continuity assumption on the goal space, which is satisfied in many practical settings. Finally, Assumption 4 leads to a trade-off in choosing a: A small a leads to a larger set of achievable goals, but at a lower goal-achieval rate. In contrast, large leads to more conservative set of achiev- able goals, but at a higher goal- achievall rate. This trade-off matches the empirical effect of a (cf. Fig- ure 10 in the appendix). The parameter controls the rate of expansion of the set of achievable goals.
In the above setting, we bound the number of episodes until DISCOVER reaches the target goal g": Informal Theorem 4.2 (formalized in Theorem C.9). Fix any confidence ā (0,1) and any a E (0, 2) Let the above assumptions hold. We denote by D = -Va the distance from the initial state so to the target goal g* under the optimal policy. Then, with probability 1 - 6, selecting goals 9r with DISCOVER (with at = a and Br chosen appropriately), the number of episodes N until the target goal g" is achievable by the agent is bounded by
N S δ 11)-2a)((1-00 a))x33
Ddf
Ō
Ddl A33
This theorem shows that DISCOVER efficiently learns to solve hard, initially unachievable tasks. With larger dimensionality d of the feature space, the learning task becomes harder, which is reflected in the bound. Similarly, the larger the distance D from the initial state to the target goal, the longer it takes to reach the target goal. In contrast, the larger the rate of expansion K, the faster the agent reaches the target goal, since the set of achievable goals expands faster. Finally, the bound suggests choosing Re 0.1 (cf. Figure 7 in the appendix) which roughly matches the average chosen in experiments by our adaptation strategy (cf. Figure 11 in the appendix).
Despite our simplifying assumptions, achieving the target goal 9" remains non-trin non-trivial. The agent must trade off learning the value function against exploiting the direction this value suggests toward g". Overconfidence in the value estimate may lead the agent to diverge and never reach 9". On the other hand, if the agent is too conservative its value estimate (or does not use the value estimate for direc- tion at all), it may never reach the target goal within a reasonable time. To see why guidance matters, imagine an mn-dimensional goal space that is a ball of radius R. Covering that ball with hypercubes of side e requires on the order of (R/c)"" cells, exponential in m. This indicates that to achieve hard goals in a high-dimensional goal space, undirected exploration is insufficient, and the agent must balance exploration and exploitation. In doing so, DISCOVER ER avoids this curse of dimensionality and exploits the learned value to stay close to a nearly one- mie-dimenioonl corridor from so to g*. For this reason, the bound in Informal Theorem 4.2 depends solely on the (I (I-dim) distance D and not on the total volume of the goal space G. Bounds of previous work [78] depend on the total volume of G, and quickly become vacuous in high-dimensional problems.
the-ennelope calculation
5 Results
We evaluate the empirical performance of DISCOVER actoss three complex, sparse-reward, long-horizon control tasks, highlighting five main insights. Unless mentioned otherwise, we employ the TD3 [24] actor-critic algorithm for training all agents. While our evaluation focuses on model-free methods, the goal-based directed exploration of DISCOVER can also be used with model-based backbones such as Dreamer [29, 30, 31]. For all experiments, we report the mean performance across 10 seeds along with its standard error. Additional implementation details, hyperparameter choices and experimental results are reported in Appendices D, E and E.3, respectively. The code is available at /tttps:/ggithe
bazBone/discover..... /iscoovrr.
Environments For our experiments, we use the JaxGCRL library [9] to assess performance on challenging, high-dimensional navigation and manipulation tasks. Specifically, we evaluate

---

Point Maze
Ant Maze
Arm
1.00
1.00
Success Rate (Easy)
0.4
0.75
0.50
0.50
0.2
0.25
0.25
0.00
0.0
20
20
0.4
Success Rate (Hard)
0.8
0.6
0.3
0.6
0.4
0.2
0.4
0.1
0.2
0.0
0.0
0.0
20
20
Step (M)
Step (M)
Step (M)
Uniform
MEGA
Achievability + Novelty
DISCOVER
Figure 3: Comparison of the success rates on the target task over the course of training in the pointmaze, antmaze arm environments. We compare DISCOVER to other strategies for goal selection. We consider two difficulty levels for each environment. We find that the DISCOVER agents learn to solve difficult target tasks significantly faster than the baselines.
the antmaze environment, where a simulated quadruped with a 27-dimensional state space and an 8-dimensional action space must learn navigate through a maze to reach a target location. For manipulation, we consider the arm environment, which features 23-dimensional state and 5-dimensional action space. In this task, robotic arm must move cube specified target location, potentially while avoiding obstacles. Additionally, we evaluate randomly generated pointmazes varying dimensionality, to assess capabilities of different goal selection strategies to explore high-dimensional goal spaces efficiently. We construct these n--dimensional pointmazes by randomly generating paths in the n--dimensional hypercube until target location was reached sufficiently often from the starting location. For all environments, we consider both simple and a hard configuration, where the latter characterized by longer horizons, more complex obstacles, or
goal spaces.
Goal selection baselines We compare DISCOVER with the following baselines.
1. Hindsight Experience Replay (HER): The HER goal selection strategy [5] always selects goals from the target goal distribution. Since we consider single fixed target goal, the goal at time
is set 9: g"
2. DISCERN (uniform): The uniform goal selection strategy [85] samples goals uniformly from the support of the achieved goal distribution, i.e., ~ Unif(supp((Pch))) The achieved goal distribution Pach is modeled using a kernel density estimator based on randomly sampled previously achieved goals.
3. Maximum Entropy Gain Achievement (MEGA): The MEGA goal selection strategy [53] selects goals with the lowest likelihood from the set of achievable goals, i.c., St arg mingee..s.. (g) In contrast to DISCOVER, MEGA additionally defines goal g as achievable if its value function V( g) exceeds threshold, which is adapted dynamically based on the goal achievement rate over recent episodes.
4. Achievability Novelty: This baseline corresponds to the undirected components of DISCOVER, i.e. St arg max,,e9.... V(50. g) (,0((5,9)) g).
Insight 1: DISCOVER outperforms state-of-the-art goal selection strategies in complex control environments. As shown in Figure 3, DISCOVER consistently outperforms all baseline goal selection strategies across the evaluated environments. The performance gains are particularly
7

---

Uniform
MEGA
Achievablity + Novelty
DISCOVER
2.0
1.3
Step
1.0
Figure 4: Visualization of the selected goals of different goal selection strategies during the first
25M steps on the antmaze environment, colored by time step. DISCOVER balances exploring the environment with exploiting the agent's 's sense of direction to select goals relevant to the target task.
notable in the more challenging variants of each task, where emphasizing relevance proves critical for learning optimal policies. Interestingly, in the environment, HER performs better than some undirected goal selection strategies. We attribute this to the unconstrained nature of the goal space in the arm environment, which leads undirected methods explore irrelevant regions that do not contribute to learning about the target goal.
Insight Undirected goal selection is insufficient for high-dimensional search spaces. We next evaluate the performance of goal selection strategies on pointmaze navigation tasks of varying dimensionality. Table demonstrates that the undirected goal selection strategies are eventually successful in two dimensions, but con- sistently fail in dimension larger than three. In contrast, DISCOVER, by focusing the most relevant directions, successfully solves mazes in up to six dimensions. The substantial difference in empirical performance be explained by the size the search space explored by each method. For undirected methods, this space grows exponentially with dimension, while DISCOVER mitigates this challenge by only selecting goals that likely to lead to the final objective, thereby dramatically reducing the effective search space. While the performance gap is most pronounced in complex, high-dimensional tasks, we demonstrate that DISCOVER also improves performance in standard sparse-reward environments.
Dimension
HER
0C
MEGA
4.8
00
Ach. + Nov. 5.2
00
00
00
00
DISCOVER 2.9
3.1
7.4
5.4
18.7
Table 1:
Comparison of the required number of steps (M) for reaching 10% target goal achievement pointmazes of varying dimension. oo denotes no achievement of 10% success rate be- fore termination after 50M steps. DIS- COVER scales large mazes due to its awareness of direction and uncertainty.
Insight 3: DISCOVER improves performance by selecting relevant goals towards reaching the target, while exploring sufficiently. We visualize the goal selection behavior of DISCOVER and the baseline strategies in the antmaze environment in Figure 4. While all baseline methods perform undirected goal selection, exploring the entire state space, DISCOVER, after an initial exploration phase, quickly identifies the correct direction and subsequently focuses its goal selection the relevant region. These plots explain the improved performance, as DISCOVER can select (and achieve) goals at the target much earlier than the other strategies. We provide detailed evaluation of how the different components DISCOVER influence goal selection in Appendix (cf. Figure 14).

---

Insight 4: DISCOVER can leverage prior knowledge to further accelerate exploration. In many scenarios, prior information about the environment is available, for example through pre-training on related environment. To evaluate whether DISCOVER can leverage prior knowledge for exploration, we integrate prior information on relevance by substituting the prior for (gg.9") in Equation (3), We evaluate two kinds of priors: (1) a hand-designe prior, leveraging human knowledge akin to reward shaping, and (2) a pre-trained prior from similar environment. We use the antmaze (hard) environment, picking as a natural hand-designed prior the Li-distance the target goal g" (ignoring obstacles), and as the pre-trained prior a value function learned on pointmaze with the same layout. We find in Figure 5 that DISCOVER with a prior can explore marginally faster than bootstrapping value estimates from scratch. In particular, in the maze with obstacles, using the pre-trained prior accelerates exploration, since the agent explores only in the direction of the target (cf. Figure 13 in the appendix). We expect that this benefit of priors increases in even harder tasks, since DISCOVER explores only the difficult and novel aspects of the target task.
Success Rate Hard
1.0
DISCOVER
hand designed direction
direction
pre-trained direction
0.8
0.6
0.2
0.0
0
20
60 80
100
Step (M)
Figure Comparison of using different strategies to determine direction, which replace the V(g. g") term in the DIS- COVER objective. Hand-designed di- rection: |lg - 9" g0 pre-trained direction: critic from training in a pointmaze en- vironment with the same maze layout.
Insight 5: Subgoal selection enables deep exploration. Finally, we evaluate the importance of goal-conditioning for solving sparse-reward tasks. To this end, we compare DISCOVER to methods for exploration in RL that do not explicitly select exploratory intermediate goals [24, 27,
Average Averge Success Rate Simple
0.6
0.4
48]. This includes state-of-the- approaches based on cu-
riosity and reward shaping [10, 71]. We show in Figure 6 that even in the simpler environments, these standard methods unable to solve the task. In Figure 15 of the appendix, we visualize the states visited by the non-goal- conditioned baselines. While methods leveraging curiosity to shape the reward explore faster than others, none of them reaches the target task within our maximum number of episodes. This highlights that in long horizon,, sparse- reward settings, directed goal selection can facilitate deep exploration, which is essential for solving complex tasks.
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Normalized Environment Interactions
TD3
SAC + MaxInfoRL
SAC
DISCOVER
RND
Figure State-of-the-ar art RL algorithms fail to achieve the target tasks even in their "simple" configuration.
Conclusion
In this work, we introduce DISCOVER, a goal selection method for solving challenging tasks by balancing novelty, achievability, and relevance. DISCOVER is closely related to principled methods for balancing exploration and exploitation, and we theoretically show that it efficiently reaches the target goal in simplified linear bandit setting. We further empirically evaluate DISCOVER on various complex control tasks and find that consistently outperforms prior of-the----e-rr exploration strategies in RL in solving difficult, sparse-reward tasks.
limitation of DISCOVER is that it relies bootstrapped estimates of the value function, which depend on the ability of the value network to generalize. Additionally, our method incurs overhead by training an ensemble critics for uncertainty estimation, potentially limiting its direct applicability to implementations involving large critic networks such as in language domains. We believe that exploring alternative means of efficient uncertainty estimation for DISCOVER is an exciting direction for future work. Furthermore, we hypothesize that directed exploration is especially advantageous in digh-dimensional and complex goal spaces, as demonstrated for the pointmaze with variable dimensions. Therefore, particularly interesting is the application of DISCOVER to problems with highly complex goal spaces, such as in mathematics or programming with large language model priors. Finally, our work also highlights important directions for future research, including enabling the generation (rather than selection) of goals, extending DISCOVER to hierarchical planning, and reusing experience from one target task for future tasks.

---

Acknowledgments
We would like to thank Bhavya Sukhija, Yarden As, and Nico Gürtler for feedback on early versions of the paper. Marco Bagatella supported by the Max Planck ETH Center for Learning Systems. This project was supported in part by the European Research Council (ERC) under the European Union's 's Horizon 2020 research and Innovation Program Grant agreement no. 815943, and the Swiss National Science Foundation under NCCR Automation, grant agreement 51NF40 180545.
References
[1] Yasin Yadkori Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013.
[2] Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NewrlPS, 2011.
[3] Siddhant Agarwal, Ishan Durugkar, Peter Stone, and Amy Zhang. f-policy gradients: A general framework for goal-conditioned using f-divergences. NeurIPS, 2023.
[4] Ekin Akyürek, Mehul Damani, Adam Zweiger, Linlu Qiu, Han Guo, Jyothish Pari, Yoon Kim, and Jacob Andreas. The surprising effectiveness of test-time training for few-shot learning. arXiv preprint 2rXiv:2411.072799 2024.
[5] Marein Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In NeurIPS, 2017.
[6] Marco Bagatella, Jonas Hübotter, Georg Martius, and Andreas Krause. Active fine-tuning of multi-task policies. ICML, 2025.
[7] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota with large scale deep reinforcement learning. arXiv preprint /91/vv/912..00 2.26000 2019.
[8] Ryo Bertolissi, Jonas Hübotter, Ido Hakimi, and Andreas Krause. Local mixtures of experts: Essentially free test-time training via model merging. arXiv preprint 2515:22505.44136, 2025.
[9] Michat Bortkiewicz, Wladyslaw Palucki, Vivek Myers, Tadeusz Dziarmaga, Tomasz Arczewski. Lukasz Kuciński, and Benjamin Eysenbach. Accelerating goal-conditioned rl algorithms and research. ICLR, 2025.
[10] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In ICLR, 2019.
[11] Daesol Cho, Seungjae Lee, and H Jin Kim. Diversify & conquer: Outcome-directed curriculum via ofitt--distributtin disagreement. In NeurlPS, 2023.
[12] Daesol Cho, Seungjae Lee, and Jin Kim. Outcome- reinforcement learning by uncertainty & temporal distance-aware curriculum goal generation. In ICLR, 2023.
[13] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In ICML,, 2017.
[14] Sebastian Curi, Felix Berkenkamp, and Andreas Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. In NeurIPS, 2020.
[15] Karan Dalal, Daniel Koceja, Gashon Hussein, Jiarui Xu, Yue Zhao, Youjin Song. Shihao Han, Ka Chun Cheung, Jan Kautz, Carlos Guestrin, et al. One-minute video generation with test-time training. arXiv preprint arXiv:2504.05290 2025.
[16] Peter Dayan and Geoffrey E Hinton. Feudal reinforcement learning. In NewrIPS, 1992.
10

---

[17] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In NeurlPS, 2020.
[18] Ishan Durugkar, Mauricio Tec, Scott Nickum, and Peter Stone. Adversarial intrinsic motivation for reinforcement learning. In NeurIPS, 2021.
[19] Onno Eberhard, Jakob Hollenstein, Cristina Pinneri, and Georg Martius. Pink noise all you need: Colored noise exploration in deep reinforcement learning. ICLR, 2023.
[20] Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847), 2021.
[21] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In ICLR, 2019.
[22] Benjamin Eysenbach, Tianjun Zhang, Ruslan Salakhutdinov, and Sergey Levine. Contrastive learning as goal-conditioned reinforcement learning. NeurIPS, 2022.
[23] Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In ICML, 2018.
[24] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. ICML, 2018
[25] Jonas Gehring, Gabriel Synnaeve, Andreas Krause, and Nicolas Usunier. Hierarchical skills for efficient exploration. In NeurIPS, 2021.
[26] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Iims via reinforcement learning. arXiv preprint arXiv:2501.12944, 2025.
[27] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In ICML, 2018.
[28] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint 1rXiv:1812.05903 2018.
[29] Danijar Hafner, Timothy Lillicrap. Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In ICLR, 2020.
[30] Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In ICLR, 2021.
[31] Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse control tasks through world models. Nature, 2025.
[32] Nicklas Hansen, Rishabh Jangir, Yu Sun, Guillem Alenyå, Pieter Abbeel, Alexei Efros, Lerrel Pinto, and Xiaolong Wang. Self-supervised policy adaptation during deployment. In ICLR, 2021.
[33] Moritz Hardt and Yu Sun. Test-time training on nearest neighbors for large language models. In ICLR, 2024.
[34] Philipp Hennig and Christian J Schuler. Entropy search for informmtiin-efficieet global opti- mization. JMLR, 2012.
[35] Edward S. Hu, Richard Chang, Olch Rybkin, and Dinesh Jayaraman. Planning goals for exploration. In ICLR, 2023.
[36] Jonas Hübotter, Sascha Bongni, Ido Hakimi, and Andreas Krause. Efficiently learning at test-time: Active fine-tuning of 1lms. In ICLR, 2025.

---

[37] Jonas Hübotter, Bhavya Sukhija, Lenart Treven, Yarden As, and Andreas Krause. Transductive active learning: Theory and applications. NeurIPS, 2024.
[38] Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. Exploration in deep reinforce- ment learning: A survey. Information Fusion, 85, 2022.
[39] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NewrIPS, 2017.
[40] Seungjae Lee, Daesol Cho, Jonghae Park, and Jin Kim. Cqm: Curriculum reinforcement learning with a quantized world model. In NeurIPS, 2023.
[41] Xuefeng Li, Haoyang Zou, and Pengfei Liu. Limr: Less is more for rl scaling. arXiv preprint arXiv:2502./ 1886, 2025.
[42] David JC MacKay. Information-bass objective functions for active data selection. Neural computation, 4(4), 1992.
[43] Russell Mendonca, Oleh Rybkin, Kostas Danilldiss, Danijar Hafner, and Deepak Pathak. Dis- covering and achieving goals via world models. In NeurlPS, 2021.
[44] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 13215:13/2.5602, 2013.
[45] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540). 2015.
[46] Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In NeurlPS, 2018
[47] Soroush Nasiriany, Vitchyr H. Pong, Ashvin Nair, Alexander Khazatsky, Glen Berseth, and Sergey Levine. Disco rl: policies. In ICRA, 2021.
reinforcement learning for general- purpose
[48] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In NewrIPS, 2016.
[49] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In ICML, 2016.
[50] Ian Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Morteza Ibrahimi, Xiuyuan Lu, and Benjamin Van Roy. Epistemic neural networks. In NeurIPS, 2023.
[51] Seohong Park, Oleh Rybkin, and Sergey Levine. Metra: Scalable unsupervised rl with metric- aware abstraction. In ICLR, 2024.
[52] Deepak Pathak, Pulkit Agrawal, Alexci A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In ICML, 2017.
[53] Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In ICMI., 2020.
[54] Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforcement Icarning: Challenging robotics environments and request for research. arXiv preprint arXiv: 080...00004444 2018.
[55] Gabriel Poesia, David Broman, Nick Haber, and Noah Goodman. Learning formal mathematics from intrinsic motivation. In NeurIPS, 2024.
12

---

[56] Vitchyr H. Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State-covering sulf-super reinforcement learning. ICML, 2020.
[57] Zhizhou Ren, Kefan Dong, Yuan Zhou, Qiang Liu, and Jian Peng. Exploration via hindsight goal generation. NeurlPS, 2019.
[58] Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. Learning by playing solving sparse reward tasks from scratch. In ICML,
[59] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directéd sampling. In NeurlPS, 2014.
[60] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1), 2018.
[61] Cansu Sancaktar, Sebastian Blaes, and Georg Martius. Curious exploration via structured world models yields zero-shot object manipulation. In NeurlPS, 2022.
[62] Erdi Sayar, Giovanni Iacca, Ozgur S Oguz, and Alois Knoll. Diffusion-based curriculum reinforcement learning. In NeurlPS, 2024.
[63] Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxi- mators. ICML, 2015.
[64] Jürgen Schmidhuber. Learning to generate sub-goals for action sequences. In Artificial neural networks, 1991.
[65] Jürgen Schmidhuber. Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem. Frontiers in psychology, 4, 2013.
[66] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schritwieser,, loannis Antonoglou, Veda Panneershelvam, Mare Lanetot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587), 2016.
[67] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre. Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.018155 2017.
[68] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In ICML, 2010.
[69] Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. In ICLR, 2018.
[70] Bhavya Sukhija, Lenart Treven, Cansu Sancaktar, Sebastian Blaes, Stelian Coros, and Andreas Krause. Optimistic active exploration of dynamical systems. In NeurIPS, 2023.
[71] Bhavya Sukhija, Stelian Coros, Andreas Krause, Pieter Abbeel, and Carmelo Sferrazza. Maxin- forl: Boosting exploration in reinforeement learning through information gain maximization. In ICLR, 2025.
[72] Bhavya Sukhija, Lenart Treven, Carmelo Sferrazza, Florian Dorfler, Pieter Abbeel, and Andreas Krause. Optimism via intrinsic rewards: Scalable and principled exploration for model- based reinforcement learning. ICLR 2025 Robot Learning Workshop: Towards Robots with Human- Level Abilities, 2025.
[73] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time training with self-supervision for generalization under distribution shifts. In ICML, 2020.
13

---

[74] Yu Sun, Xinhao Li, Karan Dalal, Jiarui Xu, Arjun Vikram, Genghan Zhang, Yann Dubois, Xinlei Chen, Xiaolong Wang, Sanmi Koyejo, al. Learning (leam at time): Rnns with expressive hidden states. arXiv preprint arXiv:2407.04622, 2024.
[75] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[76] Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1), 1999.
[77] Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In NeurlPS, 2017.
[78] Jean Tarbouriech, Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Adaptive multi-goal exploration. A/STATS, 2022.
[79] Gerald Tesauro. Td-gammon, self-tcaching backgammon program, achieves master-level play. Neural computation, 6(2), 1994.
[80] Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your distance:
Solving sparse reward tasks using self-balancing shaped rewards. In NeurIPS, 2019.
[81] Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In AAAI, 2016
[82] Rui Wang, Joel Lehman, Jeff Clune, and Kenneth Stanley. Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions. arXiv preprint 1rXiv:1901.011 2019.
[83] Tongzhou Wang, Antonio Torralba, Phillip Isola, and Amy Zhang. Optimal goal-reaching reinforcement learning via quasimetric learning, In ICML, 2023.
[84] Yiping Wang, Qing Yang, Zhiyuan Zeng, Liliang Ren, Lucas Liu, Baolin Peng, Hao Cheng, Xuehai He, Kuan Wang. Jianfeng Gao, et al. Reinforcement learning for reasoning in large language models with training example. arXiv preprint 2xXiv:2504220577 2025.
[85] David Warde-Farley, Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non- parametric discriminative rewards. arXiv preprint arXiv:1811.11335, 2018
[86] Yunzhi Zhang, Pieter Abbeel, and Lerrel Pinto. Automatic curriculum learning through value disagreement. In NeurIPS, 2020.
[87] Andrew Zhao, Yiran Wu, Yang Yue, Tong Wu, Quentin Xu, Matthieu Lin, Shenzhi Wang, Qingyun Wu, Zilong Zheng, and Gao Huang. Absolute zero: Reinforced self-play reasoning with zero data. arXiv preprint arXiv:2505.03333. 2025.
[88] Yuxin Zuo, Kaiyan Zhang, Shang Qu, Li Sheng, Xuckai Zhu, Biqing Qi, Youbang Sun, Ganqu Cui, Ning Ding, and Bowen Zhou. Ttrl: Test-time reinforcement learning. arXiv preprint arXiv:2504, 16084, 2025.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract outlines the main contribution presented in the paper. All empirical claims are supported by the presented experiments the Results section. All theoretical contributions are supported by the results presented in the Section 4.2. All proofs are presented in Appendix C.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conelusion section we outline the main limitation of our work, which is the assumption in the theoretical part that the learned value function provides well- calibrated model of the true value function. This assumption is unrealistic in practice, due to the update of the value function using bootstrapped estimates. Although we performed extensive evalutation on three complex control tasks, further experiments especially in other domain would support the argument, but are beyond the scope of this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong ussumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
15

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions and proofs for all theoretical results outlined in Appendix
C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experiments in the paper are easily reproducible by following the instruc- tions provided the README.md file in the attached code submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
experimental results for the new reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All code used for implementing the method and running all experiments is attached to the submission. All experimental results reproducible by following the instructions provided in the README.mo file. No additional datasets were used for the experiments of this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
muuides/CodeSubmise
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: (ww.eoSumiisiiionooooooo
/ httpssscccppbllccccc
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We outline the most relevant implementation details in Appendix E and list the most relevant hyperparameter choices in Table 2. All further implementation detail can be found the provided implementations.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
17

---

Justification: All results are accompanied by error bars. All experiments were performed for 10 different seeds and the mean and one standard error is reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were run on an internal cluster using a single NVIDIA GeForce RTX 2080 Ti GPU for each run. Any standard consumer GPU is sufficient for running all experiments. The experiments require at most 16GB of memory. The longest experiment run took approximately 50 hours and reproduce all experiments about 800 runs, totalling an approximated 8000 compute hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///oourrpscccpuuooee/ ww/ppblicc/chiccauiieeeeeeeoeeee
Answer: [Yes]
Justification: The research conducted in this paper respects the NeurlPS code of ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
18

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss the broader societal impacts in the following: Improving the efficiency of exploration is one of the key challenges in sparse-reward reinforcement learning. The societal impacts of improved reinforcement learning systems are broad due to their wide applicability. This includes major societal benefits such as improved roboties, accelerating scientific progress, etc. Of course, the overall RI. framework so general that potential misuse cannot be ruled out.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper doesn't 't release any data or model, which poses any risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
19

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: For experiments adapt the JaxGCRL code base and cite the original authors properly. No additional existing assets are used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi wwwdeeetcoe...oo com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The only asset introduced in this work is the implementation of the novel DISCOVER method along side its baselines. We provide the implementation along side documentation for understanding the main components and reproducing the experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
20

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy (https: http///eerrrsp.eee cc/ /20/e/// for what should or should not be described.
21

---

Appendices
A Additional Related Work
23
Connection to the Likelihood of Success
23
C Proofs
23
C.1 Notation
23
C.2 Assumptions
24
C.3 Proof of Informal Theorem 4.2
24
D Additional Experimental Results
28
Implementation Details
33
E.1 Probabilistic Value Estimation
33
E,2 Environment Details
33
E.3 Training Hyperparameters
34
22

---

A Additional Related Work
Self-play Many games can be naturally formulated sparse-reward reinforcement learning problems, where the agent receives a reward only upon winning. Seminal works have achieved superhuman ability using this approach [e.g., 45, 66, 67, 7]. A central technique. enabling these successes, is self-play [79, 64, 65, 66]. There are clear connections between these techniques and the directed exploration in DISCOVER. Self-play can be viewed as form of goal selection [64, 65], where the current agent (or simultaneously trained agent) is choosen as its own opponent. This opponent selection promotes achievabilityy as it is possible to beat recent version of yourself, novelty as the opponent is of similar ability, and relevance as it is the currently strongest opponent to beat.
Hierarchical RL DISCOVER is closely related to the field of hierarchical RL [76, 16, 46), which aims to explore and plan at higher level of abstraction. Recent methods have introduced frameworks in which multiple hierarchical levels are used to propose and learn skills [46, 25]. In this work, foeus simplified setting in which single goal is selected for exploration in each episode. However, the general approach can be naturally extended to more complex hierarchical structures.
Directed exploration in sequential decision making DISCOVER designed efficiently address the exploration-exploiaatioo dilemma, a key concept in sequential decision making. Fundamentally, it expresses an agent's 's inevitable trade-off between the objectives of learning its environment and solving task. A particularly common approach to balancing exploration and exploitation is grounded in the principle of optimism in the face of uncertainty [e.g., 68). Thereby, the agent selects actions that max- imize an upper confidence bound (UCB) of the reward function, i.e., it selects actions which based on the agents' imperfect knowledge could lead to a large reward. In many settings of sequential decision making, such as linear bandits, this approach achieves the rate-optimal regret Ii ~ O(d'T) [68, 2, 1. 133. The DISCOVER objective extends UCB to the problem of goal selection in RL. Beyond UCB, many other methods have been shown to effectively direct exploration towards "relevant" experience, such as in bandits [e.g.. 60, 59, 34], in RL [e.g.. 14, 72], or in active learning [e.g.. 42, 37, 6].
B Connection to the Likelihood of Success
From a goal-reaching perspective, the undiscounted version of the DISCOVER criterion is tightly connected to the actual objective of the agent, i.c., reaching the target goal. This emerges naturally as when y + 1, + 0, and π π², the value function becomes a (negative) quasimetric [83]. Thus, it is non-positive, and respects the triangle incquality.
~ (so, g) ("(()"") S V (so.9")),
for arbitrary so E S. E G. Note that the direction of the inequality is flipped as the value function represents negative distance. For a 0.5, DISCOVER maximizes probabilistic estimate of the left hand side of Equation (5), which is a tight lower-bound to V (=0"..g" g*). The value V (so. g") is exactly the quantity of interest for the agent, as represents the negative expected number of steps to reach the
true goal g". Intuitively, DISCOVER selects goals that are optimistically going to guarantee the short- est path to the actual goal or, in the undiscounted case, the likelihood of reaching it within an episode.
C Proofs
In this section, we prove the theoretical guarantee informally stated in Informal Theorem 4.2. We begin by introducing some useful notation and the formal assumptions before proving Theorem C.9.
C.1 Notation
We define the reward function rg())= = aV* + (1-a)""(gg for any fixed a E (0, 1). We define d' (g.g') = -V* g)). We denote by G. S the goals that are achievable by the agent in episode / with probability at least a, i.e., the policy is able to reach goals within G. with probability at least a. We use log to denote the natural logarithm. For simplicity, we assume throughout that the initial state so is fixed across all episodes.
23

---

C.2 Assumptions
Assumption C.1 (Linear value function within feature space), For any n 2 and for all E In. the value functions V* (s0, g) and V*(g."" ye) are linear in the features o6.), :p(+) E Rd with o(-) 1 sp)))
i.e,
(su. 9) (0(9), 0)
and (*(ggg)) (v(()). 0*)
for some fixed 0,0' I with |: |0 1.
Assumption C.2 (Noisy feedback). In episode t, selecting any Jt. E Gt the agent receives noisy feedback y/2 (ge) Et. We assume that the noise sequence {ee [et)tm) is conditionally R-sub-
Gaussian for fixed constant R 2 0, i.e.
A R²R² 2
AA 2 O, E, EleAr [F-11] S exp
where Fi-1 the o-algebra generated by the random variables {gs: E. 1mmi and gt-
Assumption C.3 (Value function estimates). For any 2 1, 2 h, the value function estimate relative to is given by
V)(so--) def (2 x1)
Σ p(g))yor
ox(80.-) def ((.))(EE. + A7)-1
where Ex Eimh (gg)) and >> 0. The value function estimate relative to g" is defined analogously with respect the feature vector yp)).
Assumption C.4 (Goal space contains optimal paths*). For any goal g' E G. the optimal path from g' to g is contained in Formally, there exists a g E G such that d' (g'."* 4²)) = d' (g' .g) + + (g.gg")) for any d= d .9) E [0, d' (g',
Assumption C.5 (Goal achievability). We denote by G. S G the goals that are achievable by the agent episode with probability least (0, 1). Moreover, for any 2 1, the G, contains all goals for which we have previously selected goal, which is (1 - -x)x-llose (under the optimal value function). We call x > 0 the expansion rate. Formally,
G++1 2 fg
Et' S d" (gr. g) S (1 a))..
Further, Go 2 {so}. i.c., the initial state is always achievable.
Relaxing Assumption C.2 One can consider any individual feedback yr being the result of an oracle that achieves the commanded goal 9. with probability at least a within episodes. With this looser assumption, our bound in Informal Theorem 4.2 simply increases by factor K.
C.3 Proof of Informal Theorem 4.2
We begin by restating the regret bound obtained for linear bandits in [13]. Proposition C.6. Let Assumptions C.I to C.3 hold. Fix any d E (0, 1), n 2 1, E (0, 1). and let
=1 RV 2(d n 1)+1++++ log(1/6)) fort n.
(6)
We then have with probability 8 that the regret of selecting goals Ins Int1.... with DISCOVER(a, 3e) is bounded by
h-T
max maxr" (g) -r)) ((())) OddVTlog T Tlog(1/8)) 9EG.
"This assumption simply states that the goal space & is geodesically convex under the quasimetric d' induced by the optimal value function. This is standard "reachability" condition, which may be familiar to readers from control theory.
24

---

Proof. By Theorem 3 in [13] and using that the feature spaces ø and ( are orthogonal (cf. Assump- tion C.I), we have
A+T
Σ
max r (g) -r) SO(VT(BBTT + vr VT log(1 (1/)))
899n t=
with B 1. Bounding YT Od I') using Assumption C.I. completes the proof.
Lemma C.7. Let Assumption C.4 hold and fix any > 0, > 0. Then, for all g' E g with d' (g'gg") 2 there exists g E 9 with d' (g. g') such that r* (g) r" rr) (1 2a)c.
Proof. Consider the optimal path from g' to g" i...,, the goals satisfying
d'' = d'' + d' (g.g").
By Assumption C.4, for any d' (g' E [0, c). we have that g E G. We take the goal such that
d' (g' = c. We then obtain
r" r'(g) r" (g') =
a<V" 9) V (80. g )) + (1 a)
(g,9 o)(V V - ald g¹) d' (su, g)) + aal-a)dd'(g - d"(gg
axdd (so, g') d' (sp, g)) + (1-a)e
2 axd"" g') (d' g') d' (g', (1 ai)e
(triangle inequality)
aad + (1 -a)e
ac + +1 aa)
(1 - 2a)e.
Lemma C.8 (Improvement lemma). Let Assumptions C.I to C.4 hold with 3e as in Equation (6). Fix
any 1), n 2 1, e 0, a E (0, 2)) and 0 < A < (1 22x).. With probability 1 there exist al l' E ,n....,, T) with T O 2aje- A7 and 9 E 9 with d' (ge, 9) E such that
d²
(0) max r' (g) 2 A.
9.9.
Proof. With probability 1 2. the number of episodes T until the agent has achieved Tach of its goals is bounded as T O Zach ).6 We denote by T C {n,..., + T3 the set of episodes in which the agent has achieved its goal. Further, by Proposition C.6, also with probability 8 we have
2
Rn
Σ max r' (g) r r9))) - O(d/vIT)
1ET AESn
All further steps are conditional on the union the above high probability events. Thus, the regret in successful episodes is bounded by R, < (dd/VTach).
Observe that for some Tach = ((d2/(() - 2air - )))), we have that R, <1
(1- - 20)e A, where the conditions < 1 and A (1 2a.ec ensure that the bound on the regret is positive. This then 2 implies that there exists 1' E T such that
max (g) - r" (gr)) S (1 200e A
9E9.
Further, by Lemma C.7, there exists
such that d= (g(- g) = e and
(g) (gr) (1 2aje.
(8)
Combining the above, we obtain
(g) max r" (g) 2 r" (g) [11 2a)e A + r" (g:)))
(Equation (7))
gEGn
r) r* (ge) (1 20)e + A
> (1- 2a) - (1 2a)E -
(Equation (8)
= A.
25

---

f(a) a(1 20) a)"
0.04
0.03
f(o)
0.02
0.01
0.00
0.0
0.1
0.2
0.3
0.4
0.5
Figure 7: Plotting the effect of the parameter the (inverse) goal-achieval rate (cf. Theorem C.9).
The target goal is reached fastest for a Re 0.1.
Theorem C.9. Let Assumptions C.I to C.5 hold with 3r as Equation (6). Fix any
5 E 1), E (0, 1)) and let D d' d" g"). Then, with probability 1 - 8, selecting goals gt with DISCOVER(a, 3r), the number of episodes until g GN is bounded by Dd2
N < 0 a(1 (1- = Ö Def)
Proof. We first note that
r'(g") r" (so) aVV g') - ('0 so)) + (1- (1-a))V'('')) (*(oo.g g"))
= aV 8-) (1 ">o' g²)
(2a 1)V""so,
(1 2a)d (su. 9") (1 - -.
We prove the theorem by applying Lemma C.8 M def [1-2011) times, while setting = (1 - a) First, for arbitrary 0 < M 1, we assume for the goal set Ger with some
= O [(( (aa((122) (1) AJo that it holds that
max r" (g) 2 r" (so) + it..
geGer
Now, applying Lemma C.8 yields that after additional T' steps, with high probability, there exists 1)T) such that there is a g E g with d' dgr,, g) & (1 a)x satisfying
max geGir
(g) A.
Hence, by Assumption C.5, we have that (6+ and therefore,
max rg(g) 2 (g) 2 A + max r" (g) 2 r (so) + (i 1)A. gE9
gESer
Iterating this argument M times and applying a union bound, we obtain
max (g) r" (50) + MA (g)))) gEBMr
The total number of episodes is
N MT Sō Aa((1 20) a)K 1\3
(1 - 2ax
We can optimize a and minimize under the constraints < a 2" A 0, and
< (1 - 21) a)x. The optimal choices are A {1 21 (1 a) n and a = 0.1. Sub-
stituting, obtain N < Ō ((xT(-200 21
D
Ō DaP
Finally, we include technical lemma that is used in the proof of Lemma C.8.
SSee Lemma C.10.
26

---

Lemma C.10. a 1, < < 1 and suppose Tach 2 8 8log(1/6). Furthermore, let
X1y...y XT Lid. ~ Bern(a) and ST Ei= Xt. Then, for some T O Fach ) with probability 1 6, we have ST Tach.
Proof. Set
2 (og(1/0) Tach
T (1+t) Tuck Tack = 0 (aah)))
) 1 E(ST] T.
7 --1
a
Note that μ 2 (1 + Tach and < < (for Tach 2
Hence,
Tach = (1 () μ. 6=
Tach
7(2+7) (1+7)²
2
7 147
E (0,
By the multiplicative Chernoff bound.
Pr[Sr < Tach] = Pr[Sr < (1 - c)pu S <exp(-#t # S eepp( - Tach
= =xxp( - (og(0)/)/))) = 6.
27

---

(a) pointmaze
(b) antmaze
(c)
Figure 8: Sparse-reward environments from the JaxGCRL [9] library used in our evaluation. We additionally implement the pointmaze environment (left), which allows for arbitrary dimensionality. The maze is created by randomly generating paths in the environment until the target is found sufficiently often.
D Additional Experimental Results
In this section, we present additional experiments and ablations. The environments used for this evaluation visualized in Figure [9].
In nigh-dimensional search spaces, even direction
estimates with high variance are useful. In com- plex environments, obtaining accurate direction esti- mates can be challenging. To evaluate the utility of directed goal selection in scenarios where direction estimates are imprecise, we add Gaussian noise to the target goal location. We then compare the number of environment steps required to reach 10% target goal achievement rate using the hand-designed goal selec- tion strategy from Figure 5, under varying levels of noise variance. The results in Figure show that even with substantial noise, pointmaze environments that vnsolvable by undirected methods, remain solv- able by DISCOVER. This demonstrates that even imprecise directional estimates significantly aid target goal discovery in complex goal spaces.
Steps until 10% Success (M)
40-
5
10
20
Variance of Randomized Target
2D
4D
6D
3D
5D
Figure 9: Evaluation of robustness directed goal selection with respect noisy target es- timates. The variance refers to the variance of the random Gaussian noise that added to the target goal before selecting the goals using the hand-designed goal selection strat- egy, which uses the L2 distance to estimate direction.
Ablation the online parameter adaptation strat- egy In Figure 10, we evaluate the effect of using the simple proposed adaptation strategy with differ- ent target goal achievement ratio РAA- and compare with fixing the o; parameters to 0 (Target Relevance + Novelty) and 0.5 (Fixed DISCOVER). Furthermore, we report the average ai for DISCOVER for all easy
and hard tasks respectively in Figure 11. The comparison of the success rates the antmaze environments demonstrates that the adaptation strategy with any target goal achievement works better than fixing the parameters. This can be observed from the goal achievement rates. If fix a, 0.5, we choose goals that are "too easy" and therefore don't 't explore sufficiently. On the other hand, by fixing a, 0 select goals that are "too hard". which also leads too poor improvement. By using the simple adaptation strategy, we roughly achieve the target goal achievement specified. The optimal performance is achieved for the target goal achievement Y 0.5, which is in line with what other methods found [53, 41, 84]. The average O₁2, which is found by the adaptation strategy, initially goes up to 0.15, which is roughly what we found in the theoretical analysis in the lincar bandit setting (cf. Theorem C.9), and then starts to decay. The decay can be explained by the fact that once we can reach the target goal, we don't need to optimize for achievability anymore.
Influence of the term agg.9" In Figure 12, we study how the standard deviation a(g.g" from goal y to the target g* influences the training. This term theoretically is part of the UCB term, directing the agent towards the target goal. To this end, we fix the contribution of ( g) (i.c., set
28

---

Ant Simple
Ant Hard
1.00
Success Rate
0.75
0.50
0.25
0.00
10
20
30
40
20
40
60
80
100
1.00
Goal Achievement Rate
0.75
0.50
0.25
0.00
10
20
40
20
40
60
80
100
Step (M)
Step (M)
Fixed Target Relevance + Novelty
Adaptation P1 0.25
Adaptation p1
0.75
Fixed DISCOVER
Adaptation p1
Figure 10: Comparison of how the adaptation strategy influences the goal achievement and success
rates. We compare two constant strategies (Fixed DISCOVER and Fixed Target Relevance + Novelty) with adaptation rule for different goal achievement targets.
Average og easy
Average hard
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Normalized environment interactions
Normalized environment interactions
Figure 11: We plot the average 0ş the training, adapted by the previously introduced online adaptation strategy for the DISCOVER goal selection strategy. The a are averaged over the three main environments.
29

---

Ant Simple
Ant Hard
1.0
Success Rate
0.5
0.0
0
10
20
30
40
0
20
40
80
100
Step (M)
Step (M)
6' 0.0
0.5
5'
1.0
8 ==
2.0
5 5.0
Figure 12: Comparison of how changing the coefficient of ag 9¹) influences the performance, when training on the two antmaze configurations. We use the configuration with 3 = 0 in all other experiments.
3: 1) and consider a separate fixed B H The plot shows that value for the 3' parameter has significant positive effect on the performance. For this reason, we substitute ( for (g (0.g") g²) in our other experiments with DISCOVER.
T-a' which determines the contribution of (g, g²).
Exploration of DISCOVER + pre-trained prior We visualize the exploration of the DISCOVER + pre-trained prior gaol selection strategy in Figure 13. In comparison to DISCOVER starting from randomly initialized agent, it only explores in the correct direction, avoiding obstacles. This demonstrates that access to prior can further improve performance of DISCOVER.
1e7
2.0
1.5
1.0
Investigation of the role of the DISCOVER components for exploration We visualize the different components of the DISCOVER objective over the course of training
0.5
in Figure 14. The first term V(su. g) has bigh-value close to the initial state. By maximizing it, we will pick goal that is close the start and likely be achievable, which matches the intuition. The second term V(g. .h represents the value from a goal g to the target goal g".
Figure 13: Selected goals by "DIS-
COVER + pre-trained prior" in the antmaze environment.
The plots show that in the first episodes the value is small everywhere and only once goals are discovered that are closer to the final target we observe higher values. Over the course of training, its role of encouraging therefore directs the goal selection towards the final goal. Finally, the standard deviation ( g) has the largest value at the border of the current achievable goal set and therefore encourages selecting novel goals. In general, the components of the DISCOVER objective during the training match the previously presented intuition and efficiently guide the goal selection towards the desired target.
pick goals relevant to the final target becomes more evident. This term
Investigation of Direction Estimation To further investigate the ability of the relevance term in the DISCOVER objective direct the exploration towards to the target goal, we plot the pearson correlation between the relevance term V**g,, (g.g") and proxy for the true distance ||g - g in Figure 16a. The correlation in both the antmaze and pointmaze environments increases quickly during training. This indicates that the relevance term captures a useful notion of distance. even before the final goal reached for the first time. This behavior explains DISCOVER s superior performance compared to undirected goal-selection strategies, as the value function is able to capture a useful notion distance to the target, before it was reached. This allows DISCOVER to effectively guide the exploration to the true target goal. Notably, the correlation does not converge to one. This expected, as the Fuclidean distance in the goal space is an imperfect proxy for the true shortest. traversable path within the environment.
30

---

Step 8M
Step
Step
Step
200
Vise, g)
400
Vise. g1
600
-00
915.8
-200
Vig. g
916.0
4000
viG.
600
900
9164
20
ciecc g)
20
di g)
15
10
700
DISCOVER
-750
DISCOVER
400
300
600
800
Figure 14: Visualization of the components of the DISCOVER objective at different points of the training. We plot the value functions in the regions, where achieved goals are sampled and therefore goals can be selected. The final DISCOVER objective combines the visualized terms with the current adaptation parameters az Bt.
TD3
Thompson Sampling
SAC
SAC MaxInfoRL
le7
1.5
Step
1.0
Figure 15: Visualization of the exploration of the standard non-goal-conditionel RL methods in the
antmaze environments. run the otate-of-the-ar MaxInfoRL [71] with SAC.
31

---

Cor(V" (g."")) All g g" 1la)
0.8
Saccess Raie Ant Hard
0.6
0.0
10
20
30
40
50
100
150
200
Steps (M)
Step (M)
ena_size = ena si2e 6
Ant Hard
Point Hard
en8_6i3e
ena_sise
(a) Direction estimates become useful before the fi- nal goal is reached. We plot the pearson correlation between the current relevance estimate and the L2- distance between the goal and the target goal for the hard variants of the antmaze poin tointmaze envi- ronments.
value function ensemble size of six strikes good balance hetween computational cost quality of uncertainty estimates, leading to improved exploration and task performance. We plot the perfor- mance of DISCOVER varying the number of value function ensemble members hard an antmaze en- vironment.
Ablation of Ensemble Size A key parameter in the DISCOVER algorithm is the value function ensemble size. To quantify the impact of ensemble size on uncertainty estimates, we evalute the performance of DISCOVER in the hard antmaze environment, comparing ensembles of 2, 6, and 8 critics in Figure 16b. Consistent with prior work [48], increasing the number of critics above the default of two improves uncertainty estimation. In our experiments, ensemble of six crities proved sufficient to yield robust performance.
Relying ensemble of critics can be computationally expensive. We find that in our experiments the overhead of increasing the critic size from to 6 was modest. This is mainly due to small critic networks and highly parallel training using jax. In practice, we find that increasing the ensemble from to 6 critics was sufficient to yield high-quality uncertainty estimates, while incurring only 26% increase in runtime.
32

---

E
Implementation Details
We consistently substitute (gg. (5" by a g) in all our experiments. In our evaluated environments, the empirical performance of DISCOVER largely irrespective of ag .9" (ef. Figure 12).
E.1 Probabilistic Value Estimation
crucial component of DISCOVER is probabilistic model of the value function, which can enable uncertainty-aware strategies. Fortunately, there are many options for probabilistic models of the value function [39, 48, 47]. For simplicity, we employ ensemble of value functions [48] and quantify uncertainty via disagreement. This strategy has been used before to select goals, which have high exploration potential and therefore provide novel experiences [86]. Intuitively, these ensemble provide valid uncertainty estimates, as we use different random initilizations for the networks and train on different data. If the networks have been trained on a certain training sample sufficiently often, the different ensemble members will converge to the same value, while if sample hasn't 't been observed yet or only few times the discrepancy will be higher. The mean and standard deviations used for the DISCOVER objective are computed as follows:
N
V(s.g)
Vs(s.g)
(s,
V
This can be seen as a straightforward extension of the standard twin critic approach [24]. We find that slightly higher numer of critic improves accuracy of uncertainty estimates. We further find that by training each critic against a random minimum of two target critics we obtain sufficient diversity for good uncertainty estimates well cireumvent the maximization bias [81]. Additionally, use a softplus activation at the output of each critic to limit the values to negative values.
Scaling critic ensembles to domains with large models (e.g., language) is challenging. An exciting direction for future work is to explore DISCOVER with other tools for uncertainty quantification, such epistemic neural networks [50].
E.2
Environment Details
We adapt the antmaze and arm environments from the JaxGCRL library [9]. In both cases, we fix the initial-state distribution to be uniform pertubation of fixed intial state, and we fix single target goal location per environment (marked by the red cross in Figure 4). In addition to these two challenging nigh-dimensional benchmarks, implement pointmaze environment with potentially arbitrary dimensionality d. In our experiements we consider po pointmazes with d E [2...., 6). We construct the pointmazes follows. We sample random paths in the d-dimensional hypercube, by starting from the origin and randomly changing direction with a probability of 16.6%. We terminate this process once the target goal is observed sufficiently often. This number was set to 2 to depending on the dimensionality of the maze.
In our experiments we evaluate both "simple" and "hard" versions of each environment. For the pointmaze, the simple configuration is realized on a two-dimensional grid while the hard configuration uses a four-dimensional hypercube. In the antmaze, the simple setup contains walls between start and goal, whereas the hard version introduces a single wall that blocks the direct route to the target (visualized in Figure 4). Finally, in the arm environment the simple scenario places one small obstacle that the manipulator must skirt around, while the hard variant includes two larger obstacles that require more precise cube maneuvering reach the goal.
In the pointmaze, the goal space coincides with the full state space, covering all dimensions (for the simple maze and for the hard maze). Consistent with JaxGCRL [9], in the antmaze the goals are defined by the agent's planar-coordinates, and in the arm environment by the 3-dimensional coordinates of the cube.
33

---

E.3 Training Hyperparameters
Hyperparameter
Value
Offline RL algorithm
TD3
Ensemble size
Discount factor
0.99
Batch size
256
Learning rate
3 10-4
Policy update delay
Target critie Polyak factor
0.005
Relabel strategy
Uniform future: 70%, original: 30% Minimum of two random target critics
Target critic computation
Size of critic ensemble
Initial apdation parameter oxp
Horizon
100-250 64-128
Parameter adaptation lookback kadapt
Table 2: Hyperparameters for training in JaxGCRL Environments.
34


Reviews:
[{"review_id": "dMADS52AeZ", "reviewer": "Reviewer_fisY", "summary": "The paper introduces a method called \"DISCOVER\" that selects exploratory goals in the direction of task. Using the critic networks in deep learning, the method can propose achievable goals that can help an agent with a better goal selection to complete the task. By learning an ensemble of critics, the method can also estimate uncertainty regarding a task and leverages value estimates to find useful intermediate goals. The method shows considers three sparse-reward long-horizon settings (Point Maze, Ant Maze and Arm) and shows improvements over the baselines.", "questions": "- Can you please explain why the success rate is still low for almost half of the environment settings? Also, how exactly is the success rate calculated here?\n- Have you considered comparing your method with the intrinsic reward based exploration methods that can do well over long-horizon settings?\n- How sensitive are the uncertainty estimates based on the size of the ensembles used?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The method addresses an important problem of exploration over long horizons in RL and considers goal based RL settings.\n- Using a combination of metrics (achievability, novelty and relevance) sounds a reasonable and interesting metric to consider goal selection.\n\nWeaknesses:\n- The method relies on an ensemble of critics which can be computationally expensive and slow to learn in challenging environments.\n- The tasks used for evaluation are simpler tasks, as compared to more difficult to explore settings in which goal-based methods can actually be helpful in achieving good exploration.\n- The baselines considered do not consider the usual exploration based methods, especially those that are based on intrinsic rewards or RND rewards in sparse-reward settings. A comparison with those can help one understand if the goal-based methodology is even required given when these exploration based methods fail.\n- The success rate of some of the tasks is still low, eg in Easy setting of Arm, and Hard setting of PointMaze and Arm. It would be interesting to see if the curves changes as more number of timesteps are added.", "was_revised": true, "final_justification": "Update:\nI would like to thank the authors for their rebuttal which has been useful for me to understand their work better. I have also looked at the reviews and discussions from other reviewers that has also clarified a bunch of my concerns. Since the authors have clarified most of my concerns, I am updating my scores accordingly.", "rebuttal": "Thank you for your review and detailed comments! We are happy to address each of the points individually.\n\n> Using a combination of metrics (achievability, novelty and relevance) sounds like a reasonable and interesting metric to consider for goal selection.\n\nThank you!\n\n### Computational cost of ensembles\n\n> The method relies on an ensemble of critics which can be computationally expensive and slow to learn in challenging environments\nWe agree that large neural‐network ensembles can incur significant costs, particularly at the scale of today’s language models, but in our experiments the overhead was modest for three main reasons. First, training of the ensembles can be parallelized in modern machine learning frameworks such as JAX, substantially reducing wall-clock time. Second, deep RL methods typically employ relatively small critic networks (or even partial ensembles [1]), keeping the overall memory footprint low. Third, TD3 and the majority of off-policy RL algorithms already rely on twin critics, in order to control the overestimation bias. These three factors have allowed previous works to dramatically scale the ensemble size (up to 100 [2]).\nIn practice, we find that  increasing the ensemble from 2 to 6 critics was sufficient to yield high‐quality uncertainty estimates, while incurring only a ~26 % increase in runtime:\n\n|                   | ens_size=2 | ens_size=4 | ens_size=6 | ens_size=8 |\n|:------------------|-----------:|-----------:|-----------:|-----------:|\n| **Time for 1M steps** |     109.8s |     121.5s |     138.6s |     144.6s |\n\n\n> How sensitive are the uncertainty estimates based on the size of the ensembles used?\n\nThank you for suggesting this important ablation! To quantify the impact of ensemble size on uncertainty estimates, we conducted an ablation study in the hard Ant Maze environment, comparing ensembles of 2, 4, 6, and 8 critics. Consistent with prior work [2], increasing the number of critics above the default of two improves uncertainty estimation. In our experiments, an ensemble of six critics proved sufficient to yield robust performance:\n\n\n| Ensemble Size                 | Success Rate @15M | @25M | @50M | @100M | @150M |\n|:------------------|-----------:|-----------:|-----------:|-----------:|------------:|\n| ens_size=2 | 0% |    7% | 36 % | 46 % | 40 % |\n| ens_size=4 | 2%| 19 % | 45 % | 50 % | 61 % |\n| ens_size=6 | 1%| 17 % | 61 % | 69 % | 66 % |\n| ens_size=8 | 1%| 14 % | 54 % | 63 % | 55 % |\n\n\n\nThese results demonstrate that using six critics strikes a good balance between computational cost and the quality of uncertainty estimates, leading to improved exploration and task performance.\n\n### Comparison to RND rewards\n\n> The baselines considered do not consider the usual exploration based methods, especially those that are based on intrinsic rewards or RND rewards\n\n> Have you considered comparing your method with the intrinsic reward based exploration methods that can do well over long-horizon settings?\n\nThank you for suggesting this comparison, which we believe highlights the value of direction on sparse-reward tasks. We agree that intrinsic‐reward methods play an important role in sparse‐reward, long‐horizon tasks. By design, RND is task-agnostic, and will provide a strong signal towards sources of novelty. RND relies on an intrinsic reward term: within the framework of goal selection for exploration, MEGA (see Figure 2) can be seen as its counterpart, since it largely samples novel goals in any direction.\n\nTo address your comment, we have evaluated RND as a baseline. We have evaluated RND on simple configurations of the three considered environments (Point Maze, Ant Maze and Arm) and **find that it achieves 0% success rate across all tasks**, while DISCOVER achieves 60% on average. This is in line with the results we report for the MaxInfoRL baseline, which is another intrinsic-reward method, based on information gain of a dynamics mode. Both RND and MaxInfoRL explore into “all” directions until a reward is observed for the first time, which leads to inefficient exploration. We will report the RND baselines, along the MaxInfoRL baseline, in Figure 7. These results underscore the advantage of our directed, goal-conditioned exploration approach, which is required to solve hard exploration tasks.\n\n### Complexity of tasks and asymptotic success rate\n\n> Can you please explain why the success rate is still low for almost half of the environment settings?\n\nThe set of environments we consider was recently introduced as part of JAXGCRL [3], and was thus designed to be challenging for modern GCRL algorithms. Figure 3 from [3] shows that, except for the simplest environment (Reacher, which we do not consider), the remaining tasks are only partially solved given a limited compute budget. As our setup (single‐goal, sparse‐reward RL) differs from the multi‐goal experiments in JAXGCRL, this does not constitute an apple-to-apple comparison, but rather an indication of the challenging nature of the environments.\n\n> Also, how exactly is the success rate calculated here?\n\nThe policy is periodically evaluated every 250-500K episodes, depending on the environment. Each episode is considered successful if any state within a finite horizon (100-250 depending on the difficulty of the task) is close enough to the goal, where the closeness criterion is the standard one defined by JAXGCRL [3] (L2-distance on the relevant part of the state).\n\n—\n\nWe thank you for raising these important points, which we think highlight two important features of the algorithm, namely its computational footprint, and its performance gains over intrinsic reward approaches. We hope to have addressed your remaining concerns. Please let us know if you have any further questions or suggestions.  We would greatly appreciate it if you could reconsider the score based on our response and extended results.\n\n\n#### References\n\n[1] Sekar et al., Planning to Explore via Self-Supervised World Models, ICML 2020\n\n[2] An et al., Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble, NeurIPS 2021\n\n[3] Bortkiewicz et al., Accelerating Goal-conditioned Reinforcement Learning Algorithms and Research, ICLR 2025"}, {"review_id": "9MIEHO1mEE", "reviewer": "Reviewer_2Mok", "summary": "This paper introduces DISCOVER, a novel goal-selection strategy for sparse-reward reinforcement learning that creates an automated curriculum of exploratory tasks. The method balances the achievability, novelty, and relevance of potential goals, using bootstrapped value function estimates to direct exploration towards a final target task without requiring prior information. The authors demonstrate that this approach significantly outperforms state-of-the-art exploration methods on 3 complex, long-horizon control tasks.", "questions": "If the bootstrapped estimate of relevance is not optimal, could it trap the agent into refining its policy within a suboptimal point, thereby preventing the discovery of a better path to the goal?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The problem of generating a curriculum of simpler, relevant tasks is crucial for solving complex, high-dimensional problems, and this paper makes a direct and effective contribution to this area.\n- Bootstrapping a \"sense of direction\" entirely from the agent's own value estimates is a clever and practical approach. This avoids the need for strong prior knowledge or costly auxiliary components like generative models, which are often required by other directed exploration strategies.\n\nWeakness\n\n- Although the method is presented as general, the empirical evaluation is confined to navigation-centric environments (Point Maze, Ant Maze, Arm)  where a geometric \"sense of direction\" is intuitive. This casts some doubt on the method's generality, as the vital \"relevance\" component may not function as effectively in more abstract or combinatorial tasks that lack a simple spatial correlation between intermediate and final goals.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns during the rebuttal period.", "rebuttal": "Thank you for your review, and the positive evaluation of our work. We are happy to address each point.\n\n> Bootstrapping a \"sense of direction\" entirely from the agent's own value estimates is a clever and practical approach.\n\nThank you!\n\n### Generality of the DISCOVER goal selection method.\n\n> Although the method is presented as general, the empirical evaluation is confined to navigation-centric environments (Point Maze, Ant Maze, Arm) where a geometric \"sense of direction\" is intuitive.\n\nWe appreciate this observation. We agree that, at a high level, the geometry of the tasks considered is rather intuitive. However, we would like to stress that the networks (and in particular the critic) largely receive proprioceptive measurements: in antmaze, only 2 of the 29 state dimensions convey information about the ant’s position in a 2D plane, while all remaining variables describe the configuration of the ant’s joints. Therefore, these representations are not overly biased towards a simple 2D geometry, and **the critic needs to learn the sense of direction from scratch**. Even when this information is isolated, the critic cannot rely on simple L2 distances, but needs to learn about the obstacle we introduced in the hard variants. \n\nBecause our approach operates on learned representations rather than handcrafted objectives, we believe it holds the potential of  generalizing beyond spatial tasks to tasks with a less straightforward sense of direction. For instance, one could imagine applying the same directional exploration principles for reasoning tasks in large language models. Exploring such extensions is an exciting avenue for future work.\n\n### Escaping local optima.\n\n> If the bootstrapped estimate of relevance is not optimal, could it trap the agent into refining its policy within a suboptimal point, thereby preventing the discovery of a better path to the goal?\n\nIt is indeed true that relying exclusively on the mean value estimate could lead the agent to commit to a suboptimal direction. To address this, we adopt an Upper Confidence Bound (UCB) inspired selection criterion that explicitly encourages exploration by maximizing standard deviation of the value function ensemble. This leads to the method prioritizing novel experiences effectively and avoids getting stuck in local optima. Intuitively, after exploring a currently believed optimal path sufficiently often the value function will become more concentrated on the mean and therefore reduce its standard deviation. Hence the method will switch to alternative goals, which maximize the standard deviation leading to novel experiences. We empirically and theoretically show that this trade-off between exploration and exploitation leads to strong performance (Theorem 4.2, Figure 3). Balancing exploration and exploitation is crucial for preventing the agent from being trapped at a suboptimal point.\n\n—\n\nWe thank you for raising these important points about our algorithm’s generality and exploration capabilities. We hope to have addressed your remaining concerns. Please let us know if you have any further questions or suggestions. We would greatly appreciate it if you could reconsider the score based on our response and extended results."}, {"review_id": "Oel6nGbQUl", "reviewer": "Reviewer_nh3j", "summary": "This paper presents DISCOVER, a goal-directed exploration method for RL, which performs exploration using a combined metric that defines a set of goals to attempt so as to focus exploration towards the true target goal state.", "questions": "1. The discussion of the value of \"sense of direction\" in the abstract and figure 1 is confusing, since this isn't standard exploration terminology and thus without a definition on hand leaves the reader confused as to what is meant. Consider writing those passages.\n\n2. Does the use of the value estimate for the achievability component of the DISCOVER objective result in favoring goals reachable in fewer timesteps? If not, what prevents this bias?\n\n3, In section 4.2, how do these value estimates affect exploration? Maximizing value is simple exploitation.\n\n4. In theorem 4.2 and associated sections, I'm confused as to why the bound is linear with the distance to the target. The value function has no knowledge of the target, so why would it bias selected goals towards the target? The target has never been observed during training, by construction, no? I must be missing something about how there is useful information about an unknown target in the value function. Is this relying on generalization in function approximation? I'm unsure why that would appear in the theoretical bound, though.\n\n5. In figure 7, it seems odd to compare primarily to TD3 and SAC, since these are not really exploration methods. Ideally I'd suggest comparing to random network distillation here, as a commonly used baseline for a state novelty based exploration bonus method.", "limitations": "Limitations are suitably discussed. I don't see any direct potential negative societal impacts from this work.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Overall, I think this paper is excellent. It is very well written (easily the best read in my batch of papers to review for NeurIPS this cycle), strongly motivated by an important topic in RL, and shows strong performance from an intuitive and theoretically grounded method for high impact. While similar in some ways to prior goal directed exploration methods, the key \"relevance\" term proposed is to my knowledge novel, and the paper does a good job of grounding the other elements of the algorithm in prior work.\n\nThe main weakness I can see is that I'm still a bit confused as to why this method works so well- Given that the true goal is never sampled during early training for the evaluated tasks, I'm a little confused as to how the relevance term is providing useful information for goal selection. Some of this might be down to imperfect explanation, but I can imagine experiments that would shine light on when and for what states or goals this term provides a meaningful signal and when/where it is basically noise (perhaps comparing the relevance term computed with the current learned value function to a known oracle/pretrained value function for different states/goals?).\n\nIn aggregate, though, I think this paper is a quality submission and more than sufficient for publication as is. If my concern about the basis for outperformance in the experimental results can be addressed and added to the paper, I would raise my score even further as well.", "was_revised": true, "final_justification": "The authors were able to provide convincing intuition for why the proposed method works so well, as well as adding an important comparison method (which performed poorly compared to DISCOVER). As such I raised my score since I have no remaining concerns and I think this is potentially high-impact work that can break new ground on exploration in RL, a critically important challenge in the field for which few effective and general methods exist presently.", "rebuttal": "We would like to thank you for the positive evaluation of our submission, and the detailed and clear feedback. We will address each point individually.\n\n> Overall, I think this paper is excellent.\n\nThank you for this evaluation!\n\n### Relevance and sense of direction\n\n> I'm a little confused as to how the relevance term is providing useful information for goal selection\n\nWe appreciate this insightful question, which touches on a core aspect of DISCOVER. As you observed, in a strictly tabular setting the relevance term would not be informative, as it would not be updated until the target goal is reached. However, in practice, the critic is a neural network and thus capable of some degree of generalization. We find that this generalization is not precise enough to extract an optimal policy for the target goal directly, but informative enough for subgoal selection. This knowledge is sufficient to rank subgoals by their expected utility toward the unseen target, effectively directing exploration.\n\nTo substantiate this hypothesis, we have prepared an ablation that tracks the Pearson correlation between value estimates $V(\\cdot, g^\\star)$ and a reasonable proxy for the optimal value function (i.e., negative L2 distance between the relevant part of the state and the target goal). We find that even before the agent reaches the target once, the critic’s estimates increasingly align with this distance-based proxy. This shows that the value function can be used to determine which goals will be likely to lead to the target. For a visualization of this behavior we refer to Figure 15 in the appendix, showing that before the target goal is reached closer goals are determined to be of higher utility.\n\n| $Cor(V^\\star(g,g^\\star),\\parallel g-g^\\star\\parallel_2)$ | 2M | 5M | 10M | 15M | 20M |\n|:------------------|-----------:|-----------:|-----------:|-----------:|------------:|\n| Ant Maze Hard | 1% |    4% | 13 % | 35 % | 48 % |\n| Point Maze Hard | 21%| 61 % | 60 % | 61 % | 61 % |\n\n\n> The discussion of the value of \"sense of direction\" in the abstract and figure 1 is confusing\n\nThank you for highlighting this! We agree and will include the following sentences in the abstract to clarify the meaning of “sense of direction”:\n\nWe argue that solving such challenging tasks requires solving simpler tasks that are relevant to the target task, i.e., whose achievement will teach the agent skills required for solving the target task.\nWe demonstrate that this sense of direction, necessary for effective exploration, can be extracted from existing RL algorithms, without leveraging any prior information.\n\n### Achievability component\n\n> Does the use of the value estimate for the achievability component of the DISCOVER objective result in favoring goals reachable in fewer timesteps?\n\nIndeed, if the achievability component *alone* is considered, DISCOVER would select goals that can easily be reached. The two additional components (relevance and novelty, see Equation 3) are thus crucial to recover guarantees (Theorem C.9) and good empirical performance. In combination with them, this term mostly prevents “reckless” exploration, which would only pursue subgoals that are promising, but also very hard to reach. \n\n\n### Exploration vs exploitation\n\n> In section 4.2, how do these value estimates affect exploration? Maximizing value is simple exploitation.\n\nTheorem 4.2 follows from our use of a probabilistic model over value estimates combined with an optimistic goal‐selection strategy (see lines 152–154). By acting *on the upper confidence bounds* of these estimates, the algorithm naturally incorporates the novelty term from Equation 3. In contrast, greedily maximizing value alone would amount to pure exploitation and yield suboptimal exploration. The upper confidence bound maximizes the mean as well as the standard deviation of the value functions, leading to the desired exploration.\n\n### Linear bound\n\n> In theorem 4.2 and associated sections, I'm confused as to why the bound is linear with the distance to the target.\n\nTheorem 4.2 holds in a simplified setting, that is defined through Assumptions C.1 to C.5. In particular, the assumptions C.1 (linearity of the optimal value function) and C.2 (noisy feedback of the value between subgoal and target goal) enable the agent to learn the value function. Carefully balancing exploration and exploitation (via the UCB objective) then allows the agent to explore in only roughly the direction of the target goal. We recognize that assumptions C.1 and C.2 are simplifying and do not hold in most practical settings. The assumptions can be seen as a parallel to the generalization ability of a neural critic, as demonstrated in the correlation results above.\n\n\n### RND baseline\n\n> I'd suggest comparing to random network distillation\n\nThank you for suggesting this comparison, which we believe highlights the value of direction on sparse-reward tasks. We agree that intrinsic‐reward methods play an important role in sparse‐reward, long‐horizon tasks. By design, RND is task-agnostic, and will provide a strong signal towards sources of novelty. RND relies on an intrinsic reward term: within the framework of goal selection for exploration, MEGA (see Figure 2) can be seen as its counterpart, since it largely samples novel goals in any direction.\n\nTo address your comment, we have evaluated RND as a baseline. We have evaluated RND on simple configurations of the three considered environments (Point Maze, Ant Maze and Arm) and **find that it achieves 0% success rate across all tasks**, while DISCOVER achieves on average 60%. This is in line with the results we report for the MaxInfoRL baseline, which is another intrinsic-reward method, based on information gain of a dynamics model. We will report the RND baselines, along the MaxInfoRL baseline, in Figure 7. These results underscore the advantage of our directed, goal-conditioned exploration approach, which is required to solve hard exploration tasks.\n\n—\n\nWe would like to thank you for your thorough and positive evaluation. We hope to have adeptly answered your remaining questions. We hope that the additional experimental results were able to address the improved performance of our method sufficiently to justify increasing the score. Please let us know if you have any further questions or suggestions.\n\n[1] Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain\nexploration for long horizon multi-goal reinforcement learning. In ICML, 2020"}, {"review_id": "l4T6ZuDM44", "reviewer": "Reviewer_9aeB", "summary": "The paper introduces DISCOVER, a modification of goal-conditioned reinforcement learning for sparse goal-directed tasks that utilizes a set of intermediate goals to accelerate exploration. It combines estimates of achievability and novelty with estimates of the distance between the current and target goal to the goal selection process. The goal selection is then biased to select intermediate goals that are reliably achievable, novel, and are estimated to be close to the target goal. The paper offers a theoretical bound of the number of episodes needed to achieve the target task and shows the advantage of the proposed method in multiple experiments over three different environments.", "questions": "- What are the goals used in the experiments?\n\n- How is the relevance term used before reaching the target goal for the first time?\n\n- Why is the weighting term $\\beta_t$ of the variance the same for both novelty and relevance? Also, is it set to $\\beta_t=1$ in the experiments (as described in line 171)?\n\n- If the theoretical bound is independent of the set of goals, how is it advantageous over standard RL?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Quality\nThe method is well-motivated and validated in the experiments by comparing to three other baselines for goal selection, as well as to three baselines without goal-conditioning. The method is not compared to other methods that could use the goal information from hierarchical RL or reward shaping, but this comparison might be out-of-scope for this work. \n\nA theoretical upper bound on the number of episodes learn to to reach the goal is given (informal intuition in the main text, formalized proofs in the appendix).\n\n### Clarity\nOverall, the paper is well-written. The motivation and description of the method are well-structured and comprehensible. The experiment setup lacks some details on the environments. Most notably the exact construction of the *pointmazes* environment (used dimensionalities and number of paths to goal) as well as the details on the *simple* and *hard* configurations for all environments including the used goals are missing. The result section is well structured and easy to follow.\n\n### Significance\nThe method transfers general goal-conditioned RL to the sparse goal-directed setting to use intermediate goals to accelerate learning of a target task. The method is shown to improve over the state-of-the-art for goal selection strategies.\n\n### Originality\nTo the best of my knowledge, the proposed method is novel and relevant citations are given where needed.", "was_revised": true, "final_justification": "The missing details of the experiment setup have been provided. The raised concerns regarding the benefit of the relevance term and theoretical results (and therefore the potential impact) have been lifted by the additional insights from the rebuttal.\n\nAccordingly, I have increased my score.", "rebuttal": "We would like to thank you for a thorough review and for suggesting formatting and clarity improvements. We would like to address each point individually.\n\n\n### Hierarchical RL and reward shaping\n> The method is not compared to other methods that could use the goal information from hierarchical RL or reward shaping, but this comparison might be out-of-scope for this work.\n\nWe agree that goal-based settings are well suited for hierarchical methods or reward shaping. As pointed out, our work is focused specifically on the goal-selection problem driving exploration. As such, hierarchical and reward-shaping approaches are in part orthogonal, and can be combined to form even stronger methods. This remains an exciting avenue for future work.\n\n### Environment Specification\n> The exact construction of the pointmazes environment (used dimensionalities and number of paths to goal)\n\nThank you for this question! We consider 2 to 6 dimensional Point Mazes. We construct the Point Mazes as follows. We sample random paths in the $d$-dimensional hypercube, by starting from the origin and randomly changing direction with a probability of 16.6%. We terminate this process once the target goal is observed sufficiently often. This number was set to 2 to 4 depending on the dimensionality of the maze. We will add this clarification in Section E.2 of the Appendix.\n\n>  Details on the simple and hard configurations for all environments\n\nIn our experiments we evaluate both “simple” and “hard” versions of each environment. For the Point Maze, the simple configuration is realized on a two-dimensional grid while the hard configuration uses a four-dimensional hypercube (as in Figure 4). In the Ant Maze, the simple setup contains no walls between start and goal, whereas the hard version introduces a single wall that blocks the direct route to the target. Finally, in the Arm environment the simple scenario places one small obstacle that the manipulator must skirt around, while the hard variant includes two larger obstacles that require more precise cube maneuvering to reach the goal. We will include all details in section E.2 of the appendix.\n> Fig. 1: Which environment was used?\n\nThank you for pointing this out. Figure 1 reports the average success rate across all three tasks (Point Maze, Ant Maze, and Arm) separately for their simple and hard configurations. In other words, “Average Success Rate Simple/Hard” aggregates the mean performance shown in Figure 3 over those three environments. We will update the caption of Figure 1 to make this explicit.\n\n> What are the goals used in the experiments?\n\nIn the Point Maze, the goal space coincides with the full state space, covering all d dimensions ($n=2$ for the simple maze and $d=4$ for the hard maze). Consistent with JAXGCRL [1], in the Ant Maze the goals are defined by the agent’s planar $(x,y)$-coordinates, and in the Arm environment by the $3$-dimensional coordinates of the cube.\nThank you for highlighting these additional environment specifications, and will include all details in Section E.2 of the Appendix.\n\n### Relevance term\n> How is the relevance term used before reaching the target goal for the first time?\n\nWe appreciate this insightful question, which touches on a core aspect of DISCOVER. As you observed, in a strictly tabular setting, the relevance term would not be informative, as it would not be updated until the target goal is reached. However, in practice, the critic is a neural network and thus capable of some degree of generalization. We find that this generalization is not precise enough to extract an optimal policy for the target goal directly, but informative enough for subgoal selection. This knowledge is sufficient to rank subgoals by their expected utility toward the unseen target, effectively directing exploration.\n\nTo substantiate this hypothesis, we have prepared an ablation that tracks the Pearson correlation between value estimates $V(\\cdot, g^\\star)$ and a reasonable proxy for the optimal value function (i.e., negative L2 distance between the relevant part of the state and the target goal). We find that even before the agent reaches the target once, the critic’s estimates increasingly align with this distance-based proxy. This shows that the value function can be used to determine which goals will be likely to lead to the target. For a visualization of this behavior we refer to Figure 15 in the appendix, showing that before the target goal is reached closer goals are determined to be of higher utility.\n\n| $Cor(V^\\star(g,g^\\star),\\parallel g-g^\\star\\parallel_2)$ | 2M | 5M | 10M | 15M | 20M |\n|:------------------|-----------:|-----------:|-----------:|-----------:|------------:|\n| Ant Maze Hard | 1% |    4% | 13 % | 35 % | 48 % |\n| Point Maze Hard | 21%| 61 % | 60 % | 61 % | 61 % |\n\n\n> Why is the weighting term $\\beta_t$  of the variance the same for both novelty and relevance? Also, is it set to $\\beta_t = 1$ in the experiments?\n\nWe fix $\\beta_t =1$, which we find to ensure sufficient exploration in our experiments. We ablate the weighting of novelty and relevance in Figure 13 of the appendix (Section D). We find that choosing a fixed $\\beta_t$ leads to similarly strong performance as adapting $\\beta_t$ for each term. Intuitively, both uncertainty quantities are from the same critic; hence, one can expect them to be of similar scale.\n\n### Theoretical bound\n> If the theoretical bound is independent of the set of goals, how is it advantageous over standard RL?\n\nThank you for this question! We emphasize that the theoretical bound is independent of the goal set because we show that the final target becomes reachable in a number of steps proportional to the optimal distance to the target, yet independent of the goal space’s dimensionality. In contrast, standard RL with undirected exploration incurs complexity that scales with the volume of the goal set, making long-horizon tasks in high-dimensional spaces far more expensive [3]. We note that our theoretical results hold under the simplifying assumptions C.1–C.5.\n### Formatting Concerns \n\n> Fig. 5: What is the meaning of the color scheme?\n\nThe color scheme in Figure 5, as mentioned in the caption, visualizes the time at which a goal was selected. We will incorporate this information into the plot for clarification.\n\n> Insight 5 / Fig. 7: [47] is cited but not part of the baselines\n\nThank you for pointing this out. [2] is closely related to the goal selection mechanism of Achievability + Novelty, as this strategy selects goals with high disagreement. We will adapt the citation accordingly.\n\n> The focus on goal-directed rewards instead of general sparse-rewards could be clarified in the introduction and abstract.\n\n> Fig. 4: Might be better represented by a table.\n\n> Fig. 13 in Appendix: add dashes to better discern lines\n\n> Table 1 in Appendix: discount factor repeated (as \"discount factor\" and \"discounting factor\")\n\nThank you for reviewing our submission thoroughly and your suggestions! We are happy to directly fix all of these issues, namely by making the reward class explicit in the introduction, replacing Fig. 4 with a table, and updating the Appendix as suggested.  \n\n—\n\nWe hope we were able to clarify your concerns, and look forward to the coming discussion window. Please let us know if you have any further questions or suggestions. We would greatly appreciate it if you could reconsider the score based on our response and extended results.\n\n\n### References\n[1] Bortkiewicz et al., Accelerating Goal-conditioned Reinforcement Learning Algorithms and Research, ICLR 2025\n\n[2] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via\nbootstrapped DQN. In NeurIPS, 2016 \n\n[3]  Jean Tarbouriech, Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Michal Valko,\nand Alessandro Lazaric. Adaptive multi-goal exploration. In AISTATS, 2022"}]

Author rebuttal:

Meta-review: This paper introduces DISCOVER, a goal-selection strategy for sparse-reward RL that combines achievability, novelty, and relevance. By leveraging ensembles of critics to estimate uncertainty, the method builds automated curricula that guide exploration toward intermediate goals. Theoretical analysis provides connections to UCB-style exploration, and experiments on PointMaze, AntMaze, and Arm tasks show consistent improvements over existing goal-selection and standard RL baselines.

**Strengths:** Clear motivation, solid theoretical grounding, and good empirical results across multiple tasks. The idea of incorporating a relevance signal into goal selection is novel and practically effective. The paper is also clearly written and well structured.

**Weaknesses:** Evaluation is restricted to navigation-style tasks, leaving some doubt about generality. Comparisons with some intrinsic-reward exploration methods are also missing. The authors are encouraged to enhance their manuscript with at least some discussion on these issues.

**Final Recommendation:** Overall, DISCOVER represents a meaningful step forward in exploration for sparse-reward RL. Despite some limitations, the contributions are clear, the results compelling, and reviewer concerns were largely addressed in rebuttal. I recommend acceptance.
Decision: Accept (poster)