On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs Wei Cao Jian Li1 Yufei Tao

This paper discusses how to efficiently choose from n unknown distributions the k ones whose means are the greatest by a certain metric, up to a small relative error. We study the topic under two standard settings--multi-armed bandits and hidden bipartite graphs--which differ in the nature of the input distributions. In the former setting, each distribution can be sampled (in the i.i.d.