- Rating
- 3
- Confidence
- 4(+1)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes SUccessor-to-Novelty (SUN), a goal-selection framework for reward-free exploration that jointly considers goal novelty and reachability. SUN defines a multiplicative score using a goal-conditioned successor value function and an inverse visitation count. The authors further introduce an adaptive goal-reselection strategy based on changes in estimated reachability, together with a lightweight neighborhood-based pseudocount estimator. Several theoretical properties are established under oracle assumptions, including count-bonus equivalence, a short-horizon hitting-probability bound, and rejection of unreachable goals. Experiments on 14 environments, including navigation and continuous-control tasks, demonstrate improvements in state coverage and visitation entropy over AdaGoal, DISCOVER, and other variants.
Critical strengths
- A simple and well-motivated formulation of reachability-aware exploration.
The multiplicative SUN indicator in Eq. (2) provides an intuitive way to balance novelty and reachability without introducing an additional weighting coefficient. Its connection to discounted goal-reaching values also gives the formulation a meaningful interpretation beyond a purely heuristic combination.
- An effective adaptive goal-selection strategy.
The proposed reselection rule addresses an important limitation of episodic goal commitment, particularly when goals become unreachable following stochastic or irreversible transitions. The comparison with episodic and per-step selection in Figure 7 provides convincing evidence for the practical benefit of this mechanism.
- A computationally practical novelty estimator.
The neighborhood-based pseudocount shifts density-estimation costs from repeated goal queries to replay-buffer updates. The implementation is conceptually straightforward, and the sensitivity analysis in Appendix H provides useful evidence that the estimator behaves similarly to discretized visitation counts across several environments.
- Strong empirical evaluation and informative ablations.
The experiments cover a diverse set of exploration challenges, including unreachable states, irreversible transitions, and continuous control. Comparisons against AdaGoal and DISCOVER are relevant, and the use of 20 random seeds strengthens the results. The indicator and goal-selection ablations help isolate the main contributions.
Critical weaknesses
- The theoretical guarantees are limited to an idealized setting.
The main theoretical properties in Appendix A assume exact successor values and frozen visitation counts, with additional assumptions for the deterministic analysis. The count-bonus equivalence is essentially an identity for a fixed goal-specific reward, while unreachability rejection follows from an exact zero-valued reachability estimate. These results do not establish whether learned successor values can reliably reject unreachable goals or preserve the same exploration behavior under approximation errors.
- The practical benefits are evaluated mainly through exploration metrics.
The experiments focus on goal coverage and visitation entropy, which are appropriate for reward-free exploration but do not necessarily translate into better downstream policy learning. Although Section 3.4 discusses integration with reward-driven RL, the paper does not directly evaluate whether SUN improves sample efficiency or final returns on downstream tasks. Such evidence would strengthen its practical significance.
- Goal selection is restricted to previously visited states.
SUN samples candidate goals from the replay buffer, so it cannot explicitly target unexplored states outside the collected data. This may restrict exploration in environments where reaching novel regions requires extrapolating beyond observed goals. The method also evaluates endpoint novelty rather than the cumulative novelty of trajectories, potentially overlooking informative paths through underexplored regions. The implications of these restrictions deserve further investigation.
- The adaptive reselection rule has limited robustness justification.
The rule discards a goal when its estimated successor value falls below the value at selection time. However, such decreases may arise from critic approximation errors, training-induced value changes, or ordinary stochastic fluctuations rather than genuine reachability deterioration. Proposition 1 only establishes stability under exact values and deterministic dynamics. The method would benefit from an analysis of sensitivity to critic noise or alternative reselection thresholds.
- Some experimental comparisons would benefit from tighter controls.
Appendix F specifies different candidate-pool sizes for SUN and the episodic baselines, while DISCOVER uses a fixed novelty coefficient depending on the environment family. Although these choices follow the respective implementations, they may influence both exploration performance and computational cost. Additional sensitivity analysis under matched candidate budgets and baseline coefficient tuning would help isolate the benefits of the proposed indicator.
- The scalability of pseudocount maintenance remains uncertain.
Although pseudocount queries take constant time, insertion requires neighborhood searches over the replay buffer, with O(NM) complexity for buffer size N and goal dimension M. The implementation also periodically estimates feature scales and may rebuild counts. Since experiments retain all collected samples, cumulative maintenance costs can grow substantially with training duration. The reported runtimes are encouraging, but larger-buffer and higher-dimensional evaluations would better substantiate scalability.
Questions for authors
-
Can the authors quantify how often learned successor values incorrectly classify unreachable goals as reachable, particularly early in training? How sensitive is SUN's performance to such estimation errors?
-
Have the authors evaluated whether SUN's improved coverage and visitation entropy lead to better downstream task performance or faster learning of reward-driven policies?
-
How sensitive is the adaptive reselection mechanism to critic noise and the choice of comparison threshold? Would introducing a tolerance margin improve stability?
-
How do the results change when candidate-pool sizes and goal-selection computational budgets are matched across methods? Was DISCOVER's novelty coefficient tuned beyond the reported default values?
-
How does pseudocount maintenance scale with replay-buffer size and goal dimensionality in practice, including feature-scale updates and count rebuilding?
8 comments
Response to W1 and Q1
W1. The theoretical guarantees are limited to an idealized setting... preserve the same exploration behavior under approximation errors.
Q1. Can the authors quantify how often learned successor values incorrectly classify unreachable goals as reachable, particularly early in training? How sensitive is SUN's performance to such estimation errors?
W1: scope of the theory
Oracle results. We agree with this point. Both count-bonus equivalence and unreachability rejection are theoretical results established under idealized oracle assumptions, and we have explicitly clarified this in the revised manuscript.
The former is now called count-scaled value and is described as an identity: SUN is the value of the goal-reaching reward scaled by the inverse count, not the state-wise count bonus of Bellemare et al. (Section 3.1 and Appendix A.2; the abstract is reworded accordingly). Both results are relabeled as propositions, and Appendix A now states for each result which conditions it uses.
Beyond the oracle. For learned values, the revision adds a proposition on goal selection under approximate values (Appendix A.5). Let the error of the learned value be at most on the candidates, let be the reachable candidates, and let be the smallest count among the unreachable ones.
- No unreachable goal is selected if , and this condition cannot be relaxed.
- The true score of the selected goal is within of the best true score, attained by .
The tolerated error shrinks as unreachable goals become rarer than reachable ones, so rejection is hardest exactly where novelty is highest. This agrees with what we measure.
Q1: how often, and how sensitive
Measurement (Appendix L). In the Gridworlds, where reachability is known exactly, we count how often each algorithm selects a goal that cannot be reached from the state where it is selected (Fig. 8a and Appendix L, Fig. 27). All SUN variants do so in less than 7% of their selections on average, and almost only early in training, while the critic is still inaccurate. The same rate is about 55% for Novelty-Only, 33% for AdaGoal, and 14% for DISCOVER.
Sensitivity. As for the sensitivity of performance to these errors, it is low. The errors are confined to early training (Fig. 27). In ThreeRoom, the adaptive check replaces 83% of the goals that were unreachable when selected, a median of 4 steps after selecting them (68% in FourRoomStuck, and 63% with sticky actions; Appendix L, Fig. 28b). Even the variant that never abandons a goal ends at about the same coverage and entropy in most Gridworlds and Classic Control environments (Appendix Q.2).
Response to W2 and Q2
W2. The practical benefits are evaluated mainly through exploration metrics... evidence would strengthen its practical significance.
Q2. Have the authors evaluated whether SUN's improved coverage and visitation entropy lead to better downstream task performance or faster learning of reward-driven policies?
We agree that coverage and entropy are proxies for downstream performance, and the revision adds a downstream evaluation (Appendix Q.1). In all of it, the task policy is trained fully off-policy, using data collected exclusively by the exploration policy.
Gridworlds and Classic Control. The agent learns a task Q-function from the task reward, and we evaluate its greedy policy. We also include an -greedy agent, the only one that acts on the task Q-function during training.
- In MountainCar, the task where exploration matters the most, SUN is the only algorithm that solves the task.
- In FourRoomStuck and GridMaze, SUN and -greedy attain a higher return than AdaGoal and DISCOVER, although in GridMaze the difference disappears by the end of training.
- In Pendulum, the task is easy to learn, and all algorithms reach about the same return.
- In LunarLander, only -greedy improves during training.
GCRL Control. We also present the goal conditioned policy performance analysis during exploration in Appendix Q.1 and Fig. 45b. Here the task is itself to reach goals, so we evaluate the goal-conditioned policy that the agent learns while exploring, with no additional network. As in DISCOVER, we report its success rate on the task goals of the benchmark over the course of training, in AntMaze-S and ArmPush-H. These goals are never used during training. In AntMaze-S, SUN is the first algorithm to reach the task goals and stays ahead throughout training. In ArmPush-H, DISCOVER improves faster early in training, but SUN catches up after about 4M steps and ends with the highest success rate.
Better exploration is therefore not always better for downstream tasks. In MountainCar and in the GCRL tasks, the more exploration the better, and SUN attains the best results. In LunarLander, this is not the case: the reward-free agents explore the whole state space, for example by flying as high as possible, whereas the task requires the agent to land. How to combine exploration and exploitation is a long-standing problem in RL, and we do not claim to solve it: in these experiments, the task policy never collects data. A more complete method would also act greedily with respect to the task Q-function during training, for example every fixed number of episodes, or once coverage or novelty crosses a threshold. The appendix discusses these options, and we leave them to future work. It also explains why ThreeRoom, Acrobot, and CartPole are not included.
Overview comment
We thank the reviewer for the careful and constructive review, and acknowledge the contribution of our formulation and empirical evaluation. In response, we have revised our paper and analyzed SUN under learned values, both in theory and by measuring goal selection and reselection against the true value in experiments. We also added a downstream evaluation, sweeps of the candidate pool and of the novelty coefficient β, and a task with a 15-dimensional goal. Below, we will answer each weakness and question with details.