Graph Topology Augmentation for Prioritized Sweeping in Non-stationary Reinforcement Learning

Prioritized Sweeping (PS) accelerates model-based reinforcement learning by selecting backups according to 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 Graph Topology Augmentation for Prioritized Sweeping (GTA-PS), a concrete instance of a broader topology-augmentation principle for priority-based planning. GTA-PS constructs a policy-induced transition graph and augments the residual key with a mixing of regularized directed-Laplacian potentials that diffuses residual information through forward and backward graph structure. The topology weight is controlled by a scheduler based on the Second Largest Eigenvalue Modulus (SLEM), allowing the queue to adapt to the chain's mixing regime. We prove that the forward potential coincides with discounted residual propagation at a canonical regularization parameter and show that GTA-PS gives nonzero priority to states that standard PS can leave blocked after sparse reward shifts. Tabular experiments on FourRooms and GARNET domains demonstrate improved replanning efficiency over standard PS under both exact DP and Dyna-style host planners.