Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits
Authors: Yue Kang
Cho-Jui Hsieh
Thomas Lee
Venue: Accepted by TMLR ()

Abstract: In stochastic contextual bandits, an agent sequentially makes actions from a time-dependent action set based on past experience to minimize the cumulative regret. Like many other machine learning algorithms, the performance of bandits heavily depends on the values of hyperparameters, and theoretically derived parameter values may lead to unsatisfactory results in practice. Moreover, it is infeasible to use offline tuning methods like cross-validation to choose hyperparameters under the bandit environment, as the decisions should be made in real-time. To address this challenge, we propose the first online continuous hyperparameter tuning framework for contextual bandits to learn the optimal parameter configuration in practice within a search space on the fly. Specifically, we use a double-layer bandit framework named CDT (Continuous Dynamic Tuning) and formulate the hyperparameter optimization as a non-stationary continuum-armed bandit, where each arm represents a combination of hyperparameters, and the corresponding reward is the algorithmic result. For the top layer, we propose the Zooming TS algorithm that utilizes Thompson Sampling (TS) for exploration and a restart technique to get around the \textit{switching} environment. The proposed CDT framework can be easily utilized to tune contextual bandit algorithms without any pre-specified candidate set for multiple hyperparameters. We further show that it could achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.

Published in Transactions on Machine Learning Research (04/2024)
Online Continuous Hyperparameter Optimization for Gener- alized Linear Contextual Bandits
Yue Kang
guekang@hudavii.com edu
University of Colifornia, Davis
Cho-Jui Hsich
chohsich&cs. ucla eduu
Google and University of California, Los Angeles
Thomas C. M. Lee
tcmlee edu
University of California, Davis
Reviewed on OpenReview: https: // openreview. net/ formf id= LQE2Acd
Abstract
In stochastic contextual bandils, an agent sequentially makes actions from a lime-dependent action based on past experience minimize the cumulative regret. Like many other machine learning algorithms, the performance of bandits heavily depends on the values of hyperparameters, and theoretically derived parameter values may lead to unsatisfactory results in practice. Moreover, it is infeasible to use offline tuning methods like cross- validatin to choose hyperparameters under the bandit environment, as the decisions should be made in real-time. To address this challenge, we propose the first online continuous hyperparameter tuning framework for contextual bandits to learn the optimal parameter configuration in practice within a search space on the fly. Specifically, we use a double-layer bandit framework named CDT (Continuous Dynamic Tuning) and formulate the hyperparameter optimization as non-stationary of hyperparameters, and the corresponding reward is the algorithmic result. For the top layer, we propose the Zooming TS algorithm that utilizes Thompson Sampling (TS) for exploration and a restart technique to get around the swilching environment. The proposed CDT framework can be easily utilized to tune contextual bandit algorithms without any pre-specified candidate achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.
partinuum-armen bandit, where each arm represents combination
for multiple hyperparameters. We further show that could
Introduction
The contextual bandit is a powerful framework for modeling sequential learning problems under uncertainty, with substantial applications in recommendation systems (Li et al. 2010), clinical trials (Woodroofe) 1979), personalized medicine (Bastani & Bayati 2020), etc. At each round i, the agent sequentially interacts with the environment by pulling an arm from a feasible arm set A, of K arms (K might be infinite), where every arm could be represented by d-dimensional feature vector, and only the reward of the selected arm is revealed. Here A₁ is drawn IID from unknown distribution. In order to maximize the cumulative reward, the agent would update its strategy on the fly to balance the exploration-exppoitatio tradeoff.
Generalized linear bandit (GLB) was first proposed in Filippi et al. (2010) and has been extensively studied under various settings over the recent years (Jun et al. 2017 Kang et al.) 2022), where the stochastic payoff of an arm follows a generalized linear model (GLM) of associated feature vector and some fixed, but initially unknown parameter 6*, Note that GLB extends the linear bandit (Abbasi- Yadkori al.) 2011] in representation power and has greater applicability in the real-world applications, e.g. logistic bandit.

---

Published in Transactions on Machine Learning Research (04/2024)
algorithms Zhang et al. (2016) can achieve improvement over linear bandit when the rewards are binary.
Upper Confidence Bound (UCB) (Auer et al. 2002a Filippi et, al. 2010 Li et al. 2010) and Thompson Sampling (TS) (Agrawal& & Goyal 2012 2013 are the two most popular ideas to solve the GLB problem.
Both of these methods could achieve the optimal regret bound of order Ó(VT) under some mild conditions,
where T stands for the lotal number of rounds (Agrawal & Goyal 2013).
However, the empirical performance of these bandit algorithms significantly depends on the configuration of hyperparameters, and simply using theoretical optimal values often yields unsatisfactory practical results, not to mention some of them are unspecified and need to be learned in reality. For example, in both LinUCB (Li et al. 2010) and LinTS (Abeille & Lazaric 2017: Agrawal & Goyal 2013) algorithms, there are hyperparameters called exploration rates that govern the tradeoff and hence the learning process. But it has been empirically verified that the best exploration rate to use is always mustanc--dependee
and may vary at different iterations Bouneffouf & Clacys (2020); Ding et al. (2022b). Note it is inherently impossible to use any stato-of-tho-arr offline hyperparameter tuning methods such as cross validation (Stone 1974) or
Bayesian optimization (Frazier, 2018) since decisions in bandits should be made in real time. To choose the best hyperparameters, some previous works use grid search in their experiments (Ding et al. 2021 Jun et al.) 2019), but obviously, this approach is infeasible when it comes to reality, and how to manually discretize the hyperparameter space is also unclear. Conclusively, this limitation has already become bottleneck for bandit algorithms in real-world applications, but unfortunately, it has rarely been studied in the previous literature.
The problem of hyperparameter optimization for contextual bandits was first studied in Bouneffoul' & Claeys (220)), where the authors proposed two methods named OPLINUCB and DOPLINUCB to learn the practically optimal exploration rate of LinUCB in a finite candidate set by viewing each candidate as an arm and then using multi-armed bandit to pull the best one. However, 1) the authors did not provide any theoretical support, and 2) we believe the best exploration parameter in practice would vary during iterations - more exploration may be preferred at the beginning due to the lack of observations, while more exploitation would be favorable in the long run when the model estimate bocomes more accurate. Furthermore, 3) they only consider tuning one siugle hyperparameter. To lackle these issues, Ding el al. (202b)) proposed TL and Syndicated framework by using a non-stationary mullti-armed bandit for the hyperparameter set. However, their approach still requires pre-defined set of hyperparameter candidates. In practice, choosing the candidates requires domain knowledge and plays a crucial role in the performance. Also, using a piccewise-stationay setting instead of a complete adversarial bandit. (e.g. EXP3) for hyperparameter tuning is more efficient since we expect fixed hyperparameter setting would yield indistinguishable results in a period of time. Conclusively, it would be more efficient to use a continuous space for bandit hyperparameter tuning.
We propose an efficient bandit-over-bandit (BOB) framework (Cheung et al. 2019 named Continuous Dynamic Tuning (CDT) framework for bandit hyperparameter tuning in the continuous hyperparameter space, without requiring a pre-defined set of hyperparameter candidate configurations. For the top layer bandit we formulate the online hyperparameter tuning as non-stationary Lipschitz continuum-any bandit problem with noise where each arm represents a hyperparameter configuration and the corresponding reward is the performance of the GLB, and the expected reward is a time-dependent Lipschitz function of the arm with some biased noise. Here the bias depends on the previous observations since the history could also affect the update of bandit algorithms. It is also reasonable to assume the Lipschitz functions are piecewise stationary since we believe the expected reward would be stationary with the same hyperparameter configuration over a period of time (i.e. switching environment). Specifically, for the top layer of our CDT framework, we propose the Zooming TS algorithm with Restarts, and the key idea is to adaptively refine the hyperparamcter space and zoom into the regions with more promising reward (Kleinberg et al., 2019) by using the TS methodology (Chapelle & Li 2011). Moreover, we demonstrate that a simple restart trick could handle the piecewise changes of the bandit environments in both theory and practice. To sum up, we summarize our contributions as follows:
1) We propose an online continuous hyperparameter optimization framework for contextual bandits called CDT that handles all aforementioned issues of previous methods with theoretical guarantees. To the best of our knowledge, CDT is the first hyperparameter tuning method (even model selection method) with
10(+) ignores the poly-logarithmic factors.
2

---

Published in Transactions on Machine Learning Research (04/2024)
continuous candidates in the bandit community. 2) For the top layer of CDT, we propose the Zooming TS algorithm with Restarts for Lipschitz bandits under the switching environment. To the best of our knowledge, our work is the first one to consider the Lipechitz bandits under the switching environment, and the first one to utilize TS methodology in Lipschitz bandits. 3) Experiments on both synthotic and real datasets with various GLBs validate the efficiency of our method.
Notations: For a vector x E RR, we use ||=||| to denote its l2 norm and | == Vx Ax for any positive definite matrix A E Rdxd, We also denote [T] {1....,Ty T) for T E e
2 Related Work
There has been extensive literature contextual bandit algorithms, and most of them are based on the UCB or TS techniques. For example, several UCB-type algorithms have been proposed for GLB, such as GLM-UCB (Filippi et al. 2010) and UCB-GLM (Li et al. 2017) that achieve the optimal Ö(vT) regret bound. Another rich line of work on GLBs follows the TS idea, including Laplace-TS (Chapelle & Li 2011), SGD-TS (Ding et al., 202T). ; etc. In this paper, we focus on the hyperparameter tuning of contextual bandits, which is a practical but under-cxplored problem. For related work. Sharaf & Daumé III (2019) first studied how to learn the exploration parameters in contextual bandits via a meta-learuing method. However, this algorithm fails to adjust the learning process based previous observations and hence can be unstable in practice. BBunnefoof & Clacys (2020) then proposed OPLINUCB and DOPLINUCB to choose the exploration rate of LinUCB from a candidate set, and moreover Ding et al. (022b)) formulates the hyperparameter tuning problem as a non-stochastic multi-armed bandit and utilizes the classic EXP3 algorithm. However, as we mentioned in Section| D1 both works have several limitations that could be decently fixed. Note that hyperparameter tuning could be regarded as a branch of model selection in bandit algorithms. To name a few for this general problem, Agarwal al. (2017) proposed master algorithm that could combine multiple bandit algorithms, while Foster et al. (2019) initiated the study of model selection tradeoff in contextual bandits and proposed the first model selection algorithm for contextual linear bandits. Pacchiano et al. (2020) further considered the confidence tuning in OFUL and model selection in reinforcement learning. However, these general model selection methods may fail for the bandit hyperparameter tuning task. To clarify this point, we take the state-of-the-art corralling idea Agarwal et al. (2017) as an example: in theory, it has regret bound or order O(v + M Rmax) where M is the number of base models (number of hyperparameter combinations in our setting) and Rmax is the regret of the worst candidate model in the tuning set. Therefore, the one hand, M is infinitely large in our problem setting with continuous candidate set, which means the regret bound would also be infinitely large. On the other hand, in order to achieve sub-linear regret in hyperparameter tuning, the corralling idea requires that all hyperparameter candidates yield sub-linear regret in theory, which is a very unrealistic assumption. On the contrary, our work only assumess the existence of a hyperparamoter candidate in the tuning set which yields good thcoretical regret in theory. In experiments, it is also costly to use since it requires updating all base models at each round, and we have infinitely many base models under our setting. Ding et al. (2022b) includes the corralling idea in their experiments, and we can observe that it achieves almost lincar regret in cach setting since it has no sub-linear regret guarantec for the bandit hyperparameter tuning problem. In conclusion, the only existing methods that focus on hyperperameter tuning of bandits are OP and TT. (Syndicated), and we use both of them in our paper as baselines. And we propose the first continuous hyperparameter tuning framework for contextual bandits, which doesn't require a pre-defined set of candidates. Note it is doable to finely discretize the continuous space and then implement an algorithm with discrete candidate sets (e.g- Syndicated) in mothodology, but. we highlight the inefficiency of this idca on both the empirical and thcoretical side in Appendix A.4
We also briefly review the literature on Lipschitz bandits that follows two key ideas. One is uniformly discretizing the action space into mesh (Kleinberg) 2004 Magureant et all 2014] that any learning process like UCB could be directly utilized. Another more popular idea is adaptive discretization on the action space by placing more probes in more encouraging regions (Bubeck et al. 2008 Kleinberg et al. 2019 Lu et al. 2019; Valko et al. 2013), and UCB could be used for exploration. Furthermore, the Lipschitz bandit under adversarial corruption was recently studied in Kang et al. (2023). In addition, (Podimata & Slivkins, 2021) proposed the first fully adversarial Lipschitz bandit in an adaptive refinement manner and derived instance-dependent regret bounds, but their algorithm relies on some unspecified hyperparameters and is
3

---

