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 m (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-plane 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) ,2)) 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 (xr, 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 [Reeg] 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 Rd, let gd-1 = {x E R2; [|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)-rer 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 (rrlllogd)--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-paneeeae 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 -rrvvvityy 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, l..., 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-exploration 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 556544005566220 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": "pPfYS9QUZe", "reviewer": "Reviewer_7k7P", "summary": "\nThis work studies a variant of contextual linear bandits, where for each episode the learner is presented with a set of possible actions, selects an action, incurs the loss, and observes the best action of the given action set instead of the loss function. The authors first relate the contextual recommendation problem to the low-regret cutting plane methods based on well-studied separation oracle methods, which have been developed to minimize the number of calls. The relationship is formally stated in Theorem 3.1.\n\nThen, with the help of strong separation oracles, the authors design algorithms which achieve O(d log T) and O(exp(d log d)) regret based on existing cutting-plane algorithm, where d is the number of dimensions and T is the number of episodes. \n\nBesides this contextual recommendation setting, the authors also consider the list contextual recommendation where the learner is allowed to recommend a bounded set of actions, and the local contextual recommendation where the feedback for each episode is a better action instead of the best action in the given action set. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "1. Contribution\n\nThe algorithm relies on specific geometric properties of the Steiner potential and the center-of-gravity such as that stated in Theorem 2.1. With the help of these properties and the algorithm of Liu et al. (2021), the authors proves that, by simply selecting the center-of-gravity of certain convex sets, one can achieve exp(O(d log d)) or O(d log T) regret for low-regret cutting plane problems. \n\nTo the best of my knowledge, the problem setups and the usage of geometric techniques are novel and realistic. On the other hand, the efficiently discretization of the curvature path is also new to me. \n\n2. Weaknesses\n\nThe results are purely theoretical and I wonder if the algorithms can be efficiently implemented. \n\n3. Writing Issues\n\nThe format of references seems incorrect. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is pure theoretical and does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "bUawknCoC9y", "reviewer": "Reviewer_1hLE", "summary": "Authors address a variant of a contextual linear bandit problem where the objective is to estimate the unknown d-dimension vector w* by only observing the identity of the best arm (from the context set X_t) after each round. The paper design algorithms for this problem that achieve regret O(d log T) and exp(O(d log d)) using novel cutting-plane algorithms. They also studied a variant that allowed to provide a list of several recommendations and give an algorithm with O(d2 log d) regret, list size being O(poly(d)).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper suggests a novel cutting-plane algorithm-based method to address the problem of contextual search problem. The problem formulation is novel and relevant and their proposed algorithms provide near-optimal bounds for the objective. \nIs not the exp(d) regret bound trivially follows as there can only be O(2^d) \"distinct X_ts\" possible? What happens if X_t's are generated stochastically from some underlying set distribution, instead of adversarially? Instead of the identity of the best arm, if a ranking over first m best arms (m < A) are revealed, how do you expect the regret bound to be scaled. Would the results if the potential class of X_ts are infinite / continuous (in other words, what is the notion of gap that shows up in the regret bounds)?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Satisfactory.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~3-4"}, "extra_text": {}}, {"review_id": "KOgbKq2TfmH", "reviewer": "Reviewer_oGv3", "summary": "This paper introduces the problem of low-regret cutting plane algorithms and studies its applications to contextual recommendations, which is also introduced in this paper. The low-regret cutting plane problem is similar to the standard cutting plane setting, but instead of bounding the number of iterations the goal is to bound the total regret. Specifically, we have a convex body $K_1$ and a hidden point $w^* \\in K_1$. In round $t\\geq 1$, we pick a point $p_t\\in K_t$, the adversary picks a direction $v_t$ such that $\\langle w^* - p_t, v_t\\rangle \\geq 0$, and the next convex body $K_{t+1}$ is defined as the intersection of $K_t$ with the halfspace $\\{x : \\langle x - p_t, v_t\\rangle \\geq 0\\}$. The goal is to minimize the total regret $\\sum\\limits_{t=1}^{T} \\langle w^* - p_t, v_t\\rangle$. In the convextual recommendation problem, there is again a hidden point $w^*$ (corresponding e.g. to some unknown user preferences). In each step $t$, the goal is to pick some $x_t$ from a set of possible actions $\\mathcal{X}_t$ (e.g. set of all paths in route planning). Then, we pay $\\langle x_t^* - x_t, w^* \\rangle$, where $x_t^*$ is the optimal action and subsequently get to learn $x_t^*$. This is different from other known settings where the feedback is instead the value of the regret, i.e. $\\langle x_t^* - x_t, w^* \\rangle$.\n\nThe main results are:\n* An $exp(O(d\\log d))$-regret cutting plane algorithm\n* An $O(d\\log T)$-regret cutting plane algorithm\n* An $O(\\mathrm{poly}(d))$-regret cutting plane algorithm if the adversarial direction $v_t$ does not depend on the point $p_t$ chosen.\n\nThe first two immediately transfer to the contextual recommendation problem, and the third one can be translated to an algorithm for a weaker variant of contextual recommendation where there are $\\mathrm{poly}(d)$ recommendations instead of $1$.\n\nThe algorithms are based on convex geometry, and the techniques include the Steiner potential and a new characterization of the centroid of $K+rB$ (i.e. all points within distance $r$ from $K$) as a function of $r$.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the fact that the authors define the low regret cutting plane problem in an abstract way, as this might help attract some attention to the problem and motivate further connections to other problems. The idea of bounding the length of the centroid curve is nice and new, to the best of my knowledge, and it takes another step into showing how useful Steiner polynomials are for these types of problems. The first two low-regret cutting plane algorithms are more standard, and their techniques follow more naturally from previous work. In particular, these (especially the $O(d\\log T)$ bound) seem quite similar to (and maybe even recoverable by) [supp 20]. It would be useful if the authors could clarify if this is not the case. Even so, the authors' approach of dealing with the parametric convex body $K+rB$ seems slightly cleaner. More generally, it would be good to clarify how contextual recommendations and contextual search are different, in terms of the techniques used in them. I have the following comments:\n\n* I would be interested in getting more thorough motivation behind the contextual recommendation problem. In particular, the fact that it is assumed that the user will pick the _optimal_ action seems somewhat less natural to me than the setting where the user can pick any action that is at least as good as the suggestions. Unfortunately, the bounds for the latter depend linearly on the ratio $|\\mathcal{X}_t| / (\\text{number of suggestions} - 1)$, which seems impractical ($\\mathcal{X}_t$ could be very large, e.g. the total number of paths in a graph). \n* Related to the previous point, it would be useful to have some experiments of the proposed algorithms on real data, as the problem of contextual recommendations is very practically motivated. In particular, this might show that the bounds for the latter (more realistic) setting from the previous bullet are too pessimistic, which would be interesting.\n* There is something off in the paragraph starting in line 314. If we incur loss $w\\approx d r$, and this happens $O(d\\log (2/r))$ times, then the total loss should at \nbest be $O(d^2)$ and not $O(d\\log d)$.\n\nI think the main significance of this work is formalizing the low-regret cutting plane algorithms, and introducing the centroid curve in the context of cutting plane algorithms.\n\nSome typos (from the supplementary):\n* Line 82: What is K?\n* Line 168: Minkowsi\n* Lines 231-232: doesn’t make sense\n* Line 419: The quantity right after this line is negative\n* It seems to be implied that K_1 = B, but I couldn't find where it was stated\n* Line 463: I think it should be (2T)^d", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "* No numerical experiments", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "7W-GyJNo_2", "reviewer": "Reviewer_77iV", "summary": "In the contextual recommendation (CR) problem, the agent receives in each round the best arm given the contextual, which is contrasted to the standard online learning procedure where a reward is usually observed. To tackle the problem, this paper explores the connections between CR and the cutting-plane algorithms, which aims to locate a hidden point by iterative hyperplanes. The main theorem in the paper states that a $O(\\tho)$-regret CR algorithm can be constructed from a $O(\\rho)$-regret cutting-edge algorithm. The paper further proposes two variants of algorithms that achieve low regrets. Furthermore, the paper tackles other variants of the CR problem and presents algorithms with guaranteed regrets. In general, this paper is a theoretical paper. I think the theorems and the algorithms can be important to the field.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Although the paper aims mainly on the theoretical side, adding empirical verifications can be more convincing and illustrative.\n\nQuestion: when the separation oracle is weak, i.e., the direction is chosen before the agent makes the choices, the resulting regret is worse (Theorem 5.2) than Theorem 3.1. Why a weaker oracle leads to a more difficult problem?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not Applicable", "review_text": "", "extra_scores": {"ethical_concerns": "Not Applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the problem of contextual recommendation, a variant of the linear contextual bandit algorithm in which a learner selects actions based on context in order to maximize reward, but rather observing the reward, observe the identity of the optimal action instead. The reviewers found that the results are novel and technically interesting, and in particular thought that formalizing the problem of regret for cutting plane algorithms and connecting this to contextual recommendation was valuable, and is likely to find further use. Overall, this is a solid contribution (albeit, slightly niche for the NeurIPS community). The authors are encouraged to incorporate the reviewers' suggestions and spend more time motivating the problem, as well as discussing practical aspects of their algorithms (e.g., implementation).
Decision: Accept (Poster)