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 sr . 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
M=(S,A,p,rt,γ)
Finite discounted tabular MDP with stable transition skeleton and piecewise-stationary reward
π,πPS
Host policy and topology policy, respectively
PtPS(e.g., Pt)
Topology-policy-induced transition matrix
Ltout=I−Pt
Out-Laplacian; governs forward diffusion
Ltin=Dtin−(Pt)⊤
In-Laplacian; governs backward attribution
ftout,ftin
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 ∣S∣ . Solid lines denote mean L1 error and dashed lines denote mean L∞ 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- β variant.
Figure 3: Cumulative tracking ablation under repeated reward shifts in GARNET. GTA-PS β lowers the per-episode terminal error, reduces cumulative tracking error 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
∣S∣
K
Standard-PS
GTA-base
GTA- β
Overhead
FourRooms
40
10
4.10
9.73
9.31
2.37×/2.27×
GARNET
75
18
18.79
48.41
48.85
2.58×/2.60×
GARNET
200
50
51.20
112.39
114.00
2.20×/2.23×
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 ∣S∣=75 and FourRooms with ∣S∣=40 when varying over calibration weight β . The vertical axis is Spearman correlation ρ 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 β gives the strongest agreement between the topology field and the realized backup order, peaking at β=0.02 in GARNET and β=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 α=α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 α , which favor out-degree Laplacian signal, prioritizing proactive backward propagation.
Figure 6: Figure 6 reports shift-end L1 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 L1 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 ℓ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 tmix claim. Each panel fixes K=20,50,100 and varies the corridor width, which changes the mixing scale and therefore the ratio K/tmix . When K≪tmix , 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.
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.
Kai Ruan, Jinghao Lin, Qianshan Wei +2
Gaoling School of Artificial Intelligence, Renmin University of China · Independent Researcher · Institute of Automation, Chinese Academy of Sciences +2
Reinforcement learning with verifiable rewards spends much of its rollout budget on states that yield no learning signal. We recast this as a question about the sampling distribution itself: under a fixed rollout budget, which distribution over states minimizes the variance of the policy-gradient estimator? The answer admits a closed-form Neyman allocation, μvarπ(s)∝dπ(s)σπ(s), which connects naturally to GRPO's group-relative advantage and induces an emergent reverse curriculum as the policy improves, with no externally imposed schedule. Building on this principle, we propose VSR (Variance-driven State Resampling), a plug-in modification to GRPO using a prefix replay buffer and a zero-cost variance proxy. On mathematical reasoning benchmarks and long-horizon agentic tasks (Sokoban, BabyAI), VSR outperforms GRPO and GiGPO on most benchmarks with fewer generated tokens per update.
Standard reinforcement learning (RL) optimizes policies for reward but imposes few constraints on how decisions evolve over time. As a result, policies may achieve high performance while exhibiting temporally incoherent behavior such as abrupt confidence shifts, oscillations, or degenerate inactivity. We introduce Dynamical Prior Reinforcement Learning (DP-RL), a training framework that augments policy gradient learning with an auxiliary loss derived from external state dynamics that implement evidence accumulation and hysteresis. Without modifying the reward, environment, or policy architecture, this prior shapes the temporal evolution of action probabilities during learning. Across three minimal environments, we show that dynamical priors systematically alter decision trajectories in task-dependent ways, promoting temporally structured behavior that cannot be explained by generic smoothing. These results demonstrate that training objectives alone can control the temporal geometry of decision-making in RL agents.