Lipschitz Bandits with Batched Feedback
Authors: Yasong Feng
Zengfeng Huang
Tianyu Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: batched bandits
Lipschitz bandits

Abstract: In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a $T$-step problem with Lipschitz reward of zooming dimension $d_z$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate $\widetilde{\mathcal{O}}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ using only $ \mathcal{O} \left( \log\log T\right) $ batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that $\Omega(\log\log T)$ batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate using minimal communication.

Lipschitz Bandits with Batched Feedback
Yasong Feng Shanghai Center for Mathematical Sciences Fudan University
Zengfeng Huang"
School of Data Science
Fudan University
ysfeng200fudan. edu. edu. cn
huangzf wudaan.ffdd....o eew.uddnnnnuuu.... en
Tianyu Wang'
Shanghai Center for Mathematical Sciences Fudan University
wangtianyudfuudan edu. cn
Abstract
In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for Ttst problem with Lipschitz reward of zooming dimension dz, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate ① T T
using only (log log T) batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that S2(log log T) batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate using minimal communication.
Introduction
Multi-Armed Bandit (MAB) algorithms aim to exploit the good options while explore the decision space. These algorithms and methodologies find successful applications in artificial intelligence and reinforcement learning [e.g..377] 3.. While the classic MAB setting assumes that the rewards are immediately observed after each arm pull, real-world data often arrives in different patterns. For example, observations from clinical trials are often be collected in batched fashion (34). Another example is from online advertising, where strategies are tested on multiple customers at the same time [0]. In such cases, any dnservation-dependent decision-makinn should comply with this data-arriving pattern, including MAB algorithms.
In this paper, study the Lipschitz bandit problem with batched feedback MAB problem where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. In such settings, rewards communicated only at the end of the batches, and the algorithm can only make decisions based on information up to the previous batch. Existing Lipschitz bandit algorithms heavily rely on timely access the reward samples, since the partition of arm space may change at any time. Therefore, they can not solve the batched feedback setting. To address this difficulty, we present novel adaptive algorithm for Lipschitz bandits with communication constraints, named Batched Lipschitz Narrowing (BLiN). BLiN learns the landscape of the reward by adaptively narrowing the arm set, so that regions of high reward are more frequently played. Also, BLiN determines the data collection procedure adaptively, so that only very few data communications are needed.
"Comesponding authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The above BLiN procedure achieves optimal regret rate Ö dett
(T (dg is the zooming dimension
26
15 and can be implemented in clean and easy-to-implement form. In addition to achieving optimal regret rate, BLiN also optimal the following senses:
BLiN's communication complexity is optimal. BLiN only needs (log log T) rounds of commu- nications to achieve the optimal regret rate (Theorem 2 and no algorithm can achieve this rate with fewer than (loog log I") rounds of communications (Corollary 2
BLiN's 's time complexity optimal (Remark [ if the arithmetic operations and sampling are of complexity (1),, then the time complexity of BLiN is ( which improve the best known time
complexity ( log T) for Lipschitz bandit problems [5].
1.1 Settings & Preliminaries
For Lipschitz bandit problem (with communication constraints), the arm set is a compact doubling metric space (A, d.)). The expected reward μ + 1-Lipschitz with respect the metric d.A- that is, |ạ([z)) (x22)] I dA((11 for any I1, E .A.
At time S T, the learning agent pulls where 6, is a mean-zero independent sub-Gaussian noise. Without loss of generality, we assume that 6 (0, 1), since generalizations to other sub-Gaussiaa noises not hard.
3i E A that yields reward sample y (a(are) et.
Similar to most bandit learning problems, the agent seeks to minimize regret the batched feedback environment. The regret is defined as R(T) = Ei= (μ² p(xx)), where μ denotes max p(r). For simplicity, define A, μ p(xr) (called optimality gap of x)) for all x E A.
1.1.1 Doubling Metric Spaces and the ((0, 1] 11 Metric Space
By the Assouad's embedding theorem (6. the (compact) doubling metric space (A,, dA)) can be embedded into Euclidean space with some distortion of the metric; See (43) for more discussions in machine learning context. Due to existence of such embedding, the metric space (IO, 11 lloo), where metric balls are hypercubes, is sufficient for the purpose of our paper. For the rest of the paper, we will use hypercubes in algorithm design for simplicity, while our algorithmic idea generalizes to other doubling metric spaces.
1.1.2 Zooming Numbers and Zooming Dimensions
An important concept for bandit problems in metric spaces is the zooming number and the zooming dimension 26 [4 39), which we discuss now.
Define the set of r-optimal arms as S(r) = fx E A A, S rr. .. For any r == 2- the decision space [o. 1] can be equally divided into 2di cubes with edge length r, which we call standard cubes (also referred to as dyadic cubes). The r-zooming number is defined
Nr # {C: C is standard cube with edge length r and C S(16r))
In words, N, the r-packing number of the set S(16r) terms standard cubes. The zooming dimension is then defined
d_ min 0: 3a 0, N, S ar Vr 2 for some i N}.
Moreover, we define the zooming constant C. as the minimal a to make the above inequality true for d,, C. = ma > 0: N, < ar -d. Vr = 2 for some i N).
Zooming dimension d2 can be significantly smaller than ambient dimension d and can be For simple example, consider problem with ambient dimension d = 1 and expected reward function u(x) for 0 < 1. Then for any = 2- with i > 4, have S(16r) N, = 16. Therefore, for this problem the zooming dimension equals to 0, with zooming constant C. 16.
16r, 1] and
1.2 Batched feedback pattern and our results
In the batched feedback setting, for a T-step game, the player determines a grid T T= (4o.... LB) adaptively, where 0 to < ti ... < <tp T and B & T. During the game, reward observations

---

are communicated to the player only at the grid points ti,-.. .t. As consequence, for any time tj, the reward ys cannot be observed until time tj. and the
t in the j-th batch, that is, 1-1 decision made at time depends only rewards up to time f5-1. The determination of the grid TT adaptive the sense that the player chooses each grid point 1 E 'T based on the operations and observations up to the previous point f--1-
In this work, we present BLiN algorithm solve Lipschitz bandits under batched feedback. During the learning procedure, BLiN detects and eliminates the 'bad area' of the arm set in batches and partition the remaining area according to an approporiate edge-length sequence. Our first theoretical upper bound is that with simple Doubling Edge-length Sequence I'm = 2-m++ BLiN achieves optimal regret rate (T
(T dx.11 #242
by using (loog T) batches.
Theorem 1. With probability exceeding 1 Edge-length Sequence (D-BLiN) satisfies
Ta. the T-eep total regret R(T) of BLiN with Doubling
R(T) TT. (log T
where d2 is the zooming dimension of the problem instance. In addition, D-BLiN only needs no more than Olog T) roundy of communications to achieve this regret rate. Here and henceforth, S only omits constants.
While D-BLiN is efficient for batched Lipschitz bandits, its communication complexity is not optimal. We then propose a new edge-length sequence, which we call Appropriate Combined Edge-length Sequence (ACE Sequence) to improve the algorithm. The idea behind this sequence is that by appropriately combining some batches, the algorithm can achieve better communication bound without incurring increased regret. As we shall see, BLiN with ACE Sequence (A-BLiN) achieves regret rate O (T with only Ollog log T) batches.
Theorem 2. With probability exceeding 78, the T-sepp total regret R(T) of A-BLiN satisfies
R(T) S T (log T) a/ta log log
where dg is the zooming dimension of the problem instance. In addition, Algorithm only needs no more than Ollog log T) rounds of communications to achieve this regret rate.
show that the optimal regret bound for Lipschitz bandits without communications constraints, where the reward observations are immediately observable after each arm pull, is R(T) $ T Lut1
As comparison, seminal works 26
(log T) I in terms of zooming dimension, and
N log T
R(T) (T) inf To
r Σ
in terms of zooming number. Therefore, A A-BLiN achieves optimal regret rate of Lipschitz bandits by using very few batches.
Moreover, our lower-bound analysis shows that 2(log log 7) batches are necessary for any algorithm to achieve the optimal regret rate. Thus, BLiN is optimal in terms of both regret and communication.
1.3 Related Works
The history of the Multi-Armed Bandit (MAB) problem can date back to Thompson this problems include the UCB algorithms [28 7 the arm climination method 20 32 36 the
42 Solvers for
e-greedy strategy 40) the exponential weights and mirror descent framework [8]
Recently, with the prevalence of distributed computing and large-scale field experiments, the setting of batched feedback has captured attention [e.g.. [7]. Perchet al. [33] mainly consider batched bandit with two arms, and matching lower bound for static grid is proved. It was then generalized
by Gao et al. 21 to finite-armed bandit problems.
their work, the authors designed an elimination method for finite-armed bandit problem and proved matching lower bounds for both static and adaptive grid. Soon afterwards, Zhang al. [46] studies inference for batched bandits. Esfandiari et
al. [19] studies batched lincar bandits and batched adversarial bandits. Han et al. [22 and Ruan et
3

---

al. [35
provide solutions for batched contextual linear bandits. Li and Scarlett [29] studies batched Gaussian process bandits. Batched dueling bandits have also been studied by 2 Parallel to the regret control regime, best arm identification with limited number of batches was studied in []] and [23]. Top-k arm identification in the collaborative learning framework also closely related to the
batched setting, where the goal is to mínimize the number of iterations (or communication steps)
between agents. In this setting, tight bounds have been obtained in the recent works [41 24]. Yet the problem of Lipschitz bandit with communication constraints remains unsolved.
The Lipschitz bandit problem is important in its own stand. The Lipschitz bandit problem was introduced as "continuum-armi" armed bandits" " [3, where the arm space is compact interval. Along this line, bandits that are Lipschitz (or Hölder) continuous have been studied. For this problem, Kleinberg [25] proves a 22(72/3) lower bound and introduced a matching algorithm. Under extra conditions on top of Lipschitzness, regret rate of (TT/22 was achieved [8] For general (doubling) metric spaces, the Zooming bandit algorithm 226 and the Hierarchical Optimistic Optimization (HOO) algorithm [15] were developed. In more recent years, some attention has been focused on Lipschitz bandit problems with certain extra structures. To name a few, Bubeck et al. [16] study Lipschitz bandits for differentiable rewards, which enables algorithms to run without explicitly knowing the Lipschitz constants. Wang al. 44 studied discretization based Lipschitz bandit algorithms from a Gaussian process perspective. Magureanu et al. [3 derive a new concentration inequality and study discrete Lipschitz bandits. The idea of robust mean estimators [1 5 was applied to the Lipschitz bandit problem to cope with heavy-tail rewards, leading to the development of near- optimal algorithm for Lipschitz bandit with heavy-tailed rewards [30] Lipschitz bandits where clustering is used to infer the underlying metric, has been studied by 45). Contextual Lipschitz
bandits have also been studied by [39] and [27). Yet all of the existing works for Lipschitz bandits
assume that the reward sample is immediately observed after each arm pull, and none of them solve the Lipschitz bandit problem with communication constraints.
This paper is organized as follows. In section 2 we introduce the BLiN algorithm and give a visual illustration of the algorithm procedure. In section gl we prove that BLiN with ACE Sequence achieves the optimal regret rate using only O (log log T)) rounds of communications. Section 4 provides information-tee -therrrict lower bounds for Lipschitz bandits with communication constraints, which shows that BLiN is optimal in terms of both regret and rounds of communications. Experimental
results are presented in Section 5
2 Algorithm
With communication constraints, the agent's knowledge about the environment does not accumulate within each batch. This characteristic of the problem suggests a 'uniform' type algorithm - we shall treat each step within the same batch equally. Following this intuition, in each batch, we uniformly play the remaining arms, and then eliminate arms of low reward after the observations are communicated. Next we describe the uniform play rule and the arm elimination rule.
Uniform Play Rule: At the beginning of each batch m, a collection of subsets of the arm space An = {Cm,,1 Cm.2, ... Cm,,AA.... } is constructed. This collection of subset Am consists of standard cubes, and all cubes in A., have the same edge length I'm We will detail the construction of An when we describe the arm elimination rule. We refer to cubes in Am as active cubes of batch m.
During batch m, each cube in Am is played n.m 16 T times, where T is the total time horizon. r
More specifically, within each C' E Am, arms IC,1, ICCm E C' are played 2 The reward samples { VC,,, ... mm JOEAm corresponding to { TC,2, , ICC. CEA. collected at the end of the this batch.
will be
Arm Flimination Rule: At the end of batch m, information from the arm pulls is collected, and estimate the reward of each C E Am by (C) = 1 Σmm UC,.- Cubes of low estimated rewards are then eliminated, according to the following rule: a cube C An is eliminated if
f. Pm (C)= 2 4rm. where pmax == maxceA.. Pm (C). After necessary removal of "bad cubes",
each cube in Am that survives the elimination is equally partitioned into
Ymu Tm+11
subcubes of edge
"One can arbitrarily play æ0.1, #0,2," " FCCmm m. as long 20,4 E C for i.

---

length Tm+1, where Tm+1 is predetermined. These cubes (of edge length rm+11 are collected to construct Am+1, and the learning process moves on to the next batch. Appropriate rounding may be required to ensure the ratio
I'm
is an integer. See Remark 2 for more details.
Pm++1
The learning process is summarized in Algorithm
Algorithm 1 Batched I. Lipschitz Narrowing (BLiN)
1: Input. Arm set A [0, 1 time horizon T.
2: Initialization Number of batches B; Edge-length sequence {rm | The first grid point 0;
Equally partition A to rf subcubes and define A1 as the collection of these subcubes.
3: Compute 7m 16 16log I' for 1, B
mm
4: for m = 1, ... do
5: For each cube C' Am. play arms IC,1, &Caam from C.
6: Collect the rewards of all pulls up to lm Compute the average payoff (m
- Ne. for
each cube C' E Am. Find Ta = maxcEAm To(C).
7: For each cube E Am. eliminate C. if pm (m > 4m Let Ar be set of cubes not eliminated.
8: Compute 1m+1 = fm + (Um/rmm1l 1d |Att -1m+1. 1f 2 T or m = B then break.
9: Equally partition each cube in At into Tm//Tm+1/ )
subcubes and define Am+1 as the collection of these subcubes. S*See Remark 2 for more details cases where (fm//m+11) is not an integer:*/
end for Cleanup: Arbitrarily play the remaining arms until all T steps are used.
11:
The following theorem gives regret and communication upper bound of BLiN with Doubling Edge- length Sequence r' = 2-++1 (see Appendix for proof). Note that this result implies Theorem
1
Theorem With probability exceeding Edge-length Sequence (D-BLiN) satisfies
Ta, the T-step total regret R(T) of BLiN with Doubling
R(T) S 528(1og T) 7.72 T T
where dgy is the zooming dimension of the problem instance. In addition, D-BLiN only needs more rounds of communications to achieve this regret rate.
than log T-log log
d,+2
Although D-BLiN efficiently solves batched Lipschitz bandits, its simple partition strategy leads to suboptimal communication complexity. Now we show that by approporiately combining some batches, BLiN achieves the optimal communication bound, without incurring increasing regret. Specifically, we introduce the following edge-length sequence, which we call ACE Sequence.
Definition 1. For problem with ambient dimension d, zooming dimension de and time horizon T, d,+1 we denote (d+2)(d,+2 log T and Cs+1 ne; for any 2 1, where
T
d+1-ds Then the d+2
Appropriate Combined Edge-length Sequence {rm} is defined by I' = 2 E. for any m 2 1.
We show that BL.iN with ACE Sequence (A-BLiN) obtains an improved communication complexity, thus proves Theorem 2
Theorem 4. With probability exceeding fs. the T-step total regret R(T) of Algorithm 7 satisfies
128C,
d=1l T T (log T) 2,72
R(T)
2+2 log log + 8e
(2)
log T+1-d;
where de is the zooming dimension of the problem instance. In addition, Algorithml 7 only needs no
more than
log Ing rounds of communications to achieve this regret rate. log
The partition and elimination process of a real A-BLiN run is in Figure the i-th subgraph, the white cubes are those remaining after the (i - 1) batch. In this experiment, we set A = [0. 1 and the optimal arm is x² (0.8, 0.7). Note that x is not eliminated during the game. More details of this experiment are in Section 5
5

---

Figure I: Partition and elimination process of A-BLIN. The i-th subfigure shows the pattern before the i-th batch, which is from real A-BLiN run on the reward function defined Section [ Dark gray cubes are those eliminated in the most recent batch, while the light gray ones are those eliminated in earlier batches. For total time horizon T 80000, A-BLiN needs 4 rounds communications. For this experiment,
I g1 T3 16
which is the ACE sequence (rounded as 32
Remark 2 for and d₂ 0.
Remark (Time and space complexity). The time complexity of our algorithm is O(T), which is better than the state of the (T' in (15). This is because that the running time of batch is of order O(4y), ) where 1j = tj tj-1 is number of samples in batch j. Since E T, the time complexity of BLiN is O(T). Besides, the space complexity of BLiN is also improved, because do not need store information of cubes in previous batches.
Regret Analysis of A-BLiN
In this section, we provide regret analysis for A-BLiN. The highlight of the finding is that Olog log T)
batches are sufficient to achieve optimal regret rate of (T
4.+1
3=12
summarized in Theorem 4
To prove Theorem 4 we first show that the estimator f is concentrated to the true expected reward J (Lemma D. and the optimal arm survives all eliminations with high probability (Lemmal 2). In the following analysis, we let Bstop be the total number batches the BLiN run.
Lemma 1. Define
16 T
S Bstop 1, VC Am, Yo E E
8:
(mm(C))] I'
VI
nmm
holds that P 1 -6
Lemma Under event E, the optimal arm x= arg argmax p(x) is not eliminated after the first Bstop batches.
Based on these results, we show the cubes that survive elimination are of high reward.
Lemma 3. Under event E, for any 1 I I Bstop: any C E Am and any C, A2 satisfies
A < 8rm-1-
(3)
The proofs Lemma 1-3 are in Appendix A
We are now ready to prove the thcorem.
Proof of Theorem 4 Let R.,. denote regret of the m-th batch. Fixing any positive number B, the total regret R(T) can be divided into two parts: R(T) = Em Rm + > Rm- In the following, we bound these two parts separately and then determine B to obtain the upper bound the total regret. Moreover, we show A-BLiN uses only Olog log 7') rounds of communications to achieve the optimal regret.
Recall that Am is set of the active cubes in the m-th batch. According to Lemma 3 for any UCEAA C, have A2 S 88m Let A# be cubes not eliminated in batch m. Then any cube At is subset of 8(8rm-1). and thus
1 1h-1l= S Nr S Carmd
(4)

---

By definition, Tm = 11 mm, so
[Aml = 2 1A m
(5)
The total regret of the m-th batch is
Rm Σ
I 1Aml
16 16log
8rm =
(1)
2dcm
|
16log
8rm-1
20,
r
r
CEAm
1=1
(1)
I 2dcm
Cormbnt) m-1
128 log
(16)
20 +))d=+1)+emm((d (d+22) 128C, log
r
where (i) follows from ( (ii) follows from and (iii) follows from the definition of ACE Sequence.
m- ()2 + 1) + cm (d 2). Since Cm Cm-1 d+1-d= Define C. 12i=T
calculation shows that
d+2
Cm (Ei=1 (d2 + +) + cm-1 + 2) + cm-1 (d2 + 1 d - 2) + Cm (d + 2) for any m, we have C,.. C1 (d Hence,
Cm-1- Thus
Rm S 20 (d+2)) 1280, log T4++2 dx+1
128C2(log) T') 4at2
(6)
The inequality 6 holds even if the m-th batch does not exist (where we let Rm = 0) or is not completed. Thus we obtain the first upper bound Em<B Rm S T 128C, (log T) 2,7. Lemma 3 implies that any x played after the first B batches satisfies A, 8rp, the total regret after B batches is bounded by
Σ Rm <8rB T 8T .2 2 El = -T -8 2- B>B
8T 1:72 (log T) م,42 (T/log log T) do do-2 S 81 dst2 (logT) a.to T2
Therefore, the total regret R(T)) satisfies
R(T) Σ Rm +
Σ m>B
Rm S (228C= B 8T T T (log T) प.ी..
MCB
This inequality holds for any positive B.
Then by choosing B*
log log T log +2)
log
log log +2) we have n 1
and
log a=1-ds
242
d
TogT
128C, log log d+2
dxt1 T -Ta+t (log T)astz
R(T) S
8e
log J+1-d;
The above analysis implies that we can achieve the optimal regret rate Ö ( by letting the for-loop run B* times and finishing the remaining rounds in the Cleanup step. In other words, B* + rounds communications are sufficient for A-BLiN to achieve the regret bound
in line 9 of Algorithm I may not be integers for some m. Thus, Remark 2. The quantity
Tuo-1 D c.J. Bn 1 c, and define rounded ACE Sequence Br for m 2k. Then the total regret can
practice we denote O'n
by Pm 0tc for m 2k and Fm 2- be divided R(T) E1StSB RZx-1 + E1 Ras Em>2B- Rm. For the first part we have F2k-2 Tk-1 and F2 Tk, while for the second part we have Pak-1 2. Therefore, by Fak
similar argument to the proof of Theorem 4 we can bound these three parts separately, and conclude that BLiN with rounded ACE sequence achieves the optimal regret bound Ö 4: by using only Olog log T') rounds of communications, The details are in Appendix C
7

---

Lower Bounds
In this section, we present lower bounds for Lipschitz bandits with batched feedback, which in turn gives communication lower bounds for all Lipschitz bandit algorithms. Our lower bounds depend on the rounds of communications B. When for the vanilla Lipschitz bandit problem @ (T)) (R²(T) is defined in Eq. More importantly, this dependency B gives the minimal rounds of communications needed to achieve optimal regret bound for all Lipschitz bandit algorithms. which is summarized in Corollary 2 Since this lower bound matches the upper bound presented in Theorem 4 BLiN optimally solves Lipschitz bandits with minimal communication.
sufficiently large, our results match the lower bound
4.1 Proof Outline
Similar to most lower bound proofs, we need to construct problem instances that are difficult to differentiate. What's different that we need to carefully integrate batched feedback pattern [33] with the Lipschitz payoff reward [39 [30]. To capture the adaptivity in grid determination, we construct "static reference communication grids" to remove the stochasticity in grid selection [1] Below, we first consider the static grid case, where the grid is predetermined. This static grid case will provide intuition for the adaptive and more general case.
The expected reward functions of these instances are constructed as follows: we choose some 'position' and 'height', such that the expected reward function obtains local maximum of the specified 'height' at the specified "position'. We will use the word 'peak' to refer to the local maxima. The following theorem presents the lower bound for the static grid case.
Theorem 5 (Lower Bound for Static Grid). Consider Lipschitz, bandit problems with time horizon T such that the grid of reward communication T is static and determined before the game. If B rounds of communications are allowed, then for any policy n, there exists a problem instance such that
[[RT(=)) (log
(atat))
RS (T) (T))'((az)*)
where > O is numerical constant independent of B, T, n and T, (T) is defined in and d is the dimension of the arm space.
To prove Theorem we first show that for any k: > 1 there exists an instance such that ([)) 2
Fixing t: > I, we let Tk-
and Ms : 1- Then we construct a set of problem
instances Ia I... J J. such that the gap between the highest peak and the second highest peak is about for every instance in Ig.
Based on this construction, we prove that no algorithm can distinguish instances in I& from one another in the first (k- - 1) batches, so the worst-case regret is at least rsty, which gives the inequality we need. For the first batch (0, ti.. we can easily construct set of instances where the worst-case regret is at least 11, since no information is available during this time. Thus, there exists a problem
instance such that [[]T(T)] Z max
t1
Since < t < ... < tB = T, the
inequality in Theorem follows.
As result of Theorem 5 we can derive the minimum rounds of communications needed achieve optimal regret bound for Lipschitz bandit problem, which is stated in Corollary []
Corollary 1. Any Lipschitz bandit algorithm needs Vilog log T') rounds of communications to achieve the optimal regret rate, for the case that the times of reward communication are predetermined and static
The detailed proof of Theorem and Corollary are deferred to Appendix D and t
4.2 Communication Lower Bound for BLiN
So far we have derived lower bounds for the static grid case. Yet there is gap between the static and the adaptive case. We will close this gap in the following Theorem.
8

---

Theorem 6 (Lower Bound for Adaptive Grid). Consider Lipschitz bandit problems with time horizon T such that the grid of reward communication adaptively determined by the player. If B rounds of communications are allowed, then for any policy there exists an instance such that
(Z E 2C
T) (aia)))
Rd (T)
where с > is numerical constant independent of B, T, a and T, (T) is defined in 7 and the dimension of the arm space.
To prove Theorem we consider a reference static grid T, = {Tu, T1, ... TB}. where T, = 7 2 for E = d+2' We construct a series 'worlds', denoted by I,. .I.. Each world a set of problem instances, and each problem instance world Z; is defined by peak location set U4 and basic height rj. where the sets Lj and quantities Tj for 1 S S B are presented in Appendix [
Based on these constructions, we first prove that for any adaptive grid and policy, there exists an index ) such that the event A, = -t < T--1, 2 Tý} happens with sufficiently high probability world Σj. Then similar to Theorem [ we prove that in world I, there exists set of problem instances that is difficult to differentiate in the first j batches. In addition, event Aj implies that t, 2 J,. so the worst-case regret least r, TT which gives the lower bound we need.
The proof of Theorem is deferred to Appendix F Similar to Corollary |
we can prove that at least alog log T)) rounds of communications needed achieve optimal regret bound. This result is formally summarized in Corollary
Any Lipschitz bandit algorithm needs 2(log log T) rounds of communications to achieve the optimal regret rate.
Corollary 2.
5
Experiments
In this section, we present numerical studies of A-BLiN. In the experiments, we use the arm space
A [0, 1]2 and the expected reward function u(x) = 1 | x ||2 1o || x2/12 where = 70.8. 0.7) and #2 = (0.1, 0.1). The landscape of and the resulting partition is shown in Figure ((a) As can be seen, the partition finer in the area closer to the optimal arm x² = (0.8, 0.7).
1.0
3500
3000
2500
0.8
2000
0.4
0.5
2500
044
Zooming
500
ABUN
0.0
02
0.4
0.8
0.8
1.0
20000
40000
60000
80000
(a) Partition
(b) Regret
Figure 2: Resulting partition and regret of A-BLiN, In Figure 2(a) we show the resulting partition of A-BLiN. The background color denotes the true value of expected reward μ. and blue means high values. The figure shows that the partition is finer for larger values of In Figure 2(b) we show accumulated regret of A- A-BLiN and zooming algorithm (6).. In the figure, different background colors represent different batches of A-BLiN, For the total time horizon T = 80000, A-BLiN needs 4 rounds of communications.
We let the time horizon T' 80000, and report the accumulated regret in Figure 2(b) The regret curve is sublinear, which agrees with the regret bound (2). Besides, different background colors in Figure 2(b) represent different batches. For the total time horizon T 80000, A-BLiN only needs rounds of communications. We also present regret curve of zooming algorithm (26 for
"including algorithms of which the number of batches be determined adaptively

---

comparison. Different from zooming algorithm, regret curve of A A-BLiN is approximately piecewise linear, which because the strategy of BLiN does not change within each batch. Results more repeated experiments are in Appendix G as well as experimental results of D-BLiN. Our code is Narrowing
available at https:///.t.t......aaa///aaaaaaa
Conclusion
In this paper, we study Lipschitz bandits with communication constraints, and propose the BLiN algorithm as solution. We prove that BLiN only need O (log log T) rounds of communications to achieve the optimal regret rate of best previous Lipschitz bandit algorithms [26 [4] that need batches. This improvement in number of the batches significantly saves data communication costs. We also provide complexity analysis for this problem. We show that Q(log log rounds of communications are necessary for any algorithm to optimally solve Lipschitz bandit problems. Hence, BLiN algorithm is optimal.
Acknowledgments and Disclosure of Funding
This work was partly supported by the National Key Research and Development Program China (200AAAA0006000);
References
[1] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Conference on Learming Theory, pages 39-75. PMLR, 2017.
[2] Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Batched dueling bandits. arXiv preprint 22X6v:2202.10660, 2022.
[3] Rajeev Agrawal. The aantin bandit problem. SIAM Journal on Control and Optimization, 3366); 1995.
[4] Rajeev Agrawal. Sample mean based index policies by O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 1054):1054-1 1071-0188--1----111111111111 1995.
[5] Noga Alon, Yossi Matias, and Mario Szegedy, The space complexity of approximating the frequency moments. Journal of Computer and System Sciences. 58(1):137-147, 1999.
[6] Patrice Assouad. Plongements Lipschitziens dans R Bulletin de la Société Mathématique de France, 41:4429444, 1983.
[7] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[8] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-2) 77, 2002.
[9] Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved rates for the stochastic continuum- armed bandit problem. In Conference on Computational Learning Theory, pages 454 468. Springer, 2007.
[10] Dimitris Bertsimas and Adam Mersereau. learning approach for interactive marketing to customer segment. Operations Research, 55(6): 1130-1135, 2007.
[11] Peter J. Bickel. On some robust estimates of location. The Annals of Mathematical Statistics, pages 847-858, 1965.
[12] Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Séminaire de probabilités de Strasbourg, 12:342-363. --33,, 1978.
[13] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IFEE Transactions Information Theory, 59(11) 2013.
10

---

[14] Sébastien Bubeck, Rémi Munos, Gilles Stoltz. and Csaba Szepesvári. Online optimization in X'armed bandits. Advances in Neural Information Processing Systems, 22:201-208, 2009.
[15] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X'aammed bandits. Journal of Machine Learning Research, 12(5): (555):65551699 2011.
[16] Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the Lipschitz constant. In International Conference on Algorithmic Learning Theory, pages 144-158. Springer, 2011.
[17] Nicolo Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26: 160-1168, 2013.
[18] Eric W. Cope. Regret and convergence bounds for class of continuum-armed bandit problems. IEEE Transactions Automatic Control, 14(6)):243-12555 2009.
[19] Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7340-7348, 2021.
[20] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi- armed bandit and reinforcement learning problems. Journal of machine learning research, 7 2006.
[21] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi- bandits problem. Advances in Neural Information Processing Systems, 32:503-513, 2019.
[22] Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits. arXiv preprins 26X35. 2020.
[23] Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu. Top identification in multi-armed bandits with batch arm pulls. In Artificial Intelligence and Statistics, pages 139-148. PMLR, 2016.
[24] Nikolai Karpov, Qin Zhang, and Yuan Zhou. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 160-171. IEEE, 2020.
[25] Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 18:697-704, 2005.
(26] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 68 669-690, 2008.
[27] Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. Contextual bandits with continuous actions: smoothing, zooming, and adapting. In Conference on Learning Theory, pages 2025-2027. PMLR, 2019.
[28] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, 6(1):4-22, 1985.
[29] Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, pages 92-107. PMLR, 2022.
[30] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithms for Lipschitz bandits with heavy-tailed rewards, In International Conference on Machine Learning, pages 4164-4163, 2019.
[31] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999. PMIR, 2014.
11

---

[32] Vianney Perchet and Philippe Rigollet. The multi aumei bandit problem with covariates. The Annals of Statistics, 41(2):693-721, 2013.
[33] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 14(2):660-68) 2016.
[34] Stuart Pocock. Group sequential methods in the design and analysis of clinical trials. Biometrika, 64(2):191-199, 1977.
[35] Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 74-87, 2021.
[36] Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinking based bayesian optimization algorithm with order-optimal regret performance. In Advances in Neural Information Processing Systems, volume 34, pages 28836-28847, 2021.
[37] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[38] Sean Sinclair, Tianyu Wang, Gauri Jain, Siddhartha Banerjee, and Christina Yu. Adaptive dis- cretization for model-based reinforcement learning. Advances in Neural Information Processing Systems,,3:3888 33:3858- -8781, 2020.
[39] Aleksandrs Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 15(1):2533-250) 2014.
[40] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[41] Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: tight bounds for distributed exstributedexlloraaiin multi-armed bandits. 20/9 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 126-146. IEEE, 2019.
[42] William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933.
[43] Tianyu Wang and Cynthia Rudin. Bandits for BMO functions. In International Conference Machine Learning, pages 9996-19969999 10066. PMLR, 2020.
[44] Tianyu Wang, Weicheng Ye, Dawei Geng, and Cynthia Rudin. Towards practical lipschitz bandits. In Proceedings of the 2020 ACM-IMS on Foundations Data Science Conference, FODS '20, page 129-138, New York, NY. USA, 2020. Association for Computing Machinery.
[45] Nirandika Wanigasekara and Christina Yu. Nonparametric contextual bandits in an unknown metric space. In Advances in Neural Information Processing Systems, volume 32, pages 14684-14694, 2019.
[46] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits, Advances in Neural Information Processing Systems, 1199818-98229 2020.
Checklist
1. 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? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
12

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you 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]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you 'r 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 or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable?
[N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "elGyofNnM-H", "reviewer": "Reviewer_fkQo", "summary": "This paper studied the problem of Lipschitz bandit learning with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. The authors introduced a landscape-aware algorithm called BLiN to solve this problem. The authors showed that for a $T$-step problem with order-optimal regret with order-optimal batches (i.e., communication rounds).", "questions": "\n- Although the batched version of Lipschitz bandit learning is new, the analysis techniques used in proving the key results in Theorem 4 appear to be standard. It's unclear what new technical contributions this paper provides in the proof and it would be great if the authors could provide further clarifications.\n\n- The experiments in this paper are rather basic and small-scale (two-dimensional). This paper could benefit from more extensive and larger-scale experiments to verify the theoretical results.\n\n- There seems to be a mismatch between the motivating examples and the studied batched Lipschitz bandit problem in this paper. For example, in distributed computing, it is more typical that the batches are generated in a fixed periodic fashion. However, in later settings in this paper, the grid points (i.e., the timing of batched observations) are adaptive and can be controlled by the player. Could the author also analyze the periodic version of batched Lipschitz banding learning?", "limitations": "This paper is theoretical and not relevant to negative societal impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ This paper studied a batch-version of Lipschitz bandit learning, which is new in the literature.\n+ The authors established the order-optimality of communication for their proposed BLiN algorithm.\n\nWeaknesses:\n\n- Novelty and contributions are unclear in this paper.\n\n- Experiments are rather limited.\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": {}}, {"review_id": "S8QIJWg6Rw8", "reviewer": "Reviewer_Bnts", "summary": "This paper studies Lipschitz bandits with batched feedback where the expected reward is a Lipschitz function of arm and the feedback is accessible only in the end of each batch. The paper proposes elimination-based algorithms and derives the regret bound of the proposed algorithms. Lower bounds are also provided to show that the proposed algorithm is nearly optimal in terms of regret and number of batches. Experiments on synthetic dataset demonstrate that the proposed algorithm can achieve regret comparable to existing Lipschitz bandits algorithm with immediate feedback.", "questions": "Can the number of cubes over T rounds be upper bounded? What is the time and space complexity of cube partition over T rounds?", "limitations": "The potential negative societal impact of this work is ignorable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper is the first to study the batched setting in the context of Lipschitz bandits. The proposed algorithms are novel in the sense that most of existing Lipschitz bandits algorithms are based on the zooming method while this paper takes the elimination method as the algorithmic framework. The proposed algorithms are nealy optimal as both upper bounds and matching lower bounds are established. The empirical performance on synthetic dataset is also promising.\n\nWeakness:\nWhile the paper discuss the time complexity, it ignores the time cost of cube partition. The motivation of the batched setting originates from real-world data but the proposed algorithms are only tested on synthetic datat.", "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": "RDQzq37e_Au", "reviewer": "Reviewer_XwZm", "summary": "This paper provides a batched algorithm for Lipschitz bandit optimization. In each batch, the algorithm divides the remaining domain into cubes, makes a certain amount of arbitrary pulls in each cube, and eliminates sub-optimal cubes based on the noisy observations. This method achieves optimal cumulative regret of $\\widetilde{O}(T^\\frac{d_z+1}{d_z+2})$ in terms of zooming dimension $d_z$ using $O(\\log\\log T)$ batches. This work also provides lower bounds for general algorithms of B batches with predetermined and adaptively determined batch allocations, showing $\\Omega(\\log\\log T)$ batches is necessary for algorithms with optimal regret.\n\nGenerally, the paper is well-written. The proposed method is easy to understand and has good theoretical analysis.", "questions": "- What are the advantages of the proposed algorithms over other Lipschitz bandit algorithms with optimal regret except for the number of batches?\n- The algorithm arbitrarily pulls $n_m$ arms in each cube. Does uniformly selecting arms with equal distance make more sense?\n- Executing A-BLiN requires knowing the zooming dimension to compute the ACE sequence. Can we obtain the value of the zooming dimension when the true function $\\mu$ is unknown?\n- In figure 2(b), the slope (or simple regret) of the last batch is not zero. Is there any evidence showing the remaining cubes after the last batch have small sub-optimalities?\n- Based on my understanding, the ACE sequence can be predetermined without randomness as in definition 1. Why the sequences of different trials are different in figure 3?", "limitations": "There are some discussions regarding the time and space complexity. In the experiments, only one existing algorithm is used for comparison and even has better regret than the proposed algorithm. I recommend trying some different T and therefore different B.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The algorithm is evaluated comprehensively based on its performance, time complexity, and space complexity.\n- The appendix shows significant efforts in theoretical analysis.\n- The results are also supported by experiments.\n\nWeakness:\n- We need to know the zooming dimension in advance if we wish to use the ACE sequence to achieve $O(\\log\\log T)$ batches.\n- I think the constant term in theorems 3 and 4 might be too large for a 1-Lipschitz function on $[0,1]^d$.\n- The practical performance is slightly worse than the baseline algorithm in figure 2(b).\n\nMinor comments:\n- I recommend rephrasing theorems 1 and 2 into the normal text since this is the introductory section and theorems 3 and 4 will show the details.\n\nSome works worth mentioning: \n- A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance\n- Gaussian Process Bandit Optimization with Few Batches\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": {}}, {"review_id": "FvqN0mGOH3", "reviewer": "Reviewer_ADGD", "summary": "The paper considers the problem of Lipschitz-bandits when the evaluations arrive in batches. Two algorithms are proposed. The more adaptive one achieves log-optimal regret with an optimal number of batches. The theoretical part provides regret upper bounds for the algorithms, and lower bounds for static and adaptive grid algorithms. Small empirical evaluations provide illustration on the partition mechanism if the algorithms and a comparison with the zooming algorithm. \n", "questions": "How would be the bounds affected with a different Lipschitz constant, or if the constant would be unknown?\n\nWhile there is some indication in e.g. line 85 of what the authors mean by optimality, it would be useful to specify it more formally, since it is referred in some theoretical statements (e.g. Corollary 2)\n", "limitations": "The lower bound for the adaptive case relies on the choice of number of batches (B). This would exclude algorithms that adapts the number of batches depending on feedback. This is not a major limitation, and the proofs might be adapted to include this more adaptive variant, but the limitation could be mentioned by the authors.\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The batched Lipschitz bandit is reasonably interesting, although its applicability of the proposed algorithms is somewhat limited by the 'weak' regret bounds that are usual for Lipschitz bandit problems that have no further assumptions. In fact the low number of batches required (log log T) to achieve log-optimal regret is indicative of how little adaptivity is required in selecting the evaluation points. \n\nFor the problem in case, the authors do well to design an algorithm with low communication, and prove matching upper and lower bounds. The algorithm has low (time/space) complexity as well, although this is usually not a major problem for most Lipschitz bandit algorithms. \n\nWhile the empirical work is not extensive, it is sufficiently illustrative to understand the performance of the algorithm. It would have been interesting to see some examples where the optimality gap between local optima is smaller. \n\nThe paper is well written with a clear structure. \n\nWhile the relevant literature is discussed w.r.t. the proposed problem and results, there could be some deeper insight provided on how the proof techniques relate to the proof techniques used for similar problems.\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