Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits

Chen Wang

Regret minimization in streaming multi-armed bandits (MABs) has been studied extensively in recent years. In the single-pass setting with $K$ arms and $T$ trials, a regret lower bo…