Non-Stationary Lipschitz Bandits
Authors: Nicolas Nguyen
Solenne Gaucher
Claire Vernade
Venue: NeurIPS 2025 poster ()
Keywords: non-stationary bandits
Lipschitz bandits
tracking most significant shifts
Primary area: theory
TL;DR: We study the problem of non-stationary Lipschitz bandits and achieve minimax optimal rate without knowledge of the non-stationarity.

Abstract: We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time. We design an algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function. To detect such reward changes, our algorithm leverages a hierarchical discretization of the action space. Without requiring any prior knowledge of the non-stationarity, our algorithm
achieves a minimax-optimal dynamic regret bound of  $\mathcal{\widetilde{O}}(\tilde{L}^{1/3}T^{2/3})$, where $\tilde{L}$ is the number of significant shifts and $T$ the horizon. This result provides the first optimal guarantee in this setting.

Non-Stationary Lipschitz Bandits
Nicolas Nguyen University of Tübingen
Solenne Gaucher École Polytechnique, CMAP sol sonenne. gaachhrr@polyteccmiieeeeeee
nicolas.nggyen@um wtw.rennnnnitttttnneeee.ee tuebingen.de de
Claire Vernade
University of Tübingen
claire.
Abstract
We study the problem of non-stationary Lipschitz bandits, where the number of actions is infinite and the reward function, satisfying a Lipschitz assumption, can change arbitrarily over time. We design algorithm that adaptively tracks the recently introduced notion of significant shifts, defined by large deviations of the cumulative reward function. To detect such reward changes, our algorithm leverages a hierarchical discretization of the action space. Without requiring any prior knowledge of the non-stationarity, our algorithm achieves minimax-optima dynamic regret bound of (i.1/3/2/3) where L. is the number of significant shifts and T the horizon. This result provides the first optimal guarantee in this setting.
Introduction
Many practical applications involve decision-making over continuous space of actions (or arms) where the environment evolves over time. For example, dynamic pricing, the space possible prices is inherently continuous, and market dynamics may shift abruptly. In such setting, it is both natural and crucial to leverage smoothness in the reward function to generalize across similar actions, while also remaining adaptive to temporal changes. However, most existing works non-stationary bandits focus on discrete action spaces and overlook the structure present in continuous domains.
The -on-ssationary bandit problem extends the classical stochastic multi- armed bandit setting [Slivkins al., 2019, Lattimore and Szepesvári, 2020] by allowing the mean reward functions to change over time. Over the past two decades, several frameworks have been proposed to quantify non-stationarity. Common approaches quantify the number of changes L.T of any arm's 's mean reward over rounds [Auer et al., 2002b, Garivier and Moulines, 201 1], or their total variation V7 in the reward functions [Beshes et al., 2014, Cheung et al., 2019]. Algorithms that are built upon these approaches achieve dynamic regret bounds of order T or Vi! V/1/3/22/3 respectively. Importantly, they all assume prior knowledge of the degree of non-stationarity LT Vy. remained an open question whether such rates could be achieved without knowing T-r or Vr, until line of work answered this affirmatively [Auer et al., 2019a.b, Chen et al., 2019, Wei and Luo, 2021].
Recent works have introduced more refined measures of non-stationarity. In fact, the standard metrics LT and V can be overly pessimistic: both of them may be arbitrarily large even when the best arm remains unchanged. To address this, Abbasi-Yadkori et al. [2023] designed an algorithm that tracks the number of times the best arm changes over T rounds, Sy, and showed that it achieves / / for the dynamic regret, adaptively'. The important work of Suk and Kpotufe [2022] proposed a finer notion of stationnaaay called significant shifts, which identifies only changes that meaningfully
In all our work, "adaptively" should understood the same as "without knowledge the non-stationarity".
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

