Accelerating Linear Bandits with Persistent Candidate Sets

arXiv:2610.13407 · cs.LG · Submitted 2026-10-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Accelerating Linear Bandits with Persistent Candidate Sets".

Jane: The gist: Persistent Candidate LinUCB accelerates Linear Bandits by maintaining a set of active actions and sampling challengers from the remaining set,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, let's talk about the core concept behind this paper. The title "Accelerating Linear Bandits with Persistent Candidate Sets" suggests they are focusing on speeding up the learning process by managing which actions we score.

Jane: Exactly. It’s not just about finding a better way to calculate the reward; it’s about fundamentally changing how much data we need to collect to get a good answer when K is huge. The authors introduce PC-LinUCB, which uses these persistent candidates and those sampled challengers to achieve that acceleration.

Lu: The mechanism hinges on combining the standard UCB scores with this persistent candidate set, but there's a specific way they update those scores using clipped values. This clipping ensures that the scores only go down, which is important for how we track optimism over time.

Meng: So, if an action’s score drops below a certain threshold because it hasn't been evaluated recently or isn't in the active set, it stays there until something happens. That sounds like a way to manage our computational budget more intelligently than just checking everything every time.

Lalam: It’s about maintaining a persistent set of potentially good actions and using the challengers to keep that set fresh, ensuring we don't completely forget on promising candidates while still being able to explore new ones.

The paper's summary: Tom: The summary points out two main things they establish. First, they get problem-independent regret bounds, meaning the cost to learn isn't tied to the specific structure of our rewards or features. That’s hard to achieve in bandit problems.

Jane: And second, they have problem-dependent bounds too, which involves a term dependent on some minimum gap between mean rewards. This shows they can account for how much difference there is between the best action and the others in our specific problem context.

Lu: The core of their analysis is separating the standard learning cost from an additive discovery cost, which is O ((K minus k) log (K minus k)/q) at fixed confidence. This means that even with this partial access, we still have a predictable cost associated with finding the best action.

Meng: That additive term is what I'm most concerned about for deployment. The paper says that this discovery cost doesn't grow as the horizon gets longer, which is good because we don't need to plan for infinite time just to keep finding new things.

Lalam: They also provide a lower bound under uniform challenger sampling showing an unavoidable regret cost of order Omega ((K minus k)/q) when q is small relative to K minus k. This means simply having partial access imposes a minimum cost on our learning process.

The paper's improvements: Tom: So, what’s the actual mechanism they propose that makes this faster? The key improvement is using clipped scores to guide both action selection and candidate retention simultaneously. It’s a dual purpose update rule.

Jane: That clipping is crucial because it means each candidate’s score only decreases or stays the same, while still respecting the standard confidence event. This keeps the optimism in check but lets us keep track of what's still plausible without needing to re-evaluate everything.

Lu: They use a specific formula involving a regularization parameter lambda greater than zero to define those optimistic scores using an ellipsoidal confidence construction from OFUL, which gives them the formal mathematical backing they need for this method.

Meng: From a practical deployment view, it means we can set k and q strategically. If we need low latency updates, we probably want k plus q to be small enough that the scoring is fast enough to keep up with our real-time needs.

Lalam: They tune parameters by increasing q to search the inactive set more quickly and increasing k to retain more promising actions, balancing exploration and exploitation in a way that seems quite efficient empirically.

Conclusion: Tom: So, to wrap up, PC-LinUCB offers a way to manage the cost of scoring in linear bandits by reducing it from O(K) down to O(k plus q). The results show they get strong regret bounds and prove that the discovery cost doesn't grow with time.

Jane: It seems like they’ve found a solid way to handle large action spaces without having to exhaustively score every single option in every single round. They provide rigorous guarantees on performance even when we only look at a subset of actions.

Lu: The persistence and the challenger sampling mechanism are clever because they ensure that even actions outside our current set still get a chance to enter the candidate pool, which is important for long-term exploration.

Meng: For production, this means we can build systems that are computationally lighter while maintaining comparable performance to exhaustive methods, provided we're okay with the additive discovery cost term.

Lalam: This paper on Accelerating Linear Bandits with Persistent Candidate Sets provides a concrete framework for dealing with large action sets in linear bandit problems by balancing persistent candidates and challenger sampling effectively.

Bingkui Tong, Daria Korovaitceva, Marina Sheshukova, Sergey Samsonov, Junpei Komiyama

Mohamed bin Zayed University of Artificial Intelligence · HSE University 3RIKEN AIP

cs.LG

Submitted: 2026-10-09

