A Simple and General Approach to top-k Selection
Abstract
This paper considers the Bayesian top-k identification problem, wherein a decision maker is tasked with selecting k items from a pool of items of unknown quality. To assess the items, the decision maker adaptively allocates a fixed sampling budget, where each sample of an item yields a noisy observation of its quality, with the objective of minimizing the expected opportunity cost of the selected set. We propose an approach that allocates each batch of samples by minimizing a surrogate objective derived from an upper bound on the expected opportunity cost. The approach is general: samples can be allocated in batches, the selection size k is arbitrary, and it applies to many sampling distributions. It is also simple and intuitive. We prove that the method's posterior expected opportunity cost decays at an exponential rate of at least half the best rate achievable by any sampling rule. In simulations across a wide range of settings, the method is competitive with, and often improves upon, the best existing algorithm in each setting.
Related
- Squaring Up by Selection: NP-Completeness at Three Simple Roots
- A simple construction of a simple nil ring
- Simple Cuts, Simple Landscape: Dimension-Free Rank Bounds for Burer-Monteiro Factorizations via Rank-Width
- Periodically kicked feedforward chains of simple excitable FitzHugh–Nagumo neurons
- Finding Simple Proofs for First-Order Optimization
BibTeX
@misc{goldberger2026simple,
title = {{A Simple and General Approach to top-$k$ Selection}},
author = {Motti Goldberger and Nils Rudi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26407},
eprint = {2610.26407},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26407},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Simple and General Approach to top-k Selection
AU - Motti Goldberger
AU - Nils Rudi
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.26407
UR - https://arxiv.org/abs/2610.26407
AB - This paper considers the Bayesian top-k identification problem, wherein a decision maker is tasked with selecting k items from a pool of items of unknown quality. To assess the items, the decision maker adaptively allocates a fixed sampling budget, where each sample of an item yields a noisy observation of its quality, with the objective of minimizing the expected opportunity cost of the selected set. We propose an approach that allocates each batch of samples by minimizing a surrogate objective derived from an upper bound on the expected opportunity cost. The approach is general: samples can be allocated in batches, the selection size k is arbitrary, and it applies to many sampling distributions. It is also simple and intuitive. We prove that the method's posterior expected opportunity cost decays at an exponential rate of at least half the best rate achievable by any sampling rule. In simulations across a wide range of settings, the method is competitive with, and often improves upon, the best existing algorithm in each setting.
ER -