Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

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 Xt subseteq ℝd of possible actions. If we choose (i.e. recommend to the user) action xt, we obtain utility langle xt, w^* rangle but only learn the identity of the best action argmaxx ∈ Xt langle x, w^* rangle. We design algorithms for this problem which achieve regret O(dlog 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(d2 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.