Efficient Selection of Multiple Bandit Arms: Theory and Practice (2010)
We consider the general, widely applicable problem of selecting from n real-valued random variables a subset of size m of those with the highest means, based on as few samples as possible. This problem, which we denote Explore-m, is a core aspect in several stochastic optimization algorithms, and applications of simulation and industrial engineering. The theoretical basis for our work is an extension of a previous formulation using multi-armed bandits that is devoted to identifying just the one best of n random variables (Explore-1). In addition to providing PAC bounds for the general case, we tailor our theoretically grounded approach to work efficiently in practice. Empirical comparisons of the resulting sampling algorithm against state-of-the-art subset selection strategies demonstrate significant gains in sample efficiency.
View:
PDF, PS, HTML
Citation:
In Proceedings of the 27th International Conference on Machine Learning (ICML 2010) 2010.
Bibtex:

Shivaram Kalyanakrishnan Ph.D. Alumni shivaram [at] cs utexas edu
Peter Stone Faculty pstone [at] cs utexas edu