# Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

arXiv: https://arxiv.org/abs/2106.04819 · HTML: https://mlsanity.com/paper/2106.04819/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 43 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 8 of 8)

- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [A geometric alternative to Nesterov's accelerated gradient descent](https://mlsanity.com/paper/1506.08187/) (2015)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Stochastic Online Shortest Path Routing: The Value of Feedback](https://mlsanity.com/paper/1309.7367/) (2013)

## Built on by (most cited first, 15 of 15)

- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)
- [Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods](https://mlsanity.com/paper/2405.14273/) (2024)
- [Learning from a Learning User for Optimal Recommendations](https://mlsanity.com/paper/2202.01879/) (2022)
- [Efficient Online Set-valued Classification with Bandit Feedback](https://mlsanity.com/paper/2405.04393/) (2024)
- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions](https://mlsanity.com/paper/2510.04455/) (2025)
- [Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs](https://mlsanity.com/paper/2607.22263/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)
- [Optimal and Efficient Online Inverse Optimization](https://mlsanity.com/paper/2610.08735/) (2026)

## Abstract (arXiv)

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.