Published in Transactions on Machine Learning Research (04/2024)
computationally infeasible. Since the expected reward function for hyperparameters would not drastically change every time, it is also inefficient to use fully adversarial algorithm here. Therefore, we introduce a new problem of Lipschitz bandits under the switching environment, and propose the Zooming TS algorithm with a restart trick to deal with the "almost stationary" nature of the bandit hyperparameter tuning problem.
3 Preliminaries
We first review the problem sctting of contextual bandit algorithms. Denote T as the total number of rounds and K as the number of arms we could choose at each round, where K could be infinite. At each round t E [T] == (1.....7] the player is given K arms representod by set of feature vectors X = ( a E [K]] S Rd drawn from some unknown distribution, where Zr, is a d-dimensional vector containing information of arm at round t. The player selects an action a2 E [K] based on the current X; and previous observations, and only receives the payoff of the pulled arm ay- Demote 24 == Ft,a, as the feature vector of the chosen arm a and y/ as the corresponding reward. We assume the reward y/ follows canonical exponential family with minimal representation, a.k.a. generalized linear bandits (GLB) with some mean function p(.). In addition, one can represent this model by y = ulx; 0*) t,, where E, follows a sub-Gaussee Gaussian distribution with paramcter o² independent with the information filtration J, offa, Xx. yo V=)==l) and (X4) up to round i, and 0* is some unknown coefficient. Denote or,* = arg max p=xzia, 0*) as the optimal arm round t and Ft, as its corresponding feature vector. The goal is to minimize the expected cumulative regret defined as:
T Σ [m(a,, - (x(xT()))
R(T)- =
-
Note that all state-of-the-art contextual GLB algorithms depend on at least one hyperparameter to balance the well-known exploration-explitaiiin tradeoff. For example, LinUCB (Li et al., 2010). the most. popular UCB lincar bandit, uses the following rule for arm selection at round t:
de arg max x 0. 0z + on (1) [|rtally-"
(LinUCB)
[E(K]
Here the model parameter 0, is estimated at each round via ridge regression, i.e. 0, = V Tsys where V, = Mr, + + x.x._ And it considers the standard deviation of each arm with an exploration parameter a1 (t(),, where with a larger value of (1(t) the algorithm will be more likely to explore uncertain arms. Note that the regularization parameter is only used to ensure V2 is invertible and hence its value is not crucial and commonly set to 1. In thoory we can choose the value of an (t) as (1) = a / ((1 + t/A)/8) + ||0*]] vx, to achieve the optimal Ö(VT) bound of regret: However, in practice, the values of a and ||0*| are unspecified, and hence this thcorctical value of (1 is inaccessible. Furthermore, it has been shown that this is a very conservative choice that would lead to unsatisfactory practical performance, and the practically optimal hyperparameter values to use are distinct and far from the theoretical ones under different algorithms or settings. We also conduct a series of simulations with several state-of-the-art GLB algorithms to validate this fact, which is deferred to Appendix A.1 Conclusively, the best exploration parameter to use in practice should always be chosen dynamically based on the specific scenario and past observations. In addition, many GLB algorithms depend on some other hyperparameters, which may also affect the performance. For example, SGD-TS also involves a stepsize parameter for the stochastic gradient descent besides the exploration rate, and it is well known that a decent stepsize could remarkably accelerate the convergence (Loizou et al., 2021 b. To handle all these cases, we propose a general framework that can be used to automatically tune multiple continuous hyperparameters for contextual bandit.
For certain contextual bandit, assume there are p different hyperparameters a(t) = {a: and each hyperparameter (t) could take values in an interval [a,, Vt. Denote the parameter space A = 8 [ag by]. and the theoretical optimal values as a" (t). Given the observations Fe up to round t, we write a (a((t) as the arm we pulled when the hyperparameters are set to (<l), and xy (.) as the corresponding feature vector.
Motivated by the success of Bayesian optimization Frazierr 2018 on the hyperparameter tuning of the offline machine learning algorithms, the main idea of our algorithm is to formulate the hyperparameter optimization
4

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 1 Zooming TS algorithm with Restarts
Input: Time horizon T, space A, epoch size H.
1: for t 1 to T do
2: if tE + 1:7 0, .,... then
Initialize the total candidate space Ao = A and the active set J S Ao s.t. Ao S Cre (i)) Restart
and n1(v) 1, Ve e J.
4: else if f(()) f((u) > re(o) 2r.(u) for some pair of u, then
5:
Set Mu] and Ao - (o,((u,rxuu)
Removal
end if
if An & B(, (w)) then Activate and pull some point Ao that has not been covered: J J
Activation
8:
9: else
10:
Us arg max,eJ de(v), break ties arbitrarily.
Selection
11:
end if
12:
Observe the reward De+1, and then update components the Zooming TS algorithm: T++1(1); (v), fer1()) St-1 (c) for the chosen ot E J:
m++1(0)) = (x(e)) + 1, (1 = (f((v))ma(v)) + Dc+ m)/
13: end for
as (another layer of) non-stationary Lipschitz bandit in the continuous space A S RP, L.c. the agent chooses an arm (byperparameter combination) a E A in round t E [T]. and then we decompose (a)x(a) 8*)
((z)(a(FF) 0*) (a + 1FF.a
(2)
Here St is some time-dependent Lipschitz function that formulates the performance the bandit algorithm under the hyperparameter combination a at round t, since the bandit algorithm tends to pull similar arms if the chosen values of hyperparameters are close at round l. In other words, we expect close hyperparameter values to yield similar results with other conditions fixed, as in Bayesian optimization offline hyperparameter tuning. To demonstrate that our Lipschitz assumption w.r.t. the hyperparameter values in Eqn. equation 3 is reasonable, we conduct simulations with LinUCB and LinTS, and defer it to Appendix A due to the space limit. Moreover, (M,,, [])r,,))) is IID sub-Gaussian with parameter 72, and to be fair we assume E[1,,,a]] could also depend on the history J,, since past observations and action sets would explicitly influence the model parameter estimation and hence the decision making at each round. In addition Lipschitzness, we also suppose gi follows switching environment: 9e is piecewise stationary with some change points, i.e.
(g)())) - 90(02) < ||a - azll, Vai, 02 E A;
(3)
Ba E A: go(a) + ( c(T), c(T) N.
(4)
Since after sufficient exploration, the expected reward should be stable with the same hyperparameter sctting, could assume that c(T) Ó1). Detailed justification this piecewise Lipschitz assumption deferred to Remark in Appendix B Although numerous research works have considered the switching environment
(a.k.a. abruptly-changing environment) for multi-armed linear bandits (Auer et al., 2002b Wei et al. 2016).
our work is the first to introduce this setting into the continuum-arnn bandits. In Section 4.1 we will show
that by combining our proposed Zooming TS algorithm for Lipschitz bandits with a simple restarted strategy, a decent regret bound could be achieved under the switching environment.
4 Main Results
In this section, we present our novel online hyperparameter optimization framework that could be casily adapted to most contextual bandit algorithms. We first introduce the continuun-arm Lipschitz bandit problem under the switching environment, and propose the Zooming TS algorithm with Restarts which
5

---

Published in Transactions on Machine Learning Research (04/2024)
Figure 1: Illustration of the restarted strategy.
Round H Zooming TS algorithm
epoch 1
C
Round H 11+1-1 - 2H: Zooming TS algorithm
epoch 2
C
C
Round (m - (m-1)H+1- T Zooming TS algorithm
epoch [T/H]
modifies the traditional Zooming algorithm [Keiinerg et al.) 2019 to make it more efficient and also adaptive to the switching environment. Subsequently, we propose our bandit hyperparameter tuning framework named Continuous Dynamic Tuning (CDT) by making use of our proposed Zooming TS algorithm with Restarts and the Bandit-over-Bande (BOB) idea.
W.l.o.g. assume that there exists positive constant S such that ||0 s S and || S 1, Vt, a, and each hyperparameter space has been shifted and scaled to [0. We also assume that the mean reward p(zTTa 0*) E [o, 1], and hence naturally (a) E [0, Va E A = -0, [0,1),,
4.1 Zooming TS Algorithm with Restarts
For simplicity and consistency, we will reload and introduce a new system of notations in this subsection. Consider the non-stationary Lipschitz bandit problem on a compact space under some metric Dist(:..) 2 0, where the covering dimension is denoted by Pe- The learner pulls an arm &r E A at round t E [2] and ne: where t == .,..., T and ne is ITT) zero-mean error with sub-Guassian parameter 76: and Se is the expected reward function round and is Lipschitz with respect to Dist(:.)). The switching environment assumes the time horizon T is partitioned into c(T") 1 intervals, and the bandit stays stationary within each interval, i.e.
subsoquently receives a reward He sampled independently of Pv, Jt = f((v)) +e
(f((m) - fe(n)) S Dist(m, n), m,n n E A; and Σ 13m E A: fe(m) & fe+1(m)] = c(T).
Here in this section c(T) = o(T) could be any integer. The goal of the learner is to minimize the expected (dynamic) regret that is defined as:
T
max Sa()) RT(T) Σ
Σ 1=1
E (f((t))
tm1
At each round t, of = arg max fe(u) denotes the maximal point (w.Lo.g. assume it's unique), and (v()) = f((u*) > f((v) the "badness" of cach arm v. We also denote A,, as the r-optimal region at the scale (0, 1], ie. Ar,: {o A r/2 < (,( I r) at time t. Then the r-zooming number Nr,(r)) of (A, is defined the minimal number of balls of radius no more than r required to cover Ar,- (Note the subscript stands for zooming here.) Next, define the zooming dimension Pz.t (Kleinberg et al. 2019 at time t as the smallest 2 0 such that for every r E (0, 1] the r-zooming number can be upper bounded by cr for some multiplier e > 0 free of r:
Ps. min(g 2 3c N,Nr)( & cr " V (0,
It's obvious that 5 Pr,1 S Pe, Vt [T]. (Note Ps. is fixed under the stationary environment.) On the other hand, the zooming dimension could be much smaller than Pe under some mild conditions. For example, if

---

Published in Transactions on Machine Learning Research (04/2024)
the payoff function fi defined R is greater than ||l =ll in scale for some B 2 1 around o" in the space A, i.c. fe(vf) - f(( = 2[1 - ) then it holds that Pz, S 1/-1/B)p.- Note that we have 8 2 (i.e. Pz.t S Pe/2) when f+(-) is C²-smooth and strongly concave in a neighborhood of v². More details are presented in Appendix C Since the expected reward Lipschitz function f((-) is fixed in each time interval under the switching environment, the zooming number and zooming dimension Pa, would also stay identical. And we also write P=,. max Ps,t S Pe-
Our proposed Algorithm ! extends the classic Zooming algorithm (Kleinberg et al. 2019). which was used under the stationary Lipschitz bandit environment, by adding several new ingredients for better efficiency and adaptivity to non-stationary environment: on the one hand, we employ the TS methodology and propose novel removal step. Here we utilize TS since it was shown that TS is more robust. than UCB in practice (Chapelle & Li 2011] Wang & Chen 2018), and the removal procedure in line 5 of Algorithm | could adaptively subtract regions that are prone to yield low rewards. Both of these two ideas could enhance the algorithmic efficiency, which coincides with the practical orientation of our work. On the other hand, the restarted strategy proceeds our proposed Zooming TS in epochs and refreshes the algorithm after every H rounds, as displayed Figure [ The epoch size is fixed through the total time horizon and controls the tradeoff between non-stationarity and stability. Note that H in our algorithm does not need to match the actual length of stationary intervals of the environment, and we would discuss its selection later. At each epoch, we maintain a time-varying active arm set St S A, which is initially empty and updated every time. For each arm E A and lime I, demote ne(v) the number of times arm has been played before time since the last restart, and (v) as the corresponding average sample reward. We let f(()) = 0 when n,(u) 0. Define the confidence radius and the TS standard deviation of active arm at time & respectively as
re(v)= = 1378 In T 2n (v)
sc(v) B0g me(v))
(5)
where So = = 552TT IT).). We call (()) fu E R" R":
Dist(u, v) S re (v() as the confidence ball of arm at time E [T]- We construct randomized algorithm by choosing the best active arm according to the perturbed estimate mean l()):
(6) where Ze is i.i.d. drawn from the clipped standard normal distribution: we first sample Z, from the standard normal distribution and then set Ze, = max(1/V2m, ). This truncation was also used in TS multi-armed bandits (Jin al.] (221), and our algorithm clips the posterior samples with a lower threshold to avoid underestimation of good arms. Moreover, the explanations of the TS update is deferred to Appendix D due to the space limit.
- =
+ Ze)
The regret analysis of Algorithm is very challenging since the active arm set is constantly changing and the optimal arm 8" cannot be exactly recovered under the Lipschitz bandit setting. Thus, existing theory on multi-armed bandits with TS not applicable here. We overcome these difficulties with some innovative use of metric entropy theory, and the regret bound of Algorithm I is given as follows.
Thcorem 4.1. With = θ (1///// +3)),, the total regret of our Zooming TS algorithm with Restarts under the swilching enwironment over time T is bounded
RL(T) O (1..4)) Tiv... (2)...2)))/
when c(T) > O. In addition, if the excvironment is stationary (i.e c(T)= = 00 Jt ft= S.P2. =P,, == P2, then by using = T (i.e. no restart), our Zooming TS algorithm could achieve the optimal regret bound for Lipschitz bandits up to logarithmic factors:
Vt, Vt E (T),
Rt S Ō (1(6rt))//ottt)))
We also present empirical studies to further evaluate the performance of our Algorithm D compared with stochastic Lipschitz bandit, algorithms in Appendix A.3. A potential drawback of Theorem 4.1 that

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Continuous Dynamic Tuning (CDT)
Input: T1, T2, {2 A = 8 i=1 [as, Dz]-
1: Randomly choose at E [K] and observe 21, yt, t & Ti.
2: Initialize the hyperparameter active set J s.L. AS ((r))((())))) where un, (v) t Vo E J.
3: for t= (Ti + 1) to T do
4: Run the t-th iteration of Algorithm 1 with initial imput horizon T -1, input space A and restarting
epoch length Tz. Denote the pulled arm at round & as a(ia) E A.
> ToP
5: Run the contextual bandit algorithm with hyperparameter a(4)) to pull an arm d..
Bottoo
6: Obtain ye and update components in the contextual bandit algorithm.
BBottom Update TTop Update
7: Update components in Algorithm 1 by treating y as the reward of arm a<tt)
8:
end for
the optimal epoch size H under switching environment relies on the value of c(T) and Pa.., which are unspecified in reality. However, this problem could be solved in theory by using the BOB idea (Cheung et al.] 2019 Zhao et al. 2020) to adaptively choose the optimal epoch size with a meta algorithm (e.g. EXP3 (uue et al. 2002b)) in real time. In this case, we prove the expected regret can be bounded by the max { ccTT) po-a, T }) in general, and some better regret bounds in problem- dependent cases. More details are presented in Theorem F.1 with its proof in Appendix F However, in the following Section 4.2 we could simply set H = ((2+p)/(++P) in our CDT framework where p is the number of hyperparameters to be tuned after assuming c(T) = Õ(1) is of constant scale up to logarithmic terms. The value of To can be determined by assuring the observed rewards are bounded. Note our work int a new problem Lipschitz bandits under the switching environment. One potential limitation of our work is how to deduce a regret lower bound under this problem setting is unclear, and we leave it as future work.
order of Ô T Pc-3
4.2 Online Continuous Hyperparameter Optimization for Contextual Bandits
Based on the proposed algorithm in the previous subsection, we introduce our online double-layer Contimuous Dynamic Tuning (CDT) framework for hyperparameter optimization of contextual bandit algorithms. We assume the arm to be pulled follows a fixed distribution given the hyperparameters to be used and the history at each round. The detailed algorithm is shown in Algorithm 2 Our method extends the bandit- oeciit--vve--baaa banddi (BOB) idea that was first proposed for non-stationary stochastic bandit problems (Cheung et al.) 2019), where it adjusts the sliding-window size dynamically based on the changing model. In our work, for the top layer we use our proposed Algorithm [ to tune the best hyperparameter values from the admissible space, where each arm represents a hyperparameter configuration and the corresponding reward is the algorithmic result. T2 is the length of each epoch (i.c. H in Algorithm [], and we would refresh our Zooming TS Lipschitz bandit after every T2 rounds as shown in Line of Algorithm [ due to the non-stalionarityy The bottom layer the primary contextual bandit and would run with the hyperparameter values aiic) chosen from the top layer at each round t. We also include a warming-up period of length Ti in the beginning to guarantec sufficient exploration as in Li et al. (0177); Ding et al. (2021). Despite the focus of our CDT framework is the practical aspect, we also present a novel theoretical analysis in the following for the completeness of our work.
Although there has been a rich line of work on regret analysis of UCB and TS GLB algorithms, most literature certainly requires that some hyperparameters, e.g. exploration rate, always take their theoretical values. It is challenging to study the regret bound of GLB algorithms when their hyperparamoters are synchronously tuned in real time, since the chosen hyperparameter values may be far from the theoretical ones in practice, not to mention that previous decisions would also affect the current update cumulatively. Moreover, there is currently existing literature and regret analysis on hyperparameter tuning (or model selection) for bandit algorithms with an infinite number of candidates in a contimuous space. Recall that we denote F, = a (fa,, X., Us H==1) as the past information before round 1 under our CDT framework, and at It are the chosen arm and its corresponding feature vector at time t, which implies that a, = a, (a(t)))) ot = xe (F) Furthermore, we denote a" (t) as the theoretical optimal value at round t and Fi as the past information filtration by always using the theoretical optimal a (t). Since the decision at each round t also depends on the history observe by time i, the pulled arm with the same hyperparameter at!) might be different under F, F?- To
8

