Invariance-Based Dynamic Regret Minimization
| Authors | Margherita Lazzaretto et al. |
| Year | 2026 |
| Field | Statistics / ML |
| arXiv | 2603.03843 |
| Download | |
| Categories | stat.ML, cs.LG |
Abstract
We consider stochastic non-stationary linear bandits where the linear parameter connecting contexts to the reward changes over time. Existing algorithms in this setting localize the policy by gradually discarding or down-weighting past data, effectively shrinking the time horizon over which learning can occur. However, in many settings historical data may still carry partial information about the reward model. We propose to leverage such data while adapting to changes, by assuming the reward model decomposes into stationary and non-stationary components. Based on this assumption, we introduce ISD-linUCB, an algorithm that uses past data to learn invariances in the reward model and subsequently exploits them to improve online performance. We show both theoretically and empirically that leveraging invariance reduces the problem dimensionality, yielding significant regret improvements in fast-changing environments when sufficient historical data is available.
Engineering Breakdown
Plain English
This paper tackles the problem of learning from changing environments in stochastic linear bandit settings, where the reward model shifts over time. Most existing algorithms discard old data to adapt to changes, but this wastes potentially useful historical information. The authors propose that reward models often decompose into stable (stationary) and changing (non-stationary) components, and introduce ISD-linUCB—an algorithm that learns what stays constant about the reward model from past data, then exploits those invariances to make better decisions in the present. Both theory and experiments show this approach reduces regret compared to methods that simply forget the past.
Core Technical Contribution
The key innovation is decomposing the linear reward parameter into stationary and non-stationary components, allowing the algorithm to extract and reuse learnable invariances from historical data rather than discarding it. ISD-linUCB introduces a mechanism to identify which aspects of the reward model are stable across time, then leverages this knowledge to improve exploration-exploitation trade-offs in the current non-stationary context. This is fundamentally different from prior work that treats non-stationarity as a reason to shrink the effective learning horizon; instead, it treats stationarity as an asset to be mined. The algorithm couples invariance learning with online adaptation, creating a hybrid approach that neither fully trusts old data nor completely rejects it.
How It Works
The algorithm operates in two coupled phases: first, it uses historical data to learn a representation of the stationary component of the reward model—the features or parameters that remain invariant over time. Concretely, ISD-linUCB maintains a feature space that captures reward structure that persists across time periods, while simultaneously learning time-varying adjustments on top of this base model. At each round, the algorithm performs confidence-bound-driven exploration (similar to standard linUCB) but uses the learned invariances to tighten its uncertainty estimates, because some directional information is trusted across time. The non-stationary component is handled via localization (down-weighting or forgetting) but only for the residual unexplained by the stationary part. The output at each step is a context-aware action decision that balances exploration in uncertain directions with exploitation of both time-invariant and time-specific reward signals.
Production Impact
In real-world systems with gradually-evolving reward structures—recommendation systems where user preferences drift, pricing models subject to seasonal trends, or supply-chain optimization with stable cost structures but fluctuating demand—this approach can substantially reduce the regret budget (exploration cost) compared to naive forgetting strategies. Engineers would integrate invariance learning as a preprocessing/parallel track: maintain a slowly-updated model of stable reward components while running the online bandit algorithm on top. This trades modest additional computation (learning invariances from a growing historical dataset) for fewer exploration samples wasted on rediscovering known structure. In practice, you'd need to decide periodically whether to refresh invariance estimates; a wrong choice could lead to systematic bias if the environment shifts in unexpected ways. The method assumes some reward structure genuinely persists—if the environment is chaotic with no stable components, this adds overhead without benefit.
Limitations and When Not to Use This
The core assumption that rewards decompose into stationary and non-stationary parts may not hold for many real environments where drift is correlated or cascading. The paper provides no principled way to detect when this decomposition assumption is violated or when the learned invariances have become stale—an algorithm could silently suffer if it over-trusts outdated structure. Computational complexity of learning and maintaining invariances over a growing historical dataset is mentioned only briefly; in high-dimensional settings or with streaming data, this could become prohibitive. The theoretical analysis (which appears incomplete in the abstract) likely requires bounded drift or smoothness conditions on the non-stationary component that may not be realistic in adversarial or chaotic settings. The paper would benefit from ablations showing sensitivity to the invariance learning procedure itself and concrete guidance on when NOT to use this over simpler baselines.
Research Context
This work extends the stochastic linear bandit literature, which has traditionally handled non-stationarity through aggressive forgetting (sliding windows, discounting, or resets). It's motivated by observation that many real systems have partially stable structure—building on intuition from transfer learning and domain adaptation where invariances across tasks are mined and reused. The approach aligns with recent trends in online learning to combine representation learning (learning what's stable) with contextual bandits (using that representation for decisions). This opens a research direction toward hybrid non-stationarity handling: rather than choosing between full memory and full forgetting, strategically decompose the problem to keep what matters and shed what doesn't, with formal guarantees.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::