Tracking Most Significant Shifts in Nonparametric Contextual Bandits
Authors: Joe Suk
Samory Kpotufe
Venue: NeurIPS 2023 poster (2023)
Keywords: multi-armed bandits
non-stationary
contextual bandits
nonparametric
Lipschitz
TL;DR: Optimal and adaptive dynamic regret bounds for non-stationary nonparametric contextual bandits in terms of new, tighter non-stationarity measure .

Abstract: We study nonparametric contextual bandits where Lipschitz mean reward functions may change over time.
We first establish the minimax dynamic regret rate in this less understood setting in terms of number of changes $L$ and total-variation $V$, both capturing all changes in distribution over context space, and argue that state-of-the-art procedures are suboptimal in this setting.

Next, we tend to the question of an _adaptivity_ for this setting, i.e. achieving the minimax rate without knowledge of $L$ or $V$. Quite importantly, we posit that the bandit  problem, viewed locally at a given context $X_t$, should not be affected by reward changes in other parts of context space $\cal X$. We therefore propose a notion of _change_, which we term _experienced significant shifts_, that better accounts for locality, and thus counts considerably less changes than $L$ and $V$. Furthermore, similar to recent work on non-stationary MAB (Suk & Kpotufe, 2022), _experienced significant shifts_ only count the most _significant_ changes in mean rewards, e.g., severe best-arm changes relevant to observed contexts.

Our main result is to show that this more tolerant notion of change can in fact be adapted to.

Tracking Most Significant Shifts in Nonparametric Contextual Bandits
Joe Suk Columbia University joe. suk@columbi a. edu
Samory Kpotufe
Columbia University samory@columbia edu
Abstract
We study nonparametric contextual bandits where Lipschitz mean reward functions may change over time. We first establish the minimax dynamic regret rate in this less understood setting in terms number of changes L and total-variation V, both capturing all changes in distribution over context space, and argue that state-of-the -ic--of-the-rrr art procedures are suboptimal in this setting.
Next, tend to the question of an adaptivity for this setting, i.e. achieving the minimax rate without knowledge of L or V. Quite importantly, we posit that the bandit problem, viewed locally at given context X,, should not be affected by reward changes in other parts of context space X. We therefore propose notion of change, which term experienced significant shifts, that better accounts for locality, and thus counts considerably less changes than L and V. Furthermore, similar recent work non-stationary MAB [Suk and Kpotufe, 2022], experienced significant shifts only count the most significant changes mean rewards, e.g., severe best-arm changes relevant observed contexts.
Our main result is to show that this more tolerant notion of change can in fact be adapted to.
Introduction
Contextual bandits model sequential decision making problems where the reward of chosen action depends on an observed context X; at time f, e.g., a consumer's profile, a medical patient's 's history. The goal maximize the total rewards over time of chosen actions, informed by seen contexts. As such, one suitable measure of performance is that of dynamic regret, which compares earned varying oracle maximizing mean rewards X,. While it often assumed in the bulk of works in this setting that rewards distributions remain stationary over time, it is understood that in practice, environmental changes induce nontrivial changes rewards.
rewards
In fact, the problem of non-stationary environments has received a surge of attention in the simpler non-contextual Aaand-irm-aandits Bandits (MAB) setting, while the more challenging contextual case remains ill-understood. In particular in the contextual case, some recent works [Wu et al., 2018, Luo et al., 2018, Chen et al., 2019, Wei and Luo, 2021] consider parametric settings, i.e. where reward functions belong to fixed parametric family, and show that one may achieve rates adaptive to an unknown number of L of shifts in rewards to notion of total- nall-variation V. both acccounting for all changes over time and context space. Instead here, we consider a much larger class of reward functions, namely Lipschitz rewards, corresponding the natural assumption that closeby contexts have similar rewards even as reward distributions change.
As first result for this nonparametric setting, we establish some minimax lower-bounde as baseline terms of either L V, and argue that state-of-the -fttrrrrttttttt procedures for the parametric case-extended to the class of Lipschitz. functions do not achieve these baselines.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We then turn attention to whether such baselines may be achieved adaptively, i.e., without knowledge of L or V. The answer as we show is affirmative, and more importantly, some much weaker notions of change may be adapted to; for intuition, while 7. or V accounts for any change at any time over the context space (say X), it may be that all changes are relegated to parts of the space irrelevant to observed contexts X, at the time they are played. For instance, suppose at time t, we observe X; = z0. then it may not make sense to count changes that happen at some other 21 far from Zo, or changes that happened at To itself but far back in time.
We therefore propose a new parameterization of change, termed experienced significant shifts that better accounts for the locality of changes in time and space, and as such may register much less changes than either L or V. As sanity check, we show that an oracle policy which restarts only experienced significant shifts can attain enhanced regret rates in terms of the number T. = L(X1, Xx) of such experienced shifts (Proposition 2), a rate always worse that the baseline we first established in terms of L and V.
Our main result is to show that experienced significant shifts can be adapted to (Theorem 3), i.e., with no prior knowledge of such shifts. Importantly, the result holds in both stochastic environments, and in (oblivious) adversarial ones with no change to our notion, algorithmic approach, nor analysis. Furthermore, similar to recent advances in the non-contextual case [Abbasi- Yadkori et al., 2022, Suk and Kpotufe, 2022], an experienced shift is only triggered under severe changes such as changes of best arms locally at context X,, An added difficulty in the contextual case is that we cannot hope to observe rewards for given arm (action) repeatedly at X; as the context may only appear once, and have to rely on carefuly chosen nearby points to identify unknown shifts in reward at Xt.
1.1 Other Related Work
Nonparametric Contextual Bandits. The stationary bandits with covariates (where rewards and contexts follow a joint distribution) was first introduced in a one-armed bandit problem [Woodroofe, 1979, Sarkar, 1991], with the nonparametric model first studied by Yang et al. [2002]. Minimax regret rates, based on a margin condition, were first established for the two-armed bandit in Rigollet and Zeevi [2010] and generalized to any finite number of arms in Perchet and Rigollet [2013], with further insights thereafter [Qian and Yang, 20,6a,,, Reeve et al., 2018, Guan and Jiang, 2018, Hu et al., 2020, Arya and Yang, 2020, Suk and Kpotufe, 2021, Gur et al., 2022, Cai et al., 2022]. However, the mentioned works all assume stationary distribution of rewards over contexts. Blanchard et al. [2023] studies non-stationary nonparametric contextual bandits, but in the much-differen context of universal learming, concerning when sublinear regret is achievable asymptotically. Lipschitz contextual bandits also appears as part of studies on broader infinite- armed settings [Lu et al., 2009, Krishnamurthy et al., 2019]. Related, Slivkins [2014] allows for non-stationary (i.c., obliviously adversarial) environments, but only studies regret to the (per-context) best arm in hindsight. Realizable contextual bandits posits that the regression function capturing mean rewards in contexts lies in some known class of regressors F, over which one can do empirical risk minimization [Foster et al., 2018, Foster and Rakhlin, 2020, Simchi-Levi and Xu, 2021]. While this setting recovers Lipschitz contextual bandits, the only applicable non-stationary guarantee to our knowledge is Wei and Luo [2021], which yields suboptimal dynamic regret (see Table 1).
Non-Stationary Bandits and RL. In the simpler non-contextual bandits, changing reward dis- tributions (a.k.a. switching bandits) was introduced in Garivier and Moulines [201]] 1] and further explored with various assumptions and formulations [Karnin and Anava, 2016, Allesiardo et al., 2017, Liu al., 2018, Wei and Srivatsva, 2018, Besbes et al., 2019, Cao et al., 2019, Mukherjee and Maillard, 2019, Besson et al., 2022]. While these earlier works focused on algorithmic design assuming knowledge of con-stationarity, such a strong assumption was removed via the adaptive procedures of Auer et al. [2019], Chen et al. [2019]. In followup works, Abbasi-Yadkori Yadkori et al. [2022], Suk and Kpotufe [2022] show that tighter dynamic regret rates are possible, scaling only with severe changes in best arm. The ideas from non- -on-stationary MAB were extended to various contextual bandit settings by Wu et al. [2018] (for linear mean rewards in contexts), Luo al. [2018], Chen al. [2019] (for finite policy classes), and Wei and Luo [2021] (for realizable mean reward functions). There have also been extensions to various reinforcement learning setups [Jaksch et al., 2010, Gajane et al., 2018, Chi Cheung et al., 2019, Ortner et al., 2020, Fei et al., 2020, Cheung et al., 2020. Touati and Vincent, 2020, Domingues et al., 2021, Mao et al., 2021, Domingues et al., 2021, Wei and Luo, 2021, Zhou et al., 2022, Lykouris et al., 2021, Wei et al., 2022, Chen and Luo, 2022, Ding and Lavaci, 2023].

---

Of these works, only Domingues et al. [2021] can recover Lipschitz contextaul bandits, whereupon we find their dynamic regret bounds are suboptimal (see Table 1). Again, the typical aim of the aforementioned works on contextual bandits or RL is to minimize a notion of dynamic regret in terms of the number of changes total-variation V. As such, the guarantees of such works don't involve tighter notions of experienced non-stationarity, such as those studied in this work.
2
Problem Formulation
2.1 Contextual Bandits with Changing Rewards
Preliminaries. We assume a finite set of arms [K] = (1,2..., K}. Let Y, E [0, denote the vector of rewards for arms a E [K] round t E [T] (horizon T), and X, the observed context at that round, lying in X = [0, 1]6, which have joint distribution (X,, Y2) Dz. We let X, = {X,) bx,, Y, = {Ys}ase denote the observed contexts and (observed and unobserved) rewards from rounds
In our setting, oblivious adversary decides sequence of (independent) distributions on {(x,, Y.) before the first round.
Notation. The reward function St : X captures the mean rewards of arm o at context x and time L.
[0, 1]K is f2(x) = E| 20), [K], and
policy chooses actions each round I, based on observed contexts (up to round () and passed rewards, whereby at each round /. only the reward Y of the chosen action is revealed. Formally:
Definition (Policy). A policy æ = {mee hew is a random sequence of functions ne : X" x [K] x [0, 111-1 + [K]. A randomized policy πT maps distributions on [K), In abuse of notation. in the context of a sequence of observations till round t, we let nt E [K] denote the (possibly random) action chosen round
The performance of policy is evaluated using the dynamic regret, defined as follows:
Definition 2. Fix context sequence XT. Define the dynamic regret of policy n, as
T
RT
Σ
max f: - (X,)
aE[K]
So, we aim to minimize E[RT Xy)] where the expectation is over XT, Yr, and randomness in n. Notation. As much of our analysis focuses the gaps in mean rewards between arms observed contexts Xt, the following notation will serve useful. Let 8e(d', a) = fe' (X:) - (Xt) denote the relative gap of arms a to a' at round t at context Xt. Define the worst gap of arm as da(a) = max òz(a', a), corresponding and context X,- Thus, the dynamic regret can be written ExerT, Blōx(T:)). Additionally, we will occasionally talk about the gap functions in context E X. In an abuse of notation, let 54 ex) = ft (x) - (x) and 8f (x) = max 5f "a'." ((x). Generally, when a context x is not specified, as in the quantities 8e(a', a), 8e(a), it should be assumed that the context in question Xt-
the instantaneous regret of playing a at round
2.2 Nonparametric Setting
We assume, as in prior work on nonparametric contextual bandits [Rigollet and Zeevi, 2010, Perchet and Rigollet, 2013, Slivkins, 2014, Reeve al., 2018, Guan and Jiang, 2018, Suk and Kpotufe, 2021], that the reward function is I-Lipschitz.
Assumption (Lipschitz fo). For all rounds t E N, a E [K] and x x' E X.
(f) - f. & || 1o1
For ease of presentation, we assume the contextual marginal distribution px remains the same across rounds. Furthermore, we make a standard strong density assumption on μxx which is typical in this nonparametric setting [Audibert and Tsybakov, 2007, Perchet and Rigollet, 2013, Qian and Yang, b016a,b, Gur et al., 2022, Hu et al., 2020, Arya and Yang, 2020, Cai et al., 2022]. This holds, e.g. μx has continuous Lebesgue density [0, 1) and ensures good coverage of the context space.
3

---

Assumption 2 (Strong Density Condition), There exist Ca, ca > 0 s.t. Vl balls B C [0, 1| of diameter r E 10:
Ca.r" & 2 (x 2 Ca r
(2)
We can in fact relax Assumption 2 so that p (.) is changing in 1 and (2) is satisfied with different constants Ca.t Ca.- Our procedures in the end will not require knowledge of any Ca.,, Cd,t-
Remark
pxx()))
2.3 Model Selection
common algorithmic approach in nonparametric contextual bandits, starting from earlier work [Rigollet and Zeevi, 2010, Perchet and Rigollet, 2013], is to discretize partition the context space X' into bins where we can maintain local reward estimates. These hins have a natural hierarchical tree structure which we first elaborate.
Definition 3 (Partition Tree). Let R = (2- (0}), and let Tr, r R denote a regular partition of [0, 1]d into hypercubes (which refer to as bins) of side length (a.ka. bin size) r. We then define the dyadic tree T = {Tr TrER. i.e., a hierarchy of nested partitions of [0, 1] We will refer to the level r T as the collection of bins partition T,. The parent of a bin E T,, r < is the bin B' E TTrr containing B; child, ancestor and descendant relations follow naturally. We'll use (x) to refer the bin level r containing x, while rBB) is the side length of bin B.
Note that, while in the above definition, T has infinite levels r R, at any round t in procedure, we implicitly only operate on the subset of T containing data.
Key in securing good regret is then finding the optimal level r E R of discretization (balancing local regression bias and variance), which over T stationary rounds is known to be (K/T) x [Rigollet and Zeevi, 2010J. The intuition for this choice is that a bias of T sोạ is safe to pay for T rounds to 1+d maintain a minimax regret rate of T244 (see rates in Theorem 1). We introduce the following general notation, useful later in the non-stationary problem, for associating a level with an intervals rounds.
Notation 1 (Level). For n E N U (0), let rn be the largest 2m E R such that (K/n) х 2 2 m When I is an interval of rounds, we use Ti as shorthand for m/n, where [I] is the length of I.
We use Tm Tm (2) as shorthand denote (respectively) the tree T, of level r I'm and the (unique) bin at level Tm containing x.
3 Results Overview
3.1 Minimax Lower Bounds Under Global Shifts
Dynamic Regret Upper Bound 14d L/22. T244
ADA-ILTCB [Chen al., 2019]
A
V 1/3
3 .Tatd (0+4)3+00)
MASTER with FALCON [Wei and Luo, 2021]
L T
A
Vil
1/3
.T s4d 36-4)334
V.l 13 2td +0(1/a)
KeRNS [Domingues et al., 2021] (non-adaptive)
Minimax Lower-Bound
V
34d
Table Existing dynamic regret upper-bounds are suboptimal the Lipschitz setting.
As baseline, we start with some basic lower-bounds under the simplest parametrizations of changes in rewards which have appeared in the literature, namely global number of shifts, and total variation.
Definition (Global Number of Shifts), Let L =T 1(3x E X, a E [K] (f) + f (z)} be the number of global shifts, i.e., it county every change in mean-reward overtime and over X space,
Definition 5 (Total Variation). Define VT = ΣT [D, D.-1ll where recall D, E X x 00. 1] the joint distribution on context and rewards at time t.
We have the following initial result (for two-armed bandits) to serve as baseline for this study.

---

