# Low-rank Bandits with Latent Mixtures

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2016.

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

- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Tractable Optimality in Episodic Latent MABs](https://mlsanity.com/paper/2210.03528/) (2022)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs](https://mlsanity.com/paper/2310.09358/) (2023)

## Abstract (arXiv)

We study the task of maximizing rewards from recommending items (actions) to users sequentially interacting with a recommender system. Users are modeled as latent mixtures of C many representative user classes, where each class specifies a mean reward profile across actions. Both the user features (mixture distribution over classes) and the item features (mean reward vector per class) are unknown a priori. The user identity is the only contextual information available to the learner while interacting. This induces a low-rank structure on the matrix of expected rewards r a,b from recommending item a to user b. The problem reduces to the well-known linear bandit when either user or item-side features are perfectly known. In the setting where each user, with its stochastically sampled taste profile, interacts only for a small number of sessions, we develop a bandit algorithm for the two-sided uncertainty. It combines the Robust Tensor Power Method of Anandkumar et al. (2014b) with the OFUL linear bandit algorithm of Abbasi-Yadkori et al. (2011). We provide the first rigorous regret analysis of this combination, showing that its regret after T user interactions is tilde O(C√BT), with B the number of users. An ingredient towards this result is a novel robustness property of OFUL, of independent interest.