Invariance-Based Dynamic Regret Minimization

The paper proposes ISD-linUCB, an algorithm for stochastic non-stationary linear bandits that leverages the decomposition of reward models into stationary and non-stationary components to learn invariances from historical data, thereby reducing problem dimensionality and significantly improving dynamic regret in fast-changing environments.

The Gist

Here is an explanation of the paper "Invariance-based dynamic regret minimization" using simple language and creative analogies.

The Big Picture: The Chameleon Chef

Imagine you are a chef trying to perfect a recipe for a soup that changes its taste slightly every day.

• The Context: The ingredients you have (the "context").
• The Action: The amount of salt you add (the "action").
• The Reward: How good the soup tastes (the "reward").

In the world of Machine Learning, this is called a Contextual Bandit. The goal is to learn the perfect recipe to maximize the "taste score" over time.

The Problem: The Moving Target

Usually, algorithms assume the recipe is static. But in the real world, things change. Maybe the water quality changes, or the supplier switches to a different type of salt. This is a non-stationary environment.

Existing algorithms handle this by being very cautious: they say, "The world changed yesterday, so I'm going to throw away all my old notes and start learning from scratch." They only look at the last few days of data.

• The Flaw: This is like throwing away your entire cookbook because the water changed. You might have learned that salt always needs to be added, regardless of the water. By discarding old data, you lose valuable, permanent knowledge.

The Solution: The "ISD-linUCB" Algorithm

The authors propose a new way to think about the problem. They suggest that even though the soup recipe changes, some parts of it never change.

Think of the recipe as having two parts:

1. The Invariant Part (The Constant): "Always add 2 grams of salt." This rule never changes, no matter the day.
2. The Residual Part (The Variable): "Adjust the pepper based on the humidity." This part changes constantly.

The new algorithm, ISD-linUCB, uses a clever trick:

1. Offline Phase (The Library): It looks at a massive library of old recipes (historical data) to figure out what never changes. It isolates the "Always add salt" rule.
2. Online Phase (The Kitchen): When a new day comes, it doesn't re-learn the salt rule. It already knows that. Instead, it only focuses on learning the changing part (the pepper).

The Analogy: The GPS and the Road

Imagine you are driving a car (the algorithm) on a road that is constantly under construction (the changing environment).

• Old Algorithms: Every time the road shifts, the GPS says, "I have no idea where I am! Let me forget the map and start scanning for landmarks again." This is slow and inefficient.
• ISD-linUCB: The GPS realizes that while the road is changing, the compass (North) and the laws of physics (gravity) never change.
  • It uses old data to lock onto the Compass (the invariant part). It knows North is always North.
  • It only uses its current sensors to figure out the Road Construction (the residual part).

By separating the "Compass" from the "Road," the car doesn't have to re-learn how to drive; it only has to learn where the potholes are today.

Why This Matters: The "Dimension" Magic

In math terms, the "size" of the problem is called dimension ($p$).

• If you have 10 ingredients to figure out, the problem is "10-dimensional."
• If you have to learn all 10 from scratch every time the environment changes, it takes a long time.

The paper proves that if you can identify that only 2 of those ingredients are actually changing (and the other 8 are constant), you don't need to learn 10 things. You only need to learn 2.

• The Result: The algorithm makes fewer mistakes (lower "regret").
• The Catch: You need a big library of old data (offline data) to figure out which parts are constant. If you have enough history, the algorithm becomes incredibly fast and accurate in a chaotic world.

Summary of Contributions

1. The Algorithm (ISD-linUCB): A new method that splits the problem into "what stays the same" and "what changes."
2. The Math: They proved that if you have enough historical data, your mistakes grow much slower than before. Instead of struggling with the full complexity of the world, you only struggle with the changing part.
3. The Proof: They showed through simulations that this works. When they gave the algorithm a huge history book, it learned the "constant" rules instantly and only focused on the "changing" rules, beating standard algorithms that tried to relearn everything.

The Takeaway

In a world that is constantly changing, the smartest move isn't to forget the past. It's to figure out what in the past is still true today, lock that knowledge in, and only spend your energy figuring out what's new. That is the power of Invariance-based learning.

Technical Summary

Here is a detailed technical summary of the paper "Invariance-based dynamic regret minimization" by Lazzaretto, Peters, and Pfister.

1. Problem Setting

The paper addresses stochastic non-stationary linear contextual bandits.

• Context: An agent interacts with an environment over $T$ rounds. In each round $t$, the agent observes a context $X_t$, selects an action $a_t$, and receives a noisy reward $R_t$.
• Reward Model: The expected reward is linear: $R_t = \phi(X_t, a_t)^\top \gamma_{0,t} + \epsilon_t$, where $\phi$ is a known feature map and $\gamma_{0,t} \in \mathbb{R}^p$ is an unknown, time-varying linear parameter.
• Challenge: In non-stationary settings, the parameter $\gamma_{0,t}$ changes over time. Standard approaches (e.g., sliding windows, discounting, or periodic restarts) discard or down-weight historical data to adapt to changes. This effectively shrinks the learning horizon, leading to higher regret, especially when the environment changes rapidly.
• Goal: To leverage historical data that remains relevant despite non-stationarity, thereby reducing the effective dimensionality of the learning problem and improving regret bounds.

