Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors formulate a novel variant of the contextual linear bandit problem where the feedback is the identity of the best arm instead of the output of the reward function. This leads to a harder optimization problem which is a reduced to a geometric online problem which the paper solves uses separation based oracle algorithms. They also show the connection to the recently considered contextual search problem. 
Various regret bounds are provided in the case of strong and weak separation oracles.
main_review: Overall, the paper is well-structured in presenting the problem and the proposed contributions. The problem is novel and would be of broad interest to the community and the geometric problem could be of interest to other machine learning models. 

Pros:
(A) The connection to the regret problem in cutting-plane methods is nice and then showing how it can solved by John ellipsoid queries and center of gravity of queries in general settings is nice. These lead to efficient algorithms in terms of T. 
(B) The contextual list recommendation problem is solved under a weak separation oracle setting and also shown to regret independent of T. 

Cons/Questions:

(1) The lack of experimental results on the intended applications in recommender systems weakens the strong contributions. 
(2) How resistant is the proposed algorithm to noisy feedback in terms of the identity of the best arm? Suppose it is corrupted in say 's' of the T rounds, would it still be able to recover? 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The authors considered a variant of the Regret minimization problem in the Adversarial Linear contextual bandit problem. For each action x_t is chosen, a reward of <x_t, w^*> is received, but this reward is not observed. Instead, the identity of the best arm x_t^* can be observed. The authors further Considered the problem of presenting a list whose size is at most L, instead of recommending a single item. The authors proposed a cutting-plane-based algorithm with regret guarantees. The algorithm is inspired by the recent results of contextual search.
main_review: The problem setup looks a little odd to me. If we could observe the best action every time without noise, we would surely find the best action if we could do the whole search (no need to consider exploration-exploitation trade off). If we happened to observe a non-best action once due to an error, will we suffer a very large regret? Also, the setting where the action set is chosen as adversarial seems strange. For example, is there a service in the real world where a very difficult action set is forced on the user every time? 

Related work is not discussed/compared satisfactorily. (See e.g., Abbasi-Yadkori et al. 2011, Bastani, Hamsa, Mohsen Bayati, and Khashayar Khosravi. "Mostly exploration-free algorithms for contextual bandits." Management Science, 2021). The diverse principle (around line 63) required for the list recommendation has been discussed in the field of learning to rank for many years. The authors should complete a survey and comparison with those results.

It seems to me that the proof of the theorem is just an application of the existing contextual search results. 

The lack of numerical experiments and application of real-world data does not negate the fact that the problem setting is pathological.

The methods/ideas using the cutting plane based algorithm and its theoretical analysis look solid and interesting.

limitations_and_societal_impact: It is not fully discussed (e.g., comparison with the existing studies).
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper defines and gives low-regret algorithms for two online learning problems using ideas from convex geometry. The problems are the contextual recommendation problem and the list contextual recommendation problem.

The contextual recommendation problem is similar to the adversarial linear bandit problem; the only difference is the feedback the learner receives. Suppose there exists an unknown $d$-dimensional vector $w^*$ in the unit ball. In each round $t=1,2,\dots,T$, the learner is given a set of actions to choose from, say $X_t$. Suppose the learner chooses action $x_t$, and suppose $x^*_t$ is the vector in $X_t$ that has the largest dot product with $w^*$. Then the learner incurs regret $\langle x^*_t, w^* \rangle - \langle x_t, w^* \rangle$ but does not observe $\langle x_t, w^* \rangle$; instead, the learner observes $x^*_t$. 

The problem is motivated by recommendation systems: $w^*$ is the preference-vector of a given user, $X_t$ is the set of possible products/items to choose from in round $t$, and $x^*_t$ is the actual product this user prefers. After giving a recommendation, the system only observes what product the user chose.

For the contextual recommendation problem, the paper gives two algorithms: one with regret $O(d \log T)$ and one with regret $\exp(O(d \log d))$.

