Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the classic dueling bandits problem in the sleeping bandits setting, i.e. where each round an adversarially selected subset of actions is available. As in dueling bandits, each round the learner is allowed to choose two of the available actions, and learns a noisy signal about which action is better. We also assume there is a consistent total ordering of the items. The learner would like to minimize their total regret over T rounds compared to an algorithm which knows this ordering in advance.

This paper proves the following results:
- They show an Omega(K^2 log T) (really Omega(log T * sum 1/gap_{i, j})) lower bound on the regret of any learning algorithm.
- They then give an algorithm (S1DB-UCB) that matches this lower bound. The idea, roughly, is to maintain a confidence interval for each pair of items representing the probability that one beats the other. Each round, the algorithm picks one random element from the set of “potential winners” (roughly, items which have a chance of being the best item), and then a second item being the one with the highest UCB probability of beating the first item.
- They give a slightly more computationally efficient algorithm (taking ~O(K) time per step instead of O(K^2) time per step) with a slightly worse regret bound.
- Finally, they run some empirical simulations comparing the two above algorithms on synthetic data.

main_review: 
I think this is a pretty nice paper. The problem is very natural (I’m surprised it hasn’t been studied in the bandit setting previously), and the paper provides a pretty comprehensive set of results. Nothing strikes me as incredibly technically novel, but definitely the details of the algorithms and their analysis are non-trivial. Overall the paper was well-written, although I would prefer a clear single description somewhere of both algorithms (BB-UCB and UB-UCB) and the regret bounds they achieve; I found that I had to piece these together across multiple paragraphs of exposition. 
Dueling Bandits with Adversarial Sleeping

This paper studies the classic dueling bandits problem in the sleeping bandits setting, i.e. where each round an adversarially selected subset of actions is available. As in dueling bandits, each round the learner is allowed to choose two of the available actions, and learns a noisy signal about which action is better. We also assume there is a consistent total ordering of the items. The learner would like to minimize their total regret over T rounds compared to an algorithm which knows this ordering in advance.

This paper proves the following results:
- They show an Omega(K^2 log T) (really Omega(log T * sum 1/gap_{i, j})) lower bound on the regret of any learning algorithm.
- They then give an algorithm (S1DB-UCB) that matches this lower bound. The idea, roughly, is to maintain a confidence interval for each pair of items representing the probability that one beats the other. Each round, the algorithm picks one random element from the set of “potential winners” (roughly, items which have a chance of being the best item), and then a second item being the one with the highest UCB probability of beating the first item.
- They give a slightly more computationally efficient algorithm (taking ~O(K) time per step instead of O(K^2) time per step) with a slightly worse regret bound.
- Finally, they run some empirical simulations comparing the two above algorithms on synthetic data.

The sleeping bandits setting is an interesting setting for dueling bandits. I think this paper does a thorough job of studying the dueling bandits problem in this setting (getting e.g. tight lower / upper bounds). The algorithms and their analysis are not incredibly novel, but they do appear non-trivial. In particular, I am not super familiar with the existing algorithms for dueling bandits, but some of the complexity of the analysis seems rooted in the sleeping model (as the authors point out). 

The writing is in general good, although I found it a little confusing to read in some places. I think overall the paper could benefit from a slightly more in-depth summary of the previous work on dueling bandits (see question below). 

Questions:

In remark 2, you mention that S1DB-UCB also improves the state of the art regret bound for regular UCB-based dueling algorithms (in particular, you say that S1DB-UCB is O(K log T / Delta) in the non-sleeping case, whereas existing state-of-the-art is O(K/Delta^2))? I’m not super familiar with the dueling bandits literature, but I imagine there is some catch here? E.g., does R-UCB also require a total ordering assumption like these algorithms? If there’s no catch, this seems like a significant result that you should emphasize more. In either case, I think it would be very useful for this paper to explain more thoroughly the prior work on dueling bandits, to understand how this work’s algorithms and model differ. 

Minor Comments:

Page 9: “though the later” -> “though the latter”
Page 6: “computatinally” -> “computationally”

limitations_and_societal_impact: I have no concerns here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). The paper provides a lower bound for this problem, and proposes two algorithms with near optimal regret guarantees. Experimental results are shown to demonstrate the effectiveness of the proposed algorithms.
main_review: Overall, I think that the considered problem of this paper is interesting, and the theoretical analysis seems solid. However, there are still some weaknesses. 
1.	The proposed S1DB-ED algorithm is too similar to RMED (Komiyama et al. 2015), so I think the novelty of this part is limited. The paper needs to give a sufficient discussion on the comparison with RMED.
2.	The comparison baselines in experiments are not sufficient. The paper only compares the proposed two algorithms, so readers cannot evaluate the empirical performance of the proposed algorithms. While I understand that this is a new problem and there are no other existing algorithms for this problem, the paper can still compare to some ablation variants of proposed algorithms to demonstrate the effectiveness of key algorithmic components, or reduce the setting to conventional dueling bandits and compare with existing dueling bandit algorithms.

**After Rebuttal**

