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

• URL: http://arxiv.org/abs/2606.00984v1
• Date: Sun, 31 May 2026 03:46:16 GMT
• Title: Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
• Abstract summary: We study linear contextual bandits under rare parameter updates.<n>We propose two practical algorithms with only $O(loglog T)$ parameter updates.<n>Our results yield statistically optimal algorithms under $O(loglog T)$ parameter updates.
• Score: 33.46701416812218
• License: http://creativecommons.org/licenses/by/4.0/
• 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 statistically optimal algorithms under $O(\log\log T)$ parameter updates that are also computationally efficient in practice.

Related papers

• Achieving Limited Adaptivity for Multinomial Logistic Bandits [0.7373617024876725]
  We present two algorithms that operate in the batched and rarely-switching paradigms.<n>B-MNL-CB achieves $tildeO(sqrtT)$ regret when presented with $tildeO(log log T)$ update rounds.<n> RS-MNL works with adversarially generated contexts and can achieve $tildeO(sqrtT)$ regret with $tildeO(log T)$ policy updates.
  arXiv  Detail & Related papers  (2025-08-05T04:43:01Z)
• Optimal and Practical Batched Linear Bandit Algorithm [8.087699764574788]
  We study the linear bandit problem under limited adaptivity, known as the batched linear bandit.<n>We propose BLAE, a novel batched algorithm that integrates arm elimination with regularized G-optimal design.<n> BLAE is the first algorithm to combine provable minimax-optimality in all regimes and practical superiority in batched linear bandits.
  arXiv  Detail & Related papers  (2025-07-11T09:29:28Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Practical Performance Guarantees for Pipelined DNN Inference [3.493620624883548]
  We optimize pipeline parallelism for deep neural network (DNN) inference by partitioning graphs into $k$ stages. We show that our improved lower bounds close the optimality gap by a factor of 9.855x.
  arXiv  Detail & Related papers  (2023-11-07T03:55:39Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  We propose two novel algorithms based on truncation and mean of medians. Our truncation-based algorithm supports online learning, distinguishing it from existing truncation-based approaches. Our algorithms improve the regret bounds by a logarithmic factor compared to existing algorithms when $epsilon=1$.
  arXiv  Detail & Related papers  (2023-10-28T13:01:10Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  We study the problem of emphdynamic regret minimization in $K$-armed Dueling Bandits under non-stationary or time varying preferences. This is an online learning setup where the agent chooses a pair of items at each round and observes only a relative binary win-loss' feedback for this pair.
  arXiv  Detail & Related papers  (2021-11-06T16:46:55Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Improved Regret Bound and Experience Replay in Regularized Policy Iteration [22.621710838468097]
  We study algorithms for learning in infinite-horizon undiscounted Markov decision processes (MDPs) with function approximation. We first show that the regret analysis of the Politex algorithm can be sharpened from $O(T3/4)$ to $O(sqrtT)$ under nearly identical assumptions. Our result provides the first high-probability $O(sqrtT)$ regret bound for a computationally efficient algorithm in this setting.
  arXiv  Detail & Related papers  (2021-02-25T00:55:07Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. A natural way to resolve this problem is to apply online gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information, achieves $tildeO(sqrtT)$ regret with the total time complexity that
  arXiv  Detail & Related papers  (2020-06-07T01:12:39Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.