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

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(log log 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 Goptimal 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 minimax-optimal algorithms for linear contextual bandits and a near-optimal generalized-linear extension under O(log log T ) parameter updates, while remaining computationally efficient in practice.