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: The authors study the batched dueling bandit problem under the Condorcet condition. They design an algorithm named C2B with a few adaptive rounds, and derive the upper bound for the asymptotic regret. Computational experiments are carried out with a number of real-world datasets.
strengths_and_weaknesses: Strength:
1. The authors show that the proposed algorithm can achieve good performance with number of batches as small as $O(\log t)$, which seems an interesting and new result.
2. The feature of few adaptive rounds of the algorithm might accommodate modern applications of large scale.
3. Overall, the paper is well-organized and easy to follow. The paper is detailed in backgrounds as well.

Weakness:
Please find my questions/concerns in the next part.
questions: 1. The authors claim that their method can nearly achieve the best rate for regret (line 12 and 115). Meanwhile, they mention a lower bound of $O(\frac{K}{\Delta_{\min}}\cdot poly(\log T))$ (line 113), while the regret bound they derive is $\tilde{O}(\frac{K^2}{\Delta_{\min}^2})$. It seems a gap exists here, especially when $K$ is large or $\Delta_{\min}$. Is it possible to diminish the gap by trade-off the number of batches with performance?

2. In the proposed algorithm, whenever a pair $(i,j)$ is compared in round $r$, it is always compared $q_r = \lfloor q^r\rfloor$ times. Will it be useful to adaptively assign the number of times for compare at each round based on previous compare results, in order to improve the performance? Intuitively, we might want to compare a pair more times if it is harder to tell which one is better.
limitations: The authors discuss the limitations of their work to some extent. There seems no negative societal impact.
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 work considered the batched dueling bandit problem under the Condorcet condition. It proposed a sequential elimination-based algorithm and derived regret bounds in expectation and with high probability. It also presented numerical experiments to show the effectiveness of the proposed algorithm.
strengths_and_weaknesses: Strengths: The paper is well organized and is easy to follow. It clearly discussed the motivation of problem setting, algorithm design and the technique challenges in detail and evaluate the algorithm with real-life datasets.

Weaknesses: A lower bound may help strengthen the theoretical results and more explanation in the experiments setup is appreciated. (See "Questions" part for more details.)
questions: 1. Are the authors willing to provide a regret lower bound? If it matches the derived lower bound, it would be more convincing that the upper bound is tight and the algorithm is optimal. There should be some discussions in Section 1.4.
2. As the algorithms are proposed for different settings, how are they compared? It is nice that the algorithms are compared using several datasets, but more explanation of the experiment setup is appreciated.
3. In Section 2, in addition to the detailed discussion, the readers may get a even clear view if a table comparing the bounds and conditions of algorithms in the existing literature is presented.
limitations: There seems to be no societal issue from my view.
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 studies the dueling bandit problem with regret minimization as the objective under the assumption of an existing Condorcet winner. In contrast to most existing work dealing with fully adaptive learning situations, this work considers the situation of batched learning, where the learner does not decide before each learning round which pairwise comparison to perform, but decides this only in a limited number of rounds, i.e., it performs a batch of the same pairwise comparison at certain learning rounds. For this learning scenario, a learning algorithm is proposed that has a near-optimal upper bound on its cumulative regret using a nearly optimal number of batches. This improves upon existing methods which additionally need stronger assumptions than merely the existence of a Condorcet winner. The suggested algorithm is compared in a numerical study on real-world data sets with existing regret minimizing learning algorithms for the dueling bandit setting.
strengths_and_weaknesses: # Strengths

- Batched learning settings are definitely relevant for practical applications and have also been studied recently in the standard multi-armed bandit setting. Thus, the scope of the paper is relevant to the ML community. 

- The paper is generally well-written. The notation is well thought out and the main ideas underlying the suggested learning algorithm are described in sufficient detail.
- Although the learning setting is not novel, as it has been considered by other authors before, the suggested learning algorithm comes with stronger theoretical guarantees than existing methods.
- The proofs seem to be sound as far as I can tell.

# Weaknesses

## Related literature

There is some missing related literature:

