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

We study reinforcement learning in non-stationary communicating MDPs whosetransition drift admits a low-rank plus sparse structure. We proposeSVUCRL (Structured Variation UCRL) and prove the dynamic-regret bound $\mathcal{O}(D_{\max }S\sqrt{AT}+D_{\max }\sqrt{(B_r+B_p)KST}+D_{\max }{\delta }_B{B}_p).$ 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 variationbudgets, and $KSA$ the rank of the structured drift.

The first term is the statistical price of learning in stationary problems; the second is the non-stationarity price, which scales with $\sqrt{K}$ rather than$\sqrt{SA}$ when drift is low-rank. This matches the $\sqrt{T}$ rate (uptologs) and improves on prior $T^{3/4}$-type guarantees.

SVUCRL combines: