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

2023/06/03 by Chen Wang, Wang, Chen · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2306.02208

openalex publication_date 2023/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 bound of Ω(T^2/3) has been proved for any algorithm with o(K) memory (Maiti et al. [NeurIPS'21]; Agarwal at al. [COLT'22]). On the other hand, however, the previous best regret upper bound is still O(K^1/3 T^2/3log^1/3(T)), which is achieved by the streaming implementation of the simple uniform exploration. The O(K^1/3log^1/3(T)) gap leaves the open question of the tight regret bound in the single-pass MABs with sublinear arm memory. In this paper, we answer this open problem and complete the picture of regret minimization in single-pass streaming MABs. We first improve the regret lower bound to Ω(K^1/3T^2/3) for algorithms with o(K) memory, which matches the uniform exploration regret up to a logarithm factor in T. We then show that the log^1/3(T) factor is not necessary, and we can achieve O(K^1/3T^2/3) regret by finding an ε-best arm and committing to it in the rest of the trials. For regret minimization with high constant probability, we can apply the single-memory ε-best arm algorithms in Jin et al. [ICML'21] to obtain the optimal bound. Furthermore, for the expected regret minimization, we design an algorithm with a single-arm memory that achieves O(K^1/3 T^2/3log(K)) regret, and an algorithm with O(log^*(n))-memory with the optimal O(K^1/3 T^2/3) regret following the ε-best arm algorithm in Assadi and Wang [STOC'20]. We further tested the empirical performances of our algorithms. The simulation results show that the proposed algorithms consistently outperform the benchmark uniform exploration algorithm by a large margin, and on occasion, reduce the regret by up to 70%.

Cited by

• Keeping Up with the Models: Online Deployment and Routing of LLMs at Scale

Related

• Tight Memory-Regret Lower Bounds for Streaming Bandits
• Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
• A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
• Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap