UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
Efficient Selection of Multiple Bandit Arms: Theory and Practice (2010)
Shivaram Kalyanakrishnan
and
Peter Stone
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:
@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://www.cs.utexas.edu/users/ai-lab?kalyanakrishnan:icml10", year={2010} }
People
Shivaram Kalyanakrishnan
Ph.D. Alumni
shivaram [at] cs utexas edu
Peter Stone
Faculty
pstone [at] cs utexas edu
Areas of Interest
Machine Learning
Labs
Learning Agents