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

1. Problem Setting

This paper addresses the problem of stochastic linear contextual bandits under the constraint of rare parameter updates. In this setting, an agent sequentially selects actions (arms) from a time-varying set of $K$ arms, each characterized by a $d$-dimensional feature vector. The reward is generated by an unknown linear model $\theta^*$ plus noise.

The core constraint is that the learner may only incorporate reward feedback into its parameter estimate (e.g., via ridge regression or MLE) at a small number of update times, $B$, over a horizon $T$. Crucially, the authors distinguish this from strictly batched settings. While rewards are delayed until the end of an interval, the authors argue that in practical deployments, contexts are observed online before actions are chosen. Therefore, the learner should be allowed to perform reward-free within-interval updates (e.g., updating Gram matrices or elimination sets based on observed contexts) even if the heavy parameter retraining is delayed. This distinction bridges the gap between fully sequential methods and strictly batched methods that forbid within-interval adaptivity.

The goal is to design algorithms that:

1. Achieve minimax-optimal regret in both small-$K$ ($K \le O(ed)$) and large-$K$ ($K \ge \Omega(ed)$) regimes.
2. Operate with only $O(\log \log T)$ parameter updates.
3. Avoid computationally expensive subroutines, specifically G-optimal design, which has been a bottleneck in prior strictly batched optimal algorithms.

2. Methodology

The paper proposes two primary algorithms for linear contextual bandits and one extension for generalized linear bandits.

BLCE-G (Batched-Feedback Linear Contextual Bandit with Elimination and G-optimal design)

This algorithm combines arm elimination with a near G-optimal design strategy.

• Structure: It operates on a static grid of intervals.
• Mechanism: Within each interval, rounds are split into phases. The first phase utilizes a near G-optimal design to sample arms, ensuring sufficient information gain. Subsequent phases involve selecting the most informative direction relative to the current Gram matrix and finally a greedy selection based on the latest estimate.
• Elimination: Suboptimal arms are eliminated iteratively using estimates from previous intervals.
• Complexity: It retains the theoretical tightness of G-optimal design but relaxes the exact computation to a near-optimal version computable in $O(Kd^3)$, updated via Sherman-Morrison.

BLCE (Batched-Feedback Linear Contextual Bandit with Elimination)

This algorithm removes the G-optimal design step entirely to improve computational efficiency.

• Structure: Similar static grid and arm elimination framework as BLCE-G.
• Mechanism: Instead of G-optimal design, BLCE relies on uncertainty-driven exploration (selecting the arm with the maximum norm in the inverse Gram matrix) combined with arm elimination. The exploration phase is lengthened to compensate for the lack of explicit design.
• Significance: It is the first linear contextual bandit algorithm with rare updates to achieve minimax optimality without relying on G-optimal design, reducing the time complexity to $O(Kd^2 T \log \log T)$.

BGLE (Batched-Feedback Generalized Linear Contextual Bandit with Elimination)

This extends the principles of BLCE to generalized linear rewards (exponential family distributions).

• Mechanism: It uses Maximum Likelihood Estimation (MLE) at interval boundaries and employs a weighted Gram matrix during exploration to handle non-linearity.
• Key Feature: The regret bounds are independent of the worst-case curvature parameter $\kappa$, which can diverge in saturation, relying instead on the average inverse curvature $\hat{\kappa}$.

3. Key Contributions

The paper makes the following specific contributions:

1. Tightest Regret Bounds under Rare Updates: The authors introduce BLCE-G, which achieves minimax-optimal regret (up to polylogarithmic factors) in both small-$K$ and large-$K$ regimes using only $O(\log \log T)$ parameter updates. This matches the known minimax lower bounds $\Omega(\sqrt{dT} \log K)$ and $\Omega(d\sqrt{T})$.
2. Optimality without G-Optimal Design: BLCE is presented as the first algorithm to achieve minimax-optimal regret in the rare-update setting without the computationally expensive G-optimal design step. It achieves the lowest known time complexity among optimal algorithms.
3. Redefining the Adaptability Landscape: The paper explicitly categorizes and distinguishes three operational settings:
   • Fully Sequential: Full adaptivity every round.
   • Strictly Batched: No within-interval context adaptivity (action rules are fixed at the interval start).
   • Rare Parameter Updates: Restricts reward-dependent updates but allows reward-free within-interval adaptivity.
     The authors argue that "Rare Parameter Updates" is the practical regime that avoids the computational bottlenecks of strict batching while maintaining statistical efficiency.
4. Generalized Linear Extension: The extension to generalized linear bandits (BGLE) provides near-optimal regret guarantees that are independent of the worst-case curvature parameter $\kappa$, a significant improvement over prior work where transient terms depended on $\kappa$.
5. Practical Superiority: Experimental results demonstrate that the proposed algorithms consistently outperform state-of-the-art baselines (e.g., RS-OFUL, BatchLinUCB-DG, SoftBatch) in terms of both regret and runtime, particularly in high-dimensional or large-$K$ settings where prior optimal methods suffer from exponential or high-polynomial time complexity.

4. Results

• Regret Bounds:
  • BLCE-G: $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log d \log \log T})$.
  • BLCE: $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log T \log \log T})$.
  • BGLE: Leading term $O(RS\sqrt{d(d+\log T)T \log T \log \log T / \hat{\kappa}})$.
• Parameter Updates: All algorithms operate with $O(\log \log T)$ updates.
• Time Complexity:
  • BLCE-G: $O(Kd^2 T (d + \log \log T))$.
  • BLCE: $O(Kd^2 T \log \log T)$.
  • BGLE: $O(Kd^2 T \log \log T + C_{opt}^{tot})$.
• Empirical Performance: In experiments with $T=10,000$, BLCE and BLCE-G achieved the lowest cumulative regret across various $(K, d)$ pairs. BLCE demonstrated the fastest runtime, often comparable to suboptimal baselines, while strictly batched optimal methods (like those relying on G-optimal design) showed "Exponential" runtime or significantly higher costs.

5. Significance and Claims

The paper claims that its results unify theory and practice in linear and generalized linear contextual bandits. The primary significance lies in demonstrating that limited reward adaptivity does not necessitate computationally expensive pre-planned exploration. By allowing lightweight, reward-free processing of contexts within intervals, the authors show that it is possible to:

• Retain the statistical optimality of rare-update algorithms.
• Eliminate the dominant computational bottleneck (G-optimal design) that has hindered the deployment of strictly batched optimal methods.
• Provide algorithms that are both theoretically sound (minimax-optimal) and practically efficient (low runtime), making them suitable for real-world pipelines where model retraining is costly but context observation is continuous.

The authors remain modest regarding the theoretical bounds, noting that while BLCE-G has a strictly smaller minimax regret bound in theory, empirical results show BLCE often performs comparably or better in benign stochastic environments, suggesting that greedy exploitation may be highly effective even with rare updates.