Persistent candidate sets speed up linear bandit decision making
Accelerating Linear Bandits with Persistent Candidate Sets
Machine Learning
Summary
Choosing the best option among many possibilities can be slow when each choice needs to be scored every time. The authors of this paper created a method called Persistent Candidate LinUCB that keeps a smaller set of active options and only checks a few new ones each round, making the process faster. They show that this approach still learns well with only a small extra cost that doesn’t grow over time. Their experiments confirm it speeds up decision making without losing quality.
What this means in practice
- •For online recommendation teams: Accelerate product or content selection algorithms by limiting score computations to persistently promising candidates with occasional sampling of others.
- •For advertising platform developers: Reduce computational cost in real-time ad selection systems by maintaining a smaller active candidate set and sampling other ads to explore.
Authors
Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama
Abstract
Exhaustive optimistic scoring can make action selection costly in linear bandits with a large fixed set of $K$ actions, requiring $\mathcal{O}(K)$ score evaluations per round. We introduce Persistent Candidate LinUCB (\textsc{PC-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, \textsc{PC-LinUCB} reduces the number of score evaluations per round to $\mathcal{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 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an $Ω\left((K-k)/q\right)$ regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that \textsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.