Updated: 2026-10-09

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist: Persistent Candidate LinUCB accelerates Linear Bandits by maintaining a set of active actions and sampling challengers from the remaining set, reducing score evaluations to O(k + q) while

Key concepts

Persistent Candidate LinUCB (PC-LinUCB): This algorithm keeps track of a small set ($k$) of promising actions and samples new challengers ($q$) uniformly from the remaining actions at every round. It uses clipped scores to decide which candidates to keep, ensuring only the most relevant actions are scored, drastically cutting down evaluations compared to checking every action.
Score Evaluation Cost Reduction: Standard LinUCB requires scoring all $K$ actions per round, leading to $\mathcal{O}(Kd^2)$ cost. PC-LinUCB reduces this by only scoring the $k+q$ active candidates. This makes the algorithm much faster when the total number of actions $K$ is large, as it avoids unnecessary computations.
Regret Decomposition: The analysis separates regret into two parts: a standard learning term and an additive discovery cost. The discovery cost, $\mathcal{O}((K-k)\log(K-k)/q)$, represents the unavoidable time spent exploring actions that might be optimal, even with partial access. This cost does not grow with the horizon at fixed confidence.
Access-Induced Regret Lower Bound: This lower bound proves that simply having partial access to candidates imposes a minimum regret cost of order $\Omega((K-k)/q)$ when $q$ is small relative to the remaining actions. This shows that reducing evaluations is not free; there is always a fundamental cost associated with only sampling a subset of possible actions.

Summary

The gist: Persistent Candidate LinUCB accelerates Linear Bandits by maintaining a set of active actions and sampling challengers from the remaining set, reducing score evaluations to O(k + q) while establishing regret bounds that separate learning costs from partial access costs.

Introduction and Problem Formulation

Bandit algorithms are used for sequential decision making under uncertainty to find the action with the largest expected reward The central challenge is balancing exploration of uncertain actions with exploitation of actions that appear promising. In linear bandits, direct implementations of LinUCB require O(Kd2) scoring cost per round. Existing work focuses on reducing the cost of scoring each action or reducing the number of actions that need to be evaluated. This work focuses on reducing the number of actions evaluated, proposing Persistent Candidate LinUCB (PC-LinUCB), which combines a persistent candidate set with UCB scores.

Persistent Candidate LinUCB Mechanism

The PC-LinUCB algorithm maintains an active set of k actions and samples q challengers uniformly from the remaining K − k actions at each round. A key innovation is the use of clipped scores to guide both action selection and candidate retention, where each candidate’s score is updated to the minimum of its previous value and the newly evaluated LinUCB score. The action with the largest clipped score is selected, and the k candidates with the largest clipped scores form the next active set. This process reduces the number of score evaluations per round from K to k + q, substantially lowering the cost when k + q ≪ K.

Regret Analysis

The analysis establishes problem-independent and problem-dependent regret upper bounds that separate the standard linear-bandit learning term from an additive discovery cost of order O((K − k) log(K − k)/q) at fixed confidence. This additive cost captures the time required for random challengers to expose an action that remains plausible for optimality and does not grow with the horizon at fixed confidence. Furthermore, a regret lower bound under uniform challenger sampling is established, showing that partial candidate access itself imposes an unavoidable regret cost of order Ω((K − k)/q) when q ≪ K − k.

Tradeoffs and Applications

The analysis shows that the additive term does not grow with the horizon at fixed confidence. Theorem 1 provides a problem-independent bound, while Theorem 2 provides a problem-dependent bound that includes a term dependent on ∆min, the minimum positive gap between mean rewards. The access-induced regret lower bound shows that uniform partial access alone imposes an expected regret cost of order Ω((K − k)/q) for fixed ∆ and sufficiently long horizons. Empirical results demonstrate that PC-LinUCB substantially reduces computation while maintaining comparable regret, and the persistent candidate mechanism can extend beyond LinUCB through an application to SpectralUCB.

Experimental Results

Experiments compare PC-LinUCB with five baselines on controlled synthetic problems and four large action sets derived from real data. The results show substantial reductions in end-to-end wall-clock time with regret comparable to exhaustive LinUCB, alongside distinct time–regret tradeoffs for methods based on infrequent switching, matrix compression, and elimination. Ablation experiments examine the total scoring budget and its allocation between persistent actions and random challengers. The application to SpectralUCB further shows that the persistent candidate mechanism can also serve as an efficient action-selection mechanism beyond LinUCB.

Limitations