In the list contextual recommendation problem, the learner can choose a subset of size $L$ of the set of actions $X_t$. The round-$t$ regret equals the difference between the value of the best action in $X_t$ and the value of the best action in the list. So, the case $L=1$ corresponds to the contextual recommendation problem, and the case $L=\max_t |X_t|$ achieves zero regret.

For the list contextual recommendation problem, the paper gives an algorithm with $L=O(d^4)$ with expected regret $O(d^2 \log d)$.

The algorithms for both problems are based on new algorithms for the "separation oracle" problem. In this problem, there exists an unknown d-dimensional vector $w^*$ in the unit ball. In each round $t=1,2,\dots,T$, the learner chooses a vector $p_t$ as a "guess" for $w^*$ and receives a separating hyperplane, i.e., receives a unit vector $v_t$ such that $\langle w^* , v_t \rangle \geq \langle p_t, v_t \rangle$, and incurs regret $\langle w^* , v_t \rangle - \langle p_t, v_t \rangle$.

The paper gives a black-box reduction from the contextual recommendation problem to the separation oracle problem, and then give a low-regret algorithm for the latter problem using ideas from convex geometry.

The algorithm for the list contextual recommendation problem is based on an algorithm this paper gives for a variant of the separation oracle problem.
main_review: I think this is a good paper. The problems are well-motivated and also interesting from a mathematical point of view. The algorithms use non-trivial ideas from convex geometry. I haven't verified the proofs though; they appear in the supplementary material.

Originality: The context recommendation problem and all the algorithms are original.

Quality: I haven't checked the proof details, but the overall proof outline seems robust to me.

Clarity: The paper is generally well-written. Some minor corrections are needed here and there. I have included some below.

Significance: The paper is written for theoretical machine learning community and would excite them. Perhaps those working in recommendation system may also use ideas from the paper, although I don't know how the algorithm would work in practice. Because the setting of the paper is quite general, it is likely to find applications in other domains as well.

Minor comments:
- There is some confusion about regret vs. expected regret. For the first few pages, it seems that regret is deterministic. Later, it turns out that the regret is random, and some of the bounds are regarding the expected regret. This needs to be clarified sooner. That is, in line 66 we should already know that you are talking about the expected regret.

- Line 80: I'm not sure if "up to poly(d) factors" can be considered "nearly tight." Usually, this phrase is reserved for polylog factors.

- Lines 130 to 134: there is a serious repeating typo here. Many of the $w^*$s must be $v_t$s.

- In the title, I think the word recommendation should appear singular.

- Line 7: regret -> regrets

- Line 28 and throughout: "in" every round a user arrives

- Line 28: The vector $w^*$ is specific to each user. So, this is a situation where a single user interacts with the system over $T$ rounds. In the current version, it seems that there could be different users. Please fix this.

- Line 29: delete "etc."

- Line 33: delete "e.g."

- Line 48: and -> but. 

- Line 48: Delete "absolute"

- Line 49 and 50: you basically repeat a sentence.

- Line 52: even being independent of the time horizon T -> is independent of the time horizon T

- Line 58: fixed L -> given L. To some, "fixed" means constant.

- Line 66: obtain -> obtains

- Line 71: the learner -> the user

- Lines 71 -- 77: in this paragraph, we first refer to the learner as the third person. Then suddenly the learner is the first person. Also, the user, the learner, and the adversary are conflated in this paragraph. Please rewrite. I would suggest to refer to all of them as third person, as is done in the rest of the paper.

- Line 73: delete "at least"

- Line 77: their -> the

- Line 79: regret -> regrets

- Line 81: demonstrate -> present

- Line 81: What is K?

- Line 88: the other "one"

- Line 122: why has the domain changed from the unit ball to [0,1]^d ? This is confusing.

- Line 128 and 129: The learner changes from singular to plural in the middle of the sentence.

- Line 131: where -> when

- Line 133 and 134: halfspace -> unit vector

- Line 134: This inequality must be strict (the question is what happens if the dot products are equal---does the oracle returns $v_t$ or $-v_t$?)

