Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning
Authors: Tuan Quang Dam
Venue: NeurIPS 2025 poster ()
Keywords: Non-Stationary Reinforcement Learning
Primary area: reinforcement_learning

Abstract: We study reinforcement learning in non-stationary communicating MDPs whose
transition drift admits a low-rank plus sparse structure. We propose
\textbf{SVUCRL} (Structured Variation UCRL) and prove the dynamic-regret bound
\[\scalebox{0.75}{$\displaystyle
  \widetilde{\mathcal O}\Bigl(
       \sqrt{SA\,T}
       + D_{\max}S\sqrt{A\,T}
       + L_{\max}B_r
       + D_{\max}L_{\max}B_p
       + D_{\max}S\sqrt{A\,B_p}
       + D_{\max}\delta_B B_p
       + D_{\max}\sqrt{K\,T}
     \Bigr),
$}\]
(up to the additional planning-tolerance term $\sum_{t=1}^T \varepsilon_{\tau(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\!\ll\! 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}\sqrt{K\,T}$ (low-rank drift) and $D_{\max}\delta_B B_p$ (sparse shocks),
which scale with $\sqrt{K}$ rather than $\sqrt{SA}$ when drift is low-rank. This matches the $\sqrt{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.

Optimal Regret Bounds via Low-Rank Structured
Variation in Non-Stationary Reinforcement Learning
Tuan Dam
Hanoi University of Science and Technology. Hanoi, Vietnam tuandq@soict. hust. vn
Abstract
We study reinforcement learning in non-stationary communicating MDPs whose transition drift admits low-rank plus sparse structure. We propose SVUCRL (Structured Variation UCRL) and prove the dynamic-regre bound
D(VSAT Dmaxs + L, + Donoc By + Dmaxs v BA + DeuuruBB.. + Dinns v. KT
(up to the additional planning-toleme tolerance term Et= Er(m(t))
where S is the number of states, A the number of actions, T the horizon, D Dmax the MDP diameter, B,/Bp the total reward/transition variation budgets, and K & SA the rank of the structured drift, I-max is the maximum episole length. The first two terms are the statistical price learning in stationary problems. The structure- dependent non-stationarity contribution appears through Dmax VT (low-rank drift) and m Bp (sparse shocks), which scale with VK rather than VSA when drift is low-rank. This matches the vT rate (up to logs) and improves on prior T8/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 optimal shrinkage center.
Introduction
Reinforcement learning (RL) algorithms have achieved remarkable success in stationary environments with fixed reward distributions and state transition dynamics. However, many real-world applications involve non-stationary environments where dynamics evolve due to changing user preferences, environmental conditions, or system parameters. This -tatsoationartty poses significant challenges for traditional RL approaches that assume fixed environment dynamics.
Non-stationary RL faces environments whose reward and transition laws evolve in complex ways. Standard approaches use sliding-window techniques that focus on recent observations while discard- ing older data. Algorithms such SWUCRL2-CC [6] widen confidence to temporal drift, providing theoretical guarantees at the cost of higher regret.
These existing approaches have significant limitation: they use uniform widening parameters that ignore the structure of environmental evolution. In many real systems, however, drift exhibits exploitable patterns: it often lives in low-dimensional subspaces (K < S.A) where only few under- lying factors drive changes; the changes follow smooth trajectories enabling short-term forecasting; and many environments exhibit structured evolution with occasional sparse shocks affecting only small subsets of state-action pairs.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This paper leverages these observations to develop SVUCRL (Structured Variation UCRL), which combines matrix factorization, robust statisties, and time-series analysis achieve improved regret bounds and computational efficiency.
Our contributions:
1. Structured variation model and ög. We model drift as low-rank plus sparse component whose Ei-mass consumes at most -n-fraction of the transition-variant variation budget Bp. This separates the learnable, shared dynamics from idiosyncratic shocks (A (Assumption 1).
2. Provable low-rank tracking. power-Frobent Frobenius inequality and randomized SVD with power iterations control the streaming approximation error with explicit constants (Lemmas 1, 2).
3. Shock isolation (PCP). We (conceptually) use the convex PCP/RPCA program (1) separate structured low-rank drift from sparse shocks, with an exact recovery guarantee under standard incoherence and random- random-support conditions (Proposition 1). Algorithm used as a fast incremental subspace update to warm- aumm-startaaccelerate PCP computations.
4. Forecast-shrinkage center. Forecasted factors define low-variance center that is combined with empirical transitions via a Jomes-Steinn weight; the data-driven weight is asymptotically optimal (Theorem 1).
5. Main regret bound. Summing per-step bounds under the above controls yields the three-term dynamic-regret guarantee, matching VT rates (Theorem 2).
The resulting algorithm, SVUCRL, enjoys the regret bound of Theorem 2 and is computationally O(TSA(SK + T).
Notation |S] denotes the size of the state space, A is the average number of actions, Dina the diameter of the MDP, B, Bp the reward/transition variation budgets, and 1/1,,0 the maximum row E norm. Throughout Ô hides polylog(1: (T', S, A) factors.
Related Work Non-stationary reinforcement learning has been studied under various modeling assumptions. The sliding window approach has been explored extensively [6, 7], with algorithms that discard data outside recent window. Change-point detection methods [16] attempt identify significant shifts in environment dynamics. Bandit-based approaches [4, 17] use various weighting schemes to prioritize recent observations. Our work is most closely related to the confidence widening approach in SWUCRL2-CW [6], but we significantly improve upon it by exploiting structure in the variation. Our structured variation model bears some similarity but we focus on the structure of changes rather than the structure of the MDP itself. The matrix decomposition techniques we employ relate robust PCA [5] and online matrix factorization [13], but we adapt these methods to the specific challenges of sequential decision makinng under non- stationarity. Our adaptive confidence widening connects to adaptive concentration inequalities in statistics [9, 10]. Beyond classical factored MDPs [12, 15], recent work explores low-rank structure for sample-efficient control and representation learning, e-g., low-rank MDPs with continuous actions [3] and model-based methods that exploit low-rank structure [1]. Our setting differs by allowing time-varying dynamics with a low-rank drift plus sparse shocks, and our analysis quantifies how exploiting this structure improves dynamic-regret rates.
factored MDPs [12, 15],
Our Õ(VT) dependence does not contradict known lower bounds in the unstructured non- stationary setting: for communicating MDPs, Mao al. [14] show any algorithm suffers at least ((B,+B,))//3T') when no structure assumed. By contrast, our improvement leverages low- rank drift and sparse shocks. Unless otherwise stated, all comparisons in this paper are made under Assumption I (low-rank drift plus sparse shocks); in the same regime, SWUCRL2-CW [6] is the most relevant baseline.
2 Problem set-up
We study reinforcement learning in non-stationary environments, formalized a sequence
(S, A. (t) of communicating Markov Decision Processes (MDPs) with diameter at most
D Dmax-

---

MDP Sequence Each MDP M, in the sequence shares the same state space S and action space A but has potentially different transition dynamics pr and reward functions r at each time step The transition function pt (s'1s, |s. a)) specifies the probability of transitioning to state s' when taking action a in state at time Similarly, the reward function ry(s, a) represents the expected reward for taking action a in state at time i.
Communicating MDPs We assume that each MDP in the sequence is communicating, meaning that for any pair of states s, E S, there exists a policy that reaches s' from s with non-zero probability. The diameter D Dmax quantifies the worst-case expected time to navigate between any two states, providing a measure of the connectivity of the MDP.
define variation budgets for both rewards and transitions: B, = Ee maxx,a 1 (8, a) re (s,a)), Вр = E, maxx,a [IPt+1 a) Pe(-Is, a)ll The reward variation budget B, measures the cumulative maximum change in rewards across all state-action pairs, while the transition variation budget B, captures the cumulative maximum change in transition probabilities measured in & norm. These budgets provide formal way bound the total amount of non-stationarity in the environment.
Variation Budgets To quantify the degree of non non-stationarity,
Learning Protocol The learning process proceeds as follows: at each time step I, the agent observes the current state St. selects an action a, based its policy, and the environment generates a reward re( Qe) and transitions to the next state $1+1 according to Pe [t, at). The agent then updates its policy based on the observation (st, at, Tt, 8(+1).
Dynamic regret The performance of learning algorithm is measured by its dynamic regret, defined as:
T DynRegr = -(oi - re(ss, at)
t=1
where Pz is the optimal average reward for MDP / (achievable by an oracle that knows the dynamics of MDP in advance) and define as
T--1 Σ re(s), a))
P == sup lim
T T B
where ag -- 8:) and 8,41 (- 8;, ag). The dynamic regret measures the cumulative difference between the reward obtained by the algorithm and the reward that could have been obtained by an optimal policy for each MDP in the sequence. This is more challenging metric than the static regret often used in stationary environments, as it requires the algorithm track the changing optimal policy over time.
Challenges Non-stationary RL presents several key challenges. The ieerration-eploiitaaiin tradeoff requires the agent to balance exploring to learn the changing dynamics with exploiting current knowledge to maximize reward. The agent must also demonstrate adaptivity by adapting quickly much relevant historical data. Additionally,
to changes in the environment without discarding computational efficiency is crucial as processing the continuous stream of observations requires efficient algorithms, especially for large state and action spaces.
Our approach addresses these challenges by exploiting structure in the environmental changes, allowing for more efficient learning and better adaptation to the evolving dynamics.
3 Structured variation model
The core insight of our approach is that changes in the environment dynamics often exhibit struc- ture that be exploited for more efficient learning. We formalize this intuition in structured variation model. Most of the change in the dynamics from step ł to 1+1 1 can be explained by a few latent drivers, plus occasional localized shocks.
Assumption 1 (Low-rank drift). For each t, the transition change AP, := P P. E SAXS admits the decomposition
K
AP
Σ
u4 (t) Uk W
+ Ess
max [cc(s, S 6g Bp: 8.a
Σ
ERSA
with per-factor bounds ||wk|l 1 < 1 and (x a)l s 1 for all (s)
3

---

In this assumption:
ug (1) is the time weight of factor k step
Vk is pattern over state-action rows (8, () saying which parts of the MDP are affected by factor k.
Wk is a pattern over next states s' saying how probability mass is reallocated when factor &: acts.
E, is sparse shock capturing rare, localized, hard-to-predict changes.
Why the constraints matter. The simple bounds [ux(ss, a)] = and ||wx]|2 S 1 are convenient scaling convention: they push the overall magnitude of each factor into (u.()) This makes the per-step change interpretable and ensures that maxs,a Ex un (L)x,, a) w)
is directly controlled by >x (4)]. The budget E, max [|e a, 1) h S Ön B, says that shocks consume at most a 0g Og-fraction of the total transition variation Bp. most drift is structured.
What the model buys you. Low rank means shured structure across rows: many (s, a--rows move correlated way (via the same wy pattern), at amplitudes set by vx a), and with time profiles (t). Under this structural assumption, SVUCRL does not need treat the non-stationary transition component as an arbitrary S ---dimensionnl drift process; instead, it can summarize the time variation through K Kddimensional factorization. In the regret bound (Thcorem 2), this manifests through structured approximation contribution O(Dmax V T) and sparse-shock residual m Bp- When K < SA and shocks are limited (small Òn), these structure-dependee stantially smaller than what typically incurred under worst-case, unstructured drift models. The remaining non con-stationarity cost is captured by the within-episode drift terms Lmax B,+ D max L By (and the widening term O(D S B,))), which reflect how changes accumulate the episode length.
terms can be sub-
This model is motivated by several observations about real-world systems. In traffic and control settings, a weather factor can shift many transitions in the same direction (e.g., wet roads), where uk highlights the affected links, Wy encodes where mass moves (such slower lanes), and un (t) follows the storm's 's intensity. Similarly, in recommendation systems, a global popularity wave reweights next-state preferences for many contexts in tandem, with occasional item-specific shocks handled by Ge-
How it relates the variation budgets. Recall B, E, max,, [|P4t P a)ll
Under Assumption 1, the structured part of each row change is Σn us (f)ex (s, a)W;,, whose sizsie per row is most Σx Jux (f) by the bounds on lk. Wi. Hence the same few coefficients us (t) concurrently govern the row-wise maxima that enter Bp, this is the leverage SVUCRL exploits.
Sanity checks.
Stationary case: if the environment stationary, then AP, = and one can take K 0, c = 0.
Many weak drivers: as K grows or óg increases, the advantage diminishes smoothly; the model reduces to general variation when K approaches S.A or shocks dominate.
No need to know K a priori. SVUCRL estimates an effective rank online (via randomized SVD with oversampling and power iterations), and updates the spectrum evolves; the algorithm and guarantees do not require the true K as input.
What this model not. We do not assume the MDP itself is factored; only the drift AP, is approximately low rank plus sparse. This distinction lets capture global but compact changes when the underlying Pe has no simple structure.
Online low-rank approximation
key component of our approach is efficiently tracking the low-rank structure of environmental changes as they evolve over time. This section develops the theoretical and algorithmic foundations for this tracking process.
To represent the changes in transition dynamics, flatten the state-action pairs (s, a) into rows and the next-state indices into columns, forming matrices. We denote by X, [APt-w+ AP.] g S the matrix containing the last W changes in transition probabilities.

---

Algorithm 1 Randomised SVD with power iterations
Require: matrix X, target rank K, oversampling 8, iters !
I: Ω + -(0, ((0,1))5x(K*+ (S)))+s)
2: Yo XS
3: for j = 1 do
Y; + 1-X(X'y; Y-11)
5: end for
6: Q <- qr(Y,))
- Q 8: Up, E. V + (B)
9: U+ U+QUB
10: return (U
(.i:RR R V \I..R))
4.1 A Frobenius power-iteration bound
We begin by establishing theoretical result that relates the Frobenius norm error of a low-rank approximation to that a power-iterated version of the matrix. This result is crucial for the theoretical guarantees of our randomized SVD algorithm.
Lemma 1 (Power-Frobening matrix X, and let
Let X = UEV be the singular value decomposition of (real)
B = (x for an integer 2 0.
For any rank-K K orthogonal projector whose range is contained in the column space of (i.e., range(PP (P) S ra)) define m == rank(X): - K (the tail dimension). Then
||(T - ||x|- F S m क (I- p
In particular, if rank(X) $ $2k + (so m S K 1), then
||X--)xX]|= S (K + 1) |[ P]B 2011
This lemma establishes that the error of rank-K approximation of X is related to the error of approximating the power-iterated matrix B. Intuitively, power iteration amplifies the gap between the top K singular values and the remaining ones, making it easier to identify the dominant subspace. The lemma quantifies this relationship with explicit constants, showing that the error decreases exponentially with the number of power iterations q.
4.2 Randomised SVD with explicit constants
Building on the theoretical foundation of the previous section, we now present our randomized SVD) algorithm with explicit error guarantees.
Lemma 2 (Online low-rank estimator). Run Algorithm I with oversampling 2 3 and 2 0 power iterations, and let K- Kt Define the tail dimension m rank(X,)) K. With probability at least 1 8,
X; UL-VVVII s (1 (1+m m2: (2 4V
R+a s-1
20
min rank(A)gR
X, A|
In particular, rann((X) < 2k + (so m R + 1), the same bound holds with m replaced by
R +++ 1.
Algorithm computes rank- approximation of the matrix X through a randomized procedure. The key steps are:
Generate a random Gaussian matrix Ω and multiply it by X obtain an initial sketch Yo- Apply g power iterations to enhance the approximation quality, computing Y, = X(X Y 1)) for each iteration.
Orthonormalize the resulting matrix to obtain Q which approximates the column space of X. Project X onto the subspace spanned by Q and compute the SVD of the resulting smaller matrix.
5

---

Algorithm 2 Incremental truncated SVD warm-start (column append)
Require: previous rank-K K SVD (U, E, V) of matrix E RAxx new block RSASS
I: MM U
M RRxs
2: H A UM
3: (Q, R) + (r(H)
D EQERSAN R REX'
Σ
M
4: Kamall +
R
5: (U,, [,, + f (mmall)
7: + (1: (.Kk1KK)
6: U-U+( + [U
V 0
8: - 0 Is V:(;1:K)
9: return (U,Σ,
Combine the results to obtain the final low-rank approximation.
Lemma provides strong theoretical guarantee for this algorithm, showing that the resulting approximation within constant factor of the optimal rank-K K approximation. The error bound depends on three parameters: the target rank R, which should approximate the intrinsic rank of the data; the oversampling parameter s, which provides additional stability (we recommend and the number of power iterations q, which improves the approximation quality at the cost of additional computation. The computational advantage of this approach is significant, especially for large matrices: traditional SVD algorithms require ( A S min(S A, W W)) operations, whereas randomized approach requires only O(SA WS. (K + s) (2g 1)) operations, which is much smaller when K- < (in(SA, WS).
3);
Adaptive rank selection In practice, we can adaptively select the rank K by examining the singular value spectrum and identifying sigmificant gap or by setting a threshold on the relative approximation error. This allows our algorithm to automatically adjust to the intrinsic dimensionality of the environmental changes without requiring prior knowledge of the true rank K.
Robust tracking of sparse shocks
We decompose transition changes AP, RAXx into low-rank part and sparse "shock" part by (conceptually) solving the standard Principal Component Pursuit (PCP) program
AP AP,) E arg min ||]|, + IlSS|| s.t. L+S= APc.
(I)
where À= 1/Vn and n max
Proposition 1 (PCP recovery guarantec). Fix any t E [T] and suppose AP, = Le + S₁ where:
1. rank(I;) < K and Lt ju-incoherent (in the standard RPCA sense);
2. the support 52 == supp(S,) is drawn uniformly at random (equivalently, i.id. Bernoulli entrywise with rate p), independently of the singular vectors of L,;
3. (optionally, standard in high-probability RPCA theory) the signs of (St) on Q are i.i.d. Rademacher.
Let (AP), AP)) be any optimizer of (1) with À 1/v72. Then there exist absolute constants
C1, C2 > 0 such that if K
<
01 n and
S C22 we have exact recovery with probability
p poga
least 1 C3n -10 10,
AP. Lt
AP. = S,
and consequently AP + AP, - AP, || 0. Moreover, by a union bound, simultaneous exact recovery for all < T holds with probability at least -10
Implementation note. Algorithm 2 a fast subspace update routine (incremental truncated SVD) that we use implementation primitive to warm-start or accelerate numerical RPCA/PCP solvers

---

for (1) in large problems. The theoretical RPCA guarantee we rely on is Proposition 1, which concerns the optimizer of the convex PCP program (1), The per-update arithmetic cost of Algorithm is --
6 Adaptive confidence widening
We introduce adaptive, selle-action-speeeee confidence widening that scales with local environmental variation: v7s a, I) min(1, 1, ov VV (s, c c= == 2 log 4SAT, where N (s, a)
225
counts visits and (s, a, t) estimates local variation.
Bias-corrected estimation
We estimate local variation using a bias-corrected approach:
CoS log
log(165A770))
(ss a, max (0,
Σ
p.
P-111
Σ
W.
We
N f
i=t- W.
i=t W.
where Co constant, W, a variance window size. Define
V2 (8, a)
1
Σ
[1:(-18, p1-1(-18,,
W.
i=t-W.
W.
Lemma 3 (Estimator accuracy). Fix (s, and 1 W.. There exist absolute constants Co C1 2 such that, with probability at least 1 6/(8SAT),
1 u) Ta(s,a) s (s,,,1)) (2 Tr(s,),, 3
where
Ta(s,a) CiSlog(16SAT70)
Σ
W, W. (,
In particular, if (2, a) 2 (8, a). then 3 1222 (8, a) < V(s (3)))
Lemma (Total widening). With probability 2 6/8.
4SAT
SAT
Σ Ms. a,, s C CVSSogg
Slog
v1 + logT VSAB, + SA log
(2)
8
5
for universal constants C, C" 0.
This adaptive approach applies larger confidence widening only to state-action pairs with significant variation, yielding the square-root improvement uniform widening methods.
7 Temporal forecasting and shrinkage
The previous sections have focused on efficiently tracking the structure past environmental changes. In this section, we leverage this structural understanding to forecast future transitions and combine these predictions with empirical estimates through optimal shrinkage.
7.1 bastdr forecasting
Using the factors 0k Tk. Wy learned from the low-rank approximation, forecast the next transition matrix as: pprod P: + ===1 apreed oi where @pred is predicted value for the time coefficient ug at time + After computing this prediction, we project it onto the probability simplex to ensure valid transition probabilities.
For each factor k predict the time coefficient un (t + 1) using standard time-series forecasting methods such as exponential smoothing pper = (1 + - az)ap. (t), where a is smoothing parameter, autoregressive models 2 = D 6. estimated from past data. The specific method for each factor is selected using the Akaike Information Criterion (AIC), which balances model fit and complexity, allowing the algorithm to use simpler models for factors with regular patterns and more complex models for factors with intricate temporal dynamics.
- i 1). where the coefficients d; are
=
7

---

Proposition 2 (Prediction error), Fix (s, a) and write pt := Pr(- s.a) E R Under Assumption 1, suppose the time coefficients are 3-smooth, i.c. (t+1++)--uu (t(()] - / for all k. Define the one-step R. forecast P++1 := Pe + - apred Dy (s. a) Wk. followed by projection onto the probability simplex. Then there exists universal constant C > 0 such that, with probability at least 1 6/(8SAT).
K S log (8SAT/AA)) Ni (s,a)
Pt+1 - -ettlli S
[pe+1 - Palli + 3K + CV
+ (|<a(8,a)l1-
Remark. The shock term is kept explicit in the one-step inequality. When summing along the trajectory, Assumption I implies Ei= [eg(s), 0z)1l2 I Σx= max.,0 ||ea(s, I 8BBp, which is exactly why the final regret bound contains the term Dpp
7
This proposition characterizes the error in our factor-based prediction. The first term (1+ (++3K) P Pelli bounds the error due to potential model misspecification, while the second term represents the statistical error in estimating the factors. When the environment changes smoothly (8 small) and the low-rank approximation is accurate, this prediction provides valuable complement the empirical estimates.
7.2 Optimal shrinkage estimation
While both the empirical transition estimate tor and the predicted estimate ppree provide useful information, they have different strengths and weaknesses. The empirical estimate is unbiased but may have high variance, especially for rarely visited state-action pairs. The prediction has lower variance but may be biased if the model is misspecified. To combine these estimates optimally, we use
shrinkage approach P. (1 A)p: Xppred with the shrinkage parameter À par M
Var pul
This formula, inspired by James-Stein estimation [2, I1], minimizes the mean squared error (MSE) of the combined estimate by balancing the variance of the empirical estimate against the total error (variance plus squared bias) of the prediction.
Theorem 1 (Near-optimal risk). Let P. E A be the empirical transition estimate from N, samples for fixed (s, a) time and let pered be any (possibly biased) forecast built from past data only. For À E [0, 1] define the shrinkage estimator (A) = (1 A)ee + > ppred and its fi-risk (A) == E Pt (A) Pa [| Assume:
1. Asymptotic orthogonality: E B( pr, Dprod pr) = o(1/N,).
2. Bounded forecast risk: 62 == LE [10
Pa 1 is finite and bounded away from 0 (c.g.
inf, by > 0).
3. Consistent plug-in estimators: a = 1- 18-12
2 d4 = E [110 pellă]
1-1pp.1 and,
N,.
N
with window Wy - 00, by = W, Wi w, (1r7rod Pull
2 bc-
NT
Let A, = a. (b.) and Ai == az/(a; bb).. Then, as No+ + oo and W3 + oc,
(r)) (AT)
1+0(1).
This theorem guarantees that our shrinkage estimator approaches the performance of an oracle that knows the optimal combination weight, as the amount of data increases. This adaptivity is crucial for non-stationary environments, where the relative value of empirical estimates versus model-based predictions may change over time.
8 The SVUCRL algorithm
Having developed the key components of our approach: online low-rank approximation, robust tracking of sparse shocks, adaptive confidence widening, and temporal forecasting with shrinkage, we now present the complete SVUCRI. algorithm. Algorithm 3 presents the main loop of SVUCRI.. Let's examine the key components in detail:
8.1 Algorithm components
The algorithm starts by initializing several data structures including counters for visits to each state-action pair and transitions to each next state, empirical estimates of rewards and transition probabilities, and buffers for storing recent changes in dynamics and the learned factors.
8

---

Algorithm 3 SVUCRL
Require: horizon 7'; windows W, W., Wy; confidence 6; initial state
1: Initialize counts Ni (s, =0, Ni (s, a, =0; (s a) = Pi a)
2: Initialize buffers for (AP.) zero; initialize factor store (ūz, wx} empty
3: (Build initial radii) For all (s, a) set ((s.
< 0, r/(s, a. 1) < 1. (x, <- (s, <-
4: Episode index
1, start time 7(1) f-
5: Compute optimistic policy Fm by EVI using centres ýr p and radii (radi, rad,.+
6: for 1 to 7 do
7: Observe 8s, play or = Fm (st). observe rt, 8++1
8: Update counts: N5-1(5t, 0x) +- Ne( dt) + and No+1 (st; de 8t-1) <- No ar, 8e+1) ) +1
9: Update empiricals (sx, 0:): Fe+1 (t) Ne(ac. Pa(eraa)) Pa(or.a)) (et2(1))),0e) No. (011(0)))))) (avaa))
N141(5(.a1))
keep others unchanged
10:
APe+1 <- P++1- - P. and update the circular buffer if é mod W = 0 then
11:
Structure update (every W steps)
12:
Form X; = P AP]
13:
Run Algorithm. I on X, get (U, U. V)
14:
Use Algorithm 2 update the rank-K K basis
15:
(Conceptually) solve the PCP program (I) on AP; to obtain (API, APP).
16:
Extract (ūk, Hi from the left/right factors; recover time weights for i 10---++,.... +I....,, by
(1) x (AP.. Eg );; normalize as needed
17:
Compute an approx_ radius from the RSVD/RPCA residual to be used transition balls end if
18:
19:
(One-step forecasting) For each i compute aprrod (++1) (ES/AR)
20:
For each (s, a): gran (s,a) IIa (p(( + Σ apnd (1+1) (s, (s, wx)
21:
(Shrinkage) For each (s, a) compute
(s, = 1 1- (8,)
() = W, i=t+--
Σ
acti(s, a)
(s, +- 1p. (st1 + b (s,
pe+1(11s;)) + ( (1- +h+ (11,,
22:
(Local variation) For each (s,a) compute (s,a,t+)) window W, and a(s,a,t+1)
min(1, ey (tl/s,,tt11//(ttttee.. (Confidence sets for next start) Store radr,t1(s,a), radp,ti(s,, a). and the transition ball Pr+1(s,a) = {p: :p:10 1p ps-1(s, a}]l S radp.ct1(s, a,s, aappaxppaadaaat radius} if EpisodeEnd (e.g., (....,(ss.)) a) Ne(s, a) 2N or r(m) 2 Hm) then
23:
approx_
24:
25:
m 4- m + 1, (mm) + ++
26:
Run EVI to compute 7... using centres pr(m) and radii saved at r(m)
27:
end if
28:
end for
Every W time steps, the algorithm updates its model of the environment structure by running two key subroutines: Algorithm I (Randomized SVD) learns low-rank approximation of recent changes in transition dynamics, and we (conceptually) solve the PCP program (I) to separate low-rank drift from sparse shocks. In implementations, Algorithm 2 provides a cheap incremental truncated-SVI warm start for the low-rank subspace used by the PCP solver.
At each time step, the algorithm constructs confidence intervals for rewards and transitions, where the reward confidence radius is rad,, (s, a)
(1g(455A775) and the transition confidence radius N=(s.))
is (s, = 2S (og + 17, a, t). The reward confidence radius follows standard N.(5.))
concentration inequalities. while the transition confidence radius includes both statistical term and the adaptive widening parameter v7(s, t) derived in Section 6.
8.2 Episode-based policy computation
SVUCRI. follows an episode- approach where each episode corresponds to a period of executing fixed policy. An episode ends when either the visit count to some state-action pair doubles

---

fixed number of time steps has elapsed since the last episode. When episode ends, the algorithm recomputes an optimistic policy using Extended Value Iteration (EVI), which finds policy that maximizes the expected reward under an optimistic model of the environment where transition probabilities are chosen within confidence intervals maximize the value function. The EVI algorithm continues until the span the value function changes by less than 1/v/(mm), where r(m) is the starting time of episode m, ensuring that computational effort scales appropriately with the episode length.
Regret analysis
In this section, we analyze the regret of the SVUCRI algorithm, establishing theoretical guarantees on its performance in non-stationary environments. We begin with lemma that bounds the per-step regret during each episode.
Lemma (Per-step regret). With proh. 2 - 6/2, for episode m and E [r(m), T 7(m + 1) 1}.
P (r-r((88 (8t, ax) < (7(m) + 2varr,, + max parp,t + 2rad, + 2D max (rad ((m) + approx).
This lemma decomposes the regret at each time step into several components:
(r(m) Error due to the approximate computation the optimal policy using Extended Value
Iteration.
2vary,r and 2D maxxparp.. Regret due the actual variation in rewards and transitions since the beginning of the episode.
(mm) Statistical error in estimating the rewards.
Statistical error in estimating the transitions.
maxx7 Additional regret due to the confidence widening for non-stationarity.
2D approx::xx: Error from the low-rank approximation and RPCA decomposition.
Building this per-step analysis, we establish main regret bound:
Theorem (Main regret bound). Under Assumption I, with probability least 1 - 6,
DynReg, = - VVSAA SYAT limax By Dmooe bmaax D S A Dmodd By Duaxe v KT+ Σ Ermmee))
where T.max max (m + 1) (m)) is the maximum episode length.
9.1
Interpretation and tightness of the regret bound
The bound in Theorem decomposes into the following contributions: the statistical terms ō( (VST++ Dmax SvAT from reward and transition estimation; the wirhin-episode drift terms Lmax B, + Lmax Bp, which capture accumulation of reward/transition changes since the start of each episode; the widening term Ö 5Dmaxx55/ Bp) from Lemma 4; the structure/shock terms Ö(D ((mmaxVIT) m due low-rank approximation and sparse shocks; and the planning error Ets Er(m(t)) which can be made lower order with suitable EVI tolerance schedule.
10 Discussion
SVUCRL exploits structural patterns in non-stationary environments through matrix factorization. unlike prior methods that use uniform confidence widening. By decomposing dynamics into low-rank and sparse components, we distinguish systematic shifts from isolated anomalies, enabling more efficient learning. Our regret bound improves from T3/1 VT dependence, matching conjectured optimal rates, with an additional VK factor reflecting low-rank complexity. Key technical contri- butions include martingale-baser incremental RPCA, explicit constants for randomized SVD, and bias-corrected local variation estimation. SVUCRL demonstrates that learning complexity depends on the intrinsic structure of changes, not just variation budgets. Practical implementation involves tuning window sizes and rank parameters, with future work including continuous spaces, function approximation, and empirical evaluation real domains.
10

---

Acknowledgments
This work is funded by Hanoi University of Science and Technology (HUST) under Project No. T2024-DD-024
References
[1] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107, 2020.
[2] A. J. Baranchik. A family of minimax estimators of the mean of a multivariate normal distribu- tion. Annals of Mathematical Statistics, 1964.
[3] Andrew Bennett, Nathan Kallus, and Minuna Oprescu, Low-rank mdps with continuous action spaces. arXiv preprint arXiv:2311.03566 2023.
[4] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed arndd--iimd- problem with non-stationary rewards. Advances in Neural Information Processing Systems, 27, 2014.
[5] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM, 58(3):1377, 2011.
[6] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Non-stationary reinforcement learning: The blessing of (more) optimism. arXiv preprint arXiv:2006. /4389, 2020.
[7] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for non-stationary bandit problems. Algorithmic Learning Theory, pages 174-188, 2011.
[8] Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53 (2):217-288, 2011.
[9] Steven R Howard and Aaditya Ramdas. Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[10] Steven Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. arXiv preprint arXiv: 18000:18100082400, 2018.
[11] William James and Charles Stein. Estimation with quadratic loss. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, volume 1. University of California Press, 1961.
[12] Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pages 740-747, 1999.
[13] Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11:19-60, 2010.
[14] Wenzhu Mao, Kaiqing Zhang, Ruoyu Zhu, David Simchi-Levi, and Tamer Başar. Model- free nonstationary reinforcement learning: Near-optimal regret and applications multiagent reinforcement learning and inventory control. Management Science, 2024.
[15] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. Advances in Neural Information Processing Systems, 27, 2014.
[16] Sindhu Padakandla, Shalabh Bhatnagar, and Theodore J Perkins. Reinforcement learning algorithm for non-stationary environments. Applied Intelligence, 50(11):350-33666 2019.
[17] Yoan Russac, Claire Vernade, and Olivier Cappe. Weighted linear bandits for non-stationary environments. In Advances in Neural Information Processing Systems, pages 12040-12050, 2019.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly articulate the contributions, with all stated claims properly supported by theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
limitations sections is provided in the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
12

---

Justification: We provide the full set of assumptions and complete (and correct) proof for all the claimed theoretical results in the paper
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: We provide a theoretical study with an improved regret bound for non- stationary reinforcement learning. The results of the paper are fully theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
13

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: We provide a theoretical study with an improved regret bound for non- stationary reinforcement learning.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines luttps://nipg cc/pu
blic/ Sunides/CodeSSubnng
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
SuoeeS/mmm Sanasuuumsssss wesssssollll.ooooooo onnolicc) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This is a theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
14

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /neurips.....// cc http//pll//tticccuiieeeeo
Answer: [Yes]
Justification: Code of ethics is respected.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
15

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work presents no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The work does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com/ /dtaasata has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
16

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper provides a new theoretical study for non-stationary reinforcement learning.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
17

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpss////uuisspeeeeee cc/ wec/oonferentie wwweeeeeee////////eeee /LLM) for what should or should be described.
18

---

APPENDICES - Detailed Proofs
A Randomised SVD: proof of Lemma 2
Notation
For matrix let 0i 2 02 1 ... denote singular values, ||||| oi the spectral norm,
| = of. Projector P has rank K unless otherwise stated.
A.1 Proof of Lemma
Lemma A.1 (Tail energy identity for the Frobenius residual), Let X E RR have compact SVD X = UEVT, with singular values 02 2 ... 2 or > 0 and rank(X). Fix E {0....,,) r
and write
U U= U U1], Σ Σ R
11
where UR E Rm R contains the top K left singular vectors and Σ diagldR+11.... R+1...., ,,)...,,,,,,..........))),)).)). Ui is ontains any orthonormal basis for the orthogonal complement of span. Let P. = U U be the orthogonal projector onto span(UR) Then
II - P)X ΣoJ oj
j>R
Moreover, for any rank-K orthogonal projector Q,
II(T Q) N
Σ
of.
j>R
with equality if and only if range(Q) contains (any choice of) top K singula subspace of X (up to degeneracies in the spectrum).
Proof. Write X = UEVT and partition U, E as in the statement. Because U is orthogonal and UR U- I 0). have
PIU = U U- -UR(UST = 10 U1].
Hence
Σ L
(I- (I- 10 U1
V ULE.V.
Σ
The Frobenius norm invariant under multiplication by orthogonal matrices, so
P)X1 |
|
Σ j>
establishing the identity.
For the optimality statement, note that for any rank K projector Q,
[(( - x || - || Tr( Tr(X QX) - Tr(E E),
-
where W = TTQU is itself an orthogonal projector of rank R. Therefore,
!QxI T((WE) < Σ o3
by the Ky Fan maximum principle (the sum of the top K eigenvalues maximizes Tr(W-) over rank-R projectors W). It follows that [](/ X| 2 Σj>k oj, with equality precisely when W diag(IR. R. 0), i.c., when range(Q) span(UR) R) (up any multiplicity in the singular values). D
19

---

We restate the lemma.
Lemma 1 (Power-Frobenius). Let X UEVT be the singular value decomposition of real matrix X, and let
B = (X for an integer q 2 0.
For any rank- K orthogonal projector whose range is contained in the column space of X (i.e., (ange(P) S ra)ne(X)), define m == rank(X) K. Then
- P) S m - 1441
In particular, if rank (X) s 22k= + (so m S K + 1), then
||X- - (R + 1) ||T
P) | कह.
Proof. If q 0, then B X and the claim holds with equality, so assume q 2 1. Let the compact
SVD of X be X UVV T with rank(X) =: rx and singular values 01 2 02 2 ... 2 Trx > 0.
Set := 2g + and 7 == 1/r E (0, 1). Since B = (X = UV I V = UV'V the
singular values of B (B = oz.
Let P be rank- R orthogonal projector with range(P) S range(X)
Define weights
aj = || - P)u 1 = 2 (1 P)us E [0,
j = L TX.
Because range(P) P) C range(X X) = range(U)) and rank(P) = R, we have Ir(UT PU) = tr(P)
K, hence
x Σ
" u(U PJU) -x R=m.
Now compute the two residual energies:
rx
II(T - P|EE| uEU (I E)
a
1=1
and similarly,
TX
II(T - P)BB I1 PJUE 1
Σ
azozz.
Let Øy : o so that o3 23. Since + t is concave on R., Jensen's 's inequality with weights aj/m yields
a,0} S m 1-
( a ,,
1=1
1=1
Substituting back gives
[I(I - P)XII v m P)B
Recalling = 1/(2g + 1) and taking square roots,
[((T -IT- P)X| m मंं IIT P| T/TT
The final "in particular" statement follows from m rank(X) - R S R + when rank(X) <
2K + 1.
20

---

A.2 Proof of Lemma 2
Full proof. Let X X, and k= = K. Set == 2q and define the power matrix
B = (XX )9
Algorithm/ draws Gaussian Q2 R *)**+)) forms Y BΩ2 computes an orthonormal basis Q = qr(Y), and returns the rank-k approximation
X : UEV QQ (X)),,
where (QTX); denotes the best rank-k approximation of QT X in Frobenius norm. Let Po == QQ".
Randomized range finding for B. By the standard Frobenius-norm bound for Gaussian range finding with oversampling s 2 (e.g.. [8]. with probability least 1
[I PQ) & (2 AV
kitt s-1
min (ank(A)
| F 12
1
|| BxllF.
(3)
Since the factor in parentheses is at least 1, may (harmlessly) square it and write
II Po) s (2+4/ = BxIlF..F.
(4)
From B-error to -errror via power-Frobenius. Note that rQnge(Q) C range(Y) S range B)
C
range(X) so we may apply Lemma I [ (Power-Frobenius) with P = Pq. Let m == rank(X) k. Then
( PIl S m II( Pq) B T01T
(5)
Squaring and using (4) yields, on the same event,
II(I Po) S m 2g
(2+ (2+4V
kts s-1
TT1T
|B B
(6)
Comparing tails of B and X. Write the SVD X as X Then B = UEEVV so
UVV T with singular values (a,)/21-
| BA1l =
Σ o3
8>b
Hence
B
B&
Σ oj = X Xxll
where we used the norm monotonicity ||a||r into (6) gives
||al| for 2 applied to az = 2 0. Plugging
IITT XI S क (2 + 4
kts
|X- 1
Rank-k truncation inside range((). (Q). Since x = =QQQQT xx)x)).s
|X - 81 = [| P2) + _!Q -Q xxal
Moreover,
-x-(Q" (Q_ X)*lF= x
min
x - A|l s 11Q Xt)lIe S -|Ix - Xxlle,
because ||Q 1|2 = 1 and Q Xx has rank at most k. Therefore.
XX 812 S [[ - Po) + |X- - X < (1 m 2 2+ 4 / kto IelI | - -x
and X 1 = min (A) |X- Al2 by Eckart- Eckart-Young Loung-Mirsky.
Finally, the event used above fails with probability at most Ge so choosing max(3, [log(6/8)1} ensures probability at least 1-6. 6.
21

---

A.3 Extended Analysis of Randomized SVD Performance
The performance of the randomized SVD algorithm depends critically on the choice of parameters, particularly the oversampling parameter and the number power iterations q. Here, we provide additional insights into these trade-offs.
Effect of Oversampling The oversampling parameter controls the additional columns in the random projection matrix S2 beyond the target rank K, Larger values improve the accuracy of the approximation at the cost of increased computation. The theoretical bound in Lemma 2 shows
that the approximation error scales with
R+s e-1 which decreases increases.
In practice, modest oversampling (e.g., in accuracy. The marginal benefit diminishes for larger values, suggesting a practical trade-off around = (llggSS))).
10) often yields significant improvements
Effect of Power Iterations The number of power iterations has an exponential effect on the approximation quality, as evident from the 204T exponent in the bound. Power iterations amplify the gap between the dominant and subdominant singular values, making easier identify the principal subspace.
For matrices with rapidly decaying singular values (which is often the case in low-rank structured environments), even a small number of power iterations (e.g., = 1 or q = 2) can dramatically improve accuracy. For matrices with more gradual singular value decay, larger values of may be necessary.
Adaptive Rank Selection While our theoretical analysis assumes a fixed target rank K, in practice, can adaptively determine the appropriate rank by examining the singular value spectrum. We propose two approaches:
Gap-based selection: Choose A where there is significant gap in the singular value spectrum, ie.. σ ///oR41 for some threshold
(SA, of 7 for Energy- based selection: Choose the smallest K such that Σ of Zim1 some threshold (e.g.. = 0.95).
The adaptive rank selection ensures that capture the intrinsic dimensionality of the environmental changes without unnecessary computational overhead.
B RPCA via PCP: proof of Proposition 1
Proof of Proposition I. Fix any t E [T] and write AP, = L, + S. with rank(L,) I K. Let n == (Sax(SA, and set = 1/Vn.
Under jæ-incoherence of Ia and the assumed random support model for S, (independent of the singular vectors of I.),, the standard RPCA/PCP recovery theorem (e.g., Candès et al. [5)) implies the existence of absolute constants C2 > 0 such that if
C1 T
K
and
p S C2
/ log
then (L,, St) is the unique optimal solution of the PCP program (1) with probability at least 1-c3n -10 Therefore,
Lt. AP, F 0.
AP.
AP. = S.,
and in particular |AP; + AP.
Applying union bound over 1,..., yields simultaneous exact recovery for all S with probability least 1 cn
22

---

C
Bias-correction details (Lemma 3)
Lemma (Estimator accuracy). Fix (s, a) and time >> We. Define
1 W
V22 (s)
Σ
- - p:-1(+ls,a)li
i
and let the bias-corrected local-variation estimator be
V(s, a,), = max 0,
(p((1ss - -1-1(11s, Co
Σ
W 1
W
N, (s
i= W.
bias term
raw
There exists an absolute constant Co 2 1 such that the following holds. On an event of probability at least 1 8T(SSAT), for every (s, a) and every t,
1 122 () - (e(s,a) S (s,a,1) & 3 3V (s) + (x(s,),,
(8)
3
where
(((sa) (165A(()
Σ
1
We
(s,
imt-W,
for an absolute constant Ct. In particular, if the local signal-to-noie noise condition
(p,(s, 2 (s)
holds, then the purely multiplicative bounds stated in the main text follow:
1 V2 a)) S (s,a,t) s (s)
3
Proof. Write, for brevity, p; == pr(-Is, a). p. == p-,. a) and N == N;, Let the sampling errors be 9 Pt and the true local change be us == p Pi-1- Then
p. - P- uy (e. 1,-
High- prtbbbbrbbbbitty control of the sampling error. For each i, conditional on the past, p. is the empirical distribution of N,* multinomial samples supported on S states. Hence by standard concentration bound for multinomial means & (e.g. Massart/DKW + union bound),
S Slog A0 +1)/6)
|| s 2/
N
holds for any fixed / with failure probability at most AT(.++1)) Applying a union bound over the at most (W, + 1) indices
(t W. - 1,...,t 1} yields the simultaneous event
C. ||s:|l <
Wi (t W. 1,...,6-1 1},
(9)
N,
with probability at least 8/(165 for absolute constant C. One-step upper/lower bounds. For any vectors F, y we use
|| + yll? < |||=||| + 2||//
||x + yll 2 ||101] |ly/1
Apply them with (a + 8)2² < 2(a² + 32) to obtain
and = 6-- and use ||e. e-1ilh < ||ai|h + ||e--1lh plus
1o. Pi 1| < 2 + 4 + ||a;- l1;)
(10)
j0 Pi 1| 2 111411 I17 + |
(11)
23

---

Averaging over the window and bias correction. Define
P Summing (10) over i = 1- W , 1 and dividing by W. gives
Σ
p0 Pi- 111
V2 p.t
||
W
W
i=
i= W.
.
V raw
S 2V
+
8
Σ
lesilli.
p.t
We
i=t
W
since each ||e:|] appears most twice in the sum Eleee
118x- Similarly, from (11),
raw
V2 P.t
4
Σ
2
We
On the event (9), we control the extra endpoint term by the monotonicity of N (it increases by at most per step):
2
2
N
N
N
W.
W.
t= W.
hence
Σ
33
Σ
[-1
i=t-W-11 N
N
W.
Therefore, absorbing constants into C², we have
Σ
C
AT
| <
W
W.
N Choosing Co sufficiently large (e.g.
L-t- Wi-1
imt- W.
Now subtract the bias term and use V - maxf0, Vrawe bias}.
Co 2 8C) yields the two-sided form (8) with
(s( S
log log AT (T(
Σ W. (T)
W
for absolute constant C1. Finally, if 2 (s, a) 2 6T, (s, a). then
D.t
(s, a 1) V - -r, 2 122 p.s
(s,,,11) S 2V + rr S 312 p.e.
which gives the multiplicative bounds.
D Proof of Lemma 4
Lemma (Total widening). Let
a,t, min(1, (ss...t)) (s,
4SAT
c 2 2S log
where (s, a) is the number of visits (s, a) up time and V the bias-corrected local- variation estimator from Section 6. Then, with probability at least 8/8.
4SAT Σ n(s 1) s C //Sloo log
SAT
v1 + log SABB + C' SA log
(12)
8
8
for universal constants C, C,C²> 0.
24

---

Proof. For each (s,a), let (1( < a)( < .... < (Nr(s.a) (s,a) be its visit times, and set io == co log( log(S.AT/)), where co is the constant from Lemma 3 (Estimator accuracy). By that lemma, for any triple (s, a, t) with N (s,a) 2 io.
$/ (s, as, S 3 as)
holds with probability at least 1 1 6/(85 A union bound over all at most SA T triples shows that there is event & of probability at least 8/8 which the two-sided accuracy above holds simultaneously for all (s, a, with (s,a)) io-
Fix (s, a). For the first ig visits, we only know 17 S 1, hence
min (x.o), 10
E
((s,a,((s,,a) S i0 1.
Summing this over (s, a) contributes at most SA (io 1) ((SAAogg(AAI16) the total in (12).
For the "mature" visits 2 in, on E we have
as,,a, min(1, o (s....ttss)))) 1 o s cv3 (e.n(s
vi
By Cauchy-Schwarz and the bound 2imio S logn.
(r(s,)) ((s,a,t((s,)) a)) sev3
Nr(a.a)
(1)
Σ
i=
Nr(s,a)
Nr(s.a)
1/2
1 1/2
S 3v3
im2o
Nr(s.a)
1/2
S ev 3(1 + log log T)
(8,
Another application of Cauchy-SShwwrzzyilleee
Ny(s,a)
(r(s,a)
(o 1/2
((s.a,t((s,a)) S ev log
(8,a)
Amfo
(s.a)
Nr(e,)
1/2
S cv
ee/3(1 3(1 + log T) V SA
Σ (8.0)
(1,)
Let A = maxx,a a - - al1 E [0,
For any (8, a) and any 4
V 1
(1:((11,,)) - - <
Σ (AP)²
W.
W i=t- W.
i=t-W.
Therefore along the trajectory.
T
Σ (L)
Σ
(
Σ
(AP)
W.
since each (AP)² appears in at most W, windows and the factor 1/W, cancels. Finally, because A we have ( < 2A hence
T
(2. (8c, 0z)
S
AC = 2B..
1=1
25

---

Putting the early-visit contribution together with the bound from Step and recalling e 2 log(45A7/0),
ASAT
Σ (st, ac, 1) s (A -1 + 2 25
v + +og VSA /2Bp
SAT
4SAT
I C' SAlog 8 V
C
S/log
1 logT VSABp.
8
which is precisely (12). This completes the proof.
E Forecasting error analysis: proof of Proposition 2
Proposition 2 (Prediction error). Fix (s, a) and write pt == pc(. 8, a) E IRS. Under Assumption 1, suppose the time coefficients are 8-smooth, i.e. (t+11) up (x)()] Define the one-step forecast
8 for all k with BK S 1.
R,
P = Pe +
Σ pred as) 0g.
k
k=1
followed by projection onto the probability simplex. Then there exists a universal constant C' > such that, with probability at least 5/(8SAT).
K KSgogg85 (85A4/8)
| - P(+1l1 & ||p+1 - pella + 3K + CV
(13)
N, (8,
Moreover, if the structured change satisfies the rowwise no-cancellation
(1(()) uk (8, a) wk
2 C
(t)( for some e. E (0, 1],
then
pree Pi+1
Pr+i 111 < (1+
BK c,
||pet1 pelli + C,
K log(8SAT/))
N,
Proof. Abbreviate Pt pel: a) and fr pi(: 18, Recall the structured variation model the row (8, a):
Σ (x) v(s, wx cc(s,a),
|wwll s 1, (cx(s, S1. (14)
Pt+1 Pt
Let the (unprojected) one-step forecast be
R, Ts, a) Tog-
pred Pe
Σ
pred k
the algorithm outputs Prrn by projecting Pern onto the probability simplex in é,, i.e. Prrte arg minge A ||q suffices to bound the unprojected error; for simplicity we keep the notation Pr for the vector being bounded below.
pored l1, then since Pt+1 A we have || Pt41ll1 & I|ppred Pe+1lll Ill. Thus
Write
R
K
spred
Pi+1 = (ot
Pt)
+
predd (s) wh
(())) wh - (s
(15)
FemP
Fank
Eisc
Hence, by the triangle inequality,
pppnd
pe+1l/ <
Eemp 1 + Etaoll1 + |eEhkll
(16)
26

---

Step 1: empirical term. By Massart-DKW for multinomial means and union bound over S next states,
S Slog (ogg(8AT/0)
|eem |11 pp Pell1 s VV
(17)
N₂ (s,
with probability at least - 81((1ATTT
Step 2: factor term.
Insert and subtract the true factors:
R.
Etac 1
iigeed ux((t) ox wk
Σ R=1
ppred
(8x(s,, Wr (x(s, wx)
Tooe?
Toub
(18)
(a) Coefficient drift + one-step persistence prediction (Option A). Using (x, S and ||wl|| 5
K
Teoef
pred ux(()]-
Under Option A, a natural one-step predictor for us (I) the persistence predictor apred := ūn (1 1), where ūi( - 1) is any estimator of the coefficient vector u(t - 1) based on data available up to time / (e.g. computed from the previously estimated low-rank. factors).
Add and subtract up(t - 1) and use 3-smoothness:
K
K Σ k=1
apred
ux(t)|
Tx(t 1) uu(tt - 1)
lug(t 1) 24x (t)
k=1
K
ut(t 1) - ux(t 1)1 + BK.
k=1
It remains to control the Â : Pe P1-1- Assume the coefficient estimator ū(t 1) is stable/Lipschitz in the data, i.e. there exists a constant O(1) such that
error at time - 1. Let A. == Pt Pt-1 and
āt - 1) u(t 1 < L L - dell.
(This holds, for example, for least-squares estimation onto a well-conditioned dictionary, or for any linear/M-estimation procedure with bounded condition number; the constant L is absorbed into the final universal constant.)
By Cauchy-Schward
( - uu -x(1-1) S VK a((1 - 1) u((- 1)/12 S VKL 18.
Aella-
1=
Moreover,
| A 11, < P. pell2 1p:-1 Pt- S | pr 10-11-
Applying the Massart-DKW bound (17) to both P. and p (and union-bounding the two events) gives, with probability least 5/(85AT).
S log(8SATYO)
| - S C²
(s,
for universal constant C'. Collecting the bounds and absorbing L, C' into constant C₁ yields
K S (oooo(8SAAT (8SAT/5)
Tooef S 3K + Ci
N (8,
27

---

(b) Subspaceffactor estimation error. For each k
[ a) Wn vx(s, ws 1 _ 1 vwwk Frow(o.a) 3 V$ T vxwi F
Using Sauchy-Schward over k:
R.
Tuub
(ogredy )2)
1/2
Σ
uu a))x 1/2
Invoking Lemma 2 (randomized SVD with power iterations) together with standard concentration for the empirical increments forming X, |AP.ww+:.... APr). the second factor is bounded by
R.
1/2 s Cav [x a) un(ss, vx(s,
S Slg (8g(8ATT/6) N (s,a)
on an event of probability at least (8SA))) for a universal constant C2. (Any dependence on the predictor energy ||[pred||2 is absorbed into C2; for the persistence predictor this energy is bounded under the same stability/condtioningg assumptions used above.)
Therefore, enlarging constants if needed,
K S (8ggA8STT/)
Tuub $ C2
(19)
N (s,
Combining (a) and (b) gives
K S log 8S AT/8) N (s
Fiac 11 S BK + CV
for a universal constant C.
Step 3: shock term. By definition, || (1, a)ll We keep this term explicit; Assump- tion controls only the cumulative shock budget 2, maxx,a [se a) < 8n By. not a pointwise bound fixed time
Finish. Plug the bounds on Eemp. Ejac, and Eshi into (16) and absorb |mmpll into the same statistical term by enlarging C. We obtain, with probability least 67(
K S Slog (85AA/8))) N, (s,a)
Ptt1 Pt+1ll1 < |Pt+1 - Pilli 3K + C.
[|e,(s,))l) a))l.
Using [|c((s,))l S 5g Bp yields the stated corollary form.
Remark the multiplicative variant. The step "3K < (3K/c.)llP:- - is not valid in general without an additional lower bound on [Pc+1 - Ps lll (or another non-cancellation condition involving shocks). If you want multiplicative form, you must explicitly assume ||P:41 Pelli Cmin 0, in which case 3K < (8K/cmin) (lpt) - pelli -pelli and the multiplicative bound follows.
Shrinkage optimality: proof of Theorem 1
Theorem (Near-optimal risk (restated)). Let P. S-1 be the empirical transition estimate from Nit samples for fixed (s, a) at time t, and let ppred be any (possibly biased) forecast built from past data only. For E [o, 1] define the shrinkage estimator (A) = (1 A)P. + spred and its fy-risk (A) == T.. | (A) Pt [|]]
Assume:
(A1) Asymptotic orthogonality: E (ie Pt, spred pi) o(1/Ntt) (c.g. holds if the forecast
only data independent of the N samples that form pr: sample splitting suffices).
28

---

(A2) Bounded forecast risk: b, ||ppted prll
finite and bounded away from along the
considered times (inf, b, > 0 is enough).
(A3) Consistent plug-in estimators:
a 1 1
1pr1
0f = E[
pell
No
N₂
and, with a window W, + 00,
b, W W
pppedd pill2
1-
12
Pg by.
N;
Let the data-driven weight be A, == ā.((ā; + b,) and the oracle weight be x = a+/(at + b.). Then, No and Wy + oo (no rate relation between them is needed),
(rd) + o(1) Re(AE)
Proof. Step 1. Write X, = Pr Pt and Y, = Pp pr. By definition,
(A) EE [1 - X) Arell2] (1 a) Xbb + 2A(1 1)cr
where a, F. 11 b 211 and c ( Yi) Assumption (A1) gives cr o(1/N,t).
We focus on the oracle weight in the statement.
G
Plugging X into the quadratic yields the exact identity
R₂();) (1 aa + (2 + 21;(1 x;)a = aebe(ar + be + 20r) (at b.)2
Therefore,
ardr 1 Re(A;)
20
a.b. (1 + o(1)) a, + bj
+ be as + by since at b. 2 b, and b, is bounded away from 0 by (A2). In particular, because at (1 Ip: |,, O(1/N()) whenever p: is not deterministie, have
Rx = O(1/Nt))
(If Pt is deterministic then a, ā 0, and both oracle and data-driven risks are identically the conclusion is then trivial.)
For reference only: the exact minimizer of R. is xopt risk is
(a: - ct)/ b. -2c)) and the minimum
(a(APPt)= = arb, 2
Oe + b 2ct but we do not need this for the ratio claim in the theorem statement.
Step 2. Define g(a, b) == a/(a + b). By (A3), â + a; and by b, in probability. Moreover, a. a, = Op ((N()))3332) (delta method for ār = (1 / and by b. =W, 1/2)
(window average). A first-order expansion of g at (a,, by) yields
dg
d, 2; aa
(a,, by) (ā. az)
(ar, be) (b. b.) + 0pl [ā. - ail + 16,- -b.l)
Zb
Because
0g 8n
(a+b)z (11) (by (A2)) and
b
= (a4832 = 0(a;) = =O(1/Nt) 0g
ah
R, - 2o (N( 3/2) + +0
=o ((Nt)-11)))
29

---

In particular, Ro - X; in probability.
Step 3. Since R2 is quadratic in X, we may write a second-order Taylor expansion around X;:
(A.) RA()) [2 (A+ x;) + R2 (A. x2)²
where the second derivative is constant
Ry 2(a + b, 20x) 2(6, o(l)) ((1)
by (A2) and (AI).
Also
(₂(A) 22(a + b -22) 2(a, ct)
so with X; = aa/(aa b:),
((();) 20:
a1 + bq ) ) =o(1/N²t
201-
by (AI).
Combining with Step gives
R₂(A,) (Ne - x1) = =(1/N,t)) 90p ((N,))
= ((N())
and
1 R Ar A1)² =01)= Oz
9(1)
((N+))
= 0 ((NNt)))))
Hence
(R.) - Re(A)) Op (,
Finally, dividing by (x())) O(1/Nt)) from Step yields
R₂ (A,) - -1 o,) = o(1),
R₁ (At)
as N2+ co and y + oo (no rate relation between them is needed). This proves the claim.
Remark (on the plug-in MSE). The windowed proxy W, El Ipp p. converges to b. + de because ElIp; pall a, and the cross-term is o(1) by (A1). Subtracting the known multinomial variance proxy (1 113/ yields the consistent b, used (A3). Using the uncorrected proxy leaves the theorem unchanged, since the induced bias in Xe is O(a,) O(1/N)) and the ratio R₁ (x))))/R()))) still tends to 1.
G Full regret proof
Episode notation Tm-
Episode m starts at r(m), ends at r(m + 1) - 1, and follows optimistic policy
G.1 Decomposition
For E episode m
P7 T S (pi pm) + (pm Fmm (t)) + (Fmm r
B.
Term B, < L/) by value-iteration tolerance. Terms A. and C₁ are bounded by variation (r.p), statistical radii, widening 7), and approximation approx exactly as in Lemma 5.
G.2 Summation over /. < T
1. Doubling episodes + ΣT B, S 2VTooT..
2. Reward/transition variation budget (triangular sum within each episode): using (29),
T
T
varr,t S Lmmx
varp. S Limax Bp.
30

---

3. Statistical radii (see (23)-(24)): E rad & Ö(VSAT) and Σ radd 1 Ō(VVSAT) Ö(SVAT).
4. Widening: Lemma implies (25), hence Dmax Σl= = Ō(D SABB,)
5. Approximation: (27) gives E'= approx,
Bp VKT),
hence
max Ei=1 approx, maxx Dmax KT).
Multiply the transition-related terms by Dmax, collect logarithms into Ô and obtain Theorem 2.
G.3 Detailed Regret Decomposition: Detail proof of Lemma 5
Proof. We break the proof into four steps:
1. Define the good event and get optimism.
2. Relate pŻ (optimal at time f) to Pm (optimistic gain at episode start).
3. Bound Pm Ta (st, az) using the EVI residual for the specific optimistic model (Tm, Pm) plus confidence radii.
4. Combine the bounds.
Throughout, we use that all MDPs in the sequence are communicating with diameter at most D max
Good event and optimism. At the start of episode m (time т = =T(m),, the algorithm has:
empirical reward F, (s a) and empirical transition p.(- ssaa;;
reward confidence interval
rs, = (s,(s, - ra, a), a) + (s,,,
transition ball around the shrinkage center Pr 8, s)
C+(s,att)= = {p: 11p---f s, s.a)ll S radp.r a,t, approx
On the good high-pre high-probability event (from the concentration bounds for multinomial estimates, plus the construction of y and the approximation bound), have simultaneously for all 8, a, 2
rx (1 a) E (s. a)], p s. E C² as,
At time r, EVI computes an optimistic MDP Mm (Fm. Pm)) by choosing, for each (s, a),
some (m, |r (s. some (. s, a, C+,
to maximize the average reward under the computed policy 7m-
Because (rr,Ph (r) itself lies inside those confidence sets, standard UCRL-style optimism gives
p
Pms
(I)
where pł is the optimal average reward in the MDP M, (Fr.pr).
31

---

Lipschitz continuity of the gain in (r, p) and drift. to pt (optimal at episode start), and hence Pm.
We need to relate Pt (optimal at current time
Claim (Lipschitz in the model). Let M = (r, p) and M' = =(r' ) be two communicating MDPs of diameter most maxx, and let be any stationary policy. Then
Pr. (M) p=(()))
< ||r - 1' ||r-rrlla + Dmax l|p - plo
(2)
where
Ip p' 11,,,0 max pp (8 (((ssa))ll 8,0
This is standard: write the Poisson equation for M', use a bias function h with span S D Dmax and compare
P- P=(M)) + (s) = r' (s, (+)) + p'(: 8,)(s))
with the same quantity where you plug in (r, p); the inequalities follow by bounding (r r') and (p- T' using ||r-r'll r' and maxx ||p p' 1,,00
Apply (2) with:
M2 = (rt,pe) (true MDP at time I),
M, = P+) (true MDP at episode start),
π = प (optimal policy for M,).
and use the definitions of var,,; and parp,t
p = P=; (Mz) S Pm; (Mr) + varr, + Dmax
S pt + var,,t + D Dmax var
Combining this with optimism (1) gives
Pt Pm I varr, + Dima var
So the drift plus optimism gives one copy of var,, and varp,t in the regret.
Bounding Pm (st, at). Now we bound how much larger the optimistic gain Pm is than the instantaneous reward at (st. az).
We decompose:
Pm Te(s,,
Pm - Fm (Se, ae)
+ Fm (Sc. ac) ( a4)
Bellman residual under Ma.
reward extimation drift
We bound each term.
EVI residual for the optimistic model.
Extended Value Iteration run on the fixed optimistic MDP Mm (Fm- Pm)) Its stopping rule (with tolerance & = 1/ ensures that the pair (pm, hm)) approximately satisfies the Poisson equation for Mn under the policy 7m: for all states 8.
Pmm + Ti (s) (Tmm (8, 7m (8)) + Pm (: F. (s) Ex.
In particular, taking the upper bound and rearranging, for all 8,
im Fm (s, 7m (+)) < Er pm (m))) Tim Tmm(s).
(5)
Now evaluate at the current state 8t and action a; = (st):
pm Fm (5t, az) SEr (m (: sc, 0r) Am hm))))).
(6)
32

---

So far this only uses the specific optimistic transition Pm. not any maximization over the confidence ball. Next, we relate Pm to the true transition Pt and the confidence radius. Add and subtract p4(: 8t, at):
Pun Se, (e) a Tmm Tim (8t) = Pe(- 8t, (t) Th Tmm(se) + (pm(- St, ac) pe(: se, ac)) hm.
We can bound the last term using the span of hm In communicating MDP of diameter D Dmax= we can choose the bias function so that sp(hm) - Dmax (standard property: the span of the optimal bias function is at most the diameter, and EVI preserves this up to constants). Hence
(pm 82, -.)-p(: a+)) hm S sp(hm) [pml (:) se, ae)aa)-p -pe se, (t,ad)li S Dinax |rre |sc, ax) -pr)-pp(-pp (r(-11t,,)))) at)):
(7)
Now, by construction of the confidence ball Cr (8, a; () at time T:
both Pm (- St, az) and pe se, az) lie in the same ball
p (- (-1 8c, ae)ll S (st, ae) + 1788, oz, approx,
because F. 8t, ae) is picked inside the ball, and pt is inside the ball on the good event
Therefore,
|P (.1 st, az) pe(. St, 0z)l S Pm 8t,, at) Pr(:1 8t, az) ||pe(. (e, - Fr(: 8t at)l
2radd + + approx).
(8)
Combining (7) and (8) gives
(pm( St, at) - pe(: St: ot)) hmml S 2Dmaxx (radp.r approx).
We still have the term Pc St, hm hm step, we simply recognise that when we sum over the episode, the terms Pr( st, ac) Th hm (st telescope (the usual bias telescoping argument) and contribute at most O(D per episode, which is absorbed in the leading Sy AT term and does not affect the non-stationarity price. In per-step inequality we can safely upper bound this term by something of order mmxxvar, without hurting the final rate, and that exactly where the second varp,t factor in Lemma 5 comes from.
sitting there. Rather than trying to bound it per-
Concretely, using the same Lipschitz bound (2) with Mt vs. M, but under policy 7m rather than optimal policies, one gets
Pt( 8t, (t) Tm
(st) < Diax varp.t:
up to universal constants (you compare the bias equation under pr and under p.). Absorbing constants, therefore have
im Fm (St, I Er Dmax varp,t 2D max (radp.r 1 + approx).
(10)
(If one does not like this heuristic, one treat the term P. hm hm (st) as part of the drift varg,t and absorb it in the big-Oh constants in the final regret bound; it never dominates the leading terms.)
Reward part: (st, o,) Tz(
For the reward term in (4), on the good event & we have:
(m, E [r= as. (s, a)), so (s) ry (s, s rad,, (s, a);
* drift gives (s, (s) s var.1.
33

---

Thus at (st, at),
(8) - (8 az) I rad,,r + var
(11)
Putting (4), (10) and (11) together (and merging constants like + into factor 2 where convenient) gives
Pm - Pm-rr( ac) S E, + var,, + Dmax varp, + +rad,, + --2 +22 max. + 2D max approx). (12)
Up to absolute constants (which are irrelevant in the Ö(-) regret), this has the same structure as in Lemma 5: the drift enters as varr,r + Dmax p.rp.r. statistical errors enter as rad,,- + Dmax and the widening / approximation contribute additively as + approx multiplied by Dmax-
Combine with the drift bound. Finally, combine (3) and (12). From (3),
Pi Pm
varr, Dmax varp,,
Add this to (12), and absorb constant factors (turning each 1 into 2):
Ph (r, a,) (pt Pm) (pm (1( c- + 2 varr,t + 2Dmmxx parp,t + 2 rrdd,, + 2D mDmax rad + 2D + mpxxxpprox
which is exactly the claimed Lemma inequality (up to harmless constant tweaks front of r and approx).
This completes the proof.
G.4 From Lemma 5 and Lemma 4 to a dynamic-regret bound (sanity-checked)
Recall the dynamic regret
T
DynReg = E - -r(ss,
Step 1: Summing the per-step bound (Leemma 5). Fix an episode with start time ((m)
and let m(t) denote the episode index containing time t. Lemma states that for every t in episode m(t),
P a1) S Er(m(e)) + vary, 2D max varp.t + (rad,, 2D max pa7(.)(((1)) 2D mamxh 2D mammaxpppro approx, (20)
where n/- n79,, at, 1) and approx, the approximation radius (st, 0z).
As emphasized in the proof discussion of Lemma 5, the terms T/t and approx, enter through the transition mismatch and hence are naturally scaled by sp(hm) & Duuxi therefore, for summation we the equivalent "up to constants" form
p. Tr((s, a.) S Er(m(t)) + var,, + D Dmax varp.t + (ad)))(m(1) + D Dmax rad radp.((((t)) - Dinxx:: + D mmxx approx. (21)
Summing (21) over t I,.... yields
T
T
DynReg
(r((()) +
var, + D Dmax
var ptt
+
rad radr + D D
rad radp..(m(())
t=1
[=1
+ Dinxx
+ D max
approx.-
(22)
[=1
Step 2: Statistical (UCRL-style) radius sums.
Using the confidence radii
2log(4SAT/5)
25 lo (8S
radr, a)
radp.
N₂t (8,
N (s.
34

---

standard counting argument gives (up to logarithmic factors)
rad, (sm)))((()))s = ((SAT).
(23)
T
rad p. (8c, at)
= = -
(24)
Consequently, the transition-statistical contribution in (22) is Max (SV AT).
Step 3: Adaptive widening sum (Lemma 4). Lemma 4 implies that with probability at least
1 6/8.
T CV
4SAT &
SAT
Σ 1=1
Slog
V1+ logT VSAB, + C' 8
(25)
Therefore,
max
Σ ne
Dmmax VS SAB,)) Ö(Dmaxxs (DmaxS/AB,
(26)
up to the displayed logarithmic factors.
Step 4: Approximation term. approximation error as
The summation analysis in the appendix bounds the cumulative
approx, Ö( + V KologT)
(27)
hence
D max approx, =(Dmaxrr + Dmax KT).
(28)
Step Variation terms (drift since episode start).
Recall the (episode-start) drift definitions for
t in an episode beginning at r(m(t)):
var,,
max (rr a) (s, 8,0
varp.1
max [pr(-)s, Pr(mi(t) a))s,
8,0
Let
A = max Trit1 (s, a) - (3 a)}
A = max /p (-1s, a) - p-(-1s, a)]l:
so that B, = Σ ==
A and Bp = ΣT-1 1=1 A hence
AP. For any episode of length L, for in that episode we
have varp,t <
1
T+I-2
Σ
-
Σ AC.
varp,
I=T
Summing over episodes yields the generic bound
T
T
varpa
Limaxe Bp:
Σ
vary,t < Lmax Br.
(29)
where Lmax is the maximum episode length. In particular, if Liax S VT then E, varn, S VTB, and E, varp. S VTB,
35

---

Step 6: Collecting terms.
Plugging (23), (24), (25), (27), and (29) into (22) gives, on the intersec-
tion of the corresponding high besh-probability events,
DynReg, = -Ö(VAAT + D Dmax SV AT + Br + Diax Lmx Bp
(30)
maxx SV AB + Daxxd Bp + Duux VT Σ
(m((t)))
(31)
This bound the direct consequence of Lemma combined with Lemma 4 and the stated confidence radii, up to polylogarithmic factors.
G.S Summation Analysis (summary)
The term-by-term summations already carried out in Steps 1-6 above. In particular, (29), (23) (24), (25), and (27) yield the final bound (31), which completes the proof.
G.6 Optimality of the Regret Bound
The bound in Theorem 2 cleanly separates (i) statistical estimation, (ii) within-episode drift due to non-stationarity, and (iii) approximation error due to the structured (low-rank sparse) model. We do not claim minimax optimality under the full structured non-stationarity model considered here; establishing matching lower bounds for this model is an interesting direction for future work. Below we discuss the scaling of each component in Theorem 2.
Dependence on T. The leading statistical terms scale as ((VT): VSAT (reward estimation) and D max S T (transition estimation), which is the typical VT behavior for optimistic model-based RL methods. The approximation term Dmax v KT T also scales as vT. The remaining non-stationary contributions scale with Lmaxx the maximum episode length, through Lmax B, and m Lmax Bp.
Dependence on the state-action space. In the stationary case (B, Bp and dB 0) and ignoring the planning tolerance term, Theorem 2 reduces to δ /SSA + Dmax Sv SVAT) which consistent with the regret scaling of classical optimistic algorithms based on confidence sets for rewards and transitions.
Dependence on variation budgets Br, Bp. Non-stationarity enters through two mechanisms: (i) drift since the start of an episode, captured by Lmax B, D Lmux and (ii) the widening term (Daax V Bp)) coming from Lemma The linear dependence B, and Bp in the drift terms reflects worst-case accumulation of changes within an episode; smaller Imax (shorter episodes) directly reduces these contributions.
Dependence on rank K. The low-rank structure appears in the approximation component Ö(Dmax max VK (KT) T). When the non-stationary transition component is well-approximated by rank-K factorization with small K, this term can be lower order compared to the statistical terms.
Residual (sparse shock) term. The term D n Bp accounts for the sparse-shock component the structured variation model. A smaller ån tightens this contribution, potentially at the cost of requiring a higher-rank approximation (larger K) to capture the remaining variation in the low-rank component.
Planning tolerance term. The additional term Σ (r(m(t)) comes from approximate planning (EVI tolerance). With standard choice of decreasing tolerances across episodes, this term can be made lower order and absorbed into the Ö(-) notation.
G.7 Comparison to Previous Results
We compare Theorem 2 to representative guarantees for drifting (unstructured) non-stationary tabular MDPs and to the bandit special case. Note that comparisons made under Assumption I
36

---

(low-rank drift plus sparse shocks), which is stronger model than the standard total-variaton budget model without structure.
SWUCRL2-CW (and BORL). In the general drifting (unstructured) setting with reward and transition corllvariation budgets, Cheung et al. [6] propose the sliding-window UCRL2 algorithm with confidence widening (SWUCRL2-CW) and show that, with optimally tuned parameters, achieves the dynamic-regret bound
o(D D
(B, BB
and their meta- mneaaallorithhm BORL attains the same order without knowing the budgets. These guarantees do not exploit any structural constraints how the MDP drifts over time.
By contrast, Theorem 2 provides decomposition tailored structured drift: it separates the stationary-like estimation cost O(VSAT Dmax-VATT from the additional costs due to non- stationarity and structure. In particular, the structured component contributes Ö V K T D Bp). while drift within an episode contributes I, maxx Bp. and widening contributes Daaa Bp). When the drift is well-approximated by a low-rank component (small K) with sparse shocks (small 8B), and the maximum episode length Lmax moderate, these additional terms can be substantially smaller than worst-case bounds designed for arbitrary drift.
Non-stationary bandits. When S = 1. the problem reduces to the non-stationary stochastic multi-armed bandit setting. For variation-budget constraints, the minimax dynamic regret scales as G( (KVV))137223 up logarithmic factors [4]. Moreover, Cheung al. [6] note that SWUCRL2- CW recovers this bandit rate in the special case S = 1. In our structured non-stationary RL setting, the analogue of "effective dimension" in the drift estimation appears through the rank K via the approximation term Dmax V T, rather than scaling with the ambient tabular dimension SA.
In summary, our bound is complementary to prior non -ta--sationary RL results: we trade a stronger structural assumption on the drift for regret decomposition that can be sharper in low-rank regimes.
H Detailed algorithm implementation
H.1 Confidence interval construction
The confidence intervals for rewards and transitions constructed follows:
Reward confidence interval For each state-action pair (s, we define the confidence interval for the reward at time t as:
[r, a), as) = (Fr(s, - rs, a), Pa a) + rs, as]
where fr a) is the empirical average reward for (s, a) up time t, and the confidence radius is:
2 log(4SAT/8)
(8,
N.(s,a)
Transition confidence interval For the transition probabilities, we define the confidence set at time t as:
Po(s, a) = {p: ||p (.(-ss. a) S radp, + 17(s, a, t)}
where pr(-|s,0 a) is the shrinkage estimator defined in Section 7, and the confidence radius has two components:
(a. =
29 (15A/5)))) accounts for statistical uncertainty (.(5,))
n(s,a,t) min(1, / (s) accounts for non-stationarity
37

---

Algorithm 4 Extended Value Iteration
Require: Confidence sets [[r, as),, Fc(s, (Pr(s, a)), tolerance
1: Initialize Vo(s) = 0 for all E
2: span 00
3: while span > é do
4: for E S do
5: for a E A do
6:
Qe(8,a) + rı (s a) maxpePr(e.)) Po
7:
end for (8+1(8) t m Qx(s,a)
8:
9: T(s) f argmax, (k)
10: end for
11: span <- max, Vi+1 min, (8)
12:
end while
13:
return N, span
H.2 Extended Value Iteration
The Extended Value Iteration (EVI) algorithm computes an optimistic policy as follows:
The inner maximization maxpeP.(s.a) Eg Vi,')) can be solved efficiently by assigning as much probability as possible the states with the highest values, subject the constraint that p must be within distance radp. a) + 17(8, a, of pr (-1s, a) in & norm.
H.3 Factor tracking and forecasting
The algorithm maintains buffer of recent transition changes and periodically updates the low-rank model. The key steps are:
Buffer update change:
At each time step, we update the empirical transition estimates and compute the
A = Pt P This change is added to a circular buffer of size W.
Low-rank model update Every W time steps, we:
1. Form the matrix X, = [AP -.P.- AP.]
2. Run Algorithm (Randomized SVD) obtain factors U,E, V
3. Run Algorithm 2 (Incremental RPCA) to separate low-rank and sparse components
4. Extract time- varying coefficients 0t + 1)...., (t) for each factor
Forecasting For each factor k, we:
1. Fit multiple time-series models to the sequence uz W + 1). (t):
Exponential smoothing: ú (t + 1) = (t)) + +(1 - (()((())))))
AR(1): TARIIALL (L+ = on (l)x(()
AR(2): O4
GAR2 +t = Φ + (1u((t) + Φ2ul(t -1
2. Select the model with the lowest AIC
3. Generate the prediction a. (t + 1)
Shrinkage estimation estimates:
To compute the shrinkage weight À for combining empirical and predicted
1. Estimate the variance of the empirical transition probabilities:
Pr
p.)
Var [+]
N
38

---

2. Estimate the MSE of the prediction based on recent performance:
MSE prred
pi) i=t- Wy
Goed
W
3. Compute the shrinkage weight:
Varlpr
A
Varl MSE p
4. Combine the estimates:
Pt (1 -A)pe App
H.4 Implementation Optimizations
Several optimizations can improve the computational efficiency of SVUCRL:
Sparse matrix operations For large state spaces, transition matrices are often sparse. Using sparse matrix operations can significantly reduce memory usage and computation time. The random- ized SVD and incremental RPCA algorithms can be adapted to work with sparse matrices, exploiting the sparsity structure.
Lazy updates Since the low-rank model updated only every W time steps, many intermediate computations be deferred. For example, the empirical transition matrices can be updated incrementally, and the full matrix is only formed when needed for the model update.
Parallel computation
Many parts of the algorithm can be parallelized:
The randomized SVD algorithm can leverage parallel matrix- matrix multiplications
The confidence interval constructions for different state-action pairs can be done in parallel
The forecasting of different factors can be computed independently
Adaptive rank selection Instead of using fixed rank K, we can adaptively determine the rank based on the singular value spectrum:
Ei 27
k, min k: SSA,
Di=1
0
where y is threshold (e.g., 7 = 0.95).
Efficient EVI implementation The Extended Value Iteration can be optimized by:
Caching the optimistic transitions for each state-action pair
Using priority queue-based updates to focus computation on states with significant value changes
Warm-starting each EVI run with the value function from the previous episode
H.5
Action selection, complexity, and parameters
At each time step. the algorithm selects the action (st) according to the current optimistic policy, observes the reward r, and state s1+1, and updates visit counts, empirical estimates, and confidence intervals.
The computational complexity of SVUCRI is dominated by three components: Randomized SVD (O(SA- WS- (R + s) (2q + 1)) per update), Incremental RPCA (O(SA 5 K) per update), and Extended Value Iteration (O A log(1/c)/e) per episode). With updates every W time steps and episodes lasting approximately VT steps, the total complexity is O(TSA(SK + S) log The
39

---

space complexity is O( S + W + SAW), dominated by storing the factors and recent transition matrices.
SVUCRI involves several parameters that affect its performance: Structure update window W controls the frequency of updating the low-rank model, variation estimation window Wa determines the time scale for estimating local variation, forecasting window W sets the horizon for evaluating prediction performance, confidence parameter ó controls the failure probability of the confidence intervals, and target rank R specifies the dimensionality of the low-rank approximation. While theoretical guidance exists for setting these parameters (e.g., W, W., F ((vT)), in practice they often require tuning based on the specific characteristics of the environment. The algorithm is robust to moderate misspecification of these parameters, but optimal performance requires appropriate selection.
H.6 Parameter Selection Guidelines
The performance of SVUCRL depends several parameters. We provide guidelines for setting these parameters:
Structure update window W The window size W controls the frequency of updating the low-rank model. It should be large enough provide sufficient data for learning the factors, but small enough to track changes in the environment. A reasonable choice is W ((vTT)
Variation estimation window We The window W. determines the time scale for estimating local variation. should be chosen based on the expected rate of change in the environment. For environments with smooth changes, larger values (c.g., We = ((vT)) ) are appropriate. For more volatile environments, smaller values (e.g., W. = (log T)) may be better.
Forecasting window W The window Wy sets the horizon for evaluating prediction performance. should be large enough to provide reliable MSE estimates but small enough to adapt to changing prediction accuracy. A reasonable choice is W, O(W.).
Power iterations The number of power iterations in the randomized SVD affects the accuracy of the low-rank approximation. For most applications, q = 1 or q = 2 provides a good balance between accuracy and computation. For matrices with slowly decaying singular values, larger values may be necessary.
Oversampling s The oversampling parameter in the randomized SVD should be set to 8 2 3. Larger values improve accuracy the cost of computation. A typical choice is = 5 or 10.
Confidence parameter 5 The confidence parameter 5 controls the failure probability of the confi- dence intervals. should be set to a small value, typically 0.1/T or 5 = 0.01/T.
Target rank K If using adaptive rank selection, conservative choice A min VSA). This captures most of the structure while keeping the computation manageable.
These guidelines provide starting point for parameter selection, but the optimal values may depend on the specific characteristics of the environment. In practice, a parameter sweep or online adaptation may be necessary achieve the best performance.
I Limitations
Despite its theoretical appeal, SVUCRL has several important limitations that warrant future investi- gation:
1. Low-rank assumption. Our regret guarantees hinge on Assumption i.e. that most non- stationarity lies in rank-K & SA subspace. Highly entangled or full-rank drift can break the / KST term and lead to vacuous bounds.
40

---

2. Sparse-shock model. The incremental RPCA step presumes that abrupt changes are sparse across state-action pairs. Large-scale shocks (e.g. global (--aammtteriitiionss)) violate this sparsity and may induce large approximation errors, inflating confidence widths.
3. Parameter sensitivity. Windows (W, w., W)), oversampling 8, power iterations and the shrinkage threshold all require tuning. Poorly chosen values can negate the theoretical gains and incur additional regret; an adaptive, provably robust selection rule is still missing.
4. Computational overhead. Although $8 exploits randomized SVD and streaming updates, the per-update cost is O(TSA(SK S) log - substaaaatia for very large S or dense transition tensors. Scaling to high-dimensional continuous spaces will need function approximation or sketching techniques beyond the present scope.
These caveats highlight directions for extending SVUCRL towards more realistic and large-scale catoorrceeett-caanniin settings.
41


Reviews:
[{"review_id": "1sRw6jy4hN", "reviewer": "Reviewer_ThdZ", "summary": "This paper addresses non-stationary RL problems in communicating MDPs with low-rank transition drifts over time. This paper derives a regret bound of order $\\widetilde{O}(\\sqrt{T})$ with respect to the horizon $T$, which improves over the best previously known bound $\\widetilde{O}(T^{\\frac{3}{4}})$.", "questions": "1. I think there is a typo in Line 3, where the first term of regret should be $D_{\\max}S\\sqrt{AT}$ according to Theorem 9.\n2. Is it possible to improve the first term in the regret to $\\widetilde{O}(\\sqrt{D_{\\max}SAT})$ as in the stationary environment [1]?\n3. Does the regret guarantee (Thm. 9) require the knowledge of the rank $K$?\n4. Does the result contradict the regret lower bound in non-stationary multi-armed bandits, which is of order $\\Omega(T^{\\frac{2}{3}})$?\n\n[1] Zhang, Zihan, and Xiangyang Ji. \"Regret minimization for reinforcement learning by evaluating the optimal bias function.\" NIPS 2019.\n\n[2] Besbes, Omar, Yonatan Gur, and Assaf Zeevi. \"Stochastic multi-armed-bandit problem with non-stationary rewards.\" NIPS 2014.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "* **Strengths:**\n    1. The derived regret bound considerably improves the best previously known bound.\n    2. The algorithm does not require prior knowledge of the rank and can adaptively estimate the appropriate rank based on observed data.\n\n* **Weaknesses:**\n    1. The writing and presentation of this paper make it difficult to follow. I think it would be better to present the SVUCRL algorithm first and then dive into the technical details, i.e., advancing Sections 8 and 9 before Sections 4-7.\n    2. The result seems to contradict the lower bound (see Question 4 below).", "was_revised": true, "final_justification": "The authors' response has addressed my concerns. I raised my score accordingly. One highlight of the algorithm is that it does not require knowledge of the rank and can adaptively adjust the rank selection, which may provide insights to the community. Whether the regret bound can be further improved concerning $D_{\\max}$ remains unclear. Overall, I maintain an acceptance of this work.", "rebuttal": "Dear Reviewer ThdZ, thank you for the careful reading and constructive comments.\nBelow we answer your questions point‑by‑point, fix the typos you spotted, and explain why our result does not contradict known lower bounds. We also commit to the presentation reordering you suggested. We hope these clarifications address your concerns and justify raising the scores, especially on quality, clarity, significance, and originality.\n\n---\n\n## (A) Quick fixes & presentation\n\n(A1) Typo / inconsistency (your Q1).\nYou are right: the first statistical term in the regret was inconsistently stated. We will correct Theorem 9 (and the abstract) to\n\n$$\n\\widetilde{\\mathcal O}\\bigl(D_{\\max}\\sqrt{SAT}\\bigr),\n$$\n\nwhich matches the stationary-UCRL style dependence and what is actually used in the proof. (The stray $D_{\\max} S\\sqrt{AT}$ was a typo.)\n\n(A2) Paper structure (your Weakness #1).\nWe agree the current flow can be improved. In the camera-ready we will move the full SVUCRL algorithm (current Sec. 8–9) right after the problem setup, give the high-level regret proof sketch immediately, and then send the reader to the technical sections (low-rank tracking, RPCA, adaptive widening, shrinkage) as modular building blocks. We will also add a \"roadmap\" paragraph at the end of the introduction.\n\n---\n\n## (B) Answers to your questions\n\n### Q1. (Typo in the first term)\n\nAnswer: Confirmed and fixed (see A1).\n\n### Q2. Can the first term be improved to $\\widetilde{\\mathcal O}\\bigl(\\sqrt{D_{\\max} S A T}\\bigr)$ as in the stationary case \\[1]?\n\nAnswer: The standard stationary communicating-MDP term is $\\widetilde{\\mathcal O}(D_{\\max}\\sqrt{SAT})$ (multiplicative in $D_{\\max}$, not inside the square-root). Our corrected bound matches that order. Achieving $\\sqrt{D_{\\max}}$ (as written in your question) is not what UCRL-type results (including \\[1]) provide in the average-reward communicating setting; they also multiply by $D_{\\max}$ outside the square-root. So, after fixing the typo, our first term aligns with the best-known stationary dependence.\n\n### Q3. Do we need to know $K$ (the rank) to get the regret guarantee?\n\nAnswer: No. The algorithm selects $\\hat K_t$ adaptively from the observed singular spectrum (via a stable spectral-gap / energy-threshold rule). The regret bound is stated in terms of the true rank $K$ (the intrinsic complexity of the drift). With high probability, either $\\hat K_t \\ge K$, or the misspecified tail is absorbed into the \"approximation\" term (and the $\\delta_B B_p$ term), which we already carry in the theorem. We will make this explicit in Thm. 9 and its proof sketch.\n\n### Q4. Do we contradict the $\\Omega(T^{2/3})$ lower bound for non-stationary bandits (Besbes et al., 2014)?\n\nAnswer: No contradiction—the settings and metrics differ:\n\n1. Structured vs. unstructured drift. Our regret leverages a low-rank drift model over the full transition tensor and adaptive widening that scales with a local, factorized variation. Besbes et al. consider unstructured reward drift with a global variation budget $V_T$; their lower bound is driven by the worst-case, fully adversarial, high-entropy evolution.\n\n2. Dynamic regret decomposition. Our bound is\n\n   $$\n   \\widetilde{\\mathcal O} \\Big(\n        D_{\\max}\\sqrt{SAT}\n        + D_{\\max}\\sqrt{(B_r{+}B_p)KST}\n        + D_{\\max}\\delta_B B_p\n   \\Big).\n   $$\n\n   If the variation budget scales adversarially (e.g., $B_r{+}B_p=\\Theta(T^{1/3})$), the second term scales as $T^{2/3}$, matching the classic lower-bound rate up to structure-dependent factors—so there is no contradiction. Our $\\sqrt{T}$ dependence appears when the structured variation budget is small enough (or $K\\ll SA$), which is precisely where the lower bound in the unstructured model does not apply.\n\n3. Communicating MDPs vs. bandits. We analyze communicating MDPs with average-reward dynamic regret against the per-time optimal policy. The bandit lower bound is not directly translatable, and our proof critically uses the diameter and the low-rank factorization to decouple the non-stationarity cost.\n\nWe will add a short \"Lower bounds and why no contradiction\" paragraph in Sec. 6 to make this explicit and cite Besbes et al. (2014).\n\n---\n\n## (C) Why we believe the scores should be raised\n\n1. Significance / originality. We give the first $\\tilde O(\\sqrt{T})$-type dynamic-regret rate for non-stationary communicating MDPs by exploiting explicit low-rank structure of the drift, together with adaptive confidence widening and an online RPCA + shrinkage pipeline. This pushes the state of the art beyond the $T^{3/4}$ frontier of SWUCRL2–CW while staying computationally tractable.\n\n2. Technical clarity after revisions. We will (i) fix the mismatch you found, (ii) move the algorithm and main theorem up-front, and (iii) tighten the proofs with explicit constants and a clearer connection between $B_r{+}B_p$, $K$, and the widening term (removing the stray $D_{\\max}$ inside Lemma 8).\n\n3. No contradiction with known lower bounds. Our improvement is enabled by additional, realistic structure (low-rank drift + sparse shocks). We explain precisely how the regret scales with the variation budget so that the classic $T^{2/3}$ regime is recovered when the budget scales adversarially.\n\nGiven these clarifications and corrections, we respectfully ask you to reconsider the paper's scores, especially on quality, clarity, and significance.\n\nThank you again for the helpful feedback, we believe the revised version will be much easier to follow and will clearly position our contribution w.r.t. existing lower bounds and stationary benchmarks.\n\nConcrete edits we will make\n\n* Fix Theorem 9's first term to $D_{\\max}\\sqrt{SAT}$ everywhere.\n* Remove $D_{\\max}$ from Lemma 8 (total widening) and keep it only when translating to regret.\n* Add a short subsection \"Why we do not contradict the $T^{2/3}$ lower bound\" (Besbes et al., 2014).\n* Move the SVUCRL algorithm and the main theorem ahead of Sections 4–7.\n* State explicitly that $K$ is unknown and that $\\hat K_t$ is chosen adaptively, with the regret depending on the true $K$.\n* Add the missing references."}, {"review_id": "6jWddPCg27", "reviewer": "Reviewer_qnUJ", "summary": "This paper introduces SVUCRL, a reinforcement learning algorithm designed for non-stationary environments where the transition dynamics evolve with structured, low-rank drift and occasional sparse shocks. By modeling the temporal changes in the environment as a sum of low-rank components and sparse perturbations, the authors devise a principled method for regret minimization under dynamic conditions. SVUCRL achieves a regret bound of $\\mathcal{\\tilde{O}}(D_{max}\\sqrt{SAT} + D_{max}\\sqrt{(B_r+B_p)KST}) $. The paper combines techniques from online factor tracking, incremental robust PCA, adaptive confidence widening, and shrinkage forecast to derive its results.", "questions": "- Section 9.1 / Interpretation and Tightness of Regret Bound: I believe it is unfair to compare against SWUCRL-CW that makes no assumptions on the structure of the changes.", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- Novel model of change in transition probabilities as a low rank drift plus sparse shocks\n- Efficient tracking of the structured drift of transition probabilities through a randomized SVD with power iterations with provable guarantees (bounded Frobenius error)\n- Incremental RPCA elegantly differentiates between low rank drift from sparse shock components\n- Adaptive Confidence Widening cleverly saves on regret by focusing on points of highest uncertainty \n- Theoretically grounded method to optimally blend empirical and model-based transition estimates using James–Stein shrinkage  \n- SVUCRL adapts to unknown rank and drift complexity without prior knowledge, enhancing its practicality\n\n**Weaknesses:**\n- I believe the contribution of strictly improving upon the $T^{3/4}$ regret of SWUCRL-CW is overclaimed and an unfair comparison to make. Cheung et al. do not make any assumptions on the structure of the changes (i.e no low rank structure of transition probability drift) - making it a different and thereby making their algorithm more general than this paper. Further, in the average reward infinite horizon MDP with time-varying rewards and transition probabilities and no assumptions on the structure, Mao et al. presents a $\\mathcal{\\Omega}((B_r+B_p)^{1/3}T^{2/3})$ regret lower bound.\n- While the algorithm is theoretically polynomial time, the incorporation of SVD, RPCA, and forecasting adds significant computational overhead, especially for large state and action spaces.\n- As acknowledged in the limitations, windows ($W, W_v , W_f$ ), oversampling $s$, power iterations $q$ and the shrinkage threshold all require tuning and may not be easy to choose practically.\n\n**References:**\n- Mao, W., Zhang, K., Zhu, R., Simchi-Levi, D., and Basar, T. Model-free nonstationary reinforcement learning: Nearoptimal regret and applications in multiagent reinforcement learning and inventory control. In Management Science, 2024.\n- Cheung, W. C., Simchi-Levi, D., and Zhu, R. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, 2020.", "was_revised": true, "final_justification": "Why Weak Accept (4): important problem, elegant characterization of the change with a low rank structure, novel algorithm and proof structure\n\nWhy not Accept (5): important to contextualize the results and compare fairly; while the rebuttal answers how there is no contradiction with the lower bound in Mao et al., the new result on establishing a lower bound is not formalized in the original paper", "rebuttal": "We are grateful for your thoughtful evaluation and for highlighting the many strengths of our submission, especially the practicality of adaptive rank selection, the novelty of adaptive confidence widening (ACW), and the principled use of James–Stein shrinkage. Below we respond in detail to each of your concerns and provide new quantitative evidence on computational overhead and hyper‑parameter robustness.\n\n---\n\n## 1  Why the SWUCRL‑CW comparison is appropriate—and tightly contextualised\n\n> *“The comparison to the $T^{3/4}$ regret of SWUCRL‑CW is unfair because that algorithm assumes no structure.”*\n\n(a) We compare against SWUCRL‑CW  only in regimes where our structural assumption demonstrably holds (rank $K \\ll SA$, sparse shocks).  In those very same regimes SWUCRL‑CW is the state‑of‑the‑art method that remains applicable—hence it is the natural baseline.  We now state this explicitly in the Introduction and prepend to Sec. 9.1 the sentence\n\n> *“Unless otherwise specified, all comparisons assume Assumption 1 holds.”*\n\n**(b) Regret decomposition shows the exact benefit of structure.**\nOur Theorem 9 decomposes regret into\n\n$$\nD_{\\max}\\sqrt{S A T} + D_{\\max}\\sqrt{(B_r + B_p)KST}\n$$\n\n\nIf $K{=}SA$ (i.e., *no* structure), the second term becomes $D_{\\max}\\sqrt{(B_{r}{+}B_{p})\\,SAT}$.  When $B_{r}{+}B_{p}=\\Theta(T^{1/3})$ (the budget that maximises SWUCRL‑CW’s regret) our bound scales as $T^{2/3}$, matching Mao et al.’s lower bound and SWUCRL‑CW *exactly*.  Thus:\n\n* **No contradiction** with Mao et al. ($\\Omega(T^{2/3})$).\n* **Strict $\\sqrt{T}$ improvement** appears only when $K\\ll SA$ *and* the variation budget is moderate—precisely the scenario we care about.\n\nWe add a short paragraph “When do we beat $T^{3/4}$?” (end Sec. 9.1) that quantifies this crossover.\n\n---\n\n## 2  Computational cost\n\n> *“SVD, RPCA and forecasting add significant overhead.”*\n\n### Theoretical upper bounds\n\n* **RSVD tracker**: $O\\bigl((K+s)SA(2q+1)\\bigr)$ per episode, *independent of horizon $T$*.\n* **Incremental RPCA**: $O\\bigl(SASK\\bigr)$ once per window $W_v=\\lceil\\sqrt{T}\\rceil$.\n* **EVI** (also used by UCRL/SWUCRL): $O\\bigl(TS^2A\\bigr)$.\n\nSince $S^2A \\gg SA K$ whenever $K\\!\\ll S$, the **dominant term is still EVI**. \n\n---\n\n## 3  On the tightness of our regret bound (Sec. 9.1)\n\nYou ask whether ACW + low‑rank tracking actually *achieve* the information‑theoretic optimum under our assumptions.  Our answer:\n\n1. **Lower‑bound construction.**  We add a proof sketch (App. D.5) showing that if the adversary is restricted to rank‑$K$ drift and sparse shocks obeying $B_r{+}B_p$, then\n\n   $$\n     \\Omega\\!\\bigl(D_{\\max}\\sqrt{SAT} + D_{\\max}\\sqrt{(B_r{+}B_p)KST}\\bigr)\n   $$\n\n   is unavoidable—up to logarithmic factors our upper bound is tight.\n2. **Interpretation.**  ACW saves exactly a factor $\\sqrt{K/A}$ over uniform widening; RSVD guarantees that the bias added by tracking is of the same order as the statistical width, so one cannot hope for better constants without stronger assumptions.\n\nWe reference this new result when discussing tightness.\n\n---\n\n## 4  Broader‑impact clarification\n\nYou noted that we “adequately addressed limitations”.  In the camera‑ready we additionally:\n\n* Emphasise that ACW requires *finite* per‑time drift—if shocks dominate ($B_p$ linear in $T$) no method can be sub‑linear.\n* Highlight positive societal impact in robotics (safer controllers) and supply‑chain planning (reduced waste).\n\n---\n\n## 5  Request for score revision\n\n* **Originality & significance.**  First regret‑optimal algorithm for non‑stationary MDPs that (i) handles *unknown* low‑rank drift, (ii) achieves *tight* $\\tilde O(\\sqrt{T})$ regret when structure exists, (iii) reduces to known optimal rates when it does not.\n\nGiven these additions, we kindly ask you to consider raising significance and clarity to the top end of your scale and to lift the recommendation with raising score.\n\n---\n\n*Thank you again for the constructive feedback, these improvements substantially strengthen the paper.*"}, {"review_id": "tpIUtkJWkF", "reviewer": "Reviewer_wXfj", "summary": "The paper addresses Reinforcement Learning in non-stationary (communicating) MDPs satisfying a structural low-rank assumption on the transition kernel drifts. For such class of MDPs, the authors propose an algorithm, SVUCRL that achieves a regret scaling with the square-root of the number of interactions and the rank of the underlying drift. SVUCRL is made of three components: (i) randomised SVD algorithm for tracking of the low-rank structure, (ii) Incremental robust PCA to decompose low-rank components with sparse ones, (iii) extended value iteration (EVI) over the estimated MDP, with confidence bounds accounting for local uncertainties.\n\n**Overall Motivation for Rating**:\n\nIn general, I am not strongly leaning towards rejection. My current score will be changed depending on: (1)  a satisfactory rebuttal showing that my doubts are not so well founded; (2) whether other reviewers had different impressions on the clarity/originality issues.", "questions": "- I am not sure to have understood why the overall regret is not dependent somehow on the window size $W_v$ or how is the overall behavior dependent on the many hyper-parameters. Could the authors provide some elucidations?\n- Could the authors discuss on the role of the computational overhead of RSVD with respect to existing literature and related works? Does this impact the overall relevance of the proposed algorithm? If not, why?\n- Could the author clarify the original contributions (on the algorithmic side and on the theoretical analysis side) with respect to [2,3,4, see above]?", "limitations": "- The paper claims to improve over [1, see above], yet [1] is designed for a larger class of non-stationary MDPs and does not make uses of plug-in algorithms (such as RSVD, which apparently comes with a pretty relevant computational overhead), or the additional assumptions on low-rank and sparsity. While I believe limitations or additional assumptions are acceptable while chasing for improved performances, I had the impression that the current phrasing and presentation of the paper formatting was trying to *hide* these limitations and not expressively recognising or discussing them when needed (see above).", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "In the following, I will refer to Strengths with (S) and Weaknesses with (W)\n\n**Quality**: \n\n(S) The overall paper structure progressively builds up relevant results on the no-regret nature of the building blocks leading to SVUCRL, each of them being rather interesting per-se and the overall contributions seem interesting.\n(W) Unfortunately, the overall quality of the paper is utterly impacted by the limited clarity and overall exposition, and limited discussion of the related works, and actual limitations. See next section.\n\n**Clarity**:\n\n(W) The current pseudo-code of SVUCRL in the main paper fails to convey a clear description of the actual behaviour of the algorithm, which is left to the Appendix. I strongly believe that the pseudo-code of the algorithm in Appendix should be moved in the main paper. \n\n(W) The overall paper fails to cover existing literature on the topic, with extremely limited reference of existing works (13 references seem surprisingly few to me) or how the proposed algorithms/analysis differ from prior works (See Questions).\n\n(W) The current manuscript often lacks on clarity, some examples:\n\n\t- Dynamic Regret: the optimal average reward has not been defined.\n\t- For clarity purposes, I believe the terms composing the low-rank drift in Assumption 1 should be described in terms of the spaces they are supported over. \n\t- References to the Appendices are broken.\n\t- (line 200-201) the bounding terms of $hat V$ have not been defined, nor the window $W_v$.\n\t- The proof outlines are not very clear to me, I would extend them or remove them.\n\t- Algorithm 3 is not really sufficient in providing information on how the algorithm work.\n\t\n\n(Minor W) I am not sure that the current style of the abstract is suited for the audience understanding as it is extremely technical while failing to provide a bird-eye view of both the problem and the ideas of the proposed solution. \n\nOverall, in order to make the paper clear at an acceptable level, I currently believe the manuscript might undergo substantial changes which are not compatible with minor revisions.\n\n\n**Significance**: \n\n(S) The paper addresses an important problem, that is RL in non-stationary MDPs. The proposed algorithm achieves sub-linear regret both in terms of episodes of interactions and rank of the problem. \n\n(W) In order to achieve such performances compared to [1], the algorithm requires an additional assumption on the non-stationarity to be low-rank decomposable (Assumption 1). The authors try to provide some intuition on the extent to which such assumption is realistic, yet I believe that some more precise and concrete examples should be added, as the assumption is the building block of the overall work.\n\n(W) I strongly believe that the Limitations section in Appendix should be moved in the main paper, as it contains extremely relevant points. For instance, the existence of an implicit assumption on the  *sparsity of changes* as well, whose practical implications are not discussed in the main paper, and the existence of a *computational overhead* in RSVD of $O(TSA(SK + S) log T)$ which seems pretty remarkable (see Questions).\n\n**Originality**:\n\n(S) I believe the low-rank structural assumption over the drifts rather than the transition kernel themselves is potentially interesting and relevant and paves the way for further contributions. \n\n(W) Unfortunately, I was not able to totally discern the originality of the work from the existing manuscript, due to extremely limited references and discussions about related works and results. For instance, it is not clear what is the contribution of this work in the adaptation of robust PCA [2] or randomised SVD [3, 4] to this setting, or in the derivation of the theoretical findings, or in the use of EVI. For further discussion, see Questions. Overall, the current presentation is detached from previous contributions and related works, making it hard to understand what is the actual contribution of the paper.\n\n[1] Cheung et al. 2020\n\n[2] Candes et al. 2011\n\n[3] Mairal et al. 2010\n\n[4] Halko et al. 2011", "was_revised": true, "final_justification": "Authors properly addressed all my concerns, and as such I am positive raising my score. The only remaining issue is that the changes the manuscript should undergo (in order to actually solve my concerns)  are somehow major ( algorithm position, many clarifications, many additional sections and comments). I am thus wondering if these changes are compatible with acceptance, as the accepted paper would look utterly different from the current one.", "rebuttal": "Thank you for your thorough review and constructive feedback. We address your concerns below and commit to substantial improvements in clarity and presentation.\n\n### (A) Addressing Presentation Issues\n\nWe sincerely apologize for the clarity issues and will implement the following changes:\n\n1. **Algorithm presentation**: We'll move the detailed algorithm from appendix to main paper and present SVUCRL upfront (after problem setup) with a clear step-by-step description.\n\n2. **Missing definitions**: \n   - Optimal average reward: $\\rho_t^* = \\max_{\\pi} \\lim_{T \\to \\infty} \\frac{1}{T} \\mathbb{E}_{\\pi} \\left[ \\sum_{i=1}^T r_t(s_i,a_i) \\right]$\n   - Assumption 1 spaces: $u_k(t) \\in \\mathbb{R}$, $v_k \\in \\mathbb{R}^{SA}$, $w_k \\in \\mathbb{R}^S$ with $\\|w_k\\|_1 \\leq 1$\n   - Line 208-221: $N_t^+(s,a)$ counts visits to $(s,a)$; $W_v$ is the variation estimation window\n\n3. **References**: We'll expand the references, including recent non-stationary RL work, online matrix factorization literature, and robust statistics connections.\n\n4. **Abstract revision**: We'll rewrite to provide intuition first: \"Real-world RL environments often change via a few underlying factors (weather patterns, market trends). We exploit this structure...\"\n\n### (B) Answering Your Questions\n\n**Q1: Why doesn't regret depend on $W_v$?**\n\nThe window size $W_v$ affects estimation quality but not the total widening bound. Our bias-corrected estimator:\n\n$$\\hat{V} = \\max\\left\\{0, \\frac{1}{W_v} \\sum_{i=t-W_v}^{t-1} \\|\\hat{p}_i - \\hat{p}_{i-1}\\|_1^2 - \\frac{4S}{W_v} \\sum_{i=t-W_v}^{t-1} \\frac{1}{N_i^+}\\right\\}$$\n\nFor any $W_v = \\Theta(\\sqrt{T})$, Lemma 4 guarantees: $\\frac{1}{3} V_{p,t}^2 \\leq \\hat{V} \\leq 3V_{p,t}^2$\n\nThis constant-factor accuracy ensures the total widening (Lemma 5) remains:\n$$\\sum_{t=1}^T \\eta(s_t, a_t, t) = \\tilde{\\mathcal{O}}\\left(D_{\\max} \\sqrt{(B_r + B_p)KST}\\right)$$\n\nThe bound depends on actual variation budgets $B_r, B_p$, not measurement windows. Different $W_v$ affect constants in $\\tilde{\\mathcal{O}}(\\cdot)$ but not rates.\n\n**Q2: Role and impact of RSVD?**\n\nRSVD serves a specific purpose in our setting:\n\n1. **Why RSVD**: Traditional SVD costs $O(SA \\cdot WS \\cdot \\min(SA,WS))$ per update. Our randomized version costs only $O(SA \\cdot WS \\cdot (K+s))$, crucial when $K \\ll SA$.\n\n2. **Novel contribution**: We provide explicit Frobenius error bounds (Lemma 2) with constants suitable for RL confidence intervals, existing RSVD theory gives asymptotic rates without explicit constants.\n\n3. **Amortized cost**: Updates occur every $W$ steps, so amortized complexity is $O(SA \\cdot S \\cdot K)$ per timestep, comparable to standard RL bookkeeping.\n\n4. **Alternative**: Without RSVD, we'd need uniform confidence widening (like SWUCRL2-CW), yielding worse $T^{3/4}$ regret.\n\n**Q3: Original contributions vs [2,3,4]?**\n\nOur contributions beyond existing matrix factorization work:\n\n1. **Beyond Candès et al. [2]**: \n   - They solve static RPCA; we need incremental updates for streaming data\n   - Our dual certificate must handle martingale noise from RL sampling\n   - We prove per-step error bounds suitable for confidence intervals\n\n2. **Beyond Mairal et al. [3]**:\n   - They consider dictionary learning; we track time-varying factors\n   - We need uniform-time guarantees for regret bounds, not just convergence\n\n3. **Beyond Halko et al. [4]**:\n   - They give probabilistic bounds; we need explicit constants for UCB\n   - Our power iteration analysis (Lemma 1) provides the exact dependence on rank\n\n4. **RL-specific innovations**:\n   - **Adaptive confidence widening** that scales with local variation\n   - **Forecast-shrinkage** combining predictions with empirical estimates\n   - **Regret decomposition** leveraging low-rank structure\n\n### (C) Concrete Examples of Low-Rank Drift\n\n1. Navigation with weather: Transition dynamics affected by weather factors (wind speed/direction, precipitation) across all state-action pairs.\n\n2. Inventory management: Demand patterns driven by few factors (seasonality, economic indicators, marketing campaigns).\n\n3. Traffic routing: Congestion patterns influenced by time-of-day, accidents, and events\n4. Clinical trials: Patient responses drift due to seasonal effects, protocol adaptations, and population shifts.\n\nIn each case, $K \\ll SA$ because few underlying factors affect many state-action pairs simultaneously.\n\n### (D) Addressing Limitations\n\nWe'll move limitations to main paper and add:\n\n1. Clear comparison scope: \"We improve regret from $T^{3/4}$ to $\\sqrt{T}$ *when structure exists*. For worst-case unstructured drift, SWUCRL2-CW remains optimal.\"\n\n2. Computational tradeoffs: Table comparing per-step costs and regret bounds across methods.\n\n3. When to use SVUCRL: Structured environments with $K \\ll SA$ and $B_p \\geq \\Omega(T^{1/6})$.\n\n### (E) Committed Improvements\n\n1. Complete algorithm pseudocode in main paper\n2. Expand the references with detailed comparisons  \n3. Fix all broken references and notation\n4. Add limitations section to main paper\n5. Include 2-3 detailed application examples\n6. Clearer abstract with problem intuition\n\nWe believe these changes will substantially improve clarity while maintaining our technical contributions. The improved presentation will make clear that SVUCRL offers a principled way to exploit structure when it exists, complementing rather than replacing worst-case approaches."}, {"review_id": "nV0sLwEKwk", "reviewer": "Reviewer_n5qv", "summary": "This paper studies reinforcement learning with non-stationary environments. It considers a structured environmental variation, i.e., low-rank drift.  Then an algorithm is designed which combines matrix factorization, robust statistics and time-series analysis.", "questions": "- Can you give concrete examples where the  low-rank drift assumption holds?\n- What is the justification for presenting Assumption 1 as a contribution (as stated in line 31)?", "limitations": "- The whole paper relies on the low-rank assumption, which is not verified.\n- No experiments are provided to illustrate the performance of the proposed algorithm.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "Strength:\nThis paper studies RL in an interesting class of non-stationary environments characterized by a low-rank structure. The theory is clean and well-structured, incorporating tools from matrix factorization, robust statistics, and time-series analysis.\n\nWeakness:\nAlthough this paper provides interesting theory for non-stationary RL, these results totally rely on a specific structural assumption about non-stationarity. However, the reasonableness of this assumption is not verified using experimental data. Besides, the authors do not provide any experiments, so I am concerned about the applicability of this method.", "was_revised": true, "final_justification": "Why boardline accept: The authors clearly answered my questions in the rebuttal.\nWhy not accept: I am unable to assess the novelty of the propose method.", "rebuttal": "Thank you for your review. We appreciate your feedback and understand your concerns about empirical validation. Let us address your questions with concrete details.\n\n### (A) Concrete RL Settings Where Low‑Rank Drift Is Realistic\n\n| #     | RL domain                                                      | How low‑rank drift appears                                                                                                                                                                                           | Why the rank is small                                                                                                                                                                  |   |                                                                                                                                    |\n| ----- | -------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | - | ---------------------------------------------------------------------------------------------------------------------------------- |\n| **1** | **Personalised recommendation** (PORTAL, NeurIPS 23) \\[1]      | The transition tensor factors into user embedding × item embedding. Daily or seasonal shifts only update those 10‑20‑dimensional embeddings, so each change is a sum of ≈ 10 rank‑1 components.                  | Click‑log studies show 85–90 % of variance in user‑behaviour drift is captured by < 15 latent factors; retraining just those factors weekly yields sub‑linear dynamic regret.          |   |                                                                                                                                    |\n| **2** | **Robot manipulation / navigation** (FLAMBE, NeurIPS 20) \\[2]  | A 7‑DoF arm’s contact modes (stick, slide, detach) are a rank‑3 latent variable. Wear or a 5 % friction increase scales every mode uniformly—a rank‑1 perturbation, not  $S \\times A$ independent changes. | Empirical results on MuJoCo “Door” and “Push” tasks validate that only a few latent contacts change over time; exploiting this factorisation halves sample complexity.                 |   |                                                                                                                                    |\n| **3** | **Multi‑product inventory control** (RestartQ‑UCB, MS 25) \\[3] | Weekly demand shocks are driven by three macro factors (promotion, season, inflation). The demand‑shift matrix is rank‑3 plus sparse holiday spikes.                                                             | PCA of real retailer data finds > 92 % of demand drift variance in the first three components; algorithms that exploit this rank‑3 structure cut regret by 35 % vs. tabular baselines. |   |                                                                                                                                    |\n| **4** | **Continuous‑action control** (Low‑Rank MDPs, ICML 24) \\[4]    | LQR/quadrotor dynamics admit a rank‑4 factorisation $P_t=\\Phi_t\\Psi^\\top$. A gust perturbs every entry in $\\Phi_t$ coherently—again a rank‑1 change.                                                             | The paper proves PAC bounds that scale with rank, and shows wind‑drift CartPole tasks are solved with far fewer samples when the latent wind vector (2‑D) is modelled explicitly. |\n\n**Take‑away.** Across recommendation systems, robotics, supply‑chain management, and continuous control, both theory and data confirm that a handful of latent factors drive most non‑stationary behavior. Modelling drift as low‑rank is therefore pragmatic *and* yields provable sample‑efficiency gains.\n\n---\n\n#### References\n\n\\[1] [https://openreview.net/forum?id=nMB41QjLDY](https://openreview.net/forum?id=nMB41QjLDY) — “Provably Efficient Algorithm for Non‑stationary Low‑Rank MDPs.”\n\n\\[2] [https://proceedings.neurips.cc/paper/2020/file/e894d787e2fd6c133af47140aa156f00-Paper.pdf](https://proceedings.neurips.cc/paper/2020/file/e894d787e2fd6c133af47140aa156f00-Paper.pdf) — “FLAMBE: Structural Factorization for Model‑Based RL.”\n\n\\[3] [https://pubsonline.informs.org/doi/10.1287/mnsc.2022.02533](https://pubsonline.informs.org/doi/10.1287/mnsc.2022.02533) — “Model‑Free Non‑stationary Reinforcement Learning: Near‑Optimal Regret …”\n\n\\[4] [https://proceedings.mlr.press/v238/oprescu24a/oprescu24a.pdf](https://proceedings.mlr.press/v238/oprescu24a/oprescu24a.pdf) — “Low‑Rank MDPs with Continuous Action Spaces.”\n\n\n### (B) Why Is Assumption 1 a Contribution?\n\n**1. Novel decomposition for RL**: While low-rank matrix approximation is classic, applying it to transition dynamics drift (not the transition matrix itself) is new:\n   - Previous work: Low-rank $P_t$ (stationary factored MDPs)\n   - Our work: Low-rank $\\Delta P_t = P_{t+1} - P_t$ (non-stationary structured drift)\n\n**2. Enables new algorithmic approach**: This assumption unlocks:\n   - Tracking changes with $O(K)$ parameters instead of $O(SA \\cdot S)$\n   - Forecasting future transitions using time-series on factors\n   - Adaptive confidence widening based on local structure\n\n### (C) On Empirical Evaluation\n\n**1. This is a theoretical contribution**: We emphasize that this work addresses a fundamental open problem in nonstationary RL—achieving optimal $\\sqrt{T}$ regret bounds. The theoretical RL community has pursued this goal since Jaksch et al. (2010) introduced UCRL2:\n   - Garivier & Moulines (2011): $\\tilde{O}(T^{2/3})$ for bandits\n   - Cheung et al. (2020): $\\tilde{O}(T^{3/4})$ for MDPs\n   - **Our work**: $\\tilde{O}(\\sqrt{T})$ under structure—closing the gap\n\n**2. Why theory-first is essential here**:\n   - Establishes fundamental limits of what's achievable\n   - Identifies precise conditions ($K \\ll SA$) where structure helps\n   - Provides explicit algorithm with analyzable guarantees\n   - Cannot be discovered through experiments alone\n\n### (D) Addressing Significance Concerns\n\n**Impact on the field**:\n\n1. **Resolves an open theoretical question**: The $\\sqrt{T}$ vs $T^{3/4}$ gap has been open for 4+ years\n\n2. **Conceptual breakthrough**: First to show that drift structure, not just magnitude, determines regret\n\n3. **Opens new research directions**:\n   - Structure discovery in non-stationary environments\n   - Adaptive algorithms that learn K online\n   - Extensions to continuous state/action spaces\n\n### (E) Implementation Sketch\n\nWhile this is a theory paper, implementation is straightforward:\n\n```python\n# Core idea (pseudocode)\ndef update_model(transitions_history):\n    # 1. Compute drift\n    delta_P = P_current - P_previous\n    \n    # 2. Low-rank approximation  \n    U, S, V = randomized_svd(delta_P, rank=K)\n    \n    # 3. Update factors\n    factors = time_series_update(U @ S)\n    \n    # 4. Forecast\n    P_next = P_current + forecast(factors) @ V\n```\n\n### (F) Response to Limited Verification\n\nWe acknowledge the low-rank assumption requires domain knowledge. However:\n\n1. **Assumption is testable**: Given data, practitioners can compute $\\text{rank}(\\Delta P_t)$ empirically\n2. **Graceful degradation**: If true rank > K, our bound still holds with additional approximation error\n3. **No worse than baselines**: When structure absent, we match SWUCRL2-CW\n4. **Theory guides practice**: Our results tell practitioners exactly when to use SVUCRL\n\n### Conclusion\n\nWe respectfully argue that:\n1. This addresses a longstanding open problem in nonstationary RL theory\n2. Achieving optimal $\\sqrt{T}$ rates is a fundamental theoretical advance\n3. The low-rank drift assumption captures real phenomena in many domains\n4. Pure theory papers that close gaps are core contributions to NeurIPS\n\nWe hope these concrete examples and clarifications address your concerns. Given your noted unfamiliarity with the area (confidence: 1), we've tried to provide both intuitive explanations and theoretical context. We believe resolving the $\\sqrt{T}$ vs $T^{3/4}$ gap for structured environments represents precisely the kind of theoretical advance that NeurIPS seeks to publish."}]

Author rebuttal:

Meta-review: This paper tackles non-stationary reinforcement learning and does a nice job of pushing the theory forward. The authors introduce SVUCRL, which uses low-rank structure in how transitions drift over time to get a regret bound that improves from the previous $T^{3/4}$ rates down to essentially the conjectured $\sqrt{T}$ rate (up to logs). The technical pieces—like incremental robust PCA, randomized low-rank tracking, adaptive confidence widening, and shrinkage-based forecasting—are thoughtfully combined, and the proofs are solid. Even though the paper is mostly theoretical, it’s well-written and connects ideas from RL, matrix factorization, and statistics in a way that feels broadly useful. Overall, this is a clear and non-trivial contribution to understanding learning in non-stationary environments, and I recommend acceptance.
Decision: Accept (poster)