Dueling Bandits with Adversarial Sleeping
Authors: Aadirupa Saha
Pierre Gaillard
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online
bandit
dueling
preference
stochastic
adversarial
sleeping
optimal
regret
lower bound

Abstract: We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applications, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Surprisingly, this `sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal is to compete with the best arm by sequentially querying the preference feedback of item pairs. The non-triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find an optimal `no-regret policy that can identify the best available item at each round, as opposed to the standard `fixed best-arm regret objective' of dueling bandits. We first derive an instance-specific lower bound for DB-SPAA $\Omega( \sum_{i =1}^{K-1}\sum_{j=i+1}^K \frac{\log T}{\Delta(i,j)})$, where $K$ is the number of items and $\Delta(i,j)$ is the gap between items $i$ and $j$. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB).  We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.

Dueling Bandits with Adversarial Sleeping
Aadirupa Saha"
Pierre Gaillard
Abstract
We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities (DB-SPAA). In almost all dueling bandit applica- tions, the decision space often changes over time; eg, retail store management, online shopping, restaurant recommendation, search engine optimization, etc. Sur- prisingly, this "sleeping aspect' of dueling bandits has never been studied in the literature. Like dueling bandits, the goal to compete with the best arm by sequen- tially querying the preference feedback of item pairs. The non non-triviaal triviality however results due to the non-stationary item spaces that allow any arbitrary subsets items to go unavailable every round. The goal is to find optimal 'no-regret' policy that can identify the best available item at each round, as opposed to the standard 'fixed best-arm regret objective' of dueling bandits. We first derive instance-specine K
lower bound for DB-SPAA O(E ΣK Ej=(+1 (..i)) ). where is the number of
log
items and A (i is the gap between items and j. This indicates that the sleeping problem with preference feedback is inherently more difficult than that for classical multi-armed bandits (MAB). We then propose two algorithms, with near optimal regret guarantees. Our results are corroborated empirically.
Introduction
The problem of Dueling-Bandits has gained much attention in the machine learning community 34
38 36), which is an online learning framework that generalizes the standard multiarmed bandit
(MAB) 6 setting for identifying a set of 'good" arms from a fixed decision-space (set of arms/items) by querying preference feedback of actively chosen item-pairs. More formally, in dueling bandits, the learning proceeds in rounds: At each round, the learner selects a pair of arms and observes stochastic preference feedback of the winner of the comparison (duel) between the selected arms; the objective of the learner is to minimize the regret with respect to a (or set of) 'best' arm(s) in hindsight. Towards this several algorithms have been proposed [2, 37 14 Due to the inherent tradeoff of the learning framework and several advantages of preference feedback [5] many real-world applications can be modeled as dueling bandits, including movie recommendations, retail management, search engine optimization, job scheduling, etc.
exploration-vs-exploiiee
However, in reality, the decision spaces might often change over time due to the non-availability of some items, which are considered to be 'sleeping'. This 'sleeping-aspect' of online decision making problems has been widely studied in the standard multiarmed bandit (MAB) literature 19 18 [I]]. There the goal is to learn a 'no-regret policy that maps to the 'best awake item' of any available (non-slceping) subset of items, and the learner's performance is measured with respect to the optimal policy in hindsight. This setting is famously known Sleeping Bandits in MAB [1 24 [5| ITI. More discussions are given in Related Works.
[1 24
[5
Surprisingly, however, the 'sleeping problem' is completely unaddressed in the preference bandits literature, even for the special case of pairwise preference feedback, which famously studied
Microsoft Research, New York, US; aasa@mi crosoft. com. Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France.
pierre. gaillardeinria.ft
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Parameters. Item set: [K] (known), Preference: P (un-
known), Available item sets: Sy (observed sequentially)
For = 1.2..... ........TT,, T. the learner:
Observes S: S [K] the set of available items
Chooses (Z,, yt St
Observes 0g == 1 (2x > y1) Ber (P 363)
Incurs r; == 1/2(P((t [z)) + P ( y1 -1);
where 87 is such that minjes, P ((...) 2 1/2
Figure I: Setting of DB-SPAA(P, ST)
as Dueling Bandits [37 34]. even though the setup of changing decision spaces quite relevant in almost every practical applications: Be that in retail stores where some items might go out of production over time, for search engine optimization some websites could be down certain days, in recommender systems some restaurants might be closed or movies could be outdated, in clinical trials certain drugs could be out of stock, and many more. This work is the first to consider the problem of Sleeping Dueling Bandits, where we formulated the stochastic K Kaareed dueling bandit problem with adversarial item availabilities. Here each round t {1, 2,,,,.... .......TT T3 the item preferences are considered to be generated from a fixed underlying (and of course unknown) preference matrix E [0. 1] x however, the set of available actions S, S {1.2.... ... _K is assumed to be adversarially chosen by the environment. We call the problem as Sleeping- Sheeping-Dueling Dueling Bandit with Stochastic Preferences and Adversarial Availabilities or in brief DB-SPAA(P Sr), where ST {Si, .2.... } denotes the sequence of available subsets over T rounds. We also assume the preference P follows a 'total-ordering assumption to ensure the existence of best-item per available subset S,. We describe the setting in Fig. | with formal description in Sec.
Our specific contributions are as follows:
1. We first analyze the fundamental performance limit for the DB DB-SPAA(P, Sy) problem in Sec. Thm. gives an ussaace-speciffe regret lower bound of
(EE
K-1 Σ A(..))
log
with A(i,j) being the 'preference gap' of item i-vs-j (see Eqn. (2). Our lower bound, which can be of order {)K² l/gT/A), == mink,j A(i,j) being the worst case gap, indicates that the problem of sleeping dueling bandits inherently more difficult that standard sleeping bandits (MAB), unlike the "non-sleeping' case where both dueling bandits (with "total-ordering' assumption on P) and MAB are known to have the same fundamental performance limit of 52 K log T/A) (Rem. 1
2. We next design a 'fixed confidence regret' algorithm S1DB -CB (Alg. D.. inspired from the pairwise upper confidence bound (UCB) based algorithm (37). However due the fixed confidence and -ereepial-scceping' nature of the problem, we need to differently maintain pairwise confidence bounds per item (based on the availability sequence {S.)), which makes the resulting algorithm and its subsequent analysis significantly different than standard UCB based dueling bandit algorithms:
Precisely given any > 0, S1DB-UCK achieves a regret of O
with probability at least K3 log(1/5)
A
1 over any problem instance of DB-SPAA(P. ST) (Sec. 4h.
3. In Sec.5, we design another computationally efficient algorithm, SIDB-ED (Alg. 2). for 'expected regret' guarantee. Unlike the previous algorithm (SIDB-UCB), S1DB-ED uses empirical divergence (ED) based measures to filter out the 'good' set of arms, inspired from the idea of RMED algorithm of (2 for standard dueling bandits; however, due sleeping nature of the items, it requires a different maintenance of 'good' arms and the regret analysis of the algorithm requires derivation of new results (as described in Sec. (5). The algorithm is shown to perform near optimally with an expected non-asymptotic regret upper-bound of (Thm. 6). Note that for any problem instance with constant suboptimality gaps (ii,j) = A for all < j. regret bound of SIDB-ED tight and matches the lower-bound ensuring the near optimality of SIDB-ED in the worst case. Furthermore, novelty of our finite time regret analysis lies showing cleaner tradeoff between regret vs. availability sequence ST which automatically adapts to the inherent 'hardness' of the sequence of available

---

subsets Sy. compared to existing sleeping bandits work for adversarial availabilities in the MAB which only gives worst-case regret bound over all possible availability sequences
setting [9 (Rem.
4. Finally we corroborate our theoretical results with extensive empirical evaluations. (Sec. 6
Related Works. The problem of regret minimization for stochastic multiarmed bandits (MAB) is extremely well studied in the online learning literature 6 [ 22 5 16], where the learner gets a noisy draw of absolute reward feedback of an arm upon playing a single arm per round.
much studied in the online learning community, where at any round the set of available actions could vary stochastically based on some unknown distributions over the decision space of K items 24 or adversarially [15] 19 [8]. Besides the reward model, the set of available actions could also vary stochastically or adversarially [17 24). The problem is NP-hard when both rewards and availabilities
well motivated generalization of MAB framework is Sleeping Bandits 24 18
are adversarial [9 18 [5]. In case of stochastic reward and adversarial availabilities [19] proposed
an UCB based no-regret algorithm, which was also shown to be provably optimal. The case of adversarial reward and stochastic availabilities has also been studied where the achievable regret lower bound known be S2( (2(VK' ( by the inefficient EXP4 algorithm 19 15
On the other hand over the last decade, the relative feedback variants of stochastic MAB problem has seen a widespread resurgence in the form of the Dueling Bandit problem, where, instead of getting noisy feedback of the reward of the chosen arm, the learner only gets to see noisy feedback on the pairwise preference of two arms selected by the learner. The objective of the learner is to minimize the regret with respect to 'best arm in the stochastic model. Several algorithms have been proposed to address this dueling bandits problem, for different notions of 'best arms' or preference models 33 13,, even extending the pairwise preference to subsetwise preferences However, surprisingly, unlike the 'sleeping bandits generalization' of MAB, no parallel has been drawn for dueling bandits, which remains main focus.
10
31
38
37 36.27
29
26
27 25
2 Problem Formulation
The available of items round / is denoted by S. C [ For any matrix M E RRXK we define maj == Mi,j), Vi, E [K]. We write S S {i). for any S [K] and S. 1(.) denotes the indicator random variable which takes value 1 if the predicate is true and 0 otherwise and S rough inequality which holds up to univer- sal constants. For any two items x, y E [K], we use the symbol x > y to denote æ is preferred over y. E k denotes the set of all permutations of the items in set [K]. The KL--ivergence of two Bernoullis with biases p and 9 respectively is written kl(p, q) = plog(1)) (P/s) + (1 p) log(() (1-p)/(1-0) +)). We assume 0 := 0.5 (in Alg. and 2
Notations. Decision space (or item/arm set) [K] = (1,2.... ..,,, K).
Setup. We consider the problem of stochastic K-armed dueling bandits with adversarial availabil- ities: At every iteration / - 1,..,, T, a set of available items (actions) S. C [K] is revealed, and the learner is asked to choose two items We, yt E S.. Then, the learner receives a preference feed- back o = 1(x; > y1.) ~ Ber(PP(xt, }t),, where P E [0, j is an underlying pairwise preference matrix, unknown to the learner. The setting is described in Figure [ We assume that P respects a "toaal ordering', say o² E Σg. Without loss of generality, we set o
... K)) thoughout the paper. This implies Pii.j) Z 0.5 for i S j. One possible pairwise probability model which respects "total ordering' is Plackett-Luce 77] where it is assumed that the K items are associated to positive score parameters f...... 8K. and P(..j)
0,/(B, + 0,) for all i.j E [K]. In fact any well random utility (RUM) based preference model would have the above property, like 77, 28). Note also that our assumption corresponds to assuming the existence of a Condorcet winner for every subset S, S [K].
Objective. The objective of the learner is to minimize his regret over T rounds with respect to the best policy in the policy class = (T 2 - [K] VL E [T], T (S.) E S.). i.e. any æ E such that for any t e [T]. TT (S()) E S.. More formally we define the regret follows:
3

---

P ((T((S)) 22) + ((T((S)))))) wr) -1
RT
max R
2
We analyze both fixed-confidence and expected regret guarantees in this paper respectively in Sec.
(see Thm. 3 and Sec. [5| (see Thm. ( It easy to note that under our preference modelling assumptions, the best policy, say n,, turns out to be (S) henceforth denote by 7 = (S,). We define the above problem to be Sleeping- Dueling Bandit with Stochastic Preferences and Adversarial Availabilities over the stochastic preference matrix P E
min[S} for any S S [K]. We
[0, 1] X and the sequence of available subsets ST = [SI...... Sr or in short DB-SPA Sr).
For ease of notation we respectively define the gaps and the non-zeros gaps as A (i. == ((i 11/2
and
Aii = { (i,
if it,
(2)
+00 if A (i,5) 0
The regret thus can be rewritten Ry=:= rt. where ri (A))) (it, v2) denotes the instantaneous regret. We also denote by (t)(()) := - 1 1( yt = (i,]}) the number of times the pair (i,j) is played until time and by myy() the number of times beats j in rounds.
3 Lower Bound
We first derive a worst case regret lower bound over all possible sequences of Sy. The proof idea essentially lies in constructing hard enough availability sequences Sr, where no learner can escape learning the preferences of every distinct pair of items (i,j). This leads to a potential lower bound of 2( R2 log(T)/A), For this section we denote P by Px to make the dependency on K more precise.
Theorem 1 (Lower Bound for OB-SPAA(P K, ST)). For any No-regret learning algorithm A, there exists a problem instance DB DB-SPAA K ST) with T > K3, such that its expected regret lower- bounded as:
K-1
K
log T
)
B[R 2 Ω
Σ
Σ
A(i
The No-regret learning algorithm refers to the class of 'consistent algorithms' which do not pull any
suboptimal pair more than O a E [0. 1] (see Def. 7 Appendix 8 3)
Proof (sketch) The main argument lies behind the fact that in the worst case the adversary can force the algorithm to learn the preference of every distinet pair (i, as for the 'worst-case' sequences Sr, a knowledge of the already 'learnt' pairwise preferences would not disclose any information on the remaining pairs; e.g. assuming o² = (1, 2..., K), revealing the available subsets in the following sequence (1, 2), (1,3)...(11, (2, (2, 4), (K- K) would force the learner to explore (learn the preferences) all (*) distinct pairs. The remaining proof establishes this formally, towards which we first show (TI( (1,, 2)) regret lower bound for DB-SPAA instance with just two items (i.e. K- = 2) as shown in Lem. 2 The lower bound for any general K can now be derived applying the above bound on independent (*) subintervals, with the availability sequence (1, 2), (1, 3), ... (1, K), (2, 3), (2, .)... (K- 1, K). The full proof is given in Appendix 8
Lemma (Lower Bound of DB-SPAA K. ST) for 2 items), For any No-regret learning algorithm A. there exists problem instance DB SPAA(P ST) such that the expected regret incurred by A on that can be lower bounded as: E (A)) Z - log(T), A being the 'preference-gay between the two items (i.e. A = P12 1/2, assuming P12 > 1/2 or equivalently A >> 0).
Remark (Implication of the lower bound). The above result indicates that in the preference based learning setup, the fundamental problem complexity lies in distinguishing every pair of items 1 S i < j < K. If the learner fails to learn the preference of any pair (i,j), the adversary can make the learner suffer O(T) regret by setting S, = {i,}} henceforth at all round. It is worth noting that in the 'no sleeping' case both dueling bandits and MAB are known to have the same fundamental performance limit of Ω(K log(T)) A) (assuming P respects condorcet winner 66] (T).. Thus Thm. | shows that the 'sleeping-asper of dueling bandits makes the problem K K-times harder than 'sleeping- MAB' for which the regret lower bound is known to be only Q <X
i= log(T)/A(1) + +1) 19)

---

Algorithm S1DB--UCB
input: Arm set: [K] parameters a >> 0.5, Confidence parameter å [0, 1)
2: init: (1) 6- 0, Vi, E [K]
3: define: [1:(() :- W1y (1) (l), Vt e
4: for = 1.2..... do
5: Receive S; [K]
(1)(1) wiy (t)
(t) Cig (1) 6 a at((t)
6:
Vi,j E St, (assume niz(t)
= 0.5, Vx E R)
7:
(1)(1) (1) + (1), ma(()) -- 1/2, Vi,j S.
D UCB of empirical preferences
8:
E S, do
9:
(t(t) (j St (t) 3/2}
> Potential losers to
10:
end for
11:
c== {i E S [C)( maxjes. (t)]}
Potential best items
12:
Select a random ze from C. Choose y/2 f- arg maxsec, Vax, (t)
13:
Play (I4, ye). Receive preference O:
14:
Update: Vi.j E [K]. Unan (1 + 1)= +- Wasme (1) + Or, Wyere (L + 1) t Wyzze() + (1 or),
Oij( + < mnx(1 1), (), 0)} Vi, E [K]
15: end for
4 S1DB-UCB: A Fixed-Confidence Algorithm
In this section, design an efficient algorithm for the DB-SPAA(K, T)) problem with instance- dependent regret guarantee.
Main ideas. Our algorithm, described in Alg. depends confidence parameter 8 > 0. maintains, for each item & E [K]. its own record of empirical pairwise estimates of the duels, (i,j) [K] x [K] and their respective upper confidence bounds defined
hyper-parameter 0.5 and
Pry == (t) (f)(()
and
u.y(t) = (t) - ct)(t,, with Ciy(t) =
log (t)
(ly(()
where Wiy(t denotes the total number of times item i beats j up to round t, n2y (t) = why (t) + (t) and for all i [K] and t [7]
ai (ty(t) (t) == max (CK,, 8), (t) and 8) = [44-1)) 20-1 (2a- (2a-1)8
key observation is that our careful choice of the confidence bounds Cigy (t)(t) ensures that with high probability (t) E (Pa(() Cty(t), Pij + ct)(t) for any duel i,j [K] and any t [T] (Lem. 4). Now at any round 2 1, the algorithm first computes a set of potential winners of S as == f S, [C,(t)] maxjes. (t)) where (t) {j E Se uxj(t) 11 denotes the set of items that item & dominates (optimistically). At each round, we play a random item from the set potential winners C, the left arm xt. Finally the right-arm y/ is chosen be the most competitive opponent of xr as <- arg maxiec, uta(() from the potential winners. Our arm selection strategy ensures that eventually for all t, algorithm plays the optimal pair (if it) frequently enough as desired.
Theorem FFixed-confidenc regret analysis: S1DB- UCB), Given any 8 > and 1/2, with probability at least 8, the regret incurred by SLDB -UDB-UCB (Alg. 7 is upper-boundes as:
K-1 K
RT 2
Σ
Σ
My log (C(K,8)M,
1=1 1=
where
C(K,6) = ( (4a 1)K2 (2a 1)8
- w011
and Mij
Σ
4a
km min {A(k, Akk
The complete proof with precise dependencies on the model parameters deferred to Appendix
Remark 2. The dependency A min,,; A (i.j) does not match the lower-bound of Thm. 7
which is of order O(log(T)/A) A). Instead, Thm. 3 proves O{lo((1/8)/A3 Yet, the bounds are
5

---

not directly comparable because the lower- is on the expected regret while the upper-bound considers confideneee ó and hence independent of All existing dueling bandit algorithms, that minimize the expected regret, suffer an additional constant term of order O(1/²²) -see for instance (7 21). Achieving an order (() dependendence is an interesting question for future work.
Proof sketch Thm. The key steps lie in proving the following four lemmas. The first lemma follows along the line of Lem. 1 of RUCB algorithm [37]and and shows that all the pairwise estimates are contained within their respective confidence intervals with high probability.
Lemma 4. Let > 0.5 and 8 >> 0. Then, for any i, E [K] with probubility at least 1 8/K2,
Pty(t)
Gzs (t) S Pij I (ty(t) := P.y cty(t)
Vt E
The lemma below shows that once the algorithm can not play any suboptimal pair "too many times'.
Lemma 5. Let > 0.5. Under the notations and the i, i,ikk [K] such that {i.j} + (kik), k), and for any high-probability event of Lem. 4 for all
4a log (t.5(T)
Σ 10 ()) v1 = ((i,i)) <
min () 11::11
where recall (T) max (C(K, (), (T)(
With probability of at least - ó the event of Lem. hoold and thus so do the ones of Lem. 5 The regret of Alg. [ then follows from applying the above lemmas with the following careful decomposition of the regret:
K-1 K
1
RT S
Σ 1=
Σ
Σ
(() (i,1))
Σ
Σ (Ty(T)
j=++1
and the proof is concluded by using Lemma 5 to upper-bound niy (T) The complete proof given in Appendix 9
5 SIDB-ED: An Expected Regret Algorithm
In this section, we propose another computationally efficient algorithm, S1DB-ED (Alg. 2 which achieves near-optimal expected-regret for DB-SPAA problem, and also performs competitively against SIDB-UCB empirically (see Sec. (6). Furthermore, a novelty of our finite time regret analysis of SIDB-ED lies in showing cleaner trade-off between regret availability sequence Sy which automatically adapts to the inherent 'hardness' of the sequence of available subsets Sy, unlike the
previous attempts made in standard sleeping bandits for adversarial availabilities [99 (Rem. 3)
Main ideas. We again use the notations (t), (t) as used for CIDB-UCB (Alg. 1. with the same initializations. Same as S1DB-UCB this algorithm also maintains the empirical pairwise preferences Piy(1 for each item pair i E [K]. However, unlike the earlier case here we need to ensure an initial to rounds of exploration (to 1 in the theorem) for every distinct pairs (i,j), and instead of maintaining pairwise UCBs, in this case the set of "good-items' is defined in terms of empirical divergences for all i E St
Ittt) = Σ (1
8.(0) :00=-( {i E [K] A (011((() s 1/2] ns.
JEB.(()
denotes the empirical winners of item in set S. Now intuitively since (I(()) can interpreted as the likelihood of being the best-item of S,, we denote by 7 f- arg min.es. (t) the empirical- best item of round and define the set of "near- items C, = f S. (1) Zz. whose likelihood is close enough to that of i Finally the algorithm selects an arm pair (It, y+) such
(1) S a log 1),
that s, is potential candidate of good arm (which ensures the required exploration) and y being the strongest challenger of 2; w.r.t the empirical preferences. The algorithm is given in Alg. 2

---

Algorithm 2 S1DB-ED
input: Arm set: [K] exploration parameter to 0, parameter a >> 0
2: for t-= = 1, ..,,... TI' do
3:
(t)(t) == (6;(1)
(t) p(i, i) < 1/2, Vi,j E [K] (assume = 0.5, Vx R)
4:
Receive S C [K]
5:
if [S 2 2 and j E St s.t. (iy(t) to: i # then
6:
Set z2 - i, Yt +
b Exploration rounds
7:
else
8:
(t) = Ej [K] \ (i) Pby(1) x 1//3 ns, Vi [K] > Empirical winners over i
9:
[,(1= = -EEE,(() mey (1) (1(s)(()))))))) (22, vi E [K] and ig +- arg miness, Iz(()
C 1--(iE EiE II,(t) Tr, (t) S logt]
b Potential good arms
11:
Select any xe from C, uniformly at random
12:
2 E Be, (t) or B,, (t) = 0) set yt + 87. else: yr + arg maxies Pix, (t)
end if
14:
Play (Ir, Receive preference feedback or
15:
end for
Theorem 6 (Expected regret analysis S1)B-ED). te = and a = 4K. Then as T + oc, the
expected regret incurred by SLDB-ED (Alg. 2
can be upper bounded as: For all ; EK 2
K (A(,))))))))))
K
K log T
E RT
S
Σ
nay (T) min[sy. (mi.()),((..))))
A(i,j)
max (e,, - }
ISKOSK
0
min Σ
K
K KlogT
kT218))
A(j 1,5)+
The proof is deferred to Appendix 10 Although it borrows some high-level ideas from [19 for sleeping bandits and from (21] for RMED in standard dueling bandits, our analysis needed new ingredients in order to obtain O OKK2 (1og A). This is especially the case for the proofs of the technical Lemmas & and which significantly differ from "corresponding" technical lemmas of (21). Specifically, both regret bounds of RMED and ours need to control the length of an initial exploration to after which pairwise preferences are well estimated by Pig (4). This is done respectively by our Lemma
& and Lemma 5 of [21]. Yet, RMED's original analysis is based on a union bound over all possible subsets S C [1,.... K} of items (see Equation (19) in (2I).. whose number is exponential in K. Despite our efforts, we could not follow the proof of Lemma of (2I) which the best of our understanding, should yield to an exploration tu exponentially large in K contrary to O(1) claimed in (2I) Instead, in our proof of Lem. we carefully apply concentration inequalities to run union bounds over the items directly instead of sets of items.
The upper-bound of Thm. is close optimal. It suffers most suboptimal factor K and exactly matches the lower-bound for some problems. The distribution-fiee upper-bound of order ((32/3) matches obtainable standard dueling bandit problems 21(37], since the latter algorithms also suffer constant terms of order A -2 Yet, it is unclear whether it is optimal if O can be obtained.
Remark (Sequence ST adaptivity of Alg. D. It is worth pointing out that the regret bound of Thm. is finite time and automatically adapts the sequence of available sets Sy. In the worst-case, the complexity lies in identifying for all items the gap with the earlier item j - 1. Yet, our regret- bound, which holds for any Ej 2 O, will automatically perform trade-off for each j between the gap A and Ej > 1-1 Tay (T) the number of times is played together with better item i < j. In particular, Σ (T) can be small if is rarely available in S, while not optimal. Notably, this adaptivity to ST item per item improves the regret guarantee of Thm. (10), 19), which also addresses the problem of sleeping bandits with 'adversarial availabilities' but for the stochastic multi-armed bandit setup and only provides worst-case guarantees over all Sy and a trade-off E independent of j.
Remark (SIDB-ED ED standard dueling bandits). Even the dueling bandit setting (without the sleeping component), SIDB-ED and Thm. haave advantages compared to the RMED algorithm and analysis of (21). Our regret bound valid for all number of items K, while the one of Thm. 3 of 21 is only asymptotic when K cc. This is due to the fact that the algorithm of [2 depends
7

---

on a syper-parameter f(K) which needs to larger than AK, where A is constant in K and T but which depends on the unknown sub-optimality gaps (i..j). Thus, [2T chooses f(K) = K + so that eventually the bound is satisfied when K - x. Instead, our algorithm only depends easily tunable hyper-parameters ln and a, whose optimal values are independent of unknown parameters.
6 Experiments
In this section, we compare the empirical performances of our two proposed algorithms (Alg. and Note that there are no other existing algorithms for our problem (see Sec. D..
Constructing Preference Matrices (P). We use the following three different utility based Plackett- Luce(0) preference models (see Sec. 2 that ensures fotal-ordering. We now construct three types of problem instances 1. Easy 2. Medium 3. Hard. for any given K, such that items with their respective
parameters are assigned as follows:
Easy: 0 [K/2]] = 0( @ [[LK/2] +
K) 0.5. 2.
Medium: 0(1 [K/3] ) = 1, ((LK/ /3 + [2K/3]] = 0.7, 0 /3] +1: K) = 0.4. 3. Hard:
(()) (i 1)/ K, Vi E [K] Note for each = (1 2> ... KK).
In every experiment, we set the learning parameters a = 0.51, = 1/T for S1DB-UCB (Alg. 1 and as per Thm. for SIDB-ED (Alg. 2 All results are averaged over 50 runs.
Regret over Varying Preference Matrices. We first plot the cumulative regret of our two algorithms (Alg. and over time on the above three Plackett-Luce datasets for K 10. We generate availability sequence ST randomly by sampling every item i [K] independently with probability 0.5. Fig 2 shows that, their names suggest too, instance-Easy is easiest to learn as the best-vs-worst item preferences are well separated and the diversity of the item preferences across different groups are least. Consequently the algorithms yield slightly more regret preference diversity, and the hardest instance being Hard where the learner really needs to differentiate the ranking of every item for any arbitrary set sequences Sy. Empirically SIDB-UCB is seen to slightly outperform S1DB-EI though orderwise they perform competitively.
instance-Medin
due to higher
Regret over Varying Set Availabilities. In these set of experiments, the idea is to understand how the regret improves over completely random subset availabilities as now the learner may not have to distinguish all item preferences as some of the item combinations occurs rarely. We choose K = 10 and to enforce item dependencies we generate each set S; by drawing random sample from (aussian Σ) such that 14, = O, Vi [10), and Σ is fixed 10 x 10 positive definite matrix which controls the set dependencies: Precisely we use two different block diagonal matrices for Cw-CCorrelatinn and Ffih-CCoreeation with the following correlations: 1. now-Correlation: Σ is a separated block diagonal matrix on item partitions 2,3,. {4, 5, 6). {7, 8, 9, 10). 2. High- Correlation: Σ is constructed by merging three all-1 matrices on partitions (1 (1...5) 5]. f2, .2....8), and {6.... 10), however as the resulting matrix is positive semi-definine so we further take its SVD and reconstruct the matrix back eliminating the negative eigenvalues. At every round vector from Gaussian(4 μr, Σ), and S, is considered to be the set of items whose value exceeds 0.5. Both experiments are run
sample random
instance-Hout Hard. Fig. 3 shows, as expected, on Low- cow-Corellation both algorithms converge to o² relatively faster and at lower regret compared to tigh-Correlltion (as the latter induces higher variability of the available subsets).
Mediu
Fhazz
SUGR UTS
SipE LKB
400
S108: ED
202
102
200
0.5
X10
Figure 2: Regret (R,) vs time (f) over three preference instances (P)
8

---

Ned
SIELED
420
85
Figure 3: Regret (Rt) vs time (1) over availability
Figure 4: Final regret (Rr) T 10 with varying sizes (K)
sequences ST
Final Regret vs Setsize(K). We also compared the (averaged) final regret of the two algorithms over varying item sizes K. We additionally constructed two larger Plackett-Luce (0) Easy and Hard instances for K = 20 and 40, using similar 0 assignments explained before. We set T 10 000 and use itemwise independent set generation idea, as described for Fig. 2 As expected, Fig. 4 shows the regret of both algorithms scales up with increasing K with effect on S1DB-ED ED being slightly worse than S1DB- UCB, though the latter generally exhibits higher variance.
Worst Case Regret vs Time. We run an experiment to analyse the regret of our two algorithms on the worst case problem instances. Towards this
preference matrices Pa of the form: (i 0.5 + A. A1 I < I K, i.e all items are spaced with equidistant gap A E (0, 0.5]. As before, choose T = 20, 000 and K 10, and run the algorithms above problem instances varying in the range [10/T,... 0.5] with uniform grid-size of 0.005 (i.e. total 100 values of A, each corresponds end we plot the worst case regret of both the algorithms over time, by plotting max R2 (PA) vs three availability sequences: 1. Independent (as used in Fig. 2 2.
separate problem instance Pa with different 'gap-complexity") At the
We run the experiments Nww-Coreeattion and High-Correlation (as used Fig. 33. As a consequence the resulting plots reflect the worst case (w.r.t. A) performances of the algorithms, which seem be scaling as 2
for S1DB- LD, conjectured be its distribution free upper bound (see discussion after Thm. 6). and with a slightly lower rate for 91DB-UCB Fig. shows the comparative performances.
Worst-Caree-Rereee (Independent)
Worst-Case-He Renrse--egrette (Low-Corr)
Worst-Case-Regie (Migh-Carr)
SIDB-UCB SIDB-ED
SIDB-ED
SIDB-UCB SIDB-ED
600
400
400
200
200
0.5
0.5
1.5
Figure 5: "Worst Case Regret" (maxa (e(Ps)) vs time (t) over three availability sequences Sy
Conclusion and Perspective
We introduce the problem of sleeping dueling bandits with stochastic preferences and adversarial availabilities, which, despite of great practical relevance, was left unaddressed till date. Towards this we adapt two dueling bandit algorithms for the problem and give regret analysis for both. We also derive an instance dependent regret lower bound for our problem setup which shows that our second algorithm is asymptotically near-optimal (up to the problem dependent constants). Finally, we compare both our algorithms empirically where usually the first algorithm is shown to outperform the second, although having a relatively weaker regret.
Future Works. Moving forward, one can address many open questions along this direction, including relaxing the total-ordering assumption on the stochastic preferences assuming more general ranking objective based on borda [32] copeland scores (36), or extending the framework to a general contextual scenario with subsetwise feedback. Another direction worth understanding is to analyze connection of this problem with other bandit setups, e.g., learning with feedback graphs R 4 or other side information for adversarial preference and stochastic availabilities 24 and also analyzing these class of
23 20 It would also be interesting to consider the dueling bandit problem
problems for general subsetwise preferences 225 30 g

---

References
[1] Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the aulli--rmmed bandit problem. In Conference Learning Theory, pages 19-1,2012
[2 Nir Ailon, Zohar Shay Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In ICML, volume 32, pages 856-864, 2014.
[3] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feed- back graphs: Beyond bandits. In JMLR Workshop and Conference Proceedings, volume 40. Microtome Publishing, 2015.
[4] Noga Alon, Nicolo Cesa-Bianchi Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, (1066):785--82222 2017.
[5] Jean-Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on Learning Theory-2010, pages 13-p. 2010.
[6] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, (7(2-3))235-2566 2002.
[7] Hossein Azari, David Parkes, and Lirong Xia. Random utility theory for social choice. In Advances Neural Information Processing Systems, pages 126-134, 134, 2012.
[8] Brian Brost, Yevgeny Seldin, Ingemar J. Cox, and Christina Lioma. Multi-dueling bandits and their application online ranker evaluation. CoRR, 0eep//608.065555 2016.
[9] Róbert Fusa-Fekete and Eyke Hüllermeier. A survey of preference-based online learning with bandit algorithms. In International Conference on Algorithmic Learning Theory, pages 18-39. Springer, 2014.
[10] Róbert Busa-Fekete, Eyke Hüllermeier, and Balázs Szörényi. Treference-basee rank elicitation using statistical models: The case of mallows. In Proceedings of The 31st International Conference on Machine Learning, volume 32, 2014.
[11] Corinna Cortes, Giulia Desalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with sleeping experts and feedback graphs. In International Conference on Machine Learning, pages 1370-1378, 2019.
[12] Imre Csiszár. The method of types. IEEE Trunsactions on Information Theory, 446))2550--5223, 1998.
[13] Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, pages 563-587, 2015.
[14] Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In Proceedings of the 32nd International Conference on Machine Learning, pages 218-227, 2015.
[15] Satyen Kale, Chansoo Lee, and Dávid Pál. Hardness of online sleeping combinatorial opti- mization problems. In Advances in Neural Information Processing Systems, pages 2181-2189, 2016.
[16] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection stochastic multi-armed bandits. ICML, volume 12, pages 655-662, 2012.
[17] Varun Kanade, H Brendan McMahan, and Brent Bryan. Sleeping experts and bandits with stochastic action availability and adversarial rewards. 2009.
[18] Varun Kanade and Thomas Steinke. Learning hurdles for sleeping experts. ACM Transactions on Computation Theory (TOCT), 6(3):11, 2014.
[19] Robert Kleinberg, Alexandru Niculescu-Mizil and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):245-277 2010.
10

---

[20] Tomas Kocak, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration bandit problems with side observations. In Advances Neural Information Processing Systems, pages 613-621, 2014.
[21] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. COLT, pages 1141-1154, 2015.
[22] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, 2018.
[23] Shie Mannor and Ohad Shamir. From bandits to experts: On the value of side-observations. In Advances in Neural Information Processing Systems, pages 684-692, 2011.
[24] Gergely Neu and Michal Valko. Online combinatorial optimization with stochastic decision sets and adversarial losses. In Advances in Neural Information Processing Systems, pages 2780-2788, 2014.
[25] Wenbo Ren, Jia Liu, and Ness B Shroff. PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint arXiv:1806.02970) 2018.
[26] Aadirupa Saha and Aditya Gopalan. Battle of bandits. In Uncertainty in Artificial Intelligence, 2018.
[27] Aadirupa Saha and Aditya Gopalan. PAC Battling Bandits in the Plackett-Luce Model. In Algorithmic Learning Theory, pages 700-737, 2019.
[28] Hossein Azari Soufiani, David C Parkes, and Lirong Xia. Preference elicitation for general random utility models. In Uncertainty in Artificial Intelligence, page 596. Citeseer, 2013.
[29] Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. Multi-dueling bandits with depen- dent arms. In Conference on Uncertainty Artificial Intelligence, UAI' 17, 2017.
[30] Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue. Advancements in dueling bandits. In IJCAI, pages 5502 5510, 2018.
[31] Balázs Szörényi, Róbert Busa-Fekete, Adil Paul, and Eyke Hüllermeier. Online rank elicitation for plackett-luce: A ducling bandits approach. In Advances in Neural Information Processing Systems, pages 604-612, 12, 2015.
[32] Tanguy Urvoy, Fabrice Clerot, Raphael Féraud, and Sami Naamane. Generic exploration and k-armed voting bandits. In International Conference on Machine Learning, pages 91-99, 2013.
[33] Huasen Wu and Xin Liu. Double Thompson sampling for dueling bandits. In Advances in Neural Information Processing Systems, pages 649-657, 2016.
[34] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5): 2012.
[35] Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201-1208. ACM, 2009.
[36] Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke. Copeland dueling bandits. In Advances in Neural Information Processing Systems, pages 307-315, 2015.
[37] Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke, al. Relative upper confidence bound for the k-armed dueling bandit problem. In JMLR Workshop and Conference Proceedings, number 32, pages 10-18. JMLR, 2014.
[38] Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference Web search and data mining, pages 73-82. ACM, 2014.


Reviews:
[{"review_id": "e19EtQHkd3x", "reviewer": "Reviewer_zsxN", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall, I think that the considered problem of this paper is interesting, and the theoretical analysis seems solid. However, there are still some weaknesses. \n1.\tThe 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.\n2.\tThe 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.\n\n**After Rebuttal**\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZmSbEP_RFU", "reviewer": "Reviewer_gxX7", "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.\n\nThis paper proves the following results:\n- 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.\n- 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.\n- 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.\n- Finally, they run some empirical simulations comparing the two above algorithms on synthetic data.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nI 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. \nDueling Bandits with Adversarial Sleeping\n\nThis 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.\n\nThis paper proves the following results:\n- 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.\n- 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.\n- 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.\n- Finally, they run some empirical simulations comparing the two above algorithms on synthetic data.\n\nThe 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). \n\nThe 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). \n\nQuestions:\n\nIn 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. \n\nMinor Comments:\n\nPage 9: “though the later” -> “though the latter”\nPage 6: “computatinally” -> “computationally”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "86CoV6sUCKI", "reviewer": "Reviewer_ASCB", "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.\nUnder 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "# Significance/Novelty\n\nThis 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. \n\n# Strengths\n\nThe difficulty of the considered problem is analyzed by deriving a lower bound holding for any (consistent) learning algorithm for this problem.\nAs 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. \n\n# Weaknesses\n\nIt 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). \nHowever, 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}.\nAnother (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.\n\n[1] Bubeck & Cesa-Bianchi (2012), “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems”\n\n[2] Zoghi et al., (2014), “Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem”\n\n[3] Wu & Liu, (2016), “Double Thompson Sampling for Dueling Bandits”\n\n\n# Suggestions to improve readability\n\n1. 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. \n2. 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. \n3. 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).\n4. 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)).\n5. 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). \n\n\n**Other minor things:**\n\nline 112: indicator random(?) variable\n\nProof (sketch) of Theorem 1: It is a bit strange to speak of ‘’subintervals’’\n\nWouldn’t it be more reasonable to call SlDB-UCB rather SlDB-RUCB, as it is based on RUCB?\n\nI 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).\n\nStatement of Theorem 3 (line 206): \\alpha > 1/2 is also possible I think?\n\nlines 223: holds good? \n\nStatement of Theorem 8 (line 254):  Why is T tending against infinity?\n\nFinally, 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.\n\n# Post Rebuttal\n\nThe 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues with this paper", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

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)