aiqbench analysis
This research introduces efficient algorithms for linear contextual bandits that minimize parameter updates to $O(\log\log T)$ while maintaining minimax-optimal regret in both small- and large-action regimes. By eliminating the computationally expensive G-optimal design step, these methods offer a practical solution for sequential decision-making tasks where frequent model retraining is costly or impractical. The work also extends these efficiency gains to generalized linear models, addressing a key bottleneck in strictly batched learning approaches.
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
arXiv:2606.00984v2 Announce Type: replace-cross Abstract: 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 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(\log\log T)$ parameter updates, while remaining computationally efficient in practice.
Abstract: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 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(\log\log T)$ parameter updates, while remaining computationally efficient in practice.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2606.00984 [stat.ML]
(or arXiv:2606.00984v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2606.00984 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 292 words
Related coverage
Uplifting conversion across the acquisition funnel with personalization using contextual bandits on AWS
AWS · Oct 1, 2026
Contextual Slate GLM Bandits with Limited Adaptivity
arXiv · Aug 4, 2026
Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
arXiv · Sep 28, 2026
Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
arXiv · Sep 24, 2026