Accelerating Linear Bandits with Persistent Candidate Sets

1 INTRODUCTION

• Direct LinUCB scoring costs O(Kd^2) per round with a dense confidence matrix, making large fixed action sets computationally costly.The introduction notes that candidate action sets in applications such as recommendation and online advertising can reach millions.Source: §1 · p. 1
• Reducing the number of scored actions restricts access to the action set, so candidate design must balance retaining promising actions with opportunities for inactive actions to enter.The paper frames this as a retention-and-discovery tradeoff.Source: §1 · pp. 1–2
• Clipped optimistic scores guide action selection and candidate retention, while scoring k + q candidates reduces evaluations per round from K to k + q.The clipped scores are non-increasing and preserve optimism on the standard confidence event.Source: §1 · p. 2
• For fixed-gap instances and sufficiently long horizons, uniform challenger sampling incurs expected regret of order Ω((K − k)/q) when q ≪ K − k.The lower bound holds even when the identity of an initially inactive optimal action is known in advance.Source: §1 · p. 2
• PC-LinUCB substantially reduces end-to-end wall-clock time while maintaining regret comparable to exhaustive LinUCB, and its candidate mechanism also extends to SpectralUCB.Experiments include controlled synthetic problems, four large action sets derived from real data, and an application to SpectralUCB.Source: §1 · p. 2
• The regret upper bounds separate the standard linear-bandit learning term from an additive cost induced by partial access to the action set.The discovery cost reflects the time random challengers need to expose an action that remains plausible for optimality and does not grow with the horizon at fixed confidence.Source: §1 · p. 2

2.1 Problem Setting

• The problem setting uses a fixed finite action set with unchanged feature vectors and mean rewards determined by a shared unknown parameter.Rewards include conditionally R-sub-Gaussian noise, and performance is measured by cumulative pseudo-regret.Source: §2.1 · p. 2

2.2 Confidence Sets and Optimistic Scores

• Regularized least squares and OFUL-style ellipsoidal confidence sets define the optimistic scores used by PC-LinUCB.On the stated confidence event, the true parameter remains in the confidence sets through the horizon, and the upper and lower scores bound every action's mean reward.Source: §2.2 · p. 3

2.3 Persistent Candidate LinUCB

• At each round, PC-LinUCB samples q challengers uniformly from the inactive actions and joins them with the active set to form the candidate set.The procedure initializes an active set of size k and repeats candidate formation each round.Source: §2.3 · p. 3
• For candidates, the algorithm updates each clipped score to the minimum of its previous value and its newly evaluated LinUCB score, then selects the candidate with the largest clipped score.The next active set consists of the k candidates with the largest clipped scores.Source: §2.3 · p. 3
• With dense inverse covariance, scoring k + q candidates reduces per-round scoring cost from O(Kd^2) to O((k + q)d^2).Model updates and candidate maintenance add no further dependence on K per round.Source: §2.3 · p. 3
• The parameters k and q control retention and discovery: larger k retains more promising actions, while larger q searches the inactive set more quickly.The analysis considers the regime k + q ≪ K.Source: §2.3 · p. 3

3.1 Main Results

• With probability at least 1 − δ − δ′, both regret bounds combine a standard linear-bandit estimation term with the same additive discovery term.At fixed confidence, the discovery term depends on K, k, and q, but not on horizon T.Source: §3.1 · pp. 3–4

3.2 Proof Sketch

• The proof separates regret on rounds with an alive candidate from the cost of rounds with no alive candidate.The analysis introduces a potential tracking inactive alive actions and accumulated empty-candidate rounds, and shows their interaction forms a nonnegative supermartingale.Source: §3.2 · p. 4
• An action is alive when its clipped score is at least μ⋆; on the confidence event, an optimal action stays alive and dead actions remain dead.The proof defines alive actions through the set S_t and uses the non-increasing clipped-score update to keep dead actions dead.Source: §3.2 · p. 4
• When a candidate set contains an alive action, the selected action’s refreshed clipped score is at least μ⋆, allowing confidence widths to control regret.On empty-candidate rounds, the proof instead uses the per-round regret bound of 2.Source: §3.2 · pp. 4–5

4 TRADEOFF BETWEEN ACCELERATION AND REGRET

• The regret upper bounds separate standard linear-bandit learning from a partial-access discovery term scaling as eO((K − k)/q), independent of horizon at fixed confidence.The section asks whether partial access itself creates unavoidable regret with the same dependence on K, k, and q.Source: §4 · p. 5

4.1 Access-Induced Regret

