Research map / Bandits and online learning / Multi-armed bandits

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies batched stochastic linear bandits where each batch of B pulls yields only one bit of feedback from a batch-wise memoryless agent, proving a Omega(B min{d, log|A|}) lower bound and two phased-elimination algorithms with near-matching regret.

Problem

Stochastic linear bandits when the agent must compress B rewards of each batch into a single bit and cannot retain memory across batches, so communication is limited to one bit per batch.

Approach

Combines batching with a 1-bit per-batch uplink: the learner chooses the 1-bit quantizer per batch, and the agent's bit is used for 1-bit mean estimation (localization plus refinement via threshold queries) inside phased elimination with G-optimal designs; a safe-arm tournament and warm start handle large batch sizes.

Key results

• Minimax lower bound Omega(min{T, B min(d, log|A|)}) holds even with noiseless rewards, showing the 1-bit bottleneck alone forces the cost.
• First algorithm achieves O~(dB + d sqrt(T)) regret independent of |A|, matching the general lower bound up to logs when |A| = exp(Omega(d)).
• Second algorithm achieves O~(B log|A| + d^{3/2} sqrt(B) + sqrt(dT log|A|)) regret for polynomial-size action sets, near-optimal in broad regimes; the gap to the lower bound is at most O~(sqrt(d)) in remaining regimes.

Surprising findings

• A single bit per batch of length sqrt(T) suffices to nearly match unconstrained minimax regret of linear bandits.

Limitations

• Gap remains for some regimes (e.g., T < d^2 B and B < d^3), where regret is up to sqrt(d) times the lower bound.
• Second algorithm's bound includes a d^{3/2} sqrt(B) initialization penalty; the first algorithm's dB term grows with batch size for large action sets.
• Assumes memoryless agent per batch and sigma = Theta(1); analysis is theoretical with no experiments.

Experimental setup

Metrics: expected cumulative regret high-probability regret

Baselines: Phased elimination with unquantized rewards delayed-feedback linear bandit (regret B + sqrt(dT min{d,log|A|})) Mitra et al. style quantized bandits (few bits per pull)

Builds on: phased elimination G-optimal design (Frank-Wolfe) 1-bit mean estimation (Cao and Gu-style) median-of-means Fano's inequality

Closest papers by meaning

• Regret Bounds for Batched Bandits (AAAI 2021 · similarity 0.92)
• Optimal Batched Linear Bandits (ICML 2024 · similarity 0.92)
• Optimal and Practical Batched Linear Bandit Algorithm (ICML 2025 · similarity 0.92)
• Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.89)
• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
• Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)