The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits

2023/09/06 by Assadi, Sepehr, Wang, Chen
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2309.03145

Abstract

We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory that uses the optimal sample complexity of O((n)/(Δ²)) requires Ω(\fraclog(1/Δ)loglog(1/Δ)) passes. Here, n is the number of arms and Δ is the reward gap between the best and the second-best arms. Our result matches the O(log(\frac1Δ))-pass algorithm of Jin et al. [ICML'21] (up to lower order terms) that only uses O(1) memory and answers an open question posed by Assadi and Wang [STOC'20].

Related

• Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
• Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits
• On reducing the order of arm-passes bandit streaming algorithms under memory bottleneck
• Tight Memory-Regret Lower Bounds for Streaming Bandits
• Streaming Algorithms for Stochastic Multi-armed Bandits