Choosing the best k items from a pool of unknown quality is a common problem, but noisy observations make it costly. Goldberger and Rudi frame it as Bayesian top-k identification: a decision maker spends a fixed sampling budget adaptively, with each sample giving a noisy signal of an item's quality, and wants to minimize the expected opportunity cost of the selected set.
Their method is simple: each batch of samples is allocated by minimizing a surrogate objective derived from an upper bound on expected opportunity cost. It handles arbitrary k, batched sampling, and many sampling distributions. The authors prove that the posterior expected opportunity cost decays exponentially, at a rate at least half the best rate any sampling rule can achieve.
In simulations across a wide range of settings, the approach is competitive with, and often better than, the best existing algorithm for each setting. Because the method is general and intuitive, it offers a practical alternative to bespoke top-k selection rules.