Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).
strengths_and_weaknesses: Strengths:

+ This paper studied a batch-version of Lipschitz bandit learning, which is new in the literature.
+ The authors established the order-optimality of communication for their proposed BLiN algorithm.

Weaknesses:

- Novelty and contributions are unclear in this paper.

- Experiments are rather limited.

questions: 
- 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.

- 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.

- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

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. 

For 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. 

While 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. 

The paper is well written with a clear structure. 

While 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.

questions: How would be the bounds affected with a different Lipschitz constant, or if the constant would be unknown?

While 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)

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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
This 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.

Weakness:
While 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

Generally, the paper is well-written. The proposed method is easy to understand and has good theoretical analysis.
strengths_and_weaknesses: Strengths:
- The algorithm is evaluated comprehensively based on its performance, time complexity, and space complexity.
- The appendix shows significant efforts in theoretical analysis.
- The results are also supported by experiments.

Weakness:
- We need to know the zooming dimension in advance if we wish to use the ACE sequence to achieve $O(\log\log T)$ batches.
- I think the constant term in theorems 3 and 4 might be too large for a 1-Lipschitz function on $[0,1]^d$.
- The practical performance is slightly worse than the baseline algorithm in figure 2(b).

Minor comments:
- 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.

Some works worth mentioning: 
- A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
- Gaussian Process Bandit Optimization with Few Batches

questions: - What are the advantages of the proposed algorithms over other Lipschitz bandit algorithms with optimal regret except for the number of batches?
- The algorithm arbitrarily pulls $n_m$ arms in each cube. Does uniformly selecting arms with equal distance make more sense?
- 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?
- 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?
- 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.
review_title: null

Meta-review: metareview: This is an interesting work that initiates the study of Lipschitz bandits in the case of batched feedback. That it is possible to obtain nearly optimal regret with such little adaptation (only $\log \log T$ batches), as the authors do, is an interesting result; moreover, the regret lower bound based on the number of batches shows that the optimal regret can be achieved only with $\Omega(\log \log T)$ batches, implying the authors’ method A-BLiN has communication complexity no higher than methods obtaining the optimal regret.

All reviewers are positive on this work and the work merits acceptance; that said, as some reviewers suggested, the authors would do well to highlight the novelty of their approach and relate their proof techniques to proof techniques used for similar problems. Also, I noticed that the claims need to be adjusted somewhat. At times the authors claim that their regret rate is optimal or (prior to Definition 1 and in reference to A-BLiN) "without incurring increasing regret"; this is not correct, due to the extra $\log \log T$ factor. The authors should instead say that the regret rate is near-optimal and that the regret does not increase by much (but the rate certainly does worsen, however so slightly). It is important to be clear on optimality vs near-optimality. In any case, congratulations.
confidence: Certain
Decision: Accept