📊 statistics

Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits

This paper introduces Weighted Sequential Bayesian (WSB) inference for non-stationary linear contextual bandits, a framework that replaces point estimates with dynamic posteriors to reduce over-conservatism and achieve state-of-the-art regret guarantees through new WSB-based algorithms and a simplified martingale concentration proof.

Original authors: Nicklas Werge, Yi-Shan Wu, Abdullah Akgül, Melih Kandemir

Published 2026-08-12

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicklas Werge, Yi-Shan Wu, Abdullah Akgül, Melih Kandemir

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a spaceship navigating a galaxy where the rules of physics change every few hours. Sometimes gravity pulls up, sometimes down, and sometimes it vanishes entirely. To survive, you need a navigation computer that learns from your past jumps but doesn't get stuck in old habits. This is the world of Contextual Bandits, a branch of artificial intelligence that helps computers make smart decisions when the "best" choice keeps changing. Think of it like a robot trying to guess which flavor of ice cream a customer wants. If the customer's taste changes every day, the robot can't just remember what they liked last week; it has to weigh recent history heavily and forget the distant past.

To do this, the robot usually relies on two main strategies. The first is a Frequentist approach, which is like a strict accountant. It crunches the numbers to find the single "best guess" for the current situation. The second is a Bayesian approach, which is more like a curious explorer. Instead of just one guess, it keeps a whole map of possibilities, understanding that it might be wrong and knowing exactly how uncertain it is. The problem is that in a changing galaxy, the strict accountant is fast but blind to its own uncertainty, while the explorer is smart but often too slow to compute its map. This paper steps into that gap, trying to give the explorer the speed of the accountant without losing its curiosity.

The Problem: The "Forgetting" Robot

In the real world, things rarely stay the same. A recommendation system for movies, a medical trial for a new drug, or a self-driving car all face non-stationarity—a fancy way of saying the rules of the game are shifting. If a robot tries to learn from data that is ten years old, it might be making a mistake because the world has changed.

To handle this, scientists have tried three main tricks:

Restarting: Every so often, the robot wipes its memory and starts over. This is safe but wasteful; it throws away good lessons just because time passed.
Sliding Windows: The robot only looks at the last few days of data. This is better, but it's like looking at the world through a narrow tunnel; you might miss a slow, important trend.
Weighted Learning: The robot remembers everything but gives "older" memories less weight, like a fading echo. This is the smoothest approach, but it's been hard to make it work perfectly with the "explorer" style of learning.

The Old Way: The "Fake" Explorer

For a long time, the most popular method for these changing worlds was a technique called Weighted Regularized Least-Squares (WRLS). It's the "strict accountant." It calculates a single best guess for the current situation and moves on. It's fast and efficient.

But here's the catch: WRLS doesn't naturally know how unsure it is. To make the robot explore (try new things to learn more), researchers had to hack the system. They took the accountant's single best guess and artificially added "fake noise" to it to pretend it was an explorer. It was like taking a precise map and shaking it around just to see what happens. It worked okay, but it wasn't a true reflection of how the robot should learn.

The New Way: The "Real" Explorer (WSB)

The authors of this paper, Nicklas Werge and his team, decided to stop faking it. They introduced a new method called Weighted Sequential Bayesian (WSB) inference.

Instead of forcing a single guess to act like an explorer, they built a system that is an explorer from the ground up.

How it works: Imagine the robot has a "belief" about the world. Every time it gets new data, it updates this belief. In a changing world, older beliefs fade away (they get weighted less), but the robot never stops having a full "map" of possibilities.
The Magic Trick: The authors found that this "real" Bayesian map is just as fast to calculate as the old "fake" accountant method. They managed to keep the speed of the accountant while keeping the natural uncertainty of the explorer.
The Dynamic Penalty: One of the biggest hurdles in these problems is dealing with the robot's initial guess (its "prior"). If the robot starts with a bad guess, it can be slow to correct itself. The old methods treated this initial mistake as a fixed, unchangeable penalty. The new WSB method treats it as a dynamic penalty. As the robot gathers more data and its map gets sharper, the penalty for the initial mistake shrinks automatically. It's like forgiving yourself for a bad guess once you've learned enough to know you were wrong.

What They Found

The team didn't just invent a new idea; they proved it works mathematically and tested it in simulations.

Better Math: They showed that their new method, WSB, provides the same level of safety (mathematical guarantees) as the best existing methods. In fact, they improved the math for "randomized" exploration (where the robot tries things randomly to learn) by a significant margin, reducing the error rate related to the complexity of the problem.
Three New Algorithms: They built three specific tools based on this idea:
- WSB-LinUCB: A deterministic explorer that picks the best option based on its confidence.
- WSB-RandLinUCB: A randomized explorer that adds a little bit of luck to its choices.
- WSB-LinTS: A "Thompson Sampling" explorer that picks a random scenario from its belief map and acts on it.
The Results: When they ran simulations with 4,000 rounds of decision-making (like a long game), the new methods consistently outperformed the old ones.
- In a scenario where the world changed abruptly (sudden jumps), the new randomized methods reduced the "regret" (the score of mistakes) significantly. For example, in a test with 32 dimensions (a complex problem), the old method made about 503 mistakes, while the new WSB-RandLinUCB made only 474.
- In a scenario where the world changed slowly (drifting), the improvement was even more dramatic. The old method made 435 mistakes, while the new one made just 405.
- Most importantly, the new method was less conservative. Because it didn't rely on a fixed "worst-case" penalty for its initial guess, it was willing to take smarter risks earlier on, learning faster.

The "Ablation" Check

The authors also tested what happens if the robot starts with a really bad guess (a "misspecified prior"). They found that if the initial guess is just a little off, the system handles it well. But if the guess is wildly wrong (like thinking the gravity is 100 times stronger than it is), the robot struggles at first. This confirms that while the new method is robust, it still needs a reasonable starting point to work its magic.

Why It Matters

This paper doesn't just offer a tiny tweak; it offers a cleaner, more honest way to teach robots how to learn in a changing world. By ditching the "fake noise" and using a true Bayesian approach that is just as fast as the old methods, they've shown that you don't have to choose between being fast and being smart. The robot can be both.

The authors also provided a simplified proof for a complex mathematical tool used by many researchers, making the whole field a bit easier to understand. While the current method still requires knowing how much the world might change (a "budget" of change), the framework is flexible enough that future versions could learn that budget automatically. For now, it's a solid step toward AI that adapts to our messy, shifting reality without needing to hit the reset button.

Technical Summary: Weighted Sequential Bayesian Inference for Non-Stationary Linear Contextual Bandits

Problem Formulation

The paper addresses the non-stationary linear contextual bandit problem. In this setting, a learner interacts with an environment over $T$ rounds. At each round $t$ , the learner observes a set of context-dependent actions $X_t \subseteq \mathbb{R}^d$ , selects an action $x_t$ , and receives a noisy reward $r_t = \langle x_t, \theta^*_t \rangle + \epsilon_t$ . The core challenge is that the reward parameter $\theta^*_t \in \mathbb{R}^d$ is unknown and time-varying. The degree of non-stationarity is quantified by a total variation budget $B_T = \sum_{t=1}^{T-1} \|\theta^*_t - \theta^*_{t+1}\|_2$ . The objective is to minimize dynamic regret, defined as the cumulative difference between the reward of the optimal action and the chosen action.

Existing efficient solutions typically rely on the Weighted Regularized Least-Squares (WRLS) estimator. While WRLS offers $O(d^2)$ computational complexity via recursive updates, it provides only point estimates. To perform randomized exploration (e.g., Thompson Sampling or Randomized UCB), previous methods must construct "surrogate" posterior distributions by injecting artificial Gaussian noise scaled by frequentist covariance matrices. This approach lacks a native Bayesian grounding and often relies on complex analytical constructs like local norms.

Methodology: Weighted Sequential Bayesian (WSB) Inference

The authors propose Weighted Sequential Bayesian (WSB) inference to establish a principled Bayesian framework for non-stationary linear bandits that retains the computational efficiency of WRLS.

Generalized Posterior Construction:
Instead of a point estimate, WSB maintains a sequence of Gaussian posteriors $\rho_t(\theta) = \mathcal{N}(\theta | \mu_t, \Sigma_t)$ over the time-varying parameters. The method employs a sequence of weights $\{w_{s,t}\}$ (typically exponential decay $w_{s,t} = \gamma^{t-s}$ ) to down-weight past observations. The posterior mean $\mu_t$ and inverse covariance $\Sigma_t^{-1}$ are updated recursively:
$\Sigma_t^{-1} = \gamma \Sigma_{t-1}^{-1} + \sigma^{-2} x_t x_t^\top + (1-\gamma)\Sigma_0^{-1}$
$\mu_t = \Sigma_t \left( \gamma \Sigma_{t-1}^{-1} \mu_{t-1} + \sigma^{-2} x_t r_t + (1-\gamma)\Sigma_0^{-1} \mu_0 \right)$
Under an uninformative prior, the WSB mean $\mu_t$ algebraically coincides with the WRLS point estimate $\hat{\theta}_t$ , but WSB natively provides the full posterior covariance $\Sigma_t$ required for uncertainty quantification.
Concentration Analysis and Dynamic Prior Penalty:
The authors derive a time-uniform confidence bound for the WSB posterior. The estimation error $\|\mu_{t-1} - \theta^*_t\|$ is decomposed into three components:
- Drift Term ( $\alpha^{WSB}_t$ ): Captures the bias induced by parameter changes.
- Noise Term ( $\beta^{WSB}_t$ ): Captures stochastic noise from rewards.
- Dynamic Prior Term ( $\Pi_t$ ): A novel term representing the influence of the initial prior. Unlike WRLS analyses where the initialization penalty is bounded by a fixed worst-case constant ( $\sqrt{\lambda}S$ ), the WSB penalty $\Pi_t$ is evaluated through the time-varying posterior covariance $\Sigma_t$ . As $\Sigma_t$ contracts over time, $\Pi_t$ decays, leading to a data-dependent, tighter bound.
Simplified Martingale Proof:
To establish the concentration bounds, the paper provides a simplified proof for the time-uniform concentration of vector-valued martingales. By leveraging Ville's inequality for non-negative super-martingales, the authors bypass the complex stopping-time constructions traditionally used in bandit literature, offering a cleaner derivation for self-normalized bounds.

Key Contributions

The paper makes three primary contributions:

WSB Framework: Introduction of a parametric Bayesian inference method for non-stationary linear bandits that matches the $O(d^2)$ efficiency of WRLS while providing a native posterior distribution for randomized exploration.
Refined Regret Guarantees: Establishment of frequentist regret bounds for three WSB-based algorithms: WSB-LinUCB, WSB-RandLinUCB, and WSB-LinTS. By extending refined drift analysis (previously applied only to UCB) to randomized strategies, the authors achieve regret bounds of $\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ . This improves upon the state-of-the-art $d^{7/8}$ dependence found in earlier randomized baselines (e.g., D-RandLinUCB, D-LinTS).
Dynamic Prior Penalty: Demonstration that the Bayesian formulation isolates the prior influence into a dynamic term $\Pi_t$ that decreases as the posterior covariance shrinks. This reduces over-conservatism in arm selection compared to methods using fixed initialization penalties.

Experimental Results

The authors evaluate the proposed algorithms on synthetic non-stationary scenarios involving both abrupt changes and gradual drifts.

Deterministic vs. Randomized: Randomized exploration strategies (WSB-RandLinUCB and WSB-LinTS) consistently outperform deterministic UCB-based methods across all dimensions and scenarios.
Comparison to Baselines:
- WSB-RandLinUCB achieves lower cumulative regret than its frequentist counterpart, D-RandLinUCB, across all tested dimensions ( $d=2$ to $32$).
- WSB-LinTS substantially outperforms D-LinTS.
- In deterministic settings, WSB-LinUCB performs competitively with LB-WeightUCB (the state-of-the-art WRLS UCB), though it does not consistently surpass D-LinUCB (which uses a more complex local norm) in higher dimensions.
Ablation Study: Experiments on prior misspecification show that while the algorithms are robust to moderate prior errors, severe misspecification (where the prior mean is far from the true parameter scale) can degrade performance, highlighting the importance of choosing a prior scale compatible with the parameter bound.

Significance and Claims

The paper claims that WSB offers a more principled foundation for uncertainty quantification in non-stationary bandits. By avoiding artificial surrogate distributions and local norms, WSB-based algorithms achieve:

Theoretical Optimality: Regret bounds that match the state-of-the-art for smooth, weighted strategies ( $\tilde{O}(d^{3/4} B_T^{1/4} T^{3/4})$ ), improving the dimension dependence over previous randomized methods.
Practical Efficiency: Retention of $O(d^2)$ computational complexity, avoiding the $O(t^3)$ cost of non-parametric Gaussian Process approaches.
Reduced Conservatism: The dynamic prior penalty allows for less conservative exploration as data accumulates, leading to empirically superior performance in randomized settings.

The authors note that while their bounds are competitive, they remain slightly above the theoretical lower bound of $\Omega(d^{2/3} B_T^{1/3} T^{2/3})$ , a gap attributed to the challenge of achieving minimax optimality using only smooth, continuous adaptation without periodic resets. However, the WSB framework is presented as a highly practical alternative that balances theoretical rigor with continuous adaptation capabilities.