Theorem 1 (Dynamic Regret Lower Bound). Suppose there are K = 2 arms. For V.L E [0, T) let PVV, L, T) be the family of joint distributions D = HeT) with either total variation VT S V or
at most I. global shifts. Then, there exists constant > O such that for any policy n
sup (5[[((T,TT)) ( + DEP(V.L.T)
v vaia) ((L+1)ZITTZaa)
(3)
Remark 2. Note setting 0 in Theorem I recovers the minimax rate (VT + T2/3 V(L+1)+ + T for non-contextual bandits [Besbes et al., 2019].
Achievability of Minimax Lower-Bound (3). We are interested in whether the rates of (3) are achievable, with, or without knowledge of relevant parameters. First, we note that no existing algorithm currently guarantees rate that matches (3). See Table 1 for rate comparison (details for specializing to our setting found in Appendix A).
In particular, the prior adaptive works [Chen et al., 2019, Wei and Luo, 2021] both rely on the approach of randomly scheduling replays of stationary algorithms to detect unknown non-stationarity. However, the scheduling rate is designed to safeguard against the parametric v /LT A 1//33/2/3 regret rates and thus lead suboptimal dependence on L and Vr.
However, a simple back of the envelope calculation indicates that the rate (3) may be attainable, at least given some distributional knowledge: minimax-optima stationary procedure restarted at cach
shift will incur regret, over L equally spaced shifts, (L 11)
(L + 1) T
As it turns out as we will show in the next section, (3) is indeed attainable, even adaptively; in fact, this is shown via more optimistic problem parametrization as described next.
3.2 A New Problem Parametrization Experienced Significant Shifts.
As discussed in Subsection 2.3, typical approaches [Rigollet and Zeevi, 2010, Perchet and Rigollet, 2013] in our setting discretize the context space X' into bins, each of which is treated as an MAB instance. At a high level, our new measure of non- stationarity will trigger an experienced significant shift when the observed context X, arrives in bin B E T where there has been severe change in local best arm, w.r.. the observed data in that bin.
We first define a notion of significant regret for an arm a E [K] locally within a bin B E T. We say arm a incurs significant regret in bin B on interval I if:
5d)(a) 1(X, B} 2 VK nB)nn[] ((B))))rBBBn))))))) SET
where (T( = Eser 1(X, E [} and recall r rB) is the side length of bin B. The intuition for (+) is as follows: suppose that, over n separate rounds, we observe the same context X, = zig in bin B. Then, arm a would be considered unsafe in the local bandit problem at context zo if its regret exceeds VK-n n (i.e., the first term on the above R.H.S.), which is safe regret to pay for the non-contextual problem. Our broader notion (x) extends this over the bin B by also accounting for the bias (i.e., the second term the above R.H.S.) of observing X, near given context zo E B.
Remark 3 (Significant Regret Occurs at Critical Levels). [*()) holds for some bin B, then in fact it also roughly holds for the bin B', with B' n + O, at the critical level ruj (see Notation 1) w.r.t interval I (Lemma 9 and Proposition 15). Thus, it suffices to only check (*) for the critical levels rup which will be crucial in the analysis. Additionally, all such critical levels riz are above the optimal level T-zaa = for T stationary rounds (see Subsection 2.3). Thus, only (log(T)) levels play role in in checking (*) for all intervals of time I and bins B.
We then propose to record an experienced significant shift when we experience a context X., for which there is no safe arm to play in the sense of (x). The following notation will be useful.
For the sake of succinctly identifying regions of time with experienced significant shifts, we will conflate the closed, open, and clos-closed intervals of real numbers {a, b), (a, b). and (a, b). respectively, with the corresponding rounds contained therein, i.e. [a, b) = [a, b] n N.
Notation.
5

---

Definition 6. Fix the context sequence X1, X2,X2.... ,2....,Xxp
We say arm E [K] is unsafe at context E X on I if there exists bin B E T containing such that arm a incurs significant regret (*) in bin B on I.
We then have the following recursive definition:
Let To = 1. Define the (i + 1)-th experienced significant shift as the earliest time T(+1 E (Trs T] such that every arm a E [K] is unsafe X, on some interval 1 C. [Ti, T++1]. We refer to intervals (Te, Ti+1), i 2 0, as experienced significant phases. The unknown number of such shifts (by time T)
is denoted L, whereby (TE, Tit1), for T++1 = T + 1, is the last phase.
8. (z)
(1.((x))
11
12
f3
time t
Figure I: Shown are the gap functions (.) (K= 2 arms) in time f at two contexts x, x' assumed to be far apart. Suppose at times I and (a. observe context æ, and at times L2 and l4, we observe x'. Then, the change in best arm at context & is experienced. To contrast, the change in best arm at x' not experienced and hence counted in Definition 6.
Remark 4 (Definition 6 Only Counts Most Essential Changes). It's clear from Definition that only changes in mean rewards ft (x)) at experienced contexts X, counted, and only counted when experienced (see example in Figure l).
An experienced significant shift in fact implies a best-arm change X,, since, by smoothness (Assumption 1) and (+), we have
Σ (X.)) 1[x, B} ( e B)-r(B) _ B} 0.
Thus, i - L + 1, the global count of shifts, and can in fact be much smaller. On the other hand, so long as an experienced sigmificant shift does not occur, there will be arms safe to play at each context X,. Thus, procedures need not restart exploration long unsafe arms be quickly ruled out.
As warmup to presenting our main regret bounds and algorithms, we'll first consider an oracle procedure which knows the experienced significant shift times T₁. The strategy will be to mimic successive elimination algorithm, restarted each experienced significant shift.
Definition 7 (Oracle Procedure). For each round in phase [T,, T++1), define a good arm set Ge as the set of safe arms, i.e., arms which do not yet satisfy (*) in the hin T,(X,) at level r = T containing X,. Here, recall from Subsection 2.3 that 7::1--; is the oracle choice of level [T;, T()1)). Then, define an oracle procedure क: playing a uniformly random arm a E G, at time t.
phase
We then claim such oracle procedure attains an enhanced dynamic regret rate in terms of the significant shifts {Tr}; which recovers the minimax lower bound terms of global shifts and total variation Vy from before. The following proposition (see Appendix C for proof) captures this.
Proposition 2 (Sanity Check). We have the oracle procedure of Definition 7 satisfies with proba- bility at least 1/T2 w.r.t the randomness of XT: for some
i(xT)
Ex [R (T, XT) Xr] I C'log(K) log
Σ
(T44 - T, (XT)) 243 K zta.

---

By Jensen's inequality the above regret rate is most (f(XT) + 1) 7 & (I++1) .
At the same time, the rate also faster than v T'ad (see Corollary 5). Thus, the oracle procedure above attains the dynamic regret lower bound of Theorem 1. We next aim to design an algorithm which can attain same order regret without knowledge of 7; or L.
3.3
Main Results: Adaptive Upper-bounde
Our main result is a dynamic regret upper bound of similar order to Proposition 2 without knowledge of the environment, e.g, the significant shift times, or the number of significant phases. is stated for our algorithm CMETA (Algorithm 1 of Section 4), which, for simplicity. requires knowledge of the time horizon T (knowledge of T removable using doubling tricks).
Theorem 3. Let (T:(XT)) L+1 denote the unknown experienced significant shifts (Definition 6). We then have w.p. at least 1/T² w.r.t the randomness of for some C >
((xr)
(CME(AA) Xr] (olo((K) log (T)
Σ (n((T) T T=-1 K Kzta.
Corollary (Adapting to Experienced Significant Shifts). Under the conditions of Theorem 3, with probability at least 1/T w.F.t. the randomness in Xy:
(CMETA, Xx)) Xy| < C'log(K) log (T) (K- (i(XT) + 1)) T
Note, this is tighter than the earlier mentioned (L + 1) rate. The next corollary asserts that Theorem also recovers the optimal rate in terms total-variation Vr.
Corollary 5 (Adapting to Total Variation). Under the conditions of Theorem 3:
E (CMEEA, Xr)) S log(K) log2(T) (T KTta + (Vr K)sta 354
Remark 5. Our regret bound can straightforwardly be generalized min + 1) 2842 T 28 2 K æगι2, (Vr- K) K)zzīz 3T +1 +T K 2 for 3-Hölder reward functions with B s 1, provided
functionss the notion (+) is modified to take into account a bias (B)).
4 Algorithm
We take similar algorithmic approach to Suk and Kpotufe [2022], with several important modifi- cations for our setting. The high-level strategy is to schedule multiple copies of a base algorithm (Algorithm 2) random times and durations, in order to ensure updated and reliable estimation of the gaps in (+). This allows fast enough detection of unknown experienced significant shifts.
Overview of Algorithm Hierarchy. Our main algorithm CMETA (Algorithm 1) proceeds in episodes, each of which begins by playing according to an initially scheduled base algorithm of possible duration equal to the number of rounds left till T. Base algorithms occasionally activate their own base algorithms of varying durations (Line of Algorithm 2), called replays, according to a random schedule (set via variables (Zm,, D). We refer to the currently playing base algorithm as the active base algorithm. This induces a hierarchy of base algorithms, from parent to child instances.
Choice of Level. Focusing on a single base algorithm now, each Base- Alg manages its own dis- cretization of the context space X' = [0, 1jd, corresponding level r R. (see Definition 3). Within each bin B E T, at the level r, candidate arms, maintained in a set A(B), are evicted according to importance-weighted estimates (4) of local gaps.
As discussed Subsection 2.3, key algorithmic design is determining the optimal level E R. An immediate difficulty is that the oracle procedure's 's choice of level (see Definition 7) depends on the unknown significant phase length T т., To circumvent this, and as in previous works on Lipschitz contextual bandits [Perchet and Rigollet, 2013, Slivkins, 2014], we rely on an adaptive vire-varying choice of level r,, Specifically, each base algorithm uses the level Tt-tun based on the time clapsed since the time tuur it was first activated.
7

---

Managing Multiple Base Algorithms. Instances of Base-Alg and CMETA share information, in the form global variables as listed below:
All variables defined in CMETA: te, t, (Amsser(B)) {mm,)) (see Lines 3-6 of Algorithm 1).
The choice of arm played at each round I, along with observed rewards Y and the candidate arm set A which takes value the set A(B) of the active Base-Alg round and bin B (X,) used.
By sharing these global variables, any Base-Alg can trigger new episode: once an arm is evicted from a Base-Alg A [). it is also evicted from Amuster B)), which is essentially the candidate arm set for the current episode. A new episode triggered time when Amater (B) becomes empty for some bin B (necessarily currently experienced bin), i.e., there is no sufe arm left to play at context X, in the sense of Definition 6. Note that A( are local variables internal to each Base-Alg (the owner of which will be clear from context in usage).
To ensure consistent behavior while using time-varying choice of level, enforce further regularity in arm evictions across X: arms evicted from A(B') are also evicted from child bins C B' to ensure A(B) ABB).
Algorithm 1: Contextual Meta Deta-Eliminatiin while Tracking Arms (CMETA)
Input: horizon T, set of arms [K], tree T with levels E R.
Initialize: round count +- 1.
Episode Initialization (setting global variables):
3 ig + t.
Il te indicates start of (-th episode. I/ Initialize master candidate sets
For each bin B E T, set Amuster B) [K].
For each m 2, ....... ., [[og(T)) and tt + 1...., T:
Sample and store Zm,a ~ Bernoulli
(1 शोय
Z )
// Set replay schedule.
Run Base-Alg (4e, T + tz). if t < T then restart from Line 2 (i.e. start new episode).
Algorithm 2: Base-Alg (faan,, mo): Adaptively Binned Elimination with randomized arm arm-pulls
Input:
starting round tsaat scheduled duration my- Initialize: /. 4- 4aa For each bin B at any level in T, set A(B) [K]
2 while / < ktan +mo do
Choose level in R:
Tt Lo-ta---
Let A, + A(B) and let B B+ (X,,).
Play random arm Ar selected with probability 1/|AA//-
Increment t + ++1
if such that Zm. 0 then
Let m = max E (2.4,..., [[og(T))) Zm, 0}. // Set maximum replay length. Run Base-Alg (1,, m).
// Replay interrupts.
10
Eviet bad arms bin B:
A(B) t A(B) fa [K]
3 rounds [11 82 C farm t) s.t. (5) holds for bin Tep-s, (X,))-
Amaster B
Amsster
B) (a E [K]
3 rounds [81, 82]
S Le, 1) s.t. (5) holds for bin Tag-s, (X.)).
Refine candidate arms: A(B) 6 (B
Discard arms previously discarded in ancestor bins.
14
Amaster(B) + NB'ET BCB Amastr [B').
16
Restart criterion: Amaster (B) = 0 for some bin then RETURN:;
17 RETURN.

---

Estimating Aggregate Local Gaps. E 5s(d'a) 1[x, E B} is estimated by Ee 8 (a', a). where 5,(a',a) a) 1[X, E B} is estimated by importance weighting as:
(a', a)) = |Aal (v.' 11TT d'} Y. 11 = =a) 1fa A.) 1fx, E).
(4)
Note that the above is an unbiased estimate of (a' a) 1(x, E B} whenever a' and a are both in A, at time 8, conditional on the context X.. It then follows that, conditional on Xy, the difference
(a a) 1(x, E B) - (a( is martingale that concentrates at rate of order roughly V K (
s2]). where recall from earlier that n E. 1(X, 1 the context count in bin B over interval T.
An arm a is then evicted at round é if, for some fixed Co > 04, rounds 81 82 S t such that at level I Tag-a1 and letting = Tag-a (Xt) (i.e., the bin at level T=--a1 containing Xx)
Σ (a', > Co K log( (2 V K log(T)) Tap-a: s2]( (5) o' d'E(K]
max
5 Key Technical Highlights of Analysis
While full analysis is deferred to Appendix D, we highlight key novelties and intuitive calculations.
Local Safety in Bins implies Safe Total Regret. We first argue that the notion of significant 1td
regret (+) within a bin B captures the total allowable regret rates 7' we wish to compete with over T "safe" rounds. If (x) holds for no intervals [3] in all bins B, arm would be safe and incur little regret over any [81, $2]. As it turns out, bounding the per-bin regret by (*) implies a total regret of 7 as seen from the following rough calculation: via concentration and the strong density assumption (Assumption 2) to conflate (1, 7]) = r(B)" T and the fact that there are = r bins at level r, we have:
Σ
K (n([) +r - (n((1,]) < K2/2, T1/2, d/2 +T Tr
(6)
BET,
In particular taking r x (K/T) s4. makes the above R.H.S. the desired rate K x 2
Significant Regret Threshold is Estimation Error. At the same time, the R.H.S. of (*) is standard variance and bias bound on the regression error of estimating the cumulative regret E.s,, (x) 1(x, E B} at any context & E B, conditional on Xx (see Lemma 6). Thus, intuitively, large gaps of magnitude above the threshold /K nI( + r(B) nB([) in (+) are detectable via the estimates of (4).
Combining the above two points, we conclude that the notion of significant regret (+) balances both (I) detection of unsafe arms and (2) regret of playing non-evicted arms. We next argue the randomized scheduling of multiple base algorithms is suitable for detecting experienced significant shifts.
A New Balanced Replay Scheduling. As mentioned earlier in Subsection 3.1, previous adaptive works on contextual bandits fail to attain the optimal regret in this setting due to an inappropriate frequency of scheduling re-exploration. We introduce novel scheduling (Line 6 of Algorithm 1) of replays which carefully balances exploration and fast detection of significant regret in the sense of (x). In particular, the determined probability (L/m) z4a (1/t) of scheduling new Base-Alg (1, m) comes from the following intuitive calculation: single replay of duration m will, if scheduled, incur an additional regret of about incurred due to scheduled replays is roughly upper bounded by
Then, summing over all possible replays, the total extra regret
Σ
Σ 2.2.......T
Σ T (1/t) S T
2Pd
m
1Cp > 0 needs to be sufficiently large, but is universal constant free of the horizon 7 or any distributional parameters.

---

In other words, the cost of replays only incurs extra constants in the regret. Surprisingly, we find this scheduling rate is also sufficient for detecting significant regret in any experienced subregion B of the context space X, i.e. there is no need to do additional exploration on a localized per-bin basis.
Key in this observation is the fact that, to detect significant regret over interval I in any bin B, it suffices to check it at the critical level ry x (K/|z))='> where |/] the length of In particular, a well-timed Base-Alg running on the interval I will use this level ry (Line 2 of Algorithm 2) and is, thus, equipped to detect significant regret at all experienced bins over I.
Suffices to Only Check (+) at Critical Lyvelsr At first glance, detecting experienced significant shifts (Definition 6) appears difficult as an arm a may incur significant regret over a different bin B' from the bin B that is currently being used by the algorithm.
We in fact show that it suffices to only estimate the R.H.S. of (+) in bins B' at the critical level ry (Lemma and Proposition 15). We give a rough argument for why this is the case: first, note that (*) may be rewritten as
K
(I( E5.(a) 1[x, E B)
+ r(B).
nD(II
sEI
We next relate the two sides of the above display across different levels r(B).
By concentration and the strong density assumption (Assumption 2), the R.H.S. of (7) is in fact of order x 1/V/4 r(By² + r(B), which is minimized at the critical level r(B) x ri-
The L.H.S. of (7) is an estimate of the average gap प Exer (x)) any particular x e B using nearby contexts. In fact, by concentration, the two can be conflated up to error terms of order the R.H.S. of (7).
Combining the above two points, we see that if (7) holds for some bin B, then it will also hold for the "critical bin" B', with B' n B + 0, at the critical level ry x (K/[T)) zla, In other words, significant regret at any experienced bin implies significant regret at the critical level, thus allowing us to constrain attention to these critical levels.
On the other hand, we observe that the calculations in (6) would hold if we only checked (+) for bins B at level ry. Thus, also suffices to only use the levels r', for regret minimization over intervals with experienced significant shift.
Yet, even still, the analysis is challenging there may be "missing data problems": arms E A(B) in contention at B may have been evicted from sibling bins inside the parent B' - B at the critical level. In other words, it is not a priori obvious how do reliable estimation of arms E A(B) across a larger bin B' which may contain sub-regions where a has already been evicted. We show it is in fact possible to identify subclass of intervals of rounds (Definition 12) and an associated class of replays (Definition 13) which can quickly evict arm a in the critical bin B' before there are missing data problems for bin B C B². The details of this can be found in Proposition 15 of Appendix D.2.
6
Conclusion
We have shown that it is possible to adapt optimally to an unknown number of experienced significant shifts notion introduced here which captures severe changes in best-arm, only at observed contexts. An interesting future direction is to explore other notions of experienced shifts which may yield even more optimistic rates. For example, suppose changes in best arm occur at every round, but are localized to a sub-region E of the context space X. Then, a procedure which discretizes X' into bins at level --=+a and runs local instantiations of a suitable non- con-stationary MAB algorithm (e.g.. META of Suk and Kpotufe [2022]) can attain faster rates than those of Theorem 3 for some choices of E. At the same time, such a strategy cannot always attain the i(xr)a+a 24 rate in general as using the level T r'a insufficient to detect experienced significant shifts occurring at short intervals / of length |7| < T (which require larger levels). This prompts the questions of whether there exists a unified notion of experienced shift which captures the most optimistic rates these scenarios and whether such notion can be adapted to.
10

---

References
Yasin Abbasi-Yadkorfs András György, and Nevena Lazic. A new look at dynamic regret for non-stationary stochastic bandits. arXiv preprint arXiv:2201.06532. 2022.
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: fast and simple algorithm for contextual bandits. volume 32 of Proceedings of Machine Learning Research, pages 1638-1646. PMLR, 22-24 Jun 2014.
Robin Allesiardo, Raphaël Féraud, and Odblric-Ambrym Maillard. The non-stationary stochastic multi-armed bandit problem. International Journal of Data Science and Analytics, 3(4):267-283,
2017.
Sakshi Arya and Yuhong Yang. Randomized allocation with nonparametric estimation for contextual bandits with delayed rewards. Statistics Probability Letters, 164:108818 18, 2020. ISSN 0167-7152.
Jean-Yves Audibert and Alexander B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608-4) 6336008833,200 2007.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. Conference on Learning Theory, pages 138-158, 2019.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration-explootaaiie in a multi-armed bandit problem with non-stationary rewards. Stochastic Systems, 9()): 2019.
Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, and Julien Seznec. Efficient change- point detection for tackling piecewise-stationss bandits. Journal of Machine Learning Research, 23(77):1-40, 2022.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandit algorithms with supervised learning guarantees. A/STATS, 2011.
Moise Blanchard, Steve Hanneke, and Patrick Jaillet. Non-stationary contextual bandits and universal learning. arXiv preprini arXiv:2302.077 186, 2023.
Changxiao Cai, T. Tony Cai, and Hongzhe Li. Transfer learning for contextual multi-armed bandits. arxiv preprint arXiv:2211.1266 2022.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. Proceedings the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Liyu Chen and Haipeng Luo. Near-optimal goal-oriented reinforcement learning non-stationary environments. Advances in Neural Information Processing Systems, 2022.
Yifang Chen, Chung Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non con-stationary contextual bandits: efficient, optimal, and parameter-free, In 32nd Annual Conference on Learning Theory, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary Markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pages 1884--1544 PMLR, 2020.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: learning to optimize under non-stationarity. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
Yuhao Ding and Javad Lavaei. Provably efficient primal-dual reinforcement learning for CMDPs with nta-staaionary objectives and constraints. AAAI Conference on Artificial Intelligence (AAAI), 2023.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. A kernel-based approach non-stationary reinforcement learning in metric spaces. International Conference Artificial Intelligence and Statistics, pages 5538-3546. PMLR, 2021.
11

---

Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Sevents Conference on Uncertainty in Artificial Intelligence, page 169-178. AUAI Press, 2011.
Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie. Dynamic regret of policy optimization in son-station environments. Advances in Neural Information Processing Systems, 33:6743- 6754, 2020.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. Proceedings of the 37th International Conference on Machine Learning, 119; 3199-3210, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1539-1548. PMLR, 10-15 Jul 2018.
Pratik Gajane, Ronald Ortner, and Peter Auer. A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint 1805. 2018.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pages 174-188. ALT 2011, Springer, 2011.
Melody Guan and Heinrich Jiang. Nonparametric stochastic contextual bandits. AAAI, 2018.
Yonatan Gur, Ahmadreza Momeni, and Stefan Wager. Smoothness-adapiiv contextual bandits. Operations Research, (MM6):198-3211 2022.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the parametric and non-iifferentiable regret regimes. Conference on Learning Theory, 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Zohar S Karnin and Oren Anava. Multi-armed bandits: Competing with optimal sequences. In Advances in Neural Information Processing Systems, pages 199-207, 2016.
Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Proceedings of the Thirty- Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2025-2027. PMLR, 25-28 Jun 2019.
John Langford and Tong Zhang. The epoch-greeds algorithm for multi-armed bandits with side information. In Advances in neural information processing systems, pages 817-824, 2008
Fang Liu, Joohyun Lee, and Ness Shroff. A changee-dtecctonn based framework for piecewise- stationary multi- aamed bandit problem. Proceedings of the AAAI Conference on Artificial Intelli- gence, 2018.
Tyler Lu, Dávid Pál, and Martin Pál. Showing relevant ads via context multi-armed bandits. In Proceedings of AISTATS, 2009,
Haipeng Luo, Chen-Yu Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pages 1739-1776. PMLR, 2018.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Coruption-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242-3245. PMLR. 2021.
Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Basar. Near-optimal model-free reinforcement learning in non-stationary episodic mdps. International Conference Machine Learning, pages 7447-7458. PMLR, 2021.
12

---

Subhojyoti Mukherjee and Odalric-Ambry Maillard. Distribution Distribution-dependen and bounds for piecewise i.idd bandits. Reinforcement Learning for Real Life (RLARealLife) Workshop in the 36th International Conference on Mearning Learning. 2019.
Ronald Ortner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 81-90. PMLR, 22-25 Jul 2020.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41 4122)699-721,, 2013.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2022.
Wei Qian and Yuhong Yang. Kernel estimation and model combination in a bandit problem with covariates. Journal of Machine Learning Research, 17(149):1-77, 2016a.
Wei Qian and Yuhong Yang. Randomized allocation with arm elimination in bandit problem with covariates. Electronic Journal of Statistics, 10(1):242 270, 2016b.
Henry Reeve, Joe Mellor, and Gavin Brown. The k-nearest neighbour ucb algorithm for multi-armed bandits with covariates. In Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 725-752. PMLR, 07-09 Apr 2018.
Phillipe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. COLT, 2010.
Jyotirmoy Sarkar. One-armed bandit problems with covariates. The Annals of Statistics, pages 1978-2002, 1991.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904 1931,, 2021.
Aleksandrs Slivkins. Contextual bandits with similarity information. The Journal of Machine Learning Research, 15(1):2533-2668 2014.
Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2160-2182. PMLR, 02-05 Jul 2022.
Joseph Suk and Samory Kpotufe. Self-tuning bandits over unknown covariate-shift, International Conference Algorithmic Learning Theory, 2021.
Ahmed Touati and Pascal Vincent. Efficient learning in non-stationary linear Markov decision processes. arXiv preprint arXiv:2010.12870 2020.
Chen-Yr Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. Proceedings of the 32nd International Conference on Learning Theory, 2021.
Chen-Vo Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
Lai Wei and Vaihbav Srivatsva. On abruptly-changing and slowly-vayynng multiarmed bandit. problems. Annual American Control Conference (ACC), 2018
Michael Woodroofe. A one-armed bandit problem with concomitant variable. Journal of the American Statistical Association, 74(368):799-800 1979.
Qingyun Wu, Naveen Iyer, and Hongning Wang. Learning contextual bandits in a non-stationary environment. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pages 495-504, 2018
13

---

Yuhong Yang, Dan Zhu, et al. Randomized allocation with nonparametric estimation for a multi- armed bandit problem with covariates. The Annals of Statistics, 30(1):100-121, 2002.
Huozhi Zhou, Jinglin Chen, Lav R. Varshney, and Ashish Jagmohan. Nonstationary reinforcement learning with linear function approximation. Transactions on Machine Learning Research, 2022. ISSN 2835-8856.
14

---

A Details for Specializing Previous Contextual Bandit Results to Lipschitz Contextual Bandits
A.1 Finite Policy Class Contextual Bandits
In the finite policy class setting" one is given access to known finite class II of policies [K]. and in the non-stationary variant, seeks to minimize regret to the time-varying benchmark of best policies .े = argmax en EE), (Y (m())) In other words, the "dynamic regret" in this setting is defined by (for chosen policies (
Σ max ExX.))ED xEIl
Σ B[Y(
We can in fact recover the Lipschitz contextual bandit setting and relate the above to our notion of dynamic regret (Definition 2). To do we let II be the class of policies which uses level r E R and discretizes decision-making across individual bins sequence of policies {mpracke; ) which attains the minimax regret rate of Theorem 1. So, it remains to bound the regret to the sequence ( ) in the sense above.
Tr. Then, we claim there is an oracle
Parametrizing in Terms of Global Number L of Shifts. Suppose there are L + 1 stationary +
phases of length + 1). Then, we first claim there is an oracle sequence policies ne
puracle which
attains reget (T. 1) मंय T
First, recall from Subsection 2.3 the oracle choice of level ra for a stationary period of rounds, or the level In & (K/n)zia, Now, define {męrucle) } as follows: at each round t, praacle uses the oracle level r (T)(L1) x
2+d and plays in each bin B E Ty, the arm maximizing the average reward in that bin (X,) X, E B). As this biased version of the actual bandit problem (fx))x))e(()) at context X,, it will follow that mrracl incurs regret of order the bias of estimation in B which is
K((+1) T
Concretely, suppose X, falls in bin B at level r, and let mpradee [3 be the arm selected at round t by nt in bin B. Then, as mean rewards are Lipschitz, each policy mn arracle suffers regret:
max (X,) St (B) (Xt) S max [X,) - 1 (B) (X1) X. +r=r.
aE(K]
aE[K]
Thus, the sequence of policies (mprock)) ) achieves dynamic regret (in the sense of Definition 2)
Σ max ff (X,) dE[K]
ft" maak (xe) (x)) S ((+1))
(
T ( (L+1)I
K
T
α (L+1) ze .
Thus, it suffices to minimize dynamic regret in the sense of (8) to this oracle policy mpracle, The Htateoof-the-at adaptive guarantee in this setting is that of the ADA-ILTCB algorithm of Chen et al. [2019], which achieves a dynamic regret of / //LL LT III. Thus, it remains to compute [II].
We first observe that we need only consider levels in of size at least (K/T) शें which is the oracle choice of level for one stationary phase of length T. Thus, the size of the policy class II is
Σ KT o K(T/K)afz = log( PER
T
27a
log (K).
K
Plugging this into / LTLT log( II] gives regret rate of KT'a
L /
204,
which has a worse itd
dependence on the global number of shifts L than the minimax optimal rate of Laia T (see Theorem l).
"While there are matters of efficiency and what offline learning guarantees may be assumed in this broader agnostic setting, we do not discuss these here, and readers are deferred to Langford and Zhang [2008]. Dudik al. [2011]. Agarwal et al. [2014].
15

---

Parametrizing in Terms of Total-Variation Vr. Fix any positive real number V [7 7]. Then, the lower bound construction of Theorem reveals that there exists an environment with
L+ 1+1=77 T/A stationary phases of length A =
and total-variation of order V.
Then, the earlier defined oracle sequence of policies (xemicle) attains the optimal dynamic regret rate terms of Vr (see Theorem 1) since
(L 1) T x T $12.
Meanwhile, the state-of-the the-th--nn art adaptive regret guarantee in this parametrization is Theorem 2 of Chen et al. [2019], which shows ADA-ILTCHB regret bound is:
(K-log((I)) //322///33 + / K log((
(III T x K कमीप; V 7 S hea + K x 244
We claim this rate is no better than our rate in Corollary 5, in all parameters V.K.T. For K 2 T, both rates imply linear regret. Assume K T. Then, note by elementary calculations that for all E N U (0):
2
d 2 +
1
2
3( + d)
+ d
3+d d 3(2 + d)
Then, it follows that rate of Corollary 5 is smaller using the fact that K < <:
K अहेंग 1/3 T अरीत 2 K Ka
V
sea
K Ksta
अहंय Z (KV) 7
A.2 Realizable Contextual Bandits
Lipschitz contextual bandits is also special case of contextual bandits with realizability. In this broader setting, the learner given a function class + which contains the true regression function oं X x [K] + [o, 1] describing mean rewards of context-arm pairs at round t. The goal is to compete with the time-varying benchmark policies Toz (r) = argmax o7 (z, a), using calls regression oracle over
While the natural choice for t the infinite class of all Lipschitz functions from x [K] - [0, 1], the state-of-the non-stationary algorithm only provides guarantees for finite & [Wei and Luo, 2021, Appendix 1.7].
However, it is still possible to recover the Lipschitz contextual bandit setting, by defining + similarly to how we defined the finite class of policies II above. Let + be the class of all piecewise constant functions which depends on a level r E R, and are constant on bins B E T, at level r, taking values which are multiples of T 2nd (there are O(T)) many such values in [0, 1)). Here, & is essentially the class of diffcrent ixcretization-baseee regression estimates for the true mean rewards, as appears in prior works [Rigollet and Zeevi, 2010, Perchet and Rigollet, 2013].
For this specification of t the realizability assumption is false. Rather, this is mildly misspecified regression class which is allowed by the stationary guarantees of FALCON (Simchi-Levi and Xu, 2021, Section 3.2]. In particular, by smoothness, each round E [Z'] there function oī & such that
z
sup =εX,,E[[]
(6) (x)) &
Specifically, we can let of (x. a) x Ex E B] be the smoothed version of ff (xx the bin B at level 7" aed containing æ. Then, the above misspecification introduces an additive term in the regret bound of FALCON of order 2:4 which is of the right order in our setting.
In this setting, the current state-of-the oftthe-art MASTER black-box algorithm using FALCON Simchi-Lewi and Xu [2021] ] as base algorithm can obtain dynamic regret upper bounded by [see Wei and Luo, 2021, Theorem 2]:
min (Vog(( L. T, log /3 ((
1/3, T2/3 + Vlog(1 +1)
As & is essentially the same size as the policy class IT defined in the previous section, the above regret bound specializes to similar rates as those of ADA-ILTCB derived above, and are ultimately suboptimal in light of Theorem 1.
16

---

B Useful Lemmas
Throughout the appendix, C1, C2.... will denote universal positive constants not depending on T, K any of the significant shifts (Tr())
B.1 Concentration of Aggregate Gap over an Interval within a Bin
We'll 'I first establish some concentration bounds for the local gap estimators 8 (d', a) defined in (4). For this purpose, recall Freedman's inequality.
Lemma 6 (Theorem of Beygelzimer al. [201 Let X1,..., Xn lR be martingale difference sequence with respect to some filtration Fo: Fi,... Assume for all that X, S R a.s.. Then for any ò E (0, 1), with probability least 1 Ó, we have:
(1
Σ Xi (e-
log(1/0)
Σ
B|X Rlog(1/0))
Recall from Section 4 that for round i, the local gap estimate 8/' [a) in bin B at round t between arms a',
(d a) Arl (Yi(a') 1(T, - 1(T - a}) 1sa A. 1(x, B}. We next apply Lemma 6 to our aggregate estimator from Section 4.
Proposition 7. With probability at least - 1/T w.r.t. the randomness of YT, { Xr, we have for all bins B E T and rounds 81 s2 and all arms [K] that for large enough e₁ 0:
Σ 8=81
8 (a', a)
Σ 118. ad).a) c1 (V (VKlog(T), nB([s1, s2)) + K log(T)), (10)
where F = (F. is the filtration with F, generated by (T 1 1==1
Proof. The martingale difference (a'a a) Ba a) Fa-1) is clearly bounded above by 2K
for bins B, rounds s, and all arms a, a'. We also have a cumulative variance bound:
1l (d',a)) a))² F.-1l
1(x, E B} 1...A...1 E = a or a'
8=81
8=81
1(x, E 2|AA
8=81
< 2K nB ([8, 82))
Then, the result follows from (9), and taking union bounds over bins B (note there at most T levels and at most T bins per level), arms a, a', and rounds $1, $2.
Since the error probability of Proposition 7 is negligible with respect to regret, we assume going forward the analysis that (10) holds for all arms a, a' [K] and rounds $1 $2. Specifically, let E be the good event over which the bounds of Proposition 7 hold for all all arms and intervals 82].
B.2 Concentration of Context Counts
We'll 'I next establish concentration w.r.t. the distribution of contexts Xy. This will ensure that all bins B E T have sufficient observed data.
Notation. ease notation throughout the analysis, we'll 'Ill henceforth use pl.) to refer the context marginal distribution ux (x(())
17

---

Lemma 8. Let {iel-1 be random sequence of arms whose distribution depends on Xy. With probability at least 1/T² w.r.. the randomness of XT. we have for all bins B E T, all arms a'aa E | and rounds 81 < 82, for some large enough > 0 the following inequalities hold:
[B([s1,82) - (s2 - -1 1) v(B)
S c2 (T) + (log(T))((BBB... (32 - ++1
(11)
(is, a) (1(x, E B} (B()
S c2 (log(T) (T) + vlog(T) (82
(12)
8=81
(.(a) (1(X, E B} (B))
c (log(T) Vlog(T)u(B) (82- 822-51 -1 +1)
(13)
Proof. The first inequality (11) follow from Lemma since Σ. 1(X, B} P( is martingale, which has predictable quadratic variation is at most (52 $1 1) n(B).
The other two inequalities are trickier since the corresponding sums Indeed, note (a(a) depends on X, while 6, (fs, a) may not even be adapted to the canonical filtration
necessarily martingales.
generated by Xx (i.e., i, may depend on X, for / 8). Nevertheless, observe that for any random variable W, = (X()) 1-1
(1 E B} - (B)) W. 01(0 e -)- 1 E B} - (B)).
The upper and lower bounds above are both martingale differences with respect to the canonical filtration of Xr and thus, summing the above over we have via Lemma 6:
a W. (11X, E B}- -M())
<
Σ
1[x, B) - u(B)
==81
I C2 (T) + v llog(T))(() (82 - $1 + +1)
Then, taking union bounds over rounds $1, 82, bins B T, and arms a e [K] gives the result.
Notation 2 (good event). Recall from earlier that & is the good event over which the bounds of Proposition 7 hold for all rounds $1, $2 E [T] and arms a' a E [K]. Thus, on E,, our estimated gaps in each bin will concentrate around their conditional means.
Let Eg be the good event on which bounds of Lemmaa 8 holds for all bins B, arms a E [K], rounds $1, 82 E [T]. Thus, on Ez, our covariate counts n& ([s),))))) will concentrate and we will be able to s2))
relate the empirical quantities E (a) 1(X, B} with their expectations.
Next, establish lemma which allows relate significant regret (x) and thus our eviction criterion (5) between different bins and levels.
Lemma 9 (Relating Aggregate Gaps Between Levels). On event Eg, if rounds 81 < 82, hin B' at level T Tag-as and arm a, for some c3 0:
Σ E 33 (VKlog(T) (n ([91, s2)) V K log(T)) r(B') nB (151, (181, s2l)).
then for any bin B B' and some e₁ > 0:
(a) 1(x, E B} < ca (T) rBB) Kzta. (82 - 81 81) 24
A
K Kog((T) + /
31 + +1)
The same applies for (a) replaced with 8z(a', a) for any fixed arm a' [K].
18

---

Proof. We have using (13) and the strong density assumption (Assumption 2):
52
Σ (.( 1[x, E B) S
(a) m(B)
+ (1og(T)+ + Vlog(T)u(B)) (82- - 31 + +1)
Ca C(B) 82
ca r(')d Σ ōs(a) n(B))
+ 02 (log(T) v llo((T)u(B) (52 31 + +1)
(14)
Again using (13)
82
Σ (a(a) (.(BB)))))) S Σ 6,(0) 1(X, B3} + c2 (Iog(T) + Vlog(T)u((")) (82 31 + 11
#=
< cs
(VKlog(T) (n (181, 52)) V K log(T)) + r(B) n ([81,
+Tgg(T) + Vlog(T) (s2 $1 +1)
Next, applying (11) to ng ([s1, s2l) and using the strong density assumption (Assumption 2) to bound the mass (BB") above by C2 r( (B')d, the above R.H.S. is further upper bounded by
C6 (og 1/2
( (T) शमग (s2 $1) s1) Σोत
K Klog(T))
(15)
Finally, plugging (15) into (14) and using the fact that (r(B")/2)² 2 (K/(s) $1 sfa), we have that (14) is of the desired order. The proof of the same inequalities with 6, (a' a) is analogous. M
The following lemma relating the bias and variance terms in the notion of significant regret (+) will serve useful many places in the analysis. They all follow from concentration and similar calculations via the strong density assumption (Assumption 2) as done previously.
Lemma 10 (Relating Bias and Variance Error Terms via Strong Density Assumption). Let r = Tag-st for some 82 81. Then, on event for any bin B E Tr:
(82 81 + 1) 1 B) I C7(82 - 81)=ta
211
V Vnn((s1,82)
S cs (82 - 81) Σ
K 2 + log (
+ log (T')
d/4 K 2+d
(s2 - $1)
1/2 24d
B.3
Useful Facts about Levels r E R and their Durations in Play
The following basic facts about the level selection procedure on Line 2 of Algorithm will be useful as we will decompose the analysis into the blocks, or different periods of rounds, where different levels are used.
Definition 8. Namely, for r E R, let se(r) and ee(r) denote the first and last rounds when level r used by the master Base-Alg in episode [te, te+1), i.e. rounds E [tt,, tet)) such that rt-t, Then, we call [se(r), ee(r] a block.
The proofs of the following facts all follow from the definition of the level r, (see Notation 1) and basic calculations.
Fact 1 (Relating Level to Interval Length). The level Fag-s;
2-m satisfies for 82 81 2 K:
2 (m-1)
K
> m
82
81
and hence
K (
(mm-1)))+
81 <.K K. (2+
19

---

Fact 2 (First Block). The first block (ee()) consists of rounds [te, te + K.
Fact (Start and End Times of Block), For r < 1, the start time or first round se(r) of the block corresponding to level r in episode LLe, l4+1) is se(r) = le + [K (2r)-(2+d] and the anticipated end time, or last round of the block if no new episode is triggered in said block, is ee(r) le + K r (2-42 -1.
Fact 4 (Length of Block), Each block [se(r), ee(r) is at least K rounds long. For the first block [ss (1), this is already clear. Otherwise, suppose < in which case:
ee(r) --((ssrrr))))))) + K x (2+d)
K (2rr-(2+a)
2 K.rrt (2+ 2
- 2- (2(2t)) -
2 K 22 (2+))) -1.
In particular, since 22+d(1 - (1-2 (2+2)) > for all d 2 0. we have the above is at least K.
We also have the above implies
(2+d) (1 2-+
2 (Ee(r) - se(r))
2 O depending only on d:
Rearranging, this becomes for some constant 0g
K sta
T. ee(r)-
Cg.
Note we can make oi large enough so that the above also holds for level r = 1.
The above along with the definition of rt-,, (see Notation 1) implies that the block length se(() and the episode length ex(r) - te(r) up to the end of block [se(r), er(r) can be conflated up to constants
GO (ee(r) se(r)) ee(r)) - Le S c1o (ee(r)) 8e(r))
C Proof of Oracle Regret Bound (Proposition 2)
Recall that &g is the good event on which our covariate counts concentrate by Lemma 8. It suffices to show our desired regret bound for any fixed context sequence Xy on this event.
Fix a phase TT, 1)+ and let = T---1-7-- Fix a bin B T, and let 7, be the last round E [Ta, Ti+ such that X, E B and arm a is included in G.. If is never excluded from Ge for all such 6, let ... I K Then, letting B' be the bin level Trg-n.
7, = T++1 - 1. WLOG suppose T; S 7 -... containing covariate Xyç, we have by (+) that:
8((a) 1(X, E' S VK. K ny (IT, -f1) + +r(B)) no Tf).
From Lemma 9, we conclude
Dinr ((a)) is at most
19.1
ci (1og2 xta (T/ Ti)
24
K log(T) + (B)) t4 + 1)
K K+1-a
where we use the fact that | 2 K + a for S T/ such that X, E B. Summing over arms
a E [K] with EeE[K] K+1-a S log K), we obtain from summing the above over K:
[og (T) K ald (T44 - T,) 7 + K log((T) + + Vlo((T)((B) (T - T4 +1)
e4 log(K)
(16)
Next, we claim that each significant phase [Ti, T++1) is at least K rounds long or I 7:-1 - Ti. This follows from the definition of significant regret (+) since for (s1, 82] [ra, T+41):
B ([52,, s2)) N 8.(a)-1(X. E B} VK nB((s1,
T+1 - Ta n s2)) K.
20

---

Then K S T+41 implies (via Fact I about the level P-411-7)
Σ K (Tg((T) < K log(T) - I 611 log (o)g अंत (1+11 T;)
T:) zia S en log शंय x 7;) 7;)
HTd.
BET,
Additionally, we have by Lemma 10:
V(T - (BB) S v (T++1 - Ti) (BB) I -1, K S csK CgK (T4+1 - T;) 7..
Then, plugging the above into (16) and summing over bins at level r, we have the regret in episode (Th, Ts41) is with probability at least 1 - 1/T" w.r.t. the distribution of Xy:
1--1-1 -1
7-41-1
5a(a)
1(X, E B}
E
Σ
8T(TT)
Xx
=E E
Σ
X
Ge
BET,
1=
acGi
5a(a) 1(X, B}
E
Σ
XT
[Gcl
BET, (E(K] t=
1 C12 log K)
Σ
log
1/2 (T)) ( - Tz)
24d
1td
K Kaza K log(T)
BеT
61 log()) (T1+1 Ti) 140
K ボナマ
where the strong density assumption to bound E BET, ra last inequality. Summing the regret over all experienced significant phases (T,, Te41) gives the desired result.
EBeT, ca =b(B) c in the
D Proof of CMETA Regret Upper Bound (Theorem 3)
Recall from Line 3 of Algorithm that lg is the first round of the f-th episode. WLOG, there are T total episodes and, by convention, we let = T 1 if only L - episodes occurred by round T.
We first quickly handle the simple case of < K. this case, the regret bound of Theorem is vacuous since by the sub-additivity of x: - 2
1t
f.
Σ (T+11 Tr)
T))
KIra 2 (Ti To) ) Kzid
THE
T =
0=0
Thus, it remains to show Theorem 3 for T 2 K.
We first transform the expected regret into a more suitable form, which will allow us analyze regret in similar fashion to the proof of the oracle regret bound (Appendix C).
D.1 Decomposing the Regret
We first transform the regret into a more convenient form. Let F {F,)T= be the filtration with F, fixed Xy. Then,
generated by {T,, Y } ) conditional
Xxl
(TE))
Fi-1l
Xr)
de(TTe)
E
Ae]
t=1
L
6((aa
E
X
A.
1=1
dEA,
Now, it suffices to bound the above R.H.S. on the good event E O Eg where the bounds of Lemmas 8 and 9 hold. Going forward in the rest of the analysis, we will assume said bounds hold wherever convenient.
21

---

Next, as alluded to in defining the oracle procedure (Definition 7), until the end of a significant phase [Ta 1. ). there is a safe arm each bin level 7 which is experienced.
Definition 9 (local last safe arm in each phase a)). For round t Te41), let B be the bin at level F which contains X, and let (B) be the last round in [Ta, T(+1) such that Xt,(B) E B. Then, by Definition there is (local) last safe arm of which does not yet incur significant regret in bin B in the following sense: for all [2] S [Ti, (B() letting r = Tez-o1 and B' E Ty such that B' 2 B we have:
nB Σ (.. 1[x. B') < VK nB (131, s2)) + C.n.rBBB ([11,
Remark 6. The local last safe arms {aite only depend on the distribution of XT and not on the realized rewards Yr. In particular, the sequence {al) is fixed conditional XT.
We first decompose the regret at round as (a) the regret of the local last safe arm of and (b) the regret of arm a to of. In other words, it suffices bound:
5.(a)
T Σ ((c))
5e(at, a)
11 Xx [Ail
1 (8) X7
|A
aEA:
aEA:
Note that the expectation on the first sum disappears since af is only function of X7 and the mean reward functions (t),,a
D.2 Bounding the Regret of the Local Last Safe Arm
Bounding E 5.(at) 1 n will be similar to the proof of Proposition 2. We show that the oracle procedure could have essentially just played arm of every round.
Fix a phase [Ta, T(+1) and let T Fix a bin E T, and let (B( be the local last safe arm af of the last round E [Ti, Te41) such that X, E B. Then, af a;;B) for every round E Ti41) such that X, B. Then, we have by Definition that for bin B' 2 B at level re-r
Σ (a,((()) ((X, E e s /K nB (TT 1)) + r(B') no (Tr,
Then, by Lemma 9, we have:
Σ (,(a(())) 1(x, E B} <
rd (7411-77 -2)2 _ K 24d
K logg(T) + Vlog(T)p(BB) (t Ti + +1).
(17)
Then, summing the above over bins in the same fashion as the proof of Proposition 2 gives:
Tes1-1
T-1-1
Σ (e(at)
Σ
Σ
(s(a((B)) 1(x, B} s 6r4 log(T) (TH+1 Tx) #
BET,
Finally, summing over phases [Ts, T++1) we have Σr & (af) of the right order.
D.3 Relating Episodes to Significant Phases
We next show that w.h.p. a restart occurs (i.c., a new episode begins) only if a significant shift has occurred sometime within the episode. Recall from Definition 6 that Tı, .2...., Ty the times of the significant shifts and that 11....,yy tr are the episode start times.
Lemma 11 (Restart Implies Significant Shift). On event E,, for each episode 14, let1) 1) with let1 S T (i.e., episode which concludes with restart), there exists significant shift T2 [te, ttette
22

---

Proof. Fix an episode [tg, t(+1). Then, by Line 11 of Algorithm 1, there is a bin B such that every arm [K] was evicted from B some round in the episode, i.c. (5) true for each arm a on some interval [81, 82] S [4z, (4+1). It suffices to show that this implies significnat shift has occurred between rounds ig and 12+1-
Suppose (5) first triggers the eviction of arm a at time t in B' 2 B over interval [2] where r(B') Ts--#1- By concentration (10) and our eviction criteria (5), we have that there is arm * a such that (using the notation Proposition 7) for large enough Co > and some C14 > 0:
E (a',
Fo-1] 2 (VK K (lg((T ug ((11,)2) -K log(T))2
+r(B') ng. ([s1, s2])).
(18)
Next, if arm a is evicted from A(B") at round t, then we have by the definition of 8 (a', (4):
6, a) 11x, E B'} El005 (a',a) Fa-1] = (X,) 1[x, E B)
a, a,a' E,, a E a' & As.
a A
In any case, the above L.H.S. conditional expectation is bounded above by (a) 1(x, E B'}. Thus, (18) implies arm incurs significant regret (+) in B' on [s1,
(a(a) 11x, E B3} 2 VK K
+ rBBB) nB ([5), s2]).
Then, since every arm a evicted in bin B by round t, a significant shift must have occurred in episode [te, te+1].
D.4 Regret of CMETA to the Last Safe Arm
It remains to bound E E episodes and then the blocks (see Definition 8) where a particular choice of level is used within the episode. The following notation will be useful.
E,EA, de(ai a)/[Ar] X.). We further decompose this sum over / into
Definition 10.
Let PHASES( r) = e [Z] : [ra 744) [sx(r), ee(r)] + 0} be the phases which intersect block (s ler T(i,r,)) = [m, Teta) (s(((), be the effective length of the phase as observed in block ce())
Similarly, define PHASES(() = {i [L] (41) n te+1) # 0} the phases which intersect episode [1e, (e+1)-
will fact suffice to show w.h.p. w.r.t. the distribution of Xy, for each episode (le, (e41, each block (se(r), ce(r) in [te, te+1), and each bin B E T,:
(r)
aa(afaa)
1[X, E B} 118 ( X
Arl
(r)
aeAe
[og(() (1og(T)+ + (T)
S C15 logolo( (K)
1(11)8))
Σ (EPHASES(E.r)
r(B)* T(i,r, #
Xx
(19)
D.5 Summing the Per-(Bin, Block, Episode) Regret over Bins, Blocks, and Episodes.
Admitting (19), we show that the total dynamic regret over T rounds of the desired order.
Recall from earlier that there are WLOG 7 total episodes with the convention that 4 + if only l episodes occur by round T. Then, summing per-bin regret bound (19) over all the bins B E T
23

---

at level r gives (using strong density to bound EBEr rd S ()):
Σ cc(r)
ae(af.a)
11x, E B} 1(8 XT
Arl
BET, (= REA:
S C16 log(K)E
118 n
log(T) + (T)
E
T(i, r, 6) 2- katz
Xx
BET,
(EPHASES(L.))
(20)
Next, summing over the different levels (of which there are at most (T) used in any episode), we obtain by Jensen's 's inequality the concave function
Ltd
244
Σ Σ T(i,r,))atd
Σ
Σ
T)
TER :EPUNSDS(E.r)
(EPASSD)(E) PERSIE
278
Σ
log(T)
Σ
T(,,,
REPHASES(E)
PER:SEPAAES((E.))
Now, we have
Σ
T(ir,()=
E
7++1 73 + 1.
PER:NEEHASSS((C.))
TERSiEHAAESS(C.))
We also have (via Fact I about level -1441-4 which is the smallest level used in episode (tc, t(+1))
ΣΣ PER BET,
log(T)
Σ
log(T)
FE
t++1 - tt
243
< c17 log (T))
K
c18 log (T)
Σ iEPHASES(E)
(T++1 - Ty 3 K
Thus, combining the above inequalities with (20), we obtain overall bound:
Cis log( (T)E (
Σ
(T+1 (
(EPHASES(E)
Recall now that & is the good event over which the concentration bounds of Proposition 7 hold. Then, using the fact that, on event E,, each phase [Tr, T+41) intersects at most two episodes (Lemma 11), summing the above R.H.S over episodes E E [T] gives (since most log(T)) blocks per episode) order
2 log(K) (K) log ( Σ (T41 - T)) Kala.
It then remains to show the per-(bin, block, episode) regret bound (19).
D.6 Bounding the Per-(Bin, Block, Episode) Regret to the Last Safe Arm
To show (19), we first fix block (e(r),,((r) and bin B T,. We then further decompose
8, (, a) two parts:
(a) The regret of to the local last master arm, denoted by a, to be evicted from Amaster (B) in block [s=(r), ee(r)) (ties are broken arbitrarily).
(b) The regret of the local last master arm (B) to the last safe arm of.
24

---

In other words, the L.H.S. of (19) is decomposed as:
ne(r)
(B),
ex(r)
E
1(x, B) XT
+E
Σ (=ee(r)
5e(0f, a, (B)) 1(x, B)
XT
A
( REA:
(a)
(6)
We will show both (a) and (b) of order (19).
Bounding the Regret of Other Arms to the Local Last Master Arm aB( We start by partitioning the rounds such that X₁ B and a E Ar in (a) according to before or after they are evicted from Amaster (B). Suppose arm evicted from Amsucr (B) round to [se(r), (r(r) (formally, we let t = Ex(r) if a is not evicted in block [sx(r), (r)r). Then, it suffices to bound:
K
(B),
K celr) Σ
(, a)
1(x, B]
1fa Ad 1(X, E B} X
|Ai
|4
(=82(r)
(2l)
Suppose WLOG that f. ........ K Then, for each round < E. all arms 2 a are retained in Amsster (B) and thus retained in the candidate arm set A, for all rounds where X₃ E B. Importantly, at each round t a level of at least r is used since a child Base-Alg can only use a higher level than the master Base-Alg. Thus, |A, K + a for all t t..
Next, bound the first double sum in (21), i.e. the regret of playing a to a (B) from se(r) to to 1. Applying our concentration bounds (Proposition 7), since arm a is not evicted from A(B) till round t,, on event & we have for some C19 0 and any other arm a' E A(B) through round 1 (i.e., o' E A, for all t E [te, such that X₁ E B since we always use level at least r at such round t): for bin B' 2 B level (1))1- on event & (note that we necessarily always have A(B') 2 AB) for B' 2 by Line 14 of Algorithm 2):
Σ B18 (a',a) Fi-1l S 91 K log(T) (n ((s: (r), V K (r))(r)
((se(r,,,
Next, since a, d' A₁ for each E [se(r), ef 1) such that X, E B, we have:
E (s(rr, e B ( a) Fi-1l ,((a',a).
Thus, we conclude by (5):
a) E B} S cwv log(T) (ng ((s((()))) K (lg()))) (((())
(r))
Thus, by Lemma 9, and since B' 2 B, we conclude for any such a' event E Et--1
bela'aa)
Te
1(X, B} most
ca (1og)/2(T)) Kzid (1S se(r) H5 + log((T) + (log(T)(t; se(r)) m(B)
(22)
K K
where we use the fact that [A. 2 K +
for all / E [se(r), (2). Since this last bound holds uniformly for all a' E A(B) through round 1o - 1, it must hold for a' a,(B), (B), the local last master arm.
Then, summing over all arms a, we have on event E₁:
de (B), 1(x, B} s cs log(K) (log (2gg ,d_ (er(r) se(r)) K kztz+
Σ
Aee
(r())
K Klog(T) + /log(T)(( - se(r)) m(B))
(23)
25

---

Next note that by Lemma 10:
v(s - 5c(r)) (BB) & V(e((r) - se(r)) 1BB
$ s 2
4/2 (ee(r) se(r))
S o pd (ex(r) st(r)) #
Additionally, since K S ee(r)) se(r) (Fact 4), we have:
K log(T) S (es(r) se(r)) -هं - K x rd (es(r) - se(r)) K Kzta.
Thus, combining the above two displays with (23) gives us
F
(B),)( 1(X, E B} S c20 log log(T) rd (ec(r) - sc(r)) a4d K stt
A
(+)
We next show the second double sum in (21) has an upper bound similar to the above. For this, first observe that if arm a is played in bin B after round E,, then it must be due to an active replay. The difficulty here is that replays may interrupt each other and care must be taken in managing the contribution of >, 5,(a, (B),a) a) (which may be negative) by different overlapping replays.
Our strategy, similar to that of Section B.1 in Suk and Kpotufe [2022], is to partition the rounds when a played by replay after round Ex according to which replay is active and not accounted for by another replay. This involves carefully identifying a subclass of replays whose durations while playing a B span all the rounds where is played B after 1.. Then, we cover the times when is played by collection of intervals corresponding to the schedules of this subelass of replays, on each which we can employ the eviction criterion (5) and concentration bound as done earlier.
For this purpose, we first define the following terminology (which is all w.r.t. a fixed arm a, along with fixed block (r()))))(r))) and bin B T,)): Definition 11.
(i) For each scheduled and activated Base-Alg (s. m). let the round (s. m)) be the minimum of two quantities: (a) the last round in [s, + m] when arm is retained in A(B) by Base-Alg (s, m. and all of its children, and (b) the last round that Base-Alg (s, m) is active and not permanently interrupted by another replay. Call the interval [s, M m)] the active interval of Base-Alg Alg (8, m).
(ii) Call a replay Base-Alg Alg (s, m) proper if there is other scheduled replay Base-Alg (s', sm') such that [s. $ + m] C (s', s + m²) where Base-Alg (s', m²) will become active again after round s m. In other words, a proper replay is not scheduled inside the scheduled range of rounds of another replay. Let PROPER TROPER(SE(T), start in the block (e(()))e(r)))
be the set of proper replays scheduled
(iii)
Call a scheduled replay Base-Alg (s. m. sub-replay if it is non-proper and if each of its ancestor replays (i.e., previously scheduled replays whose durations have not concluded) Base-Alg (s', m²) satisfies M(s', .m') <.s. In other words, sub-replay either permanently interrupts its parent or does not, but is scheduled after its parent (and all its ancestors) stops playing arm in B. Let SUBPROPER( (x(r) be the set of all sub-replays scheduled before round t++1-
Equipped with this language, we now show some basic claims which essentially reduce analyzing the complicated hierarchy of replays to analyzing the active intervals of replays in PROPER((((T),,c(()) SUBPROPER(sECC) (se(r), se()).
Proposition 12. The active intervals
{[s, (s, m)] Base-Alg m) E (ROPER((((f) U SUBPROOEE (UBPPROPE((((())s(())) mutually disjoint.
Clearly, the classes of replays PROPER(4,, (411) and SUBPROPER(s<(T). sp((r) are dis- joint. Next, we show the respective active intervals (x, M)) and [s', M(s'mm)) of any two Base-Alg (8, m) and Base-Alg( (s', m²) E (SoOP)((se()....))) ( (se(r), are dis- joint.
Proof.
26

---

proper replays
evicted sub-replays reintroduce arm a to A
Figure 2: Shown are replay scheduled durations (in gray) with dots marking when arm a is rein- troduced to A,. Black segments indicate the active intervals [s, M(, m)] for proper replays and sub-replays. Note that the rounds where a E A in the left unlabeled replay's 's duration are accounted for by the larger proper replay.
1. Proper replay vs. sub-replay: sub-replay can only be scheduled after the round M(s, m) the most recent proper replay Base-Alg (s, m) (which is necessarily an ancestor). Thus, the active intervals of proper replays and sub-replays are disjoint.
2. Two distinct proper replays: two such replays can only intersect by one permanently interrupting the other, and since (ss, m) always occurs before the permanent interruption Base-Alg (s, m), we have the active intervals of two such replays are disjoint.
3. Two distinct sub-replays:
consider two non-proper replays Base-Alg (s, m)) Base-Alg (s', m²) E SUBPROPER se(r)) with s' > s. Suppose their active intervals intersect and that Base-Alg (s. m) is an ancestor of Base-Alg (s', m').
Then, if Base-Alg (s', m²) is a sub-replay, we must have s' > MM(, which means that (s', M(s', m')] and [s, (s, m)] are disjoint.
Next, we claim that the active intervals [s, ((, m)] for Base-Alg (8, m) E PROPER le+1) U SUBPROPER(<<()), 8r(r) contain all the rounds where a is played in after being evicted from Amaser B). To show this, we first observe that for each round it when replay is active, there is unique proper replay associated to t, namely the proper replay scheduled most recently. Next, note that any round > ty where X, E B and where arm E A, must belong to the active interval [s, MM, m)] of this unique proper replay Base-Alg (s, m) associated to round t, or else satisfies t > (s,, m) in which case unique sub-replay Base-Alg Alg (s', m') E SUBPROPER (s(()), se(r)) is active at round t and not yet permanently interrupted by round t. Thus, must be the case that t [s', M(',, m')].
Overloading notation, we'll II'll let A,(B) be the value of A(B) for the Base-Alg active at round I. Next, note that every round E [s, (s, m]] for proper or subproper Base-Alg (s, m) is clearly round where a (B) and no such round is accounted for twice by Proposition 12. Thus.
{t E (t), (r)] A.B))
[s (s,
Base-Alg (s.m))
Then, rewrite the second double sum in (21)
M(s.m)
(B),
Σ
Z Z
Σ
1(X, B).
A
Base-Alg (s.m) (R.m))PPoPEE(xx(T)ee (F) (U)
t=
Recall in the above that the Bernoulli R.V. Zm, (see Line 6 of Algorithm 1) decides whether
Base-Alg (s, m) is scheduled.
Further bounding the sum over above by its positive part, we can expand the middle sum above over Base-Alg (s, m) PROPER((e, (e41) U SUBPRROEE(<<(T))ss((( st(r) to instead be over all Base-Alg (s, m), or obtain:
[(sm) Σ
(a),())))) 1(x, E B)
Σ
Σ
Zmn
At
Base-Alg (s,m)
27

---

where the sum is over all replays Base-Alg m), i.e. s e {te + 1...... te..,, - 1} and m E (2.4...., ['gg(T)],, j. It then remains to bound the contributed relative regret of cach Base-Alg (s, m) the interval [s t. (s, m)], which will follow similarly the previous steps in bounding the first double sum of (21).
We first have (now overloading the notation (ss m) M (s, m, a) for clarity), i.e. combining concentration bound (10) with the eviction criterion (5) and applying Lemma 9;
((s.m.a)
(B),
1(X, E
IA
L=
C21 (log" (logg/2(1)) (T) K नंत M(s, a, # K log(T) + Vlog(T) M(s m.a) ((B)
[inrejs,M(ssm.a)) [A
Thus, it remains to bound
Zm.e log 1/2 (T)r (s, m, a) + (T) + (s,
mis,ejs.MMsmm..)) [4
a,2,m
Swapping the outer two sums and, similar to before, recognizing that Ex=1 mi [Ael S
K
(o'(K) by summing over arms in the order they are evicted by Base-Alg (s, m), we have that remains to bound:
log( K))
Σ
Zm, C21 (log)/((2) nd Kata mard K log(T) + /log(T) m (B)
Base-Alg (s.m)
(24)
where m = A (ex(r) se(r)) (note may frrelly restrict all active intervals to the current block (r)))), Let
R(m, B) = C21 log (T) ,d KIt. mard 1td
(021
+ (K A m) log(T)
+olo((T) m u(Bi) n ([s, ml).
Then, in light of the previous calculations, R(m, B) an upper bound on the within-bin B regret contributed by replay of total duration m (note we can always coarsely upper bound this regret by n + ml).
Then, plugging R(m, B) into (24) gives via tower law:
T Σ s=ae(r) m
E
E
Σ Zm,s R(m, B) se(r) 8,77
XT =
Σ
Elsm,,11s Is (e((r) se(r)) B) Xr
(25)
Next, we observe that Zm.. and 1[s I ee(r)) are independent conditional on (r(r) since 1 < ee(r) only depends on the scheduling and observations of base algorithms scheduled before round Additionally, conditional on st(r). the episode start time tę is also fixed since the two are deterministically related (see Fact 3). Then, we have that:
sोय m
f/
1
P(Zm,s = = B[ 82 (x)) 1m,, le, se(r))
Thus,
B 1(s Ee((r) se(r)] 18|Zm,a se(r), te] [[ < ex(r)) st(r),te]
Ltd
3
Ei(s < ( se(r)).
m tt
Plugging this into (25) and unconditioning, we obtain:
ee(r)
[log(T)
#
1
E
R(2", B) X
(26)
2n
8 - tt
28

---

We first evaluate the inner sum over Note that
[og(T))
#47
(2" A (ee(r) - se(r)) 2-d
1-d
I log(T)) (ee(r) -s((r)) af
2n
Dog(T))
2 A
- (ec((r)-
s (ee(r) -
==1
[Tg(T))
zia
(KA2 2n) 2 log(T) K 245
Next, we plug in the above displays into (26). In particular, multiplying the above displays by Led
(s - -te) and taking a further sum over E [se(r), ex(r)] gives an upper bound of:
(ee(r) - te) पोо (ec(r)) - se(r)) Σमते Katz
(T)
+ (ee(F) - sc(r)) कन log( (T) pd K उ
log(T))
First, we note the first term inside the parentheses above inside dominates the second term for all values of K, ee(r), T.. Next, note from Fact 4 that ex(r) le ciolee(r) se(r)) and the above is at most:
p (ee(r) se(r)) # K मंं log logg/((TT) + log (T) (ee(r) se(r)) We next recall from Fact 4 that each block [se(r), (r)) is at least K rounds long. Thus,
(27)
(Ee(r) se(r))
-+2 K श 2 622 (Ee(r) - se(r)) 2 K
Thus, the second term of (27) is at most the order of the first term.
Showing (a) is order (19) then follows from writing ex(r) - (x(r) as the sum of effective phase
lengths f'i,, r, E) (see Definition 10) of the phases [Te, T(41) intersecting block [se(r), er(r)]. and using the sub-additivity of x
Bounding the Regret of the Last Master Arm (B) to the Last Safe Arm a². Before we proceed, we first convert Eesa((r) da (B)) 1{X, E B} into more convenient form in terms of the masses μl( B). By concentration (12) of Proposition 7, we have
cx(r)
(r)r)
a a 1(x, E B) s
8e(ai, ar (B)) p(B) (rx((r)
Σ
(r)(()
+ (Iog(T) V Log(T) ((((()))))s(rr))))))))))())))))) p(B)
We first show the concentration error terms the R.H.S. above negligible with respect the desired bound (19). The log(T) term is clearly of the right order, whereas the other term is handled by Lemma 10, by which
V (ee(r) se(r)) p(B)= S cT((e(r) se(r)) -(()) K
2i < 023 02331" 7d (ex(r) s(()) Kate
4/2
By similar arguments to before, where we write e *r(r) EiEPHAsSS(ee)) Tirr, and use
the sub-additivity of the function + नम the above is of the right order w.n.t. (19).
Thus, going forward, by the strong density assumption (Assumption 2) and in light of (19), it suffices to show for any fixed arm a E [K] (which we will take to be a, (B) in the end):
es (r(r)AE(B.a)
Σ
Σ
14d (T - T,) T,) 24d K Kate,
(28)
iEPHASES(EE.))
29

---

where E(B,a) a) is the last round in block (sz(r), ee(r)] for which a E Amaster (B).
This aggregate gap is the most difficult quantity to bound since arm of may have been evicted from Amaster (B) before round and, thus, we rely on our replay scheduling (Line 6 of Algorithm to bound the regret incurred while waiting to detect a large aggregate value of 6, (,(a), a).
In an abuse of notation, we'll conflate (r(r) with the anticipated block end time based on st(r); that is, the end block time if no episode restart occurs within the block. Now, for each phase [T,, 7++1) which intersects the block [se(r), (e(r)), our strategy will be to map out in time the local bad segments or subintervals of [T,, T ) where a fixed arm incurs significant regret to arm of in bin B, roughly in the sense of (*). The argument will conclude by arguing that a well-timed replay is scheduled w.h.p. to detect some local bad segment in B, before too many elapse.
In particular, conditional on just the block start time se(r), we define the bad segments for fixed arm a and then argue that too many bad segments w.n.t. a clapse in the block's 's anticipated set of rounds (r), ee(r)], then arm a will be evicted in bin B. Crucially, this will hold uniformly over all arms a and, in particular, for arm a = (B). This will then bound the regret of (B) in block [se(r), ce(r) in the sense of (28).
Notation, Going forward, we will drop the dependence on the level r, block [s)(r): (r)), and episode (e,)441) in certain definitions as they are fixed momentarily. Recall from Appendix D.2 that at is the local last safe arm of the last round t, (B) E [Te, Te+1) such that Xx,(B) E B where B is the bin at level -T containing Xt (see Definition 9).
We first introduce the notion of a bad segment of rounds which is a minimal period where large regret in the sense of (+) within bin B is detectable by a well-timed replay.
Definition 12. Fix an arm and sr(r). and let T(+1) be any phase intersecting [se(r), ee(r)) Define rounds ss,o(a), (,), (a), st,((a)... E [&e Te, T(+1) recursively as follows: let s,,o(a) te V To and define st5(0) as the smallest round in (sij-1(a), T441 Aee(r) such that arm satisfies for some fixed 621 > 0:
Σ (
8elaf, a) 2 621 log(T) (a) (1)- 2td Kataa
(29)
Otherwise, we let the 8i.(a) = T++1 1. We refer to the interval - st.((a) as a bad segment. We cull (s1)-1 (a), 8ig (a)) a proper bad segment (29) above holds.
will in fact suffice to constrain our attention to proper bad segments, since non- pooprroprr bad segments (a.j-i(a), si.(a)) (where sa) T,+1 1 and (29) is reversed) will be negligible in the regret analysis since there is at most one non-proper bad segment per phase [r., T++1) (i.e., the regret of each non-proper bad segment is most the R.H.S. of (28)).
We first establish some elementary facts about proper bad segments which will later serve useful in analyzing the detectability of (x) along such segments of time.
Lemma 13. Let s(,++(1))) be a proper bad segment defined w.nt. arm a. Let m N (0) be such that T (ssstiaa) (1)(() = 2 m Then, for some C25 = C25(d) > 0 depending on the dimension d:
(1) Σ
8e a) 2 c2s log(T) K K (s1,41(00) - (a)
(30)
tmsii (a) p2 (22mm22)224)) 21
Proof. First, may assume s1.j+1(a) si.((a) 2 4. K by choosing 624 in (29) large enough (this will make m - 2 0).
First, observe by the definition of T (=),)1(l)=ss, (Notation 1) that
12(mm-1)(2+)) < (1))+1(a)= ssi((a) < (2+()
(31)
30

---

Now, let 3 = s1,++((a) (Definition 12) that:
(2(m ((((m))))+)))- Then, we have by (29) in the construction of the (t.(sa)ss
$6 (a)
(1)41(()
ae(d)aa)=
Σ
a)
Σ
ac(af,a)
(a)
1=),)(a)
024 log T [=
((Ls++1(a) 8
81 (a)) 248 sوا(a) x
Let Let (1)+1(a) - 8i, 8i.5(() (a). Then, we have by (31) that:
ma.(a)) k2m(2+d) á (1) mzy(a) (2) 22240))) S (1-224)(11-22222))))
Plugging this into our earlier bound the constants in our updated lower bound scale like:
1 1- 1-(1- 22(2+d)+1
1
> O.
But, this last term is positive for all E NO {0} and only depends on d.
Lemma 14 (Aggregate Gap Dominates Concentration Error). Fix bin B at level Let [st. (1,)+((a)) be a proper bad segment and let B' 2 B be the bin at level (au where 3 = (1)+1(()) - K2(m (m- 2)(241)-1 is in Lemma 13. Then, for some c2a 0:
# (a)
(.(. 1(x, E B'} c2e (Iog(T) K (no (1.+1 K)
r(BB) ny (15, s1)++(a))))
Proof. We have via concentration ((12) of Lemma 8), Lemma 13, and the strong density assumption (Assumption 2):
(a)
$1.41(a) (a)
aa(a 1(x, E B}
de(af, n(BB)
(og(()) + Vlgg(T) (s 8) (BB))) 1-d 02 [og((T) + log(T) (s1)+)()))+))))) B) m(B²))
2 C25 log log(TT) st (a) whd K2-
Now, the first term the final R.H.S. above dominates the other two terms for large enough C2s and via strong density assumption (Assumption 2). Thus, it suffices to show
C25 (Tg(()))sss1(())) siy(a)) K H
C27 (log(T) K (n (13, sL,ii (a)) V K) + +r()+)BBmmm))) (IB, s11+1(())))
(32)
We first upper bound the "variance" term, the first term the R.H.S. above. Let W = 81 (a)
-5.
By Lemma 10, we have
log(T)) /K K (nv ([š, (a))) K) s ca (Iog(T). W शं. K 2t
log 2/2() K log(T)
1/g)/4(T) K
1434/4 1/2
W224
Now, we also have
sij+i(a) (a) 2 W = >log(T) (sis+1(a) sey sa)(a)) K 244 2 log(T) Waa K
31

---

Next, we note that by the definition of a proper bad segment ((29) in Definition 12) that
2 2- (*Lssti(a) sl)(a)) 2
Σ
1t4 (a a) 2 024 log(T) (8a5+1(a) - 8i,1 si,((a) ( K Kata,
[=)
This implies (st.+1((a) S1.((a))
a log(T). By similar reasoning, we have (1.)+1(a) (L)(a) 2 C2g K. From this, we conclude for C24 > 0 large enough:
log(T)- ($1,++1(a) - So.s sa) she Katd 2 log (T) + K log(T) + log
1td
5/4 (T) K 1+34/4 1/2
W 2+4,
Thus, (32) is shown.
Now, we define well-timed or perfect replay which, if scheduled, will detect the badness of arm (in the sense of (5)) in bin B over proper bad segment (a), St.--1a)). The simplest such perfect replay is one which is scheduled directly from rounds (a) to (a)) We in fact show there is a spectrum of replays (of size the length of the segment (88..+1 (a) (a)((a))) each of which can detect arm is bad in bin B. possibly by using a larger ancestor bin B' B.
Definition 13 (Perfect Replay). For fixed proper bad segment (ai) (a)), define + 1, (i5++t((a)=
perfect replay Base-Alg (famns M) with baan E [st.jti(a)= (2 K2 [2(m=2)(++))]] (where m E N U (0} as in Lemma 13) and Laan +M 2 s
The following proposition analyzes the behavior of perfect replay and shows, if scheduled, it will in fact evict arm from A(B) within a proper bad segment (a), (t.)+((a)).
Proposition 15 (Perfect Replay Evicts Bad Arm in Proper Bad Segment). Suppose event & n& holds (see Notation 2). Fix a hin B at level r. Let (stg(a), (a)) be a proper bad segment defined with respect to arm a. Let Base-Alg (Iaan, M) a perfect replay as defined above which becomes active at tsaa (i.e., Z Z. for fixed integer M 2 sig+1(a) sa,((a). Then:
(i) Let B' be the bin level (=-)L,(a) where : 8i.j+1 (a) (2((m2)(2+-)---- (m E (N is as in Lemma 13), as in Lemma 14. Then, there is "afe arm" " oF which will not be evicted from A(B") by Base-Alg (fatats M) ) (or any of its children) before round 1 (a) +1.
(ii) If a E A for all rounds t E [3, (1)+(()()))) where X₃ E B, w then arm a will be excluded from A(B) by round s1)+1(()..
Proof. For (i), we can define the "safe arm" o² (B') in a similar fashion to how of was defined. Let t, (B') be the last round in [š, (1)++(aa]] such that Xx,(B)) E B'. Then, since st.++ (a) T we have that at round t,(B), (B'), there is a safe arm a² (B') which does not satisfy (+) for any bin B" intersecting B' and interval of rounds I C [8, $1.5+1(a)) (a)]. Once Base-Alg (fstnns M) is scheduled, it (or any of its children) cannot evict arm a² (B') from B' doing would imply it has significant regret in some bin intersecting B' (following the same calculations as in Lemma 11).
We next turn to (ii). We first suppose that arms a is active in bin B' from rounds & to i (we'll carefully argue later this is indeed the case). We first observe E1 (a)(), [F-1] (c( for any round E [3, [.)]+(((a]]] such that X, E B'. We next observe that:
s1a+1(a)
sas+i(a)
(a)+i(a)
Σ Se(aa () E B >
S, a)x E B7
Σ
de (B)))
B).
(33)
By Lemma 14, the first term the R.H.S. is at least
C26 (1o((T)) K. (nB ([5+ v K) + r(B')- ([3)
32

---

Meanwhile, the second term on the R.H.S. of (33) is at most the same order by the definition of a² (B)) Thus, choosing C26 large enough gives us that
(1)
(B))))))) 1(x, E B 2 C29 (Tog(T)// K. (n (13, (15++1a)))) v K)
+ +r(BB) ngr ((8, (1)++
Then, combining the above with our eviction criterion (5) and concentration (10), we have that arm will be evicted in the bin B' 2 B at level (())) by round s.)-1(a).
Finally, it remains to show that, within Base-Alg (leat M)'s play, arm will not be evicted in any child of B' before round s This will follow from the fact that any perfect replay must use level in R. of size at least rw. In particular, by Definition 13, the starting round baart is "close enough"
to the critical round (a)
(22(m-2)22-0) so that it will not use different level than the perfect replay which starts exactly this critical round.
Formally, we have that the smallest level perfect replay can use is Tw where W = K. 2m(-2))))+))
Next, note that (a)+ Estart S K 20mmm(((222))))
and so
K
K
> 2-
$ (a)
ittrt
2 n- ()4
Thus, rw 2 2 (m (m-2), On the other hand,
K
{ (m- 2 2m(m3)))
s1.+t(aa
2 2-
242
Thus, 2- (m--2) (1) is also the level used detect that arm is bad in bin B', Thus, conclude that ri is no smaller than the level (a)- used to evict in bin B'. This means arm cannot be evicted in child of B' before round $1.f+1 (a), if is not already evicted in B. O
Next, we show for any arm a (in particular, a a B)), (B)), perfect replay characterized by Defini- tion 13 is scheduled with high probability if too many bad segments w.r.t. elapse, thus bounding the regret of to a² (B) over the phases [T,, T++1) intersecting block (e(r),ee(r))
D.7 Bounding the Regret of the Last Master Arm (B) to the Last Safe Arm of
Next, we bound the the regret of a fixed arm a to af over the bad segments w.r.t. a in B. Recall from earlier (28) that remaining goal is to establish the following bound for every bin B E T, level
r:
((())AB(B.a)
E
max KE(K]
Σ
(((), 1{)
Σ
(T++1 - Tz) K Kata,
(=se(r)
(EPHASES(EMr)
where E(B,or a) is the last round in block [se(r), ce(r)] for which Amaster (B).
Note that the bad segments (Definition 12) are defined for level r, block start time se(r), and phase [T,, T.+1). In particular, they are defined independent of any choice of bin B at level r. We'll similarly define a bad round s(a) which will indicate when "too many" bad segments w.r.t have elapsed, irrespective of choice of bin B. Then, we'll argue that for any bin B at level r, E(B,a a) S s(a).
It should be understood that in what follows, condition the block start time (r). First, fix an arm a and define the bad round s(a) > se(r) as the smallest round which satisfies, for some fixed c30 0:
(ss)+1(a)) sa.
C30 log(T) - tx) 2
(34)
(1,))
where the above sum is over all pairs of indices (i.j) E N x N such that (st,(a) (a), si.j+1 (a)) is proper bad segment with s1s+1(a) < s(a). We will show that, for any bin at level r, arm evicted from A(B) episode i with high probability by the time the bad round s(a) occurs.
33

---

For each proper bad segment [s,](a), s1.4+1 (a)), let ( = s15+1(a) - (2((==2)(++)) 2)(2+d) -1 denote
the "critical point" of the bad segment as Lemma and also let miy = 2" where n E N satisfies:
2" > st.++ - s1,(()) > 2n
Next, recall that the Bernoulli M., decides whether Base-Alg (t. M) activates at round & (see Line of Algorithm 1). If for some E (a), (a) where (a) = 8i.+1 1 (a) (2(m-2)(2++) + 1, Zm....t f 1, i.. a perfect replay is scheduled, then will be evicted from A(B) by round (1))+( (Proposition 15).
We will show this happens with high probability via concentration on the sum E(e Ee Zm
where J, i, t run through all [$.j(a), 5i, and all proper bad segments [ st.j+1 (a) with si.++ (a) < s(a). Note that these random variables, conditional on Xr, depend only on the fixed arm a, the block start time sr(r), and the randomness of scheduling replays on Line 6. In
particular, the Zm,,gt are independent conditional on iz.
Then, Chernoff bound over the randomization of CMETA on Line 6 of Algorithm 1 conditional on le yields
E|Σ (1,f) Ee Zmazy (e(r), Xyl
P
Σ (K.5)
Zmiigst S
sE(r), XT
2
BlC Ee Smasie (e((r), Xrl
$ exp
We claim the error probability on the R.H.S. above is at most 1/T To this end, we compute:
(a)
Σ
Σ
Zm se(r), XT
2
2nd
24
miij
(i.1)
(i.f) t (a)
Lid
mijj
2
s(a)
C30
log (7):
where the last inequality follows from (34). The R.H.S. above is larger than 24 log" for c30 large enough, showing that the error probability is small. Taking a further union bound over the choice of arm [K] gives us that E(,,)) E, Zm....t > 1 for all choices of arm (define this as the good event (r)) with probability at least K/TS.
Recall on the event & O &2 the concentration bounds of Proposition and Lemma 8 hold. Then, on must have for each bin B E T, at level r, E(B,a) a) I s(a) since otherwise
E & n (r)() would have been evicted in A(B) by some perfect replay before the end of the block ex(r) by virtue of E(.)) E, Zmiga 1 for arm a. Thus, by the definition of the bad round s(a) (34), we must have:
Σ
(#15+1(a) - sa.(a)) S cgo (og(((((((e()) - 4x) #
(35)
(eL,(o), (1()))))) (e(a)<ee(r)
Thus, by (29) in Definition 12, over the proper bad segments [s),((a), (2.++(())) which elapse before round (x A E(B,a) a) in phase [Ti, T++1) )) the regret is at most
Σ log(T) K Kslam (1,)
24d
Ht < log2( (T) Kala (ec(r) - tx) tz)
Over each non-proper bad segment (a), 81 (a)) and the last segment
Itd
the regret of playing arm to of is at most log(T)) K अंं m.. since there is at most one con-proper bad segment per phase [T,, 7141) (sce (29) in Definition 12).
34

---

So, we conclude that on event &1 n Eg (s(((r)) for any bin B E Tr
(B)AB(B
Σ
5e a) I 2030 log (T)
Σ
(T=-1-T;)
K
max KE[K]
(EPHASDS(C.r)
Let event G = & Then, taking expectation, have by conditioning first se(r) and then event & n Ea(e((r))
cc(r)AB(B,a)
E
Σ
de(af,a)
1(9) X
aE(K]
(=
(((r)AE(B,a)
< Bse(r)
E
max 11g 1(G
Σ
be(a), (B) se(r) XT
LE[K]
t=a((r)
T Be((r)
E
1 1(9
sE(r)
XT
We first handle the first double expectation on the R.H.S. above. We have this is at most
s 2cso log (T))ae(r)
E
((gnes(t))
E
Kzta (T141 T3) sta se(r)
X
(EPHASES(Err)
s 2C30 loogogg2ggog (T)E
1[9}
Σ
(T41 T.) Ltd
2id
XT
(EPHASES(E.r))
where in the last step we bound 1(g n (s(e(())) < (99} and apply tower law again, The above R.H.S. is of the right order w.r.t. (19), So, it remains to bound
119 (00))) s((r)) Xr |xr]
T B (r(r)
E
We first observe that events G and (T())(T) are independent conditional on Xy and (r(r) since the former event only depends the distribution of Y.,o))...,, while the latter event depends on the distribution of the Bernoulli's (12 (which are independent). Then, writing 11g n (5(ss(r)) ([9) ((E)(s))))), the above becomes most [[] (K/T²) Xr] which also of the right order w.r.t (19).
E Proof of Corollary 5
The proof of Corollary 5 will follow a similar fashion to the proof of Corollary 2 in Suk and Kpotufe [2022], which relates the total-variation setting. A novel difficulty here is that notion of significant shift 7, (Xr), i.(x,) (Definition 6) depends on the full context sequence Xy, and so it is not clear how the (random) significant phases [T:(X (XT), Ti+1 (Xr)) relate to the total-variation Vy, which is deterministic quantity.
significant shifts in the non-stationary MAB
Our strategy will be to first convert the regret rate of Theorem into one which depends on weaker worst-case notion of significant shift which does not depend on the observed Xy. Although this notion of shift weaker, it will be easier to relate the total- variatio quantity Vr.
Recall that 5 (z) max.'elk &5 (Ir) and 8 (xx) fe' (x) - (x: are the gap functions in mean rewards.
Definition 14 (worst-case sig shift). Let To = Then, recursively for 2 O, the (i (i+ 1)-th worst-
significant shift is recorded at time 71t1. which denotes the earliest time i (7., T such that there exists x E X such that for every arm a E [K], there exists round s E [7,, F]. such that
(x) N
242
1-
35

---

We will refer to intervals (Tt, F O, as worst-case (significant) phases. The unknown number of such phases (by time T) is denoted I Tup 1, whereby (+ " (bpp+ for Epp+ = T + denotes the last phase.
We next claim that
LAXT) Σ (T++ Ti (XT)) 2id 1=0
Lppp
ExT
S C24
Σ (T++1 T;) 213. 2=
This follows since the experienced significant phases [T, (Xr). Ti+1 (XT) interleave the population
analogues [Fr, F++1) in the following sense: each significant shift Ti+1 (XT) for each arm [K].
there round (XT),, Ti+1 (XT)] such that for (X
K
This means there
T-+1-
(Xr) since the criterion of Definition 14 is triggered at æ = X This in turn allows us to conclude that each worst-case
must be worst-case significant shift fy in the interval [T:((g) (Xr), Ta+
significant phase [7,, Fe41) can intersect most two significant phases [T, (Xr), T<+1 (X))).
Thus, by the sub-additivity the function x + (dropping dependence on Xy L, T3 to ease notation):
1+4
Σ 0
Ts+1
T;)
Σ
(51)) [T. R42)
0m
ff 7++)
Trp
(fz+1 - [ラ) 7,) 2/2
I C24
1=0
where we use Jensen's inequality for aP + 1/ S 21-P(a step to re-combine the subintervals of each worst-case significant phase [T], ft+1). Then, suffices to show
(a + b) for E (0, and a, 2 in the last
Typop
- Kata Tzta. KIta + (Vr K)Jaa Tate.
(36)
To start, fix worst-case significant phase [ 7+11) such that T441 < < +T+1. By Definition 14, there exists context E X' such that for arm E argmaxne[K] lhg, (x;) we have there exists round [ri, T+11 such that:
K
(x;)
(z:)
T++1
Tr
On the other hand, 0%; (z,) = 0 by the definition arm a, being the best at xy at round 7t+1- Thus, letting à E argmax, e [K] f (x;) be an optimal arm at I; at round t;, we have:
K
5ā. Fets
8ot (x.))
5ār.0 (x+)-
7+t1
For each round = ,, define the function H; : [0 1 1-1,1]] by H,(X,Y) = y:, ya, which is the realized difference in rewards between arms û; and a, within the reward vector Y. Then, using this notation and summing the above display over worst-case phases i E [Lppp].
get:
Lepee
(X,, YO]]
Ti
(37)
We next recall from the variational representation of the total variation distance [Polyanskiy and Wu, 2022, Theorem 7.24] that for any measurable function
x [0, 1 + [_,1]]
1
|D: - P.-1lTTV 11 2 (Exx, I. 1)DD [H Y. ) E(x.y)> (H Y.)l) (38)
36

---

Thus, plugging (38) into (37), we get
T
K
T-m
2 ID: DD-11llv
(39)
T++1
[=2
Remark 7. Note that it is crucial in this argument that the functions H₃ do not depend on the realized rewards Y contexts X, any particular round t. Rather, H; only depends the arms a a, which in turn only depend on the mean reward sequence (ft) In other words, the above step does not follow if az, ag were defined in terms of the experienced significant shifts T (XT)..
Now, by Hölder's inequality for p E (0, and g (0.
1+d 2+d
Lyee
T41 - 7,) 2 & T 222
P
( K
1-p
Σ
K 24d (7+ F.) 7/)
(Frt (F
7t) to) +
In particular, letting = 3+d and g = [2+][3++] and plugging in our earlier bound (39) makes the above R.H.S.
T
K मंत + VT
K K . T
F Proof of Theorem 1
We first note that it suffices to show (3) for integer L [0, CN as lower bounds for all other follow via approximation and modifying the constant e > in (3). Thus, going forward, fix V E [0, 7] and I. Z n [].
At a high level, our construction will repeat + 1 times a hard environment for stationary contextual bandits. In particular, within each stationary phase of length T/(L + 1) one is forced to pay regret of (T/(L+) + 1)) + summing to a total regret lower bound (L 1) (T/(LTT/LLL + 1)) 2
11+11)24 T2244.
To obtain the lower bound expressed in terms of total variation budget V in (3), we will choose 2id
I, x V V T and argue that the actual total variation VT (Definition 5) is at most V in the constructed environments for this choice of This is similar to the arguments of the analogous dynamic regret lower bound [Besbes et al., 2019, Theorem 1] for the non-contexiual bandit problem.
We start by establishing lower bound for stationary Lipschitz contextual bandits. The construction identical to that of Rigollet and Zeevi [2010, Theorem 4. I.. We provide the details here to (1) highlight a minor novelty in circumventing the reliance of the cited result positive "margin parameter" a > 0 and (2) to assist in later calculating the total variation Vy.
Remark 8. There are other stationary lower bound results for Lipschitz contextual bandits using similar constructions and arguments, but with context marginal measures μ.x of finite support [Foster and Rakhlin, 2020, Theorem 2; Slivkins, 2014, Theorem 7J. To contrast, our construction involves setting p.x to be uniform on [0, 1]d, thus satisfying the strong density assumption (Assumption 2).
Proposition 16. Suppose there are K = 2 arms. Then, there exists a finite family of stationary Lipsehitz contextual bandit environments E(n) over rounds such that for any algorithm я taking as input random variable U, we have for some constant e >> O and environment E generated uniformly and independently (of n. U) random from En))
(E- [T), c-n3 334
Proof. Let the covariates X, be uniformly distributed [0, 1]d at each round t E [m], that μx = (0, 3) For case of presentation, let reparametrize the two arms as + and -1.
37

---

At each round & E [n], let arm -1 have reward Y Ber(1/2) and let arm +1 have reward Yt ~ Ber(f where f X' + [0, 1] is some mean reward function to be defined. Let
M =
3e
We next partition X' = [0, 11 into regular grid of bins with centers @ = {qI,.... 9 }. where qs denotes the center of bin By, k ===,, 1....., MM. k ( ka) {1,.... Mjd we define the bin Bg coordinate-wise as:
Concretly, re-indexing the bins, for each index
k
he M
d
Bx x E:E::
M xe 5
Define Co = 1/4. Then, let ó Rd + RR be the smooth function defined by:
{1
||
0 S || S ||~||x > 1
(xx)
It's straightforward to verify ø is 1-Lipschitz over IRd. Next, to ease notation, define the integer = Md. Also, define E,, = f-1,1)m and for any w E Im define the function fw on [0, 1] via
[u(x) = 1/2 +
Wj (z(),
j=1
where x)(x)) = M-1.C... M(M- -x (j)) 1fx E B3}- Then, the optimal arm at context a E X in the convention sgn(0) = 1).
this environment is given by m3 =gn)) (f() - 1/2) (where If By, then jj_ (x) wj-
Then, define the family C of environments induced by for for w E 2m Note that Su. also 1-1 1-Lipschitz for all w. Next, let Int(B,) be the foo ball centered at qu of radius 237 (i.e., Int(By is ball of half the foo radius contained in B,). Then, by the definition of σ(x) above, we have for any E Int(B,) and any j E [m]:
(x) - 1/2 2 M C2/2.
Next, we bound the average regret w.r.t. a uniform prior over the family C of environments as:
EjecE
ff(x)) 1/21 (X,, # क (Xx)) Z
t=1
Co
E recE
17, + n"" (X,), X, E IBt)
(40)
2M
where the outer expectation is over an f E C chosen uniformly at random from C.
As recall M x मेत will suffice to show the expectation on the above R.H.S. is of order Q(n). This will follow essentially the same steps the reduction to hypothesis testing in the proof of Theorem 4.1 in Rigollet and Zeevi [2010]. In particular, we note the KI. divergence calculations for the induced distributions over observed data and decisions allows for the additional randomness U without consequence, as it's ignorable by use of KL chain rule. The only slight modification we make in their argument is to account for the fact that we only count rounds when X, Int rather than when X, E By. This will, in fact, only affect constants in the lower bound as B, and Int(B,) have similar masses.
Going into details, the following notation will be useful.
Notation 3. Let Wi-s] be w with the j-th entry removed, and let w (wi,..., 1, Wj+l.-... wm) for i E {+1). Also, let Pa,f, Br, denote the joint measure and expectation, respectively, over all the randomness of at and observations within an environment induced by mean reward function f.
38

---

Then, the aforementioned reduction to hypothesis testing in the proof of Theorem 4.1 of Rigollet and Zeevi [2010] yields the following lower bound on (40):
C
Σ
exp (-
4
Naw (aalw)) (w),
(41)
2m M
4M
3M2
-1-l
m0
where, letting X Mx be independently drawn context,
Σ (x)(() = 1, BJ)
(W)((W) = Entsari u[-s]
Ex
Nj,((w) = ou Ex
Σ (m) x. Int(B;))
We next claim (,x((w) NA. / /2d, summation in the above formulas. In particular, we have
which will follow from swapping the order of expectations and
(w)
(x((X) = 1|x E Int(BB)) px E Int(BB)) P x.
=
1=1
1 d
P (Tt(X)
1|x E (nt(
2M
1
P Pr.fa F
(To(X) = 1|X BB) (x E B3)
2d
NN (2)
Thus, (41) becomes lower bounded by
C$
4
Nir((w)
Σ
Ng.x(w)
exp
2
M
4M
3M2
2d
WI-j)Enm-
C
2
8 2d
M
#20
inf
4Md
exp
3M2
- +2].
z).
The above R.H.S. optimized x = 3M² log (M)2TZ) Plugging this into the above along with our choice of M detined earlier gives lower bound of (()2))).
1+
lower bound immediately follows by lower bounding the total regret over random environment formed by concatenating T.+ 1 i.i.d. sampled environments from Uni + 1))). Any such resultant environment clearly has at most L global shifts. Note that the average regret (w.rt. the random environment) over any stationary phase of length IiT
Given Proposition 16, the (L+1)
T+
is lower bounded by (I+1)
regardless of the information learned prior that phase, such information can be formalized as exogeneous randomness U in Proposition 16.
Next, we tackle the lower bound V 3t4 in terms of total-variation budget V. First, if V < O(T 2ंट ), then we're re already done as the desired rate
T + T ssaa) a (LL 1
is minimized by the first term which is of order O Thus, using Proposition 16 with single stationary phase E(T) gives lower bound of the right order in this regime. Such an environment clearly has total-variation Vr = 0 < V.
3id
39

---

2
Suppose then that V 2 T =tz
Let
A
T and consider ++1 p. P-T/A
stationary phases of length A, for some fixed constant have the regret lower bounded by
0. Then, by the previous arguments we
T
T
(L (L+1)
T 344
V
A
2 344
(T/V)
344
Additionally, T V dominates T since V 2 T मेर. Thus, the regret lower bound is proven in terms of V.
remains to verify that the total-varian antl-vvriationn Vr at most V in the above constructed environments so that any such environment lies in the family P(V, L.).
Clearly, the "instantaneous rotal-variation" [|D, 12---111 1|v 0 for all rounds / being the start of a new stationary phase. On the other hand, for round marking the beginning of a new phase, we have that since conditioning increases the total-variation [Polyanskiy and Wu, 2022, Theorem 7.5(c)), the instantancous total-variation is at most:
DD Dr-1lhrv S Ezzax [| = =) Dy-1(Y--1(Xi-= = =x][[v].
(er(f((z)) have the R.H.S.'s inner TV quantity is just the total variation fi-1 (z)] Carefully analyzing the variations in the constructed Lipschitz reward functions in the proof of Proposition 16 reveals this TV between
Since Y between Bernoulli's m=)) I (I)
Bernoulli's 's is at most phases, we have
(3e)
[++1
Fe
Then, summing the instantaneous total-variation over
3tप (3e)
L+1
Vr S (L + +1)
2
T
(3c)
S p2 (L + 1) 2
T
24d
2
1-n
T
V,
where the third inequality follows by letting p be small enough constant.
40


Reviews:
[{"review_id": "mo9DR53Mfz", "reviewer": "Reviewer_PUca", "summary": "This paper studies nonparametric contextual bandits where the mean reward functions can change over time. A key assumption is that the rewards are Lipchitz in context. The authors then adopt a typical approach to discretize the context space into bins. The notions “significant regret”, “unsafe at context”, and “experienced significant shift,”; in particular, an experienced significant shift implies a change in the optimal arm in a particular bin. The authors then propose an algorithm Contextual Meta-Elimination while Tracking (CMETA) and establish regret bounds in terms of the total number of “experienced significant shifts.”", "questions": "My main concerns were raised in the “Weakness” section. To reiterate:\n1. Besides discretization of the context space into bins, how does CMETA and its analysis differ from that introduced by Suk and  Kpotufe (2022)?\n2. It would be very helpful if the authors could elaborate on the “choice of level” in Algorithm 1 (CMETA) and how the regret bound established in Theorem 3.1 depends on the level.\n\nA remaining question is:\n-  In Corollary 4, it seems that if $\\tilde{L}$ grows linearly in $T$, the bound on cumulative regret becomes linear in $\\log^3(T) T$, in bandits where rewards are bounded in $[0, 1]$ (and cumulative regret is at most $T$)?\n", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper is well-organized and introduces both a notion of “experienced significant shift” and an algorithm, CMETA, accompanied with theoretical guarantees. ", "weaknesses": "My major concerns centers around the comparison of CMETA and its analysis to the algorithm and regret analysis introduced by Suk and  Kpotufe (2022), and the presentation of the theoretical results. \n1. Besides discretization of the context space into bins, how does CMETA and its analysis differ from that introduced by Suk and  Kpotufe (2022)?\n2. As for the presentation of the results, we take Theorem 3 as an example. First, the notation is inconsistent: the notation $\\tilde{L}$ is introduced in line 214, and in Theorem 3 it is appeared as $\\tilde{L}$ in line 248 but $\\tilde{L}(\\mathbb{X}_T)$ in line 250. In addition, $\\tilde{L}$ is dependent on the discretization of context space into bins, which is determined by level $r$ in Algorithm 1, yet $r$ does not appear in Theorem 3.1? Moreover, could the authors elaborate on “choice of level” in Section 4 on how the level is adaptively chosen? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_Key Difficulties_: Although we agree with the reviewer that discretization is a natural approach appearing in fact in all past works on Lipschitz contextual bandits, this is not the main technical difficulty, neither algorithmically nor analytically: the main difficulty is to understand the level of discretization required for the specific setting, i.e., what cell width to employ in different parts of space (e.g., Rigollet & Zeevi, 2010; Perchet & Rigollet, 2013), and how to automatically infer such cell-width from data (Slivkins, 2014). This is in fact the focus of papers on the subject, and is by now well-understood in the stationary setting to tightly depend on the time horizon. In the non-stationary setting considered here, however, such automatic choice of discretization is now even more difficult: we need to not only make a choice of level in stationary phases, but also, in order to detect stationary phases of varying length, we need separate choices of levels commensurate with the unknown starts of new phases. The main challenge therefore is in understanding how to design and schedule such automatic choices of levels while maintaining optimal performance w.r.t. the unknown number and positions of stationary phases. This is explained lines 318-341 of Section 5.\n\n_Notation and Choice of Level_: We apologize for confusing notation; we drop the dependence on ${\\bf X}_T$ in $\\tilde{L}$ in some places for ease of presentation (see Lines 211--212).\n\nNote that the notion $\\tilde{L}$ of experienced sig. shift (Definition 6) is independent of any fixed level (and thus of the level used by the algorithm), which is part of its appeal. This misunderstanding is our fault as we often discuss $\\tilde{L}$ in terms of levels used by the algorithm. As said above, such choices of level are the main technical apport of our analysis.\n\nThe \"choice of level'' is adaptive in the sense that it does not depend on a fixed horizon $T$ and so can \"adapt'' to the minimax regret over unknown episode durations (the earlier Perchet & Rigollet, 2013 employ such a time-varying level in the stationary setup).\n\n_On $\\log$ Factors and Sublinear Regret_: It has unfortunately become common in bandits to write regret bounds this way. We apologize for the confusion this may have caused. Our regret is always upper bounded by $T$ and not by $\\log^3(T) \\cdot T$ in the worst case, and we'll add an indicator to our bound to express when there's $\\log$ factors."}, {"review_id": "AUWBxbSefa", "reviewer": "Reviewer_o8kG", "summary": "This paper studies nonstationary contextual bandits. In particular, a new notion of \"significant shift\" is introduced (Definition 6) which accounts for shifts in the distribution localized at the possible actions and with significant magnitude. First, the authors derive a lower bound for existing definitions of shifts (Theorem 1) and provide an oracle algorithm to achieve it. Then, after introducing the new notion of shifts, they derive an algorithm which adapts to it (i.e., which does not require the time indexes of the shifts), see Theorem 3.", "questions": "- In this paper, the available actions are the same at every time steps. Could the authors think about a generalization when the action set changes over time? In particular, would it be possible to restrict the significant changes only to the playable arms?\n- Could the Lipschitz assumption be removed? \n- In Definition 7: does $\\cal{G}_t$ always exist?\n- Do authors have in mind simple examples of $f_a^t$ where both switches characterization drastically differ?\n- If I'm not missing anything, it seems to me that no definition of switch implies the other. Then, I find it a bit misleading to compare results all along. It should be made clear that the two are two different parameterizations incomparable in general (I agree on the identity $\\tilde{L} \\le L$)\n- Assume that changes have small magnitude (e.g., small drift at each time step) or do not apply to every arms (but only to the best let say), is the regret of CMETA not impacted by those switches?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The topic is of interest to the NeurIPS community\n- The paper is globally clear and well written\n- The intuition and analysis are sound\n- Authors constantly compares their results with existing ones to position their contribution", "weaknesses": "- The paper lacks experiments. Since the authors provided a detailed algorithm, I find it disappointing that no experiment is carried out. It would be of particular interest to study the behavior of the different algorithm depending on the types of switches\n- I feel previous paper on significant switches could be discussed a bit more, to highlight the changes and challenges raised by the contextual setting\n- No lower bound for the proposed definition of switches is provided\n\n\nMinor:\n- Abstract: MAB is not defined yet\n- Section 1.1: linebreaks do not seem necessary to me and make the reading less fluid\n- When citing several works, the chronological order is preferable\n- Equation ($\\star$): what is $r(B)$?\n- Lines 242, 252: are the log factors omitted?\n- l. 305: ut\n- l. 316: $\\approx$ could be avoided", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for pointing out typos, writing suggestions, and many careful questions.\n\n**Weaknesses**: \n\n_Experiments_: We'd like to emphasize the main contribution of the paper is theoretical, rather than proposing a new algorithm. In fact, the algorithm in the paper is of a theoretical nature that only serves to drive the main theoretical message: for the well-studied setting of contextual bandits with Lipschitz rewards, both the form of the optimal regret and whether optimality can be adaptively achieved have remained open; we have resolved these questions.\n\n We agree with you, however, that an eventual goal of this fledgling line of work is to develop practical procedures, and we admit the state-of-the-art is still far from this.\n\n_Lower Bound in terms of $\\tilde{L}$_: The construction of the lower bound (Theorem 1) in terms of $L$ global shifts and total-variation $V_T$ in fact satisfies $\\tilde{L}=\\Omega(L)$. Thus, this implies a matching lower bound $T^{\\frac{1+d}{2+d}}\\cdot \\tilde{L}^{\\frac{1}{2+d}}$ of the same order as our upper bound (Theorem 3), up to log factors. We'll make this more clear.\n\n**Questions**:\n\n_Changing Action Sets_: This is an interesting future direction which is beyond the scope of our paper. Even in the simpler MAB setting, such results are unknown as there are added difficulties with changing action sets. For instance, with changing action sets, the _safe arm_ (i.e., the arm not yet incurring significant regret within a phase) and a bad arm with large regret may not be available on the same rounds, a fact crucial to the significant shift analysis of Suk and Kpotufe, 2022. This makes it unclear how to generalize key parts of the regret analysis.\n\n_Removing Lipschitz Assumptions_: We can generalize all the results to the setting of  $\\alpha$-Hölder continuous rewards with $\\alpha\\leq 1$. We'll include a remark to this.\n\n_Existence of Good Arm Set_ $\\mathcal{G}_t$: Yes, $\\mathcal{G}_t$ always exists and contains at least one arm by the definition of experienced significant shift (Definition 6).\n\n_Instances where Switch Characterizations Drastically Differ_: As a simple example, if there were no changes in best arm at any context $x$ but changes in rewards at every round (e.g., the rewards of all arms change together by the same amount) then we'd have large total-variation $V_T=T$ and global count of shifts $L=T$ versus $\\tilde{L} = 0$ experienced sig. shifts. Going even beyond this, even a tighter global count of best-arm changes $S := \\sum_{t=2}^T {\\bf 1}(\\exists x \\in \\mathcal{X}: \\text{best arm changes at $x$ from $t-1$ to $t$})$ could still be large $S=T$ while $\\tilde{L}  \\ll T$ if the changes in best arm were constrained to a small subregion of context space.\n\n_Comparability of Definitions of Switches_: In fact, the lower and upper bound results **are comparable**.  Our main adaptive upper bound always achieves the minimax optimal rate under all the parametrizations mentioned in the paper: $L \\geq \\tilde{L}$ (Corollary 4) and $V_T$ (Corollary 5).\n\n_Small Magnitude Changes and Regret of CMETA_: You're correct in that small enough magnitude changes do not affect the regret of CMETA. Additionally, changes constrained to subsets of arms which do not change the best arm do not affect the regret of CMETA.\n"}, {"review_id": "FXYS2ACuAf", "reviewer": "Reviewer_GBqh", "summary": "This paper studies the contextual bandits problem with changing Lipschitz reward function and proves a *minimax optimal* regret bounds for this problem, which includes both upper and lower bounds. For the upper bound, this paper comes up with an algorithm that achieves it. The algorithm is based on carefully maintaining a hierarchical partition tree that discretizes the context space. ", "questions": "Typos:\n1. Line 178, \"Miminimax\".\n2. Below Line 259, Algorithm 1, \"tree $T$\" -> tree $\\mathcal T$.\n3. Line 305, \"ut\". \n4. Line 306, \"(i.e., the bin at level $r_{s_2-s_1}$ containing $X_t$)\" duplicates. \n4. Line 13 in Algorithm 2, trailing ; after :\nThe authors may spend some time to polish the paper before finalizing.", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. This paper achieves minimax optimality for the problem, which closes the existing gap and solves the problem.\n2. The novel idea of significant shifts and the algorithm design of maintaining the partition tree, could be of independent interest. \n3. This paper provides excellent plain word explanation to highlight the key ideas and steps in their proof.", "weaknesses": "1. The algorithm is recursive and complicated, so it makes the audience hard to understand the algorithm, even with the algorithm explanation in Sec. 4. Maybe it is better to replace Line 9 in Algorithm 2 with some while-loop to improve readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for encouraging comments as well as pointing out typos and writing suggestions!"}, {"review_id": "UBElf9cuBq", "reviewer": "Reviewer_aF2K", "summary": "This paper studies nonparametric contextual bandit problems with distributional shifts. This paper proposes a new notion of distributional changes called the experienced significant shifts. Based on this notion, the authors develop new algorithms that achieve the minimax rates without knowing some problem-dependent parameters.\n\n====After rebuttal====\nI have read the rebuttal. I'd like to keep my scores. I also encourage the authors to add more discussions regarding the adaptivity issue.", "questions": "In bandit learning, when the goal is to minimize the cumulative regret, researchers have previously shown that adaptivity to the usual minimax rate is usually impossible and the best one can hope for is the Pareto optimality, e.g., for the model selection problem [1, 2]. However, in this paper, the authors show the opposite in this paper for learning with distributional shifts. Can authors elaborate more on this? Is this because of the common assumptions made in this setting, e.g., Assumption 2?\n\nCitations:\n\n[1] Teodor Marinov and Julian Zimmert. The Pareto frontier of model selection for general contextual bandits. \n[2] Yinglun Zhu and Robert Nowak. Pareto optimal model selection in linear bandits. ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors developed a new notion called the experience significant shifts that better capture the distribution shifts in contextual bandits. Based on this new notion, the authors show that the minimax optimal regret in contextual bandits with distributional shifts can be achieved, even without knowing problem-dependent parameters. In my opinion, this result is significant to the community. Also, along the way, the authors develop several new techniques to achieve this result (e.g., those have been highlighted in Section 5), which can be of independent interest. ", "weaknesses": "In the paper, the authors mention several generalizations of the existing setting, e.g., (i) generalization to H\\\"older continuity, and (ii) the one mentioned in Remark 1. However, no formal results are provided for these generalizations. It will be great if the authors can provide some formal statements.\n\nAlso, for the oracle procedure described in Definition 7, it's better formally state the power of the oracle, e.g., what is known to the oracle and what is unknown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for supportive comments!\n\n_Generalizations to Hölder continuity and Remark 1_: We apologize for the vagueness; we'll add explicit statements showcasing such statements.\n\n_On Adaptivity_: The cited papers in fact study other notions of adaptivity, which are not applicable to to our problem for the following reasons. [1] considers a stronger notion of adaptivity than the one considered here: the impossibility of adaptive switching regret against an adaptive adversary, which is a harder problem than our task of dynamic regret minimization with obliviously decided rewards. [2] is concerned with adaptivity to the unknown intrinsic dimension of linear representations of arms; here we focus on optimal regret in terms of the context dimension which is known (indeed, by Assumption 2, as you point out).\n\nAlso, note that adaptivity to the minimax rate for an unknown number of distribution shifts is recently shown to be possible in many bandit and RL settings (see Auer et al., 2019; Chen et al., 2019; Wei \\& Luo, 2021). So, it is a not a new phenomenon. However, we find your comment very insightful and will add discussion as such."}]

Author rebuttal:
We thank reviewers for their time and useful comments. Please see individual rebuttals to each reviewer.

Meta-review: The authors consider a non-parametric contextual bandit problem under non-stationarity conditions. While non-parametric contextual bandits is well-understood in the stationary setting, and non-stationarity in a variety of settings have come to be well-understood only recently (e.g., Wei and Luo, Suk and Kpotufe), the intersection has not been explored. As some reviewers suggest, the trope of combining two well-known concepts and calling it novel is not very inspiring. However, the authors make a number of novel contributions, including the experienced significant shift which may be useful elsewhere, and clearly describe that the analysis of the adaptive gridding common to non-parametric stationary settings must be completely rethought in the context of this non-stationary setting.
Decision: Accept (poster)