• For fixed Δ and sufficiently long horizons, uniform challenger sampling imposes an expected access-induced regret lower bound of order Ω((K − k)/q).Before the initially inactive optimal action first appears among challengers, the policy cannot select it; its per-round challenger sampling probability is q/(K − k).Source: §4.1 · pp. 5–6

4.2 Acceleration and Access-Induced Regret

• Scoring k + q candidates instead of K gives nominal acceleration, but within this policy class greater acceleration accompanies a larger lower bound on expected access-induced regret.The nominal factor measures fewer action scores per round and excludes model-update cost shared by both methods.Source: §4.2 · p. 6

4.3 Active Set and Challenger Budget

• The active-set size k retains actions, while challenger budget q explores inactive actions more aggressively and shortens access waiting time for an inactive optimum.The lower bound depends on (K − k)/q, whereas nominal acceleration depends on the total scoring budget k + q.Source: §4.3 · p. 6

5.2 Semi-Synthetic Experiments

• 38.7–77.9× speedups over LinUCB with mean final regret differing by at most 1.2% made PC-LinUCB the fastest of six semi-synthetic methods.CBSCFD achieved 44.6–63.0% of LinUCB’s regret but took 14.6–22.1 times as long as PC-LinUCB.Source: Figure 2 · p. 7, §5.2 · p. 7

5 EXPERIMENTS

• All methods used dense score evaluation to isolate the gain from reducing dependence on K; LinUCB’s cached widths were not used.Source: §5 · p. 7

5.1 Synthetic Experiments

• 5.1× and 15.5× speedups over LinUCB changed mean final regret by +1.61% and −0.42% at d = 16 and d = 100, respectively.RS-OFUL was faster but increased mean final regret by about 31%.Source: §5.1 · p. 7

5.3 Ablation Experiments

• Increasing B/K from 1% to 20% cut speedup from 8.2× to 2.4× at d = 16 and from 49.2× to 4.5× at d = 100.At d = 16, the mean regret penalty declined from 2.9% to approximately zero; regret at d = 100 varied little.Source: Figure 3 · p. 8, §5.3 · p. 8
• At fixed B/K = 5%, speedup remained nearly unchanged across persistent shares; d = 16 regret rose with a larger active-set share, while d = 100 regret stayed nearly unchanged.Source: Figure 3 · p. 8, §5.3 · p. 8

5.4 Application to Spectral Bandits

• All three candidate budgets achieved nearly identical cumulative pseudo-regret to exhaustive SpectralUCB while providing substantial end-to-end speedups.The evaluation used B/K values of 1%, 5%, and 10%, with k = q.Source: Figure 4 · p. 8, §5.4 · p. 8

• Fixed actions and features allow clipped scores and persistent candidates to remain valid across rounds.Source: §6 · p. 8
• The method does not directly extend to contextual bandits, where changing actions or features can invalidate stored scores and candidates.Source: §6 · p. 8

AI USE STATEMENT

• AI tools assisted with code development, experiment execution, visualization, language polishing, and review of theoretical arguments; the authors reviewed and verified the outputs.The authors report that an earlier Lemma 6 proof was incorrect and that AI assistance helped identify the issue and develop the corrected proof.Source: AI USE STATEMENT · p. 9

Appendix Contents.

• The appendices cover proofs of both regret bounds and experimental details, including data construction, parameters, the Spectral bandit application, and timing.Source: Appendix Contents · p. 11

A PROOFS OF THE REGRET UPPER BOUNDS

• Because all mean rewards lie in [−1, 1], on nonempty-candidate rounds (Z_t = 0), ΔI_t ≤ min{2, w_{t−1}(I_t)}; on empty-candidate rounds (Z_t = 1), ΔI_t ≤ 2.Source: A PROOFS OF THE REGRET UPPER BOUNDS · p. 12
• Elliptical-potential bounds on cumulative capped widths yield the problem-independent result, while squared capped widths and the minimum gap yield the problem-dependent result.Both arguments combine the corresponding regret reduction with a bound on empty-candidate rounds.Source: A PROOFS OF THE REGRET UPPER BOUNDS · pp. 12, 14, 15
• Clipped scores never increase, so actions that become dead stay dead and the alive sets are nested.This property underlies the inactive-alive potential argument.Source: A PROOFS OF THE REGRET UPPER BOUNDS · pp. 11–12
• The inactive-alive potential is a nonnegative supermartingale, with initial value at most K − k.It tracks inactive alive actions as challengers are sampled and active actions retained.Source: A PROOFS OF THE REGRET UPPER BOUNDS · pp. 12–13
• A maximal-inequality argument uses the potential to bound the number of empty-candidate rounds with high probability.On the confidence event, each empty round leaves the optimal action alive and inactive; the potential starts at most K − k.Source: A PROOFS OF THE REGRET UPPER BOUNDS · pp. 13–14

