Short-lived High-volume Bandits

We study how to efficiently perform A/B/n testing for a high-volume of short-lived treatments. We formulate the problem as a multiple-play bandits model. In each round a set of k actions arrive. Each action is available for w rounds and has an unknown reward rate. In each round, the learner selects a multiset of n actions and immediately observes the realized rewards. We aim to minimize the average loss under a random input model where the instance is randomly drawn from a known prior distribution D. We show that if k = O(n ρ ) for some ρ > 0, our policy achieves Õ(n -minρ, 1 2 (1+ 1 w ) -1 ) average loss on a sufficiently large class of prior distributions. We also complement this result by showing that every policy suffers Ω(n -minρ, 1 2 ) average loss on the same class of distributions. We further validate the effectiveness of our policy through a large-scale field experiment on Glance, a content card-serving platform.