Chen Wang, Rutgers University

Abstract

The multi-armed bandits (MABs) model has been studied extensively in theoretical computer science and machine learning. Motivated by modern large-scale applications, a recent line of work has focused on streaming multi-armed bandits. In this model, the arms arrive one after another in a streaming manner, and the algorithm only maintains a number of arms that is substantially smaller than the input. Any arm that is not stored or is discarded from the memory cannot be retrieved (unless we bring in another pass). 

In this talk, we will survey recent results for pure exploration and regret minimization in streaming MABs. For pure exploration, we will first give an efficient single-pass algorithm that finds the best arm with the information-theoretically optimal sample complexity and a memory of a single extra arm. We will then characterize the sample-memory trade-off in pure exploration for various single- and multi-pass settings. Finally, we will demonstrate the tight upper and lower bounds in the single-pass setting.

Part of the results are based on joint work with Sepehr Assadi and with Nikolai Karpov.

See: https://theory.cs.rutgers.edu/theory_seminar