DISCOVER: Automated Curricula for Sparse-Reward Reinforcement Learning

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.

Hierarchical RL and reward shaping

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.

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

Environment Specification

The exact construction of the pointmazes environment (used dimensionalities and number of paths to goal)

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

Details on the simple and hard configurations for all environments

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

Fig. 1: Which environment was used?

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

What are the goals used in the experiments?

In 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. Thank you for highlighting these additional environment specifications, and will include all details in Section E.2 of the Appendix.

Relevance term

How is the relevance term used before reaching the target goal for the first time?

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

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

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?

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

Theoretical bound

If the theoretical bound is independent of the set of goals, how is it advantageous over standard RL?

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

Formatting Concerns

Fig. 5: What is the meaning of the color scheme?

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

Insight 5 / Fig. 7: [47] is cited but not part of the baselines

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

The focus on goal-directed rewards instead of general sparse-rewards could be clarified in the introduction and abstract.

Fig. 4: Might be better represented by a table.

Fig. 13 in Appendix: add dashes to better discern lines

Table 1 in Appendix: discount factor repeated (as "discount factor" and "discounting factor")

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

—

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

References

[1] Bortkiewicz et al., Accelerating Goal-conditioned Reinforcement Learning Algorithms and Research, ICLR 2025

[2] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In NeurIPS, 2016

[3] Jean Tarbouriech, Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Adaptive multi-goal exploration. In AISTATS, 2022

Thank you for your review, and the positive evaluation of our work. We are happy to address each point.

Bootstrapping a "sense of direction" entirely from the agent's own value estimates is a clever and practical approach.

Thank you!

Generality of the DISCOVER goal selection method.

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.

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

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

Escaping local optima.

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?

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

—

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

Dear Reviewer 2Mok,

We greatly appreciate your effort in reviewing our paper. We would like to double-check if our response was able to address each of the points you raised. Please let us know if anything remains unclear, we are happy to further discuss!

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.

Overall, I think this paper is excellent.

Thank you for this evaluation!

Relevance and sense of direction

I'm a little confused as to how the relevance term is providing useful information for goal selection

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

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

The discussion of the value of "sense of direction" in the abstract and figure 1 is confusing

Thank you for highlighting this! We agree and will include the following sentences in the abstract to clarify the meaning of “sense of direction”:

We 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. We demonstrate that this sense of direction, necessary for effective exploration, can be extracted from existing RL algorithms, without leveraging any prior information.

Achievability component

Does the use of the value estimate for the achievability component of the DISCOVER objective result in favoring goals reachable in fewer timesteps?

Indeed, 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.

Exploration vs exploitation

In section 4.2, how do these value estimates affect exploration? Maximizing value is simple exploitation.

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

Linear bound

In theorem 4.2 and associated sections, I'm confused as to why the bound is linear with the distance to the target.

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

RND baseline

I'd suggest comparing to random network distillation

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

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

—

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

[1] Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In ICML, 2020

Thank you for your review and detailed comments! We are happy to address each of the points individually.

Using a combination of metrics (achievability, novelty and relevance) sounds like a reasonable and interesting metric to consider for goal selection.

Thank you!

Computational cost of ensembles

The method relies on an ensemble of critics which can be computationally expensive and slow to learn in challenging environments We 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]). In 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:

How sensitive are the uncertainty estimates based on the size of the ensembles used?

Thank 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:

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

Comparison to RND rewards

The baselines considered do not consider the usual exploration based methods, especially those that are based on intrinsic rewards or RND rewards

Have you considered comparing your method with the intrinsic reward based exploration methods that can do well over long-horizon settings?

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

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

Complexity of tasks and asymptotic success rate

Can you please explain why the success rate is still low for almost half of the environment settings?

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

Also, how exactly is the success rate calculated here?

The 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).

—

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

References

[1] Sekar et al., Planning to Explore via Self-Supervised World Models, ICML 2020

[2] An et al., Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble, NeurIPS 2021

[3] Bortkiewicz et al., Accelerating Goal-conditioned Reinforcement Learning Algorithms and Research, ICLR 2025

Dear Reviewer fisY,

We greatly appreciate your time and effort in reviewing our paper. We would like to double-check whether our response is adeptly addressing your concerns and questions. Please let us know if anything remains unclear, we are happy to further discuss!