mlsanityData to 14 Oct 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

arXiv 2605.30976 ↗First posted 29 May 2026stat.ML cs.IT cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size B, and during each batch the learner sends B requested arm pulls to an agent, who then observes the corresponding B rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that Omega(Bmind,loglvert A rvert) regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of widetildeOmega(Bmind,loglvert A rvert + √dT mind,loglvert A rvert). We develop two phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation. The first achieves widetildeO(dB + d√T) regret, matching the lower bound up to logarithmic factors when lvert A rvert = exp(Omega(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain widetildeO(Bloglvert A rvert + d3/2√B + √dTloglvert A rvert) regret, which is near-optimal in broad scaling regimes of (lvert A rvert, B, d, T). Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as Theta(√T).

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 37 of its 57 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

37 of 57 references.

References · 37

  1. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 136
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  3. 2019Batched Multi-armed Bandits Problemcited by 98
  4. 2020Differentially-Private Federated Linear Banditscited by 83
  5. 2018Differentially Private Contextual Linear Banditscited by 82
  6. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  7. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  8. 2021Federated Linear Contextual Banditscited by 61
  9. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  10. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  11. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  12. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
25 more
  1. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  2. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  3. 2022Shuffle Private Linear Contextual Banditscited by 27
  4. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
  5. 2022Delayed Feedback in Generalised Linear Bandits Revisitedcited by 23
  6. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  7. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  8. 2021Solving Multi-Arm Bandit Using a Few Bits of Communicationcited by 16
  9. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  10. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  11. 2023Delayed Feedback in Kernel Banditscited by 10
  12. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  13. 2022Linear Stochastic Bandits over a Bit-Constrained Channelcited by 9
  14. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  15. 2024Optimal Batched Linear Banditscited by 7
  16. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  17. 2026Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimescited by 6
  18. 2025Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexitycited by 5
  19. 2023Communication-Constrained Bandits under Additive Gaussian Noisecited by 4
  20. 2025Quantile Multi-Armed Bandits with 1-bit Feedbackcited by 4
  21. 2025Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewardscited by 4
  22. 2022The Impact of Batch Learning in Stochastic Linear Banditscited by 3
  23. 2023Sharp Noisy Binary Search with Monotonic Probabilitiescited by 3
  24. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  25. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis
  2. 2026Offline-to-Online Learning in Linear Bandits
  3. 2026Regret Analysis of Retry-Based Bandits
  4. 2026Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
  5. 2023ICQ: A Quantization Scheme for Best-Arm Identification Over Bit-Constrained Channels
  6. 2024Generalized Linear Bandits with Limited Adaptivity
  7. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
  8. 2026Gaussian-Width Bounds for Offline-to-Online Linear Bandits