Research map / Bandits and online learning / Multi-armed bandits
Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification
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.
Introduces the Linear Streaming Bandit setting, with multi-pass regret minimization (CR-MPS) and fixed-budget epsilon-best arm identification algorithms (G-MP-SE, SPC) for arms arriving as a stream with observable profile vectors.
Problem
Multi-armed bandits where a very large number of arms arrive in a stream with limited memory; the goal is regret minimization and fixed-budget epsilon-best arm identification when arm profiles linearly determine expected reward.
Approach
Exploit observable arm profile vectors under a linear reward model: a first pass uses coarse precision to discard clearly sub-optimal arms from their profiles without pulling them, and later passes refine precision (CR-MPS); for fixed-budget BAI, discretize the arm space into a grid with counters so memory is independent of the number of arms (G-MP-SE), plus a single-pass comparison method (SPC).
Key results
- CR-MPS regret upper bound is independent of the number of arms K, scaling as Õ(T^{2B/(2B+1-1)}) with B passes, approaching Ω(√T) as B grows.
- G-MP-SE error probability scales with K^{1/(B-2)} (sub-linear in K for B>2), versus linear in K for OD-LinBAI.
- On synthetic and real Kaggle data (K=10k), CR-MPS keeps regret converging while baselines MBSE and MPSE fail to converge at large K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CR-MPS for multi-pass regret minimization with confidence-radius-directed sampling | Linear Streaming Bandit · Regret minimization | pseudo-regret | Helped |
| Increase the number of passes B in CR-MPS | CR-MPS · Regret minimization | pseudo-regret scaling with T | Helped |
| Use G-MP-SE with multiple passes and grid-based elimination | Linear Streaming Bandit · Fixed-budget ϵ-best arm identification | error probability dependence on K | Helped |
| Use SPC for single-pass strict best arm identification | Linear Streaming Bandit · Strict best arm identification | number of passes | Helped |
| Use CR-MPS instead of MBSE and MPSE | Synthetic dataset · Regret minimization | regret | Helped |
| Use CR-MPS instead of MBSE and MPSE | Kaggle employee performance dataset · Regret minimization | regret | Helped |
Limitations
- Matching lower bounds for both tasks are not established.
- Regret bound for CR-MPS requires T above some N0 and the G-MP-SE bound holds in the limit eps to 0.
- Baselines in experiments are not designed for the streaming setting with large K; experiments limited to a single real dataset.
Experimental setup
Datasets: synthetic linear bandit instances Kaggle Employee's Performance for HR Analytics dataset (10k workers subset)
Benchmarks: synthetic linear streaming bandit instances Kaggle HR employee performance dataset
Metrics: pseudo-regret error probability
Baselines: MBSE MPSE
Builds on: OFUL OD-LinBAI streaming bandit algorithms (Agarwal, Khanna, and Patil 2022) Jin et al. 2021 streaming BAI
Closest papers by meaning
- Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.91)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.90)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)
- Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · similarity 0.88)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.88)
- Optimal Multi-Fidelity Best-Arm Identification (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.