2. Core Methodology: Invariant Subspace Decomposition (ISD)

The authors propose that the time-varying parameter $\gamma_{0,t}$ can be decomposed into two orthogonal components based on an Invariant Subspace Decomposition (ISD) framework:
$$\gamma_{0,t} = \beta_{inv} + \delta_{t}^{res}$$

• Invariant Component ($\beta_{inv}$): A static parameter lying in a subspace $S_{inv}$ of dimension $p_{inv}$. This component remains constant across all time steps.
• Residual Component ($\delta_{t}^{res}$): A time-varying parameter lying in the orthogonal residual subspace $S_{res}$ of dimension $p_{res} = p - p_{inv}$. This component captures the non-stationary changes.
• Key Assumption: The features projected onto $S_{inv}$ and $S_{res}$ are uncorrelated. This allows the two components to be estimated separately without bias.

The Algorithm: ISD-linUCB
The proposed algorithm, ISD-linUCB, operates in two phases:

1. Offline Phase: Using a large dataset of $T_0$ historical observations (collected by a policy exploring the space), the algorithm estimates the invariant subspace $S_{inv}$ (and its basis $U^{inv}$) and the residual subspace $S_{res}$ (basis $U^{res}$). It then estimates the invariant parameter $\beta_{inv}$ using all $T_0$ data points.
2. Online Phase: During the online horizon $T$:
   • The algorithm treats $\beta_{inv}$ as a known (or tightly bounded) quantity derived from the offline data.
   • It only performs exploration and adaptation for the residual component $\delta_{t}^{res}$ using the online data.
   • It constructs a confidence set for the total parameter $\gamma_t$ by combining the confidence set for the invariant part (derived offline) and the residual part (derived online).
   • It selects actions using an Upper Confidence Bound (UCB) strategy based on this decomposed parameter.

3. Key Contributions

1. Novel Algorithm (ISD-linUCB): A practical algorithm that reduces online adaptation to a lower-dimensional residual subspace by exploiting invariances learned from offline data.
2. Theoretical Regret Bounds:
   • Oracle Case: If the subspaces and $\beta_{inv}$ are known, the regret scales as $\tilde{O}(p_{res}\sqrt{T})$, rather than the standard $\tilde{O}(p\sqrt{T})$.
   • Estimated Case: When subspaces and $\beta_{inv}$ are estimated from $T_0$ offline samples, the regret bound is:
     $$\tilde{O}\left(\sqrt{T} \left( p_{res} + \sqrt{\frac{T}{T_0}} \left( \sqrt{p_{inv}} + \sqrt{\frac{1}{\lambda_0}} \right) \right) \right)$$
     where $\lambda_0$ relates to the minimum eigenvalue of the offline covariance matrix.
   • Implication: If $T_0 \gg T$ (sufficient historical data), the term dependent on $p_{inv}$ becomes negligible, and the regret is dominated by the residual dimension $p_{res}$.
3. Lower Bound Analysis: The authors prove a lower bound of $\Omega(p_{res}\sqrt{T})$ for this setting, demonstrating that their upper bound is optimal up to logarithmic factors when invariance is present.

4. Experimental Results

The paper validates the theory through simulations:

• Oracle Subspaces: When $S_{inv}$ and $S_{res}$ are known, the cumulative regret of ISD-linUCB scales linearly with $p_{res}$ and is independent of the total dimension $p$. In contrast, standard LinUCB scales linearly with $p$.
• Estimated Subspaces: As the amount of offline data ($T_0$) increases, the performance of ISD-linUCB (with estimated subspaces) converges to the performance of the oracle version.
• Comparison: ISD-linUCB significantly outperforms standard LinUCB and other non-stationary baselines (like sliding window or discounting methods) in environments where a significant portion of the reward model is invariant, particularly when $T_0$ is large.

5. Significance and Impact

• Efficiency in Non-Stationarity: The work challenges the paradigm that non-stationary environments require discarding historical data. Instead, it shows that if parts of the environment are stationary (invariant), that data can be fully utilized to reduce the effective dimensionality of the learning problem.
• Dimensionality Reduction: By shifting the complexity of the regret bound from the full dimension $p$ to the residual dimension $p_{res}$, the algorithm offers substantial gains in high-dimensional settings where only a few dimensions change over time.
• Practical Applicability: The approach is particularly relevant for real-world applications (e.g., recommendation systems, dynamic pricing) where user preferences or market conditions may shift (non-stationary) but underlying structural relationships (invariant) persist. The method provides a theoretical justification for leveraging large offline datasets to accelerate online learning in changing environments.

In summary, this paper introduces a principled framework for invariance-based learning in bandits, demonstrating that decomposing the reward model into stationary and non-stationary components allows for optimal adaptation with significantly reduced regret compared to existing non-stationary bandit algorithms.