I read the rebuttal of the authors. Now I agree that the analysis for the S1DB-ED algorithm is non-trivial and the authors correct the errors in prior work [21]. My concerns are well addressed. So I will keep my score.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a variant of the dueling bandit problem, where the availability of arms might differ for different time steps and consequently the learner might only choose pairs of arms from a subset of all existing arms. In other words, this variant is the preference-based counterpart of the sleeping bandit problem considered in the literature within the classical MAB problem with numerical rewards.
Under the assumption of a total order of arms and a possibly adversarial availability of the arms, the authors show a finite-time lower bound on the expected regret. Further, they suggest two algorithms for this learning scenario: one is based on the well-known RUCB for the classical dueling bandit problem, for which high-probability regret bounds are obtained. The other is a modification of the well-known RMED algorithm, for which a finite-time expected regret bound is shown. The main contribution of the paper is thus the transfer of the sleeping aspect to the dueling bandits and the theoretical analysis of the resulting problem.

main_review: # Significance/Novelty

This is the first work in the realm of dueling bandits considering the sleeping setting, which has gained much interest in the recent years in the classical multi-armed bandit problem. However, the transfer is rather straightforward, and the most interesting novelty of the paper is the modification of the RUCB algorithm by introducing the dominance sets as well as the different way of theoretical analysis for the modified RMED algorithm for this setting. 

# Strengths

The difficulty of the considered problem is analyzed by deriving a lower bound holding for any (consistent) learning algorithm for this problem.
As mentioned above, the most interesting novelty of the paper is the modification of the RUCB algorithm by introducing the dominance sets as well as the different way of theoretical analysis for the modified RMED algorithm for this setting. The theoretical analysis for the latter algorithm seems to be sound. 

# Weaknesses

It seems that the paper was written in a hurry, as there are many weird sentences due to typos, missing words, wrong grammar or suchlike. Additionally, there are also some minor niceties regarding the theoretical results (please see ‘’Minor things’’ below). 
However, and this is currently (unfortunately) the reason for me to tend towards rejecting the paper, the high probability regret bound for SlDB-UCB stated in the supplementary material (differs from the statement in the main part) seems to be wrong, as the bound is independent of the time horizon T. Although Remark 6 tries to justify that this is not necessarily a contradiction to the lower bound result, I think that using techniques to translate high-probability bounds to bounds in expectation (see for instance the proof of Theorem 3.4 in [1] or the proof of Theorem 5 in [2]) will yield a bound in expectation  for SlDB-UCB which is independent of T as well, which, however, is then a contradiction. I hope that the authors can comment on this issue and correct me if I am wrong. I suspect that Lemma 6 has a flaw and a \log(T) should occur when bounding n_{i,j}.
Another (minor) weakness is that the authors do not consider in their experiments straightforward modifications (by restricting the corresponding choice mechanism with respect to the available set of arms) of other dueling bandits algorithms such as DTS [3]. This would have made the experimental study a little more exciting.

[1] Bubeck & Cesa-Bianchi (2012), “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems”

[2] Zoghi et al., (2014), “Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem”

[3] Wu & Liu, (2016), “Double Thompson Sampling for Dueling Bandits”


# Suggestions to improve readability

1. Even if I am wrong regarding my concern of the regret bound for SlDB-UCB, the authors should state a bound in expectation for sake of completeness as well. 
2. The lower bound in Lemma 2 is strictly speaking not true, as there should be some constant on the right-hand side of the inequality. By the way, the regret of a an algorithm $\mathcal A$, that is, $R_T(\mathcal{A})$ is not rigorously introduced. 
3. Furthermore, I didn’t understand the statement in lines 269-271, as I don’t see how the O(T^{2/3}) worst-case regret for other dueling bandits algorithms follows (from your reasoning). Perhaps you could address this in the response (and also be a bit more detailed in the paper).
4. You could be more precise regarding the additive terms in the regret bounds. For instance, the O(1) term in line 233 is O(K C(K,\delta)).
5. Finally, in section 2 you use jargon that is clear to any reader who is familiar with Dueling Bandits or preference-based learning, but not necessarily to those who are not. To be more precise, the terms “preference matrix” (lines 121-122) and “beats” (line 141) are not explained and also what it means for two arms that the preference probability is larger than 1/2 (line 124). 


**Other minor things:**

line 112: indicator random(?) variable

Proof (sketch) of Theorem 1: It is a bit strange to speak of ‘’subintervals’’

Wouldn’t it be more reasonable to call SlDB-UCB rather SlDB-RUCB, as it is based on RUCB?

I think lines 12 and 13 in Algorithm 1 needs to be switched regarding the typo mentioned in lines 669-670. Also the in line 16 it should be n_{i,j}(t+1).

Statement of Theorem 3 (line 206): \alpha > 1/2 is also possible I think?

lines 223: holds good? 

Statement of Theorem 8 (line 254):  Why is T tending against infinity?

Finally, it is worth mentioning once again that there are a lot of typos in the paper (not listed above), so that the paper needs a proper proofreading.

# Post Rebuttal

The authors have convinced me that the main result for SLDB-UCB is indeed correct and does not contradict the lower bound. The misunderstanding was caused by a somewhat unclear formulation of the result, which should be discussed in more detail to avoid such misunderstandings. However, the experiments are still a bit limited as explained above (e.g., it is straightforward to modify the mechanism of DTS to the sleeping setting considered) and the paper still has some minor flaws such as typos and unclear passages, but I think they can be improved quite quickly.


limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers are unanimous that this is an interesting problem. While there were some initial concerns about the analysis and relation to other algorithms, this has been cleared up in the response and discussion. Please take the reviewers minor comments into consideration when preparing the final revision. Note also the confusions of the reviewers on certain issues explained in the response will likely also be confusing to other readers, so the final revision should take special care to clarify these potential pitfalls.

Decision: Accept (Poster)