Non-Stationary Bandits · Vaibhav on HTTPS

Corresponds to Lattimore & Szepesvári, Chapter 31.

Motivation: the benchmark must move with the world

IntuitionWhy a fixed comparator fails

Standard regret compares with the best fixed arm in hindsight. When the environment changes, every fixed arm can be bad, so a small regret against them guarantees nothing. As the Exp3 notes warned, the adversarial framework is not a model of non-stationarity: its regret has stationarity built in. The fix is to enlarge the competitor class to sequences that are allowed to switch arms, and to ask for algorithms that track the best arm.

ExampleA vacuous guarantee

Two arms with losses $y_{t1} = \mathbb I\{t\le n/2\}$ and $y_{t2} = \mathbb I\{t > n/2\}$ . Every fixed arm loses $n/2$ , so Exp3’s guarantee becomes $\mathbb E\sum_ty_{tA_t}\le\frac n2 + \sqrt{2nk\log k}$ . A coin flip achieves $n/2$ . Yet the sequence is perfectly regular: play arm 2, then arm 1, for total loss near 0, i.e. negative standard regret. A meaningful benchmark should demand this.

Setting	Comparator	Best achievable	Key algorithm
Adversarial, at most $m-1$ switches	best switching sequence	$\tilde\Theta(\sqrt{nmk})$	Exp4 (statistics); clipped mirror descent (efficient)
Stochastic, at most $m-1$ abrupt changes	per-round best arm	no gain over adversarial: $O(\log n)$ stationary ⇒ $\Omega(n/\log n)$	forgetting (discounting, sliding windows), adaptive multi-scale exploration
Stochastic, total variation $\le V$	per-round best arm	$\tilde\Theta((Vk)^{1/3}n^{2/3})$	Besbes et al.; adaptive variants

Adversarial bandits

DefinitionSwitching sequences and tracking regret

Let $\Gamma_{nm}\subseteq[k]^n$ be the action sequences with at most $m-1$ changes: $\sum_{t=1}^{n-1}\mathbb I\{a_t\ne a_{t+1}\}\le m-1$ . The non-stationary (tracking) regret is

$R_{nm} = \mathbb E\Big[\sum_{t=1}^ny_{tA_t}\Big] - \min_{a\in\Gamma_{nm}}\sum_{t=1}^ny_{ta_t}$

$R_{n1}$ is ordinary regret. In the example above, $R_{n2} = \mathbb E\sum_ty_{tA_t}$ , so small tracking regret requires detecting the change quickly.

Component	Detail
Competitor	the best piecewise-constant arm sequence with at most $m$ pieces
Parameter	$m$ , a budget on the comparator’s switches (the learner may switch freely)
Trade-off	larger $m$ means a more meaningful benchmark and more regret

Exp4 over switching sequences

TheoremTracking regret via Exp4 (Exercise 31.1)

Make each sequence $a\in\Gamma_{nm}$ an expert recommending $a_t$ in round $t$ . Theorem 18.1 gives

$R_{nm}\le\sqrt{2nk\log\lvert\Gamma_{nm}\rvert}\quad(31.1),\qquad R_{nm} = O\Big(\sqrt{nmk\log\frac{kn}m}\Big)\quad(31.2)$

using $\lvert\Gamma_{nm}\rvert\le k^m\sum_{i<m}\binom{n-1}i$ and $(m/n)^m\Phi_m(n)\le e^m$ , so $\log\lvert\Gamma_{nm}\rvert = O(m\log\frac{kn}m)$ . Choose the change points, then the arm in each piece.

TheoremLower bound (Exercise 31.2)

For $n\ge mk$ , every policy has $R_{nm}\ge c\sqrt{nmk}$ on some adversarial bandit. Run $m$ independent hard instances in sequence, each with horizon $n/m$ ; each costs $\Omega(\sqrt{nk/m})$ (Chapter 15), for a total of $\Omega(\sqrt{nmk})$ .

ImportantNot knowing when changes happen costs almost nothing

The lower bound holds even for policies told the change points, and Exp4 matches it up to logs without that knowledge. The catch is computation: naive Exp4 is linear in $\lvert\Gamma_{nm}\rvert$ , which is astronomically large.

Online stochastic mirror descent on the clipped simplex

WarningPlain Exp3 has linear tracking regret (Exercise 31.3)