---

Published in Transactions on Machine Learning Research (04/2024)
analyze the cumulative regret R(T) of our Algorithm
2 we first decompose it into four quantities:
21
R(T) = E
- (00)
+E
-(( T())
L
Quantity (A)
Quantity (B)
+
(n (x<(aa((()))) (0) 04))
+1
Quantity (C)
T
E
Quantity (D)
Intuitively, Quantity (A) is the regret paid for pure exploration during the warming-up period and could be controlled by the order O(Ti). Quantity (B) is the regret of the contextual bandit algorithm that runs with the theoretical optimal hyperparameters a²(t) (t) all the time, and hence it could be easily bounded by the optimal scale Õ(VT) based on the literature. Quantity (C) is the difference of cumulative reward with the same a (t) under two separate lines of history. Quantity (D) is the extra regret. paid to lune the hyperparameters on the fly. By using the same line of history Fe in Quantity (D), the regret of our Zooming TS algorithm with Restarts in Theorem 4.1 can be directly used to bound Quantity (D). Conclusively, we deduce the following theorem for the regret bound:
Theorem 4.2. Under our problem setting in Section 3 for UCB and TS GLB algorithms with explo- ration byperporameters (e.g. LinUCB, UCB-GLM, GLM-UCB, LinTS), by taking Ti = O(T2/(++)), Ta = o(rlot21/(++3) where p is the number of hyperparameters, and let the theoretically optimal hyperparameter combination a" (T) E A, it holds that
B O(T(F+2)/6+3))
The detailed proof of Theorem 4.2 is presented Appendix G
Note that this regret bound could be further improved to O(T(xo+2)/(o0+)) where po any constant that no smaller than the zooming dimension of (A,ge). Vt. For example, from Figure 3 in Appendix A we can observe that in practice ge would be C²-smooth and strongly concave, which implies that E[R(T)) & O(((++4)/00+)))
Note our work is the first one to consider model selection for bandits with continuous candidate set, and the regret analysis for online model selection in the bandit setting (Foster et al. 2019) is intrinsically difficult. For example, regret bounds of the algorithm CORRAL (Agarwal et al. 2017) for model selection and Syndicated (Ding et al. 2022b) for bandit hyperparameter tuning are (sub siubalinearly dependent on the number of candidates, which would be infinitely large and futile our case. Furthermore, given the fact. that Syndicated in Ding et al. (2022b) fails to recover the optimal O(VT) bound of regret without stringent assumptions under the casier setting with finite hyperparameter candidates, it would be substantially difficult to deduce feasible regret bound under our more complicated problem setting. Moreover, the non-stationarity under the switching environment would further deteriorate the optimal order of cumulative regret Cheung et al. (2019). And it is intrinsically more difficult to consider the continum-armed bandit over the multi-armed bandit. Therefore, we believe our theoretical result is non-trivia trivill and significant. Our work stands as the first seminal attempt in bandit hyperparameter tuning (or even bandit model selection) with an infinite number of candidates. An extensive study on this new problem will be an interesting future direction.
5 Experimental Results
In this section, we show by experiments that our hyperparameter tuning framework outperforms the theoretical hyperparameter setting and other tuning methods with various (generalized) linear bandit algorithms. We
9

---

Published in Transactions on Machine Learning Research (04/2024)
Simulations for UitUCB
Movielens for LinUcB
Smulltions for UntS
Movielens for LinTS
CDT
Theary
Curmuist Reggett
1000
1346
Theery
1500
CDT
Tiwory
1790
2530
CGT
Theary
DP
Ouhuistvv
840
TL
2000
TL
750-
750
208
200
1000
6300
5000
12030
2000
60:0
6000
12600
2002 Iteratoons
00300
0:00
12000
3030
6303
9035
12000
Reeraioon
Rteations
Iterations
Simulatiioss for UCB-GLM
Movielens for UCB-GILM
Sinuiaiooss for GLM-TSL
Movidens for GLM--SL.
Thoory
Theory
630
Theary
Theory
Cumuistive Recres
COT
Crmuustivve Raugr
CDT
C37
Regret
930
CDD
OP
5.0
OP
OP
OP
Cumulaative
8.0
TL
9:33
TL
330
0:3
200
220
100
1.0
230
2000
0202 Berations
5000
5500
5000
12003
5000
9202
12005
2002
12000
Berations
Simulations Laplace-TS
Movielans for Laplace-TS
Simulations
Movielens
Curtlaztv Rogret
300
106
CDT
Theory
Cumulattve WeittteeRRggeee Reggre
1.00
CDT
Theory
Curmulativ Raggrs
730
OP
Syndit aled
Syndicated
3.00
750
1200
200
2:30
220
3.00
120
lterations
Rerations
Iterations
Iterations
Simulations for SCD-T5
Movielons for SGD.TS
1260
Theary
500-
CUrTuL Dive Recgrot
3200
CDT
800
Syndicated
BG2
QP
Syndicated
Cumuistive
300
200
100-
200
30.00
6020
5000
12003
22000
Iterations
Iterations
Figure 2: Cumulative regret curves of our CDT framework compared with existing hyperparameter selection methods under multiple (generalized) linear bandit algorithms the simulations and Movielens dataset.
utilize seven state-of-the-art bandit algorithms: two of them (LinUCB [Li et al., 2010), LinTS AAgraal &
Goyal 2013 are linear bandits, and the other five algorithms MCCB-GLM Li et al. 2017), GLM-TSL Kveton
et al.
2020 Laplace-TS (Chapelle Li 2011), GLOC (Jun el al. 2017) SGD-TS (Ding el al. 2021 are
GLBs. Note that all these bandit algorithms except Laplace-TS contain an exploration rate hyperparameter, while GLOC and SGD-TS further require additional learning parameter. And Laplaco-TS only depends one stepsize hyperparameter for gradient descent optimizer. We compare our CDT framework with the theoretical setting, OP (Bouneffouf & Clacys, 2020) and TT. (Ding et al. 2022b) (one hyperparameter) and Syndicated Ding et al. 2022b) (multiple hyperparameters) algorithms. Their details are given as follows:
(1) Theoretical setting: We implement the theoretical exploration rate and stepsize for each algorithm. For the stepsize of gradient descent used in SGD-TS and Laplace-TS, we set as 1 instead. (We observe the algorithmic performance is not sensitive to this stepsize.)
(2) OP: we modify it so that it could be used in other bandit algorithms. Note that OP is only applicable to algorithms with one hyperparameter, and hence we fix the learning parameter of GLOC and SGD-TS as their theoretical values instead, and only tune the exploration rates.
(Bouneffouf & Clacys 2020) proposes OPLINUCB to tune the exploration rate of LinUCB. Here
(3) TL Ding et al. 2022b) (one hyperparameter): For algorithms with only one hyperparameter, TL. is used.
(4) Syndicated DDig et al. 2022b) (multiple hyperparameters): For GLOC and SGD-TS (two hyperparam- eters), the Syndicated framework is utilized for comparison.
We run comprehensive experiments on both simulations and real-world datasets. Specifically, for the real data, we use the benchmark Movielens 100K dataset along with the Yahoo News dataset:
10

---

