Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates

The paper studies stochastic linear contextual bandits under rare parameter updates, where the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. The authors clarify a practical distinction that is often blurred in the literature: many strictly batched methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context).

The paper explicitly distinguishes three operational settings: (i) fully sequential (fully adaptive) contextual bandits; (ii) strictly batched contextual bandits, which disallow within-interval context adaptivity; and (iii) rare parameter updates, which restrict reward-dependent parameter updates but allow reward-free within-interval context adaptivity.

The authors state: "In deployments of bandit algorithms, the practical bottleneck is often not selecting an action given a context, but updating the underlying model once new reward feedback arrives: model retraining, confidence set recomputation, or posterior updates may require expensive pipelines, logging joins, privacy checks, or human-in-the-loop validation."

The authors introduce BLCE-G (Batched-Feedback Linear Contextual Bandit with Elimination and G-optimal design), which combines near G-optimal design with arm elimination. It achieves the worst-case regret bound:

R(T) = O (sqrt dT (sqrt (KT) sqrt d + T) sqrt d sqrt T)

This simultaneously matches the minimax lower bounds (d sqrt T) in the large-K regime (K at least (e d)) and (sqrt dT K) in the small-K regime (K at most O(e d)), up to logarithmic factors, while requiring only O(T) parameter updates under a static schedule.

The authors propose BLCE (Batched-Feedback Linear Contextual Bandit with Elimination), which removes the near G-optimal design step—a dominant computational bottleneck in prior strictly batched static-grid methods—yet preserves minimax-optimal regret. BLCE achieves:

R(T) = O (sqrt dT (sqrt (KT) sqrt d + T) sqrt T sqrt T)

BLCE attains the lowest known runtime complexity among optimal algorithms: O(Kd squared T T). The authors state: "To our knowledge, BLCE is the first linear contextual bandit algorithm with rare parameter updates that achieves minimax-optimal regret without relying on G-optimal design, which has traditionally been regarded as essential in strictly batched static-grid settings."

The authors extend their rare-update and computational principles to generalized linear contextual bandits with the BGLE (Batched-Feedback Generalized Linear Contextual Bandit with Elimination) algorithm. BGLE achieves:

R(T) = O (RS sqrt d(d+ T)T T T over sqrt) + O ((R squared S e 8RS d(d+ T) T T + R)T 1/3)

Both the leading and transient terms are κ-free, in sharp contrast to prior work (Sawarni et al., 2024) whose transient term depends on κ. The authors note: Since µ̇(z) → 0 in saturation, κ can grow arbitrarily large, so removing this dependence is a substantial improvement.

• First interval: Rounds are divided into two phases with ratio c: (1-c). During the first c-fraction, arms are sampled according to a near G-optimal design over A t; in the remaining (1-c) -fraction, the algorithm selects the most informative direction with respect to the current Gram matrix.

• Subsequent intervals (at least 2): Rounds are partitioned in the ratio c squared: c(1-c): (1-c). In the first c squared-fraction, arms are sampled according to a near G-optimal design over A t(-1). In the next c(1-c) -fraction, the algorithm selects the most informative direction relative to the Gram matrix. In the final (1-c) -fraction, arms are chosen greedily with respect to the latest estimate.

• The algorithm performs-1 elimination rounds using past estimates 1,,-1, yielding nested feasible sets A t(1),, A t(-1).

• First interval: The algorithm repeatedly pulls the most informative direction with respect to the current Gram matrix.

• Subsequent intervals (at least 2): Rounds are divided into two phases. In the first phase of length cT 1-2-over 2 2 T, the algorithm selects the most informative direction with respect to the current Gram matrix. In the second phase, arms are chosen greedily with respect to the latest estimate.

• The elimination procedure is the same as BLCE-G, but without the G-optimal design phase.

• First interval: The algorithm repeatedly pulls the most informative direction with respect to the current Gram matrix.

• Subsequent intervals (at least 2): The Gram matrix is weighted by alpha t, -1(lambda) (x t,a t,-1), where alpha t,k(lambda) = (-2RS) 1k=1 + (-R(2S x t,a t V k-1 beta(lambda))) 1k at least 2.

• Beginning at interval at least 3, the algorithm performs-2 elimination rounds using estimates 2,,-1.

All three algorithms use a static grid schedule with B = O(T) parameter updates. For BLCE-G and BLCE, the interval end times are defined as T 1 = sqrt T over 2 2 T + 1 and T = T-1 + T 1-2-over 2 2 T + 2 T for at least 2. For BGLE, the schedule is T = T 1-1 over 3 times 2-4 over 2 2 T T for at least 4, with T = T-1 + T 1/3 over 2 2 T for at most 3.

The authors show in Remark 1 that the i.i.d. context assumption can be relaxed to batch-wise conditions:

1. Law(A t F T-1) about D-1, t in [T-1+1, T+1]

2. A t !!! A s, x s,a s, r s s=T-1+1 T F T-1, t in [T+1, T+1]

