Accelerating Linear Bandits with Persistent Candidate Sets

arXiv:2610.13407v1 Announce Type: new Abstract: 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 (extsc{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, extsc{PC-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 extsc{PC-LinUCB} substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

Source: arXiv cs.LG | 2026-10-12