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.

PDF, PS, HTML

In Proceedings of the 27th International Conference on Machine Learning (ICML 2010), 2010.

@InProceedings{kalyanakrishnan:icml10, title={Efficient Selection of Multiple Bandit Arms: Theory and Practice}, author={Shivaram Kalyanakrishnan and Peter Stone}, booktitle={Proceedings of the 27th International Conference on Machine Learning (ICML 2010)}, url="http://nn.cs.utexas.edu/?kalyanakrishnan:icml10", year={2010} }