The method relies on a fixed action set with fixed features, allowing clipped scores and persistent candidates to remain valid across rounds. It does not directly extend to contextual bandits, where changing actions or features can invalidate previously stored scores and candidates. The analysis assumes that at least one action is suboptimal to define ∆min.

AI Use Statement

We used AI tools to assist with code development, experiment execution and visualization, as well as language polishing of the manuscript. AI tools were also used to review the theoretical arguments for potential errors. In particular, an earlier version of Lemma 6 and its proof was incorrect, and GPT-6 Pro assisted in identifying the issue and developing the corrected proof presented in this paper. All AI-assisted outputs, including experimental code and theoretical arguments, were reviewed and verified by the authors.

References

Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312–2320.

Bayati, M., Hamidi, N., Johari, R., and Khosravi, K. (2020). Unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms. In Advances in Neural Information Processing Systems, volume 33, pages 1713–1723.

Chen, C., Luo, L., Zhang, W., Yu, Y., and Lian, Y. (2020). Efficient and robust high-dimensional linear contextual bandits. In Proceedings of the TwentyNinth International Joint Conference on Artificial Intelligence, pages 4259–4265.

Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory, pages 355–366.

García-Ortegón, M., Simm, G. N. C., Tripp, A. J., Hernández-Lobato, J. M., Bender, A., and Bacallado, S. (2022). DOCKSTRING: Easy molecular docking yields better benchmarks for ligand design. Journal of Chemical Information and Modeling, 62(15):3486–3502.

Hanna, O., Yang, L., and Fragouli, C. (2023). Efficient batched algorithm for contextual linear bandits with large action space via soft elimination. In Advances in Neural Information Processing Systems, volume 36.

Harper, F. M. and Konstan, J. A. (2015). The MovieLens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 5(4):19:1–19:19.

Jun, K.-S., Bhargava, A., Nowak, R., and Willett, R. (2017). Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems, volume 30, pages 99–109.

Kuzborskij, I., Cella, L., and Cesa-Bianchi, N. (2019). Efficient linear bandits through matrix sketching. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 177–185 PMLR.

Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22.

Lattimore, T., Szepesvári, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in RL with a generative model. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5662–5670 PMLR.

Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pages 661–670 ACM.

Paredes, E. and Ballester-Ripoll, R. (2017). SGEMM GPU kernel performance. UCI Machine Learning Repository.

Purohit, K., V., Bhattacharya, S., and Anand, A. (2025). Sample efficient demonstration selection for in-context learning. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 49959–49982 PMLR.

Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., and Wen, Z. (2018). A tutorial on Thompson sampling. Foundations and Trends in Machine Learning, 11(1):1–96.

Sen, R., Rakhlin, A., Ying, L., Kidambi, R., Foster, D., Hill, D. N., and Dhillon, I. S. (2021). Top-k extreme contextual bandits with arm hierarchy.

Improvements for AI systems

Confidence-Guided Candidate Selection: Implement Persistent Candidate LinUCB (PC-LinUCB) to reduce per-round scoring cost from O(Kd 2) to O((k + q)d 2) by scoring only these k + q candidates. This allows the system to handle large action sets where exhaustive evaluation is prohibitive.
Regret Control via Clipped Scores: Utilize clipped scores where each candidate's score is updated to the minimum of its previous value and the newly evaluated LinUCB score. This mechanism ensures that these scores are nonincreasing while preserving optimism on the standard confidence event, guiding both action selection and candidate retention.
Accelerated Exploration: By tuning parameters such that increasing 'q' searches the inactive set more quickly and increasing 'k' retains more promising actions, the system balances exploration and exploitation efficiently, leading to substantial speedups over exhaustive LinUCB (e.g., up to 70x in synthetic tests).
Guaranteed Performance Bounds: The algorithm establishes problem-independent and problem-dependent regret upper bounds which separate the standard linear-bandit learning term from an additive discovery cost of order O((K − k) log(K − k)/q). This provides rigorous guarantees on performance, even accounting for the partial access to the action set.
Unavoidable Access Cost Quantification: The system can explicitly quantify the cost imposed by candidate access by proving a regret lower bound of order omega((K − k)/q) under uniform challenger sampling, demonstrating that partial candidate access itself imposes an unavoidable regret cost.

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 (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, 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 O ((K-k) (K-k)/q) at fixed confidence. Notably, this additional cost does not grow with the horizon. For fixed gaps and sufficiently long horizons, we establish an Ω ((K-k)/q) regret lower bound under uniform challenger sampling, showing that partial candidate access itself imposes an unavoidable regret cost. Experiments show that PC-LinUCB substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

Sources

Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces