Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning

arXiv:2609.06186v1 Announce Type: new Abstract: Prioritized Sweeping (PS) accelerates model-based reinforcement learning by selecting backups according to Bellman residual magnitude. In nonstationary reward settings, however, the canonical priority score is shortsighted: after a localized reward shift, residuals propagate only through realized backups, so bottlenecked or topologically distant state estimates may remain static under a limited replanning budget. We introduce the Graph Topology Augmentation framework, which employ the graph's resolvent and its diffusion semantic, to augment the inquired signal. Our application, Graph Topology Augmentation for Prioritized Sweeping (GTA-PS), or which the alias Spectral Prioritized Sweeping (SPS) might be more universal, provides a drop-in ordering score for the setting of fixed dynamics and changing state rewards. GTA-PS uses a smootherized policy, inducing a transition chain, with its in- and out-Laplacian. The standard priority key is augmented with a mixing of regularized Laplacian inverses diffusing the residual magnitude. Furthermore, the topology contribution is annealed by a scheduler based on the Second Largest Eigenvalue Modulus (SLEM), allowing its scale to adapt to the chain's mixing regime. We prove that the forward potential coincides with geometric discounted residual propagation and show that GTA-PS gives active priority instantly to all states. Tabular experiments on FourRooms and GARNET domains demonstrate improved replanning efficiency over standard PS under both exact DP and Dyna-style host planners.

Abstract:Prioritized Sweeping (PS) accelerates model-based reinforcement learning by selecting backups according to Bellman residual magnitude. In nonstationary reward settings, however, the canonical priority score is shortsighted: after a localized reward shift, residuals propagate only through realized backups, so bottlenecked or topologically distant state estimates may remain static under a limited replanning budget. We introduce the Graph Topology Augmentation framework, which employ the graph's resolvent and its diffusion semantic, to augment the inquired signal. Our application, Graph Topology Augmentation for Prioritized Sweeping (GTA-PS), or which the alias Spectral Prioritized Sweeping (SPS) might be more universal, provides a drop-in ordering score for the setting of fixed dynamics and changing state rewards. GTA-PS uses a smootherized policy, inducing a transition chain, with its in- and out-Laplacian. The standard priority key is augmented with a mixing of regularized Laplacian inverses diffusing the residual magnitude. Furthermore, the topology contribution is annealed by a scheduler based on the Second Largest Eigenvalue Modulus (SLEM), allowing its scale to adapt to the chain's mixing regime. We prove that the forward potential coincides with geometric discounted residual propagation and show that GTA-PS gives active priority instantly to all states. Tabular experiments on FourRooms and GARNET domains demonstrate improved replanning efficiency over standard PS under both exact DP and Dyna-style host planners.

Machine Learning (cs.LG)

arXiv:2609.06186 [cs.LG]

(or arXiv:2609.06186v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.06186 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning

Related coverage