SUN: Reaching for Novelty in Reinforcement Learning
Poster A: Monday -- 11:00 - 12:30
Wenyan Yang, Arsenii Mustafin, Dominik Baumann, Joni Pajarinen, Simone Parisi
Keywords: exploration; reinforcement learning; reachability
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 lack a unified objective that accounts for both novelty and reachability --- some states appear desirable yet remain unattainable given the agent's current capabilities. 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 algorithm. To this aim, we propose SUccessor-to-Novelty (SUN), an indicator derived from successor value functions that identifies goal candidates which are both novel and reachable. We discuss its properties and establish three theoretical results: an equivalence to count-based exploration bonuses, a short-horizon hitting-probability bound, and a guarantee that unreachable goals are rejected. We prove that SUN recovers count-based bonuses in the limit, bounds short-horizon hitting probabilities, and provably rejects unreachable goals. We further present a practical implementation based on a novel multi-step relabeling, and accurate yet lightweight pseudocounts that avoids the overhead of density-based methods. Finally, we introduce new benchmarking environments (with unreachable states and irreversible transitions) that directly stress-test reachability-aware exploration. SUN consistently outperforms state-of-the-art methods on these and standard benchmarks.