Published in Transactions on Machine Learning Research (04/2024)
Table Running time (seconds) for different algorithms under settings shown in Figure
Algorithm
Setting
Theory
TL
OP
CDT
Simulation
2.11
4.01
3.70
6.89
LinUCB
Movielens
2.17
3.87
2.95
7.31
Simulation
2.21
4.10
3.95
7.63
LinTS
Movielens
2.04
4.09
3.45
7.71
Simulation
7.74
9.84
9.71
12.67
UCB-GIM
Movielens
7.89
9.64
9.35
13.05
Simulation
304.28
306.98
306.02
309.54
GLM-TSL
Movielens
294.17
295.87
294.83
298.81
Simulation
523.62
526.31
526.24
531.15
Laplace-T1 TS
Movielens
500.19
503.45
503.91
509.65
Simulation
486.58
489.31
490.24
593.15
GLOC
Movielens
474.87
476.52
477.16
481.03
Simulation 67.42
70.62
69.42
73.68
SGD-TS
Movielens
62.09
66.48
64.68
67.31
(1) Simulation: In each repetition, we simulate all the feature vectors (Ft,a) and the model parameter 0" according to Uniform(11//5A///V elementwisely, and hence we have || S We set =25, K =120 and =14,000. For linear model, the expected reward of arm a formulated as xT,a0" and random noise is sampled from (0, 0.25); for Logistic model, the mean reward of arm defined and the output is drawn from Bernoulli distribution.
p p= 1/(1 + exp(-ar7,a
(2) Movielens 100K dataset: This dataset contains 100K ratings from 943 users on 1,682 movies. For data pre-processing, we utilize LIBPMF (Yu et al. 2014) to perform matrix factorization and obtain the feature matrices for both users and movics with d 220, and then normalize all feature vectors into unit r-dimensional ball. In each repetition, the model parameter 0" is defined as the average of 300 randomly chosen users' feature vectors. And for each time t, we randomly choose K 300 movies from 1,682 available fcature vectors arms { The time horizon T is set to 14,000. For lincar models, the expected reward of arm is formulated as x o and random noise is sampled from (0, 0.5); for Logistic model, the output of arm a is drawn from the Bernoulli distribution with p 1/(1 + exp(-xI,.0"))
1,000
(3) Yahoo News dataset: We downloaded the Yahoo Recommendation dataset R6A, which contains Yahoo data from May 1 to May 10, 2009 with T = 2881 timestamps. For cach user's visit, the module will select one article from a pool of 20 articles for the user, and then the user will decide whet to click. We transform the contextual information into a 6-dimensional vector based on the processing in (Chu et al., 2009). We build a Logistic bandit on this data, and the observed reward is simulated from a Bernoulli distribution with a probability of success equal to its click thrk-through rate each time.
We first present the results on simulations and Movielens datasets: since all the existing tuning algo- rithms require a user-defined candidate set, we design the tuning set for all potential hyperparameters 10.1, 3, 4, 5). And for CDT framework, which is the first algorithm for tuning hyperparameters in interval, simply set the interval as [0.1,5] for all hyperparameters. Each experiment is repeated for 20 times, and the average regret curves with standard deviation are displayed in Figure 2 We further explore the existing methods after enlarging the hyperparameter candidate set to fairly validate the superiority of our proposed CDT in Appendix A.4.1 The results in Appendix A.4.1 further lead to discussion on why it is inefficient to first. discretize the continuous space and then implement an algorithm (e.g. Syndicated) with discrete candidate sets.
We believe large value of warm-up period T, may abandon some useful information in practice, and hence we use T, T2/(p+3) according to Theorem 4.2 in experiments. And we would restart our hyperparameter tuning layer after every T, = (7(++))(p++) rounds. An ablation study on the rolc of T₁ T2 in our CDT framework is also conducted and deferred to Appendix [A.4.2 where we demonstrate that the performance of CDT is pretty robust to the choice Tí, T3 in practice.
11

---

Published in Transactions on Machine Learning Research (04/2024)
From Figure 2 observe that our CDT framework outperforms all existing hyperparameter tuning methods for most contextual bandit algorithms. It is also clear that CDT performs stably and soundly with the smallest standard deviation across most datasets (e.g. experiments for Lin'I', UCB-GLM), indicating that our method is highly flexible and robustly adaptive to different datasets. Morcover, when tuning multiple hyperparameters (GLOC, SGD-TS), we can see that the advantage of our CDT also evident since our method is intrinsically designed for any hyperparameter space. is also verified that the theoretical hyperparamcter values are too conservative and would lead to terrible performance (e.g. LinUCB, LinTS). Note that all tuning methods exhibit similar results when applied to Laplace-TS. We believe it is because Laplace-TT TS only relies on an insensitive hyperparameter that controls the stepsize in gradient descent loops, which mostly affects the convergence speed. To further validate the high efficiency of our proposed CDT, we also report the computational running time for the 14 cases corresponding to Figure 2 Specifically, we display the average running time on each method in Table ! We can observe that all existing methods and our CDT can run very fast practice, and our CDT only slightly more expensive than TL and OP in computation (CDT only takes about four more seconds) since the procedure of removal, restarting and activation checks at each round would take some extra computation. In addition, comes from the contextual bandit algorithm want to tune on, as is shown that, e.g. GLM-TSL requires much more time than all other methods under different tuning methods. Therefore, we can conclude that our CDT significanlly purperfrms all existing baselines without increasing computational time.
can conclude that the main computation time
For the Yahoo News Recommenaation dataset, since it is a logistic bandit, we only output the cumulative rewards of GLBs in Table [ From the table, we can observe that our proposed CDT also performs the best overall. Specifically; it is only slightly worse than TL. for GLM-TSLL and GL.OC, and yields the best. results among all hyperparameter tuning frameworks for UCB-GLM, GLM-TSL, and SGD-TS. And the theoretical hypreparameter setting is very unstable again as in Figure 2 Conclusively, our proposed CDT yields uniformly the best performances compared with existing baselines in both large-scale and mild-scale experiments with multiple contextual bandit algorithms. This fact also validates the rationality of Lipschitz continuity assumption on the bandit hyperparameter tuning problem in Section 3
Method
UCB-GLM
GLM-TSL
Laplace-Te TS
GLOC
SGD-TS
Theory
221.51
214.67
217.38
206.73
CDT
221.69
218.27
217.05
217.95
218.35
OP
217.25
217.08
213.95
216.28
215.58
/T/Synnicated
218.95
219.36
214.42
218.19
215.02
Table 2: Comparisons of cumulative rewards from different algorithms on Yahoo dataset.
6 Conclusion
In this paper, we propose the first online continuous hyperparameter optimization method for contextual bandit algorithms named CDT given the continuous hyperparameter search space. Our framework can attain sublinear regret bound in theory, and is general enough handle the hyperparameter tuning task for most contextual bandit algorithms. Multiple synthetic and real experiments with multiple GLB algorithms validate the remarkable efficiency of our framework compared with existing methods in practice. In the meanwhile, we propose the Zooming TS algorithm with Restarts, which is the first work on Lipschitz bandits under the switching environment.
Limitations and future works: Beyond the hyperparameter selection, our work paves the way for exploring the broader problem of bandit model selection within a continuous candidate space. Another promising avenue for future investigation involves conducting a comprehensive study on the non-stationary Lipschitz bandit problem. The examination of lower bounds for these two novel directions falls outside the purview of our study but remains intriguing for further exploration.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Acknowledgments
We appreciate the insightful comments from the TMLR reviewers and the action editor. This work was partially supported by the National Science Foundation under grants CCF-1934568, DMS-1916125, DMS-211360$ DMS-2210388, L1S-2008173 and LIS-2048280.
References
Yasin Abbasi- Yadkoi, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neurol information processing systems, 24, 2011.
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence ond Statistics, pp. 184. PMLR, 2017.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pp. 12-38. PMLR, 2017.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Procoedings, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. International conference on machine learning, pp. 127-135. PMLR, 2013.
Peter Auer, Nicolo BiannBia and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2))235-28) 256, 2002a.
Peter Auer, Nicolo Cesa- Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002b.
Hamsa Bastani and Mohsen Bayati. Online decision making with nigh-ddimensional covariates. Operations Research, 68(1):276-29) 2020.
Djallel Bouneffouf and Emmanuelle Claeys. Jypeer-arraeetrr tuning for the contextual bandit. arXic preprint arXiv:2005.0920 2020.
Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, and Rémi Munos. Online optimization in x-armed bandits. Advances in Neural Information Processing Systems, 21, 2008.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1079 1087. PMLR, 2019.
Wei Chu, Soung- Tack Park, Todd Beaupre, Nitin Motgi, Amit Phadke, Scinjuti Chakraborty, and Joe Zachariah. A case study of behavior-driven conjoint analysis on yahoo! front page today module. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 1097 1104, 2009.
Soung-Tack
Qin Ding, Cho-Jui Hsich, and James Sharpnack. An efficient algorithm for genoralized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1585 1593. PMLR, 2021.
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 7111-7123. PMLR, 2022a.
Qin Ding, Yue Kang, Yi-Wei Liu, Thomas Chun Man Lee, Cho-Jui Hsich, and James Sharpnack. Syndicatod in contextual bandit algorithms. Advonces in
bandits: A framework for auto tuning Neural Information Processing Systems, 35:1170-1188 1181, 2022b.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pp- 586-594, 2010.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Peter I Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.02811 2018.
Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. Mots: Minimax optimal thompson sampling. In International Conference on Machine Learning, pp. 5074-5083. PMLR, 2021.
Swaan--Sug Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. Advances Neural Information Processing Systems, 30, 2017.
Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference Machine Learning, pp. 3163 3172. PMLR, 2019.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low-rank matrix bandit problems. Advances in Neural Information Processing Systems, 35:19911-19983, 2022.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. In Thirth-seventhh Conference on Neural Information Processing Systems, 2023. URL htttps//oppnreviai net/foruumPiddsRiilllkky
Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Newral Information Processing Systems, 17, 2004.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavanzadeh, and Craig Boutilier. Randomized exploration in generalized lincar bandits. In International Conference on Artificial Intelligence and Statistics, pp. 2066 2076. PMLR, 2020.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandii approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2071 2080. PMLR, 2017.
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. International Conference on Artificial Intelligence and Statistics, pp. 1306-1314. PMLR, 2021.
Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithms for lipschitz bandits with heavy-tailed rewards. In International Conference on Machine Learning, pp. 4154-4163. PMLR, 2019.
Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pp. 975 999. PMLR, 2014.
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXi::2012. 13044, 2020.
Chara Podimata and Alex Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pp. 3788 3805. PMLR, 2021.
Amr Sharaf and Hal Daumé III. Meta-learning for contextual bandit exploration. arxiv preprint 2019.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Mervyn Stone. Cross-validatoory choice and assessment of statistical predictions. Journal of the royal statistical sociely: Series B (Methodologicnl), 36(2):111-133, 1974.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultancous optimistic optimization. International Conference on Machine Learning, pp. 19 27. PMLRR 2013.
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pp. 5114 5122. PMLR, 2018
Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in non-stationary stochastic environments. Advances in newral information processing systems, 29, 2016.
Michael Woodroofe. A one-armed bandit problem with concomitant variable. Journal of the Americon Statistical Association, 74(368))799-806 1979.
Hsiang-Fu Yu, Cho-Jui Hsieh, Si Si, and Inderjit S Dhillon. Parallel matrix factorization for recommender systems. Knowledge and Information Systems, 41(3):793 819, 2014.
Lijun Zhang, Tianbao Yang. Rong Jin, Yichi Xiao, and Zui-Hua Zhou. Online stochastic linear optimization under one-bit leedback. In International Conference on Machine Learning, pp.
PMLR, 2016.
Peng Zhao, Lijum Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 746 755. PMLR, 2020.
15

---

Published in Transactions on Machine Learning Research (04/2024)
A Supportive Experimental Details
A.1 Simulations on the Optimal Hyperparameter Value in Grid Search
To further validate the necessity of dynamic hyperparameter tuning, we conduct a simulation for UCB algorithms LinUCB, UCB-GLM, GLOC and TS algorithms LinTS, GLM-TSL with a grid search exploration parameter in {0.1, 0.5, 1, 1,, 2..... .......00) f0} and then report the best parameter value under different settings. Specifically, we set 10, T 8000, K 60, 120, and choose arm Tt,a and H* randomly in {ar |||||| & 1}. Rewards are simulated from N= 0.5) for LinUCB, LinTS, and from Bernoulli(1/C) + exp (- (*)) for UCB-GLM, GLOC and GLM-TSL. The results displayed in Table 3 where we see that the optimal hyperparameter values are distinct and far from the thcoretical oncs under different algorithms or scttings. Moreover, the theoretical optimal exploration rate should be identical under different values of K for most algorithms shown here, but in practice the best hyperparameter to use depends on K, which also contradicts with the theoretical result.
Bandit type
Linear bandit
Generalized linear bandit
Algorithm
LinUCB
TinTS
UCB-GLM
GLOC
GLM-TSL,
K 60
2.5
1.5
4.5
1.5
K = 120
3
1.5
2.5
5
2
Table The optimal exploration parameter value in grid search for LinUCB, LinTS, UCB-GLM, GLOC and GLM-TSL. based on average cumulative regret of repeated simulations.
A.2 Simulations to Validate the Lipschitzness of Hyperparameter Configuration
We also conduct another simulation to show it is reasonable and fair to assume the expected reward an almost- stationary Lipschitz function w.r.t. hyperparameter values. Specifically, we set d = 6, 3000, K 60, and for each time we run LinUCB and LinTS by using our CDT framework, but also obtain the results by choosing the exploration hyperparameter in the set (0.3, 0.45, 0.6,... 8.85,91 9} respectively. For the first. 200 rounds we use the random selection for sufficient exploration, and hence we omit the results for the first 200 rounds. After the warming-up period, we divide the rest of iterations into 140 groups uniformly, where each group contains 20 consecutive iterations. Then we calculate the mean of the obtained reward of each hyperparameter value in the adjacent 20 rounds, and centralize the mean reward across different. hyperparameters in each group (we call it group mean reward). Afterward, standard deviation of the group mean reward for different hyperparameter values across all groups. The results are shown in Figure 3 where we can see the group mean reward can be decently represented by a stationary Lipschitz continuous function w.r.t hyperparameter values. Conclusively, we could formulato the hyperparameter optimization problem as a stationary Lipschitz bandit after sufficient exploration in the long run. And in the very beginning we can safely believe there is also only finite number of change points. This fact firmly authenticates our problem setting and assumptions.
calculate the mean and
A.3 Simulations for Algorithm
We also conduct empirical studics to evaluate our proposed Zooming TS algorithm with Restarts (Algorithm I in practice. Here we generate the dataset under the switching environment, and abruptly change the underlying mean function for several times within the time horizon T. The methods used for comparison well as the simulation setting are elaborated as follows:
Methods. We compare our Algorithm (we call it Zooming TS-R for abbreviation) with two contenders: (1) Zooming algorithm [Kleineerg et al. 2019): this algorithm is designed for the static Lipschitz bandit, and would fail in theory under the switchiing environment; (2) Oracle: we assume this algorithm knows the exact time for all switching points, and would renew the Zooming algorithm when reaching a new stationary environment. Although this algorithm could naturally perform well, but it is infeasible in reality. Therefore,
16

---

Published in Transactions on Machine Learning Research (04/2024)
Simulations for LinUCB
Simulations for LinTS
0.06
0.06
Centralized mean regret
Centralized mean regret
0.04
0.04
0.02
0.02
0.00
0.00
-0.02
-0.02
-0.04
-0.04
1.5
1.05
0
1
3
0
1
3
Iterations
Iterations
Figure 3: Average cumulative regret and its standard deviation of group mean reward for different hyperpa- rameter values across all groups.
we would just use Oracle as skyline here, and a direct comparison between Oracle and our Algorithm ! is inappropriate.
Settings. Assume the set of arm is [0,1]. The unknown mean function fe(x) is cho- sen from two classes of reward functions with different smoothness around their maximum: (1) (0.9 0.9 al,2
0.05, 0.25, 0.45, 0.70, 0.95] (triangle function); (2) 1 sin (x a ))) x [0 0.05, 0.25, 0.45, 0.70, 0.70,0.95) We set T = 90, 000 and c(T' 3, and choose the location of changing points at random in the very beginning. The random noise is generated according to NN, 0.1). The value of epoch size H is set as suggested by our theory H (0 For each class of reward functions, we run the simulations for 20 times and report the average cumulative regret as well as the standard deviation for each contender in Figure (The change points are fixed for each repetition to make the average value meaningful.)
[0,1]
Figure 4 shows the performance comparisons of three different methods under the switching environment measured by the average cumulative regret. We can see that Oracle is undoubtedly the best since it knows the exact times for all change points and hence restart our Zooming TS algorithm accordingly. The traditional Zooming algorithm ranks the last w.r.t both mean and standard deviation since it doesn't take the non- stationarity issue into account at all, and would definitely fail when the environment changes. This fact also coincides with our expectation precisely. Our proposed algorithm has an obvious advantage over the traditional Zooming algorithm when the change points exist, and we can see that our algorithm could adapt to the environment change quickly and smoothly.
A.4 Additional Details and Results for Section 5
A.4.1 Baselines with Large Candidate Set
To further make a fair comparison and validate the high superiority of our proposed CDT framework over the existing OP, TL. (or Syndicated) which relies on a user-defined hyperparameter candidate set, we explore whether CDT will consistently outperform if baselines are running with a large tuning sot. Here we replace the original tuning set C (0.1, 1, 2,3, 4,5) with finer set C2 = (0.1, 0.25, 0.5, 0.75, 1, 1.5, 2, 2.5, 3,5., 4, 4.5,5). And the new results are shown in the following Table g (original results in Section are in gray).
Therefore, we can observe that the performance overall becomes worse under C2 compared with the original C.. In other words, adding lots of elements to the tuning set will not help improve the performance of existing algorithms. We believe this because the theoretical regret bound TL (Syndicated) also depends on the number of candidates & in terms of Vk (Ding et al. 2022b). There no thcoretical guarantce for OP. After introducing so many redundant values in the candidate set, the TL (Syndicated) and OP algorithms would get disturbed and waste lots of concentration those unnecessary candidates.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Candidate Set
C1
Algorithm
Sctting
TL/Syndicated
OP
TI S.//ydidiatedd
OP
Simulations
343.
383.62
356.23
389.91
LinUCB
Movielens
346. 16
390.10
359.10 10
408.67
Simulations
828.41
869.30
874.34
925.29
LinTS
Movielens
519.09
666.35
516.62
667.77
Simulations
271.45
350.85
298.68
367.97
UCB-GLM
Movielens
381.00
397.58
406.29
412.62
Simulations
433.27
445.43
448.21
458.71
GLM-TSL.
Movielens
446.74
678.91
458.23
718.46
Simulations
510.03
568.81
530.29
567.10
Laplace-TS
Movielens
949.51
1063.92
958.10 10
1009.23
Simulations
406.28
417.30
414.82
427.05
GLOC
Movielens
571.36
513.90
568.91
520.72
Simulations
448.29
551.63
458.09
557.04
SGD-TS
Movielens
1016.72
1084.13
1038.94
1073.91
Table 4: Cumulative regrets of baselines under different hyperparameter tuning sets.
In conclusion, we believe the existing algorithms relying on user-tuned candidate sets would perform well if the size the candidate set is reasonable and the candidate set contains some value very close to the optimal hyperparameter value. However, practice, finding the unknown optimal hyperparameter value is black-box problem, and it's impossible to construct candidate set satisfying the above requirements the beginning. If discretize the interval finely, then the large size of the candidate set would hurt the performance well. On the other hand, proposed CDT could adaptively "zoom in" on the regions containing this optimal hyperparameter value automatically, without the need of pre-specifying "good" set of hyperparameters. And CDT could always yield robust results according to the extensive experiments we did in Section 5
On the other hand, these results also imply an interesting fact. Note it doable to first discretize the continuous space and then implement an algorithm with discrete candidate sets, such as Syndicated (Ding observe that finely discretizing the hyperparameter space will significantly hurt the practical performance and hence is wasteful and inefficient. Intuitively, it is inefficient to place lots of "probes" in other regions that do not contain the optimal point, and we should place probes in more promising regions via adaptive discretization methodology. In theory, the uniform discretization idea will lead to regret bound of order T T with covering dimension d and the zooming idea will ineur T T regret with zooming dimension d2, and we know d, < d and d, could be significantly smaller than d under various cases. Therefore, we believe the same phenomena will occur in the non-stationary Lipschitz bandits and also our hyperparameter tuning framework as well.
et al. 2022b). However,
A.4.2 Ablation Study on the Choice of Ti and Ta
For Tı, we set it to 72/(x+3) where p stands for the number of hyperparameters according to Theorem 4.2 Specifically, for LinUCB, LinTS, UCB-GLM, GLM-TSL and Laplace-TS, we choose it to be 118. For GLOC and SGD-TS, we set as 45. Here we also rerun our experiments in Section with Ti = (no warm-up) since we believe a long warm-up period will abandon lots of useful information, and then we report the results after this chango:
We can observe that the results are almost identical from Table 5 For T2. Theorem 1.2 suggests that T2 O (T(++2)/(++)). In our original experiments, we choose T/ (Tt))))(p To take ablation study on T2 we take T, (T(++))/(p+)) for 1, 3 each experiment, and to see whether our CDT framework is robust to the choice of k.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm
Setting
Ti = 0
Ti 72/(p13)
Simulation
298.28
303.14
LinUCB
Movielens
313.29
307.19
Simulation
677.03
669.45
LinTS
Movielens
343.18
340.85
Simulation
299.74
300.54
UCB-GLM
Movielens
314.41
311.72
Simulation 339.49
333.07
GLM-TSL
Movielens 428.82
432.47
Simulation 520.29
520.35
Laplaco-Th TS
Moviclens 903.16
900.10
Simulation 414.70
418.05
GLOC
Movielens 455.39
461.78
Simulation
430.05
425.98
SGD-TS
Movielens
843.91
838.06
Table 5: Ablation study on the role of in our CDT framework.
Algorithm
Setting
k: 1
k 2
h:
Simulation
328.28
300.62
298.28
LinUCB
Moviclens
310.06
303.10
313.29
Simulation
717.77
670.90
677.03
LinTS
Movielens
360.12
352.19
38
Simulation
314.01
316.95
299.74 74
UCB-GLM
Movielens
347.92
325.58
314.41
Simulation
320.21
331.43
339.49
GLM-TSL
Movielens 439.98
428.91
428.82
Simulation
565.15
540.61
520.29
Laplace-TS TS
Movielens
948.10
891.91
903.16
Simulation
417.05
414.70
415.05
GLOC
Movielens
441.85
455.39
462.24
Simulation
450.14
430.05
414.57
SGD-TS
Movielens
852.98
843.91
830.35
Table 6: Ablation study the role of Tl in CDT framework.
According to Table D we can observe that overall & = 2 and k 3 perform better than k: == 1. We believe it is because, the long run, the optimal hyperparameter would tend be stable, and hence some restarts are unnecessary and inefficient. Note by choosing to our proposed CDT still outperforms the existing TL and OP tuning algorithms overall. For 2 and k 3, comparable, which implies that the choice of & is quite robust in practice. We believe it is due to the fact that our proposed Zooming TS algorithm could always adaptively approximate the optimal point. Although it is unknown which one is better in practice under different cases, our comprehensive simulations show that choosing either one in practice will work well and outperform all the existing methods. In conclusion, these results suggest that we have a universal way to set the values of T, and T₃ according the theoretical bounds, and do not need to tune them for each particular dataset. In other words, the performance of our CDT tuning framework is robust to the choice of Ti, T2 under different scenarios.
observe that their performances are
19

