Accelerating Linear Bandits with Persistent Candidate Sets

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.