PARWiS: Winner determination under shoestring budgets using active pairwise comparisons

Shailendra Bhandari · 2026

Read PARWiS: Winner determination under shoestring budgets using active pairwise comparisons by Shailendra Bhandari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-01171.txt.

Introduction

Bhandari implements and tests PARWiS, a method for picking a winner from pairwise comparisons on a shoestring budget. Spectral ranking plus disruptive pair selection identifies the best item cheaply, with contextual and reinforcement-learning variants compared against double Thompson sampling and random choice. Across synthetic and real sets with budgets of 40, 60, and 80 comparisons for 20 items, PARWiS and its RL variant beat baselines, most clearly on Jester. The contextual variant merely matches PARWiS.

Catalog record

CREATORShailendra Bhandari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42048
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.01171

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

PARWiS: Winner determination under shoestring budgets using active pairwise comparisons Shailendra Bhandari 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 \Delta_{1,2} . Results show that PARWiS and RL PARWiS outperform baselines across all datasets, particularly in the Jester dataset with a higher Δ 1 , 2 \Delta_{1,2} , while performance gaps narrow in the more challenging MovieLens dataset with a smaller Δ 1 , 2 \Delta_{1,2} . Contextual PARWiS shows comparable performance to PARWiS, indicating that contextual features may require further tuning to provide significant benefits. I Introduction Preference-based learning through pairwise comparisons is a powerful approach for ranking and winner determination in applications such as recommender systems, social choice, and information retrieval [ 1 , 2 ] . However, in real-world scenarios, the number of comparisons is often constrained by a limited budget, known as a shoestring budget. Sheth and Rajkumar [ 3 ] introduced PARWiS (Pairwise Active Recovery of Winner under a Shoestring budget), an algorithm designed to efficiently determine the winner under such constraints using spectral ranking and a disruptive pair selection strategy. In this work, PARWiS has been implemented and extended it with two variants: Contextual PARWiS, inspired by Bengs et al. [ 4 , 5 ] , to incorporate item features when available, and RL PARWiS, a reinforcement learning-based approach that uses Q-learning to optimize pair selection. these algorithms has been compared against two baselines: Double Thompson Sampling (Double TS) [ 6 ] and a random pair selection strategy. The evaluation uses synthetic data generated via the Bradley-Terry (BT) model, as well as real-world datasets: Jester [ 7 ] and MovieLens 20M [ 8 ] . The performance has been ascessed across three shoestring budgets (40, 60, and 80 comparisons for 20 items) using metrics from [ 3 ] : recovery fraction, true rank of reported winner, reported rank of true winner, and cumulative regret. Additionally, the separation metric \Delta_{1,2} is computed to analyze problem difficulty and perform statistical tests to assess the significance of performance differences. The results demonstrate that PARWiS and RL PARWiS consistently outperform the baselines in terms of recovery fraction and cumulative regret, particularly on the Jester dataset, where a higher \Delta_{1,2} indicates an easier problem. On the more challenging MovieLens dataset with a smaller \Delta_{1,2} , PARWiS and RL PARWiS still perform better but with a narrower margin. Contextual PARWiS performs similarly to PARWiS, suggesting that the contextual features used (available only in synthetic data) may require further optimization. Statistical tests confirm that PARWiS and RL PARWiS’s improvements over baselines are significant, while error analysis reveals that RL PARWiS fails closer to the true winner compared to other agents. II Related work The problem of winner determination and ranking through pairwise comparisons has been extensively studied in the dueling bandits framework, which bridges multi-armed bandits and preference-based learning. This framework is particularly relevant in applications such as recommender systems, social choice, and information retrieval, where direct numerical feedback is often unavailable, and preferences must be inferred through comparisons. Below, we review key developments in dueling bandits, active learning for ranking, contextual extensions, and the use of real-world datasets for evaluation. II-A Dueling bandits and regret minimization The dueling bandits framework was introduced to model scenarios where feedback is relative rather than absolute, typically in the form of pairwise comparisons. Early work by Yue et al. [ 9 ] formalized the k -armed dueling bandits problem, focusing on regret minimization. They proposed algorithms like the Interleaved Filter, which balances exploration and exploitation by maintaining a set of potential winners and refining it through comparisons. Their regret bounds scale with the number of arms and the comparison budget, but the approach assumes a Condorcet winner exists, which may not hold in all settings. 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. Subsequent works extended this framework to handle more complex preference structures. Zoghi et al. [ 10 ] introduced the Relative Upper Confidence Bound (RUCB) algorithm, which adapts the Upper Confidence Bound (UCB) strategy to dueling bandits. RUCB maintains confidence intervals over pairwise preferences and selects pairs that maximize the potential for reducing uncertainty about the winner. While RUCB achieves sublinear regret, it requires a large number of comparisons to converge, making it less suitable for shoestring budgets. Sparse Borda [ 11 ] further refines this approach by incorporating sparsity conditions in the pairwise comparison matrix to eliminate suboptimal items early. This algorithm targets the Borda winner (the item with the highest average preference score), which aligns with the Bradley-Terry-Luce (BTL) winner in our setting. However, its performance under shoestring budgets is limited, as shown by Sheth and Rajkumar [ 3 ] , due to insufficient comparisons to accurately estimate the sparse structure. II-B Active learning for ranking and winner determination Active learning approaches aim to minimize the number of comparisons needed to rank items or identify the top- k items. Jamieson and Nowak [ 12 ] proposed an active ranking algorithm that models items as embeddings in a d -dimensional Euclidean space, using geometric properties to select informative pairs. While effective for noiseless comparisons, their method struggles with noisy models like BTL, which is central to our study. Mohajer et al. [ 13 ] introduced SELECT, a single-elimination tournament algorithm for top- k rank aggregation. Select pairs of items randomly at each layer, promoting winners to the next layer until the top- k items are identified. The algorithm is extended to handle shoestring budgets by repeating comparisons within layers, but its random pairing strategy limits its efficiency, as noted in [ 3 ] . Heckel et al. [ 14 ] proposed Active Ranking (AR), a generic framework for full ranking and winner determination. AR maintains confidence scores for items, partitioning them into bins to focus comparisons on uncertain pairs. While AR performs well with parametric assumptions (e.g., BTL), it requires more comparisons than shoestring budgets typically allow, making it less competitive in our setting. Sheth and Rajkumar [ 3 ] introduced PARWiS (Pairwise Active Recovery of Winner under a Shoestring budget), specifically targeting winner determination under constrained budgets. PARWiS leverages spectral ranking

Read the complete text