Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Authors: Sreenivas Gollapudi
Guru Guruganesh
Kostas Kollias
Pasin Manurangsi
Renato Paes Leme
Jon Schneider
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Learning
Convex Geometry
Separation Oracles
Linear Bandits
Contextual Bandits

Abstract: We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines  and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.

We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns. 

We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest. 

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, and
Jon Schneider
Google Research
Abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden d-dimensional value w". Every round, we are presented with a subset X S R of possible actions. If we choose (i.c. recommend to the user) action æt, we obtain utility (Iz, w²) but only learn the identity of the best action arg max (z, w*).
We design algorithms for this problem which achieve regret O(d T) and exp(O(d d)). To accomplish this, we design novel cutting-plane algorithms with low "regret" the total distance between the true point w* and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide list of several recommendations In this variant, we give an algorithm with Od log d) regret and list size poly(d). Finally, we construct nearly tight algorithms for weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques variant of Steiner's formula for the centroid of a convex set) which may be of independent interest.
in convex geometry (including a
Introduction
Consider the following problem faced by geographical query service (e.g. Google Maps). When a user searches for path between two endpoints, the service must return one route out of a set of possible routes. Each route has multidimensional set of features associated with it, such as (i) travel time, (ii) amount of traffic, (iii) how many turns it has, (iv) total distance, etc. The service must recommend one route the user, but doesn't It a priori know how the user values these features relative to one another. However, when the service recommends route, the service can observe some feedback from the user: whether or the user followed the recommended route (and if not, which route the user ended up taking), How can the service use this feedback to learn the user's preferences over time?
Similar problems are faced by recommendation systems in general, where every round a user arrives accompanied by some contextual information (e.g. their current search query, recent activity, etc.), the system makes a recommendation to the user, and the system can observe the eventual action (e.g. be viewed specific cases of
the purchase of specific item) by the user. These problems variant of linear contextual bandits that we term contextual recommendation.
In contextual recommendation, there is hidden vector w" I& (c.g. representing the values of the user for different features) that is unknown to the learner. Every round t (for T' rounds), the learner is presented with adversarially chosen (and potentially very large) set of possible actions X, Each
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

element He of Ne is also an element of R (visible to the learner); playing action 24 results in the learner receiving a reward of (z,, w*). The learner wishes to incur low regret compared to the best possible strategy in hindsight - i.e. the learner wishes to minimize
Reg= -TE ((z7, w²) (ae, w²))
(1)
where 2; = arg e (z, w²) is the best possible action at time t. In our geographical query example, this regret corresponds to the difference between the utility of a user that always blindly follows our recommendation and the utility of a user that always chooses the optimal route.
Thus far this agrees with the usual set-up for contextual linear bandits (see e.g. [4]). Where contextual recommendation differs from this is in the feedback available to the learner: whereas classically in contextual linear bandits the learner learns (a possibly noisy version of) the reward they receive each round, in contextual recommendation the learner instead learns the identity of the best arm x². This altered feedback makes it difficult apply existing algorithms for linear contextual bandits. In particular, algorithms like LINUCB and LIN-Rel [1, 4] all require estimates of (It, w²) in order to learn n over time, and our feedback prevents us from obtaining any such absolute estimates.
In this paper we design low-regret algorithms for this problem. We present two algorithms for this problem: one with regret Odd log T') and one with regret exp(O(d log d)) (Theorems 4.1 and 4.2). Note that both regret guarantees are independent of the number of offered actions | (the latter even being independent of the time horizon T). Moreover both of these algorithms implementable given an efficient procedure for optimizing a linear function over the sets X. This condition holds e.g. in the example of recommending shortest paths that we discussed earlier.
efficiently
In addition to this, we consider two natural extensions of contextual recommendation where the learner is allowed to recommend a bounded subset of actions instead of just single action (as is often the case in practice). In the first variant, which we call list contextual recommendation, each round the learner recommends set of at most L (for some fixed L) actions to the learner. The learner still observes the user's best action each round, but the loss of the learner is now the difference between the utility of the best action for the user and the best action offered by the learner (capturing the difference in utility between a user playing an optimal action and a user that always chooses the best action the learner offers).
In list contextual recommendation, the learner has the power to cover multiple different user prefer- ences simultaneously (e.g. presenting the user with the best route for various different measures). We show how to use this power to construct an algorithm for the learner which offers poly (d) actions each round and obtain total regret of poly(d).
In the second variant, we relax an assumption of both previous models: that the user will always choose their best possible action (and hence that we will observe their best possible action). To relax this assumption, we also consider the following weaker version of contextual recommendation we call local contextual recommendation.
In this problem, the learner again recommends set of at most L actions the learner (for some L >> !). The user then chooses an action which is at least as good as the best action in our list, and observe this action. In other words, we assume the learner at least looks at all the options
offer, so if they choose an external option, it must be better than any offered option (but not necessarily the global optimum). Our regret in this case is the difference between the total utility of a learner that always follows the best recommendation in our list and the total utility of a learner that always plays their optimal action?.
Let A = max, [eel be a bound on the total number of actions offered in any round, and let y A/(L- 1). We construct algorithms for local contextual recommendation with regret O(yd T)
and (x log d)). We further show that the first bound is "nearly tight" (up to poly(d) (d)
factors) in some regimes; in particular, we demonstrate an instance where T. = 2 and K = 20())
Unlike in the previous two variants, it is important in local contextual recommendation that L > 1; if L = 1 then the user can simply report the action the learner recommended and the learner receives no meaningful feedback.
"I fact, our algorithms all work for a slightly stronger notion of regret, where the benchmark is the utility of a learner that always follows the first (i.e. a specifically chosen) recommendation on our list. With this notion of regret, contextual recommendation reduces to local contextual recommendation with L max (X)].

