Reproduce “Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap” on OpenResearch

About this paper

Nikolai Karpov, Chen Wang

This paper establishes nearly tight upper and lower bounds for pure exploration in multi-pass streaming multi-armed bandits when the optimality gap between the best and second-best arm (Δ[2]) is known. Researchers from Indiana University, Rice University, and Texas A&M University demonstrate that Ω(log n / log log n) passes are necessary for sublinear memory, while an algorithm achieves Õ(∑(1/Δ[i]²)) sample complexity with O(log n) passes and single-arm memory.

Key insights

• Even with prior knowledge of Δ[2], achieving instance-optimal sample complexity in streaming MABs with sublinear memory fundamentally requires a pass complexity of approximately Θ(log n).
• The knowledge of Δ[2] shifts the lower bound dependency from terms related to inverse polynomial of Δ[2] to terms related to n (e.g., log n), indicating a distinct challenge compared to scenarios where Δ[2] is unknown.
• The developed algorithm demonstrates that a highly memory-efficient, multi-pass approach can match the established lower bounds, offering a practical pathway for large-scale online learning systems under memory constraints.

Summary by alphaXiv.