Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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>).

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. 
main_review: 
I 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. 

One 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. 

limitations_and_societal_impact: No concerns here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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.

The 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. 
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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$.

Main comments on the clarity, quality, and significance:

1) 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.

2) 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...)

3) 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$.

3) 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.

4) Minor comments on writing: The writing can be largely improved. Besides the comments above - 

a) Line 182, Lemma 1, there is a ")" missing after $y_2$.

b) Line 283, "attend" -> "attain".

c) Line 360, Remark 2: "algorithms still outperforms" -> "algorithms still outperform others"

d) Line 344, (q) should be boldfaced.

e) Figure 2 caption is covered by Figure 4.

f) Figure 3 caption: "Set size (K)" -> "Context-size (K)"?
limitations_and_societal_impact: See comments on limitations above. There is no immediate societal impact.
review_title: null

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)