Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls and Efficient Bregman Projections onto the Permutahedron and Related Polytopes

Talk 1 – Kwang-Sung Jun: Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls

We introduce a new multi-armed bandit (MAB) problem in which arms must be sampled in batches, rather than one at a time. This is motivated by applications in social media monitoring and biological experimentation where such batch constraints naturally arise. We develop and analyze algorithms for batch MABs and top arm identification, for both fixed confidence and fixed budget settings. The main theoretical results show that the batch constraint does not significantly affect the sample complexity of top arm identification compared to unconstrained MAB algorithms. Alternatively, if one views a batch as the fundamental sampling unit, then the results can be interpreted as showing that the sample complexity of batch MABs can be significantly less than traditional MABs. We demonstrate the new batch MAB algorithms with simulations and in two interesting real-world applications: (i) microwell array experiments for identifying genes that are important in virus replication and (ii) finding the most active users in Twitter on a specific topic.

Talk 2 – Cong Han Lim : Efficient Bregman Projections onto the Permutahedron and Related Polytopes

Computing the projection onto a permutahedron PH(c) — the convex hull of all permutations of a fixed vector c — is an important step for some algorithms in machine learning. This includes algorithms for online learning over rankings and algorithms for OWL-regularized problems. The projection problem (under any uniformly separable Bregman divergence) can be reduced to the Isotonic Optimization problem, which allows one to employ known fast algorithms to improve on several recent results on Bregman projections onto permutahedra. We develop two new algorithms that have better complexity when the number of distinct entries d in the vector c is small, the simplex being one such example with c = (1,0,0,…,0) and d = 2. One algorithm runs in O(n log d) for certain popular Bregman divergence measures, while the other requires O(n log (dU/epsilon)) to find epsilon-close solutions for general uniformly separable Bregman divergences, where U is a bound on the width of the interval containing the dual solution components. These match or improve best known bounds for all Bregman projection problems onto various permutahedra, including recent results for Bregman projection onto the simplex.

Joint work with Stephen Wright.