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

arXiv: https://arxiv.org/abs/2606.00984 · HTML: https://mlsanity.com/paper/2606.00984/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 31 May 2026.

## Builds on (most cited first, 14 of 14)

- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits](https://mlsanity.com/paper/2110.08057/) (2021)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [Optimal and Practical Batched Linear Bandit Algorithm](https://mlsanity.com/paper/2507.08438/) (2025)

## Built on by (most cited first, 2 of 2)

- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)
- [Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm](https://mlsanity.com/paper/2610.06006/) (2026)

## Abstract (arXiv)

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