PARWiS: Winner determination under shoestring budgets using active pairwise comparisons

Shailendra Bhandari

cs.LGMar 1, 2026

PARWiS: Winner determination under shoestring budgets using active pairwise comparisons

Authors: Shailendra Bhandari

Organizations: Department of Computer Science OsloMet– Oslo Metropolitan University Oslo, Norway

Abstract

Determining a winner among a set of items using active pairwise comparisons under a limited budget is a challenging problem in preference-based learning. The goal of this study is to implement and evaluate the PARWiS algorithm, which shows spectral ranking and disruptive pair selection to identify the best item under shoestring budgets. This work have extended the PARWiS with a contextual variant (Contextual PARWiS) and a reinforcement learning-based variant (RL PARWiS), comparing them against baselines, including Double Thompson Sampling and a random selection strategy. This evaluation spans synthetic and real-world datasets (Jester and MovieLens), using budgets of 40, 60, and 80 comparisons for 20 items. The performance is measured through recovery fraction, true rank of reported winner, reported rank of true winner, and cumulative regret, alongside the separation metric $Δ_{1,2}$ . Results show that PARWiS and RL PARWiS outperform baselines across all datasets, particularly in the Jester dataset with a higher $Δ_{1,2}$ , while performance gaps narrow in the more challenging MovieLens dataset with a smaller $Δ_{1,2}$ . Contextual PARWiS shows comparable performance to PARWiS, indicating that contextual features may require further tuning to provide significant benefits.

Figures & tables

Panel of Figure 1 — Fig. 1: Dataset Visualizations: (a) Heatmap of the preference matrix for the Synthetic dataset ( $k=20$ ), showing pairwise probabilities $P_{i,j}$ . (b) Histogram of ratings for the 20 selected jokes in Jester, ranging from -10 to 10. (c) Histogram of ratings for the 20 selected movies in MovieLens, ranging from 0.5 to 5. (d) Boxplot of $\Delta_{1,2}$ for the Synthetic dataset across 30 runs, showing the distribution of problem difficulty.

Fig. 2: Performance on Synthetic Dataset at

B=40

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner. Plots for

B=60,80

are in Appendix -A , Figure 5 and 6 .

Fig. 3: Performance on Jester Dataset at

B=40

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner. Plots for

B=60,80

are in Appendix -A Figure 7 and 8 .

	Synthetic ( $\Delta_{1,2}=0.0152\pm 0.0190$ )			Jester ( $\Delta_{1,2}=0.0946\pm 0.0000$ )			MovieLens ( $\Delta_{1,2}=0.0008\pm 0.0000$ )
Agent	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$
Double TS	0.200	0.067	0.267	0.167	0.233	0.467	0.133	0.067	0.067
Random	0.033	0.067	0.000	0.033	0.000	0.067	0.033	0.000	0.067
PARWiS	0.467	0.467	0.467	0.467	0.467	0.467	0.167	0.167	0.167
Contextual PARWiS	0.367	0.367	0.367	0.433	0.433	0.433	0.167	0.167	0.167
RL PARWiS	0.367	0.367	0.367	0.467	0.467	0.467	0.100	0.100	0.100

TABLE I: Recovery fraction across datasets and budgets.

	Synthetic ( $\Delta_{1,2}=0.0152\pm 0.0190$ )			Jester ( $\Delta_{1,2}=0.0946\pm 0.0000$ )			MovieLens ( $\Delta_{1,2}=0.0008\pm 0.0000$ )
Agent	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$
Double TS	8.233	6.933	4.767	6.700	4.700	3.133	9.233	10.300	11.500
Random	10.767	10.367	10.733	10.733	9.367	10.733	9.233	11.033	10.767
PARWiS	3.233	3.233	3.233	2.067	2.067	2.067	6.633	6.633	6.633
Contextual PARWiS	3.900	4.067	4.067	2.233	2.233	2.233	6.633	6.633	6.633
RL PARWiS	3.533	3.533	3.533	2.067	2.067	2.067	6.667	6.667	6.667

TABLE II: True rank of reported winner across datasets and budgets.

	Synthetic ( $\Delta_{1,2}=0.0152\pm 0.0190$ )			Jester ( $\Delta_{1,2}=0.0946\pm 0.0000$ )			MovieLens ( $\Delta_{1,2}=0.0008\pm 0.0000$ )
Agent	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$
Double TS	35.300	52.933	67.267	34.067	51.167	67.667	36.733	55.767	74.800
Random	36.633	54.833	73.200	36.167	54.233	72.600	37.733	56.767	75.800
PARWiS	11.733	22.000	33.133	9.567	17.600	25.633	18.067	35.100	52.333
Contextual PARWiS	13.067	24.333	35.467	10.167	18.533	27.200	18.100	35.133	52.367
RL PARWiS	14.367	26.300	42.300	11.100	21.667	32.400	19.567	38.633	56.967

TABLE III: Cumulative regret across datasets and budgets.

Fig. 4: Performance on MovieLens dataset at

