Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
Authors: QIN DING
Yue Kang
Yi-Wei Liu
Thomas Chun Man Lee
Cho-Jui Hsieh
James Sharpnack
Venue: NeurIPS 2022 Accept (2022)
Keywords: contextual bandits
online learning
hyperparameter optimization

Abstract: The stochastic contextual bandit problem, which models the trade-off between exploration and exploitation, has many real applications, including recommender systems, online advertising and clinical trials. As many other machine learning algorithms, contextual bandit algorithms often have one or more hyper-parameters. As an example, in most optimal stochastic contextual bandit algorithms, there is an unknown exploration parameter which controls the trade-off between exploration and exploitation. A proper choice of the hyper-parameters is essential for contextual bandit algorithms to perform well. However, it is infeasible to use offline tuning methods to select hyper-parameters in contextual bandit environment since there is no pre-collected dataset and the decisions have to be made in real time. To tackle this problem, we first propose a two-layer bandit structure for auto tuning the exploration parameter and further generalize it to the Syndicated Bandits framework which can learn multiple hyper-parameters dynamically in contextual bandit environment. We derive the regret bounds of our proposed Syndicated Bandits framework and show it can avoid its regret dependent exponentially in the number of hyper-parameters to be tuned. Moreover, it achieves optimal regret bounds under certain scenarios. Syndicated Bandits framework is general enough to handle the tuning tasks in many popular contextual bandit algorithms, such as LinUCB, LinTS, UCB-GLM, etc. Experiments on both synthetic and real datasets validate the effectiveness of our proposed framework.

Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
Qin Ding Department of Statistics University California, Davis gdingoucdavis. edu
Yue Kang Department of Statistics University of California, Davis yuekangbucdavis.co edu
Ye- Liu Department of Statistics University of California, Davis 1ywliu@ucdavis edu
Thomas C. M. Lee
Department of Statistics University of California, Davis tcmlee@ucdavis.c
Cho-Jui Hsieh
James Sharpnack Amazon
Department of Computer Science University of Californi, Los Angeles chohsieh@cs. ucla. edu
Berkeley, CA j jsharpna@gmail.com com
Abstract
The stochastic contextual bandit problem, which models the trade-off' between exploration and exploitation, has many real applications, including recommender systems, online advertising and clinical trials. As many other machine learning algorithms, contextual bandit algorithms often have one or more hyper-parameters. As an example, most optimal stochastic contextual bandit algorithms, there is an unknown exploration parameter which controls the trade-off between exploration and exploitation, A proper choice of the hyper-yaraaa pyper--arameters is essential for contextual bandit algorithms to perform well. However, it is infeasible to use offline tuning methods to select hyper- param--rrs in contextual bandit environment since there is no pre-collected dataset and the decisions have to be made in real time. To tackle this problem, we first propose a two-layer bandit structure for auto tuning the exploration parameter and further generalize it to the Syndicated Bandits framework which can learn multiple hyper-parameters dynamically in contextual bandit environment. We derive the regret bounds of our proposed Syndicated Bandits framework and show it can avoid its regret dependent exponentially the number of lyper-parametert to be tuned. Moreover, it achieves optimal regret bounds under certain scenarios. Syndicated Bandits framework is general enough handle the tuning tasks in many popular contextual bandit algorithms, such LinUCB, LinTS, UCB-GLM, etc. Experiments on both synthetic and real datasets validate the effectiveness of our proposed framework.
Introduction
The stochastic contextual bandit problem models the well-known peploration-explotattti dilemma in repeated game between player and an environment. At each round, the player sequentially interacts with the environment by pulling an arm from a pool of K arms, where every arm is associated with
Work done prior joining Amazon.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

