Optimal Algorithms for Stochastic Contextual Preference Bandits 
Authors: Aadirupa Saha
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online
bandit
subsetwise
dueling
preference
contextual
stochastic
optimal
regret
lower bound

Abstract: We consider the problem of preference bandits in the contextual setting. At each round, the learner is presented with a context set of $K$ items, chosen randomly from a potentially infinite set of arms $\mathcal D \subseteq \mathbf R^d$. However, unlike classical contextual bandits, our framework only allows the learner to receive feedback in terms of item preferences: At each round, the learner is allowed to play a subset of size $q$ (any $q \in \{2,\ldots,K\}$) upon which only a (noisy) winner of the subset is revealed. Yet, same as the classical setup, the goal is still to compete against the best context arm at each round. The problem is relevant in various online decision-making scenarios, including recommender systems, information retrieval, tournament ranking--typically any application where it's easier to elicit the items' relative strength instead of their absolute scores. To the best of our knowledge, this work is the first to consider preference-based stochastic contextual bandits for potentially infinite decision spaces. We start with presenting two algorithms for the special case of pairwise preferences $(q=2)$: The first algorithm is simple and easy to implement with an $\tilde O(d\sqrt{T})$ regret guarantee, while the second algorithm is shown to achieve the optimal $\tilde O(\sqrt{dT})$ regret, as follows from our $\Omega(\sqrt {dT})$ matching lower bound analysis. We then proceed to analyze the problem for any general $q$-subsetwise preferences ($q \ge 2$), where surprisingly, our lower bound proves the fundamental performance limit to be $\Omega(\sqrt{d T})$ yet again, independent of the subsetsize $q$. Following this, we propose a matching upper bound algorithm justifying the tightness of our results. This implies having access to subsetwise preferences does not help in faster information aggregation for our feedback model. 
All the results are corroborated empirically against existing baselines.

