Optimal Algorithms for Stochastic Contextual Preference Bandits

Abstract:
We consider the problem of preference bandits in the contextual setting. At each round, the learner is presented with a context set ofK items, chosen randomly from a potentially infinite set of arms D ⊆ R. 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 ∈ {2, . . . ,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 Õ(d √ T ) regret guarantee, while the second algorithm is shown to achieve the optimal Õ( √ dT ) regret, as follows from our Ω( √ dT ) matching lower bound analysis. We then proceed to analyze the problem for any general q-subsetwise preferences (q ≥ 2), where surprisingly, our lower bound proves the fundamental performance limit to be Ω( √ dT ) 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.

text: √ T ) regret guarantee, while the second algorithm is shown
to achieve the optimal Õ( √ dT ) regret, as follows from our Ω( √ dT ) matching lower bound analysis. We then proceed to analyze the problem for any general q-subsetwise preferences (q ≥ 2), where surprisingly, our lower bound proves the fundamental performance limit to be Ω( √ dT ) 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.

heading: 1 Introduction
text: Sequential decision-making problems with side information (in the form of features or attributes), have been popular in machine learning as contextual bandits [16, 13, 26]. A contextual bandit learner, at each round, observes a context before taking action based on it. 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 an oracle that knows the payoff function.
In many learning settings, however, it is more common to be able to only relatively compare actions, in a 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 specific application example is: Consider the problem of recommending items from a catalog to users on a shopping website. Each time, the context is determined by the visiting user’s features together with all items’ features. When a 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 to converge to identify the overall best item in the catalog. Additionally, since our model is designed to leverage
∗Microsoft Research, New York, US; aasa@microsoft.com.
35th Conference on Neural Information Processing Systems (NeurIPS 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 [47], [23] [43], [41] etc., or even some of the recent works on general subsetwise preference bandits (e.g. [30, 33, 38]). All of them need to maintain a K2 matrix explicitly, and their regret scales as O(K). This becomes impractical for large (or infinite) action spaces of size K.
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 ≤ q ≤ K items and gets to see a (noisy) `-length rank-ordered feedback (where 1 ≤ ` ≤ q) of the top-ranked items of the selected subset with a probability distribution governed by the items’ scores. We are primarily interested in developing adaptive subset-selection 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 a 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 is to compete with the ‘optimal policy in the pool’ for which they proposed an sparring-EXP4 like algorithm—their regret bound though scales as O( √ T ) 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 at each iteration, the learner is presented with a set of K-arms St (each represented by d-dimensional feature vectors), and the task of the learner is to select a subset of at most q-items (1 ≤ q ≤ K), with the objective being to identify the ‘best arm’ of St 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, Maximum-Informative-Pair (Alg 1), is based on the idea of selecting the most uncertain pair (‘max-variance’) from the set of ‘promising candidates’, and we prove an O(d √ T ) regret for the same (Thm. 3).
3. Our second algorithm Stagewise-Adaptive-Duel (Alg. 3), 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 Õ( √ dT ) 2 regret guarantee (Thm. 5), improving upon the regret bound of our previous algorithm by a √ d factor. 4. We also show that fundamental regret lower bound of Ω( √ dT ) for the contextual dueling bandit problem addressed here (Thm. 3). Thus theoretically our second algorithm (Alg. 3) is provably optimal, however our Alg. 1 often works better in practice as we show in the experiments (Sec. 6).
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 (q ≥ 2), upon which the winner feedback of the played subset is revealed [10, 30, 33]. We first prove an Ω( √ dT ) 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 an algorithm with near-optimal regret guarantee, whose regret bound is also independent of the subsetsize q up to logarithmic factors (Thm. 12).
2The notation Õ(·) hides logarithmic dependencies.
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 or GP-bandits), 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 to 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, [10] 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.