---

Published in Transactions on Machine Learning Research (04/2024)
B
Supportive Remarks
Remark B.1. (Justifications on assumptions) We further explain the motivations of the Lipschitzness and piecewise stationarily assumptions of the expected reward function for hyperparameter tuning of bandit. algorithms.
For Lipschitzness, we get the motivation of our formulation shown in Equ. 3 and Eqn. from the hyperparameter tuning work on the offline machine learning algorithms. Specifically, Bayesian optimization is widely considered as the statc-of-the-art and most popular hyperparameter tuning method, which assumes that the underlying function is sampled from a Gaussian process in the given space. By selecting a value æ in the space and obtaining the corresponding reward, Bayesian optimization could update its estimation of the underlying function, especially in the neighbor of sequentially. And it also relies on user-defined kernel function, whose selection is also purely empirical and lacks theoretical support. In our work, we use a similar idea as Bayesian optimization: ion: close hyperparameters tend to yield similar values with other conditions fixed. And this natural extension motivates the Lipschitz assumption made in our paper. Therefore, it is fair to make a similar and analogous assumption (close hyperparameters yicld similar results given other conditions lixed) for the hyperparameter luning of bandit. algorithms in our work. We validate this assumption using a suite of simulations in Appendix
For the piecewise stationarity, we mention in Section 3 it is inappropriate to assume the strict stationarity of the bandit algorithm performance under the same hyperparameter value setting across time T. As an example, for most UCB and TS-based bandit algorithms (e.g. LinUCB, Lin UCB-GLM, GLM-UCB, GLM-TSL, etc.), the exploration degree of an arm is a multiplier of the exploration rate and the uncertainty of an arm. In the beginning, a moderate value of the exploration rate may lead to a large exploration degree for the arm since the uncertainty is large. On the contrary, in the long run, a moderate value of exploration rate will lead to a minor exploration degrec for the arm since its value has been well estimatod with small uncertainty. Therefore, fixed hyperparameter setting may suggest different results across different stages of time, and hence it is unreasonable to expect the strong stationarity of the hyperparameter tuning for bandit algorithms at all time steps. On the other hand, it would be very inefficient to assume a completely non-stationary environment as in Ding et al. 2022b) which uses EXP3. In very close time steps, we could anticipate that the same hyperparameter setting would yield a very similar result. in expectation since the uncertainty of any arm would be close. And using a non-stationary environment will totally waste this information and hence is inefficient. Therefore, it is very well motivated to use a partial non-stationarity assumption that lies in the middle ground between the above two extremes. Note our proposed tuning method yields very promising results in extensive experiments under our formulations. And the stationary euvironment can be regarded as a special case of our switching environment setting where the functions in between all change points are the same.
Finally, we will explain why it is excessively difficult to present thcorctical validation regarding these assumptions in our paper. As we mentioned, our formulation is motivated by Bayesian optimization, arguably the most popular method for hyperparameter tuning for offline machine learning algorithms. And we use a similar idea: similar hyperparameters tend to yield similar values while other conditions are fixed. However, people could hardly provide any theory backing for the analogous assumption of Bayesian optimization for any offline machine learning algorithms (e.g. regression, classification), and hyperparameter tuning is widely considered as black-box problem for offline machine learning algorithms. Not to mention that the thcoretical analysis of hyperparamoter tuning for any bandit algorithm is much more challenging than that of oflline machine learning algorithms since historical observations along with hyperparameter values will alfect the online selection simultancously for the bandit algorithms, and we can use different hyperparameters different rounds for bandit algorithms. Conclusively, our formulation is natural and mell-motivated.
C Detailed Proof on the Zooming Dimension
In the beginning, we would reload some notations for simplicity. Here we could omit the time subscript (or superscript) since the following result could be identically proved for each round t. Assume the Lipschitz function f is defined RPc, and s² = arg max f(v) denotes the maximal point (w.lo.g. assume it's
20

---

Published in Transactions on Machine Learning Research (04/2024)
unique), and ( f(v))-((v) is the "badness" of the arm We then naturally denote A, the r-optimal region at the scale (0, 1), i.e. A, {u denoted as (r). And the zooming dimension could be naturally denoted as Ps. Note that by the Assouad's embedding theorem, any compact doubling metric space (A, (..is(((..)) can be embedded into the Euclidean space with some type of metric. Therefore, for all compact doubling metric spaces with cover dimension Pe: it is sufficient to study on the metric space ([0, 1|",, I1-11") for some I (0, +00] instcad.
A r < A(v) S rr). The r-zooming number could be
We will rigorously prove the following two facts regarding the r-zooming number (r(r) of (A, f) for arbitrary compact set A C _e and Lipschitz function f(-) defined on A:
Ps Po.
The zooming dimension could be much smaller than Pe under some mild conditions. For example, the payoff function f greater than ||o* - =II in scale in a (non-trivial) neighborhood of o for some B 2 L, i.e. f(u*)- f(v) 2 C(Ile* - =Il") as ||o -vl S r for some C > 0 and r = @(),, then it holds that P3 I (1-1/8)pe Note 3 = when we have f(.) is C2-smooth and strongly concave in a neighborhood of v*, which subsequently implies that Ps S Pc/2.
Proof. Due to the compactness of A, it suffices to prove the results when A = 10, 1]a By the definition of the zooming dimension pz, it naturally holds that 2 0. On the other side, since the space A is closed and bounded set RP' we assume the radius of A is no more than S, which consequently implies that the r/ 1/16-covering number of is most the order of
S Pc. 16
(168)) Po.
Since we know A, S A, it holds that ps S p. Secondly, the payoff function ʃ is locally greater than | u|l in scale for some $ 2 I, ie. f(v*) f(v) C(Ilo* - -Il ) then there exists C' e R and å > 0 such that as long as C [|l - 0e lls s we have f(v²) f(v)= 2 C/Ilu- - o- pl Therefore, for 0 < r < 6, it holds that,
f(e) > r/2) S (v ClIv w1 sr) = {o ||u 1Iu
[())
(u (v:r2
1---v-11 00
It holds that the r-covering number of the Euclidean ball with center of and radius (r/c) is of the order of
(8)
16
Pe
-r - (1 3)
T6
F
C7
which explicitly implies that Ps S (1-1/8)p--
D Intuition of our Thompson Sampling update
Intuitively, we consider Gaussian likelihood function and Gaussian conjugate prior to design our Thompson Sampling version of zooming algorithm, and here we would ignore the clipping step for explanation. Suppose the likelihood of reward 5t at time I, given the mean of reward I(v.) for our pulled arm ut follows Gaussian distribution ((T())), x8). Then, if the prior of ((x)) at time t is given by N(f((v)), / (v())), could easily compute the posterior distribution at time t+1. 1,
Pr([(v:) ()) x Pr((l((e))PP(((()())
as N(f++1(ve). 26 (8/m+1(V))).. We can see this result coincides with our design in Algorithm I and its proof is follows:
21

---

Published in Transactions on Machine Learning Research (04/2024)
Figure 4: Cumulative regret plots of Zoomiing TS-R, Zooming and Oracle algorithms under the switching
environment.
Simulations for triangle functions
Simulations for sine functions
6000
Zooming
Zooming
Cumulative Regret
Cumulative Regret
2500
5000
Zooming TS-R
Zooming TS-R
Oracle
2000
Oracle
4000
1500
3000
2000
1000
1000
500
01
20000
40000
60000
80000
20000
40000
60000
80000
Iterations
Iterations
Proof.
Pr(I(v)))G & Pr((i(((s)))P(((((()))
(!(ve) T0)² +m(())(((()) -
exp
280
1 [vr) + 1))((r)² 2( +n(tr)f(oo)))(
exp
25h
Me+1 (w))
[(ur)² -2
(Te m((=))(((()) Now)
exp
2s
mot1(ve)
(1+1(2))
(I(v)) -ft11(1)))
exp
2sB
Therefore, the posterior distribution of [(ve) at time t is N(f+ta 88 (
This gives us an intuitive explanation why our Zooming TS algorithm works well when we ignore the clipped distribution step. And we have stated that this clipping step is inevitable in Lipschitz bandit setting in our main paper since (1) we'd like to avoid underestimation of good active arms, i.c. avoid the case when their posterior samples are too small. (2) We could at most adaptively zoom in the regions which contains v* instead of exactly detecting v", and this inevitable loss could be mitigated by setting a lower bound for TS postorior samples. Note that although the intuition of our Zooming TS algorithm comes from the case where contextual bandit rewards follow a Gaussian distribution, we also prove that our algorithm can achieve a decent regret bound under the switching environment and the optimal instance-dependent regret bound under the stationary Lipschitz bandit setting.
E Proof of Theorem 4.1
E.1
Stationary Environment Case
will first focus on the stationary case, where f. = f. Vt [T]. When the environment is stationary, could omit the subscript (or superscript) t in some notations as in Section C for simplicity: Assume the Lipschitz function is f, and v² = max f(v) denotes the maximal point (w.l.o.g. assume it's unique), and A(v) f(v*) - [(v) is the "badness" of the arm v. We then naturally denote A, as the r-optimal region at the scale r e (0, 1), ie. A, = {u E A : < A(v) r). The r-zooming number could be denoted as Nr(r). And the zooming dimension could be naturally denoted as pa- Note we could omit the subscript (or superscript) for the notations just mentioned above since all these values would be fixed through all rounds under the stationary environment.
To prove Theorem 4.1
22

---

Published in Transactions on Machine Learning Research (04/2024)
E.1.1 Useful Lemmas and Corollaries
Recall that (((v) is the average observed reward for arm v E A by time t. And we call all the observations (pulled arms and observed rewards) over T total rounds as a process.
Definition E.1. We call it clean process, if for each time E [T] and each strategy E A that has been played at least once at any time t, we have (f((v) - f(u)) S rv(v).
Lemma E.2. The probability that, process is clean, is at least - 1/T.
Proof. Fix some arm v. Recall that each time algorithm plays arm v, the reward is sampled TTD from some distribution P., Define random variables Us, for 1 S S T as follows: for S nT(C), Uv is the reward from the s-th time arm is played, and for > (v) it is an independent sample from Pr. For each k < T we can apply Chernoff bounds to {Ue,s 1 S I k} and obtain that:
k Σ k
13Th In
13TH In T
Pr
Uv. - f(0)
2 V
S 2 exp
2k
2TT
2k
13
= =
In T
=
-72..
3.25 < T
(7)
4
since we can trivially assume that T 2 16. Let be the number of arms activated all over rounds T; note that T. Define X-valued random variables {ai){= as follows: Tÿ is the Nin(j,N)tth) arm activated by time T. For any x E A and j S T, the event {a = xو} is independent of the random variables {Ua.)): the former event depends only on payoffs observed before z activated, while the latter set of random variables has dependence
payoffs of arms other than x. Therefore, Eqn. equation is still valid if we replace the probability the left side with conditional probability, conditioned on the event {i zz}. Taking the union bound over all k S T, it follows that:
Pr(Vt S T, (f()) fa(v)l ( (n(()) = 21 WEEAjER
Integrating over all arms we get
Pr(ve S T, f((2))) (n(z,) Vje
Finally, we take the union bound over all T, and it holds that,
Pr(vt < TT. < T. f(z)) f((=))) rx())) 21-7
and this obviously implies the result.
Lemma E.3. If it is a clean process, then E (T) and arm u that is aclive at vound I, given that v² E r(v)).(v)).
could never be eliminated from Algorithm 1 for any
Proof. Recall that from Algorithm 1 at round t the ball B(u, re())) would be permanently removed we have for some active arm 0 s.t.
f((v) 1 re(e) > f(()) + (r).
If we have that v" = arg max REA f(x) E r()),, then it holds that
f((u)) + (u) 2 f() + (u) 2 f(u) + Dist(u, u²) 2 f(o"),
where the first inequality is due to the clean process and the last one comes from the fact that f is Lipschitz function. On the other hand we have that for any active arm v,
f(v) 2 f.(w)) - re(w), f(v)) 2 f(v).
Therefore, it holds that
f(v)-n(( s f((x)) + 2r.(u).
And this inequality concludes our proof.
23

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma E.4. If it is clean process, then for any time t and any active strategy v that has been played at least once before lime we have ((v) s 5B(rz(v)]- Purthermore, it holds that B((r(v)) S O(nn (T)/A(v)²).
Proof. Let St be the set of all arms that are active at time t. Suppose an arm i is played at time t and was previously played at least twice before time t. Firstly, We would claim that
f(o") - I((e)) - f(v) + (r
holds uniformly for all with probability least 1 1-6, 6, which directly implies that A(v)) S (rx( with high probability uniformly. First we show that 12(v)) 2 f(e*). Indeed, recall that all arms are covered time t, there exists an active arm of that covers v", meaning that 8" is contained in the confidence ball of eg. And based on Lemma E.3 the confidence ball containing v" could never be eliminated at round & when it's a clean process. Recall Zt,0 is the i.idd standard normal random variable used for any arm v in round t (Eqn. equation 66. Since arm 2 was chosen over ut, we have (vr)) 2 Le(z). Since this is a clean process, it follows that
- soy mi(uz) 2en 2 f(v)) = ne(uf)
Zeot 20 re(of)
(8)
Furthermore, according to the Lipschitz property we have
(estt, u²) f(xf) 2 f(v)) - Dist(u,,
-
(9)
Combine Eqn. equation g and equation 9 we have
((v)) 2 T((v)) f(v²) + Vo me(17)
Zen 2rr(((²)
52TTO In (T) n4 (x(x))
V2nT -
= =(((²) +
2 {(v*),
(10)
where we get the last incquality since we truncate the random variable Zi,oz by the lower bound 1/ 1/v2T according to the definition. On the other hand, we have
1 Ze,, = f(e)) + (1 11+222TZeN re((t)
1(ve) S f(v)) +re(e) + so ne(ve)
(11)
Therefore, by combining Equ. equation 10 and equation 11 we have that
A(v:) < (1 2v
2 Ze. re(1)).
(12)
And we know that Ze:: is defined as Z, = max(1/V22 Ze,t where Ze,: is IID drawn from standard normal distribution. In herer words, Ze,,, follows a clipped normal distribution with the following PDF:
((xx) - (1- (x))) (x- F
f(x)
V
0,
F
Here (6-) and (--) denote the PDF and CDF of standard normal distribution. And have
1
+00
2 π
E B(Z,,.))
z (o(()dr= <
4m
22T
/2m
2n
v2*
By taking expectation Equ. equation
12
have A(v:) < 5E(rx(v))) Next, would show that
E(n,(v))) s ((0 (T))) Based on Eqn. equation 11 and the definition of r.(-), we could deduce that
13 In
Vn((v)) <
2
A(v))
24

---

Published in Transactions on Machine Learning Research (04/2024)
which thus implics that
13 (1) 2222 m,
(v) -
2 To
- O(In (7)) + -22 A(ve)²
(13)
A(e))
By simple calculation, we could show that
B(Z
$
+
x² (x))d - - -- x
1 1
2 E E 211+222 $1+442m
8x < +00.
π
After revisiting Eqn. equation 13 we can show that (v:) S 0(I (T)) Now suppose arm e is only played once time then (v) >> 1 and thus the lemma naturally holds. Otherwise, let be the last time arm has been played according the selection rule, where we have rx(t) (v), and then based Eqn. equation 11 it holds that
((v) f(v) (1+2V27Ze,) m((e).
And then we could show that Auv) s 5B(r(v))). By using an identical argument as before, we could show that (()((v)) & O(I (T))/A(o)?.
Lemma E.5. Let XI,..., Xn be independent o2-sub-Gaussian Gaussian random variables. Then for every > 0,
max X,
20 20 (T) +t) se
1.S,0
Proof. Let 20 (1) + [), we have
P max X; 2 P(Bi, 2 u) S Σ P(X: 2 u) $ ne 20 =
1.Sm
E.1.2 Proof of Theorem 4.1 under stationary environment
Proof. By Lemma E.2 know that is clean process with probability at least 1 4. In other words. denote the event Ω = (clean process), and then we have that P(2) 2 11-1 J. And according to Lemma E.3 we're aware that the active confidence balls containing the best arm can't be removed in clean process. Remember that we use Sr as the set of all arms that are active in the end, and denote
B = fUESS 2
1 Aww)
< 2 where Sr U B
1=0
where 2 0. Then, under the event Qt by using Corollary E.4 we have ((nr())))) ((TT))A(()) and hence it holds that
Σ {())((r())())>> s T(I Σ VE
vEB,, A 5)(nn))22 Ba.l
Denote r; = 2-1 we have
Σ
(())(((()) 00n Bu
V
25

---

Published in Transactions on Machine Learning Research (04/2024)
Next, would show that for any active arms u, v we have
Dist(u, v) > 1 A 2T In (T)
min A(v))
(14)
with probability at least 1- 7. W.l.o.g assume u has been activated before u. Let s be the time when has been activated. Then by the philosophy of our algorithm we have that Dist(u, v) > rz(e). Then according
Eqn. equation 12 in the proof Lemma E.4 it holds that r.(v) 2v2zz for some random variable Z
following the clipped standard normal distribution. Define the event = {Zt,e, < <2 In (T) for all E [T], then based on Lemma E.5 we have P(T)
7 Then under the event Y, we have rs( 2 (2 (v),
which then implies that Eqn. equation 14 holds under Y. Since for arbitrary x, y E B1T we have
Ti < S ri.
2 Axx) Srs
2
which implics that under the event T
(ast y) > 4 In (T)
min(A(x), (1)) > 8 2n In (T)
ri
Therefore, x and y should belong to different sets of (ri/8v [B,Tl= S (2(ri/8v In (T)) z O(In(T)P)er** I ) Recall (r)r) is defined as the minimal number of balls of radius no more than r required to cover A,. As a result, under the events Ω and Y, it holds that
/008//2221 2n In (T) ( diimeetteee---
follows that
Σ
(lv)
O(IT) 1 (r(r.) r₃
(15)
E,,
Therefore, based on Equ. equation
15
we have
RT(T)= = Σ (())B(n((t))
WEST
P(QNT) Σ
Σ (v) ( r
vEST
VEST
A())((T(())(
Σ (())(((())((n1))))) (8n
2
T
T
HEST:A(D)sp
(EST:
S SP +
Σ
1
Ö(cr, P22+2
Tb
{cloga(t)
S pT + +(1
Σ
cr, +2
Ti
i<loga (1)
[log 2pl
ST + O01)
Σ
c2 +1) +2
k=0
SpT + +Õ(1)
2 2
1 20) +2
1
P.+1
S PT 0(1)
+2
2p
By choosing in the scale of
1
P--2
p Ô
T
it holds that
11+1
(T =
TP:+2
26

---

Published in Transactions on Machine Learning Research (04/2024)
E.2
Switching (Non-stationary) Environment Case
Since there are c(T) change points for the enviromment Lipschitz functions fe(.), i.e.
Σ 1Bm e A fe(m) * f(41(m)]= c(T).
Given the length of epochs as H, we would have [T/H] epochs overall. And we know that among these [T/H] different epochs, most c(T) of them contain the change points. For the rest of epochs that are free of change points, the cumulative regret could be bounded by the result we just deduced for the stationary case above. And the cumulative regret in any epoch with stationary environment could be bounded +1)p... Specifically, we could partition the I' rounds into m [T/M] epochs:
T + 1,7 (wo T + 1, 1, U (2), .... U [m 1, Wm. = T 1),
where w441 wi + H for O,.... - 2. Denote all the change points Ti P1 <... Pa(T) S and then define
Ω = W|w Pg E [w;,wa1)) W:41), 1). 3j 1,............... c; i = .,..., m 1}.
Then it holds that [ < Hc(T). Therefore, it holds that
Pr.+1 RT(T) Sō ( [c(T)) + ( H P
T Ps.+1 (H(TT)
H P
where the first part bound the regret of non-stationary epochs and the second part bound that of stationary ones. By taking = (T/c(T))(P.. +2)///) +2)/(...++) it holds that
(T( S (
Ps. TP.. +3 c(T))
And this concludes our proof for Theorem
F Algorithm
1 with unknown e(T) and Pa,*
F.1
Introduction of Algorithm 3
When both the number of change points e(T)) over the total time horizon T and the zooming dimension pz.. are unknown, we could adapt the BOB idea used in Cheung el al. (2019): Zhao el al. (2020) to choose the optimal epoch size H based on the EXP3 meta algorithm. In the following, first describe how use the EXP3 algorithm to choose the epoch size dynamically even if c(T) and Ps,, unknown. Then we present the regret analysis in Theorem F.I and its proof.
Although the zooming dimension P=,. is unknown, it holds that Pz,. Pe, and hence we could simply use the upper bound of Pz,. (denoted as Pu) as instead (recall is the covering dimension). Note that the upper bound Ps,* could be more specific when we have some prior knowledge of the reward Lipschitz function f(-): for example, as we mentioned in Appendix C if the function f(-) known be - and strongly concave in a neighborhood of its maximum defined in R it holds that Ps,- S pe/2 and then we could use Pa = P./2 as the upper bound. Note that also use the BOB mechanism in the CDT framework for hyperparameter tuning in Algorithm 2 where treat the zooming TS algorithm with Restarts as the meta algorithm to select the hyperparameter setting in the upper layer, and then use the selected configuration for the bandit algorithm in the lower layer. However, here we would use BOB mechanism differently: we firstly divide the total horizon T into several epochs the same length Ho (named top epoch), where in each top epoch we would restart the Algorithm| [ And the i-th top epoch the restarting length H, (named bottom epoch) of Algorithm I could be chosen from the the chosen bottom epoch size could be adaptively tuned by using EXP3 the meta algorithm. Here we
{J+ = [k]
1, Ho/2i-1 /2--1___ 2......, }, where
27

---

Published in Transactions on Machine Learning Research (04/2024)
fixed Ho
Zooming TS with (H1)
top epoch 1
10
C
EXP3 chooses H; from the candidate
Zooming TS with Restarts(Hz)
top epoch
|e
C
:
set J adaptively
C
Zooming TS with (estarss(H(7/aa)
top epoch [T/Ho]
Apyma ...
Figure 5: An illustration of Zooming TS algorithm with double restarts when c(T) agnostic.
restart the zooming TS algorithm from two perspectives, where we first restart the zooming TS algorithu with Restarts (Algorithm 1 in each top epoch of some fixed length Ha, and then for each top epoch the restarting length H; for Algorithm D would be tuned the fly based on the previous observations (Cheung ct al. 2019). Therefore, we would name this method Zooming TS algorithm with Double Restarts.
As for how to choose the bottom epoch size H; in each top epoch of length Ho, we implement a two-layer framework: In the upper layer, we use the adversarial MAB algorithm EXP3 to pull the candidate from J = (Jt}. And then in the lower layer we use as the bottom epoch size for Algorithm [ When a top epoch ends, we would update the components in EXP3 based the rewards witnessed in this top epoch. The illustration of this double restarted strategy is depicted in Figure And the detailed procedure is shown in Algorithm 3
Theorem F.1. By using the (top) epoch size Ho - the expected total regret of our Zooming TS algorithm with Double Restorts (Algorithm under the switching environment over time T could be bounded as
(T( So 20( (TTT.. max { (c(T) (iout)(p.ttt) }):
Pa+2
Specifically, it holds that
P++2
T T (T) put3
c(T) > Tp.+1
(T)
33+3
TA+H
c(T) < <Tp.4.
where Pu S Pe is the upper bound of Pz,e-
Therefore, we observe that if c(T') is large enough, we could obtain the same regret bound as in Theorem 4.1 given Pz,..
F.2 Proof of Theorem F.
Proof.
The proof of Theorem relics on the recent usage of the BOB framowork that was firstly introducod
in Cheung el al. (2019) and then widely used various bandit-based model selection work (Ding et al., 2022a Zhao et al. 2020). To be consistent we would use the notations in Algorithm 3 in this proof, and we would also recall these notations here for readers' convenience: for the i-th bottom epoch, we assume the candidate Hj, is pulled from the set J in the beginning, where je is the index of the pulled candidate. At round i, given the current bottom epoch length H,, for some we pull the arm (H,,) E A and then collect the stochastic reward Y, We also define (T))) as the number of change points during each top epoch, and hence it naturally holds that [T//Hal c: (T) e(T). Given these notations, the expected cumulative regret.
28

---

Published in Transactions on Machine Learning Research (04/2024)
could be decomposed into the following two parts:
HT/Hol min(T,HH))
(T) E E
Σ f((of) - f((oo)
=E Σ
f((1)) - f((o((H))))
()+11)Ho+1
[o/ min (H
E
Σ
- fe(ve(H())
1=1
1i+
Quantity (I)
(T/
min(T,sHo)
+ E
Σ
Σ
- (((()H)))((((
(16)
(i
Quantity (II)
where H could be any restarting period J. and we expect could approximate the optimal choice Hopt (T/cc(T))
in Theorem 4.1 (Here we replace Ps.- by Ps in Theorem 4.1 since the
underlying ps,. is mostly unspecified in reality.) According to the proof of Theorem 4.1 in Appendix G Quantity (T) could be bounded as:
the
Ho/
min min(T (THHo))
Ho H
P (H*)
E
Σ
Σ
fl(f)) f((v:(H)))
S
Σ Hte(T)
p.+4
((i
H T(H) Put2
However, it is clear that each candidate in J could most be the length of top epoch size Ho, which we be [T(e (T)omtt)/(pptt t2)/p=++4)] and hence would be more challenging if the optimal choice Hopt (T/e(T))(mut) (mx+2)/(px+3) is larger than Ho. To deal with this issue, bound the expected cumulative regret in two different cases separately:
(1) If Hopt = (T/c(T))(x 12/(o.++) +3) < Ho. which is equivalent to
T c(T)
P3
T
Pe
Pu
S Ho
SP
cT)) 2 TP.t4,
e(T)
then we know that there exists some H+ J such that H+ S (T/CTT)) < 2H By setting
H" = =H+ the Quantity (I) could be bounded as:
Quantity (I) = H c() +TH+) pet2
Put2 TPu+3 c put3
= Hopt HoPtec(T) ( T(Hoot)
put2 =
For the Quantity (IT), we could bound based on the results Auer et al. (202b)). Specifically, from Corollary 3.2 in Auer al. (2002b), the expected cumulative regret of EXP3 could be upper bounded by 2Q /(e 1)LK In(K), where Q is the maximum absolute sum of rewards in any epoch, L is the number of rounds and K is the number of arms. Under our setting, we can set Q Ho. T. = [T/ Ho] and K = [J] = O(1 (H)).. So we could bound Quantity (II) as:
TT/ Ho [THHoo
T [J]nn((J)) Ö(
E
Σ
Σ
-(o((H")) f((()(HH)) < 2Ve 22Ve-1Hoy Ho
1oo+
=
Put3 (Puts
=
px+2 T p ( 311u+4) t
=0 =0(TrutS P3+3
P=+2
(17)
29

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Zooming TS algorithm with Double Restarts
Input: Time horizon T, space A, upper bound Pu S Pe-
Initialization: the (top) epoch size Ho = [T(p= (2) + 4) 1, N = [loga + 1, = {H 1oo22~1113
1: Initialize the exponential weights (1y(1) = for j = 1..
2: Initialize the exploration parameter for the EXP3 algorithm a min {1, /
JJ [)) (c- 1>T//H|
3: for 1= to [T/Ho] do
4: Update probability distribution for selecting candidates in based on EXP3 as:
(i( Σ wx(()
(5 J (1
f= j=1....,1Jl
Pull je from (1,2....,IJ]] according to the probability distribution (p)(
j=1-
6:
Run Zooming TS algorithm with Restarts using the (bottom) epoch size Hj, for t= (i - 11 + to
min(T, HHo) and collect the pulled arm ex (H,,) and reward Y, at each iteration.
7: Update components in EXP3: (1) for all j f ja T5(1) = -k=((-1)0)))) (i- 1)Ho++ (i) j = Jis and
then
wy(t + 1) = wy (i) exp ( a (1)))
j = 1, 1......1I..
end for
where we have the last equality since we assume that c(T) 2 T1/(x++1), Therefore, we have finished the proof for this case. (2) If Hops (T/c(T)) (p. +2)/(x++3) > Ho, which equivalent
P.
T
+3
T
Pu+3
P.
Ho
+
T + c(T) < TPut4,
c(T)
then we know that Hopt is greater than all candidates in J, which means that we could not bound the Quantity (T) based on the previous argument. By simply using H = Ho, it holds that
Pu+3 Quantity (I) = (HOOCT) +T. Ho Pu+2 = δ 6
T
For Quantity (IT), based on Eqn. equation 17 we have
Pa+3 Quantity (II) (II= Ō +4
Combining the case (1) and (2), it holds that
pat2 T T c (T) put3
c(T) > T
RT(T) <
Pa+3
T
c(T) < T PP:41
And this concludes our proof.
G Analysis of Theorem 4.2
G.1 Additional Lemma
Lemma G.1 (Proposition in Li al. (2017). Define Vz+1= =z X,X,, where X, drown IID from some distribution in unit ball Bd. Furthermore, let = E[X,X7] be the second moment matriz, let B, 82 be lwo positive conslants. Then there exists positive, universal constants Ci and C2 such that Xuin
Amin(V.t1 (V.+1) > B
30

---

Published in Transactions on Machine Learning Research (04/2024)
with probability at least 1 - 62, long
2
Civd+ C2
2B
2
+ Xmin (E)
Amin (Σ)
Lemma G.2 (Theorem in Abbasi- Yadkori et al. Section S it holds that for all t t> 0,
(011
For any d < 1, under our problem setting in
0 0- s <3((6),
1/
Ve Rd |/c (0, 0y) S || (r(5),
with probability at least 1 - 6, where
(A+
B((6) -o
VÁS.
82
In this subsection denote a²(6) (T(ō)-
Lemma G.3 Filippi et al. 2010)). ) Let X > 0, and (xi)i=i be sequence in Id with ||x:||| 1, then we have
dde((V+11) dot(AT)
2d (1 (1 2)
||r ll: S 2log
|
Iollly.- S T
Σ
|stallis
2dt log
1+ t ) (
Lemma G.4 AAgraaal & Goyal 2013 ) For a Gaussian random variable Z with mean and variance o², for any 2 2 1,
P( m 2 20) S 1e-212
VT2
Lemma G.5 (Adapted from Lemma G.2 For any 1, under our problem setting in Section 3 with the
regularization hyper-purameterr X Dmin Amax] (Amin > 0), it holds that for all >> 0,
0₂ 0" v.
S B()),
Vx Rd x (0. 0y)l s |,l||, 1 3.)
with probability at least 1 - 6, where
(Amia +ttd )d X2
B((8) (
+ Amax...
Proof. The proof of this Lemma is trivial given Lemma G.2 it holds that, for all t >>0 0,
G.2 For any X E Dmmin Amux), according to Lemma
0. 0- v.
3((()),
Va E Rd a T(0 0*) || B())).
with probability at least 1 6, where
(,(6) o log ( (A++)dd)
(Amin + t)d
82 + Vās s so
log
+ S.
82 82 min
31

---

Published in Transactions on Machine Learning Research (04/2024)
G.2 Proof of Theorem 4.2
Recall the partition of the cumulative regret as:
7
T
R(T) - E
+E
Σ
(m(x) u(xilaa ((xrlaa(1)1)))
L(=2++1
Quantity (A)
Quantity (B)
E
( (a
+1
Quantity (C)
Σ (u (1
Quantity (D)
For Quantity (A), could be easily bounded by the length of warming up period as:
Ti
p+2 T
E
(m(=I,,0) - p(xe TO)) < = 0 ( S
(18)
For Quantity (B); it depicts the cumulative regret of the contextual bandil algorithm that runs with the theoretical optimal hyperparameter a+()) all the time. Therefore, if we implement any state-of-the-am contextual generalized linear bandit algorithms (e.g. Filippi et al. (2010) Li et al. (011 2017)), it holds that
T Σ +1
(u(xI,,0) - (((x((a
s T Ti) = Ō(VT).
(19)
For Quantity (C), it represents the cumulative difference of regret under the theoretical optimal hyperparameter combination a (t) with two lines of history F, and Ft. Note for most GLB algorithms, the most significant hyperparameter the exploration rate, which directly affect the decision-making process. Regarding the regularization hyperparameter X, is used to make V, invertible and hence would be set to in practice. And in the long run it would not be influential. Moreover, there is commonly X, and it could be set to an arbitrary constant in order to obtain the Õ(VT) bound of regret. For theoretical proof, this hyperparameter (A) is also not significant: for example, if the search interval for À is Damin )max);
theoretical optimal value for
then we can easily modify the Lemma G.3 as:
/det(V++1))
)
5 2log
2d 2d
I+
X
b
| 1oslly--
Σ
| 1
S
2dl log
Amin
We will offer more detailed explanation to this fact in the following proof of bounding Quantity (C). Furthermore, other parameters such as the stepsize in a loop of gradient descent will not be crucial cither since the final result would be similar after the convergence criterion is met. Therefore, w.loogg we would only assume there only one exploration rate hyperparameter here to bound Quantity (C). Recall that a(t) is the combination of all hyperparamctors, and hence we could denote this exploration rate hyperparameter as a(t) in this part since there is no more other hyperparameter. Here we would use LinUCB and LinTS for the detailed proof, and note that regret bound of all other UCB and TS algorithms could be similarly deduced.
32

---

Published in Transactions on Machine Learning Research (04/2024)
We first reload some notations: recall we denote Vi AI Ein 2,a, =V= Eiz 24ys where is the arm we pulled at round by using our tuned hyperparameter a(is) and the history based on our framework all the time. And we denote
X = arg max I T 0e + a (t) || JEXt
Similarly, we denote V xX the thcoretical optimal hyperparameter a" (t) under the history of always using fa (s)) and is the corresponding payoff we observe at round L. Therefore, it holds that,
X.i where X₁ the arm we pulled by using
X arg max x 0. + a² (1) 1 zEA:
By using these new definitions, the Quantity (C) could be formulated as:
T
Σ
(n
(lxa(aa (0)55) (1) Tor) = Σ Lt=Ti+1
- - m(xTor)
T=
Quantity (C)
For LinUCB, since the Lemma G.2 holds for any sequence (I1)...,, and hence we have that with probability at least 1 - 6,
| 8l1, s.((0) s (T,
(20)
where
B.(0) / log (u+1)a) vās =
822a
And we will omit 8 for simplicity. For LinUCB, we have that
x, 0. + a (1) (t)
2 X 0. + at) [|]||||]|]] ||Axelly
2 2xT0 0- + (1) |xellv-- + 8, (0, - 00) 2 8,00 0r.
Therefore, it holds that
x, 00 + +a [X:]|xx + X, (0, (00 2 X, rr
x, 0- + 2-'a" (1) [|xellv.- 2 8, 0-,
which implies that
(X, - (X)-x))Te T0 < 2a (T) Xx 1ll
By Lemma G.3 and choosing T, T2/(++3) it holds that,
Σ
Xelly, 1
Σ
|xx|| V Amin (V)) O(T IT-1033))) 0(1(042)/044)))
t=
t
And then it holds that,
(-00 Σ (xT0 Xx0) = - (T (0''TT Σ [xll - t=T1+1
(21)
T11
Note 3,)5) contain the regularizer parameter A, and it's often set to some constant (e.g. 1) in practice. If we tune À the search interval [Amin Amax], then we can still have the identical bound as in Equ. equation 20 by using the fact that
(}+t)a) g2
log (Amin + t)dd tz)a + v S.ax
B.(0) 1 log
+ VAS S Sogg v o
82 82
33

---

Published in Transactions on Machine Learning Research (04/2024)
This result is deduced in our Lemma G.5 which implies that tuning the regularizer hyperparameter would not affect the order of final regret bound in Eqn. equation 21 Therefore, as we mentioned earlier, we could only consider the exploration rate as the unique hyperparameter for theoretical analysis.
For LinTS, we have that
x, + a² (T) 2, 2 x, + + Xx 1/- 2/
2 x 0r +T" || vl, Ze + X2 (0, -8)
2 x 0- + || 1 + ||.Bellv, 1 | 011lv.
2x,0 0 (a (T) a² a²())) |xollv, 2,
where Z, and Ze,= are IID normal random variables, At. And then we could deduce that
0. (T) |X k Z4 x, (0: - 0*) 0 (o - |x x + (T) [xilly Z, a (T) || vy 2 x
a² a || llv.
(X, - x,) T s (T) - (T) X xellyy + (a' | = Kr
where K2 is normal random variable with
E(K,) S (0(T))-11643) SD(Ki) S V2a"T-1/2000
Consequently, we have
T Σ
T
(X.0 x² S
Σ K.
t=
1=f++1
p+2 E(K)= 2n (T)7 Ö p+3)
p+l
p+1
SD(K) S V2a
2p+6
2TT2+4))
Based on Lemma G.4
we have
Σ T=
p+2 2 K> (2a" + V2)T
21/2
(22)
VVVT
This probability upper bound is minimal and negligible, which means the bound on its expected value (Quantity (C)) could be easily deduced. Note we could use this procedure to bound the regret for other UCB and TS bandit algorithms, since most of the proof for GLB algorithms are closely related the rate of Σ ( and the consistency of 0, In conclusion, we have that Quantity (C) could be upper p+2
bounded by the order Ö(T++3).
For Quantity (D), which is the extra regret we paid for hyperparameter tuning in theory. Recall we assume p(zz(a(FF)) 0+) ge(a) + IF.. for some time-dependent Lipschitz function gt- And (Л E(Tr,,))) is IID mub-Gaussian with parameter 7² where E[ns,,a depends on the history F. Denote Vss.a = nF..a E|ns,a] is the ITD sub-Gaussian random variable with parameter 72, then we have that
y$ = (a()t) + (F,a(()) + E(n), +
Since ((.,) is IID sub- Gaub-aassiin random variable independent with Fe, we denote (F1,a(s)) = VFr,a(i) + as the IID Sab-Ganssian noise with parameter 72 + o² And then we have
y/ = (i())))) + F( + (())))))) E(ye) = (a(a(t)) + F((E..((t)) u(zr(a(FF) TO²) g:(()) + El
34

---

Published in Transactions on Machine Learning Research (04/2024)
For Quantity (D), recall it could be formulated as:
E
Σ (# ((r((a(t))FF) 8*) ((o((((i)))) T1+1
Quantity (D)
Since both terms Quantity (D) are based on the same line history Fr at iteration t, and the value of El [[ only depends on the history filtration Fr but not the value of a. Therefore, holds that
T
E
Σ +=
(w (()() ((baa())))))
Σ t
ge(a Blg((((t))
Quantity (D)
Σ
sup 9 (a) E[a((((()))-
t= aEA
Therefore, Quantity (D) could be regarded the cumulative regret of non-stationary Lipschitz bandit. and the noise is IID sub- Gau-saassian with parameter To = +r) We assume that, under the switching environment, the Lipschitz function se(.) would be piecewise stationary and the number of change points is scale ((1) Therefore, Quantity (D) can be upper bounded the cumulative regret of our Zooming TS algorithm with restarted strategy given c(T) = O(1). By choosing T2 = (T- (pt2))))ttptttt)))) @(rlet3)/(+t3)) and according to Theorem 4.1 it holds that,
T
p+2 TD+3
Σ sup ga(a) - Elg.(a(i))) S a
(23)
(=
By combining the results deduced in Eqn. equation equation 22 and Eqn. equation 23 we finish the proof of Theorem 4.2 for linear bandits. For generalized lincar bandits, under the default and standard assumption in the generalized lincar bandit litcrature that the derivative of jp-) could be upper bounded by some constant given |x| s S, the regret could be bounded by further multiplying a constant in the same order.
18
Equ. equation 19 Eqn. equation 21 (or Eqn.
35


Reviews:
[{"review_id": "73HyVzSkPE", "reviewer": "Reviewer_hXyJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper is generally well-written and easy to follow. The paper studies a practically important question of online hyperparameter selection in contextual bandits. The authors have proposed a new algorithm and proves its regret upper bound.\n\nWeaknesses: I'm mainly concerned with the following two points.\n1. The authors emphasize that their algorithm is the first hyperparameter tuning framework with a continuous set of hyperparameters. However, it seems that one can use a covering argument to discretize a continuous set of parameters and then apply a CORRAL-type of algorithm to conduct hyperparameter selection. One can adjust the radius of the covering argument based on the time horizon T to prove the regret bound. \n2. The lower bound analysis is missing. Thus, it's not clear how good is the proposed algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the online hyperparameter optimization for contextual bandits. The authors propose a bandit-over-bandit framework named Continuous Dynamic Tuning (CDT) to reduce the problem to a non-stationary continuum-armed bandit problem. The authors provide theoretical guarantees for the proposed algorithm; the authors also run experiments to show the efficacy of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I recommend the authors add discussion/material regarding the two weakness points I mentioned above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6RSjAYnl9E", "reviewer": "Reviewer_THCC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#Strengths\n1) The proposed algorithm does not need a pre-defined set of candidates as the existing methods in Bouneffouf & Claeys (2020) and Ding et al. (2022b). \n2) Experimental results on both synthetic and real datasets are presented to demonstrate the performance of the proposed algorithm.\n\n#Weaknesses\n1) The Zooming TS algorithm with Restarts seems to be the most critical part of the Continuous Dynamic Tuning (CDT) framework. Although this extension of the classical Zooming is new, it seems to be a straightforward combination with the restart technique, the novelty of which is limited.\n2) In general, the proposed algorithm only achieves an expected regret bound of $\\\\tilde{O}(T^{(p+2)/(p+3)})$, where $p$ is the number of hyperparameters. Even if $p=1$, this bound reduces to $\\\\tilde{O}(T^{3/4})$, which is worse than the $\\\\tilde{O}(\\\\sqrt{T})$ regret bound achieved by ideal parameters.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the hyperparameter optimization problem for generalized linear bandits (GLB), which is well-motivated since the application of GLB significantly depends on at least one hyperparameter, i.e., the exploration parameter. To this end, the authors formulate the hyperparameter optimization problem as a non-stationary (but piecewise-stationary) continuum-armed Lipschitz bandit problem, and propose a Zooming TS algorithm with Restarts for this problem, i.e., Algorithm 1 in this paper. Then, the authors propose an efficient bandit-over-bandit (BOB) framework, in which the top layer first utilizes Algorithm 1 to select the hyperparameter on the fly and runs the contextual bandit algorithm with the selected hyperparameter. As proved by the authors, for UCB and TS GLB algorithms with exploration hyperparameters, the proposed algorithm can achieve an expected regret bound of $\\\\tilde{O}(T^{(p+2)/(p+3)})$, where $p$ is the number of hyperparameters. Moreover, experimental results on both synthetic and real datasets are presented to demonstrate the performance of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There also exist some minor comments.\n1) Page 1: a related work [1] about logistic bandit algorithms with binary rewards is missing.\n2) Pages 1 and 23: IID or iid should be consistent.\n3) Pages 5 and 6: w.l.o.g or w.l.o.g. should be consistent.\n4) Theorem 4.1: there exists a redundant space before “when ...”.\n5) Table 1: the authors should briefly explain why the proposed algorithm is the slowest one.\n\n[1] Zhang et al. Online Stochastic Linear Optimization under One-bit Feedback. In ICML, 2016.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S6wsVWVmZc", "reviewer": "Reviewer_ZP1P", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nThe strengths of the paper are highlighted through its theoretical contributions, specifically in two main areas:\n- Zooming Thompson Sampling with Restarts: The authors introduce a novel algorithm coined Zooming Thompson Sampling with restarts to address the dynamic Lipschitz bandit environment.  The method combines the empirical strengths of Thompson Sampling, restarts, and zooming, to allow the algorithm to achieve sublinear regret guarantees.\n- Theoretical Guarantees for Hyperparameter Optimization: The paper provides strong theoretical foundations for online continuous hyperparameter optimization, a significant advancement in the field of contextual bandits. This framework formulates the online hyperparameter tuning problem as a non-stationary Lipschitz continuum-armed bandit problem, integrating the previous Zooming Thompson Sampling algorithm with restarts to adaptively refine the hyperparameter space and focus on promising regions for reward improvement.\n\n## Weaknesses\n- Writing Clarity: The writing of the paper is incredibly difficult to follow. \n    - First off, the introduction needs to better highlight the main contributions in the paper (either through bullets or a more streamlined presentation).  The second and third paragraphs are a bit confusing, especially in hindsight as they seem to point out issues in the related literature that the current paper also doesn't account for (well-defined parameter sets, not recovering the minimax optimal regret guarantees for the sub-problem, etc).  \n    - Later in the definition of the model the interdependence between the selection of the hyperparameter $\\alpha_t$ and the ``optimal choice'' $\\alpha^*$ is never fully described.  This seems important for the point of the paper, since it is unclear that a fixed hyperparameter $\\alpha^*$ truly is optimal.  This makes it hard to fully appreciate the regret guarantees highlighted in Theorem 4.2. Similarly, Section 4.1 introduces a completely new model / notation, that doesn't match the earlier notation established.  \n    - The relationship between the proposed Algorithm 1 vs the original Zooming Algorithm is not explicitly stated, and only defined implicitly with a small change in line 10 in the pseudocode for the action selection.  \n- Theoretical Guarantees: The theoretical guarantees of the paper seem quite weak.\n    - Theorem 4.1: The regret guarantee in the stationary setting is already known to be $T^{(p+1)/(p+2)}$ where $p$ is chosen to be the zooming dimension of the problem.  The guarantee for the dynamic setting is done through a fixed restart schedule and the regret is essentially just an application of the pidgeonhole principle, requiring the restarts to be tuned based on the number of times the environment changes.  This feels like a unreasonable assumption in practice (especially since the ``need'' for the dynamic environment or considering a fixed number of changepoints in the hyperparameter optimization setting is not well motivated or understood).\n    - Theorem 4.2: The authors state in  ``The substantial difficulty of our problem...'' comments that they recover the $\\sqrt{T}$ regret guarantee in the case of generalized linear bandits with the addition of hyperparameter tuning.  However, to my understanding Theorem 4.2 will still propose a rate of $O(T^{(p+1) / (p+2)})$ where $p$ is the dimension of the hyperparameters.  You could consider padding the hyperparameters with additional dummy ones that have no impact on the underlying problem and the proposed guarantees will scale to $O(T)$, even though just using the theoretically provided ones will have sublinear regret.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "## Main Summary\n\nMost online learning algorithms (whether that be UCB, LinUCB, etc) rely on hyperparameters implicitly defined in the algorithm statement and are required to satisfy precise rates to obtain the optimal theoretical guarantees.  However, in practice, the empirical performance of these algorithms explicitly depends on the chosen hyperparameters, and often it is the case that the theoretically prescribed ones lead to worse empirical performance.  In a nutshell, these hyperparameters should be chosen in an instance-dependent (or even possibly time-dependent) way in order to achieve the best performance from a given bandit algorithm.\n\nAt a high level, the authors address this challenge of choosing the hyperparameters by introducing an online hyperparameter optimization framework, which the authors call Continuous Dynamic Tuning (CDT), applied to generalized linear contextual bandits.  The CDT framework is developed in a double-bandit scenario, also referred to as ``bandit over bandits'' where there is a parameter set that dictates the resulting arm selection given by the low-level bandit algorithm.  Their top-level algorithm leverages a novel Zooming Thompson Sampling (TS) algorithm, which dynamically adjusts to changes in the environment by restarting and zooming into promising regions of the hyperparameter space, thereby handling non-stationary Lipschitz bandit problems efficiently. The framework's scalability is demonstrated through theoretical guarantees that depend on a time-dependent zooming dimension.\n\nLastly, the authors complement the theoretical results with experimental results.  These experimental results validate the framework's effectiveness and superiority over traditional tuning methods across synthetic datasets with applications in generalized linear bandit problems. The results showcase CDT's ability to outperform other hyperparameter tuning methods and achieve sublinear regret, highlighting its practicality and robustness in various settings.\n\n## Model\n\nThe main model is defined over-generalized linear contextual bandits.  Over rounds $t$ the algorithm is faced with a set $A_t$ of potential actions each associated with a $d$ dimensional feature vector.  After selecting an action $a_t$ they observe a reward $y_t = \\mu(x_t^\\top \\theta^\\star) + \\epsilon_t$ where $\\epsilon_t$ is independent noise, $x_t$ is the feature vector for the selected action $a_t$, $\\theta^\\star$ unknown, and $\\mu$ is the so-called link function.  The common regret-optimal algorithm in this setting, LinUCB, selects actions via estimating the parameter $\\theta^\\star$ via $\\hat{\\theta}$ using say regression, and adding on an exploration bonus proportional to $\\alpha(t)$, a hyperparameter.  In order to address the choice of the hyperparameter $\\alpha(t)$ the authors introduce another level, the so-called top-level, where the algorithm can pick $\\alpha(t)$ in some parameter set of dimension $p$.  The observed reward then is taken to be:\n\n$$ \\mu(x_t(\\alpha)^\\top \\theta^*) = g_t(\\alpha) + \\eta$$ where $\\eta$ is potentially biased noise and $g_t(\\alpha)$ just denotes the dependence on $\\alpha$ since $\\alpha$ dictates the hyperparameter.  The performance of the algorithms is measured in terms of regret, cumulative loss over the $T$ rounds to the best fixed parameter $\\alpha$ / best fixed action $a$ in hindsight.\n\n## Main Contributions\n\nThe main theoretical contributions in the paper are as follows:\n\n- (Zooming TS Algorithm with Restarts) In the first main theoretical contribution the authors provide a novel modification of the well-studied zooming algorithm for Lipschitz bandits which includes $(i)$ Thompson Sampling in the action selection, and $(ii)$ Restarts to account for the dynamic environment.  In Theorem 4.1 the authors provide a regret guarantee for this approach scaling with respect to the so-called zooming dimension in the model (of the order $T^{(p+2)/(p+3)}$) where $p$ is the zooming dimension.\n- (Continuous Hyperparameter Optimization) In the second contribution the authors use the previous algorithm as a subroutine for hyperparameter optimization of contextual bandit algorithms.  In particular, by decomposing the regret into four different quantities and dealing with the counterfactual outcomes had a fixed hyperparameter being chosen across the entire time horizon, in Theorem 4.2 the authors provide a regret guarantee of this approach on the order of $T^{(p+2)/(p+3)}$ where $p$ is the covering dimension.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Requested Changes\n\nSee the main weaknesses highlighted above.  With changes to the writing style to help the presentation to be much clearer, as well as better defining the model of hyperparameter optimization the theoretical results could be easier to appreciate.\n\n## Minor Comments\nThe paper needs some proofreading to clear up some of the issues with the writing, but here are some issues that I noticed:\n- The entire second paragraph on page 2 is unclear\n- ``Without requiring a pre-defined set of hyperparameter candidate'' on page 2 seems like a misformed comment, especially since your algorithm similarly requires a feasible parameter set\n- ``To the best of our knowledge'' is a bit redundant on page 2\n- ``However, ..., both works have several limitations that could be improved'' on page 3\n- The point re. the regret bound on order $O(\\sqrt{MT} + M R_{max})$ on page 3 was interesting and could be expanded upon later in the text to help interpret the final bounds\n- Typo on top of page 4 should be subset instead of inclusion in $R^d$\n- Frequently refer to the optimal values $\\alpha^\\star(t)$ although that is never formally defined\n- Did not discuss the main differences between Algorithm 1 and the standard zooming algorithm (all of the differences are in line 10 with an index $I_t(v)$ which is not defined in the pseudocode)\n- ``reload some notations'' on page 6\n- ``fix distribution'' on page 8\n- ``work:'' on page 8\n\n\n## Questions\n- Do you have any intuition for the lower bounds in Theorems 4.1 and 4.2?  Clearly Theorem 4.1 is optimal up to logarithmic factors for the case when the environment is not dynamic.  However, it is unclear whether the dynamic changes should make the dependence on the zooming dimension to be worse.  Similarly, I am surprised that in Theorem 4.2 we are taking a problem whose regret guarantee is initially $\\sqrt{T}$ and changing that to one which is exponential in $p$?  At this point, for many hyperparameters, why not just use the theoretical ones (which might be too large) but still retain the reasonable regret guarantees?\n- An obvious philosophical question from reading Section 4.2 is whether it makes sense to propose an algorithm (which has hyperparameters) to optimize a sub-algorithm's hyperparameters?", "broader_impact_concerns": "The work provides a general-purpose algorithm for online continuous hyperparameter tuning.  The authors note that $(i)$ the work provides a general purpose algorithm outside of any particular application and $(ii)$ researchers utilizing the method should adhere to ethical standards for their specific context.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the hyperparameter optimization problem for generalized linear bandits, by introducing an online hyperparameter optimization framework named Continuous Dynamic Tuning. The authors propose Zooming Thompson sampling algorithm as the top-level algorithm which adjusts to the changes in the environment by restarting. 

The reviewers agree that this paper studies an practical question (hXyJ), overcomes some limitations of prior works (THCC), and has provable regret guarantees (ZP1P), backed by experimental results (THCC).  

During the discussion stage most concerns of the reviewers have been addressed. One remaining concern is Reviewer ZP1P's confusion about the mathematical definition of theoretically optimal \alpha^* (e.g. page 32). Please define it formaly in the final version.
Decision: Accept (poster)