affect regret through large aggregate differences in reward. In the K K-armed bandit setting, their algorithm achieves the optimal rate of / L. where Ly is the number of significant shifts over T rounds, with LT << Lr.
In this work, we extend the ideas of Suk and Kpotufe [2022] to the setting of Lipschitz bandits, where the space is continuous (typically the interval [0, 1) and the reward functions satisfy a Lipschitz condition at each round. Despite the maturity of research in both non-stationary and Lipschitz bandits individually, their intersection remains unexplored. Our work is the first one tackle the problem of non-stationary Lipschitz bandits.
1.1 Outline and contributions
In this work, we answer the following question positively: Can we design an algorithm that adaptively achieves the minimax-optimal rate in non-stationary Lipschitz bandits? We argue that non-stationary Lipschitz bandits pose unique and fundamental challenges that go beyond a simple combination of non-stationarity and Lipschitz continuity. We highlight two central challenges addressed in this paper.
Discretization level. In the stationary Lipschitz bandit setting, common approach is to discretize the continuous arm space into finite set of bins, thereby allowing the application of standard multi-armes bandit algorithms |Kleinberg, 2004]. When the time horizon T is known, the discretization level can be carefully calibrated, typically using (T1333 bins. This choice reflects the optimal balance between discretization error and the regret incurred by running a bandit algorithm over the discretized arms, leading to the minimax -animax-optimal regret of O(T2/3). In the non-stationary setting, however, the durations of the time intervals during which the mean reward remains stable are unknown and not rigorously defined. Thus, direct horizon-dependent tuning becomes infeasible. This raises a key question: how to adaptively adjust the discretization level to match the unknown degree of non-stationarity in the environment?
Forced exploration via restarts and replays. In non-stationary bandits, detecting changes in the reward distribution requires frequent exploration of suboptimal arms. In the K K-armed bandit setting, this is often handled through periodic restarts, where all K arms are re-explored to detect shifts of the reward function. In the continuous setting, this strategy is significantly harder: not only must we decide when to restart, but also at what resolution to discretize the arm space during such restarts. Finer discretization enables more precise detection of changes but significantly increases the cost of exploration. Balancing this trade-off is central technical challenge tackled in our work.
This paper is organized as follows. In Section 2, we formally introduce the problem setting, and present our algorithm, MDBE, in Section 3. Our main results are stated in Section 4, followed by high-level proof sketch of its regret amalysis in Section 5. For completeness, the full pseudocode of MDBE is provided in Appendix B, and all detailed regret proof's can be found in Appendix D.
1.2 Related Work
Non-stationary bandits beyond K -arreed. A growing body of work has extended non-stationary bandit models beyond the classical K-armed setting. These include linear and generalized linear bandits [Russac et al., 2019, Faury et al., 2021], contextual bandits [Suk and Kpotufe, 2021], convex bandits [Zhao et al., 2021, Wang. 2023, Liu et al., 2025], kernelized bandits [Hong et al., 2023, Twazaki and Takeno, 2025, Cai and Scarlett, 2025], and more structured problems [Seznec et al., 2020, Vernade et al., 2020, Azizi et al., 2022]. Some works further explore temporal regularity assumptions, such as smooth or slowly varying reward functions [Slivkins and Upfal, 2008, Krishnamurthy and Gopalan, 2021, Jia et al., 2023]. Across these settings, non -ottiotoinn is typically quantified using either the number of global changes LT or the total variation Vr.
Bandits with infinite arms. In Lipschitz bandits [Agrawal, 1995], the infinite arm space is tackled via discretization strategies, either fixed or adaptive, that exploit the Lipschitz continuity of the reward function [Kleinberg, 2004, Kleinberg et al., 2008 Bubeck et al., 201 lb Magureanu et al., 2014]. More recently, adversarial formulations have been studied, where the goal is to minimize the regret in hindsight [Podimata and Slivkins, 2021, Kang et al., 2023b]. These differ fundamentally from our focus on dynamic regret in a stochastic setting. A separate line of work investigates infinite-armed bandits in the so-called reservoir model, where arm means are drawn independently from a fixed distribution [Wang al., 2008, Carpentier and Valko, 2015, De Heide al., 2021, Kim et al., 2022,
2

---

2024]. Unlike Lipschitz bandits, these models assume no structural relationship between arms and therefore do not exploit similarity across them. Hence, direct comparisons our setting do not apply. The only work we are aware of that addresses the problem of non-stationary Lipschitz bandits is Kang al. [2023a], who propose a zooming-like algorithm to tune generalized bandit framework. However, their formulation of non-stationary Lipschitz bandits is tailored to their specific setting and does not achieve optimal theoretical guarantees.
Tracking significant shifts. The idea of tracking significant shifts was first introduced in the K Kaarmed setting by Suk and Kpotufe [2022], and has since been extended to contextual bandits [Suk and Kpotufe, 2023], preference-bar -bsed settings [Suk and Agarwal, 2023, Buening and Saha, 2023, Suk and Agarwal, 2024], and smooth non -saationtaoyy models with temporal structure [Suk. 2024].
The works closest to ours are Suk and Kpotufe [2023] and Suk and Kim [2025], both extending the framework of tracking significant shifts beyond the classical K K-armed setting. The former considers contextual bandits where rewards are Lipschitz in the context space, but with a finite number of arms. After discretizing the context space, their algorithm effectively reduces at each context, allowing the use of techniques from the K Karreed setting [Suk and Kpotufe, 2022] without requiring discretization of the arm space. The latter studies infinite-armed bandits under reservoir model, where arms are independently drawn from a fixed distribution. While this shares the challenge of choosing from infinitely many arms, their setting assumes no regularity across arms. Therefore, their techniques and guarantees are not applicable to our setting.
finite-arm bandit problem
1.3 Notations
For any integer n, write [n]] (I,...,.)) n2. For filtration (Fi).. we denote the conditional expectation by Eg [-] = E [: [i] (the underlying filtration will be clear from context). For real numbers and b, we write a V b = max(a, bj and a Ab= min(a,b)
2 Problem setting
Without loss of generality, we assume that the space is the unit interval [0, 1].2 An oblivious adversary selects a sequence of I" mean reward functions (#+)== where each pt [0, 1] + [0, 1] satisfies the following Lipschitz condition:
Assumption (Lipschitz mean rewards μ2). Va, x' E [0, 1], [p((x) - ue S x -0-=xp x'|.
At each round E (T), an algorithm π selects an arm x, E [0. 1] and observes a stochastic reward (x.))) E [0, 1] independent from the past (arms and observations) and satisfying EE [x.)) xy x]
p4 (x). The objective is to minimize the dynamic regret
T
T Em((z)) t=1
R(T,, T) = Σ sup (x( t=1
ZEX
defined the difference between the cumulative gain of the algorithm and that of the dynamic benchmark oracle, which, at each round, knows the reward function μ4. In this paper, we design an algorithm and provide bound on expected dynamic regret [[( T)), where the expectation taken with respect to the randomness of the interactions between the algorithm and the environment.
We denote the instantaneous gap between two arms x' and x as (, x) 14(2') - (x(x,,, and the instantaneous regret of arm x: as (z) = max [(01) (x(x') pe(x), so that R(T, T) = Σ (x(2)).
2.1 Significant regret and significant shifts
We now introduce the notion of significant regret for an arm E [0, 1]. Definition 1 (Significant regret of [81, 82] if its cumulative regret on this interval is lower bounded as
æ)), An arm X incurs significant regret on interval
82
Σ
(x(x)) log(T)(s2 2/)2/3
We call such arm an unsafe arm on interval [s1, 52). and otherwise we call it safe on this interval.
Extennioos to arbitrary metric spaces and other Lipschitz constants discussed in Appendix G.
3

---

The right hand side of Definition 1 corresponds to the Mainimax-optimma regret for stationary Lipschitz bandit over horizon $2 $1, and thus captures the level of regret that is statistically detectable. Conversely, if no such interval exists where arm x: incurs significant regret, then its cumulative regret over the entire horizon must remain small. significant shift occurs when all arms become unsafe, Le. when each arm has incurred significant regret over some interval.
Definition 2 (Significant shift, significant phase). Let To 1. For i 2 1, we define the 1th significant shift as the smallest round Ti E)T such that for all arm x E X, there exists an interval [$1, s2] S [1; on which arm x incurs significant regret (Definition 1). For all i, we call [Ti, T441l significant phase, and we denote by Lr the (unknown) number of significant phases.
This definition implies that tracking significant shifts amounts to detecting intervals where the regret exceeds what would be expected in a stationary Lipschitz environment.
2.2 Comparison with other non-stationary metrics.
The notion of significant shifts provides refined perspective compared to classical metrics such as the number of global changes Lr E I [rr E [o, 1] (++1(1)) # [4(x)), the total variation VT = Σi= max,e|0.1] ( - (z)), and the number of best-arm changes over T rounds, ST = EE I [argmaxxe[o.1] (x+ # argmax [e(r)) Unlike these metries, Lr is robust to benign transformations. For instance, if each μr is shifted by the same constant across all æ, then LT and Vr may scale linearly with T, while ls = O. Similarly, Sr may count frequent changes in the optimal arm due to small fluctuations, even if the overall impact is negligible. In contrast, Lr captures only statistically meaningful shifts and satisfies L7 S ST S LT.
For example, consider a recommendation system with a continuous pool of content (e.g. movies), indexed by x: E [0, 1]. where nearby values of x correspond to similar content types. Suppose there exist two regions of high and comparable user preference, centred around x1 = 0.3 and 22 = 0.7. Imagine a scenario where preferences near 3 remain stable over time (e.g. timeless classic), while preferences near I2 undergo very frequent changes (e.g. a trending topic that evolves daily). In this case, an algorithm that consistently recommends content near Ii would incur little to no regret, even though the underlying reward function changes frequently in other regions. From a global perspective, the number of changes or the total variation in mean reward could be as large as LT = Vr= = OTT). An algorithm that relies solely on such metrics would unnecessarily restart its estimates too frequently, as would overestimate the effective difficulty of the problem. This leads to both theoretical sub-optimality and practical inefficiency. However, such changes do not constitute a significant shift, as the latter captures only changes that are statistically consequential to learning, rather than indiscriminately counting all shifts in the environment.
3 Algorithm MDBE: Multi-Depth Bin Elimination
We now present the key ideas leading to the design of our algorithm, before detailing each one of them?. At high level, our goal is to detect significant changes in the aggregate gaps Σiz., 5,(2,, ,x) between pairs of arms over time intervals. This quantity lower bounds the dynamic regret Ete., (x))) over this interval, meaning that large changes in these aggregate gaps are indicative of large dynamic regret. However, directly monitoring such changes for all possible pairs of arms is infeasible in a continuous action space. To address this, we adopt discretization strategy and instead monitor aggregate gaps between pairs of bins B. B' (i.e., subintervals of [0. 1)) in the form Σie (B', B).
Our algorithm operates in stable episodes, each split into blocks of doubling length with varying discretization levels. Within each block, a variant of the Successive Elimination algorithm removes empirically suboptimal regions. Since discarded bins may become optimal later, we use the replay mechanism of Suk and Kpotufe [2022] to revisit them and avoid missing promising regions. A key challenge is selecting the right discretization level for each replay. Our sampling procedure guarantees sufficient exploration at different scales, while a carefully designed bin eviction mechanism progressively eliminates regions that appear suboptimal based on empirical evidence.
'The full pod of Multi Deett- Bin Elimination (MDBE) can be found in Appendix B.

---

Discretization. To estimate the reward function at multiple discretization levels, we use recursive dyadic partitioning of the space, described below.
Definition 3 (Depth and Dyadic tree). Ta denotes the partition of [0, into 2 bins of size 1/24 each. We say that d is the corresponding depth of this discretization. We define the dyadic tree T aTa as the hierarchy of nested partitions of [0, 1] at all possible depth d E N. For any bin B E Tá, we denote by Children( B, d') the set of children of bin B at depth d' > d, and Parent( B, d the unique parent bin of B depth d" d. In particular we have d" d d'
NB' E Children(B, (B, d'), B' c B C Parent (rrent(Bee ).
For any bin Ta, we define the mean reward of bin round E [7] as
1
/
(b
po(x)dæ,
[ WEB
where [B] = 1/22 denotes the width of bin E Ta. We define the instantaneous relative regret between two bins B, B' E Ta as (B', , B) (B') [ee (),, and introduce its empirical estimate, to be formalized later, as (B', B) Pa(B") (B)... We also define the instantaneous regret of a bin B E Ta as (B) (r(B), & (B) and (x), (x) to denote the mean and regret for bins and arms, respectively. The distinction should be clear from context.
m (B" Jer (B). For simplicity, we use the same notation
Episodes and blocks. The algorithm proceeds in episodes, indexed by 1 E N. with episode / starting at round & (with to = 1). Each episode is divided into blocks, where the m block lasts for 8t" rounds. Within the m th block, the action space [0, 1] is discretized into 2n = (8 bins, corresponding to the mhth depth Tm We denote the block interval by [T.m. 7.m++ I. and maintain set BMASTER (m) C Tm of safe bins at depth m (referred to as the MASTER set). A significant shift is detected when EMASTER (m) 0. meaning all bins depth m have been evicted. In such cases, the block (and thus the episode) ends prematurely. Otherwise, a block ends naturally after 8m rounds.
Algorithm 1 Routine procedure for one block
Input: Starting round of the block 7.m- BMASTER (m) Tmi
// Initialize MASTER set with all bins at depth m
Schedule replays for t = Tl. + 1,... Tim + 8 and d E [m - according to (1);
for Ti.my... ..., Tm. 8m 1 do
Enter replay at depth d then
D. DDD,UU. U (d);
// Activate depth d for replay
if Exit replay at depth d then
L D. D. {d);
// Deactivate depth d after replay ends
Choose 2, using Sampling scheme (Algorithm 2);
Update mean estimates and evict bins using (+); if BMASTER(C (m) = & then
Break; terminate episode + 1 + 1, restart from block m t 1; // Shift detected
Change block: m + m + 1, 7, + 7,m + 8"";
// If (m) #
At each round E [2]] MDBE maintains a of active depths D, N. For each active depth d Dr, the algorithm maintains set of active bins (d) C Ta. which are those not yet evicted based on their observed performance. If is not active, i.e. & D,, then (d) = 0.
Replays. To detect non-stationarity at different scales, the algorithm performs replays at various depths. Each block (n, Tim++1| always initiates a replay depth by setting BMASTER (m) Ti- Additionally, replays may be triggered for all rounds 77.m 1, 1,.... Tl. + 8m at coarser depths m with probability
gd 77.m
Pa.d V
11 1(s s Tt.m = 0
(I)
Each replay at depth d runs for 8d rounds, unless is interrupted by the end of the current block. At the beginning of such replay, the set of active bins at each active depth d E D, is reset to contain
5

---

all bins at that depth: (d)d) < Ta for all d E D.. When the replay at depth d concludes, depth d simply removed from the set of active depths D., but any other active depths may continue their replays independently. Thanks to this design, multiple replays at different depths can overlap in time, allowing the algorithm to monitor for potential significant shifts at multiple scales simultaneously (Algorithm 1).
Sampling scheme. At each round, the algorithm selects an action using a hierarchical, top-down sampling procedure from the minimum active depth do(t) = min D; down to the deepest active depth that contains an active bin (Algorithm 2). Remark that if D: {m), then B (m) BMASTER (m). In this case, the sampling procedure reduces to selecting a bin uniformly from EMASTER (m)) and subsequently sampling an action from the chosen bin (see Figure
Algorithm 2 Sampling scheme
Input: Round active depths D,, active bins (B)(d)) Compute do (t) = min De;
// Identify the minimum active depth // Sample a parent bin at depth do(t)
Bpavent ~ (do,((o
for d E Sort(D,) {d)(t) do
Children parrent d) B.()) = then
// No active child bin found
Zt (Bpareu)); Return 24; else
// Sample uniformly from current bin
Behild ~ U(Children pprrent, d) n (c))); Bparent Behild;
// Sample an active child bin // Continue to the selected node
Bin eviction criterion. Our algorithm aims to identify and eliminate arms that incur significant regret, as defined in Definition 1. However, since the algorithm only relies on bin estimates de B), we introduce a notion of significant regret for bins to make localized decisions.
Definition 4 (Significant regret for bin). We say a bin B E Ta incurs significant regret interval [$1, 82) if
(, 3log(T) s1)2d
We call such bin unsafe bin this interval, and otherwise call it safe on this interval.
The right- hand side of the inequality corresponds to the rate of the minimax regret of 2d-armed bandit over interval 82]. Intuitively, this threshold captures whether the cumulative sub-optimality of the bin is statistically significant over [81, 82]. Importantly, we will later show that if bin meets this threshold, then all arms within the bin also suffer significant regret in the sense of Definition 1 (see Proposition 1). We emphasize that the notion of significant shifts (Definition 2) defined independently of any depth (and thus independently of the depth used by the algorithm).
To estimate the mean reward of a bin B, we use the following importance- weighted estimator:
YI(1))
YB Ta, (B) P(x, B B| 1fx1 E B).
(2)
where Fe is the natural filtration generated by the algorithm. Under uniform sampling within bin B. (a( is an unbiased estimate of (4(B), In partieular, during a replay depth d, the algorithm leverages these estimates to potentially evict bins across active depths d' 2 that appear suboptimal: over some [$1, 82] of length at most 8d (d is active), bin B is evicted if
4(32 - 81)
8e B) co log(T) (82 81 s1)2d v 4
max B'EB 2g
2d
1=
where is positive universal constant and ex,, (d) denotes the set of bins that remain active throughout interval [$1 sz). Importantly, when a bin B E Ta is evicted based on this criterion, it is
An exact value of co can be derived from the analysis.

---

immediately removed from the current set of active bins B₁, and also permanently removed from the global MASTER set BAASER (m). In addition, all children of B in the dyadic tree are evicted as well. As a result, no future arms will be sampled from the entire region corresponding to B and its descendants in 7 until a new replay scheduled. The next proposition establishes that the eviction rule (+) is sound: evicted bins indeed correspond to areas where all arms suffer significant regret. Proposition (Significant regret of bin implies significant regret of an action). Ifa bin B E Ta incurs significant regret on interval ($1; 82) with 82 significant regret over [81, 82)
8d, then every point E B also incurs
1-4+1
1-
Figure! 1: Example of sampling with m = 4; active bins are in blue. Left: At time 4, depths and m active. A sample path may select bin B3,3 uniformly at random (u.a.:)) depth 3, then B,, u.a.F. among its active children, then arm He u.a.F. in B Bm.6 (red path). Center: At t + 1, a replay starts depth 1. A path may go through B1, + B3.2 + BR, selecting 2; in Bm,, (red path). Alternatively, B1,2 could be chosen; with no active children, Ht is sampled directly from it (green choice). Right: At t + 9, depth exits replay. Bin has been B3,2 eliminated during the replay, and path may select B3,1 + Bm then Ia in Bm,1 (red path).
4
Main results
We establish the fundamental limits for the non-stationary Lipschitz bandit problem, and prove that our algorithm MDBE achieves minimax optimal dynamic regret. We first derive a lower bound on the dynamic regret, expressed terms of both the number of significant shifts I. and the total variation Vy. To the best of our knowledge, this is the first lower bound for non-stationary Lipschitz bandits.
Theorem 1 (Lower bound the dynamic regret). Let (T, L) denote the class of non- non-stationary Lipschitz bandit environments over the arm space [0, 1] with most Lr L significant shifts. There exists a numerical constant >> O such that for any algorithm π,
sup E2 [R(T,, T)] 2 2/3
(T.L)
Similarly, for the class (T, V) with at most VT S V total variation, there exists a numerical constant > O such that for any algorithm
Ep [R(T, T)) 2 02 (T2/3 + v2/2m3//)
sup M
To give intuition whether the optimal rate ( is achievable, consider oracle algorithu Toracle with access to the exact times of the significant shifts { The optimal algorithm partitions the horizon into T.r phases and, within each phase, runs minimax-optimal bandit algorithm (e.g. UCB [Auer et al., 2002al) using discretization of (T++ - 1/3 arms. This oracle algorithm suffers regret at most Coracle (Ti41 - 2/3 per phase, where Coracle > 0 is numerical constant, yielding
L.
IE [[ T)] < Coracle
(T411 2//3 < Coracle 1//3
1=0
However, this oracle relies on complete knowledge of T/'s. s. In contrast, our algorithm MDBE is fully adaptive. Theorem proves that it achieves minimax optimal regret, up log-itogaii factors.
7

---

Theorem 2 (Adaptive upper bound on dynamic regret). Let μ (Tp((,Lr) be Lipschitz bandit environment with Ln unknown significant shifts (Ti(p)) There exists a numerical constant O such that the expected dynamic regret of MDBE satisfies
Ey THDBE. T) S E1 log (T) (Ti(m) TC- 1
In particular, this yields the worst-case upper bound
E [R[ NDBE, T)] S O(LL
Therefore, MDBE is minimax optimal for the number significant shifts LT up to poly-log,
Since by ST Lr, Theorem 2 achieves minimax optimal rates of (15/332233 and 232233 without requiring prior knowledge of ST or Lr,, respectively. The bound provided by Theorem can be significantly sharper when LT < ST. The following result further shows that Theorem 2 also recovers the optimal rate in terms of the total variation Vr. The proof is deferred Appendix D.
Remark 1 (Beyond 1-Lipschitz bandits). Minimax optimality of Theorem 2 extends beyond Lipschitz bandits with Lipschitz constant 1. particular, for (1s. ---Hler bandits we can show that the minimax optimal rate (up to polylogarithmic factors) can be adapted as E RR(EE T)] s 2 Ö( ((T _ kI''0) <
where the minimax optimality is with respect to T, LT and Hölder constants and 3) jointly. The necessary modifications to our setting and algorithm are detailed in Appendix G. Corollary 1 (Regret bound in terms of total variation V.). Let (T, V be any Lipschitz bandit environment with total variation Vr. There exists a numerical constant 02 > such that the expected dynamic regret of MDBE satisfies:
(T2/3 Eu R TYDEE, T)] S log ( V/Z /T//4)8//))
Therefore, MDBE is minimax optimal for the total variation VT up to poly-log factors.
5 Proof intuition of Theorem
A natural question is whether one could directly apply the MASTER procedure of Wei and Luo [2021] using a discretization of the arm space as the base algorithm. However, such a direct application would not be possible in our setting, for the following reasons. The MASTER procedure is specifically designed to detect and adapt to changes in the mean reward functions μt, whereas our goal is to handle significant shifts, defined in terms of cumulative reward gaps Σ, d.. This distinction crucial: the quantity Σ, 5, is inherently more stable than the instantaneous mean rewards, as it captures suboptimality over time, even when the underlying reward functions change smoothly or gradually. As result, the detection problem in our setting is more subtle and requires finer control over the accumulation of regret. Therefore, even when discretizing the arm space with replays at different depths, the analysis of Wei and Luo [2021] would not achieve the desired dependence on Lz-
We further emphasize that our analysis goes beyond a straightforward adaptation of the techniques developed for the K-armed setting by Suk and Kpotufe [2022]. In their setting, the algorithm maintains a set of safe arms and applies a variant of Successive Elimination [Even-Dar et al., 2006] by uniformly sampling from the current set and progressively eliminating arms identified as suboptimal. Roughly speaking, to detect changes of magnitude A, they schedule replays of duration d = K/A². during which all K arms are re-sampled and their estimates updated. However, such a replay scheme is infeasible in our infinite-arm setting. If we were to discretize the arm space into 2m bins at each replay, reliably detecting shift of magnitude A would require roughly 2nt 2'"/"" A rounds, resulting in prohibitive regret cost. To circumvent this issue, our algorithm schedules replays at different discretization scales. By leveraging the hierarchical structure of the dyadic tree T. we update estimates of the gaps at multiple depths simultaneously. We exploit the key observation that each sample z provides information not only for its bin at depth d, but also for all child bins at depths d' 2 d. Through systematic aggregation of information across these nested bins, our multi-scale estimation strategy allows the algorithm to detect significant shifts efficiently different resolutions, while avoiding the prohibitive sample complexity associated with naive discretization.
8

---

We begin by highlighting the technical challenges that arise when estimating these cumulative gaps, in particular how they differ from estimating changes in the mean reward itself (Section 5.1). We then present the high-level ideas for bounding the dynamic regret in two scenarios: (7) when the process in a stable block, and no significant shift is detected, we show that the replays do not increases the regret excessively (Section 5.2); and (ii) when significant shift does occur, we show that the algorithm responds appropriately (Section 5.3). The proofs are provided Appendix D.
5.1 Estimating the reward gaps
The continuous arm space setting presents key technical challenges. These difficulties are specific to framework and are not addressed in existing work non-stationary bandits, and we believe these challenges are of independent interest and may be relevant beyond our specific setting.
The main challenge in this setting lies in estimating a continuous, non-stationary mean reward function without prior knowledge of the magnitude of distributional shifts, or, equivalently, the discretization level and time scale at which such shifts become detectable. Coarse discretization essential to rapidly detect large shifts, while finer discretization is required to capture smaller yet statistically significant changes. This motivates the multi-scale replay framework of MDBE in which each scale contributes adaptively based on the magnitude of the underlying shift.
Bias in mean reward estimation. Our algorithm actively prunes bins different depths, meaning that for a given bin B E Ta. its sub-bins B' C B at deeper depths d' > d may be evicted. As result, the empirical mean reward ia (B) can be biased. since arms HG are only drawn from non-evicted sub-bins. Leveraging Assumption 1, we control this bias, which decays as
Vt E [T], AA E Dr, BB, B' E (.)d),
E.-1 [6,(BB, B]] 5, B)
S 2d
4
(3)
Thus, the bias in estimating the gap Σi (B',,, B) of bins at depth d scales as (s2 - 81 11)/24.
Concentration of mean reward estimates. Due to the martingale property of (8, B))e we can tightly control its deviation from its conditional expectation. Recall that our hierarchical sampling scheme (Algorithm 2) ensures that the algorithm selects an active bin the minimum active depth do(() and recursively samples from child bins at finer active depths. This choice guarantees that
E [T). Ad E Dr, AB E (d), P(e. E F 2d
This ensures that all active bins at any depth dl are sampled with at least uniform probability, allowing us to control the variance of the inverse weighted estimates at all scales and to derive the following bound.
Proposition 2 (Concentration event). Let E1 be the following event: for all intervals [s1, s2), depths E k=
Dr, and bins B, B' <B|o1.ea) (d), we have
82
82
Σ
&,BBB.
Σ E
|LLB'' BJ]
S cc (s2 s1)2d 4d
where 01 is positive numerical constant. Then & holds with probability at least 1 1/T3.
Unlike in classical finite-armed bandits [Suk and Kpotufe, 2022, 2023, Suk and Agarwal, 2023], uniform sampling only holds strictly at depth (t).. This subtle distinction plays critical role in the analysis. Thanks to both the bias control (3) and the concentration control (4), we can ensure that bins are only evicted when truly unsafe, despite the complexity introduced by the hierarchical sampling.
5.2 Regret within a block without significant shiftt
Assume, for the sake of clarity, that no significant shift occurs during the block [Ti., 71,m+1 1. When only the replay at depth m is active, i.e. D: {m.. the algorithm effectively runs a Successive Elimination strategy at depth m: at each round, selects bin uniformly random from the set of safe bins BMASTER(m (m), samples an arm 2, from this bin, and eliminates bins that are deemed unsafe at this depth. this regime, since the discretization level at depth m is tuned to the block length 71mm- Tim, classical results indicate that the regret incurred within the block is of order 2/3) 4t (up to logarithmic factors).

---

It remains to control the regret from replays across different scales. A key difficulty is that such replays may overlap, making delicate control the cumulative regret contribution each depth simultaneously. A crucial property leveraged in the analysis is that our importance- weighted estimator (2) allows each sampled arm de to update the mean estimates iie for all bins B containing dt-- This multi-scale update property ensures that replays at any given depth d contribute information not only at that level but also propagate to finer depths d' > d. In particular, we leverage Proposition I, which guarantees that if a bin is identified as unsafe any depth d, then all arms it contains are suboptimal.
Our proof strategy to quantify the contribution of each replay at depth independently. Since each such replay lasts at most 8 rounds, and arms are always selected from the set of safe bins B, (d) at that depth (otherwise they would have been evicted under the concentration event & the regret contribution of each replay can be upper bounded by (8d)2/3 4 Thanks to the well-calibrated replay scheduling probability (I), there are roughly vgm-dd replays at depth d that are scheduled during block, so overall we can show that the aggregate regret from all replays across depths d m remains bounded by 4"m thus matching the regret incurred by the main replay at depth m.
5.3 Detecting significant shifts
When significant shift occurs within a block [T.m. T,m+1l J. the primary challenge is that the shift initially undetected, potentially causing the algorithm suffer large regret if it continues exploiting outdated information. In particular, such regret can accumulate if a bin that was previously evicted (due to being deemed unsafe) becomes optimal after the shift, while the algorithm keeps ignoring More precisely, detecting a shift of magnitude A at depth d requires a replay of length approximately 2d ///A2. Undetected shifts of this magnitude are tolerable at this resolution over a period of duration D as long as AD S 4d By carefully calibrating the probability of scheduling replays at each depth (see (1)), we guarantee that replays at depth d occur frequently enough to ensure, with high probability, the timely detection of shifts of size A before their contribution to regret becomes significant.
Conclusion
We studied the previously unexplored problem of non-stationary Lipschitz bandits. We introduced MDBE, a novel algorithm that leverages a hierarchical discretization of the action space to exploit the Lipschitz structure of the evolving reward function. We established a lower bound of O (F..) 72/3 on the expected dynamic regret and showed that MDBE achieves this rate adaptively.
While our work is mainly theoretical, we also analyze the computational worst-case complexity of MDBE Appendix H and show its empirical performance on a synthetic example in Appendix I. Developing computationally efficient algorithms with strong empirical performance that do not require prior knowledge of the non-stationarity [Gerogiannis et al., 2025a.b) remains an open problem. Future work could extend the significant shift detection framework to other structured bandit models such as convex or linear bandits.
Broader impacts
This work is mainly theoretical and contributes to the analysis of algorithms for ieqquential-deeisiie making under uncertainty. Our generic setting and algorithms have broad potential use; practitioners will therefore need specifically address possible social impacts with respect to the relevant application.
Acknowledgements
The authors gratefully acknowledge Joe Suk for his insightful discussions and for sharing his code, which served as inspiration for our numerical experiments.
N.Nguyen and C. Vernade are funded by the Deutsche Forschungsgemeinschatt (DFG) under both the project 468806714 of the Emmy Noether Programme and under Germany's 's Excellence Strategy-EXC number 2064/1-Projie number 390727645, Both also thank the international Max Planck Research School for Intelligent Systems (IMPRS-IS).
10

---

References
Yasin Abbasi-Yadkori, András György, and Nevena Lazić. A new look at dynamic regret for non-stationary stochastic bandits. Journal of Machine Learning Research, 24(288)1-377, 2023.
Rajeev Agrawal. The continuum-armen bandit problem. SIAM journal on control and optimization, 3366);1926-151, 1995.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learming, 47:235-22 256, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002b.
Peter Auer, Yifang Chen, Pratik Gajane, Chung-Waa Seung-Weilll Lee, Haipeng Luo, Ronald Ortner, and Chen-Yu Yu Wei. Achieving optimal dynamic regret for non-stationary bandits without prior information. In Conference on Learning Theory, pages 159-163. PMLR, 2019a.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference Learning Theory, pages 138-158 PMLR, 2019b.
MohammadJavad Azizi, Thang Duong, Yasin Abbasi-Yadkori, András György, Claire Vernade, and Mohammad Ghavamzadeh. Non Non-stationary bandits and meta-learning with small set of optimal arms. Reinforcement Learning Journal, 2022.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non- stationary rewards. Advances in neural information processing systems, 27, 2014.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5). 2011a.
Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the lipschitz constant. In Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings 22, pages 144-158. Springer, 2011b.
Thomas Kleine Buening and Aadirupa Saha. Anaconda: An improved dynamic regret algorithm for adaptive non-stationary dueling bandits. In International Conference on Artificial Intelligence and Statistics, pages 3854-3878 PMLR, 2023.
Xu Cai and Jonathan Scarlett. Lower bounds for time-varying kernelized bandits. International Conference on Artificial Intelligence and Statistics, 2025.
Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning, pages 1133-1141 PMLR, 2015.
Yifang Chen, Chung-We Wei Lee, Haipeng Luo, and Chen-Yu Wei. A new algorithm for non- ata-staiionay contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pages 696-726. PMLR, 2019.
Wang Chi Cheung, David Simchi- Levi, and Ruihao Zhu. Learning to optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
Rianne De Heide, James Cheshire, Pierre Ménard, and Alexandra Carpentier. Bandits with many optimal arms. Advances in Neural Information Processing Systems, 34:22457-22469, 2021.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.

---

Louis Faury, Yoan Russac, Mare Abeille, and Clément Calauzènes. Optimal regret bounds for generalized linear bandits under parameter drift. Proceedings of Machine Learning Research vol. 132:1-37, 2021.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International conference on algorithmic learning theory, pages 174-188. Springer, 2011.
Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, and Venugopal V Veeravalli. Dal: A practical prior-free black-box framework for non-stationary bandit environments. arXiv preprint 1xXi::2501.19011 2025a.
Argyrios Gerogiannis, Yu-Han Huang, and Venugopal V Veeravalli. Is prior-free black-box non- stationary reinforcement learning feasible? International Conference on Artificial Intelligence and Statistics, 2025b.
Kihyuk Hong, Yuhang Li, and Ambuj Tewari. An optimization-baset algorithm for non-stationary kernel bandits without prior knowledge. In International Conference on Artificial Intelligence and Statistics, pages 3048-3085. PMLR, 2023.
Shogo Iwazaki and Shion Takeno. Near-optimal algorithm for non-stationary kernelized bandits. International Conference on Artificial Intelligence and Statistics, 2025.
Su Jia, Qian Xie, Nathan Kallus, and Peter Frazier. Smooth non-stationary bandits. In International Conference on Machine Learning, pages 14944414944. PMLR, 2023.
Yue Kang. Cho-Jui Hsieh, and Thomas Lee. Online continuous hyperparameter optimization for generalized linear contextual bandits. Transactions on Machine Learning Research, 2023a.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. Advances Neural Information Processing Systems, 36: 18897-98789 2023b.
Jung-Hun Kim, Milan Vojnovic, and Se-Young Yun. Rotting infinitely many-armed bandits. In
International Conference Machine Learning, pages 11229-11254, PMLR, 2022.
Jung-hun Kim, Milan Vojnovic, and Se-Young Yun. An adaptive approach for infinitely many-armed bandits under generalized rotting constraints. Advances in Neural Information Processing Systems, 37:8785-8833, 2024.
Robert Kleinberg. Nearly tight bounds for the continuum-armet bandit problem. Advances in Neural Information Processing Systems, 17, 2004.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681-690 2008.
Ramakrishnan Krishnamurthy and Aditya Gopalan. On slowly-varying non-stationary bandits. The second Reinforcement Learning Conference, 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Xiaoqi Liu, Dorian Baudry, Julian Zimmert, Patrick Rebeschini, and Arya Akhavan. Non-stationary bandit convex optimization: A comprehensive study. arXiv preprint arXiv:2506. 02980, 2025.
Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999, PMLR, 2014.
Chara Podimata and Alex Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pages 3788-3888 3705- PMLR, 2021.
Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019.
Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. A single algorithm for both restless and rested rotting bandits. In International Conference on Artificial Intelligence and Statistics, pages 3784-3794, PMLR, 2020.
12

---

Aleksandrs Slivkins and Eli Upfal. Adapting to changing environment: the brownian restless bandits. In COLT, pages 343-354, 2008.
Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends Machine Learning, 12(1-2):1-286, 2019.
Joe Suk. Adaptive smooth non-stationary bandits. arXiv preprint arXiv:2407.0865: 2024.
Joe Suk and Arpit Agarwal. When track significant preference shifts in dueling bandits? Advances in Neural Information Processing Systems, 36:38347-38869, 2023.
Joe Suk and Arpit Agarwal, Non-stationary dueling bandits under weighted borda criterion. arXiv preprint arXiv:2403.12990 2024.
Joe Suk and Jung-hun Kim. Tracking most significant shifts in infinite-armed bandits. International Conference Machine Learning, 2025.
Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. In Conference Learning Theory, pages 2160-2182. PMLR, 2022.
Joe Suk and Samory Kpotufe. Tracking most significant shifts in nonparametric contextual bandits. Advances in Neural Information Processing Systems, 36:6202-6244 22241, 2023.
Joseph Suk and Samory Kpotufe, Self-tuning bandits over unknown awarraae-shiffee In Algorithmii Learning Theory, pages 1114-1156. PMLR, 2021.
Claire Vernade, Andras Cyorgy, and Timothy Mann. Non-stationary delayed bandits with intermediate observations. In International Conference on Machine Learning, pages 9722-9732. PMLR, 2020.
Yining Wang. On adaptivity nonstationary stochastic optimization with bandit feedback. Operations Research, 2023.
Yizao Wang, Jean-Yves Audibert, and Rémi Munos. Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems, 21, 2008
Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on learning theory, pages 4300-4354. PMLR, 2021.
Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125):1-45 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our algorithm is provided in Section 3 and its corresponding bounds provided in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We acknowledge in Section 6 that our work is mainly theoretical and does not consider numerical performances in depth.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-tex. system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Theoretical results are stated in Section 4, and all complete proofs can be found in Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The code is provided a Github repository.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code. with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code is available at Lipschitz_ ts.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ca jublic/guides/CodeSnee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.. http://niis.cccpuii//ie
for more details. The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are available in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Error bars can be found in Appendix I.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard ertor of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
No particular computer resource is needed to run the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httperrwpp..cccalllc/cchcccaaaaa
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and confirm that our paper adheres to its principles.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Societal impacts of our work are discussed in the broader impact section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww datastss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
We only use LLM for writing purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

Appendix
A Notations
We present in Table compilation of used notations in our paper.
Notation
Description
T
Time horizon.
Lr
Number of arm changes in T' rounds: LT ΣT-
T-1 1f3x E [0.1], p(+1 * m((2)}
Sr
Number of best-arm changes in rounds: S Σi= {arrmmax, (142(x) & argmax, 14 1c(x)}
Vr
Total variation in 7" rounds: Vr = Σi= max (1++((x)= (z(2))
Lr
Number of significant shifts in T rounds (see Definition 2).
Dyadic tree, i.e. hierarchical partition of [0, 1] (see Definition 3). Partition of [0, into 24 bins of size 1/2d each.
Ta
Parent (ooottBBd))) B.d)
Unique parent bin B in Ta.
Children (B.d)
Children (set of bins) of bin B depth Episode I. An episode terminates when significant shift is detected. Block m within episode I; uninterrupted. its duration is 7,m-1 T1, 8m Maximum number of blocks during one episode: Mr [logs (7(4 - (1) + 1) 17. Set of active depths at round Minimum active depth at round t: do( = min D,. Set of active bins at depth d time t.
[ti t
[T.ms 7lm+11
Mi
D.
do(t)
(,(d)
(d))
Bins at depth d active at all time in [2), MASTER set block m: BMASTER (m) S Tm.
BMASTER(M) (m)
Ri,
Replay trigger variable: RG,d indicates a replay at depth d starts time t. Replay initiated at round at depth (see Definition 6).
REPLAY(L, d)
(B() ..... B(22))
Ordered bins in (see Definition 5).
Concentration event (see Proposition 2).
&g (T.m)
Event defined in Proposition 10.
Arm selected at round é by the algorithm.
Last safe arm in phase (see Definition 7).
of = o for E [Ta, T Instantaneous regret at round t of arm z: 5e(x)) max (e()) - -m((z)
(x)
Brd
Bin selected at depth d: It Br,--
BF
Bin at depth containing ob (see Definition 8).
BF
B B for t E [T,, T.4l-
Blust
Last bin of block [T)m 7,m+1| in BMASTER (m) (see Definition 10). Instantaneous regret at round t of bin B: if B Ta. (B( max (c (B()).
(B)
[ (B), S (B))
5th bad segment of bin B (see Definition 12).
8 (B)
Approximate midpoint
bad segment [STT] (B), s (B)] (see Definition 12).
S1. (I.m(B)
Bad round of bin B (see Definition 13).
M(s, B)
Last round where bin B is active during REPLAY(S, d) (see Definition 11).
K(P,Q)
Kullback-Leible divergence between two distributions I and Q Kullback-Leibler divergence between two Bernoulli with parameters and q.
kl(p,g)
Table 1: Summary of notations.
21

---

B Full pseudo-code of MDBE
Algorithm: MDBE: Multi-Depth Bin Elimination
Input. horizon T. Lipschitz constant.
Init. / < 1. 4-
// Global initialization
while & < 7 do
(*) m 4- 1, 7.m + t;
// Init first block of episode ( // Check if current block has ended
if f 7.m + 8m then
m + m
// Change block
BMASTER(M) (m) Tmi 5 {m}:
// Reset MASTER set to full bin set at depth
// Activate only the current depth m // Update block start time // Record start time of this replay // Schedule replays in this block
TI. 1: SloreActive[ri] [start] f T7.m
for s 7.m ................................ Tim 8m do
for d = 0
m7 do
s 7.m 0[8d] then
Sample Re,d ~ Ber ////(s/ (0-4/(s110) n.m));
else
Re.d 0:
// No replay triggered at depth d in round
for d O, ...,, m do StorcActive(d]] (Sttar) <- 0. StoreActtvood [fend] < 0; // Initialize variable
(d) - 0:
// Initialize set active bins
for d = 0, ...... m
1 do if R.d then
// Check which replays are triggered in this round // If replay at depth d is triggered // Add this depth to current active depths // Store replay start time Store replay end time // Activate all bins at this new active depth
D. + (d((d)
StoreActive [start] t- StoreActive(d)) (ond) l 8d,
(i(d)- + Tai
for d E D, do if StoreActive|d[ then D: D, {d]: (d) 0;
// Check if any active replays are ending
// Deactivate this depth // Deactivate its bins
(t) + min Dr:
// Identify the minimum active depth // Sample bin from active bins at depth do(t) // Go trough the active depths, from shallowest
B Bparent (do
for d E Sort(D;) (t)) do
to deepest
if Children B Bparent, d) 0 (xd)) = 0 then // No active children at this depth // Sample arm uniformly from current bin
21 U( B Bparent):
else
Behna [CChiidreen(Baaren d (d))))
// Sample active child bin // Move to child bin
B Pparent Behitii
for d E D, do
for E (d) do
if 7[81, s2]
S (StoreActive(d[[taarr)) such that (x) holds for some active bin B'
Be(d) then
for d' Jd. m D. do (, B,(d') U UU Evict bins at active depths
BMASTER (m) + BMASTER (m) n B,():: BMASTER (m) = 0 then
// Update MASTER set // significant shift detected
T.m++ f t 1;
l- 1+ and Restart from (*);
// Change episode
1+
22

---

C Proof of Proposition
Let d be any fixed depth, and let B E Ta be bin that incurs significant regret interval [$1, s2]. Let B be any action within this bin. For each round t, define B = argmax (44 as the best bin at depth d at round t, and let , E Bi, be any action contained in
B with respect To relate the regret of bin B with respect Bi to the regret of any action a we discretize the bin-level regret at depth d as follows:
pe(uddu 1
|B] I Me(u)du
64 (B i. B) = Bi,a JEB
[ (M((U) - 1e (e + He(at,a)
Bid JUBBI
1
[B] JUEB (mi(U) (e(x))du (e(x)
$ Biaa JUERI (mo(u) Me( + po(az,d)
[me(u) ue())ldu pe(x)
[B] WEB
2
$ 2d
+
5,(1 x))
by Assumption 1.
Summing over the interval
82), we obtain:
8g
2
(B) Σ
8e B)
8e ( + 2a (82 81).
(5)
By assumption, bin B incurs significant regret over (s1, s2]; that is. from Definition 4,
(,(B) > 3log(T) (s2 s1)24.
(6)
Substituting (6) into (5), we get a lower bound on the cumulative regret action a with respect to
x
2
5e ( x)) 2 3log(T)) (82 - =212ad
2d (82 - $1)
2d
(82 2/3
= (82 2/3
3log(T))
(82 - $1)
2d
2d
(82 - 81) 113
2 (82 81) 2/3
3log(T) /
2 22og (T)
(s2 (82-8))17 1/3
2d
for horizon satisfying (og(T) 2
Now, since s2 S 8d, it follows that
2d
(82 $1 1/3 > 1,
which implies the above expression is at least:
log(T) - 8/)
Therefore
82
(B( 3log(T)) $1 21 log(T)(s2 - -1) 2/3 < Σ 51 x))
S Σ
8c(x),
L.e. action x incurs significant regret on interval (81, 82). as per Definition 1.
23

---

D Proof of the upper bound of MDBE (Theorem 2)
Before giving the proof, introduce few definitions and notations that will be useful. A full summary of notations used in the proof can be found Appendix A.
Definition (Bin ordering). For each depth d N, we partition the bins of Ta by ordering them as Ta - ...,, B(²²)
Definition 6 (Replay(s, d)). Replay(s,d) d) denotes replay at depth d starting at round
Remark 2 (Eviction time). A bin B Ta said be evicted round if is evicted at the end of round I, in the sense that B E (.(d) and B $ Be+1
D.1 Bias of the mean estimates
One challenge arising from our discretization scheme is that the importance-weigheen estimate defined (2) is inherently biased. This bias comes from the fact that our algorithm selectively samples arms Iy only from active bins, while evicting bins different depths over time.
Proposition (Sampling bias). For all round i, any active depth d E Dr, and any active bin B E (d) at this depth, the bias in the mean estimate for bin B is bounded as
E [B, (B S
2d
Moreover, the cumulative bias in the gap estimates between any pair of active bins at depth d over interval bounded as:
M[s1,82] v De, YB, B' E B(sieel)
82 0 Amag
Σ
92
E.
[B(BB,
Σ 6,(B", B) $ 1(82 81)
2
Proof of Proposition 3. We begin with the first claim. Let Dr be an active depth, and let B E (d) be an active bin at this depth. For all round by the definition of the estimator, we have for all B Ta.
V((x.)
R (B) P(x, E B Fi-1) 1 (xe E B}
Taking the conditional expectation with respect Fi-1 yields:
/ w
(e(w)ft-1 du,
where fi-1 denotes the density of ma given Ft-1 and 2t E B.
From Assumption 1, for all bin B E Ta and any E B, we have:
1
(Bx(B) - (c)))
(e(x) (z) du I B JUEB [H((1) - Me(x)) du I |B|
B JuEB
2d
Using this, we can bound the estimation bias:
EE-1 [Ax(B)] (B) = / (r(u)si-i du - (B(
WEB
< (m(uu) - pe (B)
NEB
1
1 2d
<
fc-1(u) du
2d
JEB
For the second statement, let B' also belong to (d).. Applying the triangle inequality and the previous bound, we can control the bias the gap estimate:
E 1 8,(('', B)] (,', B)
| [Mr(B')] (B²) E.- (u) + (B)
< | [mt 14 (B') [E, (B)
1
< 2 2d +2 2d
Summing this inequality over the interval [s1, s2] establishes the second claim.

---

D.2 Concentration of the mean estimates
Our sampling scheme (Algorithm 2) is carefully constructed ensure that the estimated gap between any two active bins at any active depth concentrates around its conditional expectation, especially by controlling its cumulative variance. Our result relies on this following inequality.
Lemma 1 (Beygelzimer et al. [2011]). Let (Xe), be real-valued martingale difference sequence adapted to the natural filtration Fr = (XI..... Xt), such that E [X, [Ft-1] = O. Suppose that Xt S. R almost surely and that Σ 11 [ S
Vz. Then for all E (0, 1), with probability at
least 1 6,
Σ se (Vi.log ( Rlog (
Proposition (Concentration Event). Let &l be the following event: for all intervals [81, 82). depths d E [==8 Dr, and hins B, B' (Blsrio)) (d), we have
92
22 Σ
82
8 B)
Σ E (L.BB. c1 s1)2d v 4d
(7)
where is positive numerical constant. Then & holds with probability at least 1 1/T
Proof of Proposition 2. For depth and pair of bins B, B' Ta, define the martingale difference sequence (Mi) (B, B) E ((((BBB)] adapted to the natural filtration (Fi)121
(o(1,, Y((=))))--
Lower Bound on Sampling Probability. Let Ba E (d) be any active bin at depth d at round t. distinguish two cases:
Case 1: dt)... By construction, arms are sampled uniformly at depth do((), implying
P( E Fal (do
2d
Case 2: d + do(t). The replay scheduling ensures that at round t, replay depth d can only be triggered if Tt. 0.8d). This implies that no replay at shallower depth scheduled before can still active at round Thus, when a replay is scheduled at round at depth d, either = dt(,), (t), or all replays at depth d' < d have also been scheduled at time t. No bin has been evicted at these depths before round I, so all bins at depth are children of active bins at any depth d' such that d' D,. This ensures there exists path of active bins from any bin B up to depth do()). Using induction, we now show that
Ve' E D., P(re E Ba (F--)) 1/2"
(8)
The base case at dt(t) is already established. Assuming the claim holds at depth d. For a deeper depth d' > d and any B' E (ddd) with B' Ba, we have
P(x:, E B' B'I (F.
P(z. E B' xr E Ba, F. PP((s Ba F.-
(d(dd) n Children( (B,, B') 2d
2d
2
2d 2d
2
Bound on each M,. Recall the definition of 6, B).
(((x;)
Y((r)) 1 1fz, E B}.
8,(B', B) P(x, B' B(I).
1(z, E B3)
P(x, B(Fr-
25

---

Using the lower bound (8) and the fact that rewards lie in [0, 1], we have:
(B',,, B) - 8,(B', B) 2
Bound on the variance. First, remark that
E (8.( - E.-1 [o.(B', B)] BB)"
< EE [ B)
Applying the definition and the lower bound (8), have
E, 88 (B B)
2 (1/24)²
2d+1
2d
where we use the fact that the probability that za belong to Ba or B' is upper bounded by 1/2".
Final concentration bound. Applying Lemma any interval [s1, 82] for fixed depth d and for any pair of bins B, B' E Ta. we get that with probability at least -6
Σ 8, B)
E BB Bi] <(c-1) 1)
(/les- - 81) s1)2 log
+ 2d+1 log
Taking an union bound over all possible choices of rounds $1, $2 (there are T choices). all possible choices of depths (there are at most m depths, where m S log(T")), and all possible choices of pair of bins B (there are at most Emel (T) T choices of pairing), have with probability least 1 87 log(T),
((81882) Ad E Dr, VB', B E (d),)
t=
s (ee (/100- 81) 81)2d+1 log (3) + 2d+1 log 81)
)
Σ (B(,,, B) Σ
E, (,((',, B]]
t=81
Choosing = 1/7 and e₁ = 7(e 1)v2 concludes the proof.
We summarize the bias and concentration control of mean estimates in the following statement.
Corollary 2 (Bias and Concentration Control). On event &,, for all intervals (21, all depths de E t= Dr, and all B, B' (2) (d).
52
(,',,, B)
Σ (B',, B) s ea log(T) (82 - s1)2d
4(82 81 /1)
Concentration
Blas
Proof of Corollary 2. This follows immediately by combining the concentration event (Proposition 2) with the bias control result from Proposition 3.
D.3 Properties of the eviction scheme of MDBE
We show that, under the concentration event ε,, if bin is evicted by MDBE, then all arms within that bin must have incurred significant regret.
Proposition 4. On event E,, if a bin B E Ta is evicted at some round I, 2 Tha then for all arm E B, there exists an interval (81, 82] with 81 2 Ti and 82 = such that x has incurred significant regret this interval.
26

---

Proof of Proposition 4. Assume B E Ta has been evicted at round t. By design of MDBE, there exists an interval [s S2] with $1 Fi. and $2 such that
Pd N De, B parent Bls (d') s.t. B S B parent and B parent is evicted at round t,
1=
which means that there exists bin B' B(s1,02) (d") such that
Be(B', B parent) eo log(T) (02 81)2d' v 4at + 4(82 s1)
2d
On the concentration event Er, have by Corollary 2, interval [s1, s2).
(Vis2- -1)22 V 440
4(82 - 81)
(B(B B parent))
8, Bparent) - 0i log(T)
2d'
1=21
1=81
and therefore by eviction criteria (+) we have
(V(8)- (/82281)8 ( s1)22 v v²
4(82 - 81)
(B(,,, Bparent) 2 cu log(T)
+
2d
1
(((22-5))22
4(82 81) 2d
ci log(T)
- 81 )2d V 4d
2 log (82 - 81 81)2" V 4d"
for co satisfying co 2 3 C1. Since Eie,, (,',,, papennt) S Ei=,, 5e (Bpareet)), ) this implies that
Bparent incurs significant regret on [$1, 82 (Definition 4). Since Bparents also implies that
incurs significant regret (Definition 1) by Proposition 1.
We now present a complementary result showing that bins which are not evicted must exhibit low relative cumulative regret.
Proposition 5 (Safe bins have low relative regret). On concentration event & V [81, 82], Vel E 02 Dr, YB, B' (d)), if both B and B' are not evicted during this interval, then
#2
8(32 s1)
Σ
8,(B s (co a)) lo) (82 s1)2d V
2d
where co and 01 are the positive numerical constants defined respectively in (+) and Corollary 2.
Proof of Proposition 5. If and B' are not evicted on [$1, 82], then for all B" E B1s the eviction condition does not hold, i.e. have
4(32 s1)
Σ 8, B3) < co log(T)) ( v 4
2d
In particular, for B" B, we get
en Σ 5o s1)2d v 4d
4(82 - 81)
2d
1=
By Corollary 2, the true cumulative gap satisfies
4(82 $1)
Σ ((B,B)s <
8.(BBB)) + ei log(T)) (52 s1]2d v 4d
2d
1=
< (co log (s2 s1)2d V4d 8(82 $1)
2d
27

---

D.4 Relating episode and significant shifts
We show that, with high probability, new episode begins only if significant shift occurs within it. This ensures a correspondence between episodes [t,, t(+1 and significant phases [T,, T++1 In particular, each significant phase overlaps with most two episodes.
Proposition 6. On concentration event ε,, for each episode [t,, 1411 there exists at least one significant shift TÜ [t,, 1.+1/
Proof of Proposition 6. Let [TIm, 7,m++ be the block during which episode [M, 41+1 terminates. By the design of MDBE, the episode ends whenever BMASTER (m)) 0 at the end of this block. Thus, by the eviction condition (+), we have:
Vr E X, 3[s1, s2] S [T.m 7.m+1l 3d N
D.. 3B E B mz) (d) with x E B, 3B' E Bisn.sa) (d) s.t.
8=81
((B',B) co log( (s2 $1)2" (2)22ve V v 4(82 - $1)
2d
1=
Since we are on event & by Corollary 2,
4(82 - 81)
(B'B', B) S
8B(B', c1 lo (s2 ---sss22 s1)2d V 4d
2d
t=8
4(82 81)
(, B)
8,',,, B) log(T') (82 s1)2d V
2d
t=
1=81
(BB',B(a) 2 (cu co) (s2 - s1)2d 4 log(T)) (82 - 100-ss)27 -1)24,
where we used Ba(x) denote the bin at depth containing arm s.
This implies that bin Ba(x)) incurs significant regret on interval [s1, 82] (by Definition 4). Then, by Proposition 1, the
B also incurs significant regret on [$1 (Definition 1).
Thus, every episode contains at least one significant shift.
D.5 Regret decomposition and discretion within one block
We first introduce important definitions used throughout the regret analysis.
Definition 7 (Last safe arm 2²). For each significant phase [Ta, Ti41 we define x² as the last safe arm (Definition 1), with ties broken arbitrarily. For all E [Ts, T4+i lb define at x
Definition (Last safe bin B B.aa)- We denote by B E Ta the unique bin at depth d containing z!. For all E (Te, Ti41 ly we define B =Ba==B Definition (Bin Br,)). For each round t, let Bi, E Ta denote the unique bin at depth containing the arm played at time t: Z, E B,
Note that Bad may not belong the active set (d).
Decomposing dynamic regret into relative regrets. We begin from the definition of the expected dynamic regret:
E [M(TEOEE T) = Σ
sup eu (x) xeX
E
Σ Me (xx)
E
Σ Se(
which decomposes as
T
T
E
5, (xx))
= ー>
8, (x +
Σ
8 8, xx)
1m1
28

---

where zf is deterministic. The first term can be bounded using the definition of 2
LT Σ o = Σ>
Lr log(T) (To+1 -T4)2/3
o,
(x
$=0
The difficulty lies in upper bounding the second sum E
E. 6e( xi)
Without loss of generality,
there are T total episodes, and by convention we set t = T + 1 only t. Summing episodes gives
episodes occur by round
T Σ 1=1
T
+++
5 xn
E
Σ
1=1
We further decompose each episode [4, 441 into blocks. Let M, [ogs (7(1+ 44) +1) be the maximum number of block within this episode. For notational convenience, we can extend Tim
1/+1 for M.. Then,
Mi
E
Σ de (a 2i))
Σ
de (e
m==
Discretization trick within each block. Within each block [T, 7.++1 we relate the regret 5, (x nr)) to the regret of their corresponding parent bins at depth ma introducing a discretization bias of order 1/2"
Than
Tmmml1 11
Σ
x0( =
Σ
pe(xi) (e(e))
t Tom
T.m+1-1
71m-1-1 1-1
pe(x)) Me (Be
Σ
pr(Bi - Me(e))))
t
tm
The first term captures the cumulative discretization error over one block [r,m: T.m+1 at depth m. and by Assumption is upper bounded as
Th.+1-1
(m) (ee(Bi Σ
S 2m (7,m+1 TI.m) S 4th
For the second term, by design of our sampling scheme (Algorithm 2), if Bt,., is active, then conditionally on Bt.m B we have v, ~ U(B). Otherwise, 24z is sampled uniformly from one its active parent at higher depth (that has no active child), and conditionally on Bt.m B we also have It ~ (B), and therefore in both cases, Vt, E (xx( Bt.m = B] = Mc(B). This yields
7mm+1-1
Tmm+1-1
E
Σ t=
Pe(B),n) - (2)()))
= E
Σ
(e(B H4l Bt.m)
t=
Thint1 11
E
Σ
8,(BB. mm Bimm)
L=
Putting this together,
Mi
Mr
Mi 7,
E
de
<E
+ E
Σ
dr Beml)
(9)
m==
Lm=0
m=0
t= Tm
29

---

Upper bounding the bias. Using the definition of Mr, we upper bound the bias over one episode:
M1
4 4
E
4m
6E (t141 - t/)3/3
3
Summing over all episodes yields:
T
M2
Σ
E
4
S 6
(t1+1 - t/)2/8)
(10)
1=1
Summary of regret decomposition. So far, we have shown that expected dynamic regret is upper bounded as
E THDBEE 7)] log(T))
T141
T/)3/33
2/3
E (l1+1 - 11)3/3
1=1
Mr
Tiam Tmmi11-
Σ
8e Br,m)
72
Using the fact that event & holds with probability at least 1 - 1/T3 (Proposition 2), and the fact that rewards are bounded in [0, 1]. we get
LT
T Σ E 1181} (t1+1 - (
T
E [R[TTDDBE T)] & log(T)
Σ
(T41 (T441-7))2) 2/33 +67
21)2/3
+
7
1=0
1=1
T
Mi Σ
7.m+1-1
T2
E
1 (
Σ
de( Be(Bi, i.m Be,m)
+
T3
1=1
m=0
1=7m
Lr
T
= (T)
(Ti+1 Ti) 2/3 +
E [111] (1++1 11)2/3
1=0
T
Mi
7,m+1-1
Σ
E
1{8)}
Σ
Σ
BelBi,m Bemn)
T
+ T
(11)
1=1
m=0
1=
It remains to bound the terms
Σ
E 1181) (t141 - t2)2//3
1=1
and
Mi
7.m41-1 11
Σ
E
1(
Σ
Σ t=7,m
BB Bl.m)
m=0
We first focus on the latter term. We introduce the following useful definition. Definition 10 (Last bin in (MASTER(m). Bl We denote by Bl E Tm the last bin (with ties broken arbitrarily) at depth mn within block [Tt.m, +l that belongs to BMASTER(())
Then we decompose the last sum of (11), and condition on F using a tower rule,
M, T1m=1--1
Σ
(BB k,me Bl,m)
m==0
Tl
Mi Ti,m
Mi 7im 11
E
8, BBasst Bl,n)
E
8: BB
Blast)
1=7).
mm
T
E
E
Σ
8.BButtt Br,m) Fri.
+ IE
Σ E
Σ
Blyo)
Fram
t=
m==0
1=
(12)
30

---

where we recall we defined the filtration (Fi)e21 as Fi = (x.)) with by convention Fi being the trivial sigma algebra. For the next two subsections, we focus on the conditional expectations
af
m
(A) E
1(81}
Σ
8e(Bi.m Bem) Fram
and
(B) E ({8) 7,m+11-
Σ
6,(Bi,
Blart)
and our goal is show that these terms are upper-bounded almost surely by term of order of 4tm We conclude this subsection by noting two important observations:
the start of each block 7,m all previous observations are discarded.
Replays within block mi) 7lm++1 are scheduled 7,m, independently of observations prior to that round. Thus, for E [T,m T..+1| | and < m, Re,d is Fr.. -measurable.
D.6 Upper bounding (A)
The term Ei 6,( Br.) captures the cumulative regret between any bin that deemed safe by the algorithm and the bin Be,, selected by the algorithm each round Notably, Bt.m is either
A bin at depth deemed safe and retained in the active BMASTER (m),
A bin that has been evicted (or whose parent was evicted at a shallower depth d < m) and is being re-explored as part of a replay initiated at any active depth m.
Importantly, evicted bins can reappear during replays, but only through replays initiated at depths strictly less than m. We aim to show that (A) is upper-bounded almost surely by quantity of order 4
Proposition 7 (Upper bound of (A)). There exists a positive numerical constant such that
(A) I CA (T)
Our approach begins by upper bounding (A) through decomposition at depth (t( and leverage the properties of our sampling scheme (Algorithm 2) In particular, it leverages the fact that at each round 1, we choose uniformly an active bin at depth dn()).
Lemma 2. We have that (A) is upper bounded
Ton+1-
òz (Parent do(t)),
(A) E
1{8)
Σ
Fr
[Be(do(t)
2db(()
t=
(dot())(e))
Proof of Lemma 2. For all [Trm 1/ we first relate the relative regret of Bam Blust the relative regret of their parent depth do (t),
de (Blast mm Bt.m) = [e (B(aa))) 1 (t.m)
p4 (Blast) μe (Paren(BBlss do (t)))
+ Pr. (Parent( (Basst last do(t)) - 44 (Parent (Br, (t)))
+ Ne (Parent Br.m. do(t))) - pe (Br.m)
< ( (Bl ae (Parent (glasst do
+ Mr (Parent Bastt do (t))) n4, (Parent((B. (Br,m (t)))
+ Im (Parent( B, do (t))) (4(Bi,m)
< 6, (Parent Blsst do (L)), Parent (B,,, do(()) + 2do(t)
31

---

where in the last inequality we used the fact that Bt.m S Parent Bt.m do(t)), B S Parent Bl dt)) and Assumption I. Note that Parent (B do(t)) is necessarily active at depth dt).). Summing this inequality over the block [T,, 7,m++1
7h -1
Σ
de (Bi Bt.m) s
8e (Parent( (B (1)), Parent do()))
Regret of purents minimum active depth
-1
Σ
2do(1)
cumulative bins
By tower rule, since Fr.m S Fi
we have for the first sum, for any bin B E Tm
-1
E
1{E}
Σ
& (Parent(BBdoo()) Parent(Br.m do(t)))
From
t=
=
E 1{E1}
E Σ
8 (Parent(B,de do))), Parent(Br do(t)))
Fi-1
Fr.m
(=72.m
Since Parent( Br. do)))) is an active bin at depth d1()) and since we choose uniformly an active bin depth do (t), write for any bin B Tm.
8, (Parent(B B, (t)), Parent (B (t))) Frn1|
E
Σ
5, (Parent( B, do (f)), B) TP (Parent (Bt, do(()) = B Fi-1)
BEBi(do(t)
Σ
&e
[do((()
BEB,(do(0)
and therefore for all B E Tm.
Tmm+1
1(8)}
Σ
8, (Barent(B.d Parent(Br..n do(t))) Fri.
1=
ml.
=E 1{8}
Σ
8, (PParent(B,ddo(()).. (EB((do(()
Fm.m
Br (do(
1=7t.
Choosing B Blaas
Tm particular, the result above implies
7.m
E 1(E1}
Σ
& (Parent(Bludt do(t)), Parent BB.m (t)))
From
1=
mm -1
1{8,}
Σ
& (Parent(Blant do(t)), 1))
Fa
[B.(do()))
1=
BdB((do(t)
and therefore
Tm
E
1{E}}
de (Blast Bem) Frem
t=
1-
<
1{81
Σ
Σ
8, (Baet do(t)), B)
2d0(1) From
Be(do(t))
t=
(eBo(do(t))
32

---

We are now ready to prove Proposition 7. The rest of this subsection is dedicated to this purpose. Thanks to Lemma 2, it now suffices bound both the parent's regret contribution depth (t) de Paarntt (B) do(t)): B)
mlm+1
(A.1) E 1(81}
Σ
Frem
(d(d(())
t=
(d
and the cumulative bias term
mmm+1-1
4
(A.2) = E 1
Σ
From
2do(1)
1=
Upper bounding (A.1.). Considering all possible value of do (t),,, (A.1) can be rewritten using
ordering introduced in Definition 5: denoting B B!".... ..... B²² the bins at depth d, (A.1)
m -1
5, (Parent(B Blast d), d), Bc(
E
1(8)}
Σ
Σ
Σ
1(do()) =
F Fi.m
1=
d=U (d)
m1 -1 Σ
2d
6, Paarent( Blast d), (B(k)
Blb)) E B.ld)}
E
1(
[(d(()) =d3
1
Fr.m
(B.(d)
t=
d=U
7. 11 2
5z (Blent B(ll))
E
1{8)}
Σ
(do(tt) m]
if B {B((m)} Frem
[Bc(m)]
1=7Lm
Regret contribation at depth m
Tlmmi
m- 24
8e (Parent(Dlunn d), BBa)) I A(B E BB(a)}
+E
1{
Σ
(do(()) = d}
Frym
[B)
T=
d=0
k=1
Regret contriburion of replays of depih d.c.m.
(13)
We introduce the eviction time of a bin B, which will be convenient to quantify the regret contribution of each bin.
Definition 11 (Eviction time within a replay M(s, d, B)). For all bin B, Ms, d, B) denotes the last round where bin B is active within a replay at depth starting at round 8, M (8, d, B) E [s, ++84). If bin B is not evicted during this replay. we define M (s, d, B) = s + 8d. By abuse of notations. we define (T,,m, m. B) as the last round where bin B is retained in BMASTER (m), and define M (TI,m m, B) T1,m + gm = T1,++1 if it is not evicted during the block [T).m 71,m+1
Regret contribution at depth m. Since BMASTER(M)) is initialized at round Ti.m we have for all bins (k) on event E
n
Σ
Σ
[db(t)=
m m]
8x (Blans, B(b)) 11 B(ak) E [m)))
B,(m)
1=1
2m M m, B(h))
1(do(t) = m} [B.(m)) 8, (Bleet (
1=7L
Without any loss of generality, we assume that (B(h) (22")) is the ordering according to the eviction time of these bins in the block [T.m: Tlm+1 (otherwise we can always re-index the bins), that is,
Tl 5 M (T..m, d, B S M (T.., m. B(2)) < ... S M (TI,m, m. ((2")) < T..m - -1.
Blast
33

---

Thanks to this ordering, we can lower bound the active bin set at depth d as
min
(m)) 2 2nd + 1 k
( mn. mm
and therefore
2
M( )
Σ
Σ
l(do(t) =m} [m, 8. Blint Bl(h))
2
1
Σ
[(do(t) = mm de (Blms Bbh
2
t=
Moreover, since Blit and /% are by definition not evicted on interval [T.me M (7,m, m, Blx)) }}, we have by Proposition on event &
M( m. B.))
Σ
[ddo()) = m3 de (Bimnt B(kk)
7m
8 8( (M m, B!hh) 71.m
< (co + ti) log(()
(M m. B(k)) T, 2m V 4m +
2
< (co + ci) log +8x 4m
- (co 1o)
02 (7)
assuming again horizon T satisfies log(T") > and setting 02 - 8. Therefore, the regret contribution of replay at depth m is upper bounded as
2m ( )
de Blaet B(k)
2
1
Σ
1fdo(t) = =m]
C2 4
Bc(m)
2 +1-K
t=
S (co + ci + 8) log(T)4 (log(2m) +1)
S (c2 + 1) log (T)
where we used the fact that m S log(T))
Therefore, the regret contribution of the replay at depth m is upper bounded as
Fl.m 11
2
5, BBlast (A:)
E
1(8)}
Σ
Σ
(dd(tt) mm] [B.mm)
i B Bm(m))
From
1=
k=1
$ (c2 + 1) lT))
(14)
Regret contribution of replays at depth m. a depth E [0, m 1] and a bin B(() at this depth. We consider the set of rounds > 7.m for which do(t) and B(()) (d),,, and partition this set into contiguous intervals (represented as blue intervals in Figure 2).
Due to the structure of our replay schedule, each such interval must correspond to single replay at depth d, which begins at some round s satisfying Ry,d = That is, each interval is initiated the start of replay and includes only the rounds during which ((()) remains active in that replay.
Each interval concludes either when ((()) is evicted from active set B, (d), or when the replay itself ends at time 8d. Therefore, each interval spans the range [s, M(s d, ((x)), ]], where ((s, d, (²a)) is the final round during which (k) is active within that specific replay (see Definition 11).
d
The key idea of our analysis is to treat these replays depth independently, and quantify the regret
incurred due to playing the bin Bb(k) during each such replay window. This allows us to control the regret by bounding its contribution separately within each replay interval.
34

---

Ra =1
7lm++1
duii d
Figure 2: For given depth d, partition of the rounds of block where do d. Any of these blue intervals should be initialized by the start of replay at this depth, i.e. Ra,d = 1.
Following these remarks, we can upper bound the second sum Equation (13) on event E as
&e (Parent Blons d), BBb))
m
If BBah Bi(d)}
(db(t)) d}
[B)
2m
d=
km
2d
M( 8e (aarent( Blase d), B,(()
Redd
Be(d)
m,
-1
24
Mir,d, B
Σ & Parent( Blpee d), B3
Red
min
KE M(i,, [d)
d=
Again, without any loss of generality, we assume that (B ..... .... to eviction time of the replay at depth d starting at round s,
((2²)) ' is the ordering corresponding
S (s, Bs < (s,d,
-... S M(s d, B(2") S s
Thanks to this ordering, we can lower bound size the active bin set at depth d as
min ((.
Be(d) 2d + k
and therefore,
m-1
M(e.d
R
Σ
(Parent(Biatt d), B(()) BB())
min MM, 12 1101) [B((d)
2
((s.d,B(a)
Σ
Rad
Σ
8e (Parent (Blust d), B(()))
2d
l
d=0
k=1
We now proceed bound the cumulative relative regret incurred by bin ((A) with respect to its parent Parent Blast d). By design of Blast is safe bin over the entire block), it follows that its parents {Parent( Bllsst d) HED, must also be safe. Indeed, if a parent Parent Blast d) were deemed unsafe at some active depth d E D,, it would necessarily be evicted. Due to the eviction mechanism, this would result in the eviction of all of its descendants, including Blast itself, contradicting the assumption that Blast remains safe.
Now, since the bin B(h) active over the interval (s, Ms, d, B(b)),, we can apply Proposition to obtain the desired bound the event ET.
35

---

Σ
de (Parent(B).m) d), d).
(co ei) log(T) 2d (Mss, BBb)) $) 4a
d, -s)
8 x 8d
x (co + a log v 4d
2d
(co + ta) log +8x48 4"
S (Co + + 8 (T)
S c2 log()44)
assuming horizon 7' satisfies log( 2 1, and where the second inequality follows from the fact that the length of a replay at depth d stating at round is at most 8d. We used the same definition of co as above. Therefore, we have
1
2d
M(sd,ng Σ
de Parrent (Blant d), B(O))
E
1
Σ
Rud
Fr
2
k
d=0 k=1
T=
1=
2d
m+1--1
$ 02 log(T)E
118)
Σ
Σ
Re
Frim
2d
d=0 k=1
Tl.m
F1mi1-1
(cglog(T)L
1{E}} Σ
Σ
(log(2) + 1)4d
Fr
d=0
1mm-1-1
<o2log2(T))
1{8) Σ
Σ
R
From
d=0
8=
m-1
11
<2 (
Σ
Σ
Frim
2=
8=
where used the fact that S log(T).
We now leverage the fact that relatively replays occur in expectation, and the fact that the Bernoulli random variables Ra sampled independently of the observations collected during the episode. More precisely, all Bernoulli variables are drawn i.i.d. at the beginning of the block, i.e. at round t t= Ti.m- This allows us to treat the scheduling decisions as fixed ahead of time. Furthermore, by the design of the replay scheduling mechanism in Algorithm
m m+11 m+
m
Ti mm
1 7.m 0[84]]
E
Readd
Fr.m <
Vgdgd Frrm
72m
d=0
d=u
7. +1
gdd
id
d=0
m-1
<288
4d V
V2m
< <2/8/8m
< 668 Tm
(15)
V2 -
36

---

Therefore, the regret contribution of replays at depth d E [0. m 11 is upper bounded as
m,
m-1
2d
[(do(t) dd 6: (Parent( Blm d), (/.)
1(8))
Σ
Σ
1 {1( E EBi(d)}
F From
[B((d)
72,m
S 66 Sc2 log 1 (T)4TT.
(16)
From Equation (13), combining Equations (14) and (16) gives the desired rate for (A.1),
(A.1) & 18(c2 - 1) log (T)
(17)
Upper bounding (A.2). To bound this term, apply the same reasoning previously used to control (A.1), and in particular the partition argument of Figure 2. By observing that each replay at depth do(t) is initiated by round such that Rs.d and by using the fact that each replay depth d lasts most 8 rounds, distinguish the cumulative discretization bias incurred at depth and the one incurred at other depths d < m,
(A.2) = E 1{
Σ
From
2do(f)
7=7mm
m+
m Tlm+1
E
11 (do(()) = =m}
Fr.m
+
(do(()) = =d] Fr.m
2m
2d
1=
d=0)
1=
m Tl
<4m+1 + 4E
1 (do(t)) =d Fr.m
2d
t=1mmm
71,41-1
< <1nh1 + 44
Σ
Red grl 2d
1
Frnm
+ -4
+E
F From
which is exactly the same term we bounded in the proof of (A.1). By (15) we thus have the upper bound d=0
(A.2) < 4m+ + 24 x 4th 28v8 4m
(18)
Conclusion. Combining (17) and (18) gives the desired rate of thh for term (A), as
Tlm++1
(A) E 1{81}
Σ
8e(Blant Bem) Fri.m
1=
< (18(02 + 1) 1T) + 28V88 4m
Choosing CA = 18(c2 + 2) concludes the proof.
D.7 Upper bounding (B)
We recall that term (B) writes
7L -1 6,(Bi,
BB) = E 1(8)) Σ
Blast)
F
As discussed Section 5.3, the main challenge arises scenarios where significant shift occurs (as defined in Definition 1), causing the identity of the last safe arm of (and consequently the bin Bi to change. In order to avoid incurring large cumulative regret before this shift is detected, the algorithm must initiate replay at the appropriate depth to identify the change in environment. We claim that (B) is also of order 4th almost surely.
37

---

Proposition 8 (Upper bound of (B)). There exists a positive mimerical constant such that (B) S en
To prove Proposition 8, analyse the cumulative regret incurred by B with respect to B by decomposing the rounds of the blocks into bad segments, that is, time intervals during which Bi incurs significant regret relative to the safe bin B Importantly, by construction, B is never evicted during the block [Tim, 7,m-11 - 1], and thus remains active at depth throughout. However, since B is only revealed at the end of the block, we must define bad segments relative to all possible bins at depth m.
Definition 12 (Bad segment and midpoint of bad segment). Let (Tims n,m++ 1( block, and let [T, T+41 be any phase intersecting this block. For all bin B E 'Tm define rounds (s (B)); with 2 (B) E [T.m V Ts, T++1 A Tim 8 recursively follows:
(B) = T.m V Tr.
(B) is the smallest round in ( A T,m=1l such that
E
&B mm B) 2 cs coclog(T) (6T)(B (B))
LEST
(B)
where C2 is fixed positive numerical constant. For all bin B Tim we define the midpoint of bad segment [s s + as the round
8/. (B) + (1)+
$ (B)
Now, goal is to analyse the relative regret of any bin B Tm with respect B these bad segments. To build intuition, our objective is to prevent bad segments from accumulating for any bin B E Tm. Fortunately, the design of our replay mechanism ensures that if well-timed replay at suitable depth is triggered at the start of a bad segment, it can promptly detect the shift in rewards and evict B, thereby limiting the incurred regret.
Proposition 9 (Properties on bad segments). Let B E Tm be a bin and let [+ (B), m 8 ( be a bad segment. Then, on Er, any replay starting at round tstart E [8TTy (B), + (B) never evicts
Parent Bi for d E M==aar
(B)))(()) DDr Moreover, if a replays at depth da,j satisfying
gdaat S < [ S 8d..
starts Istart E (B), 8 (B)], then evicted by round (B).
(B( Proof of Proposition 9. Assume a replay evicts Parent (Bf Bi,m. d) with d E Ar Dr and lstart 2 s (B) before round (B). Then, by Proposition 1, it means that, on event E,, every arm Bf_ incurs significant regret (Definition 1). This contradicts the definition of B Indeed, by definition, xy does not change [Istart; mm +1++ C [7,, 7++1), neither does B Therefore, such replay never evicts Parent B _, d).
11(B)
Now, for all B E Tm, we have
* (B)
+ (B)
47 (B) -1
BB Lam B)
& (B B)
5, 6.(BB.... B)- < (B)
(B)
By definition of bad segment (Definition 12).
(B)
(B t.m B) 2 C3 log(T)) 2m (s
sTh (B))
38

---

and since s (B) is defined as the first round that satisfies the above inequality,
T (B)
BB B) S cs (Tg (B) 8, (B))
By combining these two inequalities above,
1 (B)
BB B) 2 cg log (Tg (Vo -5 -B) V (B) 2 (B)
log( (V) 2 -B)
4
where we used the inequality Va + b
vā L
Since Bi,,. active during the whole of the bad segment, on ε,, we have by Corollary on event &,.
C (B)
(B m. B)
8mh (B)
(B)
4(s
1,j+1 (
(B)
8
BB)
Σ
(B B) -a log(T) (0
m (B])+((B) (B)
- (B))2m*
2m
(= (B)
4 T0
(B) -
57, (B))
-a) log log(T) V (s (s (B)
$ (B)) 2m
2
Using the fact that 1. (B) - 3 (B) gd < gm+1 we have
m ( - (B)
(B) 8v +1 (B) 8 (B) (2v2)
2
2
S 8 2 (8 +1++ (B) - 33 (B))
and therefore
th +1
(B)
BB mm B)
2
C3
32 log (T)
log(T) ( 8リ. (B)) 2m
4
t (B)
Assuming horizon large enough, egg. log(T") 2 1, setting Cg = 140 + 4c₁ implies
Ta (B)
(B mm B) 2 3log(T)) (on)+1 (B) 5 (B)) 2m
(B)
and hence by (+), on event &, B is evicted.
Having established that a well-timed replay the appropriate depth can evict bin B, it remains to demonstrate that such a replay is indeed triggered before the cumulative regret accrued over the bad segments is too large. To formally define the earliest round at which this cumulative regret becomes significant, we introduce the notion of a bad round.
Definition 13 (Bad round with respect to bin B). For all block (Tr, Ti.m for all bin B E Ti we define the bad round with respect to B as
st.m (B) = inf
8 > Fl.
Σ
s sB)( > ei log n,m)
(P,)))(
A (Timm +8")
where is fixed positive numerical constant, and we define the set P(B,s) as
P(B, s) (i,5) i,j N,, such that [s (B), (B)) is bad segment and (B) < ss.
39

---

Now, let [T.m, 7,m--1,, be a block, and let B E Tm We distinguish two cases for this bin.
Case 1: the bad round happens after the end of the block (St,m (B) 77m 8m)). By applying the definition of 8t,m (B) (Definition 13) directly, we have
E
2 (5 S. (B)) ca log()) 8m22 (8m22 c4 log(T)4"
(L))E((B.s,mBB)
Case 2: the bad round happens before the end of the block (31.m (B) < T1.m + ) In this case, we claim the following result.
Proposition 10 (A well-timed replay at suitable depth is triggered). Let [Tim, T, be block. We define E2 (m)) as the following event:
BB E Tm such that 8t,m (B) 11,m+1, there exists bad segment (B)), m 87,+1 (B) such that 81 < 81,m (B) and a Replay(/start: dis) such that lstart and di, satisfy
(Definition 6)
Istart (B), mn +1 and gd. S (87++1(B)) - o7) S gd.
Then, {T()))) holds with probability at least - 1/T22
Proof of Proposition 10. Let [m, Ti.++ bloak and B E Tm such that st,m (B) < 7i, 7i,++8 +8 Let di the integer satisfying
gd. + (B) ( S gd..+22
First, we remark that d " (B), 8 (B) and (1,m only depend on the fixed bin B, the starting round of the block J.m Bi (which is deterministic), and the randomness of scheduling of the replays. Using Chernoff's if bound over randomness of the algorithm conditionally on Fr... gives
(B)
(B)
P
Σ
Σ
R Ri,
S E
Σ
Ri,
F
F
F
Fr.m
(A.))P(B, (B)) (B)) (B)
[k.))P((BBr (B)) t
8t (B)(B)
S exp
E
Σ
Σ
Re,dy Frim
(19)
(L)))P(B..L.)) (B)) t= (B)
Then, we lower bound the expectation (19),
2 (B)
Σ
Σ
Ri,des
Fr.m
(o.j)PP( (B)) t= (B)
S (B)
1ft 7.m = 0[8di,]]
E
Σ
Σ
/8duo
Fr.m
V Tim
(B (B)) t=
E
Σ
V2 F
(1.))P(B)
Sig (B) Tl.m
IV
Σ
8
877
Frem
St. (B) Tl.m
(L.))P(()
9
IV
lTg(
where use the fact that there is at least one round /. E (B), 8 (B)) such that ( L-77m Tt 0f8dss).
(..++(BB), (B)), and where i.e. that at least replay at depth di,j that can be scheduled in [ (B), s1.44
40

---

used Definition 13 in the last inequality. Setting C4 = 192, we have
(B)
(B)
P
Σ
E
Ri S
R
Σ
Σ
di
Frim
Frem
(BJ)
ty (B)
(L.) (B)) (B)
S 11/T".
Taking union bound with respect to all possible bins B E Tm (there are n S ' choices) concludes the proof.
Therefore, using Proposition 10, for any bin B E Tm. on event E1 n &2 (T.m). we have that there exists bad segment [s (B), 8m +.j0 (B)) such that
(B) 81,m [B) < 7, and there exists a Replay(fstart: di,50) starting within this segment, fstart E [s>]] (B),
sm i.jo (B)) and di satisfying gdaiio I s $1 (B) s (B) I 8 +2 By Proposition 9, this implies that bin B is evicted by round %.o++ (B). Therefore, on & n (T).m)) using the definition of the bad round
$1.m () < T1,++,,
Σ (B.))P((B....m
2m 8m (B) - (B)) S c4 log(TT) 2m Tlm)
S c4 log(T)44
Since Proposition 10 holds uniformly over all bins B E Tms it also holds for the particular choice B Blast and hence in both cases $1, (B) T,m + 8 and st,m (B) 7,m + 8m, we have
Σ
2 (s +1 (Blust) (1 2 (Blast) S log 4T
( m (Bla))
Now recall by Definition 12 that am Jooo+1 Blast) is the earliest round satisfying the lower bound on the cumulative regret
$o (B
Σ
Blast) 2 03 log(()) 2m (5%) (Blast) (B
(Blast)
(Bluat
Therefore, up to round
+1 (Blast) 1 included, the cumulative regret can be upper bounded as sn
1. (Blunn)
Σ
Blunt) I es log(T) 2m smm (Blust) (B
sm - (Blust) -
(= 1.30 (Blutt)
Since on event & n (T(,),) Blus is evicted by round s (Blant) we can upper bound the cumulative regret contribution of Blas with respect B over all bad segments of Blust.
e 41 C (Blast
Σ
Σ
(B) Blast) I C3C4 " (m
(20)
(L mn (Blas)) t=g (Blaee
remains to bound the regret incurred the non-bud segments. To this end, observe from Definition 12 that each phase contains at most one such segment. Therefore, there exists a positive numerical constant C5 such that
Σ
Σ
5. i, Blast) cs 4m
(21)
IS [T T. mi st.. I is non-bad segment tE!
41

---

Summing Equations (20) and (21) gives the total relative regret of B with respect to B over the block on event & 0 (T,,)))
7-m+1-1
de BB Bl - (caC4 cs) log (T)
t=
Finally, we use the fact that event (m.m) holds with probability at least 1/T2 (Proposition 10),
m-m-1
(B) = 1
Σ
Se
Blaa))
Frrm
7.m+1-1
18 n (2(TL
Σ
Be
de mm
Bloat)
Fre.
Tlan++111 Σ
+ E
1{81 (
8 Blone)
Fr.m
8
+ $ lo
T
S c log (T) + T
where we used the fact that 1[2 (T.,,) s (82).
Choosing CB = co + 1 concludes the proof.
D.8
Conclusion of the proof
Recall from Equation (11) that we have
7
E [ TTDBE, T)] < log(
T41 - 7,)3
T
T
T
7mm+1-1
6 E
Σ
(ti-1 (t-1-
E
1(8)}
Σ
Σ
Be(Bf, Beml)
1=1
t=1
m=0
1=7t.
Propositions 7 and 8 prove that the last sum is upper bounded
Mi
Mi Σ 4Th m==
E
1
Σ
Σ
(B Brm)
< <cA (ea+cB)lo log (
(T)
m=0
1=7.
< 6(cA + cB) log (T)L
(t++1 - 2//
< 6(cA + cB) log (T) ( (441 (441-44)2 42)2/3
CA CB
7
where we used Equation (10) for the second inequality, and where we reconditioned on event E₁ in the last line. Therefore,
7 CA CB
[R[ (TDBEE T)] S log(T))
(T41 - 7/3
T
T
T Σ
6E
1
1{8)}
Σ
(f141 2/3
+ 6(cA + cB) log2(())
1{8))
(t++1 - 2/3
1=1
(22)
We conclude the proof by relating episodes and phases, which will permit to bound the final term
T
1 {1
Σ (441 - 2/3
1=1
42

---

Definition 14 (Phases intersecting episode 1). We define the phases intersecting episode [tt, tt+1l as
Phases(tz, 1++1) {i [ir] [Ts, T++ T [4, +++l+ 0)
With this definition, rewrite the upper bound cumulative regret over each episode
T
E
1(8,)
[t41 - t/)2/8 (0E))(t+1))))
s E 1(
Σ
Σ
(T++1 (T+1- - 22/3
1=1
1=1 (ePhases(tt
Recall that Proposition shows that on ε each phase [Ti, Ta41 intersects at most two episodes. Therefore,
I E
L (T+11 T2)2/33
E
1(8))
Σ
(T++1 - -2)3/33
S
I=1
(EPhaee((t.b441)
i=1
and finally conclude the proof by plugging the bound above into (22),
E [R(TTTDE 7)] S (T)
(T411 -
+ 7 CA +
CB
T
1=0
Lr
LT
+ 12
(i+1 - T/)2 + 12(CA + cB) log (T)
> (T+11 - 2/3
iml
Fr
7 CA + CB
(log(T) + 12 + 12(CA + cB) log
(141 - -1)
T
Lr
E log (T)
T+11 T/)3/33
where cj 12(CA + cB) + 2. This completes the proof. We summarize in Table the exact values of the numerical constants used in the proof.
Constant
Numerical value
Co
3 1) 7(e 1)v2 co + C1 +
C1
C2
C3
140 + 4c1 192
C4
0s
Equation (21) CyC4 +
C6
CA
18(co + C1 + 10)
Cn
CB + 1
12(CA + CB) +2
Table 2: Summary of numerical constants used in the proof
E
Proof of Corollary 1
Recall the definition of the total variation over the horizon T:
T-1
VT
Σ
- xE
max
Fix a phase [Ts, T where T441 S T 1. Define the total variation within this phase as
T41-1
Σ
max [144(xx) - [4(()))
43

---

Let 24 argmaxxe[o..1 Mri4a (z) denote the best arm at the end of phase i. By definition, there exists an interval ($1, 82] C (Ts, Ti+1l over which x; suffers significant regret:
Σ (((2)) 2 lTg( (s2 - 81 )2/3.
Now observe that
1
(32 81)
2
(32 8//1/88
(Te+1 T()
1=
t=
which implies
$2
log(T)
6,(2;)
(Ti-1 1/3
1=
Hence, there exists at least one round
& E [2] such that:
lTg(T)
8c, (xx) 2 (T1+1 7,)
Define 7. = argmax, Mr, (2)). Then:
8 (xx) S (e, - Me, (xx) + uhi (20,) - p (3:)
20
$ 1 (2t) - Me: (x:)l + Ieke (3:) 1 (+)))
2V (1ate11))
Therefore, assuming log(T) 2 1, we conclude that
1
S 2V (7,74))
(23)
(T+11 T,)1/3
We now recall the upper bound from Theorem 2:
Ly
E [[mma T)] Elog* (T)
Σ
(Ti41 - 7/)2/3
1=0
We decompose the sum as:
LT-1
L
(T+11 - 7,) =T -
22/3
(T141 17)2/3 < 2133
7/)2/3
(T41 -//2//3
==0
1=0
1=0
Applying Hölder's inequality gives
L--1
1
(T41 7/33/3
(T++1 3//3/11
(Tit1 - 7;) 2/12
1/4
3/4
Lo
1
Σ
(T++1 - -i))
(T+11 1/3
1=1
Finally, by inequality (23), we have
2
VInTaa)) $ 2VT.
(T+1 1/3
Therefore,
T---1
(T - - 2/3 < 1/4 x
T3/4 21/412/47711
44

---

F Proof of the lower bound (Theorem 1)
Proof sketch. The proof of Theorem relies on the following ideas. First, note that the lower bound T2/3 follows from classical results of Lipschitz bandits [Kleinberg, 2004]. To prove the lower bound either with respect to total variation Vr, or with respect to the total number of changes Lr, we construct T/T stationary sub-problems with horizon T to be chosen later. For each problem, we rewards function. Each of these functions is almost flat, with the exception of one bump of size 7-1/3 hidden among K possible bins. Classical arguments show that any bandit algorithm will misidentify the optimal bin with constant probability in some problem instance, thus suffering a regret 72/3, Then, we create a dynamic problem instance by concatenating T/T such problems, where the reward function corresponding each problem of horizon T is chosen independently. The total regret of any algorithm must then be
design K 71/3 possible Lipschitz-continnne
T = 2/3 = 1/31/3
To obtain a lower bound depending on the number of reward changes Lr, we set 7 T T/L, so that there exactly T/T stationary sub-problems. This yields regret of the order /|/312/ To obtain lower bound depending on the total variation Vr, we T (T/VT)4/4, Then, we see that there T/T changes of magnitude - -1//3 each, so that the total variation is indeed T/T T 1/3 --1 V7; moreover the cumulative regret over all problems is 1/3 73/441/4
In the following, we assume that, conditionally on 2t, the reward is a Bernoulli random variable with mean (zz).
Notations.
For some integer K 2 2 be specified later, we set T = K3 and e 1/(2K) (note that e < 1/4). We define L = [T/r], and for I E [L], we define the stationary phase pl = [(1 1)r
-1.1111,, 1}. We also define the last stationary phase P = (rl....., T). For k and we define In K -1 K 1]. Finally, for a given sequence of rewards μ4, denote by E,, and PP,. the expectation and probability when the reward sequence is μ.. Note that at each round 4, the algorithm т only depends on an internal randomisation and meeasubalee events. Thus, for all / < L and all mea-uuauee random variable X and event F, E. [X] and P, (E) only depend on the sequence of rewards up to phase I, i.e. on (pe))snt In the following. we therefore abuse notation, and define for reward sequences μ of length rl, the expectation E,, and probability P,, pertaining to the first I phases, i.e. to Fea-meauurable random variables and events.
< K, define the intervals 4 = = kk-
K '
Reward function for a stationary phase. We define the possible choice of reward function during one stationary phase pl. For each k {2,..., K), define the function m* [0, 1] + (0, 1] as
1 1 c m (x))))
r 2 1
2k
)) 1 E 1x)
1x
(c-
x-
2
2
2K
We also define
1-c 2
m (x)
(x [T).
Note that for [K], when the mean reward function is m² the optimal action is 2k-1, moreover K
any action chosen outside of interval T will have an instantaneous regret at least 5. For / E [7.] and k [K]. denote No = Eiep! 1 {ar E I& the number of actions chosen in interval I& during the stationary phase pl. Examples of possible reward functions for K are given in Figure 3.
Sequential construction the non-stationary reward function. For a given algorithm n, we build difficult non-stationary reward function sequentially. We show by induction that for all < L. there exists a non-stationary sequence of reward functions (14) (egir such that the expected cumulative regret of algorithm notation and define Po = 0, so that the base case of the recursion (corresponding to [ = 0) becomes trivial.
the stationary phases Pı, .... Pi is at least 0 for all I [L]. We abuse
We then proceed to prove this statement by induction. Assume that the statement holds for some such that 0 < ( < L and some sequence of reward functions (Hu)stt. For k < K, we define μ* as the
45

---

772
I1
12
18
14
15
I1
1g 19
11
Figure 3: Reward functions m² (left) and m (right) when K 5.
extended sequence of rewards such that uu pe legtr + m² (rres((+1)r- Then, let ke be defined as k- argmin E [N]+*]]
It holds that E,, [NV+]] S R.
Now, k 1, it means that under p², the algorithm т chooses in expectation at least (K-1)r actions outside of interval 1 in phase + 1. Then, the regret in this phase must be at least (K-1)- x f rs K2 //2 In this case, using the assumption that the expected cumulated regret 8
&
of algorithm over the stationary phases P1, .... Pi is at least 0.01 121, we find that the cumulative rewards up to phase Pi+1 is at least 2 + 1), thus completing the induction step. We therefore assume henceforth that k. o 1. Now, denoting K. (P., Q) the Kullback-Leiibee divergence between probabilities P and Q, and by kl(p, q) the Kulbback-Leibler divergence between Bernoulli distributions with parameters p and g, classical arguments (see, e,g., [Lattimore and Szepesvári, 2020, Chapter 15.1)) show that
K. (PPN,,Ppr
Σ
Eyi [kl (mm (ft), (se))
+k(t5+(+11
Now, for $ Ix., kl (ml (æt) mnh (xx))
Moreover, for all [0, (26=-)) Thus,
0.
kl (m= (xa), m² (xx) < kl m2 (
-mk"
1 E Is mm ( 22k - K" 2k (2k--1)
K. (P (Pw) PaN))
Σ Byd
K (
K
1 1+6
< Epa [N kl
2
2
< T 4e2
K
3
K 4K² =1
where we have used the definition of &s and of and e. Now, we apply Bretagnolle-Hubee Inequality (see, e.g., [Lattimore and Szepesvári, 2020, Chapter 14)) the 7-(4t))-maauuable event
= [N < 3) This yields
1 Pys (A) PuL (A9) > exp (-K (PMt, Parr))
2
1
exp (-1).
2
Using 1/ exp (-1) 2 0.18 and 2 max((a, 6) 2 + b, we find that
max (Pps (A) P (A9)) 2 0.09.
Assume that P,, (A) > 0.09. On the event A, the regret phase I under reward sequence j is at least 7/2 x 6/2 K2 /8. Thus, the expected regret phase under reward sequence μ² is at least
46

---

0.01K². Similar arguments show that if P pa. (A*) 2 0.09, the expected regret on phase under reward sequence n² is at least 0.01K²2. Using the induction assumption, we find that the cumulative rewards up to phase P1+1 is at least 0. + 1), thus completing the induction step.
Conclusion. The induction above shows that for all K 2 2. there exists sequence of reward functions 14 with a most [T/K²] shifts such that the total cumulative regret of algorithm π is at least 0.01[T/K*)
Assuming moreover that K (T (1/2)1/3 we see that | 2 (/(KK)) so that the regret is at least 0.005T/AA / We now consider the two lower bounds separately.
K2, JK2
Lower bound depending on Lr. For LT E {0, 1, the bound follows from classical results on Lipschitz bandits (see, e.g., Kleinberg [2004]) by noticing that since there exists a stationary problem and a constant c > on which any bandit algorithm must have regret at least 2/3//3 there exists a problem with 0 shifts (i.e., at most Ir) such that the regret is at least cT. cT.1/3722/3 /2. Therefore, we assume that Lr > Then, setting K ((T/Lr)) 1/33, we see that K - T/2 Thus, the non-stationary reward function designed above has regret at least 0.0057 K 2 0.00572/3 1/33 Moreover, this reward function has at most LT changes.
Lower bound depending on Vr. For VT < 2T'1/3 we have Vi V//413/4 < 272233 the result follows from classical results on Stpschitz-continun there exists a stationary environment and a constant > 0 on which any bandit algorithm must have regret at least 2/2/3, Therefore, we assume henceforth that VT T Then, setting we see that K3 < T/2. Thus, the non non-stationary reward function designed above has regret at least 0.0057/ / K 2 0.005T8/4v// Moreover, the cumulative variation of this reward function is at most Vi.
bandits (see, e.g., Kleinberg [2004]) by noticing that
K (T/Vr)
G Extensions
G.1 Extension to multi-dimensional action space
In this subsection, diseuss how extend our algorithm and results multi-dimennional spaces.
We assume that at each round, the player chooses an action in the set [0, 172. where p E N, is the dimension. We assume that each mean reward function He [0, 112 + [0, 1] satisfies the following Lipschitz condition:
Problem setting in dimension
Va, E 10,, (pc(2') - pc(x)) s - | x' x'llps
vp
where ||-1|p denotes the Fuclidean norm in dimension p.
In dimension p, classical results show that when the horizon T and the problem is stationary, in the worst case a minimax-optimal algorithm can learn the reward function up to error of order lT) ,ト2, and incurs a regret of order log(T)) P+1 This justifies extending the notion of significant regret to p-dimensional action space follows. We say that an arm [0, 1)2 incurs significant regret on interval [81, 82] its cumulative regret on this interval is lower bounded as
Σ 8,(x) 2 (sg 81)
(24)
Then, based this definition, define the significant shifts and significant phases the same as in Definition 2.
Adapting the algorithm. To estimate the mean reward function in dimension p. we rely recursive p-adic partitioning of the action space. More precisely, we can define p-adic tree T [Ta]aen as the hierarchy of nested partitions of [0, 1]2 at all possible depth d E N, where Ta denotes the partition of [0, 1]2 into bins (i.e. hypercubes) with side length 1/2d.
We also adapt our doubling trick, considering blocks of duration Tr,m+1 - 72.m = (p+++2) Then, on the m th block of the 1-th episode, consider the MASTER set the bins depths If the rewards are stable enough during this round, we expect the regret of the block to be of order (p++))
47

---

We can use the same sampling strategy presented in Section 3: given set of active depth at time t, we sample a bin uniformly at the shallowest active depth. and then proceed by sampling uniformly bins among its active children at the next depth. An analysis similar to that of Proposition 2 reveals that the probability of sampling bin at depth (given that this bin active) is lower bounded by 2-pd. Then, the error for estimating the cumulative gaps between two bins at depth d active between rounds $1 and 22 must be of order v(s> ) v 4nd + 23
This motivates our considering an new eviction criteria of the form
92 (B(B' do (log(T) $1) s1)2nd V 4nd
(82 81)
max
B'EB (
2d
for some well-chosen positive numerical constant C--
As previously, we choose as duration of replay depth d the length of the d-th block of an episode. In the p-dimensional setting, this implies that we should schedule replays of duration 24(x+2) at depth d. Note that such replay allows to estimate the cumulative gaps of two bins up to precision 2d(++1).
It remains to choose the probability of scheduling replay at depth d. At all times [T, +1,+1 such that Tm 0 [2d(++2),, we schedule replay of duration d with probability Ps,d given by
2d(p+2)
Ps.d
71m
Regret analysis. Simple computations show that there are on average 22 /2d(x+2) replays of length 2d(++2) during block of length 2m(x++),, each one with regret of order 1d(++)) Thus, the regret due to replays depth d over this block is of order /2m(p+2) 222pp+))2))))+ /2 Summing over the depths d < m, we find that the total contribution of the replays over a block of length 2m(p++) is of order 2m i.e. of the same order as the minimax-optinme regret over this phase in the stationary setting.
22
To conclude, we argue that this choice of replay probability allows detect significant shifts fast enough. Assume that the mean reward of an optimal arm undergoes a shift of magnitude 2 dp, so that it becomes sub-optimal. The algorithm should identify it as unsafe in less than D rounds, where D is such that D2-dv <2m(p+), Le., D S 2m(p+1)+dp. Now, choice of Ps.d ensures that there are approximately /2mm(p+2) /2d(p++) replays at depth d scheduled during the block, so that on average, replay at depth d is scheduled every (2m(p+2//2dfp+22) rounds. Noticing that (2m(p+2)2d(x-2 < 2mm(p+1)-dp see that enough replays of the adequate length are schedule, so to ensure that a significant shift does not go undetected for too long.
Thus, the algorithm has almost minimax-optimal regret over stable phases, and detects quickly significant shifts. Conducting the same analysis as in the 1-dimensional case, we see that in dimension p the regret of our algorithm should be bounded as
ir
E R R(TOBE. T)] S c
which yields the worst-case regret
E [[ T)] S e' log(7))² 2
for some positive numerical constant c'. We emphasize here that both the phases (R) and number of phases LT are based on the definition of significant shift for p-dimensional actions, given in Equation (24).
G.2 Extension to Hölder bandits
In this subsection, discuss how to extend our algorithm and results to Hölder bandits.
48

---

Assumption 2 ((K, Höller mean reward functions). Each mean reward function satisfies
(3 1)
Yr E [0, 1]. (4(x)) /4 (2')1 S k|x =x'1.
Problem setting for Hölder bandits. We start by defining significant regret in this setting. Arm x E [0, incurs significant regret on interval [$1, 82 if
110 be(x)) 2 log(T)(s2 81) 1+28 K 1428
1=81
To give intuition, oracle policy Toracle that knows when the significant shifts T, ''s discretizes the space into K; = (Ti+1 - T,) 1िउ3 x- bins at each phase [Ti, Teil and incurs a regret of
Ô (T++1-7) 7.) 28 x 1-23 (by directly adapting results from Kleinberg [2004]), where Ô only hides
logarithmic factors and numerical constants that does not depend on or B. Thus, the dynamic regret of the oracle upper bounded by (up to polylog factors)
Lr
E [R oraalee T)] S Σ (Ti+1
Ti)
I123 KITZ
2m
S T
We now show how to adapt MDBE so that it achieves this rate adaptively. Adapting the algorithm. We consider blocks [T,,, 7, i[ of size
7m 7,m 2 /22
Thus, on each block, discretize the space into
(T 1 7.m T K 1733
2
bins, allowing us to consider the MASTER set as the bins depth m (that is, the of bins Ti of the dyadic tree). If the rewards are stable enough during this block, we expect the regret of the block be of order
R(m) (7,m+1 Tl.m)
1+3 1+23
1523
2m
For the replays, we choose as duration of replay depth d the length of the d-th block of an episode: this implies that we should schedule replays of duration
((d) = 2d 21())
at depth d, and discretize ((d) 1426 1रकह 2d bins. Such replay allows estimate the cumulative gaps of two bins up precision (1++6
Since we use exactly the same dyadic strategy is exactly the same, as well as the concentration error Proposition 2. Only the bias for
(Ta)ısasm in the 1-Lipschitz case, the sampling
estimating the cumulative reward two bins depth d changes, and will be exactly equals to 2(32 $1)r s1)x/2d6 over an interval s2). This motivates new eviction criteria depending on the Hölder constants (n. (), of the form
(82 $1)K 2db
(((BBB)) co log((T) s1)2d V 4d
max B'EB (2 1=81
where = 7(e 1) is numerical constant.
It remains to choose the probability of scheduling replay at depth d, given round. At round
8 E [7.m, Tl such that Ti, = ([{(d)) we schedule a replay of depth d < m with probability
Ps.d given by
2 21+28)
Pa.d
(we always have Ps,d < 1 for any d < m).
/3 Tim
49

---

Regret analysis. Simple computations show that there average 2 f
replays of length
((d) during one block (7,,, T.m+1I. Thus, the regret due to replays at depth d over this block is of order (ignoring multiplicative numerical constants that does not depend (3)
R(d)2 22122
1m0 4:124(122
Summing over the depths d < m, we find that the total contribution the replays over a block m exactly of order 2m(1++0) (up numerical constants), i.e. of the same order as the minimax-optimal regret over this phase in the non-stationary setting.
Moreover, this choice of replay ensures that there are approximatively 2 21 replays at depth d
(1+2010m=+))
scheduled during block m, so that on average, a replay at depth is scheduled every 2
rounds. Noticing that 2 2 (1120)mm)d)))
that enough replays of the adequate length are scheduled so to ensure that a shift of magnitude dd8 does not go undetected for too long.
I 2 249
Since in each episode |4++1 41[ there are at most Mr = c |0gal((141 -4)c) where è is numerical
1+28
constant, the regret over one episode is upper bounded as
M
2 2m(
< (t1+1 - tx) 1428 x 1438
Applying exactly Proposition 6 and applying Hölder's inequality, we have exactly the upper bound of
E THDBBE T)] S H
1+a T'-29 LT 27
1--28
where Õ hides polylog factors and numerical constants that does not depend on or B. We next prove that this bound is in fact minimax minimax-optimal with respect to T, LT, and / simultaneously.
Lower Bound for non-stationary Hölder bandits. We adapt the proof of Theorem to this setting. Any policy interacting with (k, -HHHöe bandit environment suffers regret at least 11g x 1म92 in the stationary setting [Kleinberg. 2004]. We divide the horizon into T/T blocks of length т. In each, we define an amount of K T TTz x TÝZO (Hi, (3 mean reward functions satisfying Assumption with a single bump of size = /K/T = -- 112 KI hidden uniformly at random. Standard arguments show that any algorithm misidentifies the optimal region in some instance with constant probability, implying per-block regret
R( 2 TE
Concatenating T/T such blocks (with reward functions chosen independently) gives total regret of
(T/T) R(m,T) TT Tr 1+70
To derive lower bound that depends Lt, first set T/LT. This yields R(T,T) 2
TT418 L kT and we observe that we always have L1 2 Ly. For the dependency on Vy, we
118 2428
set
T KT
easy to verify that the total variation over exactly Vr. So for any algorithm म, there exist an environment such that
1+3 1428 + T'438 V, 1438
1428
R( 2 T 1428 L
K 1428
K 1133
We recover our results for x and 3=1 1. the smoothness the reward functions increases (3 + 1 and/or - 0), the problem becomes easier, the lower bound decreases.
50

---

H
Computational complexity of MDBE
While our algorithm is feasible on small-scale problems (as showed in our experiments in Appendix D), we acknowledge that its computational complexity may limit scalability in large-scale applications. Below, we provide a more precise characterization of the computational cost.
At each round within block of length 7,m++1 7,m = 8"", the algorithm maintains estimates for all bins across all discretization depths d = -......0 m. The total number of bins at depth d is 24, and across all depths, maintain total of
NumberBins,
Σ = 0(2"). d=1
For each bin, we compute an importance-weighted mean estimate, resulting in per-round cost of (22)) for estimation alone. In addition, at each round of this block, the algorithm performs statistical test (+) over all pairs of bins (B1, B2) at each depth d [1. There are (2) = O(44) such pairs per depth, and summing over all depths yields
Pairl
Σ = 0
per block. For each pair (B1, B2), must consider all possible intervals [s1, C [m,m; E) during the block. The number of such intervals is O(8") ) in the worst case.
Putting it all together, the worst-case time complexity for each round is
0(2 + O(4" 8TT) O(3")),
and the memory complexity is ((8m). Since the number of block is upper bounded as m < log (T). conclude that the worst-case time computational complexity of our algorithm is (TT)) and its worst-case memory complexity OT*), which are both polynomial in T.
While the computational cost per block is manageable for small values of m (e.g. m S 4), it becomes quickly intractable as m increases. Developing efficient adaptive algorithms that enjoy minimax optimal regret is therefore an important direction for future work, even in the K-armed setting.
I Numerical simulations
In this section, we illustrate some numerical experiments to show the empirical performances MDBE on synthetic dataset. The code for these implementations is available at https : : /ttittgitttb com/ Ba_ddttss...
Environment. We simulate a 1-Lipschitz, piecewise- piccewise-linear reward function defined over the action space (0, 1]. with a single peak shifting smoothly from 0.3 to x 0.7 every 10 rounds. This setup induces L = 10 significant shifts over a time horizon T = 10 Thus, the mean reward changes every round, but only ten of these changes significant under our framework.
Benchmarks. We compare our method against two baselines: BinningUCB (naive) and BinningUCB (oracle). The first baseline assumes knowledge only of the total time horizon T and naively discretizes the action space into (T) x T1/ss actions, as operating in a stationary environment of length T. then estimates. The oracle baseline, by contrast, has access to the exact times of the significant shifts 7, 's and resets its estimates at each significant phase, using the optimal per-phase discretization K; (T++1 1/3
a standard UCB algorithm without resetting its statistical
Results. We report Figure 4 the cumulative dynamic regret of the three methods, averaged over 100 independent runs. Our method (MDBE) significantly outperforms BinningUCB (naive) by adapting to non-stationarities through replay mechanisms.
51

---

Cumulative Dynamic Regret (Mean + 95% CI) T=100000, 10 shifts
25000
Binning+UCB (Naive)
Binning+UCA (Oracle)
Cumulative Dynamic Regret
20000
MBDE (our algo)
15000
10000
5000
20000
40000
60000
80000
100000
Time
Figure 4: Cumulative dynamic regret of MDBE, BinningUCB (naive), and BinningUCB (oracle) over total horizon of T 10 rounds with 10 significant shifts. Results averaged over 100 independent runs, with 95% confidence intervals the mean dynamic regret shown.
52


Reviews:
[{"review_id": "Jm5L2pH7OT", "reviewer": "Reviewer_VifP", "summary": "This paper considers a fundamental online learning problem of non-stationary Lipschitz bandits. In particular, the notion of non-stationarity is new, different from previously studied ones of $L_T$ and $V_T$, both of which could be very large even if the best arm is unchanged. This new notion is called significant shifts introduced recently in other bandit problems, and the authors then propose a Multi-Depth Bin Elimination algorithm to achieve optimal regret for Lipschitz bandits under significant shifts.", "questions": "- The difference of significant shifts is still quite abstract. Can the authors provide some more concrete examples to help understanding? And it is more ideal if such example has strong practical motivation/relevance.\n- Can the authors provide a more exact characterization of $c_0$ as mentioned in the footnote? How does it affect the algorithm performance?\n- Can the authors elaborate more on the unique challenges presented in the analysis of this problem, in particular, compared to previous work by Suk and coauthors?\n- Despite no numerical implementation, can the authors at least analyze the computation complexity? This would give a better sense of the feasibility of proposed approach.", "limitations": "- No numerical experiments as acknowledged by the authors that this is pure theoretical work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength\n- This paper tackles a theoretically fundamental problem in bandits with infinite continuum actions and new notion of non-stationarity. \n- The results are strong with optimal rates.\n\n### Weakness\n- The presentation of algorithm is not very clear: there are two algorithms for separate submodules but actually not an overall algorithm presented in block algorithm environment. \n- The explained intuition of proving Theorem also seems incomplete. It would be nice to have a more high-level proof framework connecting dots together before going into details. Some schematic illustration would also be very helpful. As in current presentation, it is hard to evaluate confidently the correctness of proof. \n- It appears that the main algorithm design is a combination of binning/elimination of seminal works and the replay mechanism of recent work  Suk and Kpotufe [2022] (the same authors who also proposed significant shifts). As a result, it is not very evident how much of the theoretical contribution is conditioning on these two.\n\n### Minor\n- A few typos such as [ and ] in line 127, line 182.", "was_revised": true, "final_justification": "I thank the authors’ response in their technical novelty and soundness and maintain my positive recommendation.", "rebuttal": "We thank the reviewer for the comment.\n\n### **Presentation**\nWe appreciate the feedback regarding the presentation and will improve it by including an illustrative figure of the sampling scheme *(Algorithm 2)* in the main text, using the space provided in the additional page if our paper is accepted.\n\n### **Concrete benefits of the significant shift metric (same answer as `9z8n`)**\nConsider a recommendation system with a continuous pool of content (e.g., movies), indexed by $x \\in [0,1]$, where nearby values of $x$ correspond to similar content types. Suppose there exists two regions of high and comparable user preference, centered around $x_1 = 0.3$ and $x_2 = 0.7$. Imagine a scenario where preferences near $x_1$ remain stable over time (*e.g*., a timeless classic), while preferences near $x_2$ undergo very frequent changes (*e.g*., a trending topic that evolves daily).\n\nIn this case, an algorithm that **consistently recommends content near $x_1$** would incur **little to no regret, even though the underlying reward function changes frequently** in other regions. From a global perspective, the *number of changes* or the *total variation in mean reward* could be **as large as $L_T = V_T= \\mathcal{O}(T)$**. An algorithm that relies solely on such metrics would unnecessarily restart its estimates too frequently, as it would **overestimate** the effective difficulty of the problem. This leads to both theoretical suboptimality and practical inefficiency. However, under our framework, such changes do **not** constitute a significant shift. This example shows a key strength of our metric: it captures only those changes that are **statistically consequential** to learning, rather than indiscriminately counting all shifts in the environment. \n\nWe will include this example at the end of *Section 2.2* to further clarify the motivation for our definition.\n\n### **Constant $c_0$**\nThe constant $c_0$ is given in our theoretical analysis *(see line 568, in the supplementary material)*: \n$$c_0 = 3 + 7(e - 1)\\sqrt{2} \\approx 20.$$\nThis constant is derived from the confidence bounds of *Proposition 2*, and ensures that the test procedure $\\textcolor{red}{(\\star)}$ used to trigger bin evictions is **theoretically valid**. However, this theoretically justified choice leads to conservative behavior in practice: bins are evicted only when the statistical evidence is strong. To balance theory with empirical performance, we use a smaller constant in our numerical experiments (see the numerical results paragraph in this rebuttal, where we specifically choose $c_0 = 1$), which leads to faster elimination and better regret in practice.\n\n### **Unique challenges in our analysis (same answer as `kQLa`)**\nThe main challenge in our setting lies in estimating a continuous, non-stationary mean reward function without prior knowledge of the magnitude of distributional shifts—or, equivalently, the discretization level and time scale at which such shifts become detectable. Coarse discretizations are essential to **rapidly** detect large shifts, while finer discretizations are required to capture smaller yet statistically significant changes. This motivates a **multi-scale** replay framework in which each scale contributes adaptively based on the magnitude of the underlying shift. \n\nTo address this challenge, we propose a hierarchical replay mechanism spanning multiple scales, where each scale corresponds to a different discretization of the action space $[0,1]$. In contrast, prior works that track significant shifts operate in the $K$-armed setting, where the action space remains **fixed and finite** even when contexts are continuous. Their replay mechanisms and regret analyses therefore rely on a fixed set of arms, without the need to estimate or track reward changes across multiple scales.\n\nOur algorithm must face three fundamental challenges: ***(i)* scheduling** (potentially simultaneous) replays at different depths, ***(ii)* leveraging the information collected across different scales**, and ***(iii)* tracking the regret contribution from all scales simultaneously**. In our regret analysis, each action $x_t \\in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for ***(a)* scheduling replays at specific scales** and ***(b)* selecting the appropriate bin at a given active depth** through a carefully designed sampling algorithm.\n\nWe will incorporate this discussion at the beginning of the proof sketch in *Section 5* to clarify the novelty and technical depth of our theoretical contribution.\n\n### **Numerical results (same answer as `kQLa`, `9z8n` and `GmBd`)**\n**We implemented our algorithm and evaluated its performance**. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.\n\nWe benchmark against two baselines: $\\texttt{BinningUCB (no restart)}$, which uses $K(T)\\propto T^{1/3}$ and never resets, and $\\texttt{BinningUCB (oracle)}$, which **knows** the true change points $\\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \\propto (\\tau_{i+1}-\\tau_i)^{1/3}$.\n\nWe simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).\n\n| **Step (×10³)** | $\\texttt{BUCB (no restart)}$ | $\\texttt{BUCB (oracle)}$ | **$\\texttt{MBDE}$ (ours)**    |\n|----------------:|-------------------------:|---------------------:|---------------------:|\n| 10              | 2137 ± 101               | 551 ± 30             | **1566 ± 108**        |\n| 50              | 10580 ± 393              | 2794 ± 147           | **8556 ± 349**        |\n| 100             | 21007 ± 890              | 5596 ± 396           | **17111 ± 667**       |\n\nOur method adapts to non-stationarity via replays, significantly outperforming $\\texttt{BUCB (no restart)}$.\n\n### **Computational complexity (same answer as `kQLa`, `9z8n` and `GmBd`)**\nOur algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.\n\nIn a block of length $\\tau_{l,m+1}-\\tau_{l,m}=8^m$, the algorithm maintains $\\sum_{d=1}^m 2^d = \\mathcal{O}(2^m)$ bins. Estimating bin means costs $\\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\\textcolor{red}{(\\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\\mathcal{O}(4^d)$ pairs, totaling $\\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \\subseteq [\\tau_{l,m}, t]$, leading to $\\mathcal{O}(8^m)$ possibilities. Therefore, the total *per-round* worst-case time complexity is $\\mathcal{O}(2^m + 4^m \\cdot 8^m) = \\mathcal{O}(32^m)$, and the *per-round* worst-case memory complexity is $\\mathcal{O}(8^m)$. \n\nSince $m \\leq \\log(T)$, we conclude that $\\texttt{MBDE}$ has an overall **worst-case time complexity $\\mathcal{O}(T^6)$** and **memory $\\mathcal{O}(T^4)$**: both **polynomial in $T$**. For small $m$ (e.g., $m \\leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings *(Gerogiannis et al., 2024)*. \n\nWe will add a paragraph discussing the computational complexity in the main text.\n\n### **References**\n- *Wei and Luo. \"Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.\" COLT 2021.*\n- *Suk and Kpotufe. \"Tracking most significant shifts in nonparametric contextual bandits.\" Neurips 2023.*\n- *Gerogiannis, Huang and Veeravalli. Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible? AISTATS 2025.*"}, {"review_id": "YlXQGuq9Gy", "reviewer": "Reviewer_scsD", "summary": "This paper studies a fundamental variant of the multi-armed bandit problem in which the mean reward function is Lipschitz in space $[0,1]$) and non-stationary in time. The paper considers the notion of significant changes — a refined measure of temporal non-stationarity that generalizes earlier notions like total variation or number of abrupt changes. The authors develop an algorithm that adaptively discretizes the arm space. They achieve a minimax optimal dynamic regret of $\\widetilde{L}^{1/3} T^{2/3}$ where $\\widetilde{L}$ is the number of significant shifts.", "questions": "Do the result hold in higher dimensions?", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Fundamental problem: The setting of spatially Lipschitz and temporally non-stationary bandits is both natural and under-explored. \n- Novel technical contributions: A discretization strategy based on dyadic trees to efficiently monitor changes across scales; elimination and replay mechanisms tailored to the continuous setting.\n- Theoretical guarantees: The $\\widetilde{L}^{1/3} T^{2/3}$ regret is minimax optimal (in T and $\\tilde L$, at least)\n\n**Weakness:** The results are stated only for Lipschitz constant L=1. The work would be more complete if they could incorporate L and compare the dependence with stationary Lipschitz bandits.\n\nminor comments:\n- The phrase \"locally stationary\" phases (line 52) is unclear. Please provide a more precise definition or intuition.\n- The “three-way” trade-off mentioned under forced exploration (Section 3.2) appears to be more of a two-way trade-off: frequency of restarts and discretization granularity. Please clarify the third dimension.", "was_revised": true, "final_justification": "I will maintain my initial evaluation.", "rebuttal": "We thank the reviewer for the feedback.\n\n### **Extension to other Lipschitz constants (same answer as  `kQLa` and `GmBd`)**\n**Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate**. For the sake of space, we give a sketch of proof of this generalization (similarly to *Appendix G* for the multi-dimensional setting). \n\nOur method generalizes to **$(\\kappa, \\beta)$-Hölder mean rewards** $(\\mu_t)_t$ satisfying:\n\n$$\\forall x,x'\\in[0,1],\\quad |\\mu_t(x)-\\mu_t(x')| \\leq \\kappa|x - x'|^\\beta.$$\n\nIn the stationary setting with horizon $\\tau$, the minimax regret is $\\tau^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}$, achieved by discretizing into $K_\\text{opt}(\\tau,\\kappa,\\beta) = \\tau^{\\frac{1}{1+2\\beta}}\\kappa^{\\frac{2}{1+2\\beta}}$ bins *(Kleinberg, 2004)*. This motivates **defining significant regret** over $[s_1,s_2]$ as:\n\n$$\\sum_{t=s_1}^{s_2} \\delta_t(x) \\geq \\log(T)(s_2 - s_1)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\n\nWe consider blocks of size $\\tau_{l,m+1}-\\tau_{l,m}=2^{m(1+2\\beta)}/\\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\\ell(d) = 2^{d(1+2\\beta)}/\\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\\kappa/2^{d\\beta}$. This motivates the new **eviction rule**:\n\n$$\\max_{B'}\\sum_{t=s_1}^{s_2} \\hat\\delta_t(B',B) > c_0\\log(T)\\sqrt{(s_2-s_1)2^d} + 4\\kappa(s_2 - s_1)/2^{d\\beta},$$\n\nwhere the $c_0\\approx 20$ is exactly the same as in the 1-Lipschitz setting. \n\nReplay at depth $d$ starting at round $s$ is scheduled with **probability**:\n\n$$p_{s,d} = \\frac{1}{\\kappa} \\cdot \\frac{2^{d(1+2\\beta)/2}}{\\sqrt{s - \\tau_{l,m}}} \\quad (d < m).$$\n\nEach block includes $2^{(1+2\\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\\beta)(m-d) + 2d(1+\\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\\mathcal{O}(2^{m(1+\\beta)})$, matching the optimal bound per block.\n\nThe expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\\kappa$ and $\\beta$) $2^{(1+2\\beta)(m+d)/2}$, while shifts of size $2^{-d\\beta}$ become detectable within $2^{m(1+\\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \\log_2((t_{l+1}-t_l)\\kappa)/(1+2\\beta)$ blocks, and the regret per episode is upper bounded as\n\n$$\\sum_{m=1}^{M_l} 2^{m(1+\\beta)} \\leq (t_{l+1}-t_l)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\n\nThus, the total dynamic regret of $\\texttt{MBDE}$ is upper bounded as:\n\n$$\\mathbb{E}[R_T] \\leq \\tilde{\\mathcal{O}}\\left(T^{\\frac{1+\\beta}{1+2\\beta}} \\tilde{L}_T^{\\frac{\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}} \\right).$$\n$ \\tilde{\\mathcal{O}}(\\cdot)$ only hides poly-logarithmic factors and numerical constant **that does not depend on $\\kappa$ or $\\beta$**.\n\nWith the exact same arguments as in our Lower bound proof  *(Appendix F)*, we show that **this rate is indeed minimax-optimal with respect to $T, \\tilde{L}_T, \\kappa$ and $\\beta$**.\n\n### **Locally stationary**\nBy locally stationary phases, we mean time intervals for which the reward function does not change. We thank the reviewer for pointing this flaw and we will clarify it in the final version.\n\n### **Three-way tradeoff (same answer as `kQLa`)**\nThe *three-way tradeoff* refers to the balance our algorithm must deal between: ***(i)* exploration**, via replays to detect changes; ***(ii)* exploitation**, by choosing bins with the highest estimated rewards; and ***(iii)* discretization level**, that is, choosing the appropriate discretization depth at each time step. This third dimension arises specifically from our setting of Lipschitz mean reward functions that change over time. We will clarify this in Section 1.1.\n\n### **Extension to multi-dimension**\n**Yes**, we showed how to adapt our algorithm and analysis in $p-$dimensional action space in **Appendix G**.\n\n### **References**\n- *Kleinberg. \"Nearly tight bounds for the continuum-armed bandit problem.\" NIPS 2004.*"}, {"review_id": "U0uFhyuqUz", "reviewer": "Reviewer_kQLa", "summary": "This paper studies the problem of non-stationary Lipschitz bandits, which generalizes both non-stationary bandits and Lipschitz bandits by allowing the reward function to evolve over time while satisfying a Lipschitz condition. The key contribution is MDBE (Multi-Depth Bin Elimination), a novel algorithm that adaptively adjusts the discretization level. The paper establishes the first optimal dynamic regret guarantees for non-stationary bandits with continuous action spaces under Lipschitz continuity.", "questions": "What is the potential for broader applicability to other non-stationary settings of the adaptive discretization strategy? For example, do non-stationary smooth bandits have similar challenges in discretization? If yes, would the strategy proposed in this work be applicable to that problem?\n\nYou clearly summarize how your algorithmic contributions relate to prior work. However, the novelty of the proof techniques is less explicitly highlighted. A brief discussion of what is technically new in the analysis would help clarify the theoretical contribution.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThis paper is very well-written, with a clear motivation for studying non-stationary Lipschitz bandits as a natural generalization of both non-stationary and Lipschitz bandits with potential real-world applications. The proposed algorithm, MDBE, is novel and thoughtfully designed to address the key challenges of adaptivity and continuous action spaces under unknown non-stationarity. The theoretical results are strong. Moreover, the paper does a good job positioning its contribution relative to prior work, especially in how it extends the notion of significant shifts and adapts replay-based elimination techniques to the continuous setting.\n\nWeaknesses:\n\nThe paper introduces a three-way trade-off in the introduction, but it's unclear what the three ways are.\n\nSome technical terms, such as “dyadic tree”, may be unfamiliar to a broader audience and could benefit from a more intuitive or visual explanation.\n\nNotations in some key places, such as d in Proposition 1 or δ in Definition 4, could be clarified within the theorem statement to improve readability.\n\nWhile the paper is theoretically focused, a small simulation or experiment could help validate the regret bounds and provide intuition about the algorithm’s behavior in practice.", "was_revised": true, "final_justification": "The authors have addressed most of my questions during rebuttal, including numerical results for validation, so I raised the score to a clear accept.", "rebuttal": "We thank the reviewer for the feedback.\n\n### **Three-way tradeoff (same answer as `scsD`)**\nThe *three-way tradeoff* refers to the balance our algorithm must deal between: ***(i)* exploration**, via replays to detect changes; ***(ii)* exploitation**, by choosing bins with the highest estimated rewards; and ***(iii)* discretization level**, that is, choosing the appropriate discretization depth at each time step. This third dimension arises specifically from our setting of Lipschitz mean reward functions that change over time. We will clarify this in Section 1.1.\n\n### **Presentation and readability**\nWe thank the reviewer for pointing the flaws in our presentation. We will add figures to enhance comprehension in the supplementary allowed page if our paper is accepted.\n\n### **Numerical results (same answer as `VifP`, `9z8n` and `GmBd`)**\n**We implemented our algorithm and evaluated its performance**. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.\n\nWe benchmark against two baselines: $\\texttt{BinningUCB (no restart)}$, which uses $K(T)\\propto T^{1/3}$ and never resets, and $\\texttt{BinningUCB (oracle)}$, which **knows** the true change points $\\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \\propto (\\tau_{i+1}-\\tau_i)^{1/3}$.\n\nWe simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).\n\n| **Step (×10³)** | $\\texttt{BUCB (no restart)}$ | $\\texttt{BUCB (oracle)}$ | **$\\texttt{MBDE}$ (ours)**    |\n|----------------:|-------------------------:|---------------------:|---------------------:|\n| 10              | 2137 ± 101               | 551 ± 30             | **1566 ± 108**        |\n| 50              | 10580 ± 393              | 2794 ± 147           | **8556 ± 349**        |\n| 100             | 21007 ± 890              | 5596 ± 396           | **17111 ± 667**       |\n\nOur method adapts to non-stationarity via replays, significantly outperforming $\\texttt{BUCB (no restart)}$.\n\n### **Computational complexity (same answer as `VifP`, `9z8n` and `GmBd`)**\nOur algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.\n\nIn a block of length $\\tau_{l,m+1}-\\tau_{l,m}=8^m$, the algorithm maintains $\\sum_{d=1}^m 2^d = \\mathcal{O}(2^m)$ bins. Estimating bin means costs $\\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\\textcolor{red}{(\\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\\mathcal{O}(4^d)$ pairs, totaling $\\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \\subseteq [\\tau_{l,m}, t]$, leading to $\\mathcal{O}(8^m)$ possibilities. Therefore, the total *per-round* worst-case time complexity is $\\mathcal{O}(2^m + 4^m \\cdot 8^m) = \\mathcal{O}(32^m)$, and the *per-round* worst-case memory complexity is $\\mathcal{O}(8^m)$. \n\nSince $m \\leq \\log(T)$, we conclude that $\\texttt{MBDE}$ has an overall **worst-case time complexity $\\mathcal{O}(T^6)$** and **memory $\\mathcal{O}(T^4)$**: both **polynomial in $T$**. For small $m$ (e.g., $m \\leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings *(Gerogiannis et al., 2024)*. \n\nWe will add a paragraph discussing the computational complexity in the main text.\n\n### **Extension to smooth bandits (same answer as `scsD` and `GmBd`)**\n**Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate**. For the sake of space, we give a sketch of proof of this generalization (similarly to *Appendix G* for the multi-dimensional setting). \n\nOur method generalizes to **$(\\kappa, \\beta)$-Hölder mean rewards** $(\\mu_t)_t$ satisfying:\n\n$$\\forall x,x'\\in[0,1],\\quad |\\mu_t(x)-\\mu_t(x')| \\leq \\kappa|x - x'|^\\beta.$$\n\nIn the stationary setting with horizon $\\tau$, the minimax regret is $\\tau^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}$, achieved by discretizing into $K_\\text{opt}(\\tau,\\kappa,\\beta) = \\tau^{\\frac{1}{1+2\\beta}}\\kappa^{\\frac{2}{1+2\\beta}}$ bins *(Kleinberg, 2004)*. This motivates **defining significant regret** over $[s_1,s_2]$ as:\n\n$$\\sum_{t=s_1}^{s_2} \\delta_t(x) \\geq \\log(T)(s_2 - s_1)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\n\nWe consider blocks of size $\\tau_{l,m+1}-\\tau_{l,m}=2^{m(1+2\\beta)}/\\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\\ell(d) = 2^{d(1+2\\beta)}/\\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\\kappa/2^{d\\beta}$. This motivates the new **eviction rule**:\n\n$$\\max_{B'}\\sum_{t=s_1}^{s_2} \\hat\\delta_t(B',B) > c_0\\log(T)\\sqrt{(s_2-s_1)2^d} + 4\\kappa(s_2 - s_1)/2^{d\\beta},$$\n\nwhere the $c_0\\approx 20$ is exactly the same as in the 1-Lipschitz setting. \n\nReplay at depth $d$ starting at round $s$ is scheduled with **probability**:\n\n$$p_{s,d} = \\frac{1}{\\kappa} \\cdot \\frac{2^{d(1+2\\beta)/2}}{\\sqrt{s - \\tau_{l,m}}} \\quad (d < m).$$\n\nEach block includes $2^{(1+2\\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\\beta)(m-d) + 2d(1+\\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\\mathcal{O}(2^{m(1+\\beta)})$, matching the optimal bound per block.\n\nThe expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\\kappa$ and $\\beta$) $2^{(1+2\\beta)(m+d)/2}$, while shifts of size $2^{-d\\beta}$ become detectable within $2^{m(1+\\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \\log_2((t_{l+1}-t_l)\\kappa)/(1+2\\beta)$ blocks, and the regret per episode is upper bounded as\n\n$$\\sum_{m=1}^{M_l} 2^{m(1+\\beta)} \\leq (t_{l+1}-t_l)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\n\nThus, the total dynamic regret of $\\texttt{MBDE}$ is upper bounded as:\n\n$$\\mathbb{E}[R_T] \\leq \\tilde{\\mathcal{O}}\\left(T^{\\frac{1+\\beta}{1+2\\beta}} \\tilde{L}_T^{\\frac{\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}} \\right).$$\n$ \\tilde{\\mathcal{O}}(\\cdot)$ only hides poly-logarithmic factors and numerical constant **that does not depend on $\\kappa$ or $\\beta$**.\n\nWith the exact same arguments as in our Lower bound proof  *(Appendix F)*, we show that **this rate is indeed minimax-optimal with respect to $T, \\tilde{L}_T, \\kappa$ and $\\beta$**.\n\n### **Technical novelty (same answer as `VifP`)**\nThe main challenge in our setting lies in estimating a continuous, non-stationary mean reward function without prior knowledge of the magnitude of distributional shifts—or, equivalently, the discretization level and time scale at which such shifts become detectable. Coarse discretizations are essential to **rapidly** detect large shifts, while finer discretizations are required to capture smaller yet statistically significant changes. This motivates a **multi-scale** replay framework in which each scale contributes adaptively based on the magnitude of the underlying shift. \n\nTo address this challenge, we propose a hierarchical replay mechanism spanning multiple scales, where each scale corresponds to a different discretization of the action space $[0,1]$. In contrast, prior works that track significant shifts operate in the $K$-armed setting, where the action space remains **fixed and finite** even when contexts are continuous. Their replay mechanisms and regret analyses therefore rely on a fixed set of arms, without the need to estimate or track reward changes across multiple scales.\n\nOur algorithm must face three fundamental challenges: ***(i)* scheduling** (potentially simultaneous) replays at different depths, ***(ii)* leveraging the information collected across different scales**, and ***(iii)* tracking the regret contribution from all scales simultaneously**. In our regret analysis, each action $x_t \\in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for ***(a)* scheduling replays at specific scales** and ***(b)* selecting the appropriate bin at a given active depth** through a carefully designed sampling algorithm.\n\nWe will incorporate this discussion at the beginning of the proof sketch in *Section 5* to clarify the novelty and technical depth of our theoretical contribution.\n\n### **References**\n- *Kleinberg. \"Nearly tight bounds for the continuum-armed bandit problem.\" NIPS 2004.*"}, {"review_id": "7HRY8Do563", "reviewer": "Reviewer_9z8n", "summary": "This manuscript introduces the first algorithm with optimal regret guarantees for continuum-armed bandits\nunder time-varying, Lipschitz-continuous reward functions. The key idea is to focus on significant shifts,\nwhich meaningfully affect regret. The proposed algorithm, Multi-Depth Bin Elimination (MDBE), adaptively\nexplores a dyadic partition of the action space and uses randomized replays to detect shifts and prune\nsuboptimal regions. Without knowing the number or location of changes, MDBE achieves minimax-optimal\nregret. However, there are several aspects that should be addressed. My main concern lies\nin the comparison with prior work and the justification for adopting the new metric. The detail comments\nare listed below.", "questions": "1. In the related work part, when the authors are comparing [Suk and Kim 2025], it is mentioned that\n[Suk and Kim 2025] assumes no regularity across arms thus it is not applicable to this manuscript.\nThis statement seems too vague for me. I suggest the authors make more efforts on elaborating the key\ndifference between this paper and prior works.\n2. The notation may always be confusing. The variable x in this manuscript is denoted as the arm/action.\nHowever, in the literature of bandit, x is denoted as the context and a is denoted as the arm/action.\nI would suggest the authors make some efforts to change it, though it will not take any effect on my\nscoring.\n3. In definition 2, it is confusing whether [s1, s2] ⊆ [τi−1, τi\n] depends with x or it exists for all x.\n4. In the same time, I would like to ask the authors to compare the difference in the definition of significant\nshit with [Suk and Kim 2025], which is not cited in Definition 2.\n5. In the meantime, I also find\n6. For the Section 2.2, though mathematically the comparison makes sense, I would also want to see a\nconcrete example to show using LeT metric is statistically and significantly more efficient. This would\nstrengthen the motivation for adopting LeT and also shows the bounds in Section 4 can be tighter than\nother metrics.\n7. In the proof of Proposition 3, the notation ft−1 should also indicate the condition xt ∈ B. Thus, ft−1,B\nis a better representation.", "limitations": "Adequate.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\t1.\tAddresses a previously unstudied intersection of settings:\nThe paper considers non-stationary bandits with a continuous (Lipschitz) action space, a combination that had not been analyzed in depth before. While both components—non-stationarity and Lipschitz structure—are individually well studied, their interaction introduces new technical challenges that are not addressed by existing work.\n\t2.\tTechnically non-trivial adaptation of known methods:\nAlthough one might imagine combining known ideas—such as time-scale decomposition (as in Wang or Besbes–Zeevi) with Kleinberg-style discretization—this paper shows that a naïve hybrid is insufficient. The core difficulty lies in adaptively detecting global, cumulative changes over a continuous space without knowing when or how these changes occur. The algorithm’s hierarchical, replay-based design and multi-scale gap estimation address this challenge in a subtle and well-justified way.\n\t3.\tTheoretical guarantees match minimax lower bounds:\nThe MDBE algorithm achieves a regret bound of \\widetilde{O}(\\tilde{L}_T^{1/3} T^{2/3}), matching the minimax lower bound up to logarithmic factors. Crucially, this is done without requiring prior knowledge of the number or locations of significant shifts. The framework is also robust to small or inconsequential fluctuations, making the bound potentially sharper than those based on classical variation metrics.\n\nWeaknesses\nSummary of the Paper: “Non-Stationary Lipschitz Bandits”\n\nThis paper investigates the problem of non-stationary bandits with a continuous action space and Lipschitz reward functions that can change arbitrarily over time. Unlike traditional non-stationary bandit approaches, which often assume a discrete action set and require prior knowledge of the non-stationarity level, this work addresses the more challenging setting of an infinite arm space under Lipschitz continuity without any such assumptions.\n\nThe authors propose a novel algorithm, MDBE (Multi-Depth Bin Elimination), which adaptively tracks a refined notion of non-stationarity called significant shifts—large aggregate changes in regret that are statistically meaningful. MDBE uses a hierarchical discretization of the action space and a replay mechanism to detect these significant shifts at different resolutions efficiently.\n\nThe main result is that MDBE achieves minimax-optimal dynamic regret of order \\widetilde{O}(\\tilde{L}^{1/3} T^{2/3}), where \\tilde{L} is the number of significant shifts and T is the time horizon. This regret bound matches known lower bounds and does not rely on any prior knowledge of the number or timing of shifts. The paper provides theoretical analysis, a detailed algorithmic design, and high-probability guarantees.\n\n⸻\n\nStrengths:\n\t1.\tNovelty and Scope:\nThe paper pioneers the study of non-stationary bandits in a continuous action setting under Lipschitz continuity—a previously unexplored combination—and introduces a theoretically grounded notion of significant shifts to this context.\n\t2.\tStrong Theoretical Guarantees:\nThe algorithm achieves minimax-optimal regret bounds without knowing the degree of non-stationarity in advance. This is a substantial theoretical contribution that strengthens the relevance of the proposed method.\n\t3.\tSophisticated Algorithm Design:\nMDBE incorporates a multi-resolution replay mechanism and hierarchical bin elimination, reflecting a careful treatment of exploration vs. exploitation in a non-stationary continuous setting. The sampling and bin eviction strategies are technically sound and rigorously justified.\n\n⸻\n\nWeaknesses:\n\t1.\tLack of Empirical Validation:\nThe paper is entirely theoretical and does not provide any simulations or experiments to demonstrate how the algorithm performs in practice. This limits its immediate impact for practitioners.\n\t2.\tComplexity of the Algorithm:\nMDBE’s design is intricate, involving nested partitions, probabilistic replays, and importance-weighted estimators. While theoretically elegant, the practicality and implementation complexity may hinder adoption.\n\t3.\tComputational Concerns Unaddressed:\nThe authors acknowledge that computational efficiency is not considered. Given the algorithm’s multi-scale structure, it is unclear whether MDBE is computationally feasible for large-scale or real-time applications.", "was_revised": true, "final_justification": "After reading the discussion and the rebuttal, I decided to update my score.", "rebuttal": "We thank the reviewer for the feedback.\n\n### **Numerical results (same answer as `VifP`, `kQLa` and `GmBd`)**\n**We implemented our algorithm and evaluated its performance**. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.\n\nWe benchmark against two baselines: $\\texttt{BinningUCB (no restart)}$, which uses $K(T)\\propto T^{1/3}$ and never resets, and $\\texttt{BinningUCB (oracle)}$, which **knows** the true change points $\\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \\propto (\\tau_{i+1}-\\tau_i)^{1/3}$.\n\nWe simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).\n\n| **Step (×10³)** | $\\texttt{BUCB (no restart)}$ | $\\texttt{BUCB (oracle)}$ | **$\\texttt{MBDE}$ (ours)**    |\n|----------------:|-------------------------:|---------------------:|---------------------:|\n| 10              | 2137 ± 101               | 551 ± 30             | **1566 ± 108**        |\n| 50              | 10580 ± 393              | 2794 ± 147           | **8556 ± 349**        |\n| 100             | 21007 ± 890              | 5596 ± 396           | **17111 ± 667**       |\n\nOur method adapts to non-stationarity via replays, significantly outperforming $\\texttt{BUCB (no restart)}$.\n\n### **Computational complexity (same answer as `VifP`, `kQLa` and `GmBd`)**\nOur algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.\n\nIn a block of length $\\tau_{l,m+1}-\\tau_{l,m}=8^m$, the algorithm maintains $\\sum_{d=1}^m 2^d = \\mathcal{O}(2^m)$ bins. Estimating bin means costs $\\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\\textcolor{red}{(\\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\\mathcal{O}(4^d)$ pairs, totaling $\\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \\subseteq [\\tau_{l,m}, t]$, leading to $\\mathcal{O}(8^m)$ possibilities. Therefore, the total *per-round* worst-case time complexity is $\\mathcal{O}(2^m + 4^m \\cdot 8^m) = \\mathcal{O}(32^m)$, and the *per-round* worst-case memory complexity is $\\mathcal{O}(8^m)$. \n\nSince $m \\leq \\log(T)$, we conclude that $\\texttt{MBDE}$ has an overall **worst-case time complexity $\\mathcal{O}(T^6)$** and **memory $\\mathcal{O}(T^4)$**: both **polynomial in $T$**. For small $m$ (e.g., $m \\leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings *(Gerogiannis et al., 2024)*. \n\nWe will add a paragraph discussing the computational complexity in the main text.\n\n\n### **Differences with *Suk and Kim (2025)***\n*Suk and Kim (2025)* study the non-stationary version of infinite-armed bandits with **reservoir distribution**: at each round $t$, the learner selects an action $a_t \\in [0,1]$ and observes a noisy reward $Y_t(a_t)$ with mean $\\mu_t(a_t)$, where $\\mu_t(a_t)$ itself is drawn from a time-varying distribution $\\nu_t(a_t)$. Crucially, this reservoir distribution $\\nu_t(a_t)$ evolves over time depending on the learner’s past actions. Their primary assumption concerns the proportion of arms with low expected rewards, but they do **not impose any smoothness or regularity** conditions on the reward function $\\mu_t(\\cdot)$. In other words, **similar actions do not necessarily yield similar expected rewards**, so there is no structure to exploit.\n\nThis lack of smoothness means that exploration strategies cannot benefit from generalizing across nearby arms, **and thus do not employ discretization of the action space**. Instead, their algorithms rely on *subsampling techniques* tailored to handle the complexity of the reservoir distributions. Due to these differences, their setting and methods relate more closely to *rotting bandits* literature, which deals with non-stationary rewards that evolve over time in ways **independent of spatial smoothness**. \n\nWe will make it clear in our related work subsection.\n\n### **Notations for actions**\nWhile we agree that in $K$-armed contextual bandit settings, it is standard to denote the context by $x$ and the action by $a$, this convention does not necessarily carry over to the Lipschitz bandits literature. In fact, denoting actions by $x$ is common in this litterature, *e.g.* in *Bubeck et al. (2011)* and *Kleinberg et al. (2019)*.\n\n### **Clarifications on the definition of significant shift**\n- The interval $[s_1, s_2[$ **depends** on $x$: each arm may incur significant regret over a different interval. A *significant shift* is said to occur when **all** arms have experienced such significant regret over their respective intervals. \n- This notion of significant regret is indeed derived from previous work by Suk and coauthors: across all settings (including ours), it refers to an interval over which the regret of an arm **exceeds the minimax rate for that setting**. In our case, this threshold is $\\tilde{O}(t^{1/3})$. Consequently, the definition of a significant shift remains consistent across all settings that adopt this significant shift framework.\n  \n### **Concrete benefit of the significant shift metric (same answer as `VifP`)**\nConsider a recommendation system with a continuous pool of content (e.g., movies), indexed by $x \\in [0,1]$, where nearby values of $x$ correspond to similar content types. Suppose there exists two regions of high and comparable user preference, centered around $x_1 = 0.3$ and $x_2 = 0.7$. Imagine a scenario where preferences near $x_1$ remain stable over time (*e.g*., a timeless classic), while preferences near $x_2$ undergo very frequent changes (*e.g*., a trending topic that evolves daily).\n\nIn this case, an algorithm that **consistently recommends content near $x_1$** would incur **little to no regret, even though the underlying reward function changes frequently** in other regions. From a global perspective, the *number of changes* or the *total variation in mean reward* could be **as large as $L_T = V_T= \\mathcal{O}(T)$**. An algorithm that relies solely on such metrics would unnecessarily restart its estimates too frequently, as it would **overestimate** the effective difficulty of the problem. This leads to both theoretical suboptimality and practical inefficiency. However, under our framework, such changes do **not** constitute a significant shift. This example shows a key strength of our metric: it captures only those changes that are **statistically consequential** to learning, rather than indiscriminately counting all shifts in the environment. \n\nWe will include this example at the end of *Section 2.2* to further clarify the motivation for our definition.\n\n\n### **Notation $f_{t-1, B}$**\nTrue, thank you for pointing this!\n\n### **References**\n- *Bubeck, Munos, Stoltz, and Szepesvári (2011). X-Armed Bandits. JMLR.*\n- *Kleinberg, Slivkins, and Upfal. Bandits and experts in metric spaces (2019). Journal of the ACM.*\n- *Suk and Kim. Tracking most significant shifts in infinite-armed bandits. ICML 2025.*"}, {"review_id": "9ggimMNgLI", "reviewer": "Reviewer_GmBd", "summary": "This paper studies non-stationary Lipschitz bandits and proves the first minimax optimal dynamic regret bounds in terms of a new non-stationary metric, \"significant shifts\", which follows a similar line of results in the non-stationary K-armed bandits.", "questions": "Questions/Suggestions:\n1. Why is there a log(T) factor in Definition 1? Is this because of concentration bounds or does it optimize the log dependence in the regret bound?\n2. In the pseudocode of Section B, why reset the master set at each block instead of carrying over information about eliminated regions from previous block to current block?\n3. Again, I believe a diagram or illustrative example would be helpful to explain the bin selection mechanism and replay scheduling.\n4. The dependence on the Lipschitz constant in the regret bound and other generalities such as Holder smooth bandits are missing, some discussion on these extensions would make the paper more thorough.\n5. What is the computational complexity of the algorithm and how does it compare to other algorithms for the non-stationary setting?\n\nTypos:\n1.  \"almost\" in Line 979\n2. Line 596: \"discretion\"", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The first minimax optimal regret bound for non-stationary Lipschitz bandits with both proven lower and upper bounds.\n2. New techniques involving multi-depth binning strategy for Lipschitz bandits.\n\nWeaknesses:\n1. Lack of experimental validation of the MDBE algorithm.\n2. I think Section 3 is quite heavy in notation and can be better served with a diagram/picture and example to illustrate the process of choosing a depth/arm.\n3. Much of the analysis seems structured similarly to the previous works on learning significant shifts. In particular, the work of Suk and Kpotufe [2023] also uses a multi-depth adaptive discretization idea to address the problem of learning the right discretization level, although it is for a finite-armed problem. The authors could better highlight what are the key differences or technical challenges addressed over the Lipschitz contextual bandit setting.", "was_revised": true, "final_justification": "Authors adequately addressed all my concerns.", "rebuttal": "We thank the reviewer for the careful analysis.\n\n### **Differences with *Suk and Kpotufe (2023)***\nWhile it is true that *Suk and Kpotufe (2023)* also operate in blocks and discretize the context space accordingly, their estimation strategy **does not involve multi-scale replays**. Once the context is discretized and observed, their analysis focuses on estimating the mean rewards of a **fixed and finite set** of $K$ actions, using replays of these same actions. Our algorithm must face three fundamental challenges: ***(i)* scheduling** (potentially simultaneous) replays at different depths, ***(ii)* leveraging the information collected across different scales**, and ***(iii)* tracking the regret contribution from all scales simultaneously**. In our regret analysis, each action $x_t \\in [0,1]$ belongs to several bins across discretization levels, and we explicitly quantify the regret incurred at each scale. Moreover, to decide which bin to activate at a given depth and time step, we introduce a principled strategy for ***(a)* scheduling replays at specific scales** and ***(b)* selecting the appropriate bin at a given active depth** through a carefully designed sampling algorithm.\n\nWe will incorporate this discussion at the beginning of the proof sketch in Section 5 to clarify the novelty and technical depth of our theoretical contribution.\n\n### **$\\log(T)$ in the definition of significant shift**\nWhile it is true that previous works do not include a logarithmic factor in the definition of a significant shift (*e.g.* *Suk and Kpotufe 2022)*, we observe that incorporating a $\\log(T)$ term has no impact on the regret analysis, while leading to a **strictly sharper metric**: the number of significant shifts can only decrease with the added log factor, making the metric sharper. \n\n### **On restarts at each block**\nRestarting estimates at the beginning of each block is primarily a **theoretical simplification** that facilitates a clean application of the doubling trick (see line 625 of our supplementary material). This strategy simplifies the regret decomposition and analysis, at the expense of only a constant numerical factor in the regret bound.\n\n### **Presentation**\nWe thank the reviewer for pointing out this presentation issue. If the paper is accepted, we will use the additional allowed page in the supplementary material to include visual illustrations of the dyadic tree structure in the main text to improve clarity.\n\n### **Extension to smooth bandits (same answer as `scsD` and `kQLa`)**\n**Our algorithm and analysis can easily be adapted beyond $1$-Lipschitz reward function, and still enjoy minimax optimal rate**. For the sake of space, we give a sketch of proof of this generalization (similarly to *Appendix G* for the multi-dimensional setting). \n\nOur method generalizes to **$(\\kappa, \\beta)$-Hölder mean rewards** $(\\mu_t)_t$ satisfying:\n\n$$\\forall x,x'\\in[0,1],\\quad |\\mu_t(x)-\\mu_t(x')| \\leq \\kappa|x - x'|^\\beta.$$\nIn the stationary setting with horizon $\\tau$, the minimax regret is $\\tau^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}$, achieved by discretizing into $K_\\text{opt}(\\tau,\\kappa,\\beta) = \\tau^{\\frac{1}{1+2\\beta}}\\kappa^{\\frac{2}{1+2\\beta}}$ bins *(Kleinberg, 2004)*. This motivates **defining significant regret** over $[s_1,s_2]$ as:\n\n$$\\sum_{t=s_1}^{s_2} \\delta_t(x) \\geq \\log(T)(s_2 - s_1)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\nWe consider blocks of size $\\tau_{l,m+1}-\\tau_{l,m}=2^{m(1+2\\beta)}/\\kappa^2$, yielding $2^m$ bins and expected regret of $2^{m(1+\\beta)}$ over this block if the rewards are stable enough. Replays at depth $d$ last $\\ell(d) = 2^{d(1+2\\beta)}/\\kappa^2$ and use $2^d$ bins. The bias for estimating the cumulative reward gap is $4(s_2 - s_1)\\kappa/2^{d\\beta}$. This motivates the new **eviction rule**:\n\n$$\\max_{B'}\\sum_{t=s_1}^{s_2} \\hat\\delta_t(B',B) > c_0\\log(T)\\sqrt{(s_2-s_1)2^d} + 4\\kappa(s_2 - s_1)/2^{d\\beta},$$\nwhere the $c_0\\approx 20$ is exactly the same as in the 1-Lipschitz setting. \n\nReplay at depth $d$ starting at round $s$ is scheduled with **probability**:\n\n$$p_{s,d} = \\frac{1}{\\kappa} \\cdot \\frac{2^{d(1+2\\beta)/2}}{\\sqrt{s - \\tau_{l,m}}} \\quad (d < m).$$\nEach block includes $2^{(1+2\\beta)(m-d)/2}$ replays at depth $d$, each incurring regret $2^{((1+2\\beta)(m-d) + 2d(1+\\beta))/2}$. Summing over all dephs $d < m$ gives total replay regret $\\mathcal{O}(2^{m(1+\\beta)})$, matching the optimal bound per block.\n\nThe expected replay interval at depth $d$ is (up to numerical constants that do not depend on $\\kappa$ and $\\beta$) $2^{(1+2\\beta)(m+d)/2}$, while shifts of size $2^{-d\\beta}$ become detectable within $2^{m(1+\\beta)}$ rounds. Each episode $t_{l+1}-t_l$ has at most $M_l = \\log_2((t_{l+1}-t_l)\\kappa)/(1+2\\beta)$ blocks, and the regret per episode is upper bounded as\n\n$$\\sum_{m=1}^{M_l} 2^{m(1+\\beta)} \\leq (t_{l+1}-t_l)^{\\frac{1+\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}}.$$\nThus, the total dynamic regret of $\\texttt{MBDE}$ is upper bounded as:\n\n$$\\mathbb{E}[R_T] \\leq \\tilde{\\mathcal{O}}\\left(T^{\\frac{1+\\beta}{1+2\\beta}} \\tilde{L}_T^{\\frac{\\beta}{1+2\\beta}} \\kappa^{\\frac{1}{1+2\\beta}} \\right).$$\n$ \\tilde{\\mathcal{O}}(\\cdot)$ only hides poly-logarithmic factors and numerical constant **that does not depend on $\\kappa$ or $\\beta$**.\n\nWith the exact same arguments as in our Lower bound proof  *(Appendix F)*, we show that **this rate is indeed minimax-optimal with respect to $T, \\tilde{L}_T, \\kappa$ and $\\beta$**.\n\n### **Numerical results (same answer as `VifP`, `kQLa` and `9z8n`)**\n**We implemented our algorithm and evaluated its performance**. Because of the NeurIPS policy, we cannot share code at this stage but will release it upon acceptance.\n\nWe benchmark against two baselines: $\\texttt{BinningUCB (no restart)}$, which uses $K(T)\\propto T^{1/3}$ and never resets, and $\\texttt{BinningUCB (oracle)}$, which **knows** the true change points $\\tau_i$ and resets its estimate at the end phase. At each phase, it uses the optimal per-phase discretization $K_i \\propto (\\tau_{i+1}-\\tau_i)^{1/3}$.\n\nWe simulate a $1$-Lipschitz, piecewise-linear reward on $[0,1]$ with a peak shifting from $x=0.3$ to $x=0.7$ every $10^5$ rounds over horizon $T=10^6$, inducing $\\tilde{L}_T = 10$ significant shifts. Regret is averaged over $100$ runs (rounded to nearest integer).\n\n| **Step (×10³)** | $\\texttt{BUCB (no restart)}$ | $\\texttt{BUCB (oracle)}$ | **$\\texttt{MBDE}$ (ours)**    |\n|----------------:|-------------------------:|---------------------:|---------------------:|\n| 10              | 2137 ± 101               | 551 ± 30             | **1566 ± 108**        |\n| 50              | 10580 ± 393              | 2794 ± 147           | **8556 ± 349**        |\n| 100             | 21007 ± 890              | 5596 ± 396           | **17111 ± 667**       |\n\nOur method adapts to non-stationarity via replays, significantly outperforming $\\texttt{BUCB (no restart)}$.\n\n### **Computational complexity (same answer as `VifP`, `kQLa` and `9z8n`)**\nOur algorithm is feasible for small-scale problems, as shown in experiments, but we acknowledge that its time and memory complexity limits its scalability. We detail the worst-case computational cost below.\n\nIn a block of length $\\tau_{l,m+1}-\\tau_{l,m}=8^m$, the algorithm maintains $\\sum_{d=1}^m 2^d = \\mathcal{O}(2^m)$ bins. Estimating bin means costs $\\mathcal{O}(2^m)$ per round. Additionally, it performs the statistical test $\\textcolor{red}{(\\star)}$ over all bin pair of bins $(B_1, B_2)$ at each depth $d$, with $\\mathcal{O}(4^d)$ pairs, totaling $\\mathcal{O}(4^m)$ across depths. For each pair, it checks all intervals of the form $[s_1, t] \\subseteq [\\tau_{l,m}, t]$, leading to $\\mathcal{O}(8^m)$ possibilities. Therefore, the total *per-round* worst-case time complexity is $\\mathcal{O}(2^m + 4^m \\cdot 8^m) = \\mathcal{O}(32^m)$, and the *per-round* worst-case memory complexity is $\\mathcal{O}(8^m)$. \n\nSince $m \\leq \\log(T)$, we conclude that $\\texttt{MBDE}$ has an overall **worst-case time complexity $\\mathcal{O}(T^6)$** and **memory $\\mathcal{O}(T^4)$**: both **polynomial in $T$**. For small $m$ (e.g., $m \\leq 5$), runtime is manageable for some problem instances. Designing adaptive, efficient algorithms with optimal regret remains an important open direction, even in $K$-armed settings *(Gerogiannis et al., 2024)*. \n\nWe will add a paragraph discussing the computational complexity in the main text.\n\n### **References**\n- *Kleinberg. \"Nearly tight bounds for the continuum-armed bandit problem.\" NIPS 2004.*\n- *Suk and Kpotufe. \"Tracking most significant shifts in nonparametric contextual bandits.\" Neurips 2023.*\n- *Gerogiannis, Huang and Veeravalli. Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible? AISTATS 2025.*"}]

Author rebuttal:

Meta-review: I concur with the reviewers’ positive view of the submission and think the paper makes a valuable addition. The work combines the well-studied problems of continuous-armed bandits and of non-stationary (finite-action) multi-armed bandits in a nice way to form a new problem and proposes an algorithm for the problem that achieves minimax optimal regret without knowledge of the non-stationarity. The technical contributions are solid and well situated in the literature. Some clarity and presentation issues were raised, as well as the lack of broader empirical validation, but the authors have addressed these in the rebuttal with clarifications and a small experiment. I trust these will be incorporated in the camera ready.
Decision: Accept (poster)