Optimal Algorithms for Stochastic Contextual Preference Bandits
Aadirupa Saha"
Abstract
We consider the problem of preference bandits in the contextual setting. At each round, the learner is presented with context of K items, chosen randomly from a potentially infinite set of arms D C RR. However, unlike classical contextual bandits, our framework only allows the learner to receive feedback in terms of item preferences: At each round, the learner is allowed to play subset of size (any q . K}) upon which only (noisy) winner the subset revealed. Yet, same as the classical setup, the goal is still to compete against the best context arm each round. The problem is relevant in various online decision-making scenarios, including recommender systems, information retrieval, tournament ranking-typpcally any application where it's easier to elicit the items' relative strength instead of their absolute scores. To the best of our knowledge, this work is the first to consider preference-basee stochastic contextual bandits for potentially infinite decision spaces. We start with presenting two algorithms for the special case of pairwise preferences (q = 2): The first algorithm is simple and easy to implement with an (dv/T) regret guarantee, while the second algorithm is shown to achieve the optimal Ö(v D(VTT) regret, as follows from our ((VVT) matching lower bound analysis. We then proceed to analyze the problem for any general g-subsetwise preferences (q 2 2), where surprisingly, our lower bound proves the fundamental performance limit to be s!( ((VdT) yet again, independent of the subsetsize q. Following this, we propose matching upper bound algorithm justifying the tightness of our results. This implies having access to subsetwise preferences does not help in faster information aggregation for our feedback model. All the results are corroborated empirically against existing baselines.
Introduction
Sequential decision-making problems with side information (in the form of features or attributes),
have been popular in machine learning contextual bandits [16 13 26) A contextual bandit learner, at each round, observes context before taking action based on The resulting payoff is typically assumed to depend on the context and the action taken according to an unknown map. The learner aims to play the best possible action for the current context at each time and thus minimize its regret with respect to oracle that knows the payoff function.
In many learning settings, however, is more common to be able to only relatively compare actions, in decision step, instead of being able to gauge their absolute utilities. E.g., information retrieval, search engine optimization, recommender systems, crowdsourcing, drug testing, tournament ranking, social surveys etc. [18 21 A specifie application example is: Consider the problem of recommending items from catalog to users on shopping website. Each time, the context is determined by the visiting user's features together with all items' features. When subset of items is presented, the user clicks on one of them according to a relative preference model; only the items presented matter this plausibly models comparative cognitive choices being made by humans. The aim is converge to identify the overall best item in the catalog, Additionally, since our model is designed to leverage
Miirosoftt Research, New York, US; aasa@mi crosoft.com
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the structured preference feedback, we can handle very large decision spaces, unlike state of the art dueling bandits algorithms that only deals with pairwise preferences 447
23
etc., or even
All of them need to maintain X² matrix explicitly, and their regret scales as O(K). This becomes impractical for large (or infinite) action spaces of size K.
some of the recent works on general subsetwise preference bandits (e.g. 30
33 38
In this work, we consider a natural structured contextual preference bandit setting, comprised of items with intrinsic (absolute) scores depending on their features in an unknown way, e.g., linear with unknown weights. In the most general setup, the learner plays (compares) a subset 2 I q S K items and gets to see a (noisy) f-length rank-ordered feedback (where 1 S & S q) of the top-ranked items of the selected subset with probability distribution governed by the items' scores. We are primarily interested in developing adaptive subset-selectin algorithms for which guarantees can be given for a suitably defined measure of regret.
To the best of our knowledge, we are the first to give theoretical guarantees for the above problem of regret minimization in contextual preference bandits for potentially infinitely large decision spaces and design provably optimal algorithms for the same. Some recent works [17 (38) have considered this problem in the subset selection setup but their algorithms do not guarantee any finite time regret bounds, neither validate their performance optimality theoretically. In [15], authors considered a version of adversarial contextual dueling bandit problem, which only takes into account the special case of pairwise feedback (q = 2). Though similar in names, their problem framework and consequently the analysis are very different from ours. In their setup, at each time the preference matrix is determined by randomly chosen known context variable, and the algorithm is assumed to have access to a pool of finite set of policies. The goal of the learner to compete with the 'optimal policy in the pool' for which they proposed an sparring- -E like algorithm- thhir regret bound though scales as O(VT) in T, it depends linearly on the size of arm space (K in their notation), and thus become vacuous for infinitely large decision space. Moreover, their computational complexity also scales linearly with the size of the policy class, which tends to be prohibitively large in practice.
1. We propose the problem of structured contextual preference bandits. where each iteration, the learner is presented with set of K-arms S. (cach represented by d-dimensional feature vectors), and the task of the learner is to select a subset of at most g-items (1 9 K), with the objective being to identify the 'best arm' of Se in every round. The novelty of the framework lies in the relative preference based feedback model, which only allows the learner to see a noisy draw of the top-ranked items of the selected subset, unlike the absolute reward feedback used for standard bandits setup.
2. We first address the problem for the special case of dueling bandits, where q 2, i.e. the learner only have access to pairwise preferences of the selected item pairs at each round. We propose two algorithms for the basic dueling bandit setting: Our first algorithm, (Alg D. is based on the idea of selecting the most uncertain pair ("max-variance") ") from the set of prromisin candidates', and we prove an (ddVT) regret for the same (Thm. 3).
maximuum-Inforatiive.
3. Our second algorithm
seseewise-Adativeee Duel (Alg. B) is developed on the idea of tracking, in a phased fashion, the best arm of the context set, which ensures a sharper concentration rate of the pairwise scores. This results in Ó(VāT) P bound of our previous algorithm by a vd factor.
regret guarantee (Thm. 5). improving upon the regret
We also show that fundamental regret lower bound of 2( ((VvT) for the contextual ducling bandit problem addressed here (Thm. B. Thus theoretically our second algorithm (Alg, 3 is provably optimal, however our Alg. Toften works better in practice as we show in the experiments (Sec. G
5. We then analyze the problem for more general subsetwise preference feedback, where at each round, the learner is allowed to play a subset of q-items (g 2 2), upon which the winner feedback of the played subset revealed [10 30 33 We first prove an ((VIT) regret lower bound (Thm. 11 for the problem, which establishes that, interestingly. having access to subsetwise preferences does not really help in faster information aggregation (for the specific preference model considered here). Subsequently, we also discuss algorithm with near-optimal regret guarantee, whose regret bound is also independent of the subsetsize g up to logarithmic factors (Thm. [2p
TTee notation Ö()) hides logarithmic dependencies.
2

---

Finally, we corroborate our theoretical findings with empirical evaluations. Detailed Related works, Experiments and most of the technical proofs are moved to the appendix.
Related Works. Surprisingly, following the same spirit of extending standard multiarmed bandits (MAB) to continuous decision spaces (as in linear GP-baanits), there has been really very little work on the continuous extension of the Dueling Bandit problem [24]. The works in [38] 17 did attempt a similar objective, however, without any satisfactory theoretical performance guarantees. 24 considers the problem of dueling bandits on continuous arm set but under rather restrictive sets of assumptions: Twice continuously differentiable, lipschitz, strongly convex and smooth score/reward function, which are often impractical for modeling any real-world preference feedback. Recently, [28] consider the problem of k-way assortment selection, where the problem is minimize regret against the set of highest revenue. However, their objective is much different from ours. We focus on the regret against the single best item per iteration. Thus our pairwise action set must allow repeated item pulls, unlike their setup, due to which their algorithm does not lead to sublinear regret for our objective. In another recent work, [00] did address the problem of regret minimization in continuous Dueling Bandits, however without any finite time regret guarantee of their proposed algorithms, unlike ours, A more elaborated survey is given in Appendix A
Preliminaries and Problem Formulation
Notations. For any positive integer N,, we denote by [n] the set 21, (4p) is generically used to denote an indicator variable that takes the value if the predicate yp is true, and 0 otherwise. The decision space is denoted by D S Rd where d N.. We use 1, to denote an d-dimensional vector of all I's. For any matrix M E Rdxd, we denote respectively by Amax(MM and Amin(M) the
maximum minimum eigenvalue of matrix M. For any x E Rd, ||x||as == vx T Mx denotes the weighted f--norm associated with matrix M (assuming M is positive-definite.
2.1 Problem Setup
We consider the stochastic K armed contextual dueling bandit problem for T rounds, where at each round E [T]. the learner is presented with context set S; = {xf, x2.,.., xxx
D c Id of size
K which is drawn IID from some d-dimensional decision space DD (according to some unknown distribution on D, say Pp). The learner is permitted to play a subset Xr S S, of size q 2 2, given a fixed I K (see the formal setup in Sec. 1..). Clearly for 9 = 2, the problem reduces to the sequential duel (pair of items) selection, say in this case we denote X, = {x,, Yr). Upon this, the environment provides a stochastic subsetwise preference feedback as follows:
Subsetwise-Prefereen Feedback Model. At any round I,, upon selecting Xr, the learner receives e900)
a winner feedback Or such that: Pr(o. = x Xx)
for any x E Xr, where D - [0, 1] is utility score function on each point in the decisions space x E D. Note our preference model essentially boils down to the well studied Plackett Luce (PL) choice model with the
Σyex, eRIST
individual PI. score of item-z being c 21 35 32 30 If = 2, then or 1(x, preferred over y:) simply indicates the preferred arm of the duel (x). such that for any x. E D, the probability x is preferred over y, denoted by Pr(x > y), is drawn according to ~ Ber (a (h(x,)))) here (-))
being the sigmoid transformation (i.e. (xx = Ite for any I E IR.
1
Analysis with linear scores. In this paper, we assume that g(x) = xT 0", Vx E D, where 0' E Rd is some unknown fixed vector in R2 such that || < 1. We will henceforth denote this linear utility based 'subsetwise preference model' as SPM(0" d, .).
Regret Minimization. Suppose x; == arg maxxes, x 0" is the best arm (with highest score) of round Then the goal of the learner is minimize the T-runnd cumulative regret RT = Σin rt with respect to the best arm x; of each round I, where we measure the instantaneous
Objective:
regret r; of playing set X, in terms of the average score of the played duel Excx, 0"
Precisely,
[.]
T
Σ
X, x 0
Rr
x 0
X
3

---

Above notion of learner's 's regret is motivated from the definition of classical K-armed dueling bandit regret introduced by 44 which is later adopted by the dueling bandit literature 44 23
3.
43
45
38 31 Here the context set at any round I. is assumed to be a fixed set of K arms [] and at each round the instantaneous regret incurred by the learner for playing an arm-pair
S.
(1,,h) E [K x K] is given by r/ P((...)))(( i, E [K] being the 'best-arm' in the
41 depending on the underlying hindsight (e.g. condoreet winner [46] or copeland winner 23 preference matrix P E [0, 1]K*K
Remark 1 (Equivalence with Dueling Bandit Regret when q = 2). It is easy to note that assuming the context set St S 'D to be fixed Vt E [T] and denoting x; = x", our regret definition (Eqn. (I) is equivalent to dueling bandit regret (up constant factors), as in our case the pairwise advantage against the best arm (i.e. Pr(x',X0 - -22 can be both upper and lower bounded as:
(1) Pr(x",xx))
2(ex* 40 )² S
(e" -e 0')
(x' Tx and (2) Pr(x" Px(x"
xx)
4e
Combining above claims we get
Rg
1 RG DDD
I 2
Re (analysis detail given in Appendix B.
46
3 Dueling Feedback (q - 2): Algorithm and Analysis
We first analyze the problem for pairwise preference feedback (g = 2 case). Before proceeding to the actual algorithms, it is crucial to note that, same as generalized linear Bandits (GLB) [16 26). both our algorithms use standard MLE techniques for maintaining a 'tight estimate' of 0* (Line 5 of Alg. I Line 8 of Alg. 3. This is since our dueling preference feedback can be seen as generalized linear reward over item pairs (details in Appendix [.. However, the regret definition of ducling bandits (Eqn. )T) being very different than GL.B objective, direct application of any GL.B algorithm will simply lead to (TT) regret in our setup: The objective of any GLB learner is to converge to the arm with highest reward, unlike ours. Thus any GLM routine would always converge to the best- worst arm pair as that would be perceived to be the duel with highest reward (pairwise preference in our case). On the contrary, to have any sublinear regret, we require the learner to eventually play only the best arm in the duel, which does not have the highest perwise-preffrence (reward). This is the inherent complexity and primary difference of any dueling bandit problem w.r.t. GLB objective or any MAB framework per se. As result, sublinear MAB algorithm never works for dueling/preference bandit objectives. To circumvent the problem, we design fairly non-trivial arm-selection rules for our proposed algorithms, e.g., Alg. first needs to construct promising set C, and then pick the maximum informative pair amongst them (Line 6-7, Alg Alg. needs to optimally maintain the set of" 'good-items'' G with a careful arm-selection rule which significantly differs from any GLB approach (Line 19, Alg 2). Consequently, we also need to resolve to new proof ideas towards analyzing their regret guarantees which remains one of the primary novelty of this work.
3.1 Algorithm-1:
Our first algorithm is computationally efficient one with a O(d/T) regret guarantee (Thm. which is only suboptimal by a factor of O(Vd) (as reflects from our lower bound, Thm. 10 Sec.
Main Idea: At any time I, the algorithm simply maintains an UCB estimate on the pairwise scores y(x,y) == 0- (x y) + n/|x - yll for any pair of arms (x, x,y St. where V. = - (x+ (x)(x, - T=)T, ê being the maximum likelihood estimator (MLE) of our =={x
preference model parameter. It then builds a set of promising arms C₁ == {x E Se 7/(x, y) > 0, Vy E E S. \ {x]}): Arms that beats the rest in terms of their UCB score h(x,y). Finally it plays -
the most-uncertain (least sampled) pair (xt, Yr) := arg maXx,yeC, ||x- -yll,- Note (æ He) is the pair with highest pairwise score variance in C,,, hence 'maximum informative'. (Detail in Alg.
Analysis. Regret guarantee of Alg (Thm. is based on the following main lemmas.
Lemma 1 NSrmaleorrl Bound). Suppose [(11, Y1), (xy.Y)..... (Xx, Yet) be sequence of arm-pe -air played such that all arms x E (x,,y>); ) =1 belong to the ball of unit radius. Also suppose
the initial exploration length to be such that Amin
(x+)x=-)+)] (x>))xx>
-) 2 1. Then V > to-
Et I|(x, -r.)ll, S
2dt 2dtlog log
where recall Vo+1
== :=
(x)) -T)

---

Algorithm Maximum--nformatiie- (MaxInP)
1: input: Learning rate 17 > 0, exploration length to
2: init: Select ty pairs (=)
each drawn at random from S,, and observe the corre- sponding preference feedback {ortre
3: Set Vio+1 == - (x, y- (x+ V+)
4: for = to + 1, 60 + 2. ..... do
5: Compute the MI.F 0. on {(x+, yr, or or]] En'1 (or 07-00(6s [(xx -y-) (x+ -y-)
6:
:===xx,y- E St (x - y) O2 n +))lly, 0} 7: Compute (x,, yt) == arg yEC, x - -y
8: Play the duel (i). Receive 0r 1 beats y:)
9: Update V2+1 = 1/2 + (x: - yx)( -t)
10:
end for
Lemma 2 (Confidence Ellipsoid), Suppose the initial exploration
length to be such that
Amin
Ex=i(x - --+)") 2 1, and k is as defined in Thm.
3
Then for any > O,
with probability at least (1 -8), all 1 to 110 0ellv S
1
d
log
1
2t d
+ log f. where
2
recall Ve+1 = =t= y+) ---)
Theorem 3 (Regret bound of Maximum-Informativeeeeo (Alg.
[p]. Let "
loog(1 + ) + log where i e [or d((x -y)-))(p y)T is the mini-
2K
mum slope of the estimated sigmoid when Ô is sufficiently close to 0* derivative of the sigmoid function o()). Then given any > with probability at least (1 - -28).
(o'()) being the first order
the T round cumulative regret of Maximum Informative Pair satisfies:
1 K
d log
27 d
1
4to + T
=0 dVdTToo T)
=oddTTlog
)
T
RT S to +
1+
+
log
2dT log
d8
2
Ci Civd+Ca log(1/8) Avsin (B)
where we choose to 2
B
x. (x) y] (for
Amin(B)
some universal problem independent constants C1 C2 0).
Proof. (sketch) Our choice of to ensures that with probability at least (1 - 8), Via+1 is full rank, or more precisely Amin Anin(Ves+1) (1t++1> [42 (see Lem. 13 Appendix D for the formal statement). We next apply the two key concentration lemmas (Lem [ and 2h. upon expressing the regret definition in terms of the above concentration results. Precisely, using Lem. and our 'most informative pair' based arm selection strategy, we can show at any round t > to. we can bound r, S 4||x; yz Velly.-.. The results
now follows from the choice of and Lem
The complete proof is given in Appendix D.I
3.2 Algorithm-2:
(Sta'D))
Our second algorithm runs with provable optimal regret bound of Ô(vdT) except with an additional VlogK factor. When K = O(1), the algorithm thus yields an optimal regret guarantee.
Main Idea. The algorithm proceeds in stages E [log 7'I with the aim of tracking a set of 'promising arms' G per stage: At each such stage s, we maintain confidence interval on the pairwise scores of each index pair (i.j) (t. If at any stage s, the confidence-score of any arm-pair is not estimated to the 'sufficient accuracy', : we play that pair and include it in the of 'informative pairs' of stage &" to be further explored in following rounds. Otherwise, we sequentially eliminate the wweakly-performine
arms which gets defeated by some other arm terms of its optimistic pairwise score, and proceed to the next stage confidence interval. Now the pairwise scores of every index pair in the set of "promising-an is almost 'accurately estimated up to high confidence', we pick the first arm the one which has
to examine the surviving arms with stricter
G*
5

---

the maximum estimated score, followed by choosing its strongest challenger y, which beats x, with highest pairwise preference. The algorithm is given in Alg. B (Appendix 3).
Analysis. Thm. proves an optimal (VVTT) regret bound of Alg. (matching the regret lower bound, Thm. TO.. It is worth pointing that the near optimal regret analysis of Stagewise-Adape Adaptive- Duel crucially relies on the stronger concentration guarantees of the pairwise scores (compared the weaker concentration of Lem. used earlier for Alg. D. Note, this is made possible by specifically maintaining the independent 'stage-wise informative samples' o² as also pioneered in few of the earlier works 8 13 for multi-armed bandits (see our proof analysis of Lem.
Lemma 4 (Sharper Concentration of Pairwise Scores). Consider any
> O, and suppose we
set the parameters of Stagewise-Aduptive- (Alg. 3 as 1 = 2x
3 2 log
3TK á
where k =
inl |x- -iss ((x and to =
Civ CivatCa (lo(2/8)
4A where A
Amiaa
Amia(By
ne (df +ogg 2) and B = xy (xx -1)x-y) y) (for some universal problem independent
constants C1. C2 > 0). Then with probability at least (1 - 8). for all stages E [log at all rounds t > to and all index pairs i, E g of round t: [(x; - x (0" 09) S (((,
Theorem 5 (Regret bound of Stagewise-Adaptive Dalaptive-DullAAA (Alg. 3) Consider set to and nj as per Lem. Then for any ô > O, with probability at least (1 - 8), the regret of Alg. 3 can be bounded as:
AtnI (-d
TTg T +2VT= =0 0
/dT'lgg
TK 8
Td
Rr S to + Any 2d log
log
log
log 5
Proof. (sketch) Suppose we denote by &5 : (t [T] [tu] t & ULLnR TJ (0) the set of all good time intervals where all the index pairs pI (i, j) are estimated within the confidence accuracy VT The proof crucially relies on the concentration bound of Lem. from which we first derive:
Lemma 6. For any >> to, suppose the pair (xt, Yt) is chosen at stage st, and in denotes the best action of round t. i.e. xi: x arg maxxes, x 0". Then any 8 E (0, 1), with probability at
if E & otherwise
least (1-8), all to: iz E G for both x E y1), g(x)) S
Owning to Lem. and due to the construction of our 'stagewise-good item pairs' we can also show:
Lemma 7. At any stage s E [log TJ, with probability at least (1 5), v1Ø0 1/29
22
4tuT
The final regret bound can be derived combining the results of Lem. aan (see Appendix E.5)
4 Lower Bound for Dueling (q 2) Feedback
We now proceed to understand the fundamental performance limit of our contextual preference bandits problem for pairwise preference (g 2) case. Towards this we use a novel idea of reducing linear bandits problem to our setup which finally leads to the desired lower bound of (( /d)..
Bandits to our framework. Let us instantiate any instance of our K-armed contextual dueling bandit problem by its problem parameter 0" E Rd as Iodb _ K, T. On the other hand define any instance of K K-armed contextual linear bandit problem [13] with problem parameter 0* E Rd as Icll (0" K, T): Recall in this setup, at each iteration the learner is provided with a context set S. = {x] xh_ .......... x C Rd of size K (as before |x||| S 1, Vx E S.) upon which the learner choose an arm X2 E S,, and the environment feedbacks a reward r(x,) = x, 0" +eg. where E, is zero mean random noise. Objective is to minimize the regret with respect to the best action, x : arg maxxes, x 0", of each round f, defined as: Recl DT (x; 0" -x_ 0*)
Reducing I.
Main Idea. For proving lower bound for Iedb (0", K, T),, first show under Gumbel noise 9 3 any instance of contextual linear bandits Ielb can be reduced to an instance of Iodb,
Lemma 8 (Reducing Zelb with Gumbel noise to ITdl).. There exists a reduction from the Io problem
idd (under Gumbel noise, i.e. Et (umbel(O, 1)) to I which preserves the expected regret.

---

Proof. (sketch) Suppose we have a blackbox algorithm for the instance of Indb problem, say A To prove the claim, our goal is to show that this can be used solve the I problem where the underlying stochastic noise, 6, at round I, is generated from (um 1) distribution [39 9.
Precisely we can construct an algorithm for I=b((" K, T) (say Acle using A as follows:
Algorithm 2
Ac for problem
K,T)
0 1(((x))) > rlyi))
A (at round t)
1: for 1,2, ... [T] do
2: Receive: (x,,))) + duel played by
A0ah at time t.
3: Play X2 at round (2t 1) of Iolb Re- ceive r(xe).
((x))
AA
time 21
4: Play Yt at round of Ialh Receive r(y:).
r(x))
(at round 2t 21)
ot time
5: Feedback: o = ((((x)) > r(yi)) to Acab.
Figure I: Demonstration of the reduction idea: Ialb to I
6:
end for
Lemma 9. If A rums on a problem instance Ieth (0", "0" K. 2T) with Gumbel 1) noise, then the internally the algorithm Aodb runs problem instance of Tool (0", K,T).
The proof of the above lemma is given in Appendix F.2 Lem. precisely shows reduction of Telb to Ioul The claim of Lem. now follows from the regret definitions of the I and Todh precisely we can show for any fixed 7, Rg = Reth. Complete proof is deferred to Appendix
Our lower bound result now immediately follows as a implication of Thm. 10 and from the existing lower bound result of Kaarmed d'dimensional contextual linear bandits problem [3].
Theorem 10 (SPM(0", d, 2): Regret Lower Bound). For any algorithm A for the problem of linear-score based stochastic K K-armed contextual dueling bandit of dimensional-d, there exists a sequence of d-dimensional context sets {x],...x',, .xx)]= and constant y such that the regret incurred by A on T rounds is at least D22 /2dT), i.e. (r(A) Z 3/22dT, for any T 2 d².
5 Analysis for General Subsetwise Preference Feedback (any q E [K])
We now extend our analysis to any general q-subsetwise feedback, where at round t the learner is permitted play subset X₂ S S, of size q 2 given a fixed g S K (formal setup in Sec. (2T)). We first analyze the regret lower bound, which, somewhat surprisingly. turns out to be independent of (Thm. IT). We also propose an algorithm following this. Proof details are given in Appendix
5.1 Regret Lower Bound
We first show that for any given 2 2, there exists a problem instance where no learner can achieve a better learning rate than 22( 2(vvd2 (d). However the conclusions are much similar to the existing regret lower bounds for finite K arm preference bandits for Plackett- (PL) model [30 33). As described in Sec. 2. since our preference model can also be seen a special case of PL model, our results show even the contextual framework, the learner can not attain faster rate by playing larger subsets.
Theorem 11 (Regret Lower Bound (Subsetwise Preferences)). Given any q 2 2 and d 1, for any algorithu A for the problem of stochastic K K-armed d-dimensional linear contextual bandit with SPM(0, d, q) feedback model, there exists a sequence of d-dimensional context sets {xf,... x²x x and a choice of 0 such that the regret incurred by A on rounds is at least 2( (())T).
5.2 Algorithm and Regret Guarantee
Given the above lower bound, the first thing to note is our Alg. itself yields an optimal Ō(v dT) algorithm (which only makes pairwise queries per round) in case the problem allows the learner to query preferences of any subsets of size 1, 1,2..... However, we here propose general version of Alg. which also based on the idea of stagewise-eliminatin but can exploit subsetwise preferences for any general 2 2; it works even if the learner is restricted to play only sets of size y. Moreover, even though for the worst case instances, better regret guarantee is not possible (as shown in Thm.
II it can exploit the problem structure when there is sufficient 'quality gap' between items.
7

---

Main Ideas. The main idea is to exploit the subsetwise feedback using the idea of rank- rank-breaking [2] for extracting pairwise estimates from subsetwise feedback. Given these pairwise estimates, now the algorithm may proceed the same as the original Alg. 3 however instead of selecting a pair of arms, we can now select a subset q most-promising arms: First, by selecting a potential good arm and then recursively selecting the best challenger of the already selected items. The complete description is given in Alg. | (Appendix (..2). The challenging part, however, lies its regret analysis which requires justifying the right concentration rates of 0₁, obtained from the above pairwise estimates.
The detailed regret analysis is given in Appendix G.3 which finally lead to the following guarantee:
Theorem 12 (Regret bound of Sta DaaD+++ (Alg-
Consider any δ O, and suppose we the
2
parameters of Sta' +++ (Alg. 3) as 1
3 2xd
V
2 log
3oTK 8
and to
Civ (od++22/log(a0 (log(29/6)
Amnin
4A Amin(B) (By where A, K, B is as defined in Lem.
4
Then with probability at least (1 8), the T round
cumulative regret of Sta' + is at most O
v dT log(T)
log
9TK (=0 0
log
Td log / 8))
Experiments
This section gives empirical performances of our algorithms (Alg. and and compare them with some existing preference learning algorithms. The details of the algorithms are given below:
Algorithms. 1. MaxInP: Algorithm Dekiimmu-Inforrmtive-PPeee (Alg. as described in Sec.
2. Sta'D: D: Our proposed algorithm Stagewise-Adapiive-D
(Alg. [ as described in Sec. 3
SS: Self-Sparring (independent beta priors on each arm) algorithm for multi-dueling bandits 37
RUCB: The Relative Upper Confidence Bound algorithm for regret minimization in standard dueling bandits 46). 5. DTS: Dueling- Thooppon Sampling algorithm for best arm identification problem in bayesian dueling bandits [T7]. In every experiment, the performances of the algorithms are measured in terms of cumulative regret (sec. D. averaged across runs, reported with standard deviation.
Constructing Problem Instances. The difficulty of the instances depends on the difference scores of the best and second best arms, which, in the hindsight, is actually governed by the 'worst slope' of the sigmoid function к (see the dependency of k in Thm. 3 or Thm. [5, and also by the underlying problem parameter 0* E Rdd So used different linear score based problem instances based on 3 different characterizations of 0" E Rd (with K arms and dimension d): 1. Easy (d, K). Extreme e(d, K), and 3. Intermediate m(d, K), by suitably adjusting the norm 0 112- Also in all settings, the d-dimensional feature vectors (of the arm set) are generated as random linear combination of each arm be random linear combination of the d-dimensional basis vectors (for scaling issues of the item scores, we limit each instance vector to be within ball of radius 1, i.e. f--norm upper bounded by 1).
Regret vs Time. For this experiment we fix d = 10 and K = 50. Fig. shows both our algorithms MaxInP and Sta'D always outperform the rest, and their performance gets comparatively better with increasing hardness of the instances. As expected, RUCB performs the worst as by construction it fails to exploit the structure of underlying linear score based item preferences, due to the same reason SS performs poorly as well (note we implement independent armed version of the Self-Sparring algorithm [37] for this case, and later the Kernelized version for the case of non-linear item scores). On the contrary, DTS performs reasonably well as it designed to exploit the underlying utility structures in the wrefeiseeppeerecsss..
Cumulative negret (log2)
Reami
Cumulative Regret (log2)
ml.0.5
Cumulative Regret (log2)
Rezin
e(10.50)
DTS
DTS
RUCB
Time
Time
Time
Figure 2: Average Cumulative Regret vs Time across algorithms problem instances (linear score based preferences, d = 10, K = 50)
8

---

Regret vs Context-size (K). We now compare the (averaged) final cumulative regret of each algo- rithm over varying context set size (K) over two different problem instances. For this experiment we fix = 10 and = 1500. From Fig. note that again our algorithms superiorly outperforms the other baselines with DIS performing competitively. SS and RUCB performs very badly due to the same reason as explained for Fig Interesting observation to make is that the performance of both our algorithms MaxInP and Sta'D D is almost independent of K as also follows from their respective regret guarantees (see Thm. and Thm. [5 long as is fixed our algorithms clearly could identify the best item irrespectively of the size K of the context set, owning to their ability to exploit the underlying preference structures, unlike SS or RUCB.
h/10) IT 15001
m/10] IT = 15007
8000
Sta'D
Final regret
6000
DTS
Final regret
07S
1500
4000
1000
2000
500
20
40
60
80
100
20
40
60
80
100
Figure 3: Final regret (averaged) context-set size (K) across different algorithms two different problem instances (d 10)
Regret vs Dimension (d). For this experiment we fix K 80 and 1500. From Fig. shows that in general the performance of every algorithm degrades over increasing d. However the effect is much most severe for the DTS baseline compared to ours. Since RUCB can not exploit the underlying preference structure, its performance is mostly independent of d and same goes for SS as well due to the same reason. The interesting observation to make is with increasing d, fixed T and K, our first algorithm MaxInP indeed performs worse than Sta'D. following their theoretical regret guarantees which shows the former has multiplicative O(vd) worse regret than latter (see Thm. 5
h1801 15001
15001
Maxina
Maxinl
8000
Rúca
1000
RÚCh
regret
Final regret
6000
750
4000
500
2000
250
Figure 4: Final regret (averaged) vs featue dimension (d) across algorithms on two different problem instances (K 80)
Non-Linear score based preferences We finally also run some experiments to compare our regret performances on non-linear score based preferences (i.e. the score function gxx) not linear in x, see Sec. for details). We use three differrntt score functions for the non-linear setup.
Environments. We use thsese 3 functions as 9(-): 1. Quadratic, 2. Six-Hlump Camel and Gold Stein. Quadratic the reward function f(x) x Hx + x w + c, where H E [-1, 1]axd, w [] and [-1, 1] 1] are randomly generated. The Six-Hump Camel and Gold Stein functions as described in For all cases, we fix d = and K = 50.
Algorithms. We use slightly modified version of our two algorithms (MaxInP and Sta D) for the non-linear scores, since the GLM based parameter estimation techniques would no longer work here. But unfortunately, without suitable assumptions, we do not have an efficient way to estimate the score functions for this general setup, so instead we fit GP to the underlying unknown score function g(.) based on the Laplace approximation based technique suggested in 29 (see Chap 3). For SS also we now used the kernelized self- sparring version of the algorithm model (instead of linear model).
37 and for DTS we now fit GP

---

Cumulative Regrat (log)
Minrggton DROP)
Six-Hump Came!
Cumulettive Regret (log)
1.0
CLYDIOP)
Stein
Beebepiocy Ste BTSIGP)
Cumulative Regret
S 80
500
1000
1500
2000
1500
2000
1000 Time
1500
2000
Time
Time
Figure 5: Avg. Cumulative Regret Time across algorithms on problem instances (non-linear score based preferences, 10, = 50)
Fig. 5 shows our algorithms still outperform the rest almost all the instances. This actually implies the generality of our algorithmic ideas which applies beyond linear- (hence it is also worth understanding their theoretical guarantees for this general setup in future works). Moreover, unlike the previous scenarios SS, now starts to perform better since it could now exploit underlying preferences structures owing to the implementation of kernelized self-sparring (3]
7 Conclusion and Future Scopes
We consider the problem of regret minimization for contextual preference bandits for potentially infinite decision spaces. To the best of our knowledge, this the first work to give optimal regret (up to logarithmic factors) Ó ddT) algorithms along with a matching lower bound analysis. The problem of contextual preference bandits being niche and highly practically relevant area, undoubtedly there are numerous interesting open threads to pursue along this direction: E.g. considering other link functions (probit, nested logit, etc.) based the real-world system needs, analyzing the regret bound for adversarial preferences, or even extending preferences bandits setup to other related bandit frameworks like side information 27 22 feedback graphs 4 [] etc. Analyzing
instance dependent regret guarantees also remains to be an interesting future direction to see what improvements can be claimed for larger q under sufficient "quality gap' between the items.
10

---

Acknowledgment
Sincere thanks to Branislav Kveton and Ofer Meshi for some of the initial discussions when author was an intern at Google Research, Mountain View. Special thanks to Branislav Kveton for his insightful guidance basics of
and towards developing Algorithm
References
[1] Yasin Abbasi- Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. Conference on Learning Theory, pages 39-1, 2012.
[3] Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pages 856-864, 2014.
[4] Noga Alon, Nicolo Bisa-Bianchh, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In JMLR WORKSHOP AND CONFERENCE PROCEEDINGS, volume 40. Microtome Publishing, 2015.
[5] Noga Alon, Nicolo DisacBianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 1786)) 2017.
[6] Jean- Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COL.T-23th Conference on Learning Theory-2010, pages 13-p, 2010.
[7] Peter Auer. Using confidence bounds for sxploiaaiion-epllratiie trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
[8] Peter Auer, Nicolo Gesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
(9] Hossein Azari, David Parks, and Lirong Xia. Random utility theory for social choice. In Advances in Neural Information Processing Systems, pages 226-134, 2012.
[10] Brian Brost, Yevgeny Seldin, Ingemar J. Cox, and Christina Lioma. Multi-dueling bandits and their application online ranker evaluation. CoRR, abs/l 608 06.53,25,, 2016.
[11] Xi Chen, Yuanzhi Li, and Jieming Mao. nearly instance optimal algorithm for top-k ranking under the multinomial logit model. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2504-2522. SIAM, 2018
[12] Yuxin Chen and Changho Suh. Spectral mle: Top-k rank aggregation from pairwise comparisons. In International Conference on Machine Learning, pages 37 1-300, 2015.
[13) Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-2144 2011.
[14] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008
[15] Miroslav Dudík, Katja Hofmann, Robert Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference Learning Theory, pages 563-587, 2015.
[16] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances Neural Information Processing Systems, pages 586-594, 2010.
[17] Javier González, Zhenwen Dai, Andreas Damianou, and Neil D Lawrence. Preferential bayesian optimization. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1282-1291. JMLR. org, 2017.

---

[18] Bruce Hajek, Sewoong Oh, and Jiaming Xu. Minimax-optinn inference from partial rankings. In Advances in Neural Information Processing Systems, pages 1475-1483, 2014.
[19] Minje Jang, Sunghyun Kim, Changho Suh, and Sewoong Oh. Optimal sample complexity of m-wise data for top-k ranking. In Advances in Neural Information Processing Systems, pages 1685-1695, 2017.
[20] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 655-662, 2012.
[21] Ashish Khetan and Sewoong Oh. Data-driven rank breaking for efficient rank aggregation. Journal of Machine Learning Research, 17(193):1-54, 2016.
[22] Tomas Kocak, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration in bandit problems with side observations. In Advances in Neural Information Processing Systems, pages 613-621, 2014.
[23] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference Learning Theory, pages 1141-1154, 2015.
[24] Wataru Kumagai. Regret analysis for continuous dueling bandit. In Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017.
[25] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, 2018.
[26] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2071-2080. JMLR. org, 2017.
[27] 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.
[28] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. In Advances in Neural Information Processing Systems, pages 3145-3155, 2019.
[29] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. The MIT press, 2006.
[30] Wenbo Ren, Jia Liu, and Ness Shroff. Pac ranking from pairwise and listwise queries: Lower bounds and upper bound. arXiv preprint 1xXiv:8806.029000 2018.
[31] Aadirupa Saha and Aditya Gopalan. Battle of bandits. In Uncertainty Artificial Intelligence, 2018.
[32] Aadirupa Saha and Aditya Gopalan. Pac-battling bandits with plackett-luce: Tradeoff between sample complexity and subset size. arXiv preprint arXiv: 04000, 2018.
[33] Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. In Advances in Neural Information Processing Systems, pages 983-993, 2019.
[34] 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.
[35] Hossein Azari Soufiani, David C Parkes, and Lirong Xia. Computing parametric ranking models via rank-breaking. ICML., pages 360-368, 2014.
[36] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2010.
[37] Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. Multi-dueling bandits with depen- dent arms. In Conference Uncertainty in Artificial Intelligence, UAI' 17, 2017.
12

---

[38] Yanan Sui, Vincent Zhuang, Joel W Burdick, and Yisong Yue. Multi-dueling bandits with dependent arms, arXiv preprint arXi::1705.00255; 2017.
[39] Jakub Tomezak. On some properties of the low-dimensional gumbel perturbations in perturb-and-map model. Statistics & Probability Letters, 115:8-15, 2016.
[40] Jakub M Tomezak. On some properties of the low-dimensional gumbel perturbations in the perturb-and-map model. Statistics Probability Letters, 115:8-15, 2016.
[41] 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.
[42] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
[43] Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. In Advances in Neural Information Processing Systems, 2016.
[44] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1533 1556, 2012.
[45] 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.
[46] Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten De Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. arXiv preprint arXiv:1312.3393 2013.
[47] Masrour Zoghi, Shimon Whiteson, Remi Munos, Maarten de Rijke, et 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.
13


Reviews:
[{"review_id": "y_Uje4SAZCv", "reviewer": "Reviewer_K3kQ", "summary": "This paper studies the following learning problem. A learner wishes to learn some fixed preference vector theta in R^d. Every round (for T rounds), a set of K d-dimensional actions S_t are sampled. The learner must choose a subset (possibly of bounded size) X of these actions. The learner then learns a noisy signal of which of the actions in the subset they chose is optimal, and receives as reward the average reward of the actions in X (where the reward of action x is simply <x, theta>).\n\nThe paper first studies the case where the learner is only allowed to select subsets of size 2 (the “dueling bandits” setting). The authors give two algorithms for this problem. The first algorithm they give guarantees regret ~O(d*sqrt(T)). This algorithm works by choosing the “maximum-informative” pair of actions each round (i.e. the pair of actions for which the estimator of which action will win has highest variance). They then give a second algorithm which reduces the dependence on d to sqrt(d) at the cost of an additional sqrt(log K) term (for a total runtime of O(sqrt(d log T log K)). At a high level, this algorithm is similar to the previous algorithm but operates in a sequence of ~log T stages, eliminating some arms each round. Finally, the authors demonstrate an Omega(sqrt(d T)) lower bound via a reduction from linear-contextual bandits.\n\nThe authors show how to extend these results to the case where the learner may choose a subset of more than 2 actions. Interestingly, this does not seem to significantly help; even with this ability, there is still an Omega(sqrt(dT)) lower bound. Moreover, even if the learner is only allowed to choose subsets of size q or greater, it is still possible to modify the algorithms above to get ~O(sqrt(dT)) regret (the main idea being that it is still possible to solicit comparisons between two items even if you are forced to use larger action sets).\n\nFinally, the authors evaluate their algorithms empirically on some synthetic data sets, showing that they perform better than existing dueling algorithms for this setting. ", "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 enjoyed reading this paper -- I think the setting the authors study is quite natural, and their results are fairly comprehensive (e.g. almost matching upper and lower bounds). Technically, while none of the techniques are extemely novel, the analysis is certainly non-trivial. The paper was well-written and easy to read. \n\nOne question I had after reading this paper: do any of the algorithms extend to the setting where the set of K active arms is chosen by an adversary every round instead of being sampled stochastically? My guess is that it messes with the concentration bounds in the analysis (e.g. Lemma 4), but I haven’t thought about it much. It seems like a natural setting to explore. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "hy7AASUFYuu", "reviewer": "Reviewer_tuGP", "summary": "The authors study the contextual bandit problem where the feedback is received in the form of preferences. In this setting there are K arms and at each time step k random context vectors x^t_1, .. x^t_K are drawn i.i.d. From some distribution. The algorithm can output a subset of arms of size q and gets to see a noisy version of which of the q arms has the highest reward. This noisy distribution is assumed to be the Plackett-Luce model (a popular ranking model) with parameter theta*. The goal is to compete with the regret of the best arm (assuming expected reward of arm i is theta* \\cdot x^t_i). The reward incurred by the algorithm is assumed to be the average reward of the subset played at time t. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The authors propose a simpler algorithm that achieves O(d sqrt{T}) regret and a more sophisticated stagewise algorithm that achieves the optimal O(sqrt{dT}) regret. The authors also show a matching sqrt{d T} regret for the case of general q, thereby showing that the stagewise algorithm is near optimal.\n\nThe problem is well motivated and the authors provide optimal regret guarantees for the proposed formulation. Although the techniques are inspired by existing work on contextual bandits, non-trivial ideas are needed to extend them to the preference setting. It is not clear why and how the algorithm proposed in section 5.2 is adding anything to the results given that the stage-wise algorithm already is optimal. Furthermore, it is not clear if the lower bounds proved in the paper indeed apply to the contexts being generated i.i.d. from some distribution. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "6ZjgRjMtSn", "reviewer": "Reviewer_TXKE", "summary": "This paper studies the problem of preference bandits in the contextual setting, where the online learner plays $q$ arms and observes a noisy winner of the subset. The goal is to identify the best arm given a context. Two special algorithms for the $q = 2$ case are presented, along with the regret upper bound and a matching lower bound. The results are then extended to a general $q$. Corresponding experiments are presented to verify the theoretical results.", "questions": "", "limitations": "", "rating": 5, "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": "This paper presents two novel algorithms for the stochastic contextual preference bandits for the special case $q = 2$, and extends the algorithm and corresponding regret upper and lower bound to more general $q$.\n\nMain comments on the clarity, quality, and significance:\n\n1) The motivation does not match with the problem: The introduction motivates the problem by an application in recommender systems, while the proposed algorithm needs to play repeated arms in one step (as pointed out in lines 102-104). The motivation is therefore slightly confusing as the same product or advertisement typically will not be shown repeatedly in one step. The linear MNL model (e.g., by Oh and Iyengar, 2019) seems to be a better fit for the motivation example. It is slightly hard to appreciate the significance without proper motivation.\n\n2) Comments on the lower bound (Theorem 10): The reduction from linear-contextual bandits to the studied framework is neat. It would be better to clarify the relation of regret on $\\mathcal{I}^{clb}$ and $\\mathcal{I}^{cdb}$ in Lemma 9. The current statement of \"algorithm runs on a problem instance\" is slightly vague and confusing (and the \"rums\" seems to be a typo...)\n\n3) The results on the general $g \\ge 2$ case: While the most interesting results of this paper seem to be the algorithm/analysis for the general setting (i.e., $g \\ge 2$), most related discussions are deferred to appendix. Given that the special case of $g=2$ (discussed from page 3 to page 7) is covered by the general case, please consider compressing the special case of $g=2$.\n\n3) The experiment results: In Figure 4, it is hard to see the down-going trend of performance when increasing the dimensionality (espeically given the error bar is so small). Maybe a larger range of $d$ will show a clear pattern. It is also hard to go through the experiment results with the socre functions $h(d, K)$, $e(d, K)$ and $m(d,K)$ are all in appendix. Please consider bringing them back.\n\n4) Minor comments on writing: The writing can be largely improved. Besides the comments above - \n\na) Line 182, Lemma 1, there is a \")\" missing after $y_2$.\n\nb) Line 283, \"attend\" -> \"attain\".\n\nc) Line 360, Remark 2: \"algorithms still outperforms\" -> \"algorithms still outperform others\"\n\nd) Line 344, (q) should be boldfaced.\n\ne) Figure 2 caption is covered by Figure 4.\n\nf) Figure 3 caption: \"Set size (K)\" -> \"Context-size (K)\"?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments on limitations above. There is no immediate societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of k-armed contextual preference bandits and gives optimal efficient algorithms matching lower bound regret guarantees.  Empirical studies are also included.  The results appear interesting and novel.  Despite some concerns about the motivation, the paper makes a sufficient contribution overall to warrant acceptance.
Decision: Accept (Poster)