Accelerating Linear Bandits with Persistent Candidate Sets

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

cs.LGOct 9, 2026

Accelerating Linear Bandits with Persistent Candidate Sets

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

Organizations: Mohamed bin Zayed University of Artificial Intelligence · HSE University · RIKEN AIP

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 (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 $\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 PC-LinUCB substantially accelerates LinUCB while maintaining comparable regret, and that the persistent candidate mechanism can extend beyond LinUCB.

Figures & tables

Figure 1: Six-method comparison on synthetic action sets. Columns show $(d,T)=(16,20{,}000)$ and $(100,100{,}000)$ , with $K=10{,}000$ and $k=q=250$ for PC-LinUCB . Top: cumulative pseudo-regret (symlog scale). Bottom: end-to-end speedup over LinUCB (logarithmic scale). Curves average ten repeats; bands show $\pm 1$ SE.

Figure 2: Six-method comparison on real action features with linear simulated rewards, $d=128$ , and $T=20{,}000$ . PC-LinUCB uses $k=q$ and $B/K\approx 2\%$ . Top: cumulative pseudo-regret (symlog scale). Bottom: end-to-end speedup over LinUCB (logarithmic scale). Curves average five repeats; bands and error bars show $\pm 1$ SE.

Figure 3: PC-LinUCB ablations. (a) The total candidate budget

B=k+q

varies with

k=q

. (b) The persistent share

k/B

varies with

q=B-k

and fixed

B/K=5\%

. Top: percentage change in mean final regret relative to LinUCB. Bottom: speedup over LinUCB.

Figure 4: Persistent candidate mechanism applied to SpectralUCB. Curves show mean cumulative pseudo-regret over ten runs for

B/K\in\{1\%,5\%,10\%\}

with

k=q

; labels show speedup over SpectralUCB.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	$K$	Held-out $R^{2}$	Held-out $\rho$
MovieLens-20M	$10{,}381$	$0.412\pm 0.082$	$0.638\pm 0.069$
UCI SGEMM	$241{,}600$	$0.850$	$0.886$
NAS-Bench-101	$423{,}624$	$0.256$	$0.749$
DOCKSTRING	$260{,}155$	$0.405\pm 0.029$	$0.627\pm 0.031$

Appendix

Table 1: Held-out linearity diagnostics for the semi-synthetic action features.

R^{2}

measures value prediction, and Spearman’s

\rho

measures ranking agreement. Entries with multiple instances report the mean

\pm

sample standard deviation over five users or targets.

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	0.305	0.895	$0.895\pm 0.003$	$5.07\pm 0.02$
LinUCB	0.040	4.540	$4.540\pm 0.007$	$1.00\pm 0.00$
RS-OFUL	0.049	0.150	$0.150\pm 0.001$	$30.29\pm 0.22$
CBSCFD	0.114	4.213	$4.213\pm 0.009$	$1.08\pm 0.00$
PSI-LinUCB	0.130	5.401	$5.401\pm 0.018$	$0.84\pm 0.00$
Sub-Elim	16.221	2.569	$2.585\pm 0.045$	$1.76\pm 0.03$

Appendix

Table 2: Synthetic comparison with

K=10{,}000

d=16

T=20{,}000

, and ten paired repeats. PC-LinUCB uses

k=q=250

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	0.440	15.011	$15.012\pm 0.017$	$15.50\pm 0.16$
LinUCB	0.042	232.675	$232.675\pm 2.313$	$1.00\pm 0.00$
RS-OFUL	0.049	3.221	$3.221\pm 0.045$	$72.25\pm 0.76$
CBSCFD	0.241	137.570	$137.570\pm 1.048$	$1.69\pm 0.01$
PSI-LinUCB	0.224	142.663	$142.663\pm 1.940$	$1.63\pm 0.01$
Sub-Elim	14.643	136.877	$136.892\pm 6.257$	$1.70\pm 0.07$

Appendix

Table 3: Synthetic comparison with

K=10{,}000

d=100

T=100{,}000

, and ten paired repeats. PC-LinUCB uses

k=q=250

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	0.585	2.562	$2.562\pm 0.010$	$38.66\pm 0.11$
LinUCB	0.037	99.057	$99.057\pm 0.175$	$1.00\pm 0.00$
RS-OFUL	0.036	3.800	$3.800\pm 0.143$	$26.07\pm 1.01$
CBSCFD	0.614	37.280	$37.281\pm 0.151$	$2.66\pm 0.01$
PSI-LinUCB	0.582	42.502	$42.502\pm 0.573$	$2.33\pm 0.03$
Sub-Elim	15.432	77.560	$77.575\pm 0.389$	$1.28\pm 0.01$

Appendix

Table 4: MovieLens-20M comparison with

K=10{,}381

d=128

T=20{,}000

, and five paired repeats. PC-LinUCB uses

k=q=104

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	15.488	42.573	$42.588\pm 0.940$	$74.74\pm 1.28$
LinUCB	0.087	3182.931	$3182.931\pm 19.509$	$1.00\pm 0.00$
RS-OFUL	0.091	138.903	$138.903\pm 0.989$	$22.91\pm 0.10$
CBSCFD	16.804	914.613	$914.630\pm 9.855$	$3.48\pm 0.02$
PSI-LinUCB	16.747	1096.383	$1096.399\pm 37.921$	$2.90\pm 0.09$
Sub-Elim	373.000	1232.161	$1232.534\pm 5.321$	$2.58\pm 0.02$

Appendix

Table 5: UCI SGEMM comparison with

K=241{,}600

d=128

T=20{,}000

, and five paired repeats. PC-LinUCB uses

k=q=2416

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	25.772	84.216	$84.242\pm 4.709$	$66.05\pm 3.94$
LinUCB	0.127	5564.294	$5564.294\pm 34.611$	$1.00\pm 0.00$
RS-OFUL	0.118	225.524	$225.524\pm 0.612$	$24.67\pm 0.18$
CBSCFD	29.144	1556.777	$1556.806\pm 10.746$	$3.57\pm 0.02$
PSI-LinUCB	28.680	1848.407	$1848.436\pm 37.106$	$3.01\pm 0.04$
Sub-Elim	638.478	3459.211	$3459.849\pm 7.794$	$1.61\pm 0.01$

Appendix

Table 6: NAS-Bench-101 comparison with

K=423{,}624

d=128

T=20{,}000

, and five paired repeats. PC-LinUCB uses

k=q=4237

Method	Init. (ms)	Online (s)	Total (s)	Speedup
PC-LinUCB	15.972	43.211	$43.227\pm 0.156$	$77.92\pm 0.42$
LinUCB	0.091	3368.120	$3368.120\pm 10.575$	$1.00\pm 0.00$
RS-OFUL	0.082	138.386	$138.386\pm 0.426$	$24.34\pm 0.08$
CBSCFD	17.620	953.688	$953.706\pm 5.976$	$3.53\pm 0.03$
PSI-LinUCB	17.721	1100.410	$1100.428\pm 17.285$	$3.06\pm 0.05$
Sub-Elim	394.129	2516.168	$2516.562\pm 4.617$	$1.34\pm 0.00$

Appendix

Table 7: DOCKSTRING comparison with

K=260{,}155

d=128

T=20{,}000

, and five paired repeats. PC-LinUCB uses

k=q=2602

Configuration	Method	Init. (ms)	Online (s)	Total (s)	Speedup
$B/K=1\%$	PC-LinUCB	0.260	0.555	$0.555\pm 0.001$	$8.23\pm 0.03$
$B/K=1\%$	LinUCB	0.018	4.570	$4.570\pm 0.013$	$1.00\pm 0.00$
$B/K=2\%$	PC-LinUCB	0.265	0.639	$0.639\pm 0.001$	$7.10\pm 0.02$
$B/K=2\%$	LinUCB	0.017	4.537	$4.537\pm 0.009$	$1.00\pm 0.00$
$B/K=5\%$	PC-LinUCB	0.259	0.868	$0.868\pm 0.002$	$5.23\pm 0.01$
$B/K=5\%$	LinUCB	0.017	4.539	$4.539\pm 0.005$	$1.00\pm 0.00$

Appendix

Table 8: Candidate-budget ablation with

K=10{,}000

d=16

T=20{,}000

, and ten paired repeats per configuration. PC-LinUCB uses

k=q=B/2

Configuration	Method	Init. (ms)	Online (s)	Total (s)	Speedup
$B/K=1\%$	PC-LinUCB	0.572	7.253	$7.254\pm 0.013$	$49.18\pm 0.10$
$B/K=1\%$	LinUCB	0.024	356.727	$356.727\pm 0.246$	$1.00\pm 0.00$
$B/K=2\%$	PC-LinUCB	0.572	11.969	$11.969\pm 0.024$	$30.21\pm 0.11$
$B/K=2\%$	LinUCB	0.023	361.569	$361.570\pm 1.784$	$1.00\pm 0.00$
$B/K=5\%$	PC-LinUCB	0.565	23.762	$23.762\pm 0.077$	$15.16\pm 0.07$
$B/K=5\%$	LinUCB	0.025	360.317	$360.317\pm 0.654$	$1.00\pm 0.00$

Appendix

Table 9: Candidate-budget ablation with

K=10{,}000

d=100

T=100{,}000

, and ten paired repeats per configuration. PC-LinUCB uses

k=q=B/2

Configuration	Method	Init. (ms)	Online (s)	Total (s)	Speedup
$(k,q)=(50,450)$	PC-LinUCB	0.269	0.891	$0.891\pm 0.002$	$5.16\pm 0.01$
$(k,q)=(50,450)$	LinUCB	0.021	4.601	$4.601\pm 0.010$	$1.00\pm 0.00$
$(k,q)=(125,375)$	PC-LinUCB	0.272	0.879	$0.879\pm 0.003$	$5.23\pm 0.02$
$(k,q)=(125,375)$	LinUCB	0.021	4.601	$4.601\pm 0.011$	$1.00\pm 0.00$
$(k,q)=(250,250)$	PC-LinUCB	0.266	0.869	$0.870\pm 0.001$	$5.21\pm 0.01$
$(k,q)=(250,250)$	LinUCB	0.021	4.534	$4.534\pm 0.005$	$1.00\pm 0.00$

Appendix

Table 10: Budget-allocation ablation with

K=10{,}000

d=16

T=20{,}000

, and ten paired repeats per configuration. PC-LinUCB uses

B=k+q=500

Configuration	Method	Init. (ms)	Online (s)	Total (s)	Speedup
$(k,q)=(50,450)$	PC-LinUCB	0.814	24.487	$24.488\pm 0.055$	$15.60\pm 0.09$
$(k,q)=(50,450)$	LinUCB	0.032	381.932	$381.932\pm 2.024$	$1.00\pm 0.00$
$(k,q)=(125,375)$	PC-LinUCB	0.609	23.652	$23.653\pm 0.131$	$15.06\pm 0.06$
$(k,q)=(125,375)$	LinUCB	0.029	356.097	$356.097\pm 2.725$	$1.00\pm 0.00$
$(k,q)=(250,250)$	PC-LinUCB	0.649	23.742	$23.743\pm 0.231$	$15.27\pm 0.15$
$(k,q)=(250,250)$	LinUCB	0.028	362.568	$362.568\pm 4.355$	$1.00\pm 0.00$

Appendix

Table 11: Budget-allocation ablation with

K=10{,}000

d=100

T=100{,}000

, and ten paired repeats per configuration. PC-LinUCB uses

B=k+q=500

Method	Init. (ms)	Online (s)	Total (s)	Speedup
SpectralUCB	0.050	736.438	$736.438\pm 2.478$	$1.00\pm 0.00$
PC-SpectralUCB (1%)	1.247	10.490	$10.491\pm 0.039$	$70.20\pm 0.30$
PC-SpectralUCB (5%)	1.301	35.650	$35.652\pm 0.072$	$20.66\pm 0.08$
PC-SpectralUCB (10%)	1.294	67.213	$67.215\pm 0.072$	$10.96\pm 0.04$

Appendix

Table 12: Spectral comparison with

K=10{,}000

J=200

T=50{,}000

, and ten paired repeats. PC-SpectralUCB uses

k=q=50

250

, and

500

at budgets of

1\%

5\%

, and

10\%

, respectively.

Explore similar work

Offline-to-Online Learning in Linear Bandits
Jun 3, 2026Kushagra Chandak, Toshinori Kitamura, Xiaoqi TanMulti-Armed Bandits Contextual Bandits
Department of Computing Science, University of Alberta, Canada
Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
Oct 5, 2026Jingyuan Liu, Huiwen JiaMulti-Armed Bandits Non-Stationary Bandits
Department of Industrial Engineering and Operations Research, University of California, Berkeley
Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets
Oct 13, 2026Chen-Yu WeiAdversarial Bandits Bandit Convex Optimization
University of Virginia

Jun 3, 2026J/K move · Enter open · S save

Offline-to-Online Learning in Linear Bandits

Kushagra Chandak, Toshinori Kitamura, Xiaoqi Tan

Department of Computing Science, University of Alberta, Canada

Multi-Armed Bandits Contextual Bandits

Open paper AskPDF arXiv

We study online learning with an additional offline dataset in the stochastic linear bandit setting. Although this problem arises frequently in practice, the offline-to-online tradeoff remains poorly understood in structured environments. We propose a linear bandit algorithm that balances this tradeoff: it relies on offline data during early rounds, and increasingly favors exploration as the horizon grows. We establish regret bounds showing that our method is simultaneously competitive with both purely online and purely offline solutions. In particular, it achieves sublinear regret relative to the optimal action in the number of online interactions, while its regret relative to an offline reference decreases as the number of offline samples grows. Empirical results further demonstrate its effectiveness across various problem parameters.

Abstract

Explore similar work

Offline-to-Online Learning in Linear Bandits

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

Follow the Perturbed Leader for Linear Bandits: T\sqrt{T}T​ Regret over General Convex Sets

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets