AEDS: Adaptive edge‐difference shaping for piecewise‐stationary sparse‐reward reinforcement learning

Abstract Sparse‐reward tasks with piecewise‐stationary topology shifts challenge reinforcement learning. Continuous spectral shaping biases agents toward geometric extrema and can delay adaptation when bottlenecks move. We propose adaptive edge‐difference shaping (AEDS), a spectral reward‐shaping method that focuses exploration on structural bottlenecks. AEDS triggers a direction‐agnostic intrinsic reward only when the agent crosses the sign‐flip boundary of the dynamically updated Fiedler vector. An episodic gating mechanism limits rewarded crossings and bounds the cumulative intrinsic return. Within each stationary phase, AEDS induces an augmented Markov decision process to which the standard tabular Q‐learning convergence theorem applies. We evaluate AEDS on grid environments with shifting bottlenecks and geometric traps. Across the evaluation, AEDS performs strongly in several bottleneck‐oriented settings, while count‐based exploration or well‐oriented dense spectral shaping can be preferable in other regimes. These results support a focused scope for AEDS in bottleneck‐oriented sparse‐reward grid tasks.