Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning
Tuan Dam
We present \textbf{SVUCRL}, a reinforcement-learning algorithm fornon-stationary communicating MDPs that exploits \emph{low-rank structure} inhow transitions drift over time.When the rank of the drift is $K\ll SA$, SVUCRL achieves\[  \widetilde{\mathcal O}\Bigl(D_{\max}\sqrt{S A T}    +D_{\max}\sqrt{(B_r+B_p)K S T}\Bigr)\]dynamic regret—matching the conjectured $\sqrt{T}$ rate up to logarithms andstrictly improving on the $T^{3/4}$ dependence of \emph{SWUCRL2–CW}.Key ingredients:1.  \emph{Online low-rank tracking} with explicit Frobenius guarantees;2.  An \emph{incremental} robust-PCA decomposition that separates structured    drift from sparse shocks with martingale dual certificates;3.  \emph{Adaptive} confidence widening driven by a bias-corrected local    variation estimator; and4.  Time-series forecasting of the low-rank factors, combined with an    optimal shrinkage rule.