Source-linked AI summary
SUN: Reaching for Novelty in Reinforcement Learning
Wenyan Yang, Arsenii Mustafin, Dominik Baumann, Joni Pajarinen, Simone Parisi
TL;DR
Exploration in RL lacks a goal-selection method that jointly captures novelty and reachability, despite the importance of both signals. SUN combines successor-value-function reachability with lightweight pseudocount novelty in an off-policy-compatible framework, and consistently outperforms state-of-the-art methods across standard and challenging benchmarks.
Problem
Existing goal-conditioned exploration methods do not jointly score goals by novelty and reachability, while exploration methods also face efficiency, scalability, tuning, or stability limitations.
Method
SUN combines an SVF-based reachability signal with novelty, restricts selection to replay-buffer candidates, and uses a lightweight pseudocount for efficient querying.
Results
SUN consistently outperforms state-of-the-art methods across standard and new benchmarks, including environments with unreachable states and irreversible transitions.
Takeaways & Limitations
SUN provides a unified and practical approach to selecting goals that are both novel and reachable for off-policy RL exploration.
Takeaways & Limitations
SUN draws candidate goals from the replay buffer and therefore can propose only goals it has already encountered.
Abstract
from arXiv · showhide
Exploration in reinforcement learning (RL) remains a fundamental challenge. Recent goal-conditioned RL strategies (which select goals to encourage broader state coverage) have shown promising results, but none scores a goal by novelty and reachability jointly: the two signals are traded off by hand, applied in sequence, or one is neglected outright. In this paper, we introduce a reachability-aware goal-selection framework that explicitly integrates these two aspects, and that can be seamlessly incorporated into any off-policy RL algorithm. To this aim, we propose SUccessor-to-Novelty (SUN), an indicator derived from successor value functions to identify goals that are both novel and reachable. We prove that SUN recovers count-based bonuses in the limit, bounds short-horizon hitting probabilities, and provably rejects unreachable goals. We further present an adaptive goal-selection strategy that leverages these properties, and an accurate yet lightweight pseudocount to avoid the overhead of classic methods. We back up all our claims with thorough benchmarks: SUN consistently outperforms state-of-the-art methods in standard and novel environments with unreachable or hard-to-reach states, irreversible transitions, obstacles, mazes, and unbounded spaces.
1 Introduction
Exploration in RL is difficult because existing approaches can be inefficient, unstable, poorly scalable, or incomplete in balancing novelty with reachability. SUN addresses this tension with a unified indicator, lightweight novelty estimation, and broad benchmark evaluation.
- Classical, provably efficient, and intrinsic-motivation exploration methods face sample-efficiency, scalability, tuning, or stability limitations.These limitations motivate goal-conditioned approaches to exploration.
- Novelty alone can select unreachable goals, whereas reachability alone can select the current state and fail to drive exploration.The isolated-room example illustrates why both signals are needed jointly.
- SUN combines successor-value-function reachability with pseudocount-based novelty and is compatible with any off-policy RL algorithm.The paper instantiates the framework with DQN and TD3.
- SUN provides a lightweight pseudocount, theoretical properties linking it to count bonuses and hitting probabilities, and suppression of unreachable goals.The pseudocount has O(1) query cost, while the indicator supports formal reachability guarantees.
- SUN is reported to consistently outperform state-of-the-art methods on standard and new benchmarks designed around unreachable states and irreversible transitions.The paper frames these environments as direct stress tests of reachability-aware exploration.
2 Problem Setting
Reward-free exploration can target either broad state-visitation distributions or reachable goals, while practical deep-RL methods approximate these objectives with goal-selection heuristics. The paper identifies combining reachability and novelty, selecting goals, and computing novelty efficiently as three central problems.
- Reward-free exploration seeks to explore an MDP without task-specific rewards, with one line of work targeting state-visitation distributions and another using goal-conditioned policies.Maximum-entropy visitation corresponds to uniform state coverage, while goal-conditioned RL focuses on reachable goals.
- A goal is considered reachable when the agent can actually reach it, but this criterion alone does not specify a target visitation distribution.The two exploration objectives are principled but difficult to solve exactly at deep-RL scale.
- Successor value functions encode reachability through the cumulative γ-discounted occurrence of a goal under a policy.They generalize standard value functions and can be approximated with parameterized functions.
- Goal selection determines whether a goal-conditioned policy produces broad and uniform coverage over the goal space.The quality of the selection mechanism is therefore central to exploration performance.
- The paper formulates three subproblems: combining reachability and novelty, designing goal selection, and computing an accurate novelty signal cheaply at scale.These subproblems define the scope of the proposed framework.
3 Exploration via SUN
SUN selects goals by multiplying successor-value reachability with novelty, then adaptively reselects goals as conditions change. Its properties connect the indicator to count-based exploration, short-horizon reachability, and suppression of unreachable goals, while a replay-buffer pseudocount makes novelty estimation lightweight.
- Indicator: SUN combines an SVF-based reachability signal with a novelty signal in one goal-selection indicator.Candidates are sampled from the replay buffer, making the arg max practical in large or continuous goal spaces and compatible with off-policy algorithms.
- Indicator: With ν(g) = 1/n_g, SUN equals the value function of a reward that pays inversely to goal-visit counts.This establishes SUN as a count-bonus objective rather than merely a product of two signals.
- Indicator properties: A high SVF implies a high probability of reaching the goal within a short horizon, while unreachable goals receive SUN score zero.The short-horizon bound scales as O(log(1/V)/(1 − γ)); if no policy in the agent’s class can reach a goal, V^π(s, g) = 0 regardless of novelty.
- Indicator properties: The multiplicative indicator avoids the relative-scale tuning required by additive reachability and novelty terms.Additive formulations can admit confidence bounds but are sensitive to the relative scale of their terms, especially with approximate SVFs.
- Goal selection: SUN adaptively reselections goals when the current goal becomes less reachable or is reached, balancing episodic stability with escape from bad commitments.The strategy monitors the current goal’s SVF against its value at selection time and samples fresh replay-buffer candidates when reselection is triggered.
- Novelty estimation: SUN uses a lightweight pseudocount because continuous-space novelty must be approximated and queried repeatedly across candidate goals.The pseudocount is designed to avoid the overhead of density-based methods and supports O(1) query cost; exact SVFs and deterministic dynamics make several goal-selection strategies coincide.
4 Experiments
SUN is evaluated on environments featuring unreachable states, large or unbounded goal spaces, obstacles, mazes, and hard-to-reach states. Across these settings, SUN improves coverage and visitation uniformity, while its adaptive selection and multiplicative indicator avoid failures seen in ablations and baselines.
- Evaluation setup: The benchmarks cover unreachable or irreversible transitions, large or unbounded goal spaces, and hard exploration with obstacles, mazes, or difficult states.Goal dimensionality ranges from two to eight.
- SUN vs baselines: SUN outperforms all baselines across environments and produces broader, smoother visitation distributions than AdaGoal and DISCOVER.The baselines concentrate visits in narrow regions, including rooms, maze corners, and difficult control-state regions.
- Quantitative results: Coverage measures whether states are visited, whereas entropy measures how uniformly visits are distributed; Gridworlds expose this distinction because coverage saturates while entropy differs substantially.SUN achieves the highest entropy in these settings.
- Goal-selection ablation: Adaptive goal selection learns to reach selected goals: its reselection rate drops to zero, unlike per-step selection, while episodic selection fails when goals become unreachable mid-episode.The failure is illustrated in FourRoomStuck.
- Indicator ablation: Reachability-only exploration barely explores, novelty-only fails with unreachable goals, and additive indicators can saturate; the multiplicative indicator avoids these failure modes.Additive saturation causes entropy to drop and visits to cluster near starting states.
- Comparison and interpretation: All SUN versions achieve better coverage than AdaGoal and DISCOVER, while multiplicative versions also achieve better entropy; the additive entropy exception matches its saturation failure mode.This supports the indicator as a source of SUN’s advantage rather than goal selection alone.
- Why baselines fail: AdaGoal favors novelty before reachability is reliable, whereas DISCOVER favors nearby reachable goals; SUN progressively selects goals farther away while balancing both signals.This progression also appears with SUN’s episodic selection and is attributed to the indicator rather than reselection.
5 Discussion
The discussion presents SUN as a modular approach that combines successor-value reachability with count-based novelty and performs consistently across challenging exploration benchmarks. Its main scope boundary is that candidate goals come from the replay buffer, limiting proposals to previously encountered goals.
- Contributions: SUN combines successor-value reachability, count-based novelty, adaptive goal selection, and a lightweight pseudocount in a modular framework.The paper reports consistent outperformance of AdaGoal and DISCOVER across standard and new benchmarks.
- Interpretation: SUN’s score has an optimal-value interpretation for a count-bonus exploration objective, directing agents toward rarely visited states within reach.The lightweight pseudocount avoids classical density-based overhead while preserving accuracy.
- Limitation: Because SUN samples candidate goals from the replay buffer, it can propose only goals the agent has already encountered.Learned goal-space metrics or generalization-aware training are suggested as ways to relax this buffer-manifold limitation.
Appendices
The appendices establish SUN’s structural properties under an oracle setting: it combines rarity with reachability, relates to count bonuses and hitting probabilities, and rejects unreachable goals.
- Oracle setting: The oracle analysis assumes finite states, deterministic transitions, frozen replay statistics, and goal-conditioned policies that reach reachable goals in finite time.The stochastic extension relaxes deterministic dynamics under almost-sure hitting for reachable goals.
- Count-bonus equivalence: SUN equals the value of a goal-specific reward inversely proportional to the goal’s visit count when counts remain frozen during the trajectory.With online count updates, the equivalence becomes approximate because the reward is non-stationary.
- Hitting-probability bound: A high successor value guarantees a high probability of reaching the goal within a short horizon, with horizon O(log(1/V π)/(1 −γ)).Choosing γ^n+1 ≤ V π(s, g)/2 yields Prπ[τg ≤n] ≥V π(s, g)/2.
- Unreachability rejection: SUN assigns zero to goals unreachable under every policy, whereas novelty-only scores can maximize unreachable goals because they are never visited.This gives SUN a reachability filter that is insensitive to how rare an unreachable goal is.
- Log-space decomposition: In log space, SUN is a soft Lagrangian balancing rarity reward against discounted distance cost, with κ derived from γ rather than separately tuned.The admissible distance grows with the rarity gap, and the formulation extends to stochastic dynamics although the deterministic closed form does not.
A.7 Adaptive Goal-Selection: Theoretical Consistency and Practical Motivation
The adaptive strategy is theoretically stable with exact values and deterministic dynamics, while using successor-value drops to withdraw commitment under stochastic dynamics or value-estimation errors.
- Deterministic consistency: Under deterministic dynamics with exact successor values and frozen counts, the selected goal’s value is non-decreasing and remains the SUN arg max throughout the trajectory.Thus, adaptive selection, per-step selection, and fixed-goal commitment produce the same trajectory in the oracle setting.
- Deterministic consistency: The adaptive check never fires in the exact deterministic oracle setting, preserving fixed-goal semantics and goal stability.Theorem 3 continues to exclude unreachable goals from the candidate ordering.
- Stochastic dynamics: Under stochastic dynamics, the strategy reselects when a transition causes the current goal’s successor value to drop, rather than committing indefinitely or reselecting every step.The value drop is treated as evidence that the agent entered a less favorable region.
- Approximate values: With approximate successor values, estimation errors can break monotonicity, and the adaptive check triggers reselection when subsequent values reveal that the commitment was unreliable.This makes the same mechanism useful for learned critics as well as stochastic transitions.
- Pseudocount implementation: The pseudocount standardization floors each feature’s standard deviation at the median across features to prevent nearly constant dimensions from being amplified.A zero floored deviation falls back to one, and recomputation on insertion adds negligible overhead in the reported experiments.
D Environment Details
The environment appendix describes gridworld, classic-control, and continuous GCRL benchmarks, along with coverage and entropy metrics designed for discrete and continuous goal spaces.
- Gridworlds: Gridworlds use one-hot observations, a goal space S×A, obstacles, one-way tiles, randomized tiles, and varied starting distributions.The environments include ThreeRoom and FourRoomStuck with finite episode horizons.
- Classic control: Classic-control benchmarks use continuous states with discrete actions, including an eight-action discretization for Pendulum.The documented bounds can exceed the regions actually visited before episodes terminate.
- GCRL control: GCRL control tasks include point-mass and ant-like agents in planar, four-dimensional, maze-constrained, and unbounded goal spaces.PointMaze-H has a four-dimensional navigation space, while its heatmaps display only the first two dimensions.
- Continuous entropy: The k-NN differential-entropy estimator distinguishes continuous distributions that share identical binned counts, unlike Shannon entropy.The appendix uses subsampling to make the estimator’s cost independent of buffer size during evaluation.
E Source Code, Compute Details, and Runtimes
Experiments were run on SLURM clusters with separate PyTorch CPU and JAX GPU implementations, while runtime reporting is organized around average wall-clock minutes.
- Compute setup: Gridworld and classic-control experiments used PyTorch on AMD Turin 9965 CPUs, while GCRL control experiments used JAX on NVIDIA V100, A100, and GH200 GPUs.JIT-compiled GCRL operations ran on a single GPU per run.
- Experiment management: Runs were parallelized where possible and retained available data and statistics, including visit and goal-count maps.The reported implementation states that source code would be made available at a link to follow.
- Runtime reporting: Runtime results are presented as average wall-clock time in minutes.The runtime table is identified as Table 1.
F Training Hyperparameters
Training uses common DQN and TD3 configurations, replay-buffer goal sampling, HER relabeling, and separate neural architectures for value and policy components.
- Replay and goals: Replay buffers are warmed with random-policy data, then retain all collected samples without eviction; goal candidates are drawn from the buffer.
- Training configurations: DQN uses γ = 0.99, λ = 0.95, minibatches of 16, learning rate 10^-3, Huber loss, and gradient clipping at 1.0.
- Training configurations: TD3 uses γ = 0.99, λ = 0.95, minibatches of 256, learning rate 10^-3, MSE critic loss, and target-policy smoothing.
- Replay and goals: HER training samples replay sequences and relabels goals using a segmented-future strategy for efficient batch training.
- Network architecture: Continuous-control inputs use learnable radial-basis encoders, while state-goal features are fused by concatenation and element-wise multiplication before Maxout processing.
- Network architecture: Qθ, Vθ, and π use separate architectures: Qθ outputs |A| × |A| values, Vθ outputs one softplus value, and π uses softmax.
G Indicator and Goal-Selection Ablations
The ablations reproduce the main training-curve and visitation-heatmap trends, with Adaptive SUN usually performing best but small environment-specific exceptions.
- Ablation scope: Figures 19 and 20 provide full training curves and end-of-training visitation heatmaps for the indicator and goal-selection ablations.
- Ablation findings: The ablations exhibit the same trends described in the main text across the evaluated environments.
- Ablation findings: Adaptive SUN is not always best: Per-Step is slightly better in Acrobot, while Episodic is slightly better in another reported comparison.
H Pseudocounts Ablation
Pseudocounts generally track true-count exploration, but the appropriate radius depends on the geometry and support of each environment.
- Comparison with true counts: Pseudocounts closely track true-count coverage and entropy across environments for most radius values.
- Comparison with true counts: True counts improve coverage and entropy in almost all environments, while Pendulum shows sharply reduced entropy under exact counting.
- Radius effects: PointMaze-S achieves its best entropy and fastest coverage growth at ρ = 0.1, although all radii reach the same terminal coverage.
- Heatmap interpretation: Heatmaps compare true visit counts with pseudocounts computed from the same data at decreasing radii, using a shared scale within each environment.
- Radius effects: Large radii remain competitive on broad supports but harm compact supports: they degrade AntMaze and ArmPush-H coverage and entropy by oversmoothing reachable structure.
I Detailed Analysis Of All Environments
The environment analysis compares goal coverage, success, travel length, and reselection behavior across SUN variants and competing methods, while structural analyses examine learned reachability and theoretical limits.
- Evaluation measures: The evaluation reports selected and reached goals, goal success, steps-to-goal, and reselection rates at multiple training stages.
- Goal selection: Episodic selection fails when goals become unreachable mid-episode, whereas in-episode reselection avoids this problem.
- Goal selection: Adaptive SUN usually reduces reselection to zero during training, while Per-Step reselects more often and can hurt performance.
- Method comparisons: DISCOVER favors goals near starting states, whereas AdaGoal favors distant goals and can sacrifice reachability.
- Environment-specific behavior: SUN’s behavior reflects environment structure: MountainCar requires coherent momentum-building sequences, Pendulum contains hard-to-reach goals, and ArmPush-H requires contacting the cube before moving it.
- Structural analysis: SUN’s learned value maps assign higher values near goals and zero value across irreversible transition barriers, but the structural theory does not provide sample-complexity guarantees.
K.4 Partial Analysis
The analysis establishes concentration and reachability-filter properties, then identifies two gaps preventing a complete learning guarantee: discovering all reachable goals and relating historical executed-policy values to returned-policy optimality.
- Partial Analysis: Concentration bounds the deviation between the estimated successor value and the historical average value of executed policies.The proof uses bounded martingale differences, Azuma–Hoeffding, and a union bound over goals and time steps.
- Partial Analysis: The reachability filter is sound and monotone because it is built from observed transitions, so filtered goals are reachable and discovered reachability persists.Observed edges have positive transition probability, and the edge set only grows over time.
- Partial Analysis: SUN-UCB deterministically rejects truly unreachable goals, while preserving reachable goals only after paths to them have been observed.This filter prevents unreachable goals with large uncertainty bonuses from repeatedly consuming exploration episodes.
- Additive vs. Multiplicative SUN: The additive indicator requires a scale coefficient tied to target accuracy; with β = 1, its uncertainty guarantee becomes vacuous when uncertainties fall below the value range.The evaluated unscaled additive variant’s poor entropy is consistent with this predicted scaling failure.
- Partial Analysis: The analysis bounds reducing uncertainty for already filtered goals, costing ˜O(SL/ε2) exploration steps, but does not guarantee that every reachable goal enters the filter.A two-state counterexample shows first-hit termination can prevent new edges from being observed, requiring an explicit frontier-expansion mechanism.
- Partial Analysis: A second gap remains because the concentration result concerns historical averages of executed policies, whereas the conjecture concerns returned policies relative to the optimal value.Closing this gap requires a stopping rule, returned-policy specification, and suboptimality bound.