3. A s !!! A u, x u,a u, r u u=T-1+1 s-1 F T-1, s in (T-1+1, T]

These conditions are strictly weaker than full i.i.d., requiring only (i) equality of the conditional context law across consecutive intervals and (ii) conditional independence across and within intervals.

• BLCE-G: O(Kd squared T(d + T)) — the main costs are near G-optimal design (O(Kd 3) per call) and arm elimination (O(Kd squared T T) total).

• BLCE: O(Kd squared T T) — only arm elimination is a bottleneck.

• BGLE: O(Kd squared T T + C opt tot), where C opt tot is the total oracle cost of solving the log-loss minimization at interval boundaries.

The paper identifies computational bottlenecks in existing strictly batched algorithms:

• Ruan et al. (2021): Repeatedly compute G-optimal design distributions, leading to large polynomial dependence on d.

• Hanna et al. (2023b): Discretize the space using a fine (1/T) -net of size (T d), yielding exponential dependence on d.

• Zhang et al. (2025): Execute a near G-optimal design policy at every round of batch 1, incurring O(Kd 3) time per round.

The paper evaluates BLCE-G and BLCE over T = 10, 000 rounds across four (K,d) pairs: (1000,5), (5000,10) (large-K regime) and (50,20), (100,30) (small-K regime). Both algorithms consistently outperform baselines (RS-OFUL, BatchLinUCB-DG, SoftBatch, BatchLearning) in both regimes, achieving the lowest regret with greater stability. Runtime comparisons show BLCE achieves the fastest runtime among optimal algorithms, comparable even to suboptimal baselines. For generalized linear contextual bandits, BGLE outperforms B-GLinCB with lower regret and reduced computation.

Based on the paper, here are the specific improvements I can make to AI systems:

1. Rare-Update Sequential Decision-Making

• The AI system can now make optimal decisions in contextual bandit settings while updating its underlying reward model only O(log log T) times over a horizon of T rounds—a dramatic reduction from the O(d log T) or O(K log T) updates required by prior methods.

• This is critical for real-world deployments where model retraining is expensive (e.g., recommender systems, clinical trials, inventory control) because the system can process incoming contexts and make decisions in real-time while deferring expensive parameter updates to rare, scheduled intervals.

2. Computational Efficiency Without Sacrificing Optimality

• The system (via the BLCE algorithm) achieves minimax-optimal regret—matching theoretical lower bounds—while eliminating the computationally expensive G-optimal design step that prior optimal algorithms required.

• Total time complexity is reduced to O(Kd2T log log T), which is the lowest among all known optimal algorithms. In practice, this translates to runtime improvements of 4-10x over the next best optimal method (e.g., 1.62 seconds vs. 23.40 seconds for BLCE vs. BLCE-G at K=1000, d=5).

3. Adaptive Within-Interval Context Processing

• Unlike strictly batched methods that commit to fixed action rules at interval boundaries, the improved system can perform lightweight, reward-free updates within each interval using only the observed contexts and chosen actions.

• This allows the system to exploit real-time context information (e.g., updating Gram matrices, uncertainty scores, or elimination candidate sets) without waiting for reward feedback, bridging the gap between fully sequential and strictly batched approaches.

4. Dual-Regime Optimality

• The system simultaneously achieves optimal regret in both the small-K regime (K ≤ O(e d)) and large-K regime (K ≥ Ω(e d)):

• Small-K: regret scales as Õ(√(dT log K))

• Large-K: regret scales as Õ(d√T)

• This means the same algorithm performs optimally whether the system faces a few well-separated arms or many densely-packed arms, without requiring regime-specific tuning.

5. Relaxed Assumptions on Context Distributions

• The system's guarantees hold under conditions strictly weaker than the standard i.i.d. context assumption used by all prior work.

• It only requires: (i) equality of conditional context distributions across consecutive intervals, and (ii) conditional independence across and within intervals. This makes the system applicable to non-stationary or slowly-varying context distributions.

6. Generalized Linear Model Extension (BGLE)

• The system extends to generalized linear contextual bandits (e.g., logistic regression for binary rewards) with regret bounds that are independent of the worst-case curvature parameter κ—a significant improvement over prior work whose transient terms could diverge in saturation regimes.

• This makes the system robust to link functions with vanishing derivatives (e.g., logistic regression in extreme probability regions), where prior methods would fail.

7. Practical Flexibility in Exploration-Exploitation Trade-off

• The within-interval allocation rate c ∈ (0,1) can be tuned by practitioners. Empirical results show that smaller c values (more greedy exploitation) tend to improve performance in benign stochastic environments, giving users control over the exploration-exploitation balance without violating theoretical guarantees.

8. Stable and Low-Variance Performance

• In numerical experiments across various context distributions (uniform, normal, Student-t, Beta, Laplace, Exponential), the system consistently achieves lower cumulative regret with smaller standard deviation compared to all baselines, indicating both better average performance and greater reliability.

We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only O(T) parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in T) simultaneously in both the small- K and large- K regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under O(T) parameter updates that are also computationally efficient in practice.