A Simple and General Approach to top-$k$ Selection

Motti Goldberger; Nils Rudi

cs.LGOct 19, 2026

A Simple and General Approach to top- $k$ Selection

Authors: Motti Goldberger, Nils Rudi

Organizations: Yale School of Management

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.

Figures & tables

Figure 1: Structure of the surrogate loss $\mathcal{L}_{t}(\cdot)$ and allocation for $I=3$ , $k=1$ using $q(t)=q^{*}(t)$ . For each item $i\in\{A,B,C\}$ , the left distribution is its current prior for $\theta_{i}$ , and the right is the posterior moment-matched distribution $\mathaccent 155{\theta}_{i}(\Delta_{i})$ . The allocation shown minimizes ( 8 ) with $B_{t}=10$ . The shaded area is the item’s contribution to the loss.

Figure 2: Budget allocation across items on the Gaussian instance described in Section 5 , with $I=20$ at $k=3,5,10$ . The plots show the proportion of the total budget spent on each item, with items ordered by their true mean. TEAk uses $q^{*}(t)$ . The dashed line marks the top- $k$ boundary.

Figure 3: Left: TEAk’s sampling proportions at $t=$20,000$$ , averaged over replications, as well as $\bm{w}(q^{\dagger})$ and $\bm{w}^{*}$ . Middle: $-\log\mathrm{EOC}(\mathcal{H}_{t})/(t\,\Gamma^{*}(\bm{\theta}^{0}))$ for TEAk, the oracle allocation, and equal allocation on each of the $50$ replications (median in bold). Right: the threshold $q^{\dagger}(t)$ on each of the $50$ replications (median in bold). — Figure 3: Left: TEAk’s sampling proportions at $t=$ 20,000$$ , averaged over replications, as well as $\bm{w}(q^{\dagger})$ and $\bm{w}^{*}$ . Middle: $-\log\mathrm{EOC}(\mathcal{H}_{t})/(t\,\Gamma^{*}(\bm{\theta}^{0}))$ for TEAk, the oracle allocation, and equal allocation on each of the $50$ replications (median in bold). Right: the threshold $q^{\dagger}(t)$ on each of the $50$ replications (median in bold).

Likelihood $Y_{i,n}\mid\theta_{i}$	Distribution of true means $\theta_{i}$
$N(\theta_{i},1)$	$\mathrm{Unif}(-2,2)$	$\mathrm{Unif}(-1,1)$	$\mathrm{Unif}(-0.5,0.5)$
$\mathrm{Exp}(1/\theta_{i})$	$\mathrm{Unif}(1,9)$	$\mathrm{Unif}(1,5)$	$\mathrm{Unif}(1,3)$
$\mathrm{Bern}(\theta_{i})$	$\mathrm{Unif}(0.05,0.95)$	$\mathrm{Unif}(0.2,0.8)$	$\mathrm{Unif}(0.35,0.65)$
$\mathrm{Lognormal}(\log\theta_{i}\!-\!1/2,\,1)$	$\mathrm{Unif}(1,9)$	$\mathrm{Unif}(1,5)$	$\mathrm{Unif}(1,3)$

Table 1: The four likelihood families and the three distributions used to generate the true means.

Figure 4: % difference in PCS between benchmarks and TEAk at budget $$1,000$\!\cdot\!I$ (positive means benchmark is better). — Figure 4: % difference in PCS between benchmarks and TEAk at budget $$1,000 $\!\cdot\!I$ (positive means benchmark is better).

Figure 5: The distribution across all settings in Figure 4 for the four strongest benchmarks and TEAk- $q^{\dagger}(t)$ .

Figure 6: Gaussian: EOC (log scale) against budget (max budget $=$1,000$\!\cdot\!I$ ). Rows vary the problem size $I$ and columns vary $k$ . — Figure 6: Gaussian: EOC (log scale) against budget (max budget $=$ 1,000 $\!\cdot\!I$ ). Rows vary the problem size $I$ and columns vary $k$ .

Figure 7: PCS at the final budget of $50\!\cdot\!I$ against the batch size for the Gaussian (top) and Bernoulli (bottom) families with $k=5$ .

Appendix figures & tables24 assets

Supplementary material from the paper’s appendix.

Appendix

Likelihood $Y_{i,n}\mid\theta_{i}$	Distribution of true means $\theta_{i}$
$N(\theta_{i},1)$	$\mathrm{Unif}(-2,2)$	$\mathrm{Unif}(-1,1)$	$\mathrm{Unif}(-0.5,0.5)$
$\mathrm{Exp}(1/\theta_{i})$	$\mathrm{Unif}(1,9)$	$\mathrm{Unif}(1,5)$	$\mathrm{Unif}(1,3)$
$\mathrm{Bern}(\theta_{i})$	$\mathrm{Unif}(0.05,0.95)$	$\mathrm{Unif}(0.2,0.8)$	$\mathrm{Unif}(0.35,0.65)$
$\mathrm{Lognormal}(\log\theta_{i}\!-\!1/2,\,1)$	$\mathrm{Unif}(1,9)$	$\mathrm{Unif}(1,5)$	$\mathrm{Unif}(1,3)$

Appendix

Table 9

Figure 8: Bernoulli: same format as Figure 6 .

Figure 9: Exponential: same format as Figure 6 .

Figure 10: Lognormal: same format as Figure 6 .

Adaptive Sampling

Adaptive sampling allocates limited data, measurements, or computation where they are expected to be most useful.

See all 202 papers

Optimal Top- $k$ Identification from Pairwise Comparisons
Jul 9, 2026Motti Goldberger, Nils RudiPairwise Preference Learning Multi-Armed Bandits
Yale University, New Haven, CT, USA.
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
Oct 14, 2026Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan +4Gaussian Process Bandits Adaptive Sampling
University of Arizona · POSTECH CSE/GSAI · Meta Inc.
Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
Aug 12, 2026Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski +2Streaming Algorithms
Jagiellonian University

Jul 9, 2026J/K move · Enter open · S save

Optimal Top- $k$ Identification from Pairwise Comparisons

Motti Goldberger, Nils Rudi

Yale University, New Haven, CT, USA.

Pairwise Preference Learning Multi-Armed Bandits Pairwise Comparison Pairwise Preference Evaluation Pairwise Ranking Best-Arm Identification+1

Open paper AskPDF arXiv

We study the active learning problem of fixed-confidence top-

k

identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-

k

items with error probability at most

δ

. The objective is to design such a

δ

-correct procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as

δ\to 0

. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-

1

, or more generally top-

k

identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal-dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal-dual procedure and prove it is asymptotically optimal.

Abstract

Adaptive Sampling

Explore similar work

Optimal Top-kkk Identification from Pairwise Comparisons

Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection

Optimal Top- $k$ Identification from Pairwise Comparisons