heading: 2 Preliminaries and Problem Formulation
text: Notations. For any positive integer n ∈ N+, we denote by [n] the set {1, 2, ..., n}. 1(ϕ) is generically used to denote an indicator variable that takes the value 1 if the predicate ϕ is true, and 0 otherwise. The decision space is denoted by D ⊆ Rd, where d ∈ N+. We use 1d to denote an d-dimensional vector of all 1’s. For any matrix M ∈ Rd×d, we denote respectively by λmax(M) and λmin(M) the maximum a minimum eigenvalue of matrix M . For any x ∈ Rd, ‖x‖M := √ x>Mx denotes the weighted `2-norm associated with matrix M (assuming M is positive-definite).

heading: 2.1 Problem Setup
text: We consider the stochastic K-armed contextual dueling bandit problem for T rounds, where at each round t ∈ [T ], the learner is presented with a context set St = {xt1,xt2, . . . ,xtK} ⊆ D ⊂ Rd of size K which is drawn IID from some d-dimensional decision space D (according to some unknown distribution on D, say PD). The learner is permitted to play a subset Xt ⊆ St of size q ≥ 2, given a fixed q ≤ K (see the formal setup in Sec. 2.1). Clearly for q = 2, the problem reduces to the sequential duel (pair of items) selection, say in this case we denote Xt = {xt,yt}. Upon this, the environment provides a stochastic subsetwise preference feedback as follows:
Subsetwise-Preference Feedback Model. At any round t, upon selecting Xt, the learner receives a winner feedback ot such that: Pr ( ot = x | Xt ) = e
g(x)∑ y∈Xt eg(y) for any x ∈ Xt, where
g : D 7→ [0, 1] is a utility score function on each point in the decisions space x ∈ D. Note our preference model essentially boils down to the well studied Plackett Luce (PL) choice model with the individual PL score of item-x being eg(x) [21, 35, 32, 30]. If q = 2, then ot = 1(xt preferred over yt) simply indicates the preferred arm of the duel (xt,yt), such that for any x,y ∈ D, the probability x is preferred over y, denoted by Pr(x y), is drawn according to ∼ Ber ( σ ( h(x,y) )) , here σ(·)
being the sigmoid transformation ( i.e. σ(x) = 11+e−x for any x ∈ R ) .
Analysis with linear scores. In this paper, we assume that g(x) = x>θ∗, ∀x ∈ D, where θ∗ ∈ Rd is some unknown fixed vector in Rd such that ‖θ∗‖ ≤ 1. We will henceforth denote this linear utility based ‘subsetwise preference model’ as SPM(θ∗, d, q).
Objective: Regret Minimization. Suppose x∗t := arg maxx∈St x>θ ∗ is the best arm (with highest score) of round t. Then the goal of the learner is to minimize the T -round cumulative regret RT = ∑T t=1 rt with respect to the best arm x ∗ t of each round t, where we measure the instantaneous
regret rt of playing a set Xt in terms of the average score of the played duel ∑ x∈Xt x>θ∗
|Xt| . Precisely,
RT = T∑ t=1 ( x∗>t θ ∗ − ∑ x∈Xt x >θ∗ |Xt| ) . (1)
Above notion of learner’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 [46, 23, 3, 43, 45, 38, 31]. Here the context set at any round t is assumed to be a fixed set of K arms St = [K], and at each round the instantaneous regret incurred by the learner for playing an arm-pair (it, jt) ∈ [K × K] is given by r(DB)t = P(i∗,it)+P(i∗,jt)−1 2 , i∗ ∈ [K] being the ‘best-arm’ in the hindsight (e.g. condorcet winner [46] or copeland winner [23, 41]) depending on the underlying preference matrix P ∈ [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 ⊆ D to be fixed ∀t ∈ [T ] and denoting x∗t = x∗, our regret definition (Eqn. (1)) is equivalent to dueling bandit regret (up to constant factors), as in our case the pairwise advantage against the best arm (i.e. Pr(x∗,xt) − 12 ) can be both upper and lower bounded as: (1) Pr(x∗,xt) − 12 = (ex ∗>θ∗−ex > t θ ∗ )
2(ex∗>θ∗+ex > t θ ∗ ) ≤ (x ∗−xt)>θ∗ 2 and (2) Pr(x ∗,xt) − 12 ≥ (x∗−xt)>θ∗ 4e .
Combining above claims we get RT4e ≤ R (DB) T ≤ RT 2 (analysis detail given in Appendix B.1).
3 Dueling Feedback (q = 2): Algorithm and Analysis
We first analyze the problem for pairwise preference feedback (q = 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 θ∗ (Line 5 of Alg. 1, Line 8 of Alg. 3). This is since our dueling preference feedback can be seen as a generalized linear reward over item pairs (details in Appendix C). However, the regret definition of dueling bandits (Eqn. (1)) being very different than GLB objective, a direct application of any GLB algorithm will simply lead to O(T ) 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 pairwise-preference (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 a result, a 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. 1 first needs to construct a promising-set Ct and then pick the maximum informative pair amongst them (Line 6-7, Alg1). Alg. 2 needs to optimally maintain the set of ’good-items’ Gs 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: Maximum-Informative-Pair
Our first algorithm is a computationally efficient one with a O(d √ T ) regret guarantee (Thm. 3), which is only suboptimal by a factor of O( √ d) (as reflects from our lower bound, Thm. 10, Sec. 4).
Main Idea: At any time t, the algorithm simply maintains an UCB estimate on the pairwise scores h̄(x,y) := θ̂
> (x − y) + η‖x − y‖V −1t for any pair of arms (x,y), x,y ∈ St, where Vt = ∑t−1 τ=1(xτ − yτ )(xτ − yτ )>, θ̂ being the maximum likelihood estimator (MLE) of our preference model parameter. It then builds a set of promising arms Ct := {x ∈ St | h̄(x,y) > 0, ∀y ∈ y ∈ St \ {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,yt) := arg maxx,y∈Ct ‖x− y‖V −1t . Note (xt, yt) is the pair with highest pairwise score variance in Ct, hence ‘maximum informative’. (Detail in Alg. 1.) Analysis. Regret guarantee of Alg.1 (Thm. 3) is based on the following main lemmas. Lemma 1 (Self-Normalized Bound). Suppose {(x1,y1), (x2,y2), . . . , (xt,yt)} be a sequence of arm-pair played such that all arms x ∈ {xτ ,yτ}tτ=1 belong to the ball of unit radius. Also suppose the initial exploration length t0 be such that λmin (∑t0 τ=1(xτ −yτ )(xτ −yτ )> ) ≥ 1. Then ∀ t > t0, ∑t τ=t0+1 ‖(xτ−yτ )‖V −1τ+1 ≤ √√√√2dt log( 4t0+td ) , where recall Vτ+1 := ∑τ j=1(xj−yj)(xj−yj)>.
Algorithm 1 Maximum-Informative-Pair (MaxInP) 1: input: Learning rate η > 0, exploration length t0 > 0 2: init: Select t0 pairs {(xτ ,yτ )}τ∈[t0], each drawn at random from Sτ , and observe the corre-
sponding preference feedback {oτ}τ∈[t0] 3: Set Vt0+1 := ∑t0 τ=1(xτ − yτ )(xτ − yτ )> 4: for t = t0 + 1, t0 + 2, . . . T do 5: Compute the MLE θ̂t on {(xτ ,yτ , oτ )}t−1τ=1: ∑t−1 τ=1 ( oτ − σ ( (xτ − yτ )>θ̂t )) (xτ − yτ ) = 0 6: Ct := {x,y ∈ St | (x− y)>θ̂t + η‖(x− y)‖V −1t > 0} 7: Compute (xt,yt) := arg maxx,y∈Ct ‖x− y‖V −1t 8: Play the duel (xt,yt). Receive ot = 1(xt beats yt) 9: Update Vt+1 = Vt + (xt − yt)(xt − yt)>
10: end for
Lemma 2 (Confidence Ellipsoid). Suppose the initial exploration length t0 be such that λmin (∑t0 τ=1(xτ − yτ )(xτ − yτ )> ) ≥ 1, and κ is as defined in Thm. 3. Then for any δ > 0,
with probability at least (1− δ), for all t > t0, ‖θ∗ − θ̂t‖Vt ≤ 12κ √ d 2 log ( 1 + 2td ) + log 1δ , where
recall Vt+1 := ∑t τ=1(xτ − yτ )(xτ − yτ )>.
Theorem 3 (Regret bound of Maximum-Informative-Pair (Alg. 1)). Let η = 1 2κ √ d 2 log(1 + 2T d ) + log 1 δ , where κ := inf‖x−y‖≤2,‖θ∗−θ̂‖≤1 [ σ′ ( (x − y)>θ̂ )] is the mini-
mum slope of the estimated sigmoid when θ̂ is sufficiently close to θ∗ ( σ′(·) being the first order
derivative of the sigmoid function σ(·) )
. Then given any δ > 0, with probability at least (1− 2δ), the T round cumulative regret of Maximum-Informative-Pair satisfies:
RT ≤ t0 +
( 1
κ
√ d
2 log
( 1 + 2T
d
) + log 1
δ )√√√√2dT log(4t0 + T d ) = O ( d √ T log ( T dδ )) ,
where we choose t0 = 2
( C1 √ d+C2 √ log(1/δ)
λmin(B)
)2 + 4λmin(B) , B = Ex,y iid∼PD [(x− y)(x− y)>] (for
some universal problem independent constants C1, C2 > 0).
Proof. (sketch) Our choice of t0 ensures that with probability at least (1− δ), Vt0+1 is full rank, or more precisely λmin(Vt0+1) ≥ 1 [42] (see Lem. 13, Appendix D for the formal statement). We next apply the two key concentration lemmas (Lem 1 and 2), upon expressing the regret definition in terms of the above concentration results. Precisely, using Lem. 2 and our ‘most informative pair’ based arm selection strategy, we can show at any round t > t0, we can bound rt ≤ 4‖xt − yt‖V −1t . The results now follows from the choice of η and Lem.1. The complete proof is given in Appendix D.1.
3.2 Algorithm-2: Stagewise-Adaptive-Duel (Sta′D)) Our second algorithm runs with a provable optimal regret bound of Õ( √ dT ), except with an additional√
logK factor. When K = O(1), the algorithm thus yields an optimal regret guarantee.
Main Idea. The algorithm proceeds in stages s ∈ blog T c with the aim of tracking a set of ‘promising arms’ Gs per stage: At each such stage s, we maintain confidence interval on the pairwise scores of each index pair (i, j) pst (i, j). 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 set of ‘informative pairs’ of stage φs to be further explored in following rounds. Otherwise, we sequentially eliminate the ‘weakly-performing’ arms which gets defeated by some other arm in terms of its optimistic pairwise score, and proceed to the next stage s + 1 to examine the surviving arms with a stricter confidence interval. Now if the pairwise scores of every index pair in the set of ‘promising-arms’ Gs is almost ‘accurately estimated up to high confidence’, we pick the first arm xt as the one which has
the maximum estimated score, followed by choosing its strongest challenger yt which beats xt with highest pairwise preference. The algorithm is given in Alg. 3 (Appendix 3). Analysis. Thm. 5 proves an optimal Õ( √ dT ) regret bound of Alg. 3 (matching the regret lower bound, Thm. 10). It is worth pointing that the near optimal regret analysis of Stagewise-AdaptiveDuel crucially relies on the stronger concentration guarantees of the pairwise scores (compared to the weaker concentration of Lem. 2 used earlier for Alg. 1). Note, this is made possible by specifically maintaining the independent ‘stage-wise informative samples’ φs as also pioneered in few of the earlier works [8, 13] for multi-armed bandits (see our proof analysis of Lem. 4). Lemma 4 (Sharper Concentration of Pairwise Scores). Consider any δ > 0, and suppose we set the parameters of Stagewise-Adaptive-Duel (Alg. 3) as η = 32κ √ 2 log 3TKδ , where κ :=
inf‖x−y‖≤2,‖θ∗−θ̂‖≤1
[ σ′ ( (x− y)>θ̂ )] , and t0 = 2 ( C1 √ d+C2 √ log(2/δ)
λmin(B)
)2 + 4Λλmin(B) , where Λ =
8 κ4 ( d2 + log 3δ ) and B = E
x,y iid∼PD [(x − y)(x − y)>] (for some universal problem independent constants C1, C2 > 0). Then with probability at least (1− δ), for all stages s ∈ dlog T e at all rounds t > t0 and for all index pairs i, j ∈ Gs of round t: |(xti − xtj)>(θ∗ − θst ) ≤ pst (i, j)|. Theorem 5 (Regret bound of Stagewise-Adaptive-Duel (Alg. 3)). Consider we set t0 and η as per Lem. 4. Then for any δ > 0, with probability at least (1− δ), the regret of Alg. 3 can be bounded as:
RT ≤ t0 + 4η √ 2d log (4t0T
d
)√ T log T + 2 √ T = O (√ dT log T
κ
√ log (TK δ ) log (Td κ log 1 δ )) Proof. (sketch) Suppose we denote by φc := {t ∈ [T ] \ [t0] | t /∈ ∪blog Tcs=1 φ
s} the set of all good time intervals where all the index pairs pst (i, j) are estimated within the confidence accuracy 1√ T
. The proof crucially relies on the concentration bound of Lem. 4, from which we first derive:
Lemma 6. For any t > t0, suppose the pair (xt,yt) is chosen at stage st, and i∗t denotes the best action of round t, i.e. xti∗t = x ∗ t = arg maxx∈St x >θ∗. Then for any δ ∈ (0, 1), with probability at
least (1−δ), for all t > t0: i∗t ∈ Gst and for both x ∈ {xt,yt}, g(x∗t )−g(x) ≤
{ 2√ T
if t ∈ φc 4
2st otherwise .
Owning to Lem. 1 and due to the construction of our ‘stagewise-good item pairs’ we can also show: Lemma 7. At any stage s ∈ blog T c, with probability at least (1−δ), √ |φs| ≤ η2s √ 2d log ( 4t0T d ) .
The final regret bound can be derived combining the results of Lem. 6 and 7. (see Appendix E.5).

heading: 4 Lower Bound for Dueling (q = 2) Feedback
text: We now proceed to understand the fundamental performance limit of our contextual preference bandits problem for pairwise preference (q = 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 Ω( √ dT ).
Reducing Linear-Contextual Bandits to our framework. Let us instantiate any instance of our K-armed contextual dueling bandit problem by its problem parameter θ∗ ∈ Rd as Icdb(θ∗,K, T ). On the other hand define any instance ofK-armed contextual linear bandit problem [13] with problem parameter θ∗ ∈ Rd as Iclb(θ∗,K, T ): Recall in this setup, at each iteration the learner is provided with a context set St = {xt1,xt2, . . . ,xtK} ⊂ Rd of size K (as before ‖x‖2 ≤ 1, ∀x ∈ St), upon which the learner choose an arm xt ∈ St, and the environment feedbacks a reward r(xt) = x>t θ
∗+εt, where εt is a zero mean random noise. Objective is to minimize the regret with respect to the best action, x∗t := arg maxx∈St x >θ∗, of each round t, defined as: RclbT := ∑T t=1 ( x∗>t θ ∗ − x>t θ ∗),
Main Idea. For proving a lower bound for Icdb(θ∗,K, T ), we first show under Gumbel noise [9, 34], any instance of contextual linear bandits Iclb can be reduced to an instance of Icdb. Lemma 8 (Reducing Iclb with Gumbel noise to Icdb). There exists a reduction from the Iclb problem (under Gumbel noise, i.e. εt iid∼ Gumbel(0, 1)) to Icdb which preserves the expected regret.
Proof. (sketch) Suppose we have a blackbox algorithm for the instance of Icdb problem, say Acdb. To prove the claim, our goal is to show that this can be used to solve the Iclb problem where the underlying stochastic noise, t at round t, is generated from a Gumbel(0, 1) distribution [39, 9]. Precisely we can construct an algorithm for Iclb(θ∗,K, T ) (say Aclb) using Acdb as follows:
Lemma 9. If Aclb rums on a problem instance Iclb(θ∗,K, 2T ) with Gumbel(0, 1) noise, then the internally the algorithm Acdb runs on a problem instance of Icdb(θ∗,K, T ).
The proof of the above lemma is given in Appendix F.2. Lem. 9 precisely shows a reduction of Iclb to Icdb. The claim of Lem. 9 now follows from the regret definitions of the Iclb and Icdb, precisely we can show for any fixed T , 2RcdbT = R clb 2T . Complete proof is deferred to Appendix F.1.
Our lower bound result now immediately follows as a implication of Thm. 10 and from the existing lower bound result of K-armed d-dimensional contextual linear bandits problem [13].
Theorem 10 (SPM(θ∗, d, 2): Regret Lower Bound). For any algorithm Acdb for the problem of linear-score based stochastic K-armed contextual dueling bandit of dimensional-d, there exists a sequence of d-dimensional context sets {xt1, . . .xtK}Tt=1 and a constant γ > 0 such that the regret incurred by Acdb on T rounds is at least Ω(γ2 √ 2dT ), i.e. RT (Acdb) ≥ γ2 √ 2dT , for any T ≥ d2.
5 Analysis for General Subsetwise Preference Feedback (any q ∈ [K]) We now extend our analysis to any general q-subsetwise feedback, where at round t the learner is permitted to play a subset Xt ⊆ St of size q ≥ 2, given a fixed q ≤ K (formal setup in Sec. 2.1). We first analyze the regret lower bound, which, somewhat surprisingly, turns out to be independent of q (Thm. 11). We also propose an algorithm following this. Proof details are given in Appendix G.

heading: 5.1 Regret Lower Bound
text: We first show that for any given q ≥ 2, there exists a problem instance where no learner can achieve a better learning rate than Ω( √ dT ). However the conclusions are much similar to the existing regret lower bounds for finiteK arm preference bandits for Plackett-Luce (PL) model [30, 33]. As described in Sec. 2.1, since our preference model can also be seen a special case of PL model, our results show even in the contextual framework, the learner can not attain a faster rate by playing larger subsets.
Theorem 11 (Regret Lower Bound (Subsetwise Preferences)). Given any q ≥ 2 and d > 1, for any algorithm A for the problem of stochastic K-armed d-dimensional linear contextual bandit with SPM(θ, d, q) feedback model, there exists a sequence of d-dimensional context sets {xt1, . . .xtK}Tt=1 and a choice of θ such that the regret incurred by A on T rounds is at least Ω( √ dT ).

heading: 5.2 Algorithm and Regret Guarantee
text: Given the above lower bound, the first thing to note is our Alg. 3, itself yields an optimal Õ( √ 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, 2, . . . , q. However, we here propose a general version of Alg. 3 which is also based on the idea of stagewise-elimination but can exploit subsetwise preferences for any general q ≥ 2; it works even if the learner is restricted to play only sets of size q. Moreover, even though for the worst case instances, a better regret guarantee is not possible (as shown in Thm. 11), it can exploit the problem structure when there is a sufficient ‘quality gap’ between items.
Main Ideas. The main idea is to exploit the subsetwise feedback using the idea of rank-breaking [21] 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 of 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. 4 (Appendix G.2). The challenging part, however, lies in its regret analysis which requires justifying the right concentration rates of θst , 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′D++ (Alg. 4)). Consider any δ > 0, and suppose we set the
parameters of Sta′D++ (Alg. 3) as η = 32κ √ 2 log 3qTKδ , and t0 = 2 ( C1 √ d+C2 √ log(2q/δ)
λmin(B)
)2 +
4Λ λmin(B) , where Λ, κ,B is as defined in Lem. 4. Then with probability at least (1− δ), the T round cumulative regret of Sta′D++ is at most O (√ dT log(T )
κ
√ log ( qTK δ ) log ( Td κ log q δ )) .

heading: 6 Experiments
text: This section gives empirical performances of our algorithms (Alg. 1 and 3) and compare them with some existing preference learning algorithms. The details of the algorithms are given below:
Algorithms. 1. MaxInP: Algorithm Maximum-Informative-Pair (Alg. 1 as described in Sec. 3.1). 2. Sta′D: Our proposed algorithm Stagewise-Adaptive-Duel (Alg. 1 as described in Sec. 3.2). 3 SS: Self-Sparring (independent beta priors on each arm) algorithm for multi-dueling bandits [37] 4. RUCB: The Relative Upper Confidence Bound algorithm for regret minimization in standard dueling bandits [46]. 5. DTS: Dueling-Thompson Sampling algorithm for best arm identification problem in bayesian dueling bandits [17]. In every experiment, the performances of the algorithms are measured in terms of cumulative regret (sec. 1), averaged across 50 runs, reported with standard deviation.
Constructing Problem Instances. The difficulty of the instances depends on the difference of scores of the best and second best arms, which, in the hindsight, is actually governed by the ‘worst case slope’ of the sigmoid function κ (see the dependency of κ in Thm. 3 or Thm. 5), and also by the underlying problem parameter θ∗ ∈ Rd. So we used 3 different linear score based problem instances based on 3 different characterizations of θ∗ ∈ Rd (with K arms and dimension d): 1. Easy h(d,K), 2. Extreme e(d,K), and 3. Intermediate m(d,K), by suitably adjusting the norm ‖θ∗‖2. Also in all settings, the d-dimensional feature vectors (of the arm set) are generated as random linear combination of each arm to be a 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. `2-norm upper bounded by 1).
Regret vs Time. For this experiment we fix d = 10 and K = 50. Fig. 2 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 pairwise-preferences.
Regret vs Context-size (K). We now compare the (averaged) final cumulative regret of each algorithm over varying context set size (K) over two different problem instances. For this experiment we fix d = 10 and T = 1500. From Fig. 3 note that again our algorithms superiorly outperforms the other baselines with DTS performing competitively. SS and RUCB performs very badly due to the same reason as explained for Fig 2. Interesting observation to make is that the performance of both our algorithms MaxInP and Sta′D is almost independent of K as also follows from their respective regret guarantees (see Thm. 3 and Thm. 5)–as long as d 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.
Regret vs Dimension (d). For this experiment we fix K = 80 and T = 1500. From Fig. 4 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 a multiplicative O( √ d) worse regret than latter (see Thm. 3, 5).
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 g(x) is not linear in x, see Sec. 2.1 for details). We use three different score functions for the non-linear setup.
Environments. We use thsese 3 functions as g(·): 1. Quadratic, 2. Six-Hump Camel and 3. Gold Stein. Quadratic is the reward function f(x) = x>Hx + x>w + c, where H ∈ [−1, 1]d×d,w ∈ [−1, 1]d and c ∈ [−1, 1] are randomly generated. The Six-Hump Camel and Gold Stein functions are as described in [17]. For all cases, we fix d = 3 and K = 50.
Algorithms. We use a 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 a 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 [37], and for DTS we now fit a GP model (instead of a linear model).
Fig. 5 shows our algorithms still outperform the rest in almost all the instances. This actually implies the generality of our algorithmic ideas which applies beyond linear-scores (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 [37].

heading: 7 Conclusion and Future Scopes
text: We consider the problem of regret minimization for contextual preference bandits for potentially infinite decision spaces. To the best of our knowledge, this is the first work to give optimal regret (up to logarithmic factors) Õ( √ dT ) algorithms along with a matching lower bound analysis. The problem of contextual preference bandits being a 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 on 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], or feedback graphs [4, 5] 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 a sufficient ‘quality gap’ between the items.

heading: Acknowledgment
text: 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 on basics of linear-bandits and towards developing Algorithm 1.

Review summaries:
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>).  The 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.  The 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).  Finally, the authors evaluate their algorithms empirically on some synthetic data sets, showing that they perform better than existing dueling algorithms for this setting. 

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. 

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.