---

where any algorithm must incur regret at least min (((T)) The results for local contextual recommendation are included in the Supplementary Material.
1.1 Low-regret cutting plane methods and contextual search
To design these low-regret algorithms, we reduce the problem of contextual recommendation to a geometric online learning problem (potentially of independent interest). We present two different (but equivalent) viewpoints on this problem: one motivated by designing separation--rrale-based algorithms for convex optimization, and the other by contextual search.
1.1.1 Separation oracles and cutting-plane methods
Separation oracle methods (or "cutting-plane methods") are an incredibly well-studied class of algorithms for linear and convex optimization. For our purposes, it will be convenient describe cutting-plane methods as follows.
Let B = (w E Rdd || < 1} be the unit ball in Rd, We are searching for hidden point w² E B. Every round we can choose a point Pt E and submit this point to a separation oracle. The separation oracle then returns half-space separating pr from w"; in particular, the oracle returns direction 2Y such that (w", 02) 2 (pt, Ut).
separtth
Traditionally. cutting- plane algorithms have been developed to minimize the number of calls to the separation oracle until the oracle returns hyperplane that passes within some distance of w², For example, the ellipsoid method (which always queries the center of the cureenty-maintained maintained ellipse) has the guarantee that makes at most (d² log 1/8) oracle queries before finding such a hyperplane.
In our setting, instead of trying to minimize the number of separation oracle queries before finding "close" hyperplane, we would like minimize the total (over all rounds) distance between the returned hyperplanes and the hidden point w². That is, we would like to minimize the expression
Reg's = Σi= ((w", vz) (pr, vz))
(2)
Due to the similarity between (2) and (1), call this quantity the regret of a cutting- plane algorithm. We show that, given any low-regret cutting-plas plane algorithm, there exists low-regret algorithm for contextual recommendation.
Theorem 1.1 (Restatement of Theorem 3.1). Given a low-regret cutting- algorithm A with regret p. we can construct an Op)-rrrr algorithm for contextual recommendation.
This poses a natural question: what regret bounds are possible for cutting-plan methods? One might expect guarantees existing cutting-plane algorithms to transfer over to regret bounds, but interestingly, this does not appear to be the case. In particular, most existing cutting-plat and analysis suffers from the following drawback: even if the method is likely to find hyperplane within distance ó relatively quickly, there is no guarantee that subsequent calls to the oracle will return low-regret hyperplanes.
methods
In this paper, we will show how to design low-regret cutting-pland methods. Although our final algorithms will bear some resemblance existing cutting through the center-of-gne -f-giavtty of some convex set), our analysis will instead build off more recent work on the problem of contextual search.
plane algorithms (e.g. some involve cutting
1.1.2 Contextual search
Contextual search is an online learning problem initially motivated by applications in pricing [6]. The basic form of contextual search can be described as follows. As with the previously mentioned problems, there is a hidden vector w" E [o, 1]d that we wish to learn over time. Every round the adversary provides the learner with vector (the "context"). In response, the learner must guess the value of (Mt, w*), submitting a guess yt- The learner then incurs a loss of (0t, w*) yel (the distance between their guess and the true value of the inner product), but only learns whether (v,, w²) is larger or smaller than their guess.
The problem of designing low-regret cutting plane methods can be interpreted as "context-free" variant of contextual search. In this variant, the learner no longer provided the context v, at the beginning of each round, and instead of guessing the value of (vt, w"), they are told to directly
3

---

submit a guess Pt for the point w". The context 2t is then revealed to them after they submit their guess, where they are then told whether (pe, wn) ) is larger or smaller than (et, w²) and incur loss (1,, =²) - (Pt: w²) [- Note that this directly corresponds to querying separation oracle with the point Pt, and the separation oracle returning either the halfspace t/ (in the case that (w=, ve) 2 (w", ,P:) or the halfspace -y (in the case that (w", v2) S {w", .P))).
One advantage of this formulation is that (unlike in standard analyses of cutting-plain methods) the total loss in contextual search directly matches the expression in (2) for the regret of a cutting-plane method. In fact, were there to already exist an algorithm for contextual search which operated in the above manner guessing (Vg, w²) by first approximating w" and then computing the inner product we could just apply this algorithm verbatim and get cutting-plan method with the same regret bound. Unfortunately, both the algorithms of [7] and [6] explicitly require knowledge of the direction et-
This formulation also raises an interesting subtlety in the power of the separation oracle: specifically, whether the direction U, fixed (up to sign) ahead of time or is allowed depend on the point Specifically, we consider two different classes of separation oracles. For (strong) separation oracles, the direction v, is allowed freely depend on the point Pt (as long as is indeed true that (w,,"r) .u)) 2 (Pe, v.)). For weak separation oracles, the adversary fixes direction Vy at the beginning of the round, and then returns either 2, = u or 2/2 -u, (depending on the sign of (w" - Pt. uz)). The strong variant is most natural when comparing to standard separation oracle guarantees (and necessary for the reduction in Theorem 1.1), but for many standalone applications (especially those motivated by contextual search) the weak variant suffices. In addition, the same techniques we use to construct outting-plane algorithm for weak separation oracles will let us design low-regret algorithms for list contextual recommendation.
1.2 Our results and techniques
We design the following low-regret cutting-plane algorithms:
1. An (sp(O(d rregret cutting-plane algorithm for strong separation oracles.
2. An Old -regret cutting- plann algorithm for strong separation oracles.
3. An ((poly(d)): rregret cutting-plane algorithm for weak separation oracles.
All three algorithms are efficiently implementable (in poly(d, T) time). Through Theorem 1.1, points (1) and (2) immediately imply the algorithms with regret cx)(O(d)) and Odd 7') for contextual recommendation. Although we do not have a blackbox reduction from weak separation oracles to algorithms for list contextual recommendation, we show how apply the same ideas in the algorithm in point (3) to construct an (d2 log re-rrtt algorithm for list contextual recommendation with L == (dly
To understand how these algorithms work, it is useful to have a high-level understanding of the algorithm of [7] for contextual search. That algorithm relies on a multiscale potential function the authors call the Steiner potential. The Steiner potential scale r is given by the expression Vol(K, + where K2 (the "knowledge set") is the current set of possibilities for the hidden point w", B is the unit ball, and addition denotes Minkowsi sum; in other words, this is the volume of the set of points within distance of K,. The authors show that by choosing their guess y/ carefully, they can decrease the r-alle Steiner potential (for some r roughly proportional to the width of K, in the current direction vx) by constant factor. In particular, they show that this is achieved by choosing y/ so to divide the expanded set K2 rB exactly in half by volume. Since the Steiner potential at scale r is bounded below by Vol(rB), this allows the authors to bound the total number of mistakes at this scale. (A more detailed description of this algorithm is provided in Section 2.2).
In the separation oracle setting, we do not know ahead of time, and thus cannot implement this algorithm as written. For example, we cannot guarantee our hyperplane splits K, + rB exactly in half. We partially work around this by using (approximate variants of) Grunbaum's 's theorem, which guarantees that any hyperplane through the center-of-gravity of a convex set splits that convex set into two pieces of roughly comparable volume. In other words, everywhere where the contextual search algorithm divides the volume of K, + rB in half, Grunbaum's theorem implies we obtain comparable results by choosing any hyperplane passing through the of of K; + rB.

---

Unfortunately, we still cannot quite implement this in the separation oracle setting, since the choice of in the contextual search algorithm depends on the input vector 2, Nonetheless, by modifying the analysis of contextual search we can still get some guarantees via simple methods of this form. In particular we show that always querying the center-of -ggravity of K2 (alternatively, the center of the John ellipsoid of K2) results in an exp(O log ) )regret cutting-plane algorithm, and that always querying the center of gravity of K; + +B results in an O(d (") -regret cutting-plae paating-planeeeee algorithm.
Our cutting-plane algorithm for weak separation oracles requires a more nuanced understanding of the family of sets of the form K; + rB. This family of sets has a number of surprising algebraic properties. One such property (famous in convex geometry and used extensively in earlier algorithms for contextual search) Steiner's formula, which states that for any convex K. Vol( K + rB) is actually a polynomial in r with nonnegative coefficients, These coefficients are called intrinsic volunes and capture various geometric measures of the set K (including the volume and surface area of K).
There exists lesser-known analogue of Steiner's formula for the center-of-gravity of K + rB, which states that each coordinate of cg K + +B) is a rational function of degree at most d: in other words, the curve cg(K + rB) for r E [0, o0) is a rational curve. Moreover, this variant of Steiner's formula states that each point cg K + rB) can be written as a convex combination of d - 1 points contained within K known as the curvature centroids of K. Motivated by this, we call the curve Px (r) = cg(K + rB) the curvature path of K.
Since the curvature path pk is both bounded in algebraic degree and bounded in space (having to lie within the convex hull of the curvature centers), we can bound the total length of the curvature path PK by a polynomial in d (since it is bounded in degree, each component function of pæ can switch from increasing to decreasing a bounded number of times). This means that we can discretize the curvature path to within precision while only using poly(d)/s points on the path.
Our algorithms against weak separation oracles and for list contextual recommendation both make extensive of such discretization. For example, we show that in order to construct low-regret algorithm against a weak separation oracle, it suffices to discretize Pk, into O(d*) points and then query a random point; with probability at least O(d +), we will closely enough approximate the point p(r) = cg( K + rB) that our ahove analogue of contextual search would have queried. We show this results in poly(d) total regret'. A similar strategy works for list contextual recommendation: there we discretize the curvature path for the knowledge set K2 into poly(d) candidate values for w", and then submit our set of actions the best response for each of these candidates.
Related work
We include survey of related work in the Supplementary Material.
2 Model and preliminaries
We begin by briefly reviewing the problems of contextual recommendation and designing lew-regret cutting plane algorithms. In all of the below problems, B = {w E Rd ||/]]| S 1] is the ball of radius I (and generally, all vectors we consider will be bounded to lie in this ball).
Contextual recommendation. In contextual recommendation there is a hidden point w² B. Each round t (for T rounds) we are given a set of possible actions X; S B. If we choose action Jr E Xx we obtain reward (Iiz, w*) (but do not learn this value). Our feedback is 2; = arg max (Ir, w²), the identity of the best action'. Our goal is to minimize the total expected regret [[Re]] = E (x - _., Note that since the feedback is deterministic, this expectation only over the randomness of the learner's algorithm.
will be useful to establish some additional notation for discussing algorithms for contextual recommendation. We define the knowledge set K, to be the set of possible values for w" given the knowledge we have obtained by round 1. Note that the knowledge set K, is always convex, since the feedback we receive each round (that (wri, w²) 2 (xt, w²) for all x E X,) can be written as an
2 'The reason this type of algorithm does not work against strong separation oracles that each point this discretization could return a different direction n, in turn corresponding to different value of 'If this argmax is multi-valued, the adversary may arbitrarily return any element of this argmax.
5

---

intersection of several halfspaces (and the initial knowledge set K₁ = B is convex). In fact, we can say more.
Given a w E K2, let (w) = arg za (ar, w) be the set of optimal actions in 2 if the hidden point was w. Then: K2+1 {w E K, E (w)()).
We also consider two other variants of contextual recommendation in this paper (list contextual recommendation and local contextual recommendation). A formal definition can be found in Sections 5 and the full version in the supplementary materials.
Designing low-regret cutting-plane algorithms. In a low-regret sutting-plane algorithm, we again have a hidden point w' E B. Each round t (for T' rounds) we can query separation oracle with point in B. The separation oracle then provides us with an adversarially chosen direction U (with ||ee|| = 1) that satisfies (w" vx) 2 (pr, 04)- The regret in round is equal to (w" Pt, Ut), and our goal is to minimize the total expected regret [Regg] E Ei=
(w" Pt, (x) Again, since the
feedback is deterministic, the expectation is only over the randomness of the learner's 's algorithm.
As with contextual recommendation, it will be useful to consider the knowledge set K2, consisting of possibilities for w" which are still feasible by the beginning of round f. Again as with contextual recommendation, K, is always convex; here intersect K2 with the halfspace provided by the separation oracle every round (i.e. Ke+1 = K, n {(w Pt, vt) 2 0}).
Unless otherwise specified, the separation oracle can arbitrarily choose v, as a function of the query point pr. For obtaining low-regret algorithms for list contextual recommendation, it will be useful to consider variant of this problem where the separation oracle must commit to o2 (up sign) at the beginning of round f. Specifically, at the beginning of round t (before observing the query point Pt), the oracle fixes a direction u4 Then, on query Pt. the separation oracle returns the direction 2t = Ue if (w Pt, Ue) 2 0, and the direction 8/2 = -u otherwise. We call such a separation oracle weak separation oracle; an algorithm that only works against such separation oracles is a low-regret cutting-plane -plane algorithm for weak separation oracles. Note that this distinction only matters when the learner is using randomized algorithm; if the learner is deterministic, the adversary can predict all the directions 2G in advance.
2.1 Convex geometry preliminaries and notation
We will denote by Conv. the collection of all convex bodies in Rd, Given convex body K E Conva- we will use Vol(K) Jx 1dæ to denote its volume (the standard Lebesgue measure). Given two sets K and L in Rd, their Minkowski sum is given by K + L = fo + y: x E K, E L}. Let B denote the unit ball in Rdd let gd-1 = {x E R4; [|e||| = }} denote the unit sphere in Rd and let Ky = (Bd( be the volume of the i-th dimensional unit ball. When clear from context, we will omit the superscripts on 2d and Sd-1
We will write cg( cg(K) (sx xdx) 1dx) to denote the center of gravity (alternatively, centroid) of K. Given a direction u E gd-1 and convex set K E Conva we define the width of K in the direction as: width (; u) max (u, x) minzek (0, (,,
Approximate Grunbaum and John's Theorem Finally, we state two fundamental theorems in convex geometry. Grunbaum's 's Theorem bounds the volume of the convex set in each side of hyperplane passing through the centroid. For our purposes will be also important to bound a cut that passes near, but not exactly at the centroid. The bound given in the following paragraph comes from a direct combination of Lemma B.4 and Lemma B.5 in Bubeck et al. [3].
We will use the notation (p) = {x (xr, u) = (p, u)} to denote the halfspace passing through with normal vector u. Similarly, we let H (p) {x (z, u) 2 (p, u)}.
Theorem 2.1 (Approximate Grunbaum [2, 3J). Let K E Conva.
cg(K) and u E gd-1, Then consider the semi-space H+ = fx E Rd: (u, <) 2 t} for some t E R4. Then:
Vol(KnH Vol(K)
2)(-11 wi
John's theorem shows that for any convex set K E Conva, we can find an ellipsoid E. contained in K such that K is contained in (some translate of) dilation of E by factor of d.

---

Theorem 2.2 (John's Theorem). Given K E Conva, there is point E K and an invertible linear transformation A : F + IR' such that q + S A(K) S q + dB. We call the ellipsoid E = (1 + B) the John ellipsoid of K.
2.2 Contextual search
In this section, we briefly sketch the algorithm and analysis of [7] for the standard contextual search problem. We will never use this algorithm directly, but many pieces of the analysis will prove useful our constructions of low-regret cutting-plane plane algorithms.
Recall that in contextual search, each round the learner is given a direction er. The learner is trying learn the location of hidden point w", and at time has narrowed down the possibilities of wt to a knowledge set K₁- The algorithm of [7] runs the following steps: 1. Compute the width w = width Ke; vz) of K₁ in the direction
2. Let r = 2[l((w110d] (rounding w/ 10d to a nearby power of two). 3. Consider the set K = K2 + rB. Choose ye so that the hyperplane H = / (u,, w) = yr divides the set K into two pieces of equal volume.
We understand this algorithm follows. Classic cutting-plann methods try to decrease (K,) ) by a constant factor every round (arguing that this decrease can only happen so often before one of hyperplanes passes within some small distance our feasible region). The above algorithm can be thought as a multi-scale variant of this approach: they show that if we incur loss w z dr in a round (since loss in round is most the width), the potential function Vol(K, + rB) must decrease by constant factor. Since Vol(K, - rB) 2 Vol(rB) = r" Kg, Odd (2g(())))) times. Summing over all possible discretized values of (i.e. powers of 2 less than 1), we arrive at an (d log d) regret bound.
incur loss of this size most
3 From Cutting-Plane Algorithms to Contextual Recommendation
We begin by proving reduction from designing low-regret cutting plane algorithms to contextual recommendation. Specifically, we will show that given a regret p cutting-plan plane algorithm, we can use it to construct (rp)-rrr algorithm for contextual recommendation.
Note that while these two problems are similar many ways (e.g. they both involve searching for an unknown point w"), they are not completely identical. Among other things, the formulation of regret although similar is qualitatively different between the two problems (i.e. between expressions (1) and (2)). In particular, in contextual recommendation. the regret each round is (x) Iz, w²), whereas for cutting-pl planng-pleeneeee algorithms, the regret given by (w* Pt, vt). Nonetheless, we will able to relate these two notions of regret by considering separation oracle that always returns halfspace in the direction of x Itt-
Theorem 3.1. Given a low-regret cutting-plane algorithm A with regret Ps we can construct an Op))rrrgeet algorithm for contextual recommendation.
The reduction in Theorem 3.1 is efficient long as we have efficient method for optimizing linear function over Xr (i.e. for computing (w.).. In particular, this means that this reduction can be practical even in settings where X, may be combinatorially large (e.g. the set of s-t paths in some graph).
Note also that this reduction does not work if A is only low-regret against weak separation oracles. This is since the direction v, we choose does depend non-trivially on the point pt (in particular, in the reduction we choose 2, E (R, Later in Section 5.3, we will see how to use ideas from designing cutting-plant methods for weak separation oracles to construct low-regret algorithms for list contextual recommendation however we do not have black-box reduction in that case, and our construction will be more involved.
4 Designing Low-Regret Cutting-Plane Algorithms
In this section we will describe how to construct low-regret cutting-plane algorithms for strong separation oracles.
7

---

4.1 An exp(O(d (rrlllodd)--eeeeee cutting-plane algorithm
We begin by showing that always querying the center of the John ellipsoid of K, leads to exp(O(d log rr)-ret cutting-plane algorithm. Interestingly, although this corresponds to the classical ellipsoid algorithm, our analysis proceeds along the lines of the analysis of the contextual search algorithm summarized in Section 2.2. In particular, we show that for each round I, there's s some r (roughly proportional to the current width) where Vol(K, +r decreases by multiplicative factor of (1 - d d- Doing so allows us to prove the following theorem.
Theorem 4.1. The cutting- planne algorithm which always queries the center of the John ellipsoid of K₁ incurs (xp(O(d log d)) regret.
The remaining algorithms we study will generally query the center-of-gravity of some convex set, as opposed to the center of the John ellipsoid. This leads to the following natural question: what is the regret of the cutting-plan algorithm which always queries the center-of-gravity of K,?
Kannan, Lovasz, and Simonovits (Theorem 4.1 of [5]) show that it is possible to choose an ellipsoid E satisfying E _ K S dE such that centered cg( [)), so our proof Theorem 4. shows that this algorithm is also an exp exp(O(d log d)) algorithm. However, for both this algorithm and the ellipsoid algorithm of Theorem 4.1, we have no non-trivial lower bound on the regret. It is an interesting open question to understand what regret these algorithms actually obtain (for example, do either of these algorithms achieve poly(d) regret?).
4.2 An Odd 7) rregrtt cutting-plane algorithm
We will now show how to obtain O log -regret cutting plane algorithm. Our algorithm will simply query the center-of -f-ravvitt of K, + 7B each round. The advantage of doing this is that we only need to examine one scale of the contextual search potential (namely the value of Vol(K, + B)). By doing this, we prove that the above algorithm achieves (d T') regret.
Theorem 4.2. The cutting ppanngg-paaeeeae algorithm which queries the point pr = cg (Ke + BB) incurs Od T) regret.
List contextual recommendation, weak separation oracles, and the curvature path
In this section, we present two algorithms: 1. poly(d) expected regret cutting -laane algorithm for weak separation oracles, and an (dd log d) regret algorithm for list contextual recommendation with list size I, = (d)y
The unifying feature of both algorithms is that they both involve analyzing a geometric object we call the curvature path of a convex body. The curvature path of K is a bounded-degree rational curve contained within K that connects the center-of-grawe -ravviityy cg( ()) with the Steiner point (limy cg(K* K rB)) of K.
In Section 5.1 we formally define the curvature path and demonstrate how to bound its length. In Section 5.2, we show that randomly querying a point on a discretization the curvature path leads to (dly regret outting-plane algorithm for weak separation oracles. Finally, in Section 5.1, show how to transform a discretization of the curvature path of the knowledge set into a list of actions for list contextual recommendation, obtaining low regret algorithm.
5.1 The curvature path
An important fact (driving some of the recent results in contextual search, e.g. [6]) is the fact that the volume Vol(K + rB) is d-dimensional polynomial in r. This fact known as the Steiner formula:
Vol(K +rB) Ed= (a-(
After normalization by the volume of the unit ball, the coefficients of this polynomial correspond to the intrinsic volumes of K. The intrinsic volumes are a family of d functionals V;- Conv, - R,+ for i 0, 1, d that associate for each convex K Conv, non-negative value. Some of these
8

---

functionals have natural interpretations: Va(K) is the standard volume Vol(K). (K- is the surface area, Vi (K) is the average width and (K( is whenever K non-empty and 0 otherwise.
There is an analogue of the Steiner formula for the centroid of K + rB, showing that it admits description vector-valued rational function. More precisely, there exist d + functions Conva + R for 0 I i S d such that:
cg K + rB) = Ei (K-))))))))) Eimo Va-i(K)ear'
(4)
The point (K) E K corresponds to usual centroid cg cg(K) and (x) corresponds to the Steiner point. The functionals are called curvature centroids since they can be computing by integrating certain curvature measures associated with a convex body (a la Gauss Bouus-BBnnne).... We refer to Section 5.4 in Schneider [8] for more thorough discussion discussion. For our purposes, however, the only important fact will be that each curvature centroid e₁ (K) is guaranteed to lie within K (note that this not all obvious from their definition).
Motivated by this, given a convex body K IRd we define its curvature path be the following curve in R
pk : [0, 00] + K
(x(r) = cg(K +
The path connects the centroid pk (0) cg(K) to the Steiner point pk (xc) Our main result will
exploit the fact that the coordinates of the curvature path are rational functions of bounded degree to produce discretization.
Lemma 5.1. Given K E Conva and discretization parameter k, there exists set D {po. Pl, PP.....PP. C K such that for every r there is a point ps E D such that:
(r)(r) Pt. u)l S 4d -iith(( u), Yu gd-1
5.2 Low-regret cutting-plane algorithms for weak separation oracles
In this section we use the discretization of the curvature path Lemma 5.1 to construct a poly(d) regret outting-plane algorithm that works against weak separation oracle. Recall that weak separation oracle is a separation oracle that fixes the direction of the output hyperplane in advance (up sign). That at the beginning of round / the oracle fixes some direction v2 E gd-1 and returns either vs or - Ut to the learner depending on the learner's s choice of query point q:-
Theorem 5.2. The cutting-pla plann algorithu which chooses a random point from the discretization of the curvature path of K2 into d' pieces achieves a total regret of Odd log" d) against any weak separation oracle.
5.3
List contextual recommendation
In this section, we consider the problem of list contextual recommendation. In this variant of contextual recommendation, we are allowed to offer list of possible actions L, S X, and we measure regret against the best action in the list: loss, (w", xτ) maxxEL, (w",ar x)).
Our main result is that if the list is allowed to be of size (dd) then it is possible to achieve total regret (d2 log d).
The recommended list of actions will be computed as follows: given the knowledge set Ke, let D be the discretization of the curvature path with parameter k 200d obtained in Lemma 5.1. Then for each p; E D find an arbitrary x; E <B((p)) == arg max (pi, x) and let Le = { .2,,..,
Theorem 5.3. There exists an algorithm which plays the list L, defined above and incurs total regret of at most O(d o log d).

---

References
[1] Peter Auer. Using confidence bounds for exploitation-expllration trade-offs. Journal of Machine Learning Research, 3(Nov):397 422, 2002.
[2] Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM (JACM), 51(4):540 556544005556220 2004.
[3] Sébastien Bubeck, Bo' az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1496-1508. SIAM, 2020.
[4] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214 4. JMLR Workshop and Conference Proceedings, 2011.
[5] Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry, 13(3):541-55, 1995.
[6] Renato Paes Leme and Jon Schneider. Contextual search via intrinsic volumes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 268-282. IEEE, 2018.
[7] Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1059-1078. SIAM, 2021.
[8] Rolf Schneider. Convex bodies: the Shun--Minkosste theory. Number 151. Cambridge university press, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
10

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "sIWEwf_EKr", "reviewer": "Reviewer_51YE", "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. \nVarious regret bounds are provided in the case of strong and weak separation oracles.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, 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. \n\nPros:\n(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. \n(B) The contextual list recommendation problem is solved under a weak separation oracle setting and also shown to regret independent of T. \n\nCons/Questions:\n\n(1) The lack of experimental results on the intended applications in recommender systems weakens the strong contributions. \n(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? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YxVLVGpsLFw", "reviewer": "Reviewer_Wg9U", "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.\n\nThe 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$. \n\nThe 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.\n\nFor 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))$.\n\nIn 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.\n\nFor the list contextual recommendation problem, the paper gives an algorithm with $L=O(d^4)$ with expected regret $O(d^2 \\log d)$.\n\nThe 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$.\n\nThe 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.\n\nThe algorithm for the list contextual recommendation problem is based on an algorithm this paper gives for a variant of the separation oracle problem.", "questions": "", "limitations": "", "rating": 8, "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": "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.\n\nOriginality: The context recommendation problem and all the algorithms are original.\n\nQuality: I haven't checked the proof details, but the overall proof outline seems robust to me.\n\nClarity: The paper is generally well-written. Some minor corrections are needed here and there. I have included some below.\n\nSignificance: 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.\n\nMinor comments:\n- 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.\n\n- 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.\n\n- Lines 130 to 134: there is a serious repeating typo here. Many of the $w^*$s must be $v_t$s.\n\n- In the title, I think the word recommendation should appear singular.\n\n- Line 7: regret -> regrets\n\n- Line 28 and throughout: \"in\" every round a user arrives\n\n- 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.\n\n- Line 29: delete \"etc.\"\n\n- Line 33: delete \"e.g.\"\n\n- Line 48: and -> but. \n\n- Line 48: Delete \"absolute\"\n\n- Line 49 and 50: you basically repeat a sentence.\n\n- Line 52: even being independent of the time horizon T -> is independent of the time horizon T\n\n- Line 58: fixed L -> given L. To some, \"fixed\" means constant.\n\n- Line 66: obtain -> obtains\n\n- Line 71: the learner -> the user\n\n- 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.\n\n- Line 73: delete \"at least\"\n\n- Line 77: their -> the\n\n- Line 79: regret -> regrets\n\n- Line 81: demonstrate -> present\n\n- Line 81: What is K?\n\n- Line 88: the other \"one\"\n\n- Line 122: why has the domain changed from the unit ball to [0,1]^d ? This is confusing.\n\n- Line 128 and 129: The learner changes from singular to plural in the middle of the sentence.\n\n- Line 131: where -> when\n\n- Line 133 and 134: halfspace -> unit vector\n\n- 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$?)\n\n- Line 137: \"were there to exist ...\" very complicated sentence structure. I recommend using a simpler structure: \"if there already existed an algorithm...\"\n\n- Line 140: delete \"explicitly\"\n\n- Line 144: $p$ -> $p_t$\n\n- Line 145: delete \"freely\"\n\n- Line 161: delete \"algorithms for\" (reductions are between problems rather than between algorithms)\n\n- Line 172: delete \"so\"\n\n- Line 179: everywhere where -> whenever\n\n- Line 179: delete roughly\n\n- Line 184: it's not clear what is meant by \"simple methods of this form.\"\n\n- Line 196: cg is undefined\n\n- Line 196: rational function \"of r\" of degree at most d\n\n- Line 197: what is a \"rational curve\" ?\n\n- Line 198: delete \"each point\"\n\n- Line 199: $\\rho_K(r)$ is a \"function,\" but here you're talking about a \"curve\" in $R^d$. Please make this clear.\n\n- Lines 201 to 205: I didn't really understand this paragraph. \n\n- Line 216: delete briefly\n\n- Line 216: problems -> problem\n\n- Line 225: this sentence is not necessary.\n\n- 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.\n\n- 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?\n\n- Line 245: it should be $\\{w : \\langle w - p_t , v_t \\rangle \\geq 0\\}$\n\n- Line 261: $i$-th -> $d$\n\n- Line 267: in -> on\n\n- In Theorem 2.1, semi-space -> half-space\n\n- In Theorem 276, should $A$ be a positive definite linear transformation? Otherwise, $E$ won't be an ellipsoid.\n\n- Line 285: lg is undefined.\n\n- Line 305: halfspace -> unit vector\n\n- Line 314: we choose -> the oracle chooses\n\n- Line 317: you need a comma after however, otherwise it can be misread.\n\n- Line 374: measures -> measure\n\n- Line 374: what is \"a la\" ?\n\n- Line 375: \"discussion\" is repeated", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations have been written clearly.", "review_text": "", "extra_scores": {"ethical_concerns": "None that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2ilr6wvX27b", "reviewer": "Reviewer_7jBU", "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.", "questions": "", "limitations": "", "rating": 3, "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": "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? \n\nRelated 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.\n\nIt seems to me that the proof of the theorem is just an application of the existing contextual search results. \n\nThe lack of numerical experiments and application of real-world data does not negate the fact that the problem setting is pathological.\n\nThe methods/ideas using the cutting plane based algorithm and its theoretical analysis look solid and interesting.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is not fully discussed (e.g., comparison with the existing studies).", "review_text": "", "extra_scores": {"ethical_concerns": "There are none.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

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)