Linear Streaming Bandit: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification

Abstract

Recently, there has been a focus on the streaming setting in a line of works on the Multi-Armed Bandit (MAB). In this scenario, a large number of arms arrive in a streaming manner, and the algorithm scans through the stream and stores some arms in its limited processing memory. We advance this line of research by introducing the Linear Streaming Bandit setup, where the arriving arms have profile vectors observable to the algorithm. The profile of an arm has a linear correlation with the expected reward. This setup is motivated by real-world applications, such as when a company or a crowdsourcing platform hires a worker from many sequentially arriving applicants with their resumes. We address two problems in this setup: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification. For the former, we propose an algorithm whose regret is independent of the number of arms, thus it is able to handle arbitrarily long arm streams. For the latter, we present a multi-pass algorithm whose error probability is sub-linear w.r.t. the number of arms, and an algorithm identifying the exact best arm in only a single pass. We validate the effectiveness of all proposed algorithms through experiments on both synthetic and real-world datasets.