Reinforcement learning agents that approximate values with linear features currently have to choose between two kinds of data weighting, and neither is enough on its own. Agents that are provably as sample-efficient as possible, in the sense of matching the worst-case lower bound, down-weight each transition by how noisy it is. Agents built for environments that change over time down-weight each transition by how old it is. The first kind breaks when the environment drifts. The second kind wastes data because it treats a nearly deterministic transition and a highly random one as equally informative. We propose to replace both with a single weight: the inverse of the observation's noise variance plus an estimate of how much its target has drifted since it was collected. Under this weight, an old but very precise observation is discounted exactly as much as its staleness warrants, and no more.
The payoff is concrete. The best known guarantee for drifting linear Markov decision processes grows as $K^{3/4}$ in the number of episodes $K$ (Efficient Learning in Non-Stationary Linear Markov Decision Processes). Simpler drifting problems admit $K^{2/3}$. We conjecture that the missing $K^{1/12}$ is caused not by drift itself but by the analysis technique used to handle it, and that the variance-weighted analysis used for stationary problems can remove it once the weights are formulated correctly.
Core Claim
We first need two definitions. Minimax optimal regret means that the total reward an algorithm loses relative to the best policy matches, up to logarithmic factors, the smallest loss any algorithm could guarantee on the problem class. Dynamic regret is the same quantity measured against the best policy for each episode's current environment.
In stationary linear MDPs, LSVI-UCB+ reaches minimax regret $\widetilde{O}(Hd\sqrt{T})$ through two ingredients. The first is ridge regression weighted by estimated conditional variances. The second is a split of the estimation error into a term involving the fixed optimal value function $V^*$ and a small correction term. This split avoids a union bound over all possible value functions, which would otherwise cost an extra $\sqrt{d}$. OPT-WLSVI, the drifting counterpart, uses exponential discounting with a Hoeffding-type bonus and pays that union-bound cost inside the confidence radius. That radius is then balanced against the drift bias $\eta^{-1}\Delta$, and the balance lands at $d^{5/4}H^2\Delta^{1/4}K^{3/4}$.
Our structural observation is that under drift chosen in advance (oblivious drift), the per-episode optimal values $V^*_k$ form a fixed sequence that does not depend on the data. The error-splitting argument therefore still goes through if the dominant term is taken relative to $V^*_k$ for the current episode. What prevents this today is Gap 2 of the literature. If temporal discounting and inverse-variance weights are simply multiplied, the Bernstein-style self-normalized concentration no longer applies cleanly. It also lets a low-variance stale point dominate the estimate (Gap 4).
We resolve this by treating staleness as an additional variance term. At episode $k$, stage $h$, a past transition from episode $s$ receives the weight
$$ w^{(k)}_{s,h} = \frac{1}{\bar\sigma^2_{s,h} + \rho^2 (k-s)^2}, $$
In this formula, $\bar\sigma^2_{s,h}$ is the clipped variance estimate of the next-stage value at $(s^s_h,a^s_h)$, as in LSVI-UCB+. The parameter $\rho$ is a per-episode drift rate, so $\rho(k-s)$ bounds the bias the drift can have introduced since episode $s$. This is the weighting a Kalman filter would apply under a drift model: the effective noise of an observation is its measurement noise plus the drift accumulated since it was taken.
The resulting weight equals $1/\sigma^2$ for recent data and decays polynomially rather than exponentially for old data. Old precise points are no longer over-trusted, and old noisy points are not doubly penalized. Our target is a dynamic regret bound of order $\widetilde{O}(\mathrm{poly}(d,H)\,\Delta^{1/3}K^{2/3})$ for drifting linear MDPs, together with a variance-dependent refinement that improves on it when the total variance is small.
Relation to Prior Work
The motivating evidence comes from three papers. OPT-WLSVI (Touati & Vincent) explicitly names the $K^{3/4}$ versus $K^{2/3}$ gap. Its weights depend only on time, and its bonus scales with the reward range $H$. We keep its "weighted average MDP" bias device and change both the weights and the concentration argument.
LSVI-UCB+ (Hu et al.) supplies the method we reuse: the variance head, the Bernstein bonus, and the $V^*$ versus $(V-V^*)$ split. It assumes stationarity and needs $T \ge \max\{H^4d^{10},H^5d^5\}$ episodes before its guarantee applies. We do not attempt to shorten that burn-in.
Variance-Dependent Regret Bounds for Nonstationary Linear Bandits is the closest existing work. It combines inverse-variance weighting with drift, but only for bandits (a single step, $H=1$) and with scheduled hard restarts, which erase the accumulated design matrix every $L$ rounds. Our proposal moves to multi-step MDPs, where variance must be estimated through the Bellman backup, and replaces the restarts with the additive staleness weight.
D-LinUCB shows that smooth forgetting outperforms change-point detection under gradual drift and attains the optimal $B_T^{1/3}T^{2/3}$ rate for bandits. We take this as evidence that forgetting should be smooth, while arguing that it should also account for how noisy each observation is.
Two lines of work constrain the design. POWERS-FixShare attains minimax dynamic regret in linear mixture MDPs, but it relies on full-information rewards and known basis kernels. We work with standard linear MDPs under bandit feedback, so its techniques do not transfer directly. Chen, Ito, and Imaizumi show that transformers can emulate sliding windows and stationarity tests with optimal dynamic regret in bandits. We read this as a statement about which rates are achievable, not as a practical competitor for continuous-state MDPs.
Research Program
Analysis. The first component is the concentration argument. The weight depends on the current episode $k$, so the weighted sums are not ordinary martingales in the usual order of time. We handle this in the style of Touati and Vincent: for each fixed $k$, the weights are predictable functions of past variance estimates and deterministic ages, and we apply a Bernstein self-normalized inequality separately for each $k$, with a union bound over $k$.
The key step is to show that the effective sample size $\sum_s w^{(k)}_{s}$ behaves like a window of length about $\bar\sigma/\rho$ along each feature direction. Bias then contributes $\rho\cdot$window, and variance contributes $\bar\sigma/\sqrt{\text{window}}$ per unit weight. Balancing these two terms, with the covering penalty removed by the split, is where the $K^{2/3}$ rate should come from. It is the same arithmetic as the D-LinUCB bandit rate, now with $d$ and $H$ entering only through the Bernstein radius.
If the split fails because the correction term $(V_k - V^*_k)$ drifts faster than it contracts, the proof attempt will show exactly where. That is itself a useful negative result, because it would indicate that the gap is intrinsic to linear MDPs.
Variance head under drift. The second component is the variance head. We fit it with the same staleness weights, so that the variance estimate, like the value estimate, ignores stale squared targets. We also add an explicit bonus for its drift bias, which directly targets Gap 4. We will test whether a single drift rate $\rho$ suffices for both heads.
Choosing $\rho$ without knowing the drift budget. Knowing $\Delta$ in advance is unrealistic. We estimate $\rho$ online from residual inflation: the squared residuals of older transitions under the current estimate, minus their predicted noise variance, grow with age at rate $\rho^2$. A regression on age gives a plug-in estimate. As a fallback with guarantees, we run a small hedging layer over a geometric grid of $\rho$ values and compare it against the plug-in version.
Computation. Recomputing the weights every episode costs $O(K^2)$, the same as OPT-WLSVI. We will also test an approximation that represents $1/(a+\rho^2 t^2)$ as a sum of a few exponentials, which reduces the cost to incremental rank-one updates.
Baselines
The do-nothing reference is stationary LSVI-UCB+ (Hu et al.) with no forgetting at all. Under drift it should accumulate regret linear in $K$. Without drift it is the ideal method, so it defines the no-harm target on stationary runs.
The strongest existing method for drifting linear MDPs is OPT-WLSVI (Touati & Vincent). We run it with its discount $\eta$ tuned over the same grid size, and the same budget of environment interactions, as our $\rho$. Beating it means lower final dynamic regret with non-overlapping confidence intervals across seeds. It also means a fitted log-log regret slope in $K$ closer to $2/3$ than to $3/4$ on problems where the drift is fixed per episode.
The strongest restart competitor is our own MDP extension of Restarted-WeightedOFUL+ (Wang et al.): LSVI-UCB+ restarted every $L$ episodes, with $L$ tuned over a grid of the same size and also wrapped in Bandit-over-Bandit for the unknown-budget runs. A second restart baseline resets LSVI-UCB+ whenever an Incremental Kolmogorov–Smirnov detector (Reis et al.) fires on the reward and next-feature streams. Its window size is tuned under the same budget.
Two ablations isolate the key ingredient. The first uses the product weight $\gamma^{k-s}/\bar\sigma^2_s$, which tests whether the additive staleness form matters or whether combining the two weights in any way is enough. The second uses staleness weights with $\bar\sigma^2$ fixed at its maximum, which tests whether the variance term matters.
On single-step benchmarks we use D-LinUCB and Restarted-WeightedOFUL+/SAVE+ as the bandit baselines. As a stationary reference point on the neural bandit suite, Neural-σ²-LinearUCB reports cumulative regret below 1000 on MNIST, against about 1600 for Neural-LinUCB. With no drift present, our weight should match the former and not regress toward the latter. For all the drifting benchmarks below, we found no reported numerical result on Lacuna for any baseline. The papers report curves or qualitative comparisons only, so every drifting-benchmark number will come from our own reruns.
Why not just…?
Why not just use discounted least squares without variance weights, as in OPT-WLSVI or D-LinUCB? Their bonuses scale with the worst-case range of the value function rather than its actual variance. In stationary linear RL, that choice is exactly what costs the extra $\sqrt{H}$ (Hu et al.; UCRL-VTR+). The union-bound penalty inside OPT-WLSVI's confidence radius is our leading suspect for its $K^{3/4}$ exponent. The ablation with $\bar\sigma^2$ fixed at its maximum answers this question directly. If it matches our full method at large $H$ and low variance, the variance term is unnecessary and we will say so.
Why not just restart LSVI-UCB+ every $L$ episodes? This is the most serious threat. It is the natural MDP extension of Wang et al., and under abrupt switches it may well be competitive. Its weakness is that each restart discards coverage along rarely visited feature directions, and $L$ must be tuned to an unknown budget. We expect it to lose under gradual drift and in high dimension, and possibly to tie under a few abrupt jumps. We will report both outcomes. If it ties everywhere, our contribution narrows to the theoretical rate.
Why not just detect drift and reset? D-LinUCB found that change-point methods fail to flag slow rotation of the parameter and accumulate large regret. Statistical tests also need a minimum window before they can detect anything (Reis et al.). The rotating-drift and abrupt-jump benchmarks together show where this approach helps and where it fails.
Why not just multiply the discount and the inverse variance? A product weight keeps an old, near-zero-variance point at enormous weight long after it has become biased, which is exactly the failure described in Gap 4. The product-weight ablation, run on an environment with a deterministic region that later drifts, is designed to expose this effect.
Proposed Experiments
Drifting linear MDPs. We inject drift into the synthetic linear MDPs (synthetic_random, synthetic_robust) and the CTRL-linearized Pendulum and Mountain-Car tasks from the IntrinsicRobustness codebase associated with the reward-poisoning study. Drift is applied to $\mu_h$ and $r_h$ in three forms: a slow rotation, a few abrupt jumps, and sine-wave drift. We control heteroscedasticity by making a subset of states deterministic.
We sweep $K$ over a decade and $H \in \{10, 30, 100\}$, and fit log-log slopes of dynamic regret against $K$ at fixed $\Delta$. The decisive check is whether our slope sits near $2/3$ while OPT-WLSVI's sits near $3/4$, and whether our advantage grows with $H$ when total variance is low.
Bandit sanity checks ($H=1$). We reproduce the sine-drift, Bernoulli-noise benchmark of Wang et al., where $V_K \sim \log K$. We also run the rotating and jumping 2D benchmark and the Criteo coordinate-flip stream from Russac et al.. The metrics are cumulative dynamic regret and time to recover after the flip. At $H=1$ the staleness weight should at least match restarted variance weighting, which confirms that the MDP gains are not artifacts of a weak bandit implementation.
Stationary no-harm test. On the MNIST neural bandit setup of Bui et al., with no drift, the online estimate of $\rho$ should shrink toward zero, and regret should stay in the range reported for Neural-σ²-LinearUCB rather than rising toward that of Neural-LinUCB.
Falsification criteria. The central claim fails if the product-weight ablation matches the additive weight on the deterministic-then-drifting environment. It also fails if the fitted regret slope does not separate from OPT-WLSVI's as $K$ grows. Either result would tell us that the rate gap in linear MDPs is not a weighting problem.
References
- Efficient Learning in Non-Stationary Linear Markov Decision Processes
- Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation
- Variance-Dependent Regret Bounds for Nonstationary Linear Bandits
- Weighted Linear Bandits for Non-Stationary Environments
- Dynamic Regret of Adversarial Linear Mixture MDPs
- Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning
- Fast Unsupervised Online Drift Detection Using Incremental Kolmogorov-Smirnov Test
- Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits
- Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
- When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs