Abstract
We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown regression parameter is allowed to vary in time. To address this problem, we propose D-LinUCB, a novel optimistic algorithm based on discounted linear regression, where exponential weights are used to smoothly forget the past. This involves studying the deviations of the sequential weighted least-squares estimator under generic assumptions. As a by-product, we obtain novel deviation results that can be used beyond non-stationary environments. We provide theoretical guarantees on the behavior of D-LinUCB in both slowly-varying and abruptly-changing environments. We obtain an upper bound on the dynamic regret that is of order $d^{2/3} B_T^{1/3} T^{2/3}$, where $B_T$ is a measure of non-stationarity ($d$ and $T$ being, respectively, dimension and horizon). This rate is known to be optimal. We also illustrate the empirical performance of D-LinUCB and compare it with recently proposed alternatives in simulated environments.
Introduction
In dynamic fields such as online recommendation and digital advertising, the underlying data distributions are rarely static. User preferences drift over time, and external events can cause abrupt shifts in content relevance. Standard stochastic linear bandit models, which assume a stationary environment, often fail to adapt to these changes. This paper introduces D-LinUCB, an algorithm designed to handle non-stationarity by employing a discounted least-squares approach to prioritize recent observations over obsolete history.
The Non-Stationary Linear Bandit Problem
The authors address the Stochastic Linear Bandit problem where the hidden preference vector $\theta_t$ evolves over time. In this setting, an agent selects an action $a_t$ from a set of context vectors and receives a reward $r_t = \langle a_t, \theta_t \rangle + \eta_t$. The goal is to minimize dynamic regret against a sequence of optimal actions.
Existing approaches typically rely on sliding windows or change-point detection. Sliding windows require significant memory to store past interactions, while change-point detection algorithms often struggle with slow, continuous drifts that do not trigger a discrete "reset" of the model.
The D-LinUCB Algorithm
The core innovation is the Discounted Linear Upper Confidence Bound (D-LinUCB) algorithm. Instead of a hard window cutoff, D-LinUCB utilizes Weighted Least Squares with an exponential discount factor $\gamma \in (0, 1)$. This allows the model to smoothly "forget" older data, which acts as noise or "poison" in a changing environment.
Key technical features include:
- Recursive Implementation: The discounted estimator can be updated incrementally, requiring only the current state to be stored rather than the full history.
- Novel Concentration Inequalities: The authors developed a new maximal deviation inequality for sequential weighted least-squares to construct a confidence ellipsoid that contains the moving parameter with high probability.
- Scale Invariance: The regularization parameter is designed to ensure stability regardless of the weight scaling.
Theoretical and Empirical Results
The performance of D-LinUCB is analyzed using a "variation budget" $B_T = \sum_{t=1}^{T-1} \|\theta_{t+1} - \theta_t\|_2$. The authors prove that D-LinUCB achieves a dynamic regret of $\tilde{O}(d^{2/3} B_T^{1/3} T^{2/3})$, matching the theoretical lower bound for this problem class.
Empirical evaluations were conducted on synthetic environments and real-world Criteo display advertising data. In scenarios with abrupt changes, D-LinUCB demonstrated significantly faster recovery than stationary baselines.
Key Insights
- Robustness to Drift: D-LinUCB tracks moving targets smoothly, whereas change-point detection methods (like dLinUCB) may fail to trigger during gradual shifts.
- Efficiency: D-LinUCB matches the performance of Sliding Window (SW-LinUCB) methods while offering superior memory efficiency due to its recursive nature.
- Adaptability: On the Criteo dataset, D-LinUCB quickly reconciled new data after a simulated "preference flip," while standard LinUCB remained biased by its now-obsolete history.
Conclusion
D-LinUCB provides a theoretically optimal and computationally efficient solution for linear bandits in non-stationary worlds. While the optimal discount factor $\gamma$ currently depends on the variation budget $B_T$, future work aims to develop parameter-free versions of the algorithm that can adapt the discount factor automatically.
Summary updated