Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning

We study reinforcement learning in non-stationary communicating MDPs whose transition drift admits a low-rank plus sparse structure. We propose SVUCRL (Structured Variation UCRL) and prove the dynamic-regret bound (cid:101) O (cid:16) √ SAT + D max S √ AT + L max B r + D max L max B p + D max S (cid:112) AB p + D max δ B B p + D max √ K T (cid:17) , (up to the additional planning-tolerance term (cid:80) Tt =1 ε τ ( m ( t )) ). where S is the number of states, A the number of actions, T the horizon, D max the MDP diameter, B r / B p the total reward/transition variation budgets, and K ≪ SA the rank of the structured drift, L max is the maximum episole length. The first two terms are the statistical price of learning in stationary problems. The structure-dependent non-stationarity contribution appears through D max √ K T (low-rank drift) and D max δ B B p (sparse shocks), which scale with √ K rather than √ SA when drift is low-rank. This matches the √ T rate (up to logs) and improves on prior T 3 / 4 -type guarantees. SVUCRL combines: (i) online low-rank tracking with explicit Frobenius guarantees, (ii) incremental RPCA to separate structured drift from sparse shocks, (iii) adaptive confidence widening via a bias-corrected local-variation estimator, and (iv) factor forecasting with an optimal shrinkage center.