Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning

Hung Pham; Tuan Dam

cs.LGSep 5, 2026

Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning

Authors: Hung Pham, Tuan Dam

Organizations: SOICT, Hanoi University of Science and Technology

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.

Figures & tables

Figure 1: A localized reward shift creates sparse residual at

s_{r}

. Standard PS is shortsighted: priority of distant states receives no information hints. GTA-PS adds a topology potential on the policy-induced graph, assigning priority to upstream states before predecessor pushes reach them.

Symbol	Meaning
$\mathcal{M}=(\mathcal{S},\mathcal{A},p,r_{t},\gamma)$	Finite discounted tabular MDP with stable transition skeleton and piecewise-stationary reward
$\pi,\,\pi^{\mathrm{PS}}$	Host policy and topology policy, respectively
$P_{t}^{\mathrm{PS}}\;(\text{e.g., }P_{t})$	Topology-policy-induced transition matrix
$L^{\mathrm{out}}_{t}=I-P_{t}$	Out-Laplacian; governs forward diffusion
$L^{\mathrm{in}}_{t}=D_{t}^{\mathrm{in}}-(P_{t})^{\top}$	In-Laplacian; governs backward attribution
$\mathbf{f}^{\mathrm{out}}_{t},\,\mathbf{f}^{\mathrm{in}}_{t}$	Forward and backward residual potentials

Table 1: Core notation used.

Figure 2: Repeated reward-shift recovery under a Dyna host. Each panel reports value-error traces after multiple reward shifts for a fixed planning budget $K$ and state size $|\mathcal{S}|$ . Solid lines denote mean $L_{1}$ error and dashed lines denote mean $L_{\infty}$ error. Across all tested sizes and budgets, both GTA variants recover faster than Standard-PS, with GTA-PS β typically matching or slightly improving over the fixed- $\beta$ variant.

Figure 3: Cumulative tracking ablation under repeated reward shifts in GARNET. GTA-PS β lowers the per-episode terminal error, reduces cumulative tracking error $\mathrm{TE}(N)$ , and produces a steadily increasing cumulative advantage over Standard-PS. This is the theorem-facing empirical evidence for persistent advantage under frequent reward shifts.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Environment	$\|\mathcal{S}\|$	$K$	Standard-PS	GTA-base	GTA- $\beta$	Overhead
FourRooms	40	10	4.10	9.73	9.31	$2.37\times/2.27\times$
GARNET	75	18	18.79	48.41	48.85	$2.58\times/2.60\times$
GARNET	200	50	51.20	112.39	114.00	$2.20\times/2.23\times$

Appendix

Table 2: Empirical wall-clock planning cost, reported as median milliseconds over

120

repetitions. GTA-PS incurs a moderate but stable runtime multiplier from topology refreshes and dual-queue maintenance.

Figure 4: Figure 4 studies a single reward-shift event from a zero-initialized reward field in two en vironments: GARNET with $|\mathcal{S}|=75$ and FourRooms with $|\mathcal{S}|=40$ when varying over calibration weight $\beta$ . The vertical axis is Spearman correlation $\rho$ between the initial topology ranking and the realized pop order during the first $K$ backups. Larger values indicate that the topology field is better aligned with the backups the planner actually performs. Moderate $\beta$ gives the strongest agreement between the topology field and the realized backup order, peaking at $\beta=0.02$ in GARNET and $\beta=0.1$ in FourRooms. Larger topology gain sharply degrades the ordering quality, which complements the smallness condition in Prop. 5.1 .

Figure 5: Figure 5 is a GARNET design that calibrates over fixed $\alpha=\alpha_{t}$ . The left vertical axis reports top- $1$ accuracy, namely whether the state ranked first by the topology score matches the oracle state ranked first by the greedy propagation surrogate. The right vertical axis reports how much of the oracle’s high-priority predecessor set is recovered by the top-ranked topology states. The results favor the use of small $\alpha$ , which favor out-degree Laplacian signal, prioritizing proactive backward propagation.

Figure 6: Figure 6 reports shift-end $L_{1}$ value error after repeated replanning under a fixed budget. In the left panel, the GARNET horizontal axis is the reversibility coefficient, where $0$ is maximally directed and $1$ is exact symmetry (reversible chain); lower values therefore correspond to more strongly directional random dynamics. In the right panel, FourRooms is perturbed by three transport modes: symmetric dynamics, a one-way corridor bias, and a windy drift field. GTA-PS remains competitive in strongly directed or one-way regimes, but the benefit is not monotone in asymmetry: drift-heavy transport can weaken or reverse the gain.

