Source-linked AI summary
Learning to Optimize under Non-Stationarity
Wang Chi Cheung, David Simchi-Levi, Ruihao Zhu
TL;DR
The paper addresses linear bandits whose environments drift over time while the variation budget may be unknown. It combines sliding-window stochastic estimation with adaptive bandit tuning, obtaining near-optimal dynamic-regret guarantees for known and unknown budgets.
Problem
Non-stationary linear bandits require dynamic decisions under changing parameters, but existing methods largely assume the variation budget B_T is known.
Method
The paper develops a sliding-window regularized least-squares estimator and SW-UCB, then uses BOB to tune SW-UCB when B_T is unknown.
Results
The tuned SW-UCB algorithm has optimal dynamic regret up to logarithmic factors, while BOB achieves the best dependence on T among the stated unknown-budget results.
Takeaways & Limitations
Sliding-window estimation adapts to parameter changes, and bandit-over-bandit tuning removes the need to know the variation budget in advance.
Takeaways & Limitations
The model restricts parameter sequences to those satisfying the bounded ℓ2 variation constraint and allows them to be chosen by an oblivious adversary.
Abstract
from arXiv · showhide
We introduce algorithms that achieve state-of-the-art \emph{dynamic regret} bounds for non-stationary linear stochastic bandit setting. It captures natural applications such as dynamic pricing and ads allocation in a changing environment. We show how the difficulty posed by the non-stationarity can be overcome by a novel marriage between stochastic and adversarial bandits learning algorithms. Defining $d,B_T,$ and $T$ as the problem dimension, the \emph{variation budget}, and the total time horizon, respectively, our main contributions are the tuned Sliding Window UCB (\texttt{SW-UCB}) algorithm with optimal $\widetilde{O}(d^{2/3}(B_T+1)^{1/3}T^{2/3})$ dynamic regret, and the tuning free bandit-over-bandit (\texttt{BOB}) framework built on top of the \texttt{SW-UCB} algorithm with best $\widetilde{O}(d^{2/3}(B_T+1)^{1/4}T^{3/4})$ dynamic regret.
1 Introduction
The paper studies linear bandits in drifting environments, where stochastic noise coexists with adversarially changing parameters and the variation budget may be unknown. It introduces SW-UCB and BOB algorithms targeting near-optimal dynamic regret.
- Motivation: Drifting environments combine adversarial parameter changes with mean-zero random noise bounded by a variation budget B_T.The learner must estimate the current environment while hedging against future changes.
- Motivation: Unknown B_T remains a challenging problem because many existing non-stationary bandit methods assume the budget is known in advance.Prior efforts without this knowledge either lack guarantees or obtain sub-optimal dynamic regret bounds.
- Contributions: The paper develops tuned SW-UCB for known B_T and a BOB framework that adaptively tunes SW-UCB when B_T is unknown.The contributions combine stochastic-bandit estimation with adversarial-bandit adaptation.
- Related work: Existing K-armed drifting-bandit work obtains ˜O((K B_T)^(1/3) T^(2/3)) dynamic regret when B_T is known.Related results also study unknown budgets, contextual bandits, dynamic pricing, and full-feedback settings.
- Related work: Sliding Window UCB was previously proposed for K-armed switching environments but had only been analyzed there.The paper extends the sliding-window idea to the drifting linear-bandit setting.
2 Problem Formulation
The problem is a linear bandit with bounded actions and time-varying parameters, where rewards contain sub-Gaussian noise and parameter drift is constrained by an ℓ2 variation budget. The learner minimizes dynamic regret against the sequence of per-round optimal actions.
- 2.1 Notation: The paper defines notation for column vectors, indexed ranges, Euclidean norms, matrix norms, minima, maxima, and logarithm-suppressed growth.For positive definite A, the matrix norm is induced by x^⊤Ax; ˜O notation suppresses logarithmic factors.
- 2.2 Learning Model: At each round, an obliviously selected decision set D_t is presented and the learner chooses an action X_t from it.The decision sets are fixed independently of the learner’s actions and may be determined before the protocol starts.
- 2.2 Learning Model: The observed reward is Y_t = ⟨X_t, θ_t⟩ + η_t, with unknown parameter θ_t and i.i.d. mean-zero sub-Gaussian noise η_t.The noise has variance proxy R and satisfies the stated sub-Gaussian moment condition.
- 2.2 Learning Model: Actions and parameters are bounded by constants L and S, and rewards are normalized so that |⟨X, θ_t⟩| ≤ 1.These bounds hold for every admissible action and every round.
- 2.2 Learning Model: The drifting environment constrains the sum of consecutive parameter changes by the variation budget B_T = Θ(T^ρ), with ρ ∈ (0, 1).This replaces the stationary assumption that the reward function remains fixed over time.
- 2.2 Learning Model: The parameter sequence may be chosen adversarially by an oblivious adversary, subject to the variation constraint.Θ(B_T) denotes the set of all such obliviously selected sequences.
- 2.2 Learning Model: The learner minimizes worst-case cumulative dynamic regret against the per-round action maximizing ⟨x, θ_t⟩ over D_t.The comparator can change from round to round as θ_t changes.
3 Lower Bound
The lower-bound analysis characterizes the best achievable dynamic regret by constructing a drifting linear-bandit instance from successive stationary blocks. The resulting bound follows from balancing block difficulty with the variation-budget constraint.
- Lower bound: The paper first provides a lower bound on dynamic regret to characterize the best achievable performance.The bound applies to any policy for horizons satisfying T ≥ d.
- Lower-bound construction: The hard instance partitions the horizon into ⌈T/H⌉ blocks, each containing a new stationary linear-bandit instance.The final block may contain fewer than H rounds.
- Lower-bound construction: Each block selects parameters from a signed coordinate set, and nature chooses the block parameter based only on the learner’s policy.This construction yields worst-case regret of order Ω(d√H) per block.
- Lower-bound calculation: Across at least ⌊T/H⌋ blocks, the total regret scales as Ω(dT/√H).The blockwise lower bound accumulates over the horizon.
4 Sliding Window Regularized Least Squares Estimator
The estimator uses only recent observations in a regularized least-squares window to track changing parameters. Its error separates non-stationarity from random noise, and the analysis shows adaptation under parameter drift.
- Estimator: The sliding window regularized least-squares estimator is the key tool for estimating the unknown time-varying parameters.It uses observations from a window of length w immediately preceding the current round.
- Adaptation: Despite non-stationarity, the estimator’s estimation error can gracefully adapt to parameter changes.The result supports using recent data rather than all historical observations.
- Estimator: At round t, the estimator solves a ridge-regression problem over observations from (1 ∨ (t−w)) through t−1.The regularization parameter is λ, and the associated design matrix is V_{t−1}.
- Error decomposition: The estimation error decomposes into a drift term caused by parameter changes and a random-noise term.This decomposition enables separate control of non-stationarity and stochastic error.
- Assumption: The analysis assumes decision sets align with an orthonormal basis, so each action is a scalar multiple of one basis vector.This includes multi-armed bandits while allowing decision sets with arbitrarily many actions.
- Analysis: The noise contribution is bounded using sub-Gaussian concentration and matrix-norm analysis.The proof combines an existing concentration lemma with a deviation bound for latent expected rewards.
5 Sliding Window-Upper Confidence Bound (SW-UCB) Algorithm: A First Order Optimal Strategy
SW-UCB applies optimism over a sliding window to linear bandits in drifting environments, with window tuning that yields first-order-optimal dynamic-regret dependence on the variation budget when known or unknown.
- Known variation budget: Known B_T: choosing w = ⌊d^2/3T^2/3B_T^-2/3⌋ gives dynamic regret eO(d^2/3B_T^1/3T^2/3).This tuned choice matches the stated optimal dependence up to logarithmic factors.
- Unknown variation budget: Unknown B_T: choosing w = ⌊(dT)^2/3⌋ gives dynamic regret eO(d^2/3(B_T+1)^1/3T^2/3).The resulting dependence on T remains first-order optimal even without prior knowledge of the variation budget.
- Design and operation: SW-UCB selects each action by maximizing an upper confidence bound computed from recent observations in a sliding window.The algorithm estimates the current parameter, solves the corresponding UCB optimization problem, and then observes the reward.
- Regret analysis: The regret analysis decomposes per-round regret into non-stationarity and estimation-error terms, then bounds the resulting cumulative expression.The proof uses an upper bound by the chosen action’s UCB and separates the two contributions through supporting lemmas.
- Regret analysis: The SW-UCB proof uses the Sherman–Morrison formula because forgetting prevents direct application of stationary matrix-telescoping arguments.The first separated term is controlled by a telescoping sum, while the estimation-related term requires the new matrix argument.
6 Bandit-over-Bandit (BOB) Algorithm: Automatically Adapting to the Unknown Variation Budget
BOB adapts SW-UCB to an unknown variation budget by treating candidate window lengths as bandit choices, selecting among them across blocks and balancing tuning loss against optimization regret.
- Motivation: When B_T is unknown and large, a fixed untuned SW-UCB window can yield a bound linear in T, motivating adaptive window selection.The BOB framework is designed for the general setting where changes in θ_t do not follow a learnable stochastic process.
- Algorithm design: BOB divides the horizon into blocks and uses EXP3 to select a candidate SW-UCB window length for each block.The selected window is used by SW-UCB throughout that block, and block rewards update the EXP3 distribution.
- Algorithm design: BOB’s regret decomposes into the regret of an optimally tuned window plus the loss from learning that window.This separates SW-UCB performance from the additional cost of bandit-based window selection.
- Parameter trade-offs: The block length H trades off EXP3’s window-identification regret against the accuracy with which the selected window approximates the optimal window.The candidate set J must be both small enough for learning and dense enough to cover plausible optimal windows.
- Regret guarantee: Unknown B_T: BOB with SW-UCB achieves dynamic regret eO(d^2/3(B_T+1)^1/4T^3/4), which remains sublinear when B_T = Θ(T^ρ) for any ρ ∈ (0,1).The framework’s parameters are designed without depending on B_T.
7 Numerical Experiments
The experiments compare SW-UCB, modified EXP3.S, and BOB under constant and time-dependent variation budgets. SW-UCB substantially outperforms modified EXP3.S in the constant-budget setting, while BOB has lower regret than SW-UCB when the budget grows with time.
- Experimental Setup: The experiments vary T from 3 × 10^4 to 2.4 × 10^5 in a 2-armed bandit setting.The synthetic setup uses sinusoidal parameters with total variation O(B_T) and i.i.d. normal noise with R = 0.1.
- Unknown Time-Dependent Variation Budget: B_T = T^1/3: BOB’s regret is much smaller than SW-UCB’s regret.Modified EXP3.S does not apply in this time-dependent-budget setting; Figure 2 compares SW-UCB and BOB.
A Proof of Theorem 1
The proof constructs a blockwise non-stationary environment from decoupled linear-bandit instances. Controlling block length through the variation budget yields the lower bound Ω(d^2/3 B_T^1/3 T^2/3).
- Stationary Lower Bound: Ω(d√T_0) is the worst-case regret for a stationary linear bandit with unknown parameter θ.This stationary lower bound is applied within the independent blocks of the non-stationary construction.
- Block Construction: The lower-bound construction partitions the horizon into blocks whose parameters remain fixed within each block and vary across blocks.Each block is a decoupled linear-bandit instance, so knowledge from previous blocks cannot help decisions in the current block.
- Theorem 1: Ω(d^2/3 B_T^1/3 T^2/3) is the resulting lower bound for non-stationary linear bandits.Because blocks are completely decoupled, their regrets accumulate without information passing across blocks.
- Variation Control: The block length H must balance larger regret from shorter blocks against violating the variation budget.The proof therefore bounds total variation across consecutive blocks to determine how small H can be.
B Proof of Lemma 1
The lemma proof establishes a sequence of matrix inequalities using eigenvalue characterizations, triangle inequality, Cauchy-related bounds, and a basis decomposition. The final step exploits that two matrices are diagonal.
- Matrix Characterization: λ_max(M) is represented as the maximum quadratic form over the unit Euclidean ball.The proof uses λ_max(M) = max_{z ∈ B(1)} z^⊤Mz and the definition of V_s^-1.
- Intermediate Inequalities: Equality (32) rewrites the same sum over pairs of indices, while inequality (33) follows from the triangle inequality.The indexed terms involve X_sX_s^⊤(θ_p − θ_{p+1}) over the relevant time range.
- Intermediate Inequalities: Inequality (34) applies a matrix quadratic-form bound to y = θ_p − θ_{p+1}.The argument uses the condition λ_max(M) ≥ 0 for the relevant matrix M.
- Final Step: The final inequality uses a basis decomposition of each X_s and the fact that A_1 and A_2 are diagonal.This completes the lemma after expressing X_s through the corresponding basis vectors.
C Proof of Theorem 2
The proof establishes a uniform bound over time and feasible actions. It derives the needed inequalities using the triangle inequality, Cauchy–Schwarz, and earlier lemmas.
- Proof of Theorem 2: For every δ ∈ [0,1], time t, and action x ∈ D_t, the proof establishes the target bound.The subsequent inequalities use the triangle inequality, Cauchy–Schwarz, and Lemmas 1 and 2.
D Proof of Theorem 3
The proof bounds SW-UCB’s dynamic regret by controlling estimation, noise, and variation terms over sliding windows. A technical Sherman–Morrison argument supplies the key bound unavailable from prior analysis.
- SW-UCB’s regret is upper bounded by summing the per-round regret inequality across the full horizon.
- The proof partitions the horizon into consecutive blocks of length w and applies Cauchy–Schwarz to control the resulting terms.
- A prior sliding-window quantity cannot use the earlier analysis because accumulated variation terms break its key proof equation.
- A technical lemma based on the Sherman–Morrison formula provides the missing control for the sliding-window analysis.The lemma applies to positive definite matrices and vectors, supporting the matrix bounds used in the proof.
- The remaining steps combine intermediate inequalities, reward bounds, sub-Gaussian noise control, and a union bound to conclude the proof.