# Accelerating Linear Bandits with Persistent Candidate Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 9 Oct 2026.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [DOCKSTRING: easy molecular docking yields better benchmarks for ligand design](https://mlsanity.com/paper/2110.15486/) (2021)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Sample Efficient Demonstration Selection for In-Context Learning](https://mlsanity.com/paper/2506.08607/) (2025)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces](https://mlsanity.com/paper/2510.19349/) (2025)

## Abstract (arXiv)

Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of K actions, requiring O(K) score evaluations per round. We introduce Persistent Candidate LinUCB (textscPC-LinUCB), which maintains k active actions and samples q challengers uniformly from the remaining K-k actions at each round. By scoring only these k+q candidates, textscPC-LinUCB reduces the number of score evaluations per round to O(k+q). We establish problem-independent and problem-dependent high-probability regret bounds consisting of a standard linear-bandit learning term and an additive discovery cost of order Oleft((K-k)log(K-k)/qright) at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an Omegaleft((K-k)/qright) regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that textscPC-LinUCB substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.