Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap

Nikolai Karpov, Chen Wang

We investigate the sample-memory-pass trade-offs for pure exploration in multi-pass streaming multi-armed bandits (MABs) with the *a priori* knowledge of the optimality gap $Δ_{[2]…