# Linear Bandit Algorithms with Sublinear Time Complexity

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 55 references that are in the map.
- First posted on arXiv 3 Mar 2021.

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

- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Sampled Softmax with Random Fourier Features](https://mlsanity.com/paper/1907.10747/) (2019)
- [Quantization based Fast Inner Product Search](https://mlsanity.com/paper/1509.01469/) (2015)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Stochastic Multi-armed Bandits in Constant Space](https://mlsanity.com/paper/1712.09007/) (2017)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Scalable and Sustainable Deep Learning via Randomized Hashing](https://mlsanity.com/paper/1602.08194/) (2016)
- [A Greedy Approach for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1610.03317/) (2016)
- [Norm-Ranging LSH for Maximum Inner Product Search](https://mlsanity.com/paper/1809.08782/) (2018)
- [Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing](https://mlsanity.com/paper/1507.04299/) (2015)
- [Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space](https://mlsanity.com/paper/1911.03034/) (2019)

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

- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Artefact Retrieval: Overview of NLP Models with Knowledge Base Access](https://mlsanity.com/paper/2201.09651/) (2022)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

We propose two linear bandits algorithms with per-step complexity sublinear in the number of arms K. The algorithms are designed for applications where the arm set is extremely large and slowly changing. Our key realization is that choosing an arm reduces to a maximum inner product search (MIPS) problem, which can be solved approximately without breaking regret guarantees. Existing approximate MIPS solvers run in sublinear time. We extend those solvers and present theoretical guarantees for online learning problems, where adaptivity (i.e., a later step depends on the feedback in previous steps) becomes a unique challenge. We then explicitly characterize the tradeoff between the per-step complexity and regret. For sufficiently large K, our algorithms have sublinear per-step complexity and tilde O(√T) regret. Empirically, we evaluate our proposed algorithms in a synthetic environment and a real-world online movie recommendation problem. Our proposed algorithms can deliver a more than 72 times speedup compared to the linear time baselines while retaining similar regret.