Non-Stationary Bandits

Sliding window UCB, discounted UCB, change-point detection, EXP3, REXP3

Standard UCB and Thompson Sampling are built for stationary reward distributions. They accumulate observations indefinitely — N_a(t) grows monotonically. An arm with millions of accumulated observations has a confidence interval so tight it never loses the argmax, even after its reward has collapsed.

The algorithm stays frozen on a historically dominant arm long after its true mean has dropped. The failure mode is slow: it takes O(N_a) new observations to substantially move the empirical mean — that is months of data for a heavily exploited arm. The right production strategy combines two mechanisms: CUSUM-based change detection for abrupt shifts (triggers an immediate statistics reset when a change is detected) and sliding window or discounted UCB for gradual drift (continuously forgets stale observations so the mean tracks recent reality). Predictable seasonality is not non-stationarity — weekly cycles belong in contextual features, not in a forgetting mechanism.

Key points

• Standard UCB/TS failure after a change point: UCB1 and standard TS accumulate all historical observations monotonically. For a previously dominant arm whose reward drops, N_a is large (tight confidence interval), the UCB stays high (empirical mean barely moves), and the algorithm continues exploiting it. The empirical mean only shifts substantially after O(N_a) new observations — for an arm with 50,000 observations, it takes thousands of post-change pulls to notice. Regret grows linearly after the change.
• Sliding window UCB (SW-UCB): maintain only the last W observations per arm. UCB $index = μ̂_a(W) + B√(ln t / min(N_a, W)). Old observations e$ xpire automatically — after a change, the window fills with new observations in W rounds. Optimal window W ≈ √(T/K) for infrequent abrupt changes; regret = O(√(KT)). The tradeoff: a small W adapts quickly but has high variance; a large W is stable but slow to adapt.
• **Discounted UCB (D-UCB): weight observations exponentially: $μ̂_a = Σ γ^(t−s) r_s / Σ γ^(t−s) where γ ∈ (0,1).** Effective me$ mory length ≈ 1/(1−γ) rounds. Smoother than SW-UCB — old observations don't vanish abruptly but fade gradually. Behaves like an exponential moving average of rewards. γ = 0.99 gives effective memory of 100 rounds; γ = 0.999 gives 1000 rounds.
• Change-point detection + reset: run CUSUM or Page-Hinkley on each arm's reward stream. CUSUM maintains a cumulative sum statistic and signals a change when it exceeds a threshold; Page-Hinkley is the same idea applied to a running mean-deviation statistic instead of raw reward. On detection, reset that arm's statistics (N_a = 0, μ̂_a = flat prior). More principled than windowing — only forgets when change is actually detected, not continuously. Requires tuning the detection threshold: low threshold → fast detection but frequent false alarms; high threshold → fewer false alarms but slow detection.
• EXP3 (Exponential-weight algorithm for Exploration and Exploitation): the adversarial bandit algorithm. Maintains weights w_a per arm. Selects arm with probability proportional to w_a plus uniform exploration floor γ/K. Importance-weights the observed reward: x̂_{a,t} = r_t / p_{a_t,t}. Updates: w_{a_t} ← w_{a_t} × exp(γ x̂_{a_t,t} / K). Achieves E[R_T] ≤ O(√(KT ln K)) against any adversarial sequence with no distributional assumptions.
• EXP3 importance-weighted reward: x̂_{a,t} = r_t / p_{a,t} × 1(a_t = a). Unbiased: E[x̂_{a,t}] = p_{a,t} × μ_a / p_{a,t} = μ_a. The importance weighting compensates for selection probability — rare arms have their observed rewards scaled up to correct for how rarely they are pulled. Variance is O(K/γ) per arm per round — high, especially with small γ. This is the cost of the adversarial guarantee: no distributional structure means you must pay for all information gathering.
• REXP3 (Restarting EXP3): for non-stationary adversarial settings with Υ change points, run EXP3 in epochs of length T/Υ, restarting at each epoch. If Υ is unknown, use a doubling schedule: epochs of length 1, 2, 4,... The cost of not knowing Υ is only logarithmic in T — the doubling trick loses at most a log-T factor relative to knowing Υ in advance.
• Seasonality is not non-stationarity. Weekly cycles and hour-of-day patterns are predictable and recurring. Sliding window and discounted UCB handle the weekend-weekday difference by forgetting weekday observations on weekends — discarding useful data. The correct treatment: include day_of_week and hour_of_day as context features in a contextual bandit. The model learns that preferences differ predictably by time. Non-stationary algorithms are for genuine concept drift and external shocks — not for predictable patterns.
• EXP3 vs UCB for moderately non-stationary settings: EXP3 achieves O(√(KT ln K)) against adversarial sequences but O(√(KT ln K)) is worse than UCB's O(log T) for stationary settings. In practice, most production problems have stochastic structure with occasional abrupt changes — neither purely stationary nor fully adversarial. Sliding window or discounted UCB typically outperforms EXP3 because they exploit stochastic structure when present. EXP3 is the right choice when the adversary is strategic or the reward distribution is fundamentally unpredictable.

Recap

• Failure mode: standard UCB/TS freezes on a once-dominant arm — large N_a means the mean barely moves after a change.
• Detection is slow: O(N_a) post-change pulls needed — thousands of pulls for an arm with 50K observations.
• Sliding window UCB: keep last W observations; window fills with fresh data in W rounds; W ≈ √(T/K).
• Discounted UCB: $μ̂_a = Σ γ^(t−s) r_s / Σ γ^(t−s)$; effective memory ≈ 1/(1−γ); smoother than SW-UCB.
• CUSUM change detection + reset: forgets only when a change is actually detected, not continuously.
• EXP3 / REXP3: adversarial O(√(KT ln K)) via importance-weighted rewards; restart in epochs for Υ change points.
• NOT this: predictable seasonality isn't drift — put day_of_week / hour_of_day in context features, don't forget the data.

Check your understanding