Figure 7: Figure 7 also measures shift-end $L_{1}$ value error under the same repeated-shift budgeted replanning protocol. In the left GARNET panel, the horizontal axis is the neighbor-rate parameter n_nbr_rate , which controls how globally connected the random transition graph is; moving right-to-left corresponds to increasingly localized connectivity.The right FourRooms panel ablates over the depth ò the bottleneck corridor, measured in grid cells. Lower error therefore means that the planner is coping better with either random sparsification in GARNET or geometric bottlenecking in FourRooms. In corridor-heavy FourRooms layouts, topology-aware prioritization remains substantially stable than Standard-PS, while excels in long-corridor bottenecks.

Figure 8: GARNET cumulative tracking ablation. The left panel shows per-episode value error, the middle panel accumulates the tracking error over episodes, and the right panel plots the theorem-facing cumulative advantage. GTA-beta reduces the episode-end error faster than Standard-PS, and the gap widens rather than collapsing. The cumulative tracking error TE $(N)$ gap increases throughout the series, empirically backs Proof for Lemma and Proposition . The advantage curve remains close to linear with a positive slope, matching the intended interpretation of 5.1 . This is the cleanest evidence that GTA-PS is doing useful work when reward shifts are frequent and the planner must repeatedly recover from fresh residual fields.

Figure 9: FourRooms ablation under a Dyna host. The top row reports Standard-PS and the bottom row reports GTA-PS β on the same seeds, budgets, and shift schedule. GTA-PS β achieves higher cumulative reward while simultaneously lowering cumulative $\ell_{1}$ error, so the improvement was multi-faceted. The coverage traces remain in a comparable band for both methods, which shows that GTA-PS does not exploit aggressively. In the corridor-heavy FourRooms geometry, this is the right signal to look at because the topology module should help recover from bottlenecked propagation.

Figure 10: Threshold test against the $K$ versus $t_{\mathrm{mix}}$ claim. Each panel fixes $K=20,50,100$ and varies the corridor width, which changes the mixing scale and therefore the ratio $K/t_{\mathrm{mix}}$ . When $K\ll t_{\mathrm{mix}}$ , Standard-PS performs significantly worse than GTA-PS. As the ratio increases, the curves cross and the full GTA variant becomes competitive or superior. We can see that GTA-PS performs well over small corridors, empirically backs the intuition of proactiveness. GTA-PS also excels when given more compute, enabling scaling capabilities.

Non-Stationary RL

Non-stationary reinforcement learning studies how agents learn and act as rewards, dynamics, or task distributions change over time.

See all 63 papers

SPO++: Stream-Aligned Policy Optimization for Asynchronous Agentic RL
Aug 25, 2026Kai Ruan, Jinghao Lin, Qianshan Wei +2RL for LLM Agents Agentic RL
Gaoling School of Artificial Intelligence, Renmin University of China · Independent Researcher · Institute of Automation, Chinese Academy of Sciences +2
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards
Oct 11, 2026Yibo Wang, Yuanxin Liu, Zhaoran WangReinforcement Learning with Verifiable Rewards Policy Gradient Methods
Dynamical Priors as a Training Objective in Reinforcement Learning
Apr 23, 2026Sukesh SubaharanReinforcement Learning Policy Gradient Methods
Coimbatore Medical College Coimbatore, TN India

Aug 25, 2026J/K move · Enter open · S save

SPO++: Stream-Aligned Policy Optimization for Asynchronous Agentic RL

Kai Ruan, Jinghao Lin, Qianshan Wei, Ziqi Zhou+1

Gaoling School of Artificial Intelligence, Renmin University of China · Independent Researcher · Institute of Automation, Chinese Academy of Sciences+2

RL for LLM Agents Agentic RL Asynchronous RL

Open paper AskPDF arXiv

Group-relative reinforcement learning waits for sibling rollouts of the same prompt, which is costly for long and variable tool-use trajectories. Single-stream Policy Optimization (SPO) removes this dependency with a persistent prompt-level value estimate, but its recipe whitens one advantage per trajectory before optimizing a token-mean actor loss. We show that trajectory centering generally does not center the token-weighted quantity consumed by the actor, and fix the mismatch by standardizing terminal-outcome advantages under the action-token measure. We additionally organize prompt evidence by the policy event that generated it rather than learner receipt order. Across matched runs on ALFWorld at two model scales and on Math-TIR, SPO++ improves online learning efficiency over SPO. A paired ablation identifies action-token-measure normalization as the strongest tested component.

Abstract

Non-Stationary RL

Explore similar work

SPO++: Stream-Aligned Policy Optimization for Asynchronous Agentic RL

Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

Dynamical Priors as a Training Objective in Reinforcement Learning