- Line 137: "were there to exist ..." very complicated sentence structure. I recommend using a simpler structure: "if there already existed an algorithm..."

- Line 140: delete "explicitly"

- Line 144: $p$ -> $p_t$

- Line 145: delete "freely"

- Line 161: delete "algorithms for" (reductions are between problems rather than between algorithms)

- Line 172: delete "so"

- Line 179: everywhere where -> whenever

- Line 179: delete roughly

- Line 184: it's not clear what is meant by "simple methods of this form."

- Line 196: cg is undefined

- Line 196: rational function "of r" of degree at most d

- Line 197: what is a "rational curve" ?

- Line 198: delete "each point"

- Line 199: $\rho_K(r)$ is a "function," but here you're talking about a "curve" in $R^d$. Please make this clear.

- Lines 201 to 205: I didn't really understand this paragraph. 

- Line 216: delete briefly

- Line 216: problems -> problem

- Line 225: this sentence is not necessary.

- Line 227: "by round t" means by the end of round t or by the beginning of round t? Line 243 says "by the beginning" but it should be clarified earlier.

- Lines 231 and 232: what is the role of these two lines? They seem to be repeating what was explained before. I understand that BR is used again in lines 310 and 315. But there is a long distance between where it was defined and where it was used. Can you make them closer?

- Line 245: it should be $\{w : \langle w - p_t , v_t \rangle \geq 0\}$

- Line 261: $i$-th -> $d$

- Line 267: in -> on

- In Theorem 2.1, semi-space -> half-space

- In Theorem 276, should $A$ be a positive definite linear transformation? Otherwise, $E$ won't be an ellipsoid.

- Line 285: lg is undefined.

- Line 305: halfspace -> unit vector

- Line 314: we choose -> the oracle chooses

- Line 317: you need a comma after however, otherwise it can be misread.

- Line 374: measures -> measure

- Line 374: what is "a la" ?

- Line 375: "discussion" is repeated
limitations_and_societal_impact: I think the limitations have been written clearly.
review_title: null

Meta-review: This paper studies a new online learning problem called contextual recommendation, where similar to the full-information online classification problem, at each time step, the learner is asked to take an action, and then the optimal action at that time step is revealed; different from the classification setup, here the learner suffers a linear loss as opposed to a zero-one loss.

On the positive side: 
- The paper proposes new algorithms with O(d log T) and O( exp(d log d) ) regret; and in a variant of the model called list recommendation, it gives an algorithm with O(d^2 log d) regret with each iteration proposing a list of size O(d^4). The theoretical analysis looks solid and interesting to the reviewers.

On the negative side:
- The problem setup is very similar to full-information online linear classification in the single-vector model. The single-vector model can be used to handle a time-varying number of available classes, and the semantics of classes from round to round can be completely different. In addition, the single-vector model can capture the noisy setting, whereas the paper's formulation hasn't been extended to that yet. So the motivation of studying the new contextual recommendation model needs further justification. 

- If we view the contextual recommendation in the lens of full-information online linear classification problem, then we immediately have the corollary that when the first and the second largest reward has a gap \gamma at each round, then a naive center-of-gravity algorithm has regret O(d \log 1/\gamma). When \gamma is say, \Omega(1/d^10), the algorithm has O(d \log d) regret, which is already quite good. The reviewers and the AC acknowledged that this paper can achieve new regret guarantees that are completely independent of \gamma (e.g., for infinite action set setting), however the significance of this result is in question. 

- No experimental results are presented.

In summary, this is a good paper, but is at the borderline of acceptance bar. The model and solution proposed have some values, however comparison with prior models needs to be done more comprehensively, and this paper might be more appropriate for a theoretical CS conference such as SODA.

Minor comment: it may not be appropriate to call this paper a linear contextual bandits paper - the feedback model here is action independent - this has caused some confusion from the reviewers and the AC.
Decision: Accept (Poster)