B PROOF OF THE ACCESS-INDUCED REGRET LOWER BOUND

• Before the initially inactive optimal action first appears among challengers, the candidate-access restriction prevents its selection, regardless of knowledge of the reward model.The argument studies the waiting time to this first appearance.Source: B PROOF OF THE ACCESS-INDUCED REGRET… · p. 15
• The proof tracks the first challenger-set appearance of the optimal action, which remains inactive until that round.The action is one of the N inactive actions while it has not yet appeared.Source: B PROOF OF THE ACCESS-INDUCED REGRET… · p. 15
• Uniform sampling without replacement determines the waiting-time argument used to establish the access-induced regret lower bound.The proof separately treats the regime q ≤ N/2.Source: B PROOF OF THE ACCESS-INDUCED REGRET… · pp. 15–16

C.1 Data Construction

• The four semi-synthetic action sets are MovieLens-20M movies, UCI SGEMM GPU-kernel configurations, NAS-Bench-101 architectures, and DOCKSTRING molecules.Each feature set has 128 dimensions.Source: §C.1 · pp. 16–17
• MovieLens features are 128 principal components of Tag Genome scores, while SGEMM features encode transformed tuning parameters and their interactions.MovieLens source labels are user ratings; SGEMM source scores derive from recorded runtimes.Source: §C.1 · p. 16
• NAS-Bench-101 features encode architecture operations, edges, and paths; DOCKSTRING features are hashed Morgan count fingerprints.Their source scores are validation accuracy and negative docking scores, respectively.Source: §C.1 · pp. 16–17
• For each dataset, the authors fit a separate reward parameter using standardized source scores and an offline ridge penalty of 1, with an unpenalized intercept.The bandit environments use all available labels for fitting.Source: §C.1 · p. 17
• Held-out diagnostics fit a ridge model on 20% of labelled actions and report R² for value prediction and Spearman’s ρ for ranking agreement.The table caption says multi-instance entries are means ± sample standard deviations across five users or targets.Source: §C.1 · p. 17, Table 1 · p. 17

C.2 Method Parameters

• Method-specific hyperparameters use fixed representative configurations rather than per-dataset tuning, and PC-LinUCB’s candidate budget is fixed within each setting.All methods share the same exploration coefficient.Source: §C.2 · p. 17

C.3 Spectral Bandit Application

• The SpectralUCB application uses a weighted Erdős–Rényi graph with 10,000 nodes and a reward function generated from its first five spectral components.The reduced representation uses the 200 lowest-frequency eigenvectors; timing excludes common graph construction and eigendecomposition.Source: §C.3 · p. 18

C.4 Timing

• Within each repeat, methods share action features, reward parameters, mean rewards, and the round-wise Gaussian noise sequence.Synthetic configurations use ten instances; semi-synthetic repeats use five environments, users, or targets as specified.Source: §C.4 · p. 18
• Wall-clock timing runs serially on one server and includes initialization, search-index construction, selection, bookkeeping, observations, and model updates.Dataset loading, feature construction, reward fitting, noise generation, warmup, initial active-set sampling, and serialization are excluded.Source: Timing · p. 18

Timing.

• Regret curves report means with ±1 SE bands, and speedup is mean LinUCB wall time divided by mean method wall time.Held-out diagnostics instead report sample standard deviations across users or targets.Source: Timing · p. 18

C.5 Detailed Timing and Speedup Results

• Tables 2–12 report absolute wall-clock times and speedups, with initialization in milliseconds and online and total times in seconds.Initialization and online times are means across repeats; total times and speedups are reported as mean ± one standard error and ratio of means ± one paired standard error, respectively.Source: §C.5 · p. 19
• Online time includes action selection, reward observation, regret bookkeeping, and model updates, which were not timed separately.Shared data preparation is excluded, and speedups use LinUCB as the baseline except in the spectral experiment, which uses SpectralUCB.Source: §C.5 · p. 19
• Initialization time is calculated as the difference between recorded total and online times.Main comparisons and ablations were timed in separate batches, with each speedup using the paired baseline from its own batch.Source: §C.5 · p. 19
• 7.987 ± 0.097 seconds of shared spectral preparation time was excluded from Table 12.The time covers graph construction, eigendecomposition, feature and reward construction, noise generation, and initial-permutation generation; components were not timed separately.Source: §C.5 · p. 19