In the two-arm example, after $n/2$ rounds in which arm 2 is better, arm 1’s probability is roughly $e^{-\eta n/2}$ , which is astronomically small at the standard learning rate. When the losses switch, Exp3 almost never samples arm 1, so it gets almost no evidence that arm 1 has improved and stays stuck: $R_{n2}\ge cn$ . Over-commitment prevents discovering change points.

AlgorithmExp3 restricted to the clipped simplex

Let $\mathcal A = \mathcal P_{k-1}\cap[\alpha,1]^k$ with $\alpha\in[0,1/k]$ , $F$ the unnormalised negentropy, and $P_1$ uniform. Each round, sample $A_t\sim P_t$ , form $\hat Y_{ti} = \mathbb I\{A_t = i\}y_{ti}/P_{ti}$ , and update

$P_{t+1} = \arg\min_{p\in\mathcal A}\eta\langle p,\hat Y_t\rangle + D_F(p,P_t) \tag{31.3}$

via the two-step process: $\tilde P_{t+1,i} = P_{ti}e^{-\eta\hat Y_{ti}}$ (exponential-weights step), then KL-project onto the clipped simplex. The projection floors small coordinates at $\alpha$ and rescales the rest (Exercise 26.12).

TheoremTheorem 31.1 — Tracking regret of clipped mirror descent

$R_{nm}\le\alpha n(k-1) + \frac{m\log(1/\alpha)}\eta + \frac{\eta nk}2$

With $\alpha = \sqrt{m/(nk)}$ and $\eta = \sqrt{2m\log(1/\alpha)/(nk)}$ :

$R_{nm}\le\sqrt{mnk\log(nk/m)} + \sqrt{mnk}$

ProofRestart the mirror descent analysis at each change point

Step 1: Split at the comparator’s switches. Let the optimal $a^*\in\Gamma_{nm}$ be constant (equal to $a_i^*$ ) on blocks $[t_i, t_{i+1})$ , with $t_1 = 1$ and $t_{m+1} = n+1$ . Then $R_{nm} = \sum_i\mathbb E\big[\mathbb E[\sum_{t\in\text{block }i}(y_{tA_t} - y_{ta_i^*})\mid P_{t_i}]\big]$ .

Step 2: Pay for the clipping. $e_{a_i^*}\notin\mathcal A$ , but the clipped point (weight $1 - (k-1)\alpha$ on $a_i^*$ , $\alpha$ elsewhere) loses at most $\alpha(k-1)$ per round, since $y\in[0,1]^k$ . So each block costs at most $\alpha(\text{length})(k-1) + \mathbb E\max_{p\in\mathcal A}\sum_t\langle P_t - p,\hat Y_t\rangle$ .

Step 3: Mirror descent from an arbitrary start. By the general-start bound (28.11) and the Exp3 stability computation (Exercise 28.10), each block costs at most $\frac{D(p,P_{t_i})}\eta + \frac{\eta k\cdot\text{length}}2$ .

Step 4: Clipping bounds the restart cost. $P_{t_i}\in\mathcal A$ has every coordinate at least $\alpha$ , so $D(p,P_{t_i}) = \sum_jp_j\log\frac{p_j}{P_{t_ij}}\le\log\frac1\alpha$ . Summing over the $m$ blocks gives the bound.

∎

IntuitionClipping as built-in forgetting

Without clipping, the “distance” $D(e_a,P_t)$ from the current distribution to a newly optimal arm can grow without bound, which is Exp3’s failure. Flooring every probability at $\alpha$ caps it at $\log(1/\alpha)$ , so the algorithm can always restart cheaply at each change point. It pays $\alpha(k-1)$ per round for the forced exploration, and $\alpha\approx\sqrt{m/(nk)}$ balances the two costs. This is the mirror-descent form of the fixed-share idea (Herbster–Warmuth 1998).

WarningNot knowing $m$

With $m$ unknown, take $\alpha = \sqrt{1/(nk)}$ and $\eta = \sqrt{\log(1/\alpha)/(nk)}$ . The bound degrades by a factor of about $\sqrt m$ , to $O(m\sqrt{nk\log(nk)})$ . No adversarial algorithm achieving $O(\sqrt{mkn\log n})$ without knowing $m$ is known.

RemarkRelated algorithms

Exp3.S (Auer et al. 2002) is an efficient implementation of Exp4 over switching sequences, made tractable by a careful initialisation (György et al. 2019). Exp3.P, suitably tuned, also achieves Exp3.S-type bounds (Audibert–Bubeck 2010), presumably Exp3-IX too. György–Szepesvári (2016) made the clipping explicit and bounded regret by the cumulative change of loss vectors, which distinguishes abrupt from gradual change.

ExampleExperiment (Exercise 31.4)

With $k = 2$ , $n = 1000$ and a single switch at $n/2$ : Exp3 and Exp3-IX react slowly at standard learning rates, while clipped mirror descent tracks the switch. Compare several learning rates for each.

Stochastic bandits

DefinitionPiecewise-stationary Gaussian bandit

Each arm has a mean function $\mu_i : [n]\to\mathbb R$ , and $X_t = \mu_{A_t}(t) + \eta_t$ with $\eta_t$ i.i.d. $\mathcal N(0,1)$ . The regret is against the per-round optimum:

$R_n(\mu) = \sum_{t=1}^n\mu^*(t) - \mathbb E\sum_{t=1}^n\mu_{A_t}(t), \qquad\mu^*(t) = \max_i\mu_i(t)$

with the mean vector changing at most $m-1$ times: $\sum_t\max_i\mathbb I\{\mu_i(t)\ne\mu_i(t+1)\}\le m-1$ .

FormulaWith known change points

Restart UCB on each block. Concavity of $\log$ ( $\sum_j\log n_j\le m\log(n/m)$ ) gives

$R_n(\mu) = O\Big(m + \frac{mk}{\Delta_{\min}}\log\frac nm\Big) \tag{31.4}$

with $\Delta_{\min}$ the smallest gap over all blocks: logarithmic and non-vacuous. In the adversarial case, not knowing the change points cost almost nothing. Does the same hold here? No.

TheoremTheorem 31.2 — Good stationary regret forces bad non-stationary regret

Let $k = 2$ , $\Delta\in(0,1)$ , and $\mu$ stationary with $\mu_1 - \mu_2 = \Delta$ . If a policy has $R_n(\mu) = o(n)$ , then for all large $n$ there is a non-stationary $\mu'$ with at most two change points and gaps $\min_t\lvert\mu_1'(t) - \mu_2'(t)\rvert\ge\Delta$ such that

$R_n(\mu')\ge\frac n{22\,R_n(\mu)}$

ImportantConsequences

$R_n(\mu) = O(\log n)$ on a stationary instance implies worst-case regret $\Omega(n/\log n)$ against two changes.
$R_n(\mu) = o(\sqrt n)$ on some non-trivial stationary instance implies $\omega(\sqrt n)$ minimax regret on non-stationary ones.
So there is no hope of beating Exp4-type $\sqrt n$ rates in the stochastic switching setting, even asymptotically. To guard against abrupt changes, a policy must keep re-checking suboptimal arms, which is incompatible with logarithmic regret.

ProofHide a change in the block where arm 2 is sampled least

Step 1: A neglected block. Split $[n]$ into $L$ equal blocks $S_j$ . By pigeonhole, some block has $\mathbb E\sum_{t\in S_j}\mathbb I\{A_t = 2\}\le\mathbb E[T_2(n)]/L$ (31.5).

Step 2: The alternative. $\mu'$ equals $\mu$ except that on $S_j$ , arm 2 gets $\mu_2 + \varepsilon$ with $\varepsilon = \sqrt{2L/\mathbb E[T_2(n)]}$ . This is two change points. With $L = \lceil2\Delta^2\mathbb E[T_2(n)]\rceil$ , $\varepsilon\ge2\Delta$ , so arm 2 is optimal on $S_j$ by $\varepsilon - \Delta\ge\Delta$ .

Step 3: Indistinguishable. Only arm-2 samples inside $S_j$ carry information, so by the divergence decomposition $D(\mathbb P,\mathbb P')\le\frac{\mathbb E[T_2(n)]}L\cdot\frac{\varepsilon^2}2 = 1$ . By Bretagnolle–Huber, $\mathbb P\big(\sum_{S_j}\mathbb I\{A_t = 2\}\ge\frac{\lvert S_j\rvert}2\big) + \mathbb P'\big(\sum_{S_j}\mathbb I\{A_t = 2\} < \frac{\lvert S_j\rvert}2\big)\ge\frac1{2e}$ .

Step 4: Under $\mu$ this event is rare. By Markov and (31.5), $\mathbb P(\cdots\ge\lvert S_j\rvert/2)\le\frac{2\mathbb E[T_2(n)]}{L\lvert S_j\rvert}\le\frac1{\Delta^2\lvert S_j\rvert}$ .

Step 5: So under $\mu'$ , arm 1 is overplayed in $S_j$ . Each such play costs at least $\varepsilon/2\ge\Delta$ :

$R_n(\mu')\ge\Big(\frac1{2e} - \frac1{\Delta^2\lvert S_j\rvert}\Big)\frac{\varepsilon\lvert S_j\rvert}4\ge\frac{\lvert S_j\rvert\Delta}{4e} - \frac1{2\Delta}$

Step 6: Translate. $R_n(\mu) = \Delta\mathbb E[T_2(n)]$ , so $L\approx2\Delta R_n(\mu)$ and $\lvert S_j\rvert\approx n/L$ , giving $\frac{\lvert S_j\rvert\Delta}{4e}\approx\frac n{8eR_n(\mu)}$ . Since $R_n(\mu) = o(n)$ , the $-\frac1{2\Delta}$ term is negligible, and $\frac1{22} < \frac1{8e}$ .

∎

IntuitionThe neglected block is where the trap is set

A low-regret stationary policy samples arm 2 rarely, so some stretch of time gets very few arm-2 samples. An adversary can secretly make arm 2 the best there, by just enough that those few samples can’t reveal it. The rarer the sampling (the smaller $R_n(\mu)$ ), the longer the stretch and the larger the loss.

RemarkWhat stochasticity still buys

Adversarial algorithms can’t exploit distributional structure: Gaussian rewards are unbounded, and Bernoulli rewards have small variance near the boundary. And in the stochastic setting, algorithms that adapt to an unknown number of switches now exist (see Note 2 below). In the adversarial setting none is known.

Notes

RemarkMake it stationary with context (Note 1)

Gym ads do better in January than in July. A time-oblivious bandit sees this as non-stationary, but adding time of year to the context turns it into a stationary contextual bandit. Consider this before reaching for non-stationary algorithms.

AlgorithmForgetting: discounted UCB and sliding-window UCB (Note 2)

Discounted UCB with $\gamma\in(0,1)$ :

$\hat\mu_i^\gamma(t) = \sum_{s\le t}\gamma^{t-s}\mathbb I\{A_s = i\}X_s, \qquad T_i^\gamma(t) = \sum_{s\le t}\gamma^{t-s}\mathbb I\{A_s = i\}$ $A_t = \arg\max_i\ \hat\mu_i^\gamma(t-1) + \sqrt{\frac\alpha{T_i^\gamma(t-1)}\log\sum_jT_j^\gamma(t-1)}$

(in the book’s formula $\hat\mu^\gamma$ is a discounted sum; it should be normalised by $T_i^\gamma$ to estimate a mean).

Sliding-window UCB with window $\tau$ : use only the last $\tau$ rounds, $\hat\mu_i^\tau$ and $T_i^\tau$ , with bonus $\sqrt{\frac\alpha{T_i^\tau(t-1)}\log(t\wedge\tau)}$ .

Tuning problem: no fixed $\gamma$ or $\tau$ gives $O(\sqrt{n\log n})$ minimax regret. They are empirically useful when the stochastic assumption holds (Kocsis–Szepesvári 2006; analysed by Garivier–Moulines 2011). Extensions exist for linear bandits and MDPs.

RemarkAdapting to unknown switches

Auer et al. (2018, 2019) and Chen et al. (2019) match optimally tuned adversarial rates, about $\sqrt{mkn\log n}$ , without knowing $m$ , in the stochastic setting (first for $k = 2$ , then $k$ arms and contextual). The key idea is multi-scale explicit exploration: randomly scheduled checks of varying durations, so that changes of any size are detected at proportionate cost.

DefinitionSlow drift and variation budgets (Notes 3–4)

Brownian drift: $\mu_i(t)$ follows reflected Brownian motion. The best arm changes with constant probability each round, so regret is necessarily linear. The question becomes its slope in terms of volatility and interval size (Slivkins–Upfal 2008).
Total variation: with $V_n = \sum_t\lVert\mu_t - \mu_{t+1}\rVert_\infty\le V$ and $V\in[1/k, n/k]$ , some policy achieves $R_n\le C(Vk\log k)^{1/3}n^{2/3} \tag{31.6}$ This is nearly minimax optimal (Besbes et al. 2014), and achievable without knowing $V$ by the adaptive algorithms above.

DerivationThe variation-budget lower bound

Split $[n]$ into $m$ blocks. In each, all arms are equal except a randomly placed best arm, better by $\Delta = c\sqrt{mk/n}$ . Each block costs $\Omega(\sqrt{kn/m})$ , for a total of $\Omega(\sqrt{kmn})$ . Each block switch moves the means by at most $2\Delta$ , so $V_n\le2cm^{3/2}\sqrt{k/n}$ . Setting this equal to $V$ gives $m\approx(V^2n/k)^{1/3}$ , and the regret $\sqrt{kmn}\approx(Vk)^{1/3}n^{2/3}$ .

RemarkHistory

Gittins index: each arm is a Markov chain that evolves only when played, treated as Bayesian optimisation (Chapter 35). Restless bandits (Whittle 1988): every chain evolves every round, but only the played arm is observed. This is hard, with few positive results and a challenging frequentist analysis (Ortner et al. 2012). The adversarial tracking ideas descend from fixed share (Herbster–Warmuth 1998, 2001). Contextual non-stationary bandits: Luo et al. (2018), Chen et al. (2019).

Quick reference

Object	Statement	Note
Vacuous example	$\mathbb E\sum y_{tA_t}\le\frac n2 + \sqrt{2nk\log k}$	a fixed comparator is too weak
Switching class	$\Gamma_{nm}$ : at most $m-1$ changes	$R_{n1}$ = ordinary regret
Tracking regret	$\mathbb E\sum y_{tA_t} - \min_{a\in\Gamma_{nm}}\sum y_{ta_t}$
Exp4 over sequences	$\sqrt{2nk\log\lvert\Gamma_{nm}\rvert} = O(\sqrt{nmk\log(kn/m)})$	infeasible to compute
Lower bound	$\Omega(\sqrt{nmk})$	even with known change points
Clipped MD	$\alpha n(k-1) + \frac{m\log(1/\alpha)}\eta + \frac{\eta nk}2$	$\mathcal P_{k-1}\cap[\alpha,1]^k$
Tuned	$\sqrt{mnk\log(nk/m)} + \sqrt{mnk}$	$\alpha = \sqrt{m/nk}$ ; unknown $m$ costs $\sqrt m$
Plain Exp3	$R_{n2}\ge cn$	over-commitment
Known changes (stochastic)	$O(m + \frac{mk}{\Delta_{\min}}\log\frac nm)$	restart UCB
Garivier–Moulines	$R_n(\mu') \ge n/(22R_n(\mu))$ with two changes	$\log n$ stationary ⇒ $\Omega(n/\log n)$
Forgetting	discounted / sliding-window UCB	no minimax-optimal tuning
Variation budget	$(Vk\log k)^{1/3}n^{2/3}$	adaptive versions exist

Facts to keep to hand

Non-stationarity needs a moving benchmark. Tracking regret against switching sequences restores meaning. Its price is $\sqrt m$ : about $\sqrt{nmk}$ , nearly the same as if the change points were known.
Statistically, Exp4 solves it; computationally, clipping does. Mirror descent on a floored simplex keeps every arm at probability at least $\alpha$ , so each restart costs at most $\log(1/\alpha)$ . Plain Exp3 commits too hard and never notices changes.
In stochastic switching environments, low stationary regret is a liability. A policy that samples a suboptimal arm only $O(\log n)$ times leaves long stretches unchecked, where a hidden change costs $\Omega(n/\log n)$ . Guarding against change requires continual exploration.
Forgetting is the stochastic toolkit, and the newest methods adapt. Discounting and sliding windows work in practice but can’t be tuned minimax. Multi-scale randomised exploration adapts to unknown switch counts and variation budgets. Sometimes the right move is to model the cause of change as context.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 31
Garivier & Moulines, “On upper-confidence bound policies for switching bandit problems” (2011)
Besbes, Gur & Zeevi, “Stochastic multi-armed-bandit problem with non-stationary rewards” (2014)