B=40

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner. Plots for

B=60,80

are in Appendix -A Figure 9 and 10 .

Fig. 5: Performance on Synthetic Dataset at

B=60

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 6: Performance on Synthetic Dataset at

B=80

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 7: Performance on Jester Dataset at

B=60

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 8: Performance on Jester Dataset at

B=80

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 9: Performance on MovieLens Dataset at

B=60

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 10: Performance on MovieLens Dataset at

B=80

. From left to right: Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, Reported Rank of True Winner.

Fig. 11: Distribution of final metric values for Synthetic dataset across runs at budgets

B=40,60,80

. Metrics include Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, and Reported Rank of True Winner.

Panel of Figure 15 — Fig. 12: Distribution of final metric values for Jester dataset across runs at budgets $B=40,60,80$ . Metrics include Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, and Reported Rank of True Winner.

Panel of Figure 16 — Fig. 13: Distribution of final metric values for MovieLens dataset across runs at budgets $B=40,60,80$ . Metrics include Cumulative Regret, Recovery Fraction, True Rank of Reported Winner, and Reported Rank of True Winner.

	Synthetic ( $\Delta_{1,2}=0.0152\pm 0.0190$ )						Jester ( $\Delta_{1,2}=0.0946\pm 0.0000$ )
	$B=40$		$B=60$		$B=80$		$B=40$		$B=60$		$B=80$
Agent	Fail	Avg TR	Fail	Avg TR	Fail	Avg TR	Fail	Avg TR	Fail	Avg TR	Fail	Avg TR
Double TS	0.800	10.042	0.933	6.929	0.733	6.136	0.833	7.840	0.767	6.304	0.533	5.250
Random	0.967	11.103	0.933	10.357	1.000	10.733	0.967	11.069	1.000	9.367	0.933	11.071
PARWiS	0.533	5.188	0.533	5.188	0.533	5.188	0.533	3.000	0.533	3.000	0.533	3.000
Contextual PARWiS	0.633	5.842	0.633	5.842	0.633	5.842	0.567	3.176	0.567	3.176	0.567	3.176

TABLE IV: Error analysis across synthetic and Jester datasets.

	Synthetic ( $\Delta_{1,2}=0.0152\pm 0.0190$ )			Jester ( $\Delta_{1,2}=0.0946\pm 0.0000$ )			MovieLens ( $\Delta_{1,2}=0.0008\pm 0.0000$ )
Agent	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$
PARWiS	4.400	4.267	4.267	2.333	2.333	2.333	7.833	7.833	7.267
Contextual PARWiS	4.433	4.233	4.233	2.000	1.967	2.000	8.400	8.333	8.333
RL PARWiS	5.333	5.433	5.433	2.633	3.133	3.133	9.100	9.100	9.567

TABLE V: Reported rank of true winner across datasets and budgets.

	MovieLens ( $\Delta_{1,2}=0.0008\pm 0.0000$ )
	$B=40$		$B=60$		$B=80$
Agent	Fail	Avg TR	Fail	Avg TR	Fail	Avg TR
Double TS	0.833	9.920	0.933	11.036	0.933	12.250
Random	0.967	9.552	1.000	11.033	0.933	11.500
PARWiS	0.833	7.760	0.833	7.760	0.833	7.760
Contextual PARWiS	0.833	7.760	0.833	7.760	0.833	7.760

TABLE VI: Error analysis across the MovieLens dataset.

	Synthetic			Jester			MovieLens
Budget	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$	$B=40$	$B=60$	$B=80$
t-stat	-2.246	-3.862	-1.616	-2.594	-1.921	0.000	-0.356	-1.201	-1.201
p-value	0.029	0.000	0.112	0.012	0.060	1.000	0.723	0.235	0.235

TABLE VII: Selected t-test results (Double TS vs. PARWiS, Recovery) across datasets and budgets.

Explore similar work

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
Oct 7, 2026Shashaank Aiyer, Han ShaoPairwise Ranking Pairwise Preference Learning
University of Maryland
Active Learners as Efficient PRP Rerankers
May 14, 2026Jeremías Figueiredo Paschmann, Juan Kaplan, Francisco Nattero +3Pairwise Preference Learning Pairwise Comparison
ELIAS Lab, Departamento de Ingeniería, Universidad de San Andrés
Learning Preference from Observed Rankings
Feb 18, 2026Yu-Chang Chen, Chen Chian Fuh, Shang En TsaiUser Preference Modeling Pairwise Preference Learning
National Taiwan University

Oct 7, 2026J/K move · Enter open · S save

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

Shashaank Aiyer, Han Shao

University of Maryland

Pairwise Ranking Pairwise Preference Learning Sample Complexity Bradley–Terry Model

Open paper AskPDF arXiv

We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires

Ω(1/Δ^2)

repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using

O(\log(1/Δ))

repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only

O(1)

comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.

Abstract

Explore similar work

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

Active Learners as Efficient PRP Rerankers

Learning Preference from Observed Rankings