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%.