# Linear Bandits in High Dimension and Recommendation Systems

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2013.

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

- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [Deciding What to Learn: A Rate-Distortion Approach](https://mlsanity.com/paper/2101.06197/) (2021)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Online Matching: A Real-time Bandit System for Large-scale Recommendations](https://mlsanity.com/paper/2307.15893/) (2023)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling](https://mlsanity.com/paper/2405.11204/) (2024)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)
- [Bayesian Non-stationary Linear Bandits for Large-Scale Recommender Systems](https://mlsanity.com/paper/2202.03167/) (2022)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Navigating Sparsities in High-Dimensional Linear Contextual Bandits](https://mlsanity.com/paper/2510.08435/) (2025)
- [PREFER: Personalized Review Summarization with Online Preference Learning](https://mlsanity.com/paper/2605.05911/) (2026)
- [Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits](https://mlsanity.com/paper/2609.28718/) (2026)
- [Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers](https://mlsanity.com/paper/2609.30321/) (2026)

## Abstract (arXiv)

A large number of online services provide automated recommendations to help users to navigate through a large collection of items. New items (products, videos, songs, advertisements) are suggested on the basis of the user's past history and --when available-- her demographic profile. Recommendations have to satisfy the dual goal of helping the user to explore the space of available items, while allowing the system to probe the user's preferences. We model this trade-off using linearly parametrized multi-armed bandits, propose a policy and prove upper and lower bounds on the cumulative "reward" that coincide up to constants in the data poor (high-dimensional) regime. Prior work on linear bandits has focused on the data rich (low-dimensional) regime and used cumulative "risk" as the figure of merit. For this data rich regime, we provide a simple modification for our policy that achieves near-optimal risk performance under more restrictive assumptions on the geometry of the problem. We test (a variation of) the scheme used for establishing achievability on the Netflix and MovieLens datasets and obtain good agreement with the qualitative predictions of the theory we develop.