Non-stationary Bandit Convex Optimization: A Comprehensive Study
Authors: Xiaoqi Liu
Dorian Baudry
Julian Zimmert
Patrick Rebeschini
Arya Akhavan
Venue: NeurIPS 2025 poster ()
Keywords: Bandit Convex Optimization
non-stationary environments
online learning
dynamic regret
adaptive regret
zeroth-order optimization
Primary area: theory
TL;DR: We study Bandit Convex Optimization in non-stationary environments by establishing upper and lower regret bounds

Abstract: Bandit Convex Optimization is a fundamental class of sequential decision-making problems, where the learner selects actions from a continuous domain and observes a loss (but not its gradient) at only one point per round. We study this problem in non-stationary environments, and aim to minimize the regret under three standard measures of non-stationarity: the number of switches $S$ in the comparator sequence, the total variation $\Delta$ of the loss functions, and the path-length $P$ of the comparator sequence. We propose a polynomial-time algorithm, Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE), which adapts the sleeping experts framework from online convex optimization to the bandit setting. For strongly convex losses, we prove that TEWA-SE is minimax-optimal with respect to known $S$ and $\Delta$ by establishing matching upper and lower bounds. By equipping TEWA-SE with the Bandit-over-Bandit framework, we extend our analysis to environments with unknown non-stationarity measures. For general convex losses, we introduce a second algorithm, clipped Exploration by Optimization (cExO), based on exponential weights over a discretized action space. While not polynomial-time computable, this method achieves minimax-optimal regret with respect to known $S$ and $\Delta$, and improves on the best existing bounds with respect to $P$.

