# Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 24 Feb 2024.

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

- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Stochastic Linear Bandits with Hidden Low Rank Structure](https://mlsanity.com/paper/1901.09490/) (2019)
- [Low-rank Bandits with Latent Mixtures](https://mlsanity.com/paper/1609.01508/) (2016)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Matrix Estimation for Offline Reinforcement Learning with Low-Rank Structure](https://mlsanity.com/paper/2305.15621/) (2023)

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

- [The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure](https://mlsanity.com/paper/2410.21601/) (2024)
- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation](https://mlsanity.com/paper/2508.04444/) (2025)
- [Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity](https://mlsanity.com/paper/2605.20269/) (2026)
- [Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces](https://mlsanity.com/paper/2606.27917/) (2026)
- [Optimal Online Regret for Context-Lumpable Bandits](https://mlsanity.com/paper/2610.18258/) (2026)

## Abstract (arXiv)

We study contextual bandits with low-rank structure where, in each round, if the (context, arm) pair (i,j)∈ [m]× [n] is selected, the learner observes a noisy sample of the (i,j)-th entry of an unknown low-rank reward matrix. Successive contexts are generated randomly in an i.i.d. manner and are revealed to the learner. For such bandits, we present efficient algorithms for policy evaluation, best policy identification and regret minimization. For policy evaluation and best policy identification, we show that our algorithms are nearly minimax optimal. For instance, the number of samples required to return an varepsilon-optimal policy with probability at least 1-δ typically scales as r(m+n)over varepsilon2log(1/δ). Our regret minimization algorithm enjoys minimax guarantees typically scaling as r7/4(m+n)3/4√T, which improves over existing algorithms. All the proposed algorithms consist of two phases: they first leverage spectral methods to estimate the left and right singular subspaces of the low-rank reward matrix. We show that these estimates enjoy tight error guarantees in the two-to-infinity norm. This in turn allows us to reformulate our problems as a misspecified linear bandit problem with dimension roughly r(m+n) and misspecification controlled by the subspace recovery error, as well as to design the second phase of our algorithms efficiently.