d-dimensional contextual feature vector. Only the stochastic reward corresponding to the pulled arm revealed to the player. The goal of the player to maximize the cumulative reward or minimize the cumulative regret. Due to the partial feedback setting, the player has to balance between exploitation -pulling the arm that has the best estimated reward so far and exploration - exploring whether there are uncertain arms that may be better than the current estimated best arm.
With substantial applications in recommender systems [17] online advertising [20] clinical trials 1251 etc., bandit algorithms have been extensively studied during the past few decades. In general, there are two exploration techniques, Upper Confidence Bound (UCB) 6 18 and Thompson Sampling (TS) A [ algorithms. The UCB algorithm addresses the dilemma optimistically by pulling the arm that has the biggest upper confidence bound. The TS algorithm usually assumes that the relationship between the contextual features and rewards follows a prior model and it uses new observations at each round to estimate the posterior model. The player then pulls the arm that has the best estimated reward based on the posterior model. In general, the contextual bandit problems have regret lower bounded by ( 13 17 where T is the total number of rounds. Both UCB and TS algorithms have been shown to achieve optimal regret bounds in (generalized) linear bandit problems [17 [8]. kernelized bandit problems [12 and even in the contextual bandit problem with more complicated models such as neural networks (88).
Despite the popularity of the contextual bandit problem, there are some practical issues that prevent it from being used widely in practice. In both UCB and TS, there are unknown to the player. One of the most important paper--arameters is the exploration parameter, which controls the trade-off between exploration and exploitation. A good choice of the exploration parameter is essential for the algorithm to perform well and for the theory to hold. Another commonly seen papee-paramtter is the regularization parameter À in ridge regression or generalized linear model, which is used to model the relationship between features and rewards in (generalized) linear bandits. In contextual bandit problems with complex models such as neural network, the recently proposed NeuralUCB (28) algorithm has far more than just two hyper-parameters. Neu also needs to select the network width, network depth, step size for gradient descent to solve the neural networks and gradient descent steps, etc. Due to the nature of the bandit environment, where the decisions have to be made in real time, it is inherently difficult to tune the apper-paraetters by the traditional offline tuning methods, such as cross validation, since when you have decided to use parameter in partial datasets and make a decision based on this, the regret incurred by this decision will never be reversible in contextual bandit environment. In many prominent bandit works [17 [4] 28 10, the experiments are conducted by running a grid search on the possible choices of parameters and only the best result is reported. Although the performance of the best grid search results is of academic interest, it is not possible to do grid search in practice. In some other works [15. exploration parameter is set as a sufficient, theoretically derived, and often unknown value, but this value may be too conservative and may not achieve good performances in practice, which can be seen from the experiments in Table []
that are
In this work, we first propose two-layer bandit structure that can automatically tune the exploration parameter dynamically from the observed data. The two-layer bandit structure has its similarities to the bandit-over- sellii--vve-baaddi bandit (BOB) algorithm [11] proposed for the non-stationary stochastic bandit problems, where it uses BOB idea to successfully adapt its sliding- window sizes by restarting the algorithms in epochs. Motivated by the two-layer bandit structure we propose in Section 4 generalize it to the "Syndicated Bandits" framework where there could be multiple in the contextual bandit algorithm. We provide theoretical guarantees for our framework and show that our proposed auto tuning method in general has regret upper bound ( + Õ Vn,T). Here L is the total number of papper-prraeters to be tuned and ny is the number of candidates in the tuning set of the 1-th parpem-rrreterr. When the unknown theoretical exploration parameter is no bigger than any elements in the tuning set, our proposed framework has optimal regret upper bound Ö(VT) t Vn,T) for UCB-based algorithms. Our framework is general enough to handle tuning tasks in many contextual bandit algorithms as long as the arms to be pulled at round follows fixed distribution given the apper-parameters to be used at this round and the past information. This includes many popular contextual bandit algorithms such as Linear UCB (LinUCB) [1] M. Linear TS (SinTS) (5) I0, UCB-GLM (18) etc. Our proposed Syndicated Bandits framework the first work that considers tuning multiple parameters dynamically from observations in the contextual bandit problems with theoretical guarantees. We provide a regret bound that avoids the exponential dependency on the total number of hyper-parameters to be tuned. This is one of the main contributions of our proposed work. In Section 6 we show by experiments that our proposed framework improves
to be tuned

---

over existing works, as well as the bandit algorithms that use the unknown theoretically derived exploration parameter.
2 Related work
There is a rich line of works on multi-armed bandit (MAB) and stochastic contextual bandit algorithms, including (generalized) linear bandits, kernelized bandits and neural bandits, etc. Most of them follow the UCB and TS exploration techniques. We refer the readers to [7 for the seminal works regarding the bandit problems. There are many previous works that utilize algorithms in the stochastic MAB [33 setting to solve the hyper-parameter optimization problem 22,19 There are also some online aaper-parameter tuning works such as [24], however, those mainly focuses reducing the training cost for tuning parameters of neural networks online and they are not considering minimizing the cumulative regret in contextual bandit problems. In the following, will only pay attention to related works on the tuning tasks in stochastic contextual bandits.
18
4
5 TO 12| 28
12 proposed a meta-learning method for learning exploration parameters in contextual bandit problems. It learns good exploration strategy in synthetic datasets and applies it to the real contextual bandit problems by an imitation study. The meta-learning algorithm is compared with seven baseline contextual bandit algorithms and achieves good empirical results. We note that this algorithm cannot learn the exploration parameters adaptively from observations in the contextual bandit environment. In [.] the authors first proposed OPLINUCB and DOPLINUCB algorithms to learn exploration parameters dynamically. OPLINUCB treats the possible choices of uses standard MAB TS algorithm to choose parameters. It then uses the chosen parameter in the contextual bandit algorithm. However, this method does not have theoretical guarantee in general, since the MAB TS only works when the rewards of the candidate hyper-parameters in the tuning set stay stationary over time. For hyper-parameter selections in contextual bandit problems, the best exploration parameter does not stay the same all the time. This is because in later rounds, when the learning is sophisticated, less exploration is better. However, in the beginning, more exploration is preferred due the uncertainty. This non-stationary nature in tuning hyper-parameters makes the performance of OPLINUCB unstable in practice. DOPLINUCB is a similar tuning method as OPLINUCE, except that it uses the CTree algorithm select eeper-prrametess at each round. is shown in [9] that DOPLINUCB does not outperform OPLINUCB in stationary contetxual bandit environments, where the feward-fetture model does not change over time.
as arms and
Another close line of literature is on model selections in bandit algorithms. [6 tackles the feature
selection problem in bandit algorithms and achieve O /2/3/ where d. is the total number of optimal features. 33] uses the corralling idea to create a master algorithm to choose the best bandit model from a set of M base models. dlyper-parameee selection problem in [3) where we can treat bandit algorithms with different typer-parametert as the base models. The theoretical regret bound of the corralling idea 3 is O /MTT + M Rmax). where M is the total number of base models and Ruax is the maximum regret of M base models if they were to run alone. This means that the regret bound will be exponentially dependent on the total number of papae-parameters be tuned. In addition, if there is hyper-parameter in the tuning set that gives linear regret of the algorithm, then Rmax is linear in T which makes the corralling idea have linear regret in worst case. Our algorithm is also much more efficient than the corralling idea when M is big. The corralling idea requires updating all M base models/ algorithms at each round. However, our algorithm only needs update the selected model/ bandit algorithm with selected hyper-parameter at each round. When the time complexity of updating the model/ algorithm is big, the corralling idea is expensive. For example, if we tune configurations for UCB-GLM, the corralling idea needs ((MT2 d) time, while the time complexity of our algorithm is only O(MT - T2d).
tuming problem can be formulated as a model
We address here that none of the previous works can tune multiple parameters dynamically from observations. Although OPLINUCB 99| and the corralling idea 3 can treat all the hyper-parameters single parameter and set the tuning set as all the possible combinations of hyper-parameters: This will lead to exponential number of configurations which may not be efficient in both computation and theoretical regret bounds. Our proposed Syndicated framework avoids the exponential regret bound.
Notations: For vector E Rd,, we use ||ж||| to denote its le norm and || == Vx Ar for desitive-defintte matrix A e RR Finally, we denote [xx] == (1.2....,1))
3

---

3 Preliminaries
We study the hyper-parameter selection tasks in stochastic contextual bandit problem with K arms, where K can be an infinite number. Assume there are in total I rounds, at each round E [T]
the player is given K arms, represented by a set of feature vectors A, = f E [K]} C R As is drawn IID from an unknown distribution with || 1 for all 1 [7] and a [K], where Tr,a is a d-dimensional feature vector that contains the information of arm at round I. The player makes decision by pulling an arm de [K] based A, and past observations. We make a common regularity assumption as in [1 18). i.c. there exists a constant do > 0 such that Amin [B E Fr,al 70- The player can only observe the rewards of the pulled arms. Denote X, := 2i,a, the feature vector of the pulled arm round t and Y, the corresponding reward. We assume the expected rewards and features follow a model [E u(-) is a known model function and 8 is the true but unknown model parameter. When μu(z) = x. this becomes the well-studied linear bandits problem. When μ(.) is a generalized linear model or neural network, this becomes the generalized linear bandits (GLB) and neural bandits respectively.
u(XT7*), where
Without loss of generality, we assume that there exists a positive constant S such that ||0"| || S S. We also assume the mean rewards ((* E [0, 1] and observed rewards Y, E [0. 1]. This a non- critical assumption, which can be casily relaxed to any bounded interval. Ff = o((a, A.. Y. -- 1 is the information up to round t, we assume the observed rewards follow a sub-Gaussian distribution with parameter x², i.e., Y, = xxX (*)) + Ct. where 4 are independent random noises 6202
that satisfy Ele [F-1]] < 2 for all and E IR. Denote of = argmax,e(K (xX? OX)"0)) as the optimal arm at round í and Ft,,, as its corresponding feature, the goal is to minimize the cumulative regret over T rounds defined in the following equation.
R(T) = E -(xT(00))~(x000
For linear bandits where ju(x)= = xr classic bandit algorithms such as LinUCB 1 and LinTS 2 compute estimate of the model parameter 6, using ridge regression with regularization parameter 0, i.e., 0, = V, Σ X,Y., where V, ATa Σ X, Shown by M. with probability at least 1 - 6, the true model parameter 0² is contained in the following confidence set,
C = (0 E Rd: 110 dellv. s sa(0).
where
a(l) V d 1+1/2 SVİ.
To balance the trade-off' between exploration and exploitation, there are in general two techniques. For example, in linear bandits, LinUCB explores optimistically by pulling the arm with the maximum upper confidence bound, while LinTS adds randomization by drawing sample model from the posterior distribution and pulls an arm based on it.
0 = argmax T. O att)l
(LinUCB)
0.5 ~ N(O,, ((1)VV and -argmax Li OTS
(LinTS)
In the following, we call (t) the exploration parameter. As suggested by the theories in conservative choice of the exploration parameter is to follow Equation 3 However, in Equation 3 the upper bound of the la norm of the model parameter S and the aub-Gaussian parameter are unknown to the player, which makes it difficult track theoretical choices of the exploration parameter.
In Table show the cumulative regret of LinUCB [T7 and LinTS [5] in simulation study with d d= 5, 7 10000 and K 100. Rewards are simulated from N Nartaa0 005)). The model parameter 0" and feature vectors Ft,o are drawn from Uniform( -/a Ad) Two scenarios are considered in this table. In the first scenario, the feature of each arm keeps the same over T' rounds. While in the second scenario, the features are re-simulated from Uniform(- 1 1 at different rounds. We
Va va)

---

run grid search of the exploration parameter in (0,0.5, 10) and report the best grid search result, as well as the results using the theoretical exploration parameter given by Equation 3 (last column in Table D. As we shall see in Table [ the best exploration parameter is not the same for different scenarios. Therefore, which exploration parameter use an instance-deeendent problem and the best exploration parameter should always be chosen dynamically based on the observations. Meanwhile, theoretical exploration parameters do not always give the best performances from Table I On the other hand, in many other works where the model of contextual bandit problem is more complex, such as the generalized linear bandit [4], neural bandit (28] there may be many more hyper- paeereparmeterss than just (tt).
Table Averaged cumulative regret (cum. reg.) and standard deviation (std) of the cumulative regret based on 5 repeated experiments. "Fixed" means that the feature vectors of each arm are fixed over time. "Changing" means that the features are re-simulated from the same distribution each round.
Algorithm
Feature type
Best a(t)
Cum. reg. (std)
Theoretical cum. reg. (std)
Fixed
4.0
357.21 (188.72) 72)
364.99 (151.54)
LinUCB
Changing
1.5
312.69 (42.53)
582.59 (523.60)
Fixed
336.44 (137.01)
576.83 (110.48)
LinTS
Changing
3.5
352.79 (109.84)
488.99 (141.34)
A two-layer bandit structure for tuning exploration parameters
In the previous section, we have discussed that the best hyper-paramedd should be instant-dependent. this section, we propose a two-layer bandit structure to automatically learn the best hyper-parameter from data at each round. We will take learning the best exploration parameter as an example. However, we want to emphasize that this structure can also applied learn other single hyper- prpee-parameter.
We randomly select arms for the first Ti rounds to warm up the algorithm. For all rounds later, in this two-layer bandit structure, the top layer follows an adversarial MAB policy, namely, the EXP3 algorithm 77. Assume / is the tuning set of all the possible exploration parameters. At each round t >> Ti the top layer will select a candidate exploration parameter 0; E J, where a, the i-th element in the set J and & is the selected index at round f. The bottom layer runs the contextual bandit algorithm based on the selected exploration parameter o;,, Details are listed in Algorithm
4.1 Regret analysis
Given all the past information F.-1, denote Be(aj]Fee as the pulled arm when the exploration parameter is a; at round t. Denote (r(a,) = (1,or(a,(Ei-.) as the corresponding feature vector under Ft-1- Note that our algorithm, X, = X,(0;, when / Ti. To analyze the cumulative regret, we first decompose the regret defined in Equation Tinto three parts:
T
T
E[R(T)] = E
Σ (p (Zr, - (x,(0)
LE
Σ Le=T++1
(u (xe, -0) (xxx((((=((F
Quantity (A)
T
Ti
+ E
Σ LI=T++1
(n (x,,(a)FF - (x((r,,1== (1
+ E
(n (Ir T0 (x:'))
Quantity (B)
Quantity (C)
where u(.)) is the reward-featur model function and a E J is some arbitrary candidate exploration parameter in J. Quantity (A) the regret of the contextual bandit algorithm that runs with the same hyper- parameerrrttrr a" under the past history Ft-1 generated from our tuning strategy every round. Quantity (B) the extra regret paid to tune the hyper-parameter. Quantity (C) is the regret paid for random exploration in warm-up phases and is controlled by the scale of O(Ti). We show by Lemma [ and Theorem I below that our auto tuning method in Algorithm does not cost too much in selecting parameters in most scenarios under mild conditions.
5

---

Algorithm A Two-layer Auto Tuning Algorithm
Input: time horizon T, warm-up length Ti, candidate hyper-parameter J )m
2: Initialize exponential weights wyyTi + 1) = for j = [Ti].
1: Randomly choose a, E [K] and record X,, Y, for
3: Initialize the exploration parameter for EXP3
min { 1,
n nlog
4: for t= (Ti + 1) to 7 do
5: Update probability distribution for pulling candidates
(1 _
Wy (t)
B)
Ei=1 (t
6: J-J [xi] with probability (t)))
7: Run the contextual bandit algorithm with hyper-parameter a(l) ai, to pull arm. For example, pull arms according to the following equations
= argmax x Oe + az, Il,l, a=l...,k
(LinUCB)
0 N(O, V. and a₂ = =aggmax x 0.
(LinTS)
8: Observe reward Y and update the components in the contextual bandit algorithm.
9:
Update EXP3 components: (j) <- 0f # it. Ue(j) + (t/p5(t) if 4. and
1 "y (t+++1) wt x exp
n2 (
10: end for
Since the arms pulled by the contextual bandit layer also affect the update of the EXP3 layer in Algorithm the result of EXP3 algorithm is not directly applicable to bounding Quantity (B). We modify the proof techniques in 7 and present the proof details in Appendix.
Lemma Assume given the past information Fi-1 and the follows fixed distribution. For a random sequence of parammtrrrsssrrs {as,y..... atyy selected by the EXP3 layer in Algorithm ] and arm (o,)), is pulled in the contextual bandit layer round t, have
to be used by the
contextual bandit algorithm round t, the arm to be followollowws
max E OEJ
Σ (Xi(a)
-E EE
< $2 (X
1)mI logn,
where J fai...., is the tuning set of the ssper-parameter and [J] n.
To bound Quantity (A), we note that are not able use any existing regret bound in the literature directly since the past information Fz- here is based on the sequence of arms pulled by our auto- tuning algorithm instead of the arms generated by using a* at each round, and the history would affect the update of bandit algorithms. We overcome this challenge by noticing that the consistency of 6₂ plays vital role in most of the proofs for (generalized) linear bandits, and this consistency could hold after a warm-up period with large exploration rate. Therefore, we can expect a tight bound of the cumulative regret by using the same exploration parameter even under another line of observations F,-1 with sufficient exploration. Another crux of proof that the regret is usually related to ||aelly-", which can be similarly bounded after sufficient exploration. After we bound Quantity (A), combing Lemma] I get the following theorem.
Theorem Assume given the past information F.-1 generated from proposed algorithm for arm selection and the aaprr-parameter to be used by the contextual bandits, the arm to be pulled follows a fixed distribution. For UCB and TS based generalized linear bandit algorithms with exploration hyper-parameters (LinUCB, UCB-GLM, LinTS, ect.), the regret bound of Algorithm 7 satissies
(1) E[R(T)) 0(T2/3) + O(Vn(T Ti) log n) given the warm-up length TV O(12/3).

---

(2) For UCB- besed bandits, if the theoretical exploration parameter (T)) is no larger than any element in J. then it holds that = + O( log with T1 0.
(3) Af is convex set, and the smallest principal curvature any neighborhood of the optimal vector It,+ E AA, on A, can be lower bounded by some positive constant then E [[(( = Ö(T4/T)+ + +(Vn
log n) after warming-up up period of length Ti O
Remark We could expect a similar result for TS-based bandit algorithms as in Theorem 7 (2), and we offer an intuitive explanation in Appendix Moreover, the conditions in Proposition (3) could
be easily verified in many cases. For example, it holds when At = {o E IRd |||||| S sa), Va O.
5 The Syndicated Bandits framework for selecting multiple hyper-parameters
There can be multiple dit algorithms such as Lin and Lin'SS [1) exploration parameter a and the regularization parameter of the ridge regression À are both hyper-parameters to be tuned. In more recent contextual bandit works, there could be even more than two hyper-parameters. For example, NeuralUCB algorithm (28), which is proposed for the contextual bandit problems with a deep neural network model, has many tuning parameters such as the network width, network depth, step size for gradient descent, number of steps for gradient descent, as well as exploration parameter and regularization parameter A, etc. Another example can be found in [14, where efficient SGD-TS algorithm is proposed for generalized linear bandits, the number of tuning parameters is also more than two.
in the contextual bandit algorithm. For example, linear ban-
A naive strategy to auto-tune multiple hyper-parameters is use Algorithm D and let the tuning set J contain all the possible combinations of the hyper- parameters. Assume there are in total (L)),
Use EXP3:1) to select at /11
Use EXP3( to select atll Jt
Use EXP3(L) to select a c/2
L hyper-parameters (1),, (2) ..()),.....))) For all / E [L]. if the tuning set for ())) defined Jj- {ai (1) (.)) where ny is the size of the corresponding tuning
())
Contextual Bandit Algorithm with (2) (t
parameters o ",2" C.it)
Figure 1: Illustration of the Syndicated Bandits.
set. Then there are in total 11fm ny possi- ble combinations. Based on Lemma [ the
extra regret paid to tune the prpee-parameters (Quantity (B)) is upper bounded by Ö( Ti Therefore, the aforementioned naive approach makes the regret increase exponentially with the number of tuning parameters. To mitigate this issue, we propose the Syndicated Bandits framework that can deal with multiple hyyer-paramette while avoiding the exponential dependency the number of tuning parameters in regret bounds.
We create L +1 1 bandit instances in this framework. In the bottom layer, the contextual bandit algorithm is used decide which arm to pull. On top of the contextual bandit layer, there are L EXP3 bandits, denoted as EXP3(I) for I E [L]. Each EXP3 algorithm is responsible for tuning one hyper-parameter only. At round (I) is the index of the hyper-parameters Jr selected by the (t)
(X) bandit and the selected hyper-parameter is denoted as (.()) for l E [4]. then the contextual bandit algorithm in the bottom layer will use these parameters to make a decision and receive reward based on the pulled arm. The reward fed to all the L +- 1 bandits to update the components. Illustration of the algorithm and more details are presented in Figure and Algorithm 2 in Appendix.
5.1
Regret analysis
At round I, given all the past information F,-1, denote at ae (1)
0 (F as the arm pulled
(L)
by the contextual bandit algorithm if the parameters are chosen as (1)) o
(1) for all l E [T.] and let
(a (1) (4)
....., 3 (F-1) be the corresponding feature vector. Recall that u(-) is the reward-feature
7

---

model function, then for an arbitrary combination of hyper-parameters (a!") ....,..!))..
E[R(T)] = Ti
- [ +
EE(u(ut,0) (Xi(al) (xi(aa))..... (1) (F
(=
E j [ (1)
(X [=-))=))) 1 (xi(a (2) (2) :..,,),, "(.
E
[ [x((a (x()) 12)
1 1 F(-)) - (Xi(a h
(3) (F- ]0)
T
E (a Σ
(1) (1))
(1-1) a1 ( 1=-)))))))))) ( (6,
(
(1)
+ 1=
The first quantity represents the regret from pure exploration. The second quantity in the above de- composition is the regret of the contextual bandit algorithm that runs with the same hyper-parameters
a.")) ...") under the past history F:-1 generated from our tuning strategy every round. The next L quantities in the decomposition are the regret from tuning parameters in the EXP3 layer, which can be bounded using similar techniques in Lemma [ However, the correlations between parameters are more complicated in the analysis now. Formally, we provide the following Theorem guarantee the performance of the Syndicated Bandits framework. Proofs are deferred to the Appendix.
Theorem 2. Assume given the past information F.-1 and the spper-paraeeters be used by the contextual bandit algorithm at round I, the arm to be pulled by the contextual bandit algorithm follows a fixed distribution. Then the auto tuning method in Algorithm 2 with warm-up length Ti O has the following regret bound in general:
B(R(T)) S O(T2/3) + O Σ Vm -i)
Remark 2. Note this result avoids the exponential dependency on the number of hyper experrparrameters to be tuned in regret. When the esper-parameters to be tuned are the exploration parameter a and the regularization parameter X of the (generalized) linear model, we also have the same conclusions as in Theorem[] Please refer to Appendix (a.rndixXAA31 for a formal statement and its proof.
for
Remark 3. Without any assumptions, Algorithm 2 has its regret dependent on d as Odd + d3/2/3
for both UCB and TS. In practice, usually d <<
Experimental results
We show by experiments that our proposed methods outperform various contextual bandit algorithm using the theoretical exploration parameter, as well as existing tuning methods. We compare different hyper-parameter selection methods in three popular contextual bandit algorithms, LinUCB [ LinTS (5) and UCB-GLA GLM 18 with logistic model. In practice, we set the warm-up length as T = O and tune both exploration parameters and regularization parameters. We compare the following hyper- apper-parmmeter selection methods. Theoretical-Explore [ At round t. this method uses the true theoretical exploration parameter (x({) defined in Equation 3 OP (9]: We make simple modifications of OPLINUCT to make applicable to tune exploration parameters for LinUCB, LinTS and UCB-GLM; Corral [3: This method uses the corralling idea to tune the exploration parameter only. Comral-Combined 33: This method treats bandits with different combinations of the cxploration parameter and regularization parameter À as base model and uses the corralling idea to tune the configurations; TL (Our work, Algorithm I]: This is our proposed Algorithm [ where we use the two-layer bandit structure to tune the exploration parameter only; TL-Combined (Our work, Algorithm M. This method tunes both the exploration parameter a and the regularization parameter À using Algorithm [ but with the tuning set containing all the possible combinations of and X; Syndicated (Our work, Algorithm ) This method keeps two separate tuning sets for a and respectively. It uses the Syndicated Bandits in Algorithm 2
We set the tuning set for exploration parameter a as (0, 0.01, 0.1, 1, 10) and set the tuning set for regularization parameter À as {0.01, 0.1, in TL-Combined,
and Syndicated.
8

---

Algorithm 2 The Syndicated Bandits Framework for Auto Tuning Multiple Hyper-parameters
Input: time horizon T, warm up length T1. candidate eyper-parameter set {Ji
1: Randomly choose dg E [K] and record Xt, Yt for t E [Ti].
2: Initialize exponential weights w) (Ti 1) for 1, j ..... my and =11111111. 1 L.
3: Initialize the parameters for all EXP3 layers as 3g = min {
log m
(--1)7
4: for port=g (Ti + 1) to T do
5: Update probability distribution for pulling candidates in Jt
0 (t) Pj
31 + (1 (1)
3 (1)
(
Σ w (1)
6: ie(1) j E [nu] with probability pj (1)) for all / I,...,,. L.
7: Run the contextual bandit algorithm with hyper-parameters α0 a
(t) to pull arm.
(1)
8: Observe reward Y, and update the components in contextual bandit algorithms.
9: Update all L EXP3 bandits: 1/2 (j) - 0 if + (t). Otherwise, D1 (i) + (1/1)((). (1).
(1) 3 ( 1) w (1) exp L (1) IN
(1)
(1)) Di
10: For all = 1, ....... L, let
11: end for
Simmuattio for LinUCa
Simulation for LinTSS
Simu GLM
Cumulative Regret
Syndicated
Combiied
Cumul latie Regret
900
Sysdioted
Combined
Cumulatii live Regr Regret
332
TL
Syndicated
Combined
Theorstical Explore
520-
Theoratical Explora OP
235
Thsoretical Explore
Carral Cayyafond
Carchtied
132
-oomtined
Sze-
322
30-
2000 100
$100
10000
5010
1000
1003
6200
10100
3002
3100
(000
9300
10300
Iterations
Iterations
Moviclens
Movisiens for UCB GLM
Cumnu Vavvvve Regret
5002
Cumulative Regret
230
Syndicated
Combined
Combined
230
Theorstical- - Eeplore
Throretical -Eeplore
Cumulattve
OP
QP
Corni
2018-
2002
Cornd Comtined
0628
1002
36-
4050
9202
2000
4050
8022
10000
4000
0000
10300
Iterations
Iterations
Figure 2: Comparison of syper-parameters selection methods in LinUCB, LinTS and UCB-GLM.
For Theoretical-Exphee OP and TL, since they only tune the exploration parameter, we set the regularization parameter as X 1. In all the experiments below, the total number of rounds is T 10, 000. We run the comparisons on both simulations and the benchmark Movielens 100K real datasets. Due to limited space, the descriptions of the dataset settings are deferred to Appendix A.4 Averaged results over 10 independently repeated experiments are reported below.
we observe: 1) When tuning only one hyper-parameter (exploration parameter in our experiments), the proposed method outperforms previous tuning methods. Further, the theoretical exploration parameter does not perform well and tends to be too conservative in practice, which is consistent with the results we show in Table 2) When tuning multiple prper-parameters, previous methods do not apply. We found using the Syndicated Bandits framework usually outperforms TL-Combined and is significantly better than with respect to number of tuning parameters. 3) Using Syndicated Bandits to tune multiple hyper- parameters usually outperforms tuning one parameter only. This demonstrates a practical need of auto-tuning multiple hyper- parammerrssssses in bandit algorithms. See Appendix for additional experiments on the tuning 3 parrme-as in SGD-TS [4.
From Figure 2,
method which has exponential regret

---

7 Conclusion
In this paper, we propose a two-layer bandit structure for auto tuning the exploration parameter in contextual bandit algorithms, where the offline tuning is impossible. To further accommodate multiple ppprr-parameters tuning tasks in contextual bandit algorithms with complicated models, we generalize our method to the Syndicated Bandits framework. This is the first framework that can auto-tune multiple hyper-parameters dynamically from observations in contextual bandit environment with theoretical regrets that avoids exponential dependency the total number of hyper-parameters to be tuned. We show that our proposed algorithm can obtain ((T2/3) regret in general and has optimal ((vT) regret for UCB-based algorithms when the all candidates in the tuning set is greater than the theoretical exploration parameter. Our work is general enough to handle the tuning tasks in many contextual bandit algorithms. Experimental results also validate the effectiveness of our proposed work.
Acknowledgments and Disclosure of F Funding
We are grateful for the insightful comments from the anonymous reviewers and area chair. This work was partially supported by the National Science Foundation under grants CCF-1934568, DMS- 1405, DMS-181 1661, DDMS-116125, DMS-2113605, DMS-2210388. IIS-2008 and IIS-2048280. CJH is also supported by Samsung, Google, Sony and the Okawa Foundation.
References
[1] Yasin Abbasi-Yade Yadkori. Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320. 2011.
[2] Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[3] Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
[4] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1, 2012.
[5] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135, 2013.
[6] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
[7] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[8] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[9] Djallel Bouneffouf and Emmanuelle Clacys. Hyper-parameter tuning for the contextual bandit. arXiv preprint XXi::2055.02209 2020.
[10] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2257, 2011.
[11] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning optimize under non- stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1087, 2019.
[12] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits, In International Conference Machine Learning, pages 844-853, PMLR, 2017.
10

---

[13] Varsha Dani. Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT, pages 355-366, 2008.
[14] Qin Ding, Cho-Jui Hsieh, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pages 1585-1593. PMLR, 2021.
[15] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pages 586-594, 2010.
[16] Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
[17] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661 2010.
[18] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[19] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyper- band: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765-68 6816, 2017.
[20] Eric Schwartz, Eric Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
[21] Xuedong Shang, Emilie Kaufmann, and Michal Valko. simple dynamic bandit algorithm for hyper-parameter tuning. In Workshop on Automated Machine Learning at International Conference on Machine Learning, Long Beach, United States, June 2019, AutoML@ICM 2019 - 6th ICML Workshop on Automated Machine Learning.
[22] Amr Sharaf and Hal Daumé III. Meta-learning for contextual bandit exploration. arXiv preprint /9Xiv: 59, 2019.
[23] William Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[24] Jingkang Wang, Mengye Ren, Ilija Bogunovic, Yuwen Xiong, and Raquel Urtasun. Cost- efficient online hyperparameter optimization. arXiv preprint arXiv:2101.066 2021.
[25] Michael Woodroofe. A one-armed bandit problem with a concomitant variable. Journal of the
American Statistical Association, 74(368):799 806, 1979.
[26] Hsiang-Fu Yu, Cho-Jui Hsieh, Si Si, and Inderjit S. Dhillon. Scalable coordinate descent approaches to parallel matrix factorization for recommender systems. In IEEE International Conference of Data Mining, 2012.
[27] -usaag-Fuu 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.
[28] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A]

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] include the code in the submitted supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes) See Section 6
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See T
(d) Did you include the total amount compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasin new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix for the dataset explana-
tion
(c) Did you include any new assets either the supplemental material or as URL? [Yes] We include the code in the submitted supplementary materials.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "YAQr2vEezz", "reviewer": "Reviewer_vjwY", "summary": "This paper studied hyperparameter tuning for contextual bandits. The authors proposed a two-layer bandit structure to tune the exploration parameter where the top layer applies EXP3 to select a hyperparameter as adversarial MAB and the bottom layer is the contextual bandits to be tuned. The authors then generalized it to Syndicated Bandits to tune multiple hyperparameters. The proposed method achieve $O(T^{2/3}+\\sum_l\\sqrt{n_l T})$ regret for tuning UCB and TS based algorithms. Empirical evaluations show that proposed method outperforms baselines.\n", "questions": "Besides the questions in weakness, I have two clarification questions: \n\n1. Is expect regret upper bound for tuning TS based algorithm defined as Bayesian regret or frequentist regret? I tried to follow the proof of Theorem 1 and it looks like frequentist regret to me, but the proof mixed UCB and TS and is not very clear. \n\n2. What is the dependency of regret on feature dimension $d$? Do they the same as bottom layer algorithm, e.g., linear for UCB and $d^{1.5}$ for TS?", "limitations": "See weakness.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nHyperparameter tuning for contextual bandits is an important and interesting problem. The idea of using adversarial bandits to select best hyperparameter is simple yet very intuitive. The proposed method has a non-trivial (although may not be optimal) regret guarantee and could be also of interest to practice. The paper is also well written and the main paper is easy to follow. \n\nWeakness:\n\nI have two concerns regarding the paper:\n\n1. The regret is only analyzed for UCB and TS based generalized linear bandits and is not general. The proof technique heavily relies on analyzing confidence ellipsoid of generalized linear bandits. Is it possible to extend the two-layer method for tuning other specific algorithms such as elimination based algorithm or adversarial bandits such as EXP3 or even general bandit algorithm, just like other model selection baselines? \n\n\n2. The $O(T^{2/3})$ regret seems not optimal. The key challenge and novelty in the proof is bounding Quantity (A) where the history depends on the sequences of pulled hyperparameters instead of contextual bandits using a consistent hyperparameter. However, corralling idea can achieve $O(\\sqrt{T})$ regret as discussed in related work and is strictly better if only tuning one hyperparameter. Does the author suspect this $O(T^{2/3})$ is tight and inevitable in general case, if not allowing exponential dependency on the number of hyperparameters?\n\n3. A minor suggestion is the proof is a bit hard to follow as it mixed UCB and TS and I would suggest the authors make a better presentation.\n\n---------------After rebuttal---------------\nMost of my questions are answered and I increased my score accordingly.  I suggest the authors clearly discuss the regret dependency on dimension $d$ in the final version.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FrmdkJORj5w", "reviewer": "Reviewer_nYJA", "summary": "This paper proposed a two-layer bandits framework for automatic tuning of multiple hyper-parameters in contextual bandits algorithms. The bottom layer hosts the original bandits algorithm (UCB or TS-based), and the top layer is a set of EXP3 bandits algorithm, each of which is responsible for tuning one of the hyper-parameter in the parameter set. By sending the same global reward signals from the bottom layer to each of the top-layer bandits algorithm, the paper shows that the resulting regret bound has a linear (and not exponential) dependency on the number of hyper-parameters to be tuned. Experiments on synthetic and real-world data are performed for benchmarking and showing the advantage of the proposed framework in terms of cumulative regrets.", "questions": "- The syndicated bandits share similarity to a multi-agent setting, where each agent performs its dedicated task but the agents share the same global reward signals so as to act cooperatively. I wonder if you could draw any connection here to explain why it works much better in regret bound than using a single agent to tune the multiple parameters.\n\n- In the experiments, there are only two hyper-parameters with 15 possible combinations. Is the advantage seen in the plot from Syndicated  over TL-combined is due to the limited number of iterations? It would be better and more convincing to demonstrate the advantage of Syndicated if there were a test case with more hyper-parameters.", "limitations": "N.A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This paper can be of significant practical interest to a broad audience group who are interested in and using bandits algorithms. The auto-tuning algorithm for single and multiple hyper-parameters with a desirable regret bound provides a very useful tool for successful deployment of bandits algorithms.\n\n- The proposed algorithm comes with a regret bound analysis that offers assurance that its learning efficiency is much better than naively treating the multiple hyper-parameters as a single parameter with more options.\n\nWeaknesses\n- Besides theoretical analysis of the regret bound, it is also important to provide intuition on why the change from using a single top-layer bandit to multiple parallel bandits can allow us to avoid the exponential dependency of regret on the number of hyper-parameters. \n\n- The experiments were all conducted on test cases with only two parameters. It would be great to have concrete examples of more hyper-parameters and associated empirical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CGsz8gZK3GN", "reviewer": "Reviewer_6M9s", "summary": "This paper addressed an important and practical problem for bandit algorithms: how to auto-tune the exploration parameter to automate exploration-exploitation tradeoff to release the full power of bandit algorithms. The authors contributes knowledge on bandit hyperparameter auto-tuning with a bandit-over-bandit framework, applicable to important bandit algorithms class including LinUCB and LinTs. The proposed framework shares same flavor of EXP3 algorithms, in the sense that the superiority of a candidate exploration parameter is captured by a quantity as weight and then competes with other candidates. The validity of presented approach is backed by regret analysis and experiments.", "questions": "\nI have one question came from my personal interest. It would be of my great appreciation if the authors share their insights.\n\nMy question came from picking \"one\" class of bandit algorithms from a pool of candidate bandit algorithms\". You may already share same experience that, in your Algorithm 1 and 2, the \" time horizon T and warm up length T1\" are typically subject to change in practice. We may pick T and T1 subjectively, and I think we don't have a good strategy to find a pair of \"great (T , T1)\" to pick the \"best bandit algorithms from candidate pool\". \n\nYour framework invites to think about the possibility of \"bandit-ovet-bandit-over-bandit\" flavor framework to do automatic decision making. It would be great if you can share your thoughts on this point, if you also feel this is an interesting problem.", "limitations": "\nThe only interesting limitation came to my mind is the problem \"bandit algorithm candidate auto selection\" I elaborated in the questions section. This is not count as a limitation of current submission. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe writing is clear and easy to follow. \nThe authors did great job on presenting evidences of their claims, and the message is clear conveyed. \n\n\nWeaknesses:\n\nI am satisfied with the submitted version. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9fB_0hHfXPF", "reviewer": "Reviewer_UTTP", "summary": "This work studies the problem of hyperparameter tuning for contextual bandit algorithms.  Due to the unique properties of contextual bandits (no pre-collected dataset, and the decision have to be made online), offline tuning methods can not be directly applied. The authors proposed a two-layer framework to automatically tune the exploration hyperparameter in the process of bandit learning. A upper regret bound of $\\tilde O(T^{2/3})$ is proved for the proposed method in general. A $\\tilde O(T^{1/2})$ is derived for the UCB-based algorithm when the theoretical exploration parameter is no bigger than any elements in the tuning set. ", "questions": "- Why not perform the tuning for NeurUCB?\n- What are the  requirements of the candidate hyperparameter set, both theoretically and theoretically", "limitations": "See weakness.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The hyperparameter tuning problem is quite important and the proposed method is reasonable.\n- The theoretical analysis is sound to me.\n\nWeakness:\n\n- The empirical evaluation is quite toy.  (1) Why not also tuning more advanced bandit models, e.g., NeurUCB?  (2) In addition to the Movielens dataset, performing the evaluation on the Yahoo news recommendation dataset will be more convincing. \n- The   $\\tilde O(T^{2/3})$ upper regret bound is quite weak. \n- About the underlying assumptions on the search space of hyperparameter configurations is not clearly discussed. For example, the candidate hyperparameter set must be finite?  If it must be finite, how large it can be? Can it be larger than T? In the experiments, the size of the set is pretty small. It would be helpful and interesting if the author can add more discussions on more on the requirements of the candidate hyperparameter set, both theoretically and theoretically.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept