On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs

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.