-  Mark Braverman, Jieming Mao, and S. Matthew Weinberg. Parallel algorithms for select and partition with noisy comparisons. In Proceedings of the ACM symposium on Theory of Computing, pages 851- 862, 2016. 

This paper also studies the question of round/batch complexity of learners in the dueling bandit setting, but for the objective of finding the top-k arms.

- Chuang-Chieh Lin and Chi-Jen Lu. Efficient mechanisms for peer grading and dueling bandits. In Asian Conference on Machine Learning (ACML), pages 740-755, 2018.

This paper studies the question of round/batch complexity of learners in the multi-dueling bandit setting (with utilities of the arms), but for the objective of finding the best arm (NB: the Borda winner scenario is considered as well).

Although the objectives of the two papers are different from the considered regret minimization objective, I think they are definitely worth mentioning.

As a side note: These two papers are discussed in the following survey paper on dueling bandits (Section 3.1.18, 3.2.6, and 4.2.8):

- Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., & Hüllermeier, E. (2021). Preference-based Online Learning with Dueling Bandits: A Survey. Journal of Machine Learning Research, 22(7), 1-108.

Moreover, there are some missing references (lines 166-167) regarding the multiple arm comparison for the regret minimization objective (see Chapter 6 of Bengs et al. (2021)).

## Experimental study 

The experimental study leaves room for improvement. First, the considered competing algorithms BTM and RUCB are out of date and Double Thompson Sampling and Self-Sparring are currently the state-of-art (together with the considered RMED). Next, it is a bit doubtful that the elimination strategy is changed for the experiments, although the theoretical analysis uses a Hoeffding-based elimination strategy. While I agree with the author’s statement that *the theoretical guarantee will continue to hold*, it is nevertheless something that needs to be shown. Thus, the authors should include the original algorithm in the experiments and call the one using KL elimination differently in the experiments. Finally, it would be nice if the authors could comment on whether the data sets satisfy SST or STI, i.e., the assumptions needed for SCOMP and SCOMP2, and also report the number of batches used by C2B and SCOMP2.

NB: There is also a quite recent Python package for dueling bandits: https://duelpy.gitlab.io/duelpy/index.html

questions: Although the main ideas of the algorithm are described quite well, I would have liked to see a remark on the usage of two different confidence intervals in Section 3. I was wondering if this is technically not even one of the key design ideas which improve the theoretical results?

Moreover, the textual description in Section 3 could be connected to the high-level description in Section 1.1 by reusing the term “trapped” and “recourse”, as it does not appear in Section 3 anymore.

Finally, I am wondering why the theoretical analysis is not carried out for the KL-divergence-based confidence intervals if it (a) leads to the same theoretical results and (b) performs better empirically?

### Minor things:

- Typo in line 165: von Neumann.
- There is a typo in [35].
- In the math display of Proof of Lemma 3.1. it should be $\hat p_{i,j}(r)$
- The idea of the proof of Theorem 1.2 goes back to the proof of RUCB’s expected regret bound. I think the RUCB authors deserve some more credit.

limitations: ## Potential negative social impact
As this is a theoretical work, there is no seemingly potential negative social impact.

## Limitations
The authors clearly state that their algorithm is based on the Condorcet winner assumption and mention that it would be desirable to consider learning settings without such an assumption, e.g. Copeland winner or von Neumann winner settings.
review_title: null

Meta-review: metareview: This paper studies a batched dueling bandit problem under the Condorcet condition. The authors propose a sequential elimination-based algorithm and derive regret guarantees. Numerical experiments are reported at the end. The paper improves upon [1], where the problem has been introduced. The reviewers praised the paper but did not give strong support to it. I went over the paper myself. The results are of some interest, but indeed not utterly compelling/surprising. In general, one is left wondering what is the main technical difficulty in batching a stochastic dueling bandit algorithm over and beyond batching a standard (non-dueling) bandit one. 
Putting everything together, and considering the very high level of competition in this year's Neurips conference, I regret to say that this paper does not reach the acceptance threshold.
confidence: Certain
Decision: Accept