Non-stationary Bandit Convex Optimization: A Comprehensive Study
Xiaoqi Liu"
Dorian Baudry*t
Julian Zimmert Patrick Rebeschini"
Arya Akhavan
Abstract
Bandit Convex Optimization is a fundamental class of sequential decision-making problems, where the learner selects actions from a continuous domain and observes loss (but not its gradient) only one point per round. We study this problem in non-stationary environments, and aim to minimize the regret under three standard measures of non-ottttii nonn-tttionnaiiyy the number of switches S in the comparator sequence, the total variation of the loss functions, and the path-length of the comparator sequence. We propose polynomial-timee algorithm, Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE). which adapts the sleeping experts framework from online convex optimization to the bandit setting. For strongly vex losses, we prove that TEWA-SE minimax-optima with respect to known S and A by establishing matching upper and lower bounds. By equipping TEWA-SE with the Bandit-over-Bandi framework, we extend our analysis to enviromments with unknown non-stationarity measures. For general convex losses, we intro- duce second algorithm, clipped Exploration by Optimization (cExO), based on exponential weights over discretized action space. While not polynomial- computable, this method achieves minimax-opiin -optimal regret with respect to known S and A, and improves on the best existing bounds with respect P.
Introduction
Many real-world decision-making problems, such as resource allocation, experimental design, hy- perparameter tuning require repeatedly selecting an action from a continuous space under uncertainty and limited feedback. These settings are naturally modeled as Bandit Convex Optimization (see [1] for an introduction), which an adversary fixes a sequence beforehand, and learner sequentially interacts with the adversary for T rounds. At each round I, the learner selects an action 2, from a continuous arm set θ S Rd, assumed to convex and compact. The learner then incurs loss f( and observes noisy feedback:
loss functions f1, J2....... , JT
Rd +
y/s = (z(2,) + +
where & is a sub-Gaussian noise variable (Definition 1). The goal to minimize the learner's regret with respect to (w.r.t.) a performance benchmark. In the online learning literature [2, 3], the benchmark is typically the best static action in hindsight, with cumulative loss mingee Σ fz))
However, non-stationarity arises in many applications where different actions may work well during different time intervals. Hence, line of works [4-8] propose to compare the learner's actions against
Unnivrsitty of Oxford. Correspondence to: (shirlcy. 1iu, arya. akhavan @stats s..tttsoon ox. ac. uk. i Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France.
I GGoogle Research.
Éoole Polytechnique de Paris, IP Paris.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

sequence of comparators U1 U1...., O leading to a regret defined as
T
u1:) = Σ [f((z)) fe(u:))
where u1r denotes (u=)T=1- and the expectation is taken w.r.t. the randomness in the learner's 's actions zy 's and the randomness of the noise variables & similarly to the standard notion of pseudo-regret in the bandit literature, e.g., [9, Section 4.8]. Choosing the regret-maximizing comparator in (2)
gives rise to the notion of dynamic regret, defined as
(T)
= max R(T, u..T). u.rr E6
While addressing non-stationarity through dynamic regret has been extensively studied in multi- armed bandits (e.g.. [10-12]), it remains relatively undercxplored in continuum bandits [7, 13, 14]. This work aims bridge this gap by proposing algorithms for Bandit Convex Optimization that achieve sublinear dynamic regret. Such a rate is generally unattainable without imposing structural constraints on the environment, i.e., the comparator sequence and the loss function sequence [6]. For the comparator sequence, two commonly studied constraints are the number of switches [15] and the path-length [4], defined respectively as
T u u. P.P
(( ==
Σ (u, + 44-1) Ss, t=2
P(ULT) = Σ u1
(4)
For the loss function sequence, popular constraint is the total variation [7]. defined as
A(fir)= Σ max [f((2) f--1(2) <A. sEe
The constraints that the upper bounds S, P and A respectively impose the comparators the loss functions lead to different notions of regret. We call the regret for environments constrained by S the switching regret, which we define
ReWi (T.S)
R(T, u.:T)
(6)
WIT:S ( SSS
Similarly, we call the regret for environments constrained by P the path-length regret, denoted by Reath (T, P). We also use Rdyn (T, A) and Rayn (T, A, S) to denote the dynamic regret, where the arguments after 7 specify environment constraints. See (8) for rigorous definitions.
We detail in Section 1.3 conversion results between the different regret definitions that intro- duced: a sublinear switching regret (T, S) implies sublinear Royn(T, A), NTOm A, and Reath (T, P), as illustrated in Figure (see also [16, 17]). Furthermore, the upper bounds on the switching regret presented in this work are derived from upper bounds on the adaptive regrer [18, 19], which is defined using an interval length E [T] as follows,
pada (BTT)
E B[f((z) f((u)]
=
max max p.gE[T] WEE OC9-PSB
With an appropriate tuning of B depending on S. an adaptive regret sublinear in B implies a switching regret sublinear in T through simple reduction, e.g., discussions in [19]. We illustrate the relations between these regret notions in Figure
yoyy (pdynT, A), Royn (T. A, S)
Rada (B,
RSWi (T, S)
Reath (T, P)
Figure 1: Conversions between regrets: Rí Ri- R2 means that if regret R; is sublinear in I' (or B), then regret R2 is also sublinear in T, see Proposition I for precise mathematical statements.
We conclude this section by detailing the main notation and assumptions used throughout the paper.

---

Notation For k E N we denote by [k] the set of positive integers & k. We denote by || the Fuclidean norm, Bd {u E R ||||| I } the unit Fuclidean ball, and (x) = arg wee |/w x the Euclidean projection of to e. We use a V b = max(a, b) and A b = min a, b). If A, B depend on T. we use A = O(B) (resp. A = ((B) when there exists > S.t. A I eB (resp. 2) with independent of T', d, A and P. To hide polylogarithmic factors T, we use interchangeably A (BB) and A S (resp. A (B) and A 2 B), e.g..
5 T log T - A = ÖTT). Moreover, A = o(B) means A/B + 0 as T + 00.
Assumptions For simplicity, we assume that the time horizon T is known in advance: the case of unknown I can be handled using the standard doubling trick [20]. For some σ > 0, the noise variables (50)=1 are o-sub-Gaussian. For all E [T'] m [xx( - 1. We consider two cases: (i) general convex losses ft, where we assume Lipschitz continuity with constant K, and (ii) the special strongly- convex case, where we assume 3-smoothness. The domain O is assumed to contain a ball of radius r
for some constant > 0, and has a bounded diameter diam(E) (+) == -up( | - will x, w E ) S D
for some constant D > 0.
1.1 Main contributions
Existing works on non-stationary Bandit Convex Optimization study different aspects of the problem in isolation: [7, 14] focus on dynamic regret Royn (T, A), while [13, 21] address path-length regret Reath (T, P). The present work aims to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-ar art regret bounds w.r.t. all three non-stationn non-stationarity
measures S, A and P.
Our first contribution is a polynomial-time algorithm called Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE), which we design by adapting series of works from online convex optimization [22-24] to the bandit setting with zeroth-order feedback. It addresses the absence of gradient information by employing the randomized perturbation technique from [25, 26] estimate gradients, combined with the design of quadratic surrogate loss functions depending on a uniform upper bound on the norm of the gradient estimates.
Following [22-24], TEWA-SE runs multiple expert algorithms with different learning rates in parallel, and combines them using tilted exponentially weighted average. This allows TEWA-SE to adapt to the curvature of the loss function ft's without prior knowledge of parameters such as the strong-convexity parameter. For given interval length B, an appropriately tuned TEWA-SE simultaneously achieves an adaptive regret of the order vdB E for general convex losses and dvB for strongly-convex losses (Theorem 1). Consequently, for a known S, we prove that an optimal tuning of TEWA-SE yields switching regret upper bound of order v for general convex losses (Corollary 1). In the same result, we further prove that if the losses are strongly convex, and that A is known and incorporated in the tuning of TEWA-SE, the algorithm simultaneously satisfies a min (dvST, d A A } dynamic regret bound. Importantly, TEWA-SE does not need to know the actual strong-convexin parameter, inheriting the adaptivity properties of the framework developed in [22-24]. We prove that this dynamic regret upper bound is minimax-optimal in T, d, S and A by establishing a matching lower bound (Theorem 2). Finally, still for strongly-convex losses, we prove that TEWA-SE can also achieve a path-length regret of the order d p when P is known. We summarize these results in Table 1. To overcome the restriction of knowing S, A and P to optimally tune TEWA-SE, we also analyze a variant equipped with the Bandit-over: -oadii--vv--Baaddii framework [27].
Table I: Regret bounds we obtain for mesii (T,, S), (T A) and ppath (). respectively, for algorithms tuned with known S, A and P (polylogarithmic factors omitted). Straight underlines indicate minimax-optimal rates. A wavy underline indicates the result either new to the literature (strongly-convex case) or improves on the best-known PiT rate [13] (general convex case).
TEWA-SE (Algorithm 1)
cExO (Algorithm 3)
Convex v dAtTT, ptrt dVST, dAATT APPTT
/ dAtTi a ptri
Strongly convex
3

---

For general convex losses with known S, A and P. TEWA-SE achieves a suboptimal T rate (Corollary 1), matching the rates in similar analysis for the static regret [25, 26]. Thus, the second contribution of this work is the clipped Exploration by Optimization (cExO) algorithm with improved guarantees for this setting, which uses exponential weights on a discretized action space @ with clipping [28]. For given interval length B, this algorithm with an optimally tuned learning rate w.r.t. B attains order d /B adaptive regret (Theorem 3). When S, A and P are known beforehand, this algorithm with an optimally tuned learning rate achieves the minimax -otimaal dynamic regret w.r.t. 5 and A simultaneously, and attains a P* path-length regret (Corollary 2), improving on the previous best P [13]. While this algorithm is not polynomial-tine computable and has suboptimal rates w.r.t. the problem dimension d. it provides insights that may guide future research toward developing efficient algorithms with optimal guarantees for the convex case.
1.2 Related work
The literature on Bandit Conver Optimization (BCO) has traditionally focused on minimizing the static regret, see the recent monograph [1] for comprehensive historical overview. Both convex and strongly convex objective functions have attracted significant attention, beginning with the foundational work of [25] and further developed in subsequent studies such as [29-36]. Minimizing regret in non-stationary environments has only received attention more recently [7, 13, 14, 21), see also [1, Section 2.4] for overview for this topic. Among these works, [7, 14] study R A), whereas [13, 21] focus RPath (T, P). As we explained above (and formalize in Section 1.3), the switching regret Rew (T.) S) can induce guarantees on both (T, A) and poath (T, P), but the reverse does not necessarily hold, Therefore, the results in these works cannot be readily extended to provide regret guarantees w.r.t. all three measures S, A and P.
Minimizing regret in environments with non-stationarity measures such as S, A and P have been addressed with greater depth in Online Convex Optimization (OCO), where the learner has direct access to gradient information and can query the gradient or function value at multiple points of the loss function per round. The
algorithm with optimal adaptive regret guarantees MetaGrad with sleeping experts [24], which queries only one gradient per round, and adapts to curvature information of the loss function such as strong--onvexitg when available. Our polynomial- time algorithm TEWA-SE builds upon [24] and its precursors [22, 23), adapting this approach to BCO by replacing the exact gradient per round with an approximate gradient estimate, and by designing quadratic surrogate loss. The approach in [24] follows a long line of successive developments in OCO from expert tracking methods [15, 20, 37-41] to the study of adaptive regret [18, 19, 42-46], with recent advances [24, 47-50] reducing the query complexity from Olog T') to (1)) per round, while achieving optimal adaptive regret dynamic regret. The adaptivity of [24] directly inherits from MetaGrad [22] and its extension [23], which themselves build on earlier adaptive methods [51, 52].
For general convex functions, the approach of substituting one me-point gradient estimate for the exact gradient in each round of an OCO algorithm often yields suboptimal T rates, both in static regret [25, 26] and dynamic regret [13, 21]; see also our Corollary 1. A series of breakthroughs [28, 32, 53-56] indicate that /T rates (up to logarithms) are attainable for static regret, at the cost of a higher dependency on d. Our cεxO algorithm follows this line of work, using exponential weights on a discretized action space [28]. By playing inside a clipped domain, we transform the algorithm from one with /T static regret into one with /B adaptive regret (modulo logarithms) for intervals of length B, which in turn leads to regret guarantees w.r.t. S,A and P.
Finally, we mention that non- stationnann has been widely studied in the Multi-Armed Bandit (MAB) literature. A substantial body of work has focused on adapting standard policies-sut as UCB [57, 58], EXP3 [59], and Thompson Sampling [60-62]-to perform effectively under non-stationarity. These adaptations often employ mechanisms to discard outdated information, either actively (e.g.. change-detection methods [12, 63-67)) or passively (e-g., discounted rewards [10, 68], sliding windows [69, 70], or scheduled restarts [1]],, but are not straightforward to adapt to BCO.

---

1.3 Conversions between different regret definitions
We present the key conversions between different regret notions, illustrated in Figure I above. Using the definition of (T))
(T)) in (3), we overload notation slightly to define
Rdyn (T, A)
sup (frr(()))
E
f((z))
min f(() ZEG
(8)
and (T A, S) additionally constrains 1 + Σt= =
1(2 + =;-1) S S
where 2 == arg mingee (z) for all t [T]. In Proposition 1, we show how the adaptive regret Rada (B. can be used to bound the switching regret R (T, S), which in turn can be used bound the dynamic regret Rdyn (T, A, S) and path-lengd regret Reath P). Consequently, Rada T) and (T, S) are the primary objects to analyze.
Proposition Suppose that an algorithm can be calibrated to satisfy (B, T) S CB", for any interval length B E [T], for some factor C >> 0 that is at most polynomial in d and log(T"), and [0. 1).
Then, for any S, Sp E [T], an appropriate choice of B yields the following regret guarantees:
Switching:
B
guarantees that R (T,S) 2 CS TT
Dynamic:
B
S
Sa
T'
yields Rdyn (T, A, S RSa (T, R (T, SA)
+
I Sa
1)+
Path-length:
ensures that Reath (T, P) S naKi (TSpp) + 3F
Sp
The proof is provided in Appendix B. We note that the reduction from Reath (T, P) to RTW S) in Proposition new and employs simple geometric arguments (see Lemma 2 in Appendix B). This reduction simplifies the analysis of [T P). though it can yield slightly looser bounds on peath((T P) than a direct analysis, as discussed in [17].
2 The TEWA-SE algorithm
In this section, we develop a polynomial-time algorithm called Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE Algorithm 1), building on the two-layer structure of previous experts- based algorithms [18, 19, 43]. Each expert in TEWA-SE is uniquely defined by its lifetime and learning rate. We denote the active experts at time by E,, E.,..., En.. where E, operates over interval I with learning rate 7/:- In each round I, the active experts each propose an action, denoted 2) " and a meta-algorithm aggregates them into a single meta-action æ, by computing their tilted by
exponentially weighted average [22, 24), see line 7 in the pseudo-code. Then the algorithm receives noisy evaluation of fi at æ; and constructs approximate gradient estimate 9, Rd of at æ;- Both x; and 9, are shared with all experts, who update their actions via online gradient descent on their surrogate loss functions defined using æ; and 9.-
TEWA-SE employs the Geometric Covering scheme from [19, 24] to schedule experts across different time intervals, and the exponential grid from [22, 24] to assign varied learning rates to the experts. These deterministic schemes ensure that only a logarithmic number of experts are active per round, maintaining computational efficiency. Intuitively, the meta-algorithm achieves low adaptive regret on the original loss function because, for each subinterval of times, there cxists at least one individual expert with low static regret their surrogate loss functions this subinterval. This is guaranteed by the careful design the exponential grid of learning rates. While full details of TEWA-SE is deferred to Appendix C. we highlight below the distinctions between this paper and prior works.
Construction of one-point gradient estimate For fixed parameter h E (0,r), we define the clipped domain é {u θ u + hBd C O), where h < ensures θ 7 0. In each round t, we select meta-action æ, E Ô and query the function at perturbed point + hG,, receiving noisy feedback yt = [a( + h(,) ) + É., where Ç E Rd sampled uniformly from the unit sphere a This allows us to construct the gradient estimate g, (d/h)ytS,- As implied by [25, Lemma 1]. the
5

---

Algorithm Tilted Exponentially Weighted Average with Sleeping Experts (TEWA-SE)
Input: d, T, B, h min (YB--in1 θ {u E θ hhB" C O). G as in (10), expert algorithm E(I, r) defined in Algorithm 2, and (NT) and (4, m)kem.)) Vt E [T]
1: for 1 1. do
2:
for F, = E,, m1) E (EE, Ez,..., En, do Receive action Li, from expert E;
ny experts active at
3:
4: if min [.) = then initialize 1 1-1.1 O, clipped domain θ and parameter
5: end if
6:
end for
7:
Set meta-action as at Σm= t/s expeepp 1,,,, Σ3= "h
8:
Sample S, uniformly from OB
9:
Query point 2, = 2G + hi, to obtain y1 = f((z))+ + Construct gradient estimate 9. (d/h)giS:
10:
11:
for i 1, ,,,,....7 Ti do
12:
Send meta-action x, and 9, E; Increment cumulative loss 1,,1; = L 1.1 + P7 (x D (((()) depends on ot and 9e
13:
14:
end for
15:
end for
vector 9, is unbiased gradient estimate of a spherically smoothed version of f. æ,, satisfying
Eig, f((r)) where f((z) E [f(( h2) V E θ
with Ç distributed uniformly on the unit ball B Importantly, fc inherits the convexity properties of
St [71, Lemmas A.2-A.33. Our approach differs from related works OCO [22-24, 47, 48) that use exact gradients in two key ways: i) in each round, we query the perturbed point at + lic, rather than it,, accumulating regret the perturbed point, and ii) we constrain æ, inside the clipped domain Ô to ensure all perturbed 2, remain feasible.
In our setting, under the high probability event AT {1Erl S 20 /log(T + 1), Vt [T], we have
|| (d/h))fi(z,, + h(,)) + &ll S (d/h) 20 VlogoT + +)) =. Vt E [T].
(10)
This implies a fundamental tradeoff selecting the smoothing (and clipping) parameter h: larger values reduce G (and the variance g.), but increase both the approximation error between fi and ft and the error due to clipping, while smaller values reduce bias at the cost of higher variance in gr. Theorem I and Corollary we establish the optimal and the resulting regret guarantees.
Algorithm 2 Expert algorithm EII, q): projected online gradient descent (OGD)
Input: / = =Ir, s). n, G. clipped domain é, and surrogate loss (?(-) defined in (1)) E N+ Initialize: =,,,, any point in é
1: for t= 1,...,5 do
2: Send action =²,1 to Algorithm
3: Receive meta-action a, and 9, from Algorithm
4: Update ="+1, 11 (œ M4 V where μt
(t-++t+l
5: end for
Design of expert algorithms and surrogate losses We choose projected online gradient descent (OGD) as the expert algorithms (Algorithm 2), i.e., each expert E(I, runs OGD during its lifetime I. In the full- mall-informatin setting, where experts observe ft and gradients are evaluated at all of their actions, each expert could simply run OGD on the true loss functions. In contrast, for the bandit setting, with only one gradient estimate g, of the smoothed loss fe per round, we need to construct surrogate losses for the experts. The simplest option is the linear surrogate loss (x(x) -g." (æx, x). but this fails to leverage curvature information and leads to a large O( (VVlT) static regret for each expert, ultimately yiclding linear adaptive regret.

---

To address these limitations, inspired by [22-24], we design the following grongly-convve surrogate loss Ey RR R:
( (a, - xx)) +) Gf
- x11², Vx E R"
(11)
where G is the upper bound (10) on ||gell, and is the learning rate of the expert. We highlight that our choice of the quadratic term in (11) differs from the 7 | |2
x æ=I² and (g. (x, x))²
in [24] and [22]. The latter necessitates an additional condition relating Ellggell and Eilgg, 11 (or
Elg.g, D to be satisfied in the analysis, see e.g., [22, Theorem 2], and may yield suboptimal rates in dimension d for strongly-come
losses, similar to [22]. Our choice of the quadratic term, similar to [23], eliminates these limitations and simplifies the proof.
For comparator (11) implies that the linearized regret associated with fe interval I can be bounded as:
Σ KET
[lg Ct - u) S 5 E (())
l7 (u) Lt, Ar] +n 2
Σ EE1
| uIl². (12)
Due to the strong-convexity of EZ, each expert attains only an Olog [[] static regret under OGD with an optimally tuned step size He (see line 4 of Algorithm 2, and Lemma in Appendix C.4). This ensures term A above is also of (log []). By the convexity of fe we have
Σ [()(())) - Pe(w)) Ar] S LA+ (//² NET
ar u/l? [ Σ TET
(13)
where a = for general convex fe (and fi), and a > 0 for strongly-convex. Since both a and deterministic exponential grid of r values [19, 24), ensuring at least one expert covering I effectively minimize the RHS of (13), ultimately yielding a sublinear adaptive regret w.r.t. fe. We present this result in the following theorem.
Eier ||=; 2 are unknown priori,
Theorem 1. For any T E I++ and B E [T], Algorithm I with h = min( (BlllVdBBBB) d satisfies
Rada (B, T) S vdB +
(14)
and if fe is a-strongly-comver with arg min f((x)) E for all t E [T], furtheroree holds that
Rada (B, T)
BB 1d
(15)
where S conceals polylogarithmic terms in B and T, independent of d and a.
The proof of Theorem 1 can be found in Appendix C.2. We emphasize that TEWA-SE does not require knowledge of the strong-convexity parameter a. This parameter is only used in the analysis and appear in the upper bound (15). Compared to the O log T' and O log T log B) adaptive regrets in [24] for general convex and strongly-conver, losses respectively, our bounds Theorem reflect the separation between online first-order and zeroth-ord order optimization. This mirrors the established gap in static regret analyses, see e.g. [74] vs. [72]. We further note that our bound for the strongly-convex case has a dependency, which is suboptimal compared to the dependency in [33, 73] for static regret in BCO for a S 1.
Applying Proposition 1, the adaptive regret bounds in Theorem lead to the following bounds for Rewi (T, S), (T. A, S) and Roathh (T, P). In Corollary 1, for clarity we drop the [-] operators from the expressions for and assume without loss of generality B is an integer (proof in Appendix C.5).
Corollary 1. Consider any horizon T N+ and assume that, for all t E [T], the loss ft is convex, or strongly-convex with arg min ft f((x) E O. We refer to the second scenario as the strongly-conve (SC) case. Then, Algorithm I tuned with parameter B satisfies the following regret guarantees:
'The assumption that loss minimizers lie inside θ is common in zeroth order optimization. see e.g., 17, 72, 73J. Without upper bound analysis would have extra term depending the gradients the minimizers.
7

---

Vastr² +dS ST + +d' (SC)
Switching.
B = T -
-n (T,))
B T
YUT $ Ro S) S R (T, (
Dynamic.
5
T
7 R (T, A. 5) & RTT (T. S) (d A dtiitt (SC)
3
B
[VdT
P + Rpath (T. (T. S &r +r
Path-length.
B
rdf = P
7 Reah (T, S r +r (SC).
2.1 Lower bound for strongly-conver loss functions
In this section, we derive a minimax lower bound on the dynamic regret and path-length regret, and discuss the optimality of TEWA-SE. To derive the lower bound for the dynamic regret, we adopt a standard minimax approach by constructing a class of hard functions, following [71, Theorem 6.1 We assume that the adversary either (i) partitions the time horizon into S segments and assigns a different function from this class to each segment, or (ii) selects a sequence of functions with total variation bounded by A.
Theorem 2. Let Q Bd. For a O denote by Fa the class of a-strongly convex and smooth functions. Let π {z(]T=1 be any randomized algorithm (see Appendix D for definition). Then there exists To > 0 such that for all T 2 To holds that
R (T,A,S) A
sup FTF.
(16)
where 0j > 0 is constant independent of d, T, S &nnd A.
We detail the proof in Appendix D. This lower bound establishes that TEWA-SE achieves the miiimmax-optimll dynamic regret (up to logarithms) for strongly convex and smooth functions w.r.t. T. S and A. We note that [7] derives lower bound only in terms of T and A, matching (16), but it does not explicitly capture the dependence on nor does address the interplay between S and A, In the special case where S 1, Theorem 2 recovers the classical minimax static regret of order d'T [71, 72]. Interestingly. for d = 1 the scaling of the lower bound as function of T, S and A is the same as standard lower bounds the non-stationary MAB literature [10, 11]. The proof of Theorem can be readily adapted to consider only the measure with the switching regret, yielding a rate of dVST and thereby establishing the minimax optimality of TEWA-SE's switching regret bound.
We also derive a lower bound for path-length regret analogously that for dynamic regret. In Theorem 4 in Appendix D we show that under the same assumptions as in the statement of Theorem 2,
sup
Roath (T,P) 2 e2 Pd
(17)
ET..
where C2 > 0 is a constant independent of d, T and P. Hence, TEWA-SE may not achieve the optimal regret rate for path-length. Additionally, Eq. (17) improves upon the only existing /PT lower bound from [13] terms of the horizon T, by leveraging a different construction of a hard instance. This improvement comes from assuming P o(T),, which is necessary for sublinear regret.
2.2 Parameter-free guarantees
In Corollary 1, we showed that the knowledge of the non-stationarity measures S, A and P allows optimal tuning of TEWA-SE's parameter B. However, these measures can be hard to estimate. To obtain guarantees without such knowledge, we further analyze TEWA-SE under the Bandit-over- Bandit (BoB) framework from [27] (see Appendix C.6 for details), which divides the time horizon into epochs of suitable length L and uses an adversarial bandit algorithm (e.g., EXP3) to select B for TEWA-SE in each epoch from the set B (2
0, 1,..., [log T]}. In Corollary 3 in Appendix C.6, we adapt all the upper bounds in Corollary 1 to this framework, and show that this procedure costs an additional d+ term for the general convex case and d T for the strongly- convex case. Our parameter-fiee free path-length regret bound T + T for the general convex case improves on the p pirz bound in [13] when P ((T
8

---

Recent works on MAB [65-67, 75, 76] have proposed algorithms that achieve optimal dynamic regret without prior knowledge of S and A. However, they use procedures that crucially rely on the finiteness of the arm set, and are thus ill-suited for BCO. It remains open to determine if the minimax regret rate can be attained without such knowledge in the settings considered in this paper.
3 Clipped Exploration by Optimization
In this section, we propose second algorithm (Algorithm 3) to improve upon the suboptimal rates for R (T, A, 9) and Aeatt (T: P) that TEWA-SE achieves for general convex loss functions. For ease of presentation, we assume in this section that the problem is noiseless, i.c., & = 0 for E [Z]. We call this algorithm clipped Exploration by Optimization (cExO), which is built on Algorithm 8.3 (ExO) in [1]. The high level idea of ExO is to run exponential weights over finite discretization of the feasible set, denoted by C C O. We assume the discretization C admits a worst-case error of è Fe. mill fz')) mingge ((z), where Fo denotes the class of convex and Lipschitz functions, and (C)) denotes the (IC) 1)-dimensional simplex.
With 9o initialized as the uniform distribution, in each round t, given a loss estimate &. E RICI, ExO (in its mirror descent formulation) computes q, arg min ge (q, (,-) + " (9L(919,-11) where divergence (L((l)p) _ qi log(g:/p:) for q.p AC). The update
KL the Kullback- rule in cExO departs from the vanilla ExO in this single step, by taking the minimum over the clipped simplex = ACC n [?, 1]|s where 7 E (0, (ट is constant to be tuned, see line 2 of Algorithm 3. Clipping is a standard technique in mirror descent ensure the algorithm does not commit too hard to any single action, and therefore detect changes in the environments more easily, yielding regret guarantees w.r.t. non-stationary measures [9, Chapter 31.1].
Given the reference distribution q.- cExO selects a playing distribution p, E ACC and an estimator function E, E & which returns an updated loss estimate for each action in C, where & denotes the set of functions that map C x [-1,1] 1] to R!Cl, It does so by solving an intractable optimization problem:
arg min REE
(18)
where, with (n²)) = maX)/EA(C) (q q'm -KL(q'l the objective function is defined by
(g P. F)= = sup sup Ez-p (p - p) (p" q. ((2))()))) + (,,((F((,, p' P'EA(C) SEF
This optimization problem is intractable due to the large size of & and Fo.3 The role of this optimization problem is tradcoff the worst-case cost of deviating from the desired distribution qe versus the gain of improved exploration (hence the name Exploration by Optimization). Finally, cExO samples an action 2, according to Pt. observes the feedback f(z)) and constructs loss estimate s; E, fz..)) to be used in the subsequent round. cExO achieves the adaptive regret guarantee stated in Theorem below.
Theorem 3. For T E N+ and B E [T], Algorithm 3 calibrated with = //)/((-))/(d" log(dT)B) and log |C| = Odd (odloo(dTT) () satisfies
1 T r = T.P.
1
=
(B, S dåvB.
(19)
We then use Proposition to convert the bound of Theorem 3 into the following regret guarantees omit [-] from the expressions for B for clarity.
w.r.t. S, A and P. Like in Corollary Corollary 2. For any horizon T E N+, Algorithm 3 calibrated as in Theorem 3 and tuned with interval size B (which determines 11) satisfies the following regret guarantees:
Switching:
B
T + Rsw ( (T,S) & d VST.
g
Dynamic:
B T v (JåT/A) = Rem (T, A, S) S R S (T,S) A
Path-length:
B (rd 2 T/P) = Reath (T, -- p373
FFor detailed discussions about these functions, we refer the reader to [28].
'One can in theory bound the domain of & and discretize E, Fo and (CC). The optimization problem is hence computable, though not in polynomial time.

---

Algorithm 3 clipped Exploration by Optimization (cExO)
Input: d, T,B, feasible set +, finite covering set C C θ of O discretization error E, learning rate f clipping parameter y (0, [2] ), and Á (CC) n Iy, 1]
Initialize: 40 c Vi E [|c]].
1: for t .,..., ,,...,T7 do
2: Compute 9, arg min qea (q, 3,1)) [KL((l19:-1)
min
3: Find distribution P, E (CC) and P. E s.t. Ay(q;, Pr. F4) S infpesi)) Ag(gr: F.) + nn EEE
4: Sample 2, ~ P, and observe (1(2))
5: Compute 8, Ex(2,, fz(z)))
6:
end for
The proofs of Theorem 3 and Corollary 2 are presented in Appendix E. By comparing these results to the lower bounds in Section 2.1, obtain that for known S, A and P. cExO achieves minimax- optimal rates in T, S and A, but remains suboptimal in (for all measures), and potentially for the path-length bound (see Eq. (17)). This suboptimal dependence on d is unsurprising since even the best known static regret bounds of [31] and [34] suffer from similar dimensional dependence. Moreover, the gap between cExO's path-length regret bound and minimax lower bound of order d P may stem from either (i) looseness in the lower bound, or (ii) sub-optimality of cExO, which runs OMD in distribution space rather than directly on the action set. The latter may allow us bound path-lenghe regret more directly and sharply.
To adapt to unknown non- non-stationarity measures, cExO equipped with the BoB framework yields the upper bounds in Corollary 2 with an additional dă term (see Corollary Appendix E). Our path-length regret of p 73 and P + T for known and unknown P, respectively, improves on the P and påra rates in [13] in terms of T'
4 Conclusion
In this work, we develop and analyze two approaches for non-stationary Bandit Convex Optimization. For strongly convex losses, our polynomial-time TEWA-SE algorithm achieves minimax-optimal dynamic regret w.r.t. and without knowing the strong-convexity parameter, but incurs sub- optimal T rate for general convex losses. To address this, we propose a second algorithm, cExO, which achieves timimax--pptmmllin computable and has an increased dimension dependence. Our matching lower bounds confirm the op- timality results, but also reveal potentially suboptimal guarantees highlights& a central open challenge: designing algorithms that are simultaneously minimax-optimal and computationally efficient for general convex losses in non-stationary environments. A promising stepstone towards this goal is to incorporate second-order information, akin to the online Newton methods from [31, 34] that achieve state-of-the-art static regret guarantees for adversarial convex bandits. In particular, a restart criterion, similar to the one in line 15 of [35, Algorithm I] or line 11 of [31, Algorithm I], may enable tracking capabilities and lead improved regret bounds.
for S and A. However, this algorithm is not polynomial-time time
the path-length P. This work
Acknowledgments and Disclosure of Funding
X. Liu, D. Baudry, P. Rebeschini and A. Akhavan were funded by UK Research and Innovation (UKRI) under the UK government's Horizon Europe funding guarantee [grant number EP/Y038333/1).
References
[1] Tor Lattimore. Bandit convex optimisation. arXiv:2402.06533 2024.
[2] Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
[3] Francesco Orabona. A modern introduction to online learning. 1eXi::1912.13213: 2019.
10

---

[4] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In International Conference on Machine Learning, pages 928-936, 2003.
[5] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online opti- mization in dynamic environments: Improved regret for strongly convex problems. In Conference on Decision and Control, pages 7195-7201. IEEE. 2016.
[6] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406. PMLR, 2015.
[7] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions Research, (3(55:1227-1244 2015.
[8] Eric C Hall and Rebecca M Willett. Online convex optimization in dynamic environments. IEEE Journal of Selected Topics in Signal Processing, 9(4):447-662, 2015.
[9] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[10] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, 2011.
[11] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-banee problem with non-stationary rewards. Advances in Neural Information Processing Systems, 27, 2014.
[12] Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, and Julien Seznec. Efficient change-point detection for tackling piecewise-stationary bandits. Journal of Machine Learning Research, 23(77):1-40, 2022.
[13] Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125): 2021.
[14] Yining Wang. On adaptivity in nonstationary stochastic optimization with bandit feedback. Operations Research, 73(2):819-828 2025.
[15] Mark Herbster and Manfred K. Warmuth. Tracking the Best Expert. Machine Learning, 32(2): 151-178, August 1998.
[16] Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, et al. Dynamic regret of strongly adaptive methods. In International conference on machine learning, pages 5882-5891. PMLR, 2018.
[17] Lijun Zhang, Shiyin Lu, and Tianbao Yang. Minimizing dynamic regret and adaptive regret simultaneously. In International Conference on Artificial Intelligence and Statistics, pages 309-319. PMLR, 2020.
[18] Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments, In International Conference on Machine Learning, volume 382 of ACM International Conference Proceeding Series, pages 393-400, ACM, 2009.
[19] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pages 1405-1411. PMLR, 2015.
[20] Nicold Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert F. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427-485, May
1997.
[21] Tianyi Chen and Georgios B Giannakis. Bandit convex optimization for scalable and dynamic LoT management. IEEE Internet of Things Journal, (1)::1276-186. 2018.
[22] Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. Metagrad: Adaptation using multiple learning rates online learning. Journal of Machine Learning Research, 22(161): 1-61, 2021.
11

---

[23] Guanghui Wang, Shiyin Lu, and Lijun Zhang. Adaptivity and optimality: A universal algorithm for online convex optimization. In Proceedings of The 35th Uncertainty in Artificcal Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 659-668. PMLR, 2020.
[24] Lijun Zhang. Guanghui Wang, Wei-Wer Wei Tu, Wei Jiang, and Zhi-Hua Zhou. Dual adaptivity: a universal algorithm for minimizing the adaptive regret of convex functions. In International Conference on Neural Information Processing Systems. Curran Associates Inc., 2021.
[25] Abraham Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimiza- tion in the bandit setting: gradient descent without a gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 385-394. SIAM, 2005.
[26] Robert Kleinberg, Nearly tight bounds for the continuum-armen bandit problem. In International Conference on Neural Information Processing Systems, page 697-704. MIT Press, 2004.
[27] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non- stationarity. In International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 1079-1087. PMLR, 2019.
[28] Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages
PMLR, 2021.
[29] Alekh Agarwal, Dean Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin. Stochas- tic convex optimization with bandit feedback. Advances in Neural Information Processing Systems, 24, 2011.
[30] Ankan Saha and Ambuj Tewari. Improved regret guarantees for online smooth convex optimiza- tion with bandit feedback. In International conference artificial intelligence and statistics, pages 636-642. JMLR Workshop and Conference Proceedings, 2011.
[31] Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack Mayo. Online newton method for bandit convex optimisation. In Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1713-1714. PMLR, 2024.
[32] Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimization. Journal of the ACM, 68(4):1-35, 2021.
[33] Elad Hazan and Kfrr Levy. Bandit convex optimization: Towards tight bounds. In Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014.
[34] Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In The Thirty Seventh Annual Conference on Learning Theory, pages 4691-4766. PMLR, 2024.
[35] Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 4008-4067. PMLR, 2021.
[36] Tor Lattimore and András György. second-order method for stochastic bandit convex optimisation. In Conference on Learning Theory, pages 2067-2094, PMLR, 2023.
[37] Olivier Bousquet and Manfred K Warmuth. Tracking small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3(Nov)3363333)) 2002.
[38] N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Compu- tation, 108(2):212-261 1994.
[39] Vovk. game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153-173, 1998.
[40] Yoav Freund, Robert Schapire, Yoram Singer, and Manfred Warmuth. Using and combining predictors that specialize. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 01 1997.
12

---

[41] Wouter M Koolen and Tim Van Erven. Second-ords quantile methods for experts and combina- torial games. Conference on Learning Theory, pages 1155-1175, PMLR,, 2015.
[42] Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. Journal of Machine Learning Research, 17(23):1-21, 2016.
[43] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Online learning for changing environments using coin betting, arXiv preprint arXiv:1711.0255 2017.
[44] Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Interna- tional Conference on Machine Learning, volume 119, pages 2250-2259, PMLR, 2020.
[45] Zhou Lu, Wenhan Xia, Sanjeev Arora, and Elad Hazan. Adaptive gradient methods with local guarantees. arXiv preprint arXiv:2203.0144 2022.
[46] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Statistics, pages 1805-1845. PMLR, 2022.
[47] Guanghui Wang, Dakuan Zhao, and Lijun Zhang. Minimizing adaptive regret with one gradient per iteration. In International Joint Conference on Artificial Intelligence, IJCAI 18, page 2762-2768. AAAI Press, 2018
[48] Peng Zhao, Yan-Feng Xie, Lijun Zhang, and Zhi-Hua Zhou, Efficient methods for non-stationary online learning, Advances in Neural Information Processing Systems, 35:11573- 2022.
[49] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, Adaptive online learning in dynamic environments. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 1330-1340. Curran Associates Inc., 2018.
[50] Wenhao Yang, Yibo Wang, Peng Zhao, and Lijun Zhang. Universal online convex optimization with projection per round. In Advances in Neural Information Processing Systems, volume 37, pages 31438-31472 31472, Curran Associates, Inc., 2024.
[51] Peter L. Bartlett, Elad Hazan, and Alexander Rakhlin. Adaptive online gradient descent. In Proceedings of the 21 International Conference on Neural Information Processing Systems, page 65-72. Curran Associates Inc., 2007.
[52] Chuong B. Do. Quoe V. Le, and Chuan-Sheng Foo. Proximal regularization for online and batch learning. In International Conference on Machine Learning, page 257-264. Association for Computing Machinery, 2009.
[53] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[54] Sébastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. Bandit convex optimization: VT regret in one dimension. In Conference Learning Theorr, pages 266-278. PMLR, 2015.
[55] Sébastien Bubeck and Ronen Eldan, Exploratory distributions for convex functions. Mathemat- ical Statistics and Learning, 1(1):73-100, 2018
[56] Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathe- matical Statistics and Learning, 2(3):311 2020.
[57] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256 2002.
[58] Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 116),1516-1541, 2013.
[59] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002.
13

---

[60] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 1933.
[61] Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi- -rmeed bandit problem. In Conference on Learning Theory, 2012.
[62] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
[63] Fang Liu, Joohyun Lee, and Ness B. Shroff. A change-detection based framework for piecewise- stationary multi- bandit problem. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[64] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-statioon stationary bandit. In International Conference on Artificial Intelligence and Statistics, pages 418-427. PMLR, 2019.
[65] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, volume 99, pages 138-158. PMLR, 2019.
[66] 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-4355 PMLR, 2021.
[67] Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2160- 2182, 2022.
[68] Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019.
[69] Francesco Trovô, Marcello Restelli, and Nicola Gatti. Sliding-window thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:31 1-364, 2020.
[70] Dorian Baudry, Yoan Russac, and Olivier Cappé. On limited-memory subsampling strategies for bandits. In International Conference on Machine Learning, pages 727-737. PMLR, 2021.
[71] Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smooth- ness in derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 33:9017-9027, 2020.
[72] Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory, pages 3-24. PMLR, 2013.
[73] Shinji Ito. An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss. In International Conference on Artificial Intelligence and Statistics, pages 2229- 2239. PMLR, 2020.
[74] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, (6(2))169-192 December 2007.
[75] Haipeng Luo, Chen- Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pages 1739-1776. PMLR, 2018.
[76] Yifang Chen, Chung-Wei Lee, Haipeng Luo, and Cuen-Yu Wei. A new algorithm for non- stationary contextual bandits: Efficient, optimal and parameter-free. Conference on Learning Theory, pages 696-726. PMLR, 2019.
[77] Gilles Stoltz. Incomplete information and internal regret in prediction of individual sequences. Theses, Université Paris Sud- Paris XI, May 2005.
[78] Arya Akhavan, Karim Lounici, Massimiliano Pontil, and Alexandre B Tsybakov. Contextual continuum bandits: Static versus dynamic regret. arXiv preprint arXiv:2406.0577 2024.
14

---

[79] Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009.
15

---

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: In Section 1, we define our problem setting, goals of the paper, and assumptions we make throughout the paper. In Section 1.1 we describe our main contributions and results, while in Section 1.2 we contextualize our work by discussing related work. The abstract summarizes these.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 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: In the main contributions section (Section 1.1), we describe the limitations of the work: the polynomial-tne
algorithm TEWA-SE we develop attains suboptimal regret bounds for general convex losses, and cExO, the second algorithm we propose, achieves optimal rates w.r.t. T, and A, but is not polynomial-time computable and has suboptimal rates w.r.t. the problem dimension d. These limitations are discussed in detail after we state each theoretical result, and restated in the conclusion (Section 4). We also discuss the potential suboptimality of both algorithms w.r.t. the path-length P in our main results section and in the conclusion.
Guidelines:
The answer NA means that the paper has no 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 any strong assumptions and how robust the results are to violations of these assumptions (e.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 few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
16

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in 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 a complete (and correct) proof?
Answer: [Yes]
Justification: We state all assumptions we make in Section Each theoretical result is followed by reference its detailed proof in the appendices. We provide all proofs in the appendices: definitions (Appendix A), proof of Proposition 1 (Appendix B), proof' for TEWA-SE (Appendix C), proof' of lower bounds (Appendix D), and proofs for cExO (Appendix E).
Guidelines:
The answer NA means that the paper does not 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 in 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 supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: This paper is theoretical in nature and does not include experimental results.
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 is 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, or 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 a 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
17

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: /nipsnip..... cc/
pub 1ieelic/// qqigueiee des //wd/Coouuunnnn ssionPoo ConPollcy) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips cc/ publiccicc belbiic/guu gu ddes SCtd/CooSSuaaaa SuseSuumisss. ss onPol 1lll1ppp ecy) 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 are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing 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: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, 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?
18

---

Answer: [NA]
Justification:
This paper does not include experiments.
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, confi- dence intervals, statistical significance tests, 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, or 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.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error 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 error 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
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://eeeripp.eeeee wwtppb/lcc/tticeeeeeeeeeaeeeeeee
Answer: [Yes]
Justification: This work has been conducted a way that fully conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 (c.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
19

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is theoretical in nature and is expected have significant social impacts, positive or negative.
Guidelines:
The answer NA means that there 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 (c.g., dep.lymelm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it 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, 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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:
This paper does not use such assets.
Guidelines:
20

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be 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.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers s w thcode com/ catasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
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: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part 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 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 crowdsourcing 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:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
21

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on 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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standary components.
Please refer to our LLM policy (https: www.rips.../oooeeeeeeeeeeeeeeeee cor/Coneeeeecess / 2025/ LLM) for what should or should not described.
22

---

A Definitions
Definition 1. Let a > 0. random variable & is a-sub-Gaussian if for any X we have E(exp(AE)] S (x)((222/2).
> d function f Rd - called a-strongly convex, if for æ, 2 RR, f(z) 2 f()) + (=) 2) - --112.
Definition
Definition 3. Let 3 0. Function f: Rd + R is called B-smooth, if is continuously differentiable and any 2, 2 R
- 31 - 2||.
Definition 4. Let K 0. Function f Rd + IR called K K-Lipschitz if for any æ, 2 E R&. [f(x) - f(=) S K K - z||.
B Proof of Proposition 1
We start this section by restating the proposition, before detailing its proof.
Proposition Suppose that an algorithm can be calibrated to satisfy (ada T) S CB*, for,for any interval length B E [T], for some factor C >> 0 that is most polynomial in d and log(T),, and E [0, 1).
Then, for any S, S, Sp [T], an appropriate choice of B yields the following regret guarantees:
Switching:
B
guarantees that R (T,S) -ST-TT=
Dynamic:
yields R (T, A) R (T, R (T. SA)
I 5a
Sa
Path-length:
ensures that Reath (T, P) S RSw (T. TT.rr) + SF
Sp
Proof of Proposition /. The proof follows two steps. First, we state in Lemma the conversion between adaptive regret and switching regret. similar conversion can be found in [19], but we detail the proof for completeness. Next, we prove in Lemma 2 that switching regret guarantees for appropriate number of switches convert into dynamic and path-length regret guarantees.
In the remainder of this section, we detail the two supporting lemmas and their proof. Lemma 1. Consider an algorithm that satisfies the adaptive regret guarantees of Proposition 1, then this algorithum calibrated with interval size B = satisfies
RSWI (T, S) S 2 C
Proof of Lemma Consider B [ Let u1.T T be a sequence arbitrary comparators with at most S switches. We divide the horizon into intervals of length B (the last interval may be shorter than B), and further divide the intervals at the rounds where u, * u4-1- This ensures each of these intervals is associated with a constant comparator. By construction, these intervals are of length < B and the number of intervals is bounded by 25. Hence, we can apply the adaptive regret bound each interval to obtain
Rawi (T, 25 CB 2CS
(5)1)²
20 S2-KTK
(1 [) <2++ -2--aC.
We now prove the conversion between switching regret and dynamic and path-length regrets. Lemma Consider any fictitious number of switches S' [T'. Then the dynamic regret of environments constrained by A satisfies
(T, A) < R3M (T, S²)
(20)
37
and the path-length regret satisfies
1eath
P) < R.Si
(T,
S', + -
(21)
23

---

Proof of Lemma 2. For both upper bounds, the switching regret term comes from dividing the horizon [T] into S' intervals, denoted by (L)) each of length most 5 (defining them precisely is important for the following arguments). Recall the definition of R(T, u1:T) from (2). For any sequence of actions 21.T E @ chosen by the given algorithm, and for any arbitrary comparator sequences u1r O" and V1.9* E e it holds that
T
R(T, u1:)
[f((2)) - [(()))
T
1(t L)) (B[f((z)) - f((vs)] (fi(v.) - f((u)))
S
$ Aswi (T,S')
(f((vs) - f((u)))
(22)
EE
where the last step holds by the definition of the switching regret. It thus remains to choose suitable v. E O and upper bound the term V. for E [S"] We choose a different v, for the proof of the dynamic regret bound vs. that of the path-length regret bound.
Dynamic regret. Consider the interval T, for
[S']. Let Lg be its length and A, Exer, max [f((=) fz-((=) | be the total variation over this interval. Then, for any two time steps L and l' in I, and any θ it holds that fa(=) (z) < A, by definition of total variation. Let fa denote the average of the functions over the interval Ia and define vs E arg min fz)2..
then we have
Vs E [S"],
V. S
((i(v.)) fo + A.) AoL..
tEL.
Taking the sum over all intervals and using L, S [ completes the proof of (20).
Path-length regret. This proof proceeds similarly that for the dynamic regret. Consider the interval La for some & E [S"], and denote by La its length and Pa = Eter, |M, u:-1 || the path- length of the comparator sequence on this interval. For the proof, we construct v, θ differently from that in the proof of the dynamic regret. Before detailing the construction of v,, we first define a set of comparators (ul)eL, t as follows: for some og [0, 1] and any time t Lg, define wi to satisfy v, = agu, + (1 - ap) an)uu, Ju( Using this and by the convexity and boundedness of ft. we can bound that
f((v.) S f(())) + (1 (o)() f(())) S f((u,) + 2(1))a)) aa)
We then proceed by choosing a suitable v, and ay to make this bound depend on the path-length. Since the path-length is P.. there exists an ball of radius & that contains the comparators (Mt)s and its center c, lies in the feasible domain O By assumption (as we stated in Section 1), there also exists a ball with radius and center c, within the domain. We can thus construct v, to satisfy
ao (c.. uz) 1 - ax
v. anCy + (1 ao)c, θ which yields ui = +
(23)
where v. due to the convexity of the domain. Our goal then to choose ag as large as possible (to make - ag small) such that all the comparators (u)),,,, belong to θ. Eq. (23) implies that
|ui c,lll
Og
||c,
uill < Oro P.
og
okg
0gg
2(1 (11))))
which by definition of the ball guarantees that u' E θ as long 21-aa) condition, we can thus pick on =
apfa S To satisfy this
which guarantees by construction that P.+2r-
2r
P. S f((()) + - Vt E Is: f((v.) S f((u)) + P. + 2r
2P.
The desired bound on V, (22) directly follows. The final result (21) then comes by summation over all intervals (Ly)=E[9).
D
24

---

C Details and proofs for TEWA-SE
In this appendix, we provide additional details on TEWA-SE Section C. and establish its theoretical guarantees in Sections C.4-C.6, We present the proof of Theorem in Section C.2, followed by the supporting lemmas in Sections C.3 and C.4. We then provide the proof of Corollary in Section C.5, and the parameter-free guarantees in Section C.6.
C.1 Additional details on TEWA-SE
As described in Section 2. TEWA-SE handles non-stationary environments by employing the Geometric Covering (GC) scheme from [19] to schedule experts across different time intervals. Additionally, TEWA-SE assigns exponential grid of learning rates the multiple experts covering each GC interval, to adapt to the curvature of the loss functions. We first invoke the definition of GC intervals from [19].
Definition 5 (Geometric Covering (GC) intervals [19]). For k E N, define the set of intervals
Is {[i- 2h (i+ 2 -
(24)
that is, Ig is a partition N'+ [2 1] into intervals of length 2 Then we call I UKEN Ix the set of Geometric Covering (GC) intervals.
For any interval length N we also define the exponential grid of learning rates as
S(L) = 2
: {0. I.... logg 41}
(25)
5GD
where the uniform upper bound (10) on 19,ll. and D is the diameter of the feasible set θ For each given GC interval / = [r,s] E I. TEWA-SE instantiates multiple experts in round r. each assigned a distinct learning rate 7) E S((/)) and surrogate loss E as defined (11). removes these experts after round This scheduling scheme ensures least one expert covering I effectively minimizes the linearized regret Eter (Elg, | Ar], 2, u) associated with f on the interval T (Lemma 5), ultimately yielding the regret guarantees in Theorem and Corollary 1.
Polylogarithmic computational complexity For t E N+, use C, {I E I E I} to denote
the set of GC intervals covering time t. From Definition 5 is easy to verify that [C, = 1 + logg t
The longest interval in C, has length at most I, which is associated with most S(L)) = 1 2 log,
experts. With A, {E(1, n) t I} representing the of experts active in round t, the number of active experts in round denoted by
[Arl in Algorithm 1, satisfies
n S (1 + [loge 4J) (1 + log, ())
(26)
This ensures that the computational complexity TEWA-SE is only Oloog T') per round.
Tilted Exponentially Weighted Average In each round I, TEWA-SE aggregates the actions proposed by the active experts 1)) A, using exponential weights, tilted by their respective learning rates, by computing
EBuMEA nexpl -1),--"__,,)=", K
(27)
EF(iEEA hexp(-L"
where for / -= [r, loss accrued by expert E(I, .7) over the interval [r, t 1]. Note that (27) is equivalent to line 7 of Algorithm 1, rewritten with notation better suited for our proof.
and & E [r 1, - (" represents the cumulative surrogate
In what follows, we prove some theoretical guarantees for TEWA-SE.
C.2 Proof of Theorem
In this section, we first restate Theorem and provide its complete proof, which relies on several supporting lemmas. For clarity of exposition, we defer the statements and proofs of these supporting lemmas to the following sections.
25

---

Theorem 1. For any T E N+ and B E [T). Algorithm 1 with h = min( VdB i) satisfies
(B.T) (B,) 2
Rade
vdB +d?,
(14)
and if Jt is a-strongly-commex with arg min [+:):) for all & (T], it furthermore holds that
Rada (B, T) _ B
(15)
where S conceals polylogarithmic terms in B and T, independent of d and a.
Proof of Theorem I. We prove (14) for the general convex case and (15) for the strongly-convex case similarly. To bound Rade (B, (B, we will uniformly bound Ltzp E[f((z)) - ft(u) across all
comparators @ and intervals [p, g] shorter than B. Common setup: Invoking the event Ar {l&i 20 since ) are -suub-Guusian, have
/ Log(( + 1), Vt [T] defined above (10),
T
T+1 2
P(A))
&
15t 20 log(T +
T-2 27
(28)
2=
By the law of total expectation write for any E θ
Σ E(f((z)) fe(u)] E[f((z,) fe(u)) AT)P((T) Σ E f()))z) fe(u)
P(A7)
52T
-[)(zz)) -e(u) Ar] +4.
(29)
To bound the first term in the last display, consider the following decomposition
[(((zz)) - Se(u)) AT]
E(fe(z)) f((x))) Arl
(x.) - f((x)) Arl +
E E(f((n))) Pa(w)] AT)
E E Se(u) Ar)
(30)
term III
term TV
Since ft is convex, by Jensen's inequality we obtain that term II is negative (c.f. [71, Lemma A.2 (ii)). In what follows, we bound terms I, III and IV in this decomposition separately for the general convex case and the strongly-convex case.
General convex and Lipschitz case: Recall that (C,)7= denote uniform samples from the unit sphere OBd, and ? denotes a uniform sample from the unit ball Bd, while f(())) Ef + At)) Va e θ Since (f:)²= are K K-Lipschitz, ||C,]| 1, and E[I[[|] < 1, we can bound term I and term IV by
term =
E [ff hc,) fx AT
< K(g + 1)h,
(31)
term IV
E E[ 12) fu())) AT]
< K(g p 1)h.
(32)
'The assumption that loss minimizers lie inside θ is common in zeroth-orde order optimization. see 72, 73]. Without upper bound analysis would have extra term depending the gradients the minimizers.
26

---

To bound term III, recall that 9, denotes the gradient estimate of ft at 22. We use the convexity of ft and apply Lemma to obtain that for any u E
4
term III E
Elg, X Ar, w)
AT
E
a + 3G apobpa
0 w/12 |AT
P..Dap.appa + 3GDDVV //ppapaaaaaaa// p+
(33)
where all constants are explicit in the statement of the lemma. By combining the bounds for all four terms (30) with (29), and using h = min (vØB : r). G (1 + 2a / Vlg + 1)), ap. = + 2 log((2) (2q) + 2 log(g - + 1) & 6Tog(T + 1), and bp.q = 2 [lgg (g- p + 2) - 6 6log [B + 1).
establish that
nada (B, T) < 10G 10G p.. + +GD ap. Vu p--pp-- p+l+ - - 1)4
CVdBi +4 if <dB-
C2 C2d +4
hf
s CvdBt ccd + C2d +4,
(34)
where C, C,C1, C2 > 0 are polylogarithmic in T, independent of d, defined with My = + 20 Vogg(T + +) and Nr.B = log(T + 1) log(B + 1) as
C = 18DM, (V Nr, 20.Nr, + 2K
(35)
C = (18DMr / Nr.8 + 2K) 2K)/r
(36)
C2 = M7.
(37)
This concludes the proof of (14).
Strongly-convex and smooth case: Due to the B-smoothness of ft and the fact that E(C,] = E =
O and |[] < Elik,, [| = 1, we can bound term I and term IV each by [ - p --l---+00 1>12 When III than that (33) by restricting
the ft's are grongly-conves, we can derive tighter bound on the comparator the clipped domain θ and using the fact that when is a-strongly convex on O fe is a-strongly convex on (c.f. [71, Lemma A.3]). That is, we have for any u θ
term III <
E
(E(g, la, Ar), xt - un
| u/l? AT
2
10G 10GDap.opp + +GG 33vaappupp E
Σ
|
u112
a
Σ
xt
u/
AA
2 t=p
=
< (10GD + l apabp.a
(38)
where the last inequality holds because term ö uniformly bounded as follows:
G apppppp if V Ei-p 1| u2 < bap.ppp..
8 <
otherwise.
Combining (38) with (30) and simplifying yields for any u E G,
9
E[f((z)) fi(u)] (10GD 18 G²) ap.bp. + B(q p 1)h² +4.
(39)
The final step is to handle the case where the comparator E 0 Ô. Consider the worst case when the comparator is u² aig E fe(u) with u² θ é. Let ū" 1lo(u"). If
27

---

arg f((x)) E 6 Vt [T], then by the B-smoothness of the fi's we have
Σ - f -
Vi(u"))) ūt - u²) + i - u 113
2
- 1)h². (40)
2h2
Combining (39) with (40) yields
Rada (B, T) < (10GD + a G²"
apaina 3 p 1)h² +
C'ddBB+ 4
if VJB
1f C₁d +4 if
< C + C + C,
(41)
where C", C, C2 > 0 are polylogarithmic in T and B, independent of d, defined as
C" 72 (9My + 5aDB- 1) MT Nr. + 3 Ba
(42)
C (648M7NNT. + Ba)/
(43)
C22 360D.M.NT.B/...
(44)
This concludes the proof of (15).
The proof above crucially relies on Lemma 3, which we state and prove in the following section.
C.3 Upper bounds on lincarized regret
Lemma 3 establishes an upper bound on the linearized regret associated with the smoothed loss fo for any arbitrary interval /- = [p. 9] C [1, This result builds two key components: Lemma which characterizes how given arbitrary interval covered by a sequence of GC intervals, and Lemma 5, which provides upper bound on the linearized regret for each GC interval E Z. For
clarity, we first present and prove Lemma 3, then proceed to detail the supporting Lemmas and 5.
Lemma (Linearized regret on an arbitrary interval). For an arbitrary interval I [p. 4l S [1, Algorithm 1 satisfies for all O,
u) S 10GDap. + 3G ap.0
/
Σ
Dt - u112
(45)
where dp.q 20gg(2)) llggg - -p 1) and and = 22(logz(g - p 2)7.
Proof of Lemma 3. This proof follows similar arguments those used in proving the first part of [24, Theorem 2]. To begin, according to Lemma 4, any arbitrary interval / = [p, q] S [1, T" can be covered by two sequences of consecutive and disjoint GC intervals, denoted by 1 ---......... lo E I and II,..., In E I, where n, m E N with n < flog, Note that negative indices correspond GC intervals that precede Iy. while positive indices cor- respond to intervals that follow The indices indicate temporal ordering and are unrelated to the length of the intervals.
+ 2)] and m + 1 < flog2(q - + 2)].
By applying the linearized regret bound from Lemma 5 to each GC interval, and noticing that a,,a S ap.q for any subinterval [] S [p. g] (as evident from the definition of ap in (45)),
28

---

establish for all u E t,
7
E g2,, Arl,
u) Σ
E Dy. Arl, u)
rET:
3G Up.a Σ
2 + 10GDap.
1=-m m
1E4.
n1 100 10G + m + 1) 3G 3G /apaa
l 2012
DEL.
n
10GDap. +m+ + 3G Vapay
(n +
Σ
Σ
0t ul
NET:
S 10GDapoopa + 3G ap.aapp
Σ t=p
|0, - -2 u1l2
(46)
where the last step uses n + m + 1 1 2 [log2 (g - p + 2)] =: b
We now present Lemmas 4 and 5 which used to prove Lemma above.
Lemma (Covering property of GC intervals). Any arbitrary interval I = -p. g) S NO can be parti- tioned into two finite sequences of consecutive and disjoint GC intervals, denoted by I_m..... Io I and J J,,..., Ja E I, where = Uh=mm Ii, such that
|T-il
[+ |411
vi 1, and
1
Vi 2 2,
(47)
| [_411
with
n < ( and m +15 flog2(q (q - + 2)]
(48)
Proof of Lemma 4. Eq. (47) directly comes from [19, Lemma 1.2]. To prove (48), suppose for
contradiction n > [loga p + 2)], then we have
M 2
2
2 -
(49)
i=1
contradicting the fact that Uh_-m I I. By the same reasoning, we have m + < [log2(ą - 2)].
Lemma 5 (Linearized regret on a GC interval). For any GC interval I = [r, 8] E I, Algorithm satisfies for all O,
Dr u) < 3G, 0r,8
x 2112 + 10GDa Dar.e
(50)
where ar,s = 22g((2)) + 1 log(s - + 1).
Proof of Lemma 5. This proof is similar to that of [24, Lemma 12]. For any GC interval / = [r, s] E I and learning rate
S(s + 1), we can apply the definition of surrogate loss L from (11),

---

noticing that (x+) = 0, to obtain for all O
(E(g, Ar), xt u) Σ G ull
El (2)) 1zc
Σ E (2+)) (20k,)) De, AT]
Σ E ((() (()) 1os Ar
meta-regret log(2s)
expen.regrett
+ log(
< 2 12g(2s) + - 1 log(s r 1) ar,a
(51)
where the last step applies the upper bound on the expert-regret established in Lemma 6 and the upper bound on the meta-regret Lemma both which we defer to Section C.4. Eq. (51) can be rearranged into
Le, De, AT], u) S
anea
+ n/2
Σ
|00; u112
(52)
11
The optimal value of v that minimizes the RHS of (52) is
Or,s
n
(53)
G2 Ei
[t u |
Note that since 0r,s 2 21 1)" 2
GD [[1-++1] for all O.
The next step to select a value
from the set S(s 1 =
2-
{0, 10,1,....
logg(s }) that best approximates
LGD
77. Two cases arises:
i) if < 3GD there must exist an E S(s + 1) such that 4 S n S 17. Substituting this choice of 7 into (52) gives
20r Eig,l,, Arl, u) <
+ +n G²
| u11²= = 3G
Gr,s
|2
u 22.
17"
1=1
t=r
(54)
ii) 1f 5GD then the best choice of 17 E S(s 1) is 5GD which leads to
Eig D., Arl. u) S ar,s 5GD 2 10G
(55)
Combining (54)-(55) concludes the proof.
The proof of Lemma 5 above relied on the upper bounds the expert-regret and meta-regret from Lemmas 6 and 7. We present and prove these lemmas in the following section.
C.4 Upper bounds expert-regret and meta-regret
Lemma 6 (Expert-regret). For any GC interval I = [r, s] E Z and learning rate 1 E S(s - - + 1), Algorithm I satisfies for all E é,
E (((T,1) - (7()) De, '" Ar|
s 1 2 + 1 log(s r 1).
(56)
30

---

Proof of Lemma 6. The proof follows standard convergence analysis of projected online gradient descent for strongly convex objective functions, see e.g., [74, Theorem 1]. For any time step the surrogate loss Ey associated with the expert with learning rate v and lifetime 7 /= [r, s) serves as
our strongly-convex objective function. By applying the definition of G, we have for all O
VV (1)
Wr Ar]
= E [|ng. + 2nj (x - xz)]l xe,, Ar]
< E (111 + G² - ==))1) [ Ar]
S <G') (57)
where we introduced G' n + 21y² G By the update rule of our projected online gradient descent with step size Hr (line 4 of Algorithm 2), we have for all u E 6,
| - u/
||اا (,",, - ue Ve (e (x=,, )) =ll
-
I 14 Ve u|1
||=,", 22 pt Ve? (x" 24 u) u) (Z]()
which can be rearranged into
| u112 - |
2112
2( w) T Ve?(("")) S
+ V 2 11
(58)
Ht
Define shorthand A = 2r2² and recall He = 1/(Att-rr r 1)), then Eq. (58) implies that
a - u) (x( A Σ | - uel2
| u112 | 1,J
22
Mel ( - - Σ
|x0
uel2
t=r
t=r
1-
Σ
|,-",, - -ull2
-
1
1
2
+|l22, - u11
x
| s+1,1
2012
H4
H4-1
Hr
t=
=0
=0
20
Σ VIIV <
(59)
Noticing that with any given H, E Rd, E is X-strooglyy we apply (59) obtain that for all θ,
(T(,) - (2) It, "","",,,111
< E 2 2 u) (x,)))))
|| | Σ
u1? (0,, Ii Ar
E
Ve 2 xt. x A7
2
())
(10)
(1 + log(s + 1)) S 1 log(s - r + +1,
(60)
where (i) is result of (57). (ii) uses the bound Ek= < 1 + logn n for any E N+ and (iii) uses the fact that given 1) 5 50D it holds that
( + G² D) G² An G 22 < G² G2 0 < X
0
Lemma 7 (Meta-regret). For any GC interval I = [r, s] e I and learning rate n E S(s - r + 1),
Algorithm I satisfies
e (xx) E7 (x(,))) De, 21, =
E E. (xx,,)
De. x",, Ar] s 2lg((2s). (61)
31

---

Proof of Lemma 7. The proof is similar to that of [24, Lemma 6]. By Jensen's 's inequality and the convexity of norms, we have for all æ E θ
E E (t,, Arl, at x) | S E E at AT]lll x
E |19.1 Cr. Zr, AT] || - æll - GD,
(62)
which, given S 5GD implies that
17 (Eig,lze,Ar) Arl. xi- -x) 2 -nGD 2 -
(63)
Using (62)-(63) and applying the inequality In(1 2) 7 (El g. zt, Arl, It - 2), we obtain for all x E θ
2² for any 2 with
exp ( (- (x)) xe, Arl) = exp (1 (Elg [1, Arl n; - x) 1/ G [ - x1(²)
I exp 17 ( 3 Ar) 22 - x) - r² (E 2t. AT), 2; xx)))
- 1+ + 7 (E L A xt
(64)
Define shorthand F"11 = {x 2²,, Ar and HH = Ure F,, for t E [7]. Using (64), we can write for every & E (7).
Σ exp
E (7,1)
B(,.)E
Σ
exp (-E(LT_1, 1 exp (-E(-E((((()))) (2,11)
E(I.n)A
Σ exp
(-E(LE_1, H ( [1 + EEg 2. Ar,. X =,,ii== (65)
B(..))AA
The second term on the RHS can be bounded as follows:
Σ
exp( -E H2
(7 Arl - x²",,) ||
E(U.)E..
Elgr 1r,, AT], Σ
mexp( Pexp(-E[4A-)) 1 11) - wx,,))
B(L.)).A
Elg (2 ATl,
n (exp(-Li) -(-1.r) | H | (or - xm²;,))
Elg
[ (x AT],
Σ
7exp(
Lexp(-Li ni L. - -x,;,> |+/ ]
( 0,
(66)
E(
where (i) applies Jensen's 's inequality, and (ii) is due to the update rule of æz (27). Combining (65)-(66) yields
Σ
exp (-ELLY, HY,7)
Σ exp (-E(LY,, 04 10
(67)
E(
E(I.)).A
By summing both sides of (67) over t 1,.... s and rewriting, obtain
Σ
exp
(-E[L",
Σ
exp (-E(L,, (22)))
E(L.)A
A.L
Σ
Σ
exp (EELL,, (
1= E(LAEAAinA
Σ
(EE(L,.1)
+ Σ
Σ
exp -ELL (0E_1.1)) +
exp
B(..EA
2= A...
Σ
Σ
exp (-EILY (H-.,.l).
(68)
2=2 AiA
32

---

Canceling the equivalent last terms on both sides of (68) and noting that L²,, 0 for min e 1)
by construction (see line 4 of Algorithm 1), we obtain for 1,
Σ
exp
-EIL
E
exp (-E[L?, Hg,rl)
E(
SU..)EAA\Ar.
Σ
exp E
E
exp
E
1-111
1,1 H2 (H
B(IM)EA
E(L
E
exp(0) +
Σ E
exp(1)
B(LMEA
1=2 E(L.))EA A4-1
= |Ail+
+
Σ
Ae A--1 $ Σ
Ail
1=2
1=1
(
Σ (1+ [log2 t|) (1 +
logz t|) S 5
(1 + log, t)² S 4s²
(69)
1=1
where (i) applies (26), and (ii) is due to + log2
< 2v 11 2 1. Since exp(x) > 0 for E R, Eq. (69) implics that for any GC interval = s] and learning rate 17 E (())).
exp (-E(LY,
(H,,)) = exp
Σ EECCOND < 482.
(70)
Taking the logarithm both sides completes the proof.
C.5 Proof of Corollary
We first restate Corollary and then provide the proof. Recall that for clarity we drop the [-] operators from the expressions for B and assume without loss of generality the expressions take integer values. Corollary 1. Consider any horizon T E N+ and assume that, for all L E [T], the loss Se is convex, or strongly-conver with arg minzeR f((x) E O. We refer to the second scenario as the strongly-conver (SC) case. Then, Algorithm I tuned with parameter B satisfies the following regret guarantees:
[Vastt: + d2 (dvST dS (SC)
Switching.
B
T
R
(T,S)
T
VeT
= Rdm (T. A) S R S) A + +d3
Dynamic.
S
B T
=
3
4T
1
3 RT
A, S) S n (T, 5) ^ Atit d (SC)
B
rvaT
Rpath (T, P) S td +d
Path-length.
B
rdl
= Roath (T.P)
- r dd id (SC).
Proof of Corollary 1. We begin by applying the first result in Proposition with the adaptive regret guarantees in Theorem to obtain switching regret guarantees. For known S, Algorithm with parameter B I'' achieves in the general convex case, s R (T,S) < 2c + 2(C1 + a + )dS,
(71)
and in the case where ft is a a--sttongly--omee and arg min f((x) E θ for all t E [T],
naii (T,S) < 2C'd + 2 _ + )dd
(72)
where C₁ C2, C², Ci C3 > 0 are the terms defined in (35) and (42)-(44) which polylog- arithmic in T and B. When S and A are both known, we use (71)-(7) and apply the second result in Proposition to bound poyn S). Specifically, for general convex losses, Algorithm I with
B T
yields
Rdyn (T, A, < Rawi (T,S) A Foyn A),
33

---

where Fdym (T, A) = (2C' + 1 A + + + 3 + dd For strongly-convex losses
with minimizers inside e, Algorithm 1 with B V dT gives
novn (T, (, < n (T, S) byy A).
where Fsc (T (2C" + A 2 +
a + f A Finally, for known P
we use (71) and apply the third result in Proposition to bound Ieam (T,P), P). For the general convex case, taking rv/dT) $ gives
ppath (T, P) & (2C + 1)r 2(1 + C - P
For strongly-convex losses with minimizers inside 6, taking B = (पक yields
Rpaah (T, (2C' + id + 2(C C 3)r d
C.6 Parameter-free upper bounds
Corollary presents the optimal choice of parameter B for TEWA-SE when S, A and P are known. When the non- -ssts-ttttinttty measures are unknown, the optimal B cannot be directly computed, and we therefore employ the Bandit-over-Bande (BoB) framework from [27] to adaptively select B from a prespecified set = (2' : 0, 1 .... [log, T}}. BoB has been used [66] in a similar fashion to obtain parameter-free free algorithms. Specifically, BoB divides the time horizon into E = [T/L] epochs each with length L, denoted by (L=)== (where the last epoch may be shorter than L). In the first epoch, it runs TEWA-SE with B = B, which is randomly selected from B. For subsequent epochs, uses the cumulative empirical loss on the current epoch e to select B, E B for the next epoch via EXP3 [59]. That is, BoB computes
B In( (B( -VV-A (e 1)
pe,t (1 - 7) Σ Eve[B Se,
Vi
[B]] with 7
(73)
B
where e denotes the base of the exponential function, and then samples i. = i with probability Pe, yielding B, = 1.5 For i E [[B]] initialized with s0, = 1, the quantity se, for E N+ is updated by computing
Se+1, = Se,s exp
7 B
Fe.s)
(74)
where with My = 1 + 20 Vlog(T + 1), the wnportance-weighteed reward fe,s takes the form
Fe,s = (1 + I EiEr. (1 (1-)))) yi) /Pe.s
={(0
if otherwise.
2LMr
(75)
Note that conditioned on the event Ar = {15el S 20 /loloolooTToTT +1, V E [ defined above (10), the absolute total reward in each epoch is bounded by Q max,e[E] EIE1, y:) S LMr, which ensures the rescaled reward 1 + ZZhr Eier (1 yt in (75) remains bounded within [o, 1]. The pseudo-code for TEWA-SE equipped with BoB provided Algorithm 4, with theoretical guarantees detailed in Corollary 3.
Corollary 3 (TEWA-SE with BoB). Consider any horizon T e N+ and assume that, for all t [T], the loss ft is convex, strongly-convex with arg min fe(x) E θ (referred to as the strongly-convex (SC) case).
Then, for the general convex case, Algorithm 4 with epoch size L = (dT) attains all the regret bounds from Corollary 1 plus an additional term of d d3T', For the SC case, Algorithm with epoch size L = d satisfies all the regret bounds from Corollary plus an additional term of d dvT. Both results omitted polylogarithmic factors.
'We adopt clipping (by 7) following [27, 59), though = 0 suffices discussed in [77] and [9, Section 11.6].
34

---

end for Algorithm 4 TEWA equipped with Bandit-over-Bande (BoB)
Input: d,T, [T/L], (L)) {2' : 0.1. 1...., [log2 T|}. and y E (0, 1) as defined
in (73)
Initialize: $0, = E [|]|]
1: for e ... E' do
2:
Compute Pe,i according (73) Vi E [|6]]
3: Sample i, with probability Peçi and select B, 2 E
4: for /. E le do
5: Run TEWA-SE with B B, to select action 2; and observe losses yr f((21) &
6: end for
7: Update Se+1.i according to (74) Vi [[]]]
8:
Proof of Corollary 3. For brevity, we suppress terms that are polylogarithmic in 7 using S in this proof. For all B E B, have
Rdyn (T)
E
f((zi) min f((z)) zee
1=1
E f((z)) - fo (z((B))) | + Σd
fi (z.(Bt))
min f((=)) ZEO
E
E
Σ
Σ
fe (z, (z)(B)))
+ Σ
Σ
E
fi (ze(Bt))
min f((z) zee
== tET.
e= TE
11
(76)
where 2, (B,) represents the actual action taken by TEWA-SE in round of epoch e, and z; (Bi)
denotes the hypothetical action that TEWA-SE would have chosen had its B parameter been set to B Term in (76) can be bounded by applying the classical analysis of EXP3 from [59, Corollary 3.2],
combined with (28), follows
YBI B: term I Ive B log B E
[[Q]
SVE -PBA-P(AT))BB
Q Ar| + P(A7)E A+)
x VVT.T. (LM, 7 L) VTL.
(77)
To bound term II, we introduce shorthand F T) to refer to the upper bound on Rada((B, T) in Theorem and (T, S), pdyn (T, A, and peath (T, P) refer to the upper bounds RSwi (S), Rdyn (T, A, S) and Reath (T, P) in Corollary for known S, A and P. We also use S. 11=1EEEE 1(s * f(-1). ). By choosing Bt 2 the analysis with it = loog _ [log, LJ. term II can be bounded in terms of the number of switches S by
term II <
(
L Bt
+ Se) Rada BB,L)= s gt + 15++B ()++) Rada (Bt, L)
e=1
swi (T, + pada L.)
(78)
Combining (77) and (78), we obtain
Rowi (T, S) 1 (T F (rada(L,1) (L, VTL
(dTT + d dèT + ddT
F
(T,S+
(79)
(SC),
where we used (dT) for the general convex case, and L = dVT for the strongly-conver case. Following similar steps, by choosing B 2 in the analysis with at (logg T v [log(BB))]) A
35

---

(log2 I.] where 3 var & for the general convex case or B -7))
for the strongly-convex
case, obtain
d d Raym (T, A. & (T, + d + dvT
(80)
(SC).
The bound on Roath (T, P) can be established analogously.
D Proofs of lower bounds
We call x {= randomized procedure if 2, #,((2x)<=11 {=
where & are Borel functions, and 21 Rd is deterministic. We emphasize that, throughout this section, we assume the noise variables {5t Ve= are independent with cumulative distribution function F satisfying the condition
/ |log (dF dF (FF(F))))) (u) dF (u +)) dF(u) loo2,
|u| < vo
(8
for some 0 Lu 00,0 < to I 00. This condition holds, for instance. F has a sufficiently smooth density with finite Fisher information. In the special case where F' is Gaussian, the inequality (81) holds with vo = oo. Note that Gaussian noise also satisfies our sub-Gaussian noise assumption in Section 1, which is used in the proof of the upper bounds.
We first restate and prove Theorem 2, which establishes lower bound Royn (T, S), and then present and prove Theorem 4, which establishes lower bound on 1ppath P).
Theorem 2. Let Q Bd_ For functions. Let π = {z1]T=1 be any randomized algorithm (see Appendix D for a definition). Then there exists To > 0 such that for all T 2 To holds that
O denote by Fa the class of a-strongly conver and smooth
sup fTE.
Royn (T. S, 2a c1
(16)
where > 0 is constant independent of d, T, and A.
Proof of Theorem 2. Let no + R be an infinitely many times differentiable function that satisfies
if | S 1/4, if 1/4 < |<| 1,
(x)
E 1)
if |c|| > 1.
Denote by Ω2 1- the set of binary sequences of length d, and let 77(x) f" nu(u) du. Consider the set of functions fw Rd + R with w = (wi,..., wa) E 1], such that:
fa(x) = a ||0||² + th
Σ win
Li is to be assigned later. Let L'
x = (fI...,
(82)
h
where h min d (5)
) and
max.eR (n"((:) (x:) |. By [78, Lemma 10] have that if < min (1/2n(1), then for Fo. Moreover, if S a/2, the equation fa (x) = has the solution
hws for 1 1sisd
xx (w) (w)) with x;(w)
(83)
2a
This is the unique minimizer of fw and belongs to ar (w) E Bd because
2 1
(w))
4a
16'
We consider the following adversarial protocol. At the beginning of the game, the adversary selects No min(S, (T)) points from Q, sampled uniformly at random with replacement. Here
36

---

without loss of generality we assumed that (TA3)3 á is a positive integer. Denote these points by (w))km N. and then for each k = 1,2,.... No. let
f(K
JNT/N. = Swn.
For any w.w' E EQ let p(w, w²) = E (w; + wi) be the Hamming distance between w and w', with ws (Wiy...,uid) Wa) and w' = (w/, (w/,...,uk) w'd). . By construction, No S and
max
1 - sun (2)) S n(1 W
p(wa-1, wk) SA.
k=
For any fixed wi....,, WN.. E S2, and 1 s T, denote r [w) I... WN.] as the matrix whose columns are the wj's. s. Denote by Pr., the probability measure corresponding to the joint distribution of {=k, yu Hém where y/u = fx(2x) + & with independent identically distributed Ex² such that (81) holds and z&'s 's are chosen by the algorithm æ. We have
drr (2) dF (01 - (z1) II aF (ur - Jr (., T=2
= dF (y1 - fw, (z1)) II dF (yz swe, (Ør
(84)
where k, [[T [ + 1. (We omit explicit mention of the dependence of P Pr, and o on $2...., 2y-1, since 2, for т 2 2 is a Borel function of #1, 2n Vr) Let Er, denote the expectation w.r.t. Pr,--
Note that by a-strong convexity of fw and the fact that xt (w) E arg min (ar) from (83), we have
Σ Er, Swa, (z+) min Swa, (2r)
Er,
a
Er
|| - x (wxx)))
(85)
sce
2 1=1
Define the nearest-neighbour estimator
We E arg min ||
x (w)ll
WEl
Using this combined with the triangle inequality, we have ||= " (w:,) (wk))l S 1| x= x+x()) || x² (w(w),)) Together with (83) this implies that
|| x (wwx))l )| < 2
12,,
Er, || x (wk, )12
24 Er., [|x" x (wk.)))
Er. [p(we, wk.)l
= 4a²
Summing over I,..., T. then taking the maximum over I [w1]... WNN_] and then the minimum over all estimators W wr with values in Q we get
T Σ
2
max T
Er,t
||z, x (wk (w))))]]
min max
Σ
> Er, [n (ay,, # wk.
2
w Wy WrERRee ERTENA.
term 1
(86)
For term I, lower bounding the maximum with the average can write
term
> 2 dN. dNN
min
Er. [1 (Wir + wh.))]
W En
t=
TEnNo
1=1
2 2 d.o dN
Σ
min (-111
Era [1 (Wi,s # wh.)).
t=1 TEnNo
37

---

Next, for each i = i,.... d, define r. = (iwil...lwpy wi...., w. E Q, Wk, = 1}. Given any I E r let r | w. such that Wk.j wkij for any lo he, and let Wk, -1 and Wk,j = Wk.,j for j + i. Hence,
term I 2-
min o. (-111)
(Er (0r, + 1)] Er, [1 (0r, + 1)])
PENN
min rer
min
(Er [1 (Wi, # 1)] + E e [1 (We,z -1]])
d ((-11))
t=
Thus, can write
dPr. dPr.,
KL. (Pr,, Pr.,)
log
dPr,
=/ log
dF(1) (2]])1))
dF((11 (21))
dF swe, { (21:7 1. V1:7
11)) -1))
log
dF swi, (0, (2 1. 11:7 (1:7-11)
dF (y1 fws (z1)) II dF (u+ fwor (o, (Z1:--1, (1.7-1))
I Io
max [uw,, (x)) San, (x))2 S In24411)") WE
Since h S min( -
aJ )²) and by choosing
/ogo())(AVor<(I)), have
KL(Pr.I(PT..) < 12g. Hence, Theorem 2.12 of [79] gives
Td exp( - log(2)) = 8
Td
term 2 4
Substituting this into (86) and our overall bound (85) yields
2
Td
122Td
max T
Σ
Er. fwi, (zt)
min fwe, (x)
2
#eB
4a
64c
Finally, substituting the definition and noting that / independent d, T, and A completes the proof.
Theorem 4. Let θ Bd_ For a >> 0 denote by Fa the class of a-strongly convex and smooth functions. Let = {-1]T=1 be any randomized algorithm. Then there exists To such that for all T > To it holds that
Rpath (T, c2 P3
sup fr...
where > 0 is constant indepedent of d,T and P.
Proof of Theorem 4. The proof uses the same notation and follows the same steps in the proof of Theorem 2, but with different choices for the parameters h and N Define the set of functions
fw Rd + IR with w E {-1, 1 as they are defined in (82), and choose h min(d 1 P and
N.va
N. p Then have that
No Σ
h N
Volwa-1, w/) < hu VdN. <,,
| (wk-1) -x"(w))l
(87)
2
2=2
38

---

for any
Following similar steps in the proof of Theorem 2 for large enough T (when
h
P N.va
get
I sun, (z() (wi,(zi)
122
max T
Σ
Er,
min Sw., (ar) wEB
2
64a 2 2c
where > 0 is independent of d, T and P.
E Proofs for clipped Exploration by Optimization
We restate and prove Theorem which establishes an adaptive regret guarantee for cExO. In this section, we use (p, fe) Ez~p[/i(z)) where p belongs probability simplex.
Theorem 3. For T E N+ and B [T]. Algorithm 3 calibrated with #, 7 TCP
(log(>-1)/(4 log(dT')B) and log |C] = (og((TT))) satisfies
Rada B, T) S d
(19)
Proof of Theorem 3. Consider an arbitrary interval [a, bj of length b - a + s B, and notice that for any q¹ E A,
E[f((z)) f((2)] = Σ
(p q" f..
Ezagy [f((2)] min
f((u).
(88)
t=
term
term
In what follows, we choose a suitable q² and bound term and term Il separately.
Recall that the covering set C is assumed in Section 3 to have discretization error of implying
that there exists ue C such that Σi= fil fi(e) minwee Ei fi()) I =B. Define q* Å to be the distribution with probability mass given by
(1 11-7(11-1 - lr
if ue otherwise.
q't ('(z)
(89)
This construction ensures that
term II < (e + Br.C.)B.
(90)
To bound term I, we first apply Lemma to the sequence of Online Mirror Descent (OMD) updates It E Å and the sequence of loss estimates 8, to obtain
Σ (q. q¹ 3t) S (KL(""Ila.)
Σ Sq. (1(51) t=a
(91)
where by the definition of g² in (89), we have
q- (2)
KL((9)l9.) = (2))2)
(z)))
sEC
1- 11-7(1|-
(1
= (1 - --(|c| - 1)) log
Σ
y yog
(uc
(z)
#ECi(uc)
< 1))
(92)
39

---

Then applying (91) and (92), we have
b
term I =
I(qe
33) + (P. - ft) + (q" -9.311)
1=0
log(>
(pr q², ;1) + (a- 2r Ba) + Sq. (1181)
17
tma
log(>
+B
Ap P. B) + +nd PEA(C), BEE
inf
17
log(>
B (1all log(dT) + nd))
(93)
"
where (i) follows from the update rule (18) and the precision level assumed for solving the mini- mization problem (18) (see line 3 of Algorithm 3), and (ii) uses [I. Theorems 8.19 and 8.21] which establish that there exists a universal constant x such that
sup inf 1 AA, p. S kdt log(dT). q PEA(C), BEE
Finally, combining (90) and (93) we obtain
h Σ (p: - -- +
b
b
max O
E(fe(z)) - f((u)]
Σ
E Ex [f(()] ]
min Σ fe(u) uce
1=a
1=0
t=a
t=a
I (s + 2T|C log(7-1)
+ (yat log(d() + nd)
1
B
2 T
v Bdt log(T) log log(T( S d /B,
where (i) applies E = 7, TiC and n //log(>1))/C( (ogg===)) and (ii) is by selecting the covering set such that log |C| S log(1 16d72) (existence given by [1, Definition 8.12 and Exercise 8.13). 13)).
The proof of Theorem above relied on Lemma 8, which we present and prove below.
Lemma 8. Consider Online Mirror Descent (OMD) with Kl. divergence regularization and fixed learning rate > 0 applied to a sequence of loss estimates 8t E IR" for t E N++ When run over convex and complete domain À C An-1, the algorithum produces a sequence of updates q. E for t E I+. For any comparator in q² E and time interval (t. E ENEN aa : S b}, it holds that
Σ t=a
9"' 8t) S 1
KKLgq" (qa) + Sa (18i))
(g.
1)
where (1(1)) = (a (a q', .1s) (q))
Proof of Lemma 8. The proof is standard and included for completeness. Let F denote the neg- entropy F(q) = En qi log(q.) for q E n-1, and note that
kL(pllq) = F(p) (p VF(g)) F(q) Vp.qEA--1
(94)
Consider the update rule of the OMD defined in the lemma:
91+1 = arg min (g, n,:) + KL(gllq.) = arg min ns, + F(q)) qVF(q)),
qeá
which implies by the first order optimality condition [9, Proposition 26.14] that, for any q" E and time t,
(q 9e+1 1788 1741,778771 + (F(q..)) VF(q.)) 20.
(95)
40

---

Rearranging (95) and applying (94) we obtain
(9141 - --"
" {q- 4et1, VF(q(+1) VFF())))
= (KI((9"19..) - -KL(9919(+1) Kl((g+illa.)
S - (g. 1.-1: 0t) Sq. (181) 1 (KL(g") g:) -KL(0)ll(44)) (96)
1
1)
Rearranging (96) and summing over t E [a, b] yields
Σ t=
qg q' 81)
(( q' (8) + (q. 9441, 81)
t=a
(KL(g"lla.) KL + Sq. (ns²)
b
KL((")lqu)) KL(q"ll9641) + Σ Sq. (1s))
t=o
which combined with non-negativity of the KL divergence completes the proof.
Finally, we apply Theorem 3 to prove the bounds on R (), Royn (T, A, S) and Rpath (T, P) in Corollary as well as the parameter-free guarantees in Corollary
Corollary 2. For any horizon T E NNt, Algorithm 3 calibrated in Theorem 3 and luned with interval size B (which determines 11) satisfies the following regret guarantees:
Switching:
B JT R (T, d ST.
Dynamic:
B 3 V (d = Rd (T, A, S R (T, A)
Path-length:
( P)P) = Roath (T, P) d
We prove these results by applying the adaptive regret guarantee from Theo- rem 3 and the conversions results from Proposition 1, similarly the proof Corollary 1.
Proof of Corollary 2.
Corollary 4 (cExO with BoB). Let T N+ By partitioning the time horizon [T] into epochs of length d VT, and employing Bundit-over-Bant Bandit to select cExO's parumeter for each epoch from the set B = (2 i = 0, (log2 T}}, this algorithm achieves all regret bounds in Corollary with an additional term of d T (up polylogarithnic factors).
Proof of Corollary 4. The proof is similar to that of Corollary and is therefore omitted.
41


Reviews:
[{"review_id": "6zBd2dq7QG", "reviewer": "Reviewer_5yot", "summary": "This paper studies minimizing dynamic regret for online bandit convex optimization. The authors provide new algorithms that can solve both convex and strongly convex functions, without knowing the strong convexity parameter. The regret bound for strongly convex functions is minimax optimal, whereas the regret for convex functions is suboptimal. The authors also provide an inefficient algorithm that has a better dependence on T, the total number of iterations.", "questions": "The questions are given above.", "limitations": "Yes. Please see the above section for more discussion.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n---\n\nSignificance of the results: \n\nThis paper provides new and improved results for non-stationary bandit convex optimization: \n\nFor minimizing dynamic regret in the BCO setting, previous work mainly focuses on the setting for general convex functions and path-length regret, while this paper provides new results for strongly convex functions, and also regret with respect to other competitor-dependent terms, such as S, Delta. \n\n\nThe authors apply the Metagrad-style techniques to deal with strongly convex problems, and the main advantage is that the algorithm does not need to know the strong convexity parameter. This is also new to the non-stationary BCO setting. Moreover, the basic algorithm requires the exact value of P, Delta, and S as input, while the authors extend their algorithm with the BoB framework to deal with the setting where such parameters are unknown. \n\n\nFinally, the authors also provide a highly inefficient algorithm, but with improved regret bounds with respect to T, even with out the assumption of strong convexity. \n\n\nPresentation: \n\nThe paper is in general well-written and easy to follow. \n\n\nWeakness:\n---\nMy main concern is about the novelty of the algorithm and the connection to previous works. Specifically:\n\nThe proposed method in Algorithm 1 seems to be exactly exactly the algorithm in [23] for strongly convex functions, with OGD as the expert algorithm, the same surrogate loss function given in (11), and replacing the true gradient g_t with estimated gradient with one-point estimation, whose variance and bias is well studied in the bandit literature. It seems that the main thing one needs to do is to plug in the extra error term introduced by the one-point gradient estimation into the original proof given in [23] or the Metagrad algorithm [21]. Are there any extra significant challenges in the proof preventing us from doing so?\n\nOther limitations:\n\n\nThe proposed TEWA-SE can deal with both general convex and strongly convex functions. However, the bound for general convex functions is sub-optimal as the dependence on T gets worse. \n\n\nThe cExO algorithm given in Section 3, which follows the algorithm given in [1], requires running exponential on the entire (discretized) decision space, which is already highly inefficient. Moreover, it requires solving the intractable problem in (18). Finally, it suffers a worse dependence on d.", "was_revised": true, "final_justification": "I have read the rebuttal as well as the other reviews. Overall, I believe this is a solid paper that makes valuable contributions to the BCO area. After discussing with the authors, the techniques also appear novel to me. I would like to maintain my score.", "rebuttal": "### **1. Response to remarks on novelty of TEWA-SE and connections to prior work**\n\n Thank you for this comment. \n\n**TEWA-SE:**\nIndeed, our proposed TEWA-SE algorithm represents rigorous adaptations of established techniques, as detailed in lines 115-127. We adapt sleeping experts and MetaGrad-type adaptivity techniques from Online Convex Optimization [21-23] to the bandit setting. Key modifications include replacing exact gradients with one-point bandit gradient estimates, and designing a quadratic surrogate function. These adaptations require non-trivial technical work, including careful bias-variance trade-offs and detailed analysis of tilted exponentially weighted averaging with noisy gradient estimates. \n\nTo further clarify how TEWA-SE differs from its precursor [23], we would like to emphasize that our surrogate loss design differs from both [23] and the original MetaGrad paper [21]. We will describe this more explicitly in the revised manuscript. While [23] and [21] use $ \\eta^2||\\boldsymbol{g}_t||^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ and $\\eta^2(\\boldsymbol{g}_t^\\top(\\boldsymbol{x}_t-\\boldsymbol{x}))^2$ as the quadratic term for the surrogate loss, we use $\\eta^2G^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ in our   surrogate loss $\\ell_t^\\eta(\\boldsymbol{x})=-\\eta\\boldsymbol{g}_t^\\top(\\boldsymbol{x}_t-\\boldsymbol{x})+\\eta^2G^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ in (11), where $G$ is a high probability upper bound on $||\\boldsymbol{g}_t||$, as shown in (10).\n\nThe surrogate loss from [23] or [21] necessitates an additional condition relating $\\mathbb{E}[||\\boldsymbol{g}_t\\|]$ and $\\mathbb{E}[||\\boldsymbol{g}_t||^2]$ (or $\\mathbb{E}[\\boldsymbol{g}_t\\boldsymbol{g}_t^\\top]$) to be satisfied in the analysis, see e.g., [21, Theorem 2]. When working with tilted exponentially weighted average with noisy gradient estimates, directly using their quadratic term would complicate the proof. Our choice of the quadratic term, inspired by [22], simplifies this particular aspect of the proof.\n\n**Broader connections to prior work:**\nAttaining optimal performance for general non-stationary Convex Bandit Optimization is hard, and the field currently lacks a comprehensive, unified treatment. Existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $R^{\\text{dyn}}(T, \\Delta)$, while [13, 33] address path-length regret $R^{\\text{path}}(T, P).$ As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive parameter-free guarantees by applying the Bandit-over-Bandit framework, which offer baselines for future research on this topic. \n\nFurthermore, to clarify how our work compares with prior work, we would like to emphasize the following points:\n- The reduction from $R^{\\text{path}}(T, P)$ to $R^{\\text{swi}}(T, S)$ in Proposition 1 is new and employs simple geometric arguments (see Lemma 2 and its proof from line 863). To better position our work relative to existing work, we will add a remark discussing this reduction technique and referencing [17], noting that while our unified approach through $R^{\\text{swi}}(T, S)$ simplifies the analysis of $R^{\\text{path}}(T, P)$, it may yield slightly looser bounds on $R^{\\text{path}}(T, P)$ compared to direct analysis.\n- To our knowledge, the $d^{\\frac{4}{5}}P^{\\frac{2}{5}}T^{\\frac{3}{5}}$ lower bound for path-length regret in Theorem 4 is new  and improves upon the only existing result, the $d\\sqrt{PT}$ lower bound from [13, Theorem 5], w.r.t. $T$. This is attained by leveraging a different construction of a hard instance of loss functions.\n\n### **2. Response to remark on limitations of cExO** \n\nThe cExO algorithm builds on a long line of work, as detailed in lines 128-135 of our manuscript. Specifically, it adapts the exploration by optimization approach from [27] by adding a novel clipping step. Though not polynomial-time computable, cExO achieves the first minimax-optimal result for switching regret and dynamic regret w.r.t. $T, S$ and $\\Delta$. Moreover, obtaining optimal regret guarantees in non-stationary environments is inherently more challenging than in the static setting. The suboptimal dependence on $d$ in our upper bound is unsurprising since even the best known static regret bounds of Fokkema et al. (2024) and Suggala et al. (2024) suffer from similar dimensional dependence.\n\n**References:**\n- Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In *Conference on Learning Theory*, pages 1713–1714. PMLR, 2024.\n- Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In *Conference on Learning Theory*, pages 4691–4763. PMLR, 2024.\n- (Numbered references above correspond to the bibliography in the submitted manuscript.)"}, {"review_id": "kaCnAMyaCu", "reviewer": "Reviewer_TTmz", "summary": "The authors study the nonstationary convex bandit setting. They work with a “total variation” notion of non-stationarity and two forms of adaptive comparators.\n\nThey focus on several notions of regret for this nonstationary setting and different assumptions on environment parameter knowledge, ultimately proposing two different algorithms with a range of different theoretical properties.\n\nTheir first contribution is a polynomial-time algorithm based off of the sleeping experts framework that achieves $\\mathcal{O}(\\sqrt{d}B^{3/4})$ adaptive regret for general convex losses (where $B$ is the length of an interval of time), $\\mathcal{O}(\\sqrt{d} S^{1/4}T^{3/4})$ switching regret. They also show that if the losses are strongly convex, an if $\\Delta$ is known, their algorithm achieves a dynamic regret of $\\mathcal{O}(\\min\\\\{ d\\sqrt{ST}, d^{2/3}\\Delta^{1/3} T^{2/3}\\\\})$. This last bound is shown to be minimax optimal by providing a matching lower bound. \n\nTo overcome the requirement of knowing $S$, $\\Delta$ and $P$, the authors use a Bandit over Bandit framework.\n\nFor general convex losses with known $S$, $\\Delta$ and $P$, their algorithm is suboptimal, so they provide another algorithm with improved guarantees by using discretized action space. However, this algorithm is not polynomial-time computable.", "questions": "I think it would have been beneficial for the reader if the authors had picked, e.g. a single notion of regret and setting and written a more in-depth version of that in the main paper with more space dedicated to providing intuition to the reader. The other variants could be provided in the appendix. To be clear, I am not suggesting that the authors' work itself is of poor quality; rather, I think the organisation of the contributions could be arranged more helpfully. It currently reads like a full ablation was done over the range of scenarios, and all results are being included in large paragraphs, one chunk at a time. This makes for very dense passages with lots of internal context switching.", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "*Strengths:*\n\n- Comprehensive treatment of the non-stationary online convex bandit setting\n- Extensive regret analysis with many considerations for different assumptions\n- Extensive discussion of limitations of their contributions\n- Clear progress from the first algorithm to the second algorithm to address shortcomings\n\n*Weaknesses:*\n\n- In general I did not find this paper to be pleasant to read, there were so many juggling defintions of regret, so many settings (e.g. general convex, strongly convex), and so many different assumptions on knowledge (e.g. $\\Delta$ known and incorpated into tuning vs not) as well as two very different proposed algorithms that it was very challenging to construct a coherent picture of the full scope of contributions. It read like a summarized thesis instead of a focused study.", "was_revised": true, "final_justification": "I think this paper is technically solid if poorly organised. I recommend acceptance, though I am not deeply familiar with the line of work the authors focus on.", "rebuttal": "### **Response to remarks on organization and presentation**\n\nThank you for your constructive feedback. We aimed to provide a comprehensive study because the field currently lacks a unfied treatment of non-stationary Convex Bandit Optimization. However, we agree that the presentation could be made more accessible.\n\nAs we note in lines 105-114, existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $ R^{\\text{dyn}}(T, \\Delta)$, while [13, 33] address path-length regret $R^{\\text{path}}(T, P)$. As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive parameter-free guarantees.\n\nIn the revision, we will emphasize in the \"Introduction\" section before Section 1.1 that adaptive regret $R^{\\text{ada}}(\\textsf{B}, T)$ and switching regret $R^{\\text{swi}}(T, S)$ are the primary focus of this work, and that dynamic regret and path-length regret can be bounded using $R^{\\text{ada}}(\\textsf{B}, T)$ and $R^{\\text{swi}}(T, S)$. We will expand our discussion of Fig. 1 which visually clarifies the conversions between different regret notions. We will also expand Section 1.3 where we formally present the conversion results (Proposition 1) to provide clearer intuition before diving into technical details.\n\n**References:** Numbered references above correspond to the bibliography in the submitted manuscript."}, {"review_id": "7UzN6iSnZJ", "reviewer": "Reviewer_m61f", "summary": "The paper deals with the setting of Bandit Convex Optimisation (BCO) [1], whereby a learner is tasked with optimising over a sequence of functions $ f_{1},\\dots,f_{T} $, which may very adversarially, given only noisy point-wise zero-order evaluations. Namely, given an action played at time $t\\in[T]$, the action $x_{t} \\in \\Theta \\subset \\mathbb{R}^{d}$ ( $\\Theta$ being convex) incurs the loss $f_{t}(x_{t})$, but only the random variable $y_{t}=f_{t}(x_{t})+\\zeta_{t}$, whose expectation coincides with the true feedback, is available to the learner. Coinciding with recent interest in this problem, the present work studies the case where, in place of the usual notion of regret ($R_{T}=\\min_{x\\in \\Theta}\\left[\\sum_{t=1}^{T}f_{t}(x_{t})-f_{t}(x)\\right]$), several non-stationary variants are considered. These non-stationary variants constitute forms of the dynamic or path regret under constraints which render the problem tractable.\n\nThe authors provide an algorithm, TEWA-SE, based on MetaGrad [2] and its adaptation due to Zhang et al. [3], which efficiently attains the minimax rate in two of three cases for strongly convex functions, but is suboptimal in all cases for general convex losses. Also provided is an inefficient algorithm, cExO, which is based on the Exploration by Optimisation framework due to Lattimore & Gyorgi [4], and attains minimax rates in two out of three cases for general convex losses. Their results are extended to unknown non-stationary measures using the Bandit-over-bandit framework.\n\nTo verify optimality of the cases where $f_{t}$ is $\\alpha$-strongly-convex (i.e. $f_t \\in$ $\\mathcal{F}^\\alpha$ ) for all $ t \\in [T] $, the authors have provided several new lower bounds on the dynamic and path regret using similar techniques to [5]. Namely, by way of constructing a sequence of hard functions within the class $\\mathcal{F}^{\\alpha}$. \n\n[1] Bandit convex optimisation.Tor Lattimore. arXiv:2402.06535, 2024.\n\n[2] Metagrad: Adaptation using multiple learning rates in online learning. Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. Journal of Machine Learning Research, 22(161): 1–61, 2021.\n\n[3] Dual adaptivity: a universal algorithm for minimizing the adaptive regret of convex functions. Lijun Zhang, Guanghui Wang, Wei-Wei Tu, Wei Jiang, and Zhi-Hua Zhou. In Proceedings of the 35th International Conference on Neural Information Processing Systems. Curran Associates Inc., 2021.\n\n[4] Mirror descent and the information ratio. Tor Lattimore and Andras Gyorgy. In Conference on Learning Theory, pages 2965–2992. PMLR, 2021.\n\n[5] Exploiting higher order smoothness in derivative-free optimization and continuous bandits. Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Advances in Neural Information Processing Systems, 33:9017–9027, 2020.", "questions": "1. I would be very curious to know if the authors believe that the slack in the path-length dependent regret is on the algorithmic side, or that some slack is introduced in the additional bound in Theorem 4. I would expect the exploration-by-optimization framework to afford the minimax result, but I cannot quite see where there would be slack in the lower bound.\n\n2. I am curious whether or not one can expect similar performance achieved by cExO from a similar adaptation of MetaGrad, as the key difference seems to be the inclusion of properly estimated second-order information. MetaGrad relies on gradient outer products to adapt, but the current work relies on a course gradient bound based on variation of the loss estimates). This second-order information which can be estimated using single-point feedback with the convolution-based estimator proposed in [1] (and has found recent use in the works [2,3,4]), so I'm curious whether or not the authors suspect that the quadratic surrogate of this estimator would be sufficient to achieve a better rate.\n\n3. Would the authors suspect that second-order methods might be adaptable to the case of dynamic & path-dependent regret, as those based on variants of FTRL should already have something of a tracking property. This question may indicate a limitation in my own understanding of the degree of adaptation needed to furnish rates for the dynamic & path-dependent regret.\n\n[1] Kernel-based methods for bandit convex optimization. Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. 2017. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). Association for Computing Machinery, New York, NY, USA, 72–85. https://doi.org/10.1145/3055399.3055403\n\n[3] Improved Regret for Zeroth-Order Stochastic Convex Bandits. Tor Lattimore, Andras Gyorgy Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2938-2964, 2021.\n\n[2] A Second-Order Method for Stochastic Bandit Convex Optimisation. Tor Lattimore, András György Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2067-2094, 2023.\n\n[4] Online newton method for bandit convex optimisation. Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1713–1714. PMLR, 2024.", "limitations": "In general yes. A minor comment would be that in line 108 - “and further developed in subsequent studies such as [28–32]. ” - there are a few relatively recent references missing; I realise that this comment is not meant as exhaustive, but the two papers by Suggula and co. (see below) are a relatively important part of the story. Particularly the latter, which coincided historically with the results of Fokkema et al., and constitute state-of-art rates for a class of $\\kappa$-convex functions (basically just functions with well-conditioned hessians).\n\nHere are the references:\n\nEfficient Bandit Convex Optimization: Beyond Linear Losses; Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4008-4067, 2021.\n\nSecond Order Methods for Bandit Optimization and Control; Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, Elad Hazan Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4691-4763, 2024.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The work does indeed provide a comprehensive study of non-stationary BCO, and closes several conspicuous gaps in the literature with new (close to) minimax optimal bounds. These constitute a set of results and ideas of significant interest to the community.\n- The nuanced lower bounds illustrating clearly the (near) optimality of the results close some slack in previous results.\n- The motivation and intuition behind algorithmic choices are extremely clear, and open up several new avenues for development and follow-up.\n- The paper is well written, contributions are clearly delineated, and the overall structure serves as a template for what such a broad study of such a problem setting should entail.\n- The proofs are easy enough to follow at a high level, are firmly grounded in existing analyses, and thus I have very little doubt as to their correctness.\n\nWeaknesses:\n- Although the results themselves constitute new and interesting points on the pareto frontier of possibilities in dynamic environments, I have had a hard time finding algorithmic ideas which weren't already derived elsewhere.\n- It’s somewhat low hanging fruit (and a rather minor weakness) to say that the results are comprehensive, but not quite complete, as there still remain questions on the achievability of some of the results of cExO constructively (or rather, with an efficient algorithm). \n- In complement to the above, some of the state-of-art techniques in bandit convex optimisation haven’t been discussed substantively, or alluded to in what might be an appropriate context, and it strikes me that some of these techniques might have afforded a more efficient approach than the cExO algorithm. Or at least it would be instructive to know why these techniques weren't alluded to when developing the cExO algorithm. Nevertheless, I see this weakness as very minor.", "was_revised": true, "final_justification": "The authors have addressed my questions and those of the other reviewers, transparently delineating their contributions, degree of novelty, and have provided clear motivation for the approach. Overall, I believe this work constitutes a solid theoretical contribution, with several new results closing or partially closing gaps in the BCO literature. A downside of the work is the degree of novelty of the algorithms themselves, which inherit much of there structure from existing works, particularly MetaGrad and ExO [2], including the computational burden of the latter. Consequently, it is difficult to justify a higher score than 5. Nevertheless, this work represents an important stepping stone towards more flexible and efficient algorithms for this setting, and I believe that the insights gained through its development will be of interest to the community.\n\n[1] Metagrad: Adaptation using multiple learning rates in online learning. Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. Journal of Machine Learning Research, 22(161): 1–61, 2021.\n[2] Mirror descent and the information ratio. Tor Lattimore and Andras Gyorgy. In Conference on Learning Theory, pages 2965–2992. PMLR, 2021.", "rebuttal": "### **1. Reasons for slack between upper and lower bounds for path-length regret for cExO**\n\nThank you for this insightful comment. As far as we can see, there are three potential sources of slack between our upper and lower bounds for cExO: **(i)** our lower bound construction in Theorem 4 may not be tight, **(ii)** the cExO algorithm design itself may be suboptimal, or **(iii)** our upper bound analysis may have introduced looseness through the reduction result in Proposition 1, which bounds path-length regret $R^{\\text{path}}(T, P)$ through switching regret $R^{\\text{swi}}(T, S)$. We examine each in turn:\n- **(i)** Though our $d^{\\frac{4}{5}}P^{\\frac{2}{5}}T^{\\frac{3}{5}}$ lower bound shows better $T$-dependence than the $d\\sqrt{PT}$ from [13, Theorem 5] (the only other result in the literature), we are unsure about the true minimax rate. While we also don't see slack in the lower bound, a $T^\\frac{3}{5}$ rate is uncommon and we wouldn't be surprised if the cExO upper bound is tight.\n- **(ii)** Alternatively, a potential source of sub-optimality in cExO stems from the fact that cExO performs OMD over the distribution space rather than directly over the action set. The latter would allow us to derive path-length regret bounds more directly.\n- **(iii)** Our Proposition 1 unifies the regret analysis by bounding  $R^{\\text{path}}(T, P)$ and $R^{\\text{dyn}}(T, \\Delta)$ through $R^{\\text{swi}}(T, S)$. However, this simple approach may yield slightly looser bounds for $R^{\\text{path}}(T, P)$ compared to direct analysis, as noted in [17].\n\nWe will include a brief discussion on the above in the revised manuscript.\n\n### **2. MetaGrad combined with convolution-based estimator from Bubeck et al. (2017)**\n\nThank you for this thoughtful suggestion. As you note, MetaGrad is a first-order algorithm, where the quadratic term $\\eta^2(\\boldsymbol{g}_t^\\top(\\boldsymbol{x}_t-\\boldsymbol{x}))^2$ in the surrogate loss uses only a simple outer product of the gradient estimate $\\boldsymbol{g}_t\\in\\mathbb{R}^d$. Our TEWA-SE adaptation of MetaGrad inherits this first-order property, which is likely the reason why it achieves optimal rates for strongly-convex functions, but cannot attain optimality for general convex functions without incorporating second-order information. We will add a brief discussion on this before the \"Conclusion\" section in the revised manuscript. \n\nThe kernel-based (or convolution-based) estimator from Bubeck et al. (2017) offers a promising approach to address this limitation. It adaptively exploits second-order structure through the covariance of the current exponential weights distribution, essentially capturing the geometry of where the algorithm currently believes the optimum lies. Replacing the simple gradient outer product with this adaptive kernel-based estimator as the quadratic term in TEWA-SE's surrogate loss could in theory improve our regret bounds. However, implementing this integration would require careful analysis of how the kernel-based estimates interact with TEWA-SE's sleeping experts framework. This is an interesting direction for future work.\n\nMore broadly, your suggestion of leveraging second-order methods is very promising. Given that the online Newton methods from Fokkema et al. (2024) and Suggala et al. (2024) provide the state-of-the-art static regret for adversarial convex bandits, a natural future direction is to extend such methods to non-stationary environments.\n\n### **3. Second-order methods and tracking capabilities**\n\nThank you for this insightful question. In a setting similar to ours, we are not aware of any existing work that uses second-order methods to track changes in the environment for the purpose of minimizing switching, dynamic, or path-length regret. We would be grateful if you could point us to any such work. Nevertheless, a promising direction could be to incorporate a restart criterion, similar to the one used in line 15 of Algorithm 1 in Suggala et al. (2021), or line 11 of Algorithm 1 in Fokkema et al. (2024), which may enable tracking capabilities and potentially yield improved regret guarantees.\n\n### **4. Response to remark on missing references**\n\nThank you for pointing out two missing references in Bandit Convex Optimization (BCO). We will include both papers at line 108 in the revised manuscript. \n\nIndeed, Suggala et al. (2024) appeared concurrently with Fokkema et al. (2024) and presents an online Newton step algorithm that achieves optimal $\\sqrt{T}$ static regret for a class of convex functions with well-conditioned Hessians. Both Suggala et al. (2024) and Fokkema et al. (2024) build upon the bandit version of the online Newton step for stochastic unconstrained BCO from Lattimore and György (2023), which we will also reference at line 108. Finally, the restart condition in Fokkema et al. (2024) is derived from Suggala et al. (2021), making the latter a key reference for understanding the historical connections.\n\n**References:**\n- Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing*, pages 72–85, 2017.\n- Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In *Conference on Learning Theory*, pages 1713–1714. PMLR, 2024.\n- Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In *Conference on Learning Theory*, pages 4691–4763. PMLR, 2024.\n- Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In *Conference on Learning Theory*, pages 2067–2094. PMLR, 2023.\n- Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In *Conference on Learning Theory*, pages 4008–4067. PMLR, 2021.\n- (Numbered references above correspond to the bibliography in the submitted manuscript.)"}, {"review_id": "8Boxpp97ax", "reviewer": "Reviewer_NBQt", "summary": "This paper addresses the problem of adversarial convex bandits in a nonstationary setting. While nonstationary online convex optimization (OCO) and finite-armed bandits have been extensively studied, the bandit framework with a continuous action space remains underexplored.\n\nThe authors consider four notions of regret to measure nonstationarity: adaptive, switching, dynamic, and path-length regret. They first show that dynamic regret implies bounds for all the other notions. Consequently, the paper focuses primarily on dynamic regret, with results for the other measures derived as corollaries.\n\nThe authors then introduce the TEWA-SE algorithm, inspired by MetaGrad, which combines sleeping experts that rely on gradient estimations. While many of these techniques are standard in nonstationary online learning, the key novel idea lies in the design of a strongly convex surrogate loss, which allows all experts to share the same gradient estimator. This design enables the combination of expert predictions rather than bandit algorithm outputs. Assuming knowledge of the nonstationarity measure, the algorithm achieves an adaptive regret bound that is optimal (up to logarithmic factors) for strongly convex losses, and yields optimal or improved regret bounds for the various notions of nonstationarity.\n\nHowever, this algorithm has two drawbacks: (1) it is suboptimal for general convex losses, and (2) it requires prior knowledge of the nonstationarity measure.\n\nTo address the first issue, the authors propose a second algorithm, based on a discretized and clipped version of exponential weights. While this algorithm is not computationally tractable, it achieves optimal adaptive regret bounds for general convex losses.\n\nAdaptivity to the nonstationarity measure in both algorithms is obtained via a Bandit-over-Bandit technique. However, this comes at the cost of deteriorated regret guarantees.", "questions": "Remarks:\n\n1. What is the optimal dependence on the strong convexity parameter $\\alpha$? Would it be possible to derive a lower bound that shows an explicit dependence on $\\alpha$, or is it possible that no such dependence appears in the optimal rate?\n\n2. For smooth convex functions, could a better regret rate be achieved by optimizing $h$ differently in equation (34)? At first glance, choosing $h$ of order $B^{-1/6}$ appears to yield an adaptive regret of order $B^{2/3}$ instead of $B^{3/4}$. This would align with existing results in bandit convex optimization.\n\n3. If I understand correctly, the only parameter that requires prior knowledge of the nonstationarity is $h$ in Algorithm 1. What regret bound do you obtain if $h$ is selected without knowing $B$ (e.g., by using a fixed schedule or data-driven tuning)?\nMore precisely, by choosing $h = T^{-1/6}$ in (34), independent of $B$, one could obtain an adaptive regret bound of order $B^{1/2} T^{1/6}$, thus removing the need for prior knowledge of the smoothness.\nSimilarly, if we avoid optimizing $h$ and instead analyze path-length regret, we might obtain (though I may have made some errors) a bound of the form $T h^2 + P^{1/3} T^{2/3} h^{-1/3}$. Optimizing $h$ independently of $P$ would then yield a path-length regret of order $P^{1/3} T^{5/7}$.\nHow does this simpler tuning strategy compare to your Bandit-over-Bandit (BoB) approach? At first glance, it seems to improve performance when $P$ is small and $B$ is large. A discussion comparing these approaches—both in the convex and strongly convex settings—would be valuable.\n\n4. The paper states that TEWA-SE is polynomial-time, but as far as I can tell, the per-round computational complexity is $O(\\log(T)^2)$, correct?\n\n\nMinor remark:\n\nThe notation $B^d$ for the unit ball and $B$ for the nonstationarity measure may be confusing. It might help to disambiguate these symbols.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is clearly written and addresses an important problem. The authors provide several new regret upper bounds that either improve upon or match the optimal rates in nonstationary bandit convex optimization. These results take into account various notions of nonstationarity, both strongly convex and convex losses, and adaptivity to different parameters (e.g., nonstationarity and strong convexity). Overall, I believe this work makes a significant contribution to the field.\n\nWeaknesses:\n\n1. The technical novelty is limited. Most results are derived by combining well-established techniques—such as sleeping experts, MetaGrad, gradient estimation, and Bandit-over-Bandit methods—and the analysis largely follows from known arguments. That said, this should not diminish the value of the contributions: leveraging known tools in a clean, effective way is itself valuable, and simplicity in analysis can be a strength.\n\n2. The algorithm that achieves optimal rates for convex losses is not computationally tractable. However, this limitation is inherent to the problem, which remains challenging even in the static setting.\n\n3. Optimal regret rates are achieved only when the nonstationarity measure is known in advance.", "was_revised": true, "final_justification": "I read other reviews and rebuttal. The authors address well my most of my concerns. Some weaknesses are yet remaining (known nonstationary measure or non efficient algorithms in some settings). I lean toward acceptance and maintain my score.", "rebuttal": "### **1. Optimal dependence on strong-convexity parameter $\\alpha$**\n\nThank you for this insightful question. To the best of our knowledge, the optimal dependence on the strong convexity parameter $\\alpha$ remains an open question with some intriguing gaps between upper and lower bounds.\n \nFor static regret in adversarial Bandit Convex Optimization, the two tightest lower bounds we are aware of are [68, Theorem 7] by Shamir, which gives a $d\\sqrt{T}$ lower bound with no dependence on $\\alpha$, and [67, Theorem 6.1] by Akhavan et al. (with Hölder exponent equals 2), which implies a lower bound on the order of $d\\sqrt{T}/\\max(\\alpha,1)$.   \n- For $\\alpha\\lesssim 1$, the latter reduces to $d\\sqrt{T}$ independent of $\\alpha$, while existing upper bounds from [32, 69] achieve $d\\sqrt{T}/\\sqrt{\\alpha}$. This suggests that the $1/\\alpha$ dependence in our adaptive regret upper bound (15) in Theorem 1 is likely suboptimal.\n- For $\\alpha\\gtrsim 1$, our $d\\sqrt{\\textsf{B}}/\\alpha$ adaptive regret upper bound in (15) appears to match the $d\\sqrt{T}/\\alpha$ lower bound from [67]. However, this comparison is not definitive because both results suppress dependence on the smoothness parameter, which could affect the true relationship between these bounds.\n\nTo improve clarity, we will update the sentence starting on line 214 to read: \"We further note that our bound for the strongly-convex case has a $\\tfrac{1}{\\alpha}$ dependency, which is suboptimal compared to the $ \\frac{1}{\\sqrt{\\alpha}}$ dependency in [32, 69] for static regret in BCO for $\\alpha\\lesssim 1$.\"\n\n### **2. Adaptive regret of $\\mathcal{O}(\\textsf{B}^{\\frac{2}{3}})$ via alternative choice of $h$ in (34) for convex and smooth functions**\n\nThank you for this important comment. We appreciate the opportunity to clarify the assumptions and scope of our results. Our results for TEWA-SE address two cases: (i) general convex and Lipschitz functions, and (ii) the special case of strongly-convex  and smooth functions. Importantly, the presented results for the convex case do *not* exploit smoothness assumptions. We will clarify this in the main text of the revised manuscript, rather than relegating it to footnote 1 on p.3.\n\n**Convex and Lipschitz functions:** For this setting, $\\sqrt{d}T^{\\frac{3}{4}}$ is a classical static regret rate in bandit optimization, see e.g., [24, Theorem 3.3]. Since our TEWA-SE algorithm employs the one-point gradient estimate from [24], our adaptive regret upper bound in (34) naturally inherits a leading term of order $\\sqrt{d}\\textsf{B}^{\\frac{3}{4}}$.\n\nFor brevity, our current manuscript proves the upper bounds for TEWA-SE for both the general convex case and the strongly-convex case using smoothness assumptions, with footnote 1 noting that the convex case guarantee can alternatively be obtained using only Lipschitz-continuity. In the revised manuscript, we will restructure our proofs to match the minimal assumptions: (i) prove the general convex case directly using only Lipschitz-continuity, and (ii) separately prove the strongly-convex case using smoothness. \n    \nIn the revised proof for the convex case, the smoothness-dependent term $\\beta(q-p+1)h^2$ in (34) will be replaced by $2L(q-p+1)h$ under the Lipschitz-only assumption, where $L$ denotes the Lipschitz constant. Using our current parameter choice  $h=\\sqrt{d}\\textsf{B}^{-\\frac{1}{4}}$, we will have  $2L(q-p+1)h\\lesssim\\sqrt{d}\\textsf{B}^{\\frac{3}{4}}$, which preserves the same $\\sqrt{d}\\textsf{B}^{\\frac{3}{4}}$ rate from the original analysis.\n\n**Convex and smooth functions:** To avoid confusion, the revised manuscript will focus exclusively on cases (i) and (ii) described above. However, to answer your separate questions about convex and smooth functions:\n- **Clarification on $\\textsf{B}^{\\frac{2}{3}}$ rate:** You are correct that choosing $h=d^{\\frac{1}{3}}\\textsf{B}^{-\\frac{1}{6}}$ in (34) which currently assumes convexity and smoothness would yield an adaptive regret of order $d^{\\frac{2}{3}}\\textsf{B}^{\\frac{2}{3}}$. The $\\textsf{B}^{\\frac{2}{3}}$ term aligns with the time-dependence in the static regret upper bound of [29, Theorem 3].\n- **Clarification on choice of $h$:** TEWA-SE is designed to adapt to unknown curvature of the loss functions. Therefore, it is not feasible to choose different $h$ a priori for different functions, e.g., $h=d^{\\frac{1}{3}}\\textsf{B}^{-\\frac{1}{6}}$ if the functions are convex and smooth, or $h=\\sqrt{d}\\textsf{B}^{-\\frac{1}{4}}$ if they are strongly-convex and smooth. Our current proof uses $h=\\sqrt{d}\\textsf{B}^{-\\frac{1}{4}}$ throughout. While fixing $h=d^{\\frac{1}{3}}\\textsf{B}^{-\\frac{1}{6}}$ would yield a $d^{\\frac{2}{3}}\\textsf{B}^{\\frac{2}{3}}$ adaptive regret for the convex case, this would compromise the minimax-optimality we achieve for the strongly-convex case in switching regret and dynamic regret.\n\n### **3. Alternative choice of $h$ for parameter-free adaptive regret and path-length regret**\n\nThank you for this detailed question. We respond to your question point-to-point:\n- You are correct that $h$ is the only parameter of TEWA-SE that is tuned using the non-stationarity measures such as $S, \\Delta$ and $P$. As you note, choosing $h$ to be order of $T^{-\\frac{1}{6}}$ independently of $\\textsf{B}$ would yield an adaptive regret of $\\textsf{B}^{\\frac{1}{2}}T^{\\frac{1}{6}}$ in (34) for the convex and smooth case, and $\\textsf{B}T^{-\\frac{1}{3}}+T^{\\frac{1}{3}}$ in (41) for the strongly-convex and smooth case. However, this approach sacrifices the minimax-optimality of switching regret and dynamic regret in the strongly-convex setting.\n- We should clarify that our tuning of $h$ does not require knowledge of the smoothness parameter $\\beta$. \n- Regarding your derivation of the parameter-free path-length regret, thank you for working through this analysis. If we understand correctly, your expressions (modulo a typo) were obtained through the following steps:\n\\begin{align}\nR^{\\text{path}}(T, P)\n&\\stackrel{\\text{(a)}}{\\le}R^{\\text{swi}}(T, S')+\\tfrac{P}{r}\\big\\lceil\\tfrac{T}{S'}\\big\\rceil\\\\\\\\\n&\\stackrel{\\text{(b)}}{\\le} 2 S'\\cdot R^{\\text{ada}}(\\big\\lceil \\tfrac{T}{S'}\\big\\rceil, T) + \\tfrac{P}{r}\\big\\lceil \\tfrac{T}{S'}\\big\\rceil\\\\\\\\\n&\\stackrel{\\text{(c)}}{\\lesssim}  S'\\cdot \\Big(\\tfrac{d}{h}\\sqrt{\\tfrac{T}{S'}} + \\tfrac{T}{S'}h^2\\Big) + \\tfrac{P}{r}\\tfrac{T}{S'}\\\\\\\\\n&\\stackrel{\\text{(d)}}{\\lesssim}Th^2+P^{\\frac{1}{3}}T^{\\frac{2}{3}}h^{-\\frac{2}{3}},\n\\end{align}\nwhere (a) applies Proposition 1, (b) converts adaptive to switching regret as we do on line 860 (Lemma 1), (c) substitutes the adaptive regret bound from (34), and (d) optimizes by choosing $S'=P^{\\frac{2}{3}}T^{\\frac{1}{3}}h^{\\frac{2}{3}}$. Finally, setting $h$ to be of order $T^{-\\frac{1}{8}}$ simplifies the bound above into $P^{\\frac{1}{3}}T^{\\frac{3}{4}}$. While this approach avoids tuning $h$ based on $P$, it still requires knowledge of $P$ to set $S'$. In contrast, the presented Bandit-over-Bandit (BoB) approach is truly parameter-free by using an adversarial bandit algorithm to adaptively select $h$ for TEWA-SE in each epoch, without prior knowledge of any non-stationarity measures.\n- If we instead set $S'=T^{\\frac{1}{3}}h^{\\frac{2}{3}}$ independent of $P$ in step (d), the resulting bound becomes $PT^{\\frac{3}{4}}$, which scales linearly in $P$. When $P$ is small, this bound is tighter than our $P^{\\frac{1}{5}}T^{\\frac{4}{5}}+T^{\\frac{5}{6}}$ bound obtained using BoB. However, it becomes vacuous when $P\\gtrsim T^{\\frac{1}{4}}$. Our goal is to provide a non-vacuous bound for all $P=o(T)$, which BoB achieves.\n\n### **4. Polynomial-time complexity of TEWA-SE**\n\nYes, the computational complexity of TEWA-SE is $\\mathcal{O}(\\log^2 T)$ per round, as we reasoned in the paragraph containing equation (26) and stated below it. We describe this as polynomial-time because the overall computational complexity across the entire time horizon $T$ is polynomial in $T$. \n\n### **5. Response to remark on $B^d$ vs. $\\textsf{B}$ notation**\n\nThank you. To distinguish from the parameter $\\textsf{B}$ in TEWA-SE, we will use $\\mathbb{B}^d$ and $\\partial \\mathbb{B}^d$ to denote the unit ball and unit sphere in the revised manuscript.\n\n**References:** Numbered references above correspond to the bibliography in the submitted manuscript."}, {"review_id": "GutMP7OcDz", "reviewer": "Reviewer_JbAB", "summary": "This paper studies a non-stationary bandit convex optimization problem where the non-stationarity is measured by the number of switches $S$, the total variation $\\Delta$ of the loss functions, and the path-length $P$ of the comparator sequence. The authors propose two algorithms, a polynomial-time TEWA-SE and a non-polynomial-time cExO. By establishing the regret upper and lower bounds for both general convex and strongly-convex losses, TEWA-SE is shown to achieve minimax-optimal regret bounds with respect to known $S$ and $\\Delta$ in strongly convex cases, while not knowing the strong-convexity parameter $\\alpha$. In contrast, TEWA-SE is sub-optimal in the case of general convex losses. Furthermore, the cExO algorithm is shown to achieve minimax-optimal regret with respect to known $S$ and $\\Delta$, and improve on the best existing bounds with respect to $P$. The two approaches can be both extended to the environments with unknown non-stationarity measures via Bandit-over-Bandit framework.", "questions": "See Strengths And Weaknesses", "limitations": "See Strengths And Weaknesses", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n1. The paper is well-written, the authors clearly convey their messages, stating the claims and validating via complete analysis.\n2. The paper clearly and concisely discusses the advantages and limitations of the two algorithms. Combining with the regret lower bounds, this makes the reader clearly understand the difficulty of the problem.\n\n**Weaknesses and Questions**:\n1. The paper studies a relatively standard problem in the literature. There are some existing works considering the same problem with little difference (like different regret or different non-stationarity measure). Therefore, I am afraid that the novelty and contribution to this problem is limited. The paper should provide more discussions on the difference between this paper and the existing ones that study the almost same problem (like with different regret and with different non-stationarity measure), and showcase why the approaches in this paper is more worthy of attention.\n2. Although the discussion of TEWA-SE is comprehensive and the result itself is interesting (although not minimax optimal in general case), I feel that both the design and analysis for TEWA-SE largely follows the standard approach in the OCO literature with adaptive learning rates. I understand that in OCO literature many approaches look similar, but it still makes it less interesting. Throughout reading Section 2 and Appendix C.1, I think the authors should discuss more on its difference between TEWA-SE and previous algorithms mentioned in the paper.\n3. For the bound of TEWA-SE in the general convex losses cases, although I don't feel it is really a problem (to be published), I still wonder why it is hard to achieve the minimax-optimal regret bound with polynomial-time algorithm, when the non-stationarity measure is known. For example, in multi-armed bandit case, [1] achieves the minimax regret bounds in the case when non-stationarity (variation budget) is known, and sub-optimal otherwise.\n\n**Comments**: Given the discussions above, I think the novelty and significance for this paper is not enough to be accepted by neurips. However, I would be happy to change my mind and increase my score if I miss some important points.\n\n[1] Cheung, W. C., Simchi-Levi, D., & Zhu, R. (2019, April). Learning to optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 1079-1087). PMLR.", "was_revised": true, "final_justification": "I have carefully reviewed all the comments and all the authors' responses. The discussion is very comprehensive and address most of my concerns. I believe all these discussions make the contribution more clearly. Therefore, I will raise my score to 4.", "rebuttal": "### **1. Novelty and contributions of this work, and differences from existing work**\n\nThank you for this constructive feedback. While non-stationary Bandit Convex Optimization has been studied before [7, 13, 14, 33], our work provides the following meaningful advances: \n\n**Unifying study:** Attaining optimal performance for general non-stationary Convex Bandit Optimization is hard (see point 3 below), and the field currently lacks a comprehensive, unified treatment. Existing works study different aspects of the problem in isolation: [7, 14] focus on dynamic regret $ R^{\\text{dyn}}(T, \\Delta)$, while [13, 33] address path-length regret $R^{\\text{path}}(T, P).$ As we illustrate in Fig. 1 and formalize in Proposition 1, the dynamic regret and path-length regret can both be upper bounded using the switching regret $R^{\\text{swi}}(T, S)$, but the reverse does not necessarily hold, suggesting that our results may be more fundamental. This work is the first to systematically unify and extend previously scattered results, establishing a complete picture of the state-of-the-art. We also prove lower bounds and derive  parameter-free guarantees by applying the Bandit-over-Bandit framework, which offer baselines for future research on this topic. \n\n**Technical contributions:** Our proposed algorithms represent rigorous adaptations of established techniques, as detailed in lines 115-127 for TEWA-SE and lines 128-135 for cExO. Both algorithms build upon long lines of prior work. \n- **TEWA-SE:** We adapt sleeping experts and MetaGrad-type adaptivity techniques from Online Convex Optimization [21-23] to the bandit setting. Key modifications include replacing exact gradients with one-point bandit gradient estimates, and designing a quadratic surrogate function (see point 2 below). These adaptations require non-trivial technical work, including careful bias-variance trade-offs and detailed analysis of tilted exponentially weighted averaging with noisy gradient estimates. \n- **cExO:** The cExO algorithm builds on the exploration by optimization approach from [27] by adding a novel clipping step. Though not polynomial-time computable, cExO achieves the first minimax-optimal result for switching regret and dynamic regret w.r.t. $T, S$ and $\\Delta$. \n\nMoreover, to clarify how our work differs from prior work, we would like to emphasize the following points:\n- The reduction from $R^{\\text{path}}(T, P)$ to $R^{\\text{swi}}(T, S)$ in Proposition 1 is new and employs simple geometric arguments (see Lemma 1 and its proof from line 863). To better position our work relative to existing work, we will add a remark discussing this reduction technique and referencing [17], noting that while our unified approach through $R^{\\text{swi}}(T, S)$ simplifies the analysis of $R^{\\text{path}}(T, P)$, it may yield slightly looser bounds on $R^{\\text{path}}(T, P)$ compared to direct analysis.\n- We detail in point 2 below how the quadratic surrogate loss we tailored for TEWA-SE differs from its direct precursor in [23]. We will also emphasize this in the revised manuscript.\n- To our knowledge, the $d^{\\frac{4}{5}}P^{\\frac{2}{5}}T^{\\frac{3}{5}}$ lower bound for path-length regret in Theorem 4 is new  and improves upon the only existing result, the $d\\sqrt{PT}$ lower bound from [13, Theorem 5], w.r.t. $T$. This is attained by leveraging a different construction of a hard instance of loss functions.\n\n### **2. Differences between TEWA-SE and prior work**\n\nThank you for this comment. You are right that TEWA-SE builds on Zhang et al. [23] from Online Convex Optimization, which allows access to exact gradients. Apart from replacing exact gradients with one-point gradient estimates, we have also made a technical adaptation in the surrogate loss for TEWA-SE which we will explain more explicitly in the revised manuscript. While Zhang et al. [23] and the original MetaGrad paper [21] use $\\eta^2||\\boldsymbol{g}_t||^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ and $\\eta^2(\\boldsymbol{g}_t^\\top(\\boldsymbol{x}_t-\\boldsymbol{x}))^2$ as the quadratic term for the surrogate loss, we use $\\eta^2 G^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ in our surrogate loss $\\ell_t^\\eta(\\boldsymbol{x})=-\\eta\\boldsymbol{g}_t^\\top(\\boldsymbol{x}_t-\\boldsymbol{x})+\\eta^2G^2||\\boldsymbol{x}_t-\\boldsymbol{x}||^2$ in (11), where $G$ is a high probability upper bound on $||\\boldsymbol{g}_t||$ as in (10).\n\nThe surrogate loss from [23] or [21] necessitates an additional condition relating $\\mathbb{E}[||\\boldsymbol{g}_t||]$ and $\\mathbb{E}[||\\boldsymbol{g}_t||^2]$ (or $\\mathbb{E}[\\boldsymbol{g}_t\\boldsymbol{g}_t^\\top]$) to be satisfied in the analysis, see e.g. [21, Theorem 2]. When working with tilted exponentially weighted average with noisy gradient estimates, directly using their quadratic term would complicate the proof. Our choice of the quadratic term, inspired by [22], simplifies this particular aspect of the proof.\n\n### **3. Why harder to achieve optimality in non-stationary convex bandits than in multi-armed bandits**\n\nThank you for this insightful comment. As we detail in lines 136-141, the techniques that achieve optimal regret in multi-armed bandits under non-stationarity (with known non-stationarity measures) cannot be directly applied to Bandit Convex Optimization (BCO). The continuous action space in BCO requires fundamentally different approaches. \n\nAchieving optimal time-dependence in BCO is challenging even for static regret, as noted in lines 130-132 and in point 2 of the review by Reviewer NBQt. The current state-of-the-art Fokkema el al. (2024) and Suggala et al. (2024) use the bandit version of the online Newton step for stochastic unconstrained BCO from Lattimore and György (2023) to achieve the optimal $\\sqrt{T}$ time dependence (modulo polylogarithms). It remains unclear whether first-order methods, including our proposed TEWA-SE algorithm, can achieve the optimal rate, especially in the more challenging non-stationary environments. We will add a brief  discussion on this before the \"Conclusion\" section in the revised manuscript.\n\nTo handle non-stationary environments, an interesting future direction is to combine TEWA-SE's aggregation mechanism with second-order expert algorithms similar to that in Fokkema et al. (2024) and Suggala et al. (2024). Another idea is to explore whether incorporating a restart criterion, similar to line 11 of Algorithm 1 in Fokkema et al. (2024) or line 15 of Algorithm 1 in Suggala et al. (2021), could enable change-detection and  improve regret guarantees compared to TEWA-SE.\n\n**References:**\n- Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore, and Jack J Mayo. Online newton method for bandit convex optimisation. In *Conference on Learning Theory*, pages 1713–1714. PMLR, 2024.\n- Arun Suggala, Y Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control. In *Conference on Learning Theory*, pages 4691–4763. PMLR, 2024.\n- Tor Lattimore and András György. A second-order method for stochastic bandit convex optimisation. In *Conference on Learning Theory*, pages 2067–2094. PMLR, 2023.\n- Arun Sai Suggala, Pradeep Ravikumar, and Praneeth Netrapalli. Efficient bandit convex optimization: Beyond linear losses. In *Conference on Learning Theory*, pages 4008–4067. PMLR, 2021.\n- (Numbered references above correspond to the bibliography in the submitted manuscript.)"}]

Author rebuttal:

Meta-review: This paper studies several variants of Bandit Convex Optimization (BCO) under different non-stationarity assumptions. The reviewing team was overwhelmingly positive about the submission. Clear accept. Good job!

Please incorporate all the feedback received from the reviewers in the revised version.
Decision: Accept (poster)