用少量比较选出最佳选项，适合预算紧张的推荐场景。
PARWiS: Winner determination under shoestring budgets using active pairwise comparisons
- 结合谱排序与破坏性配对选择，高效挖掘最优项。
- 在40~80次比较内，胜过基线方法，尤其在数据差异大时更优。
- 适合需要低成本决策的推荐系统或用户偏好评估任务。
在有限预算下，通过主动成对比较确定一组项目中的最优项是偏好学习中的难题。本文实现并评估了PARWiS算法，该算法结合谱排序与破坏性配对选择，在极低预算下识别最佳项目。研究还扩展了上下文变体（Contextual PARWiS）和基于强化学习的变体（RL PARWiS），并与双贝叶斯采样（Double Thompson Sampling）及随机选择策略对比。实验涵盖合成数据与真实数据集（Jester、MovieLens），在20个项目的设定下，分别使用40、60、80次比较。评估指标包括恢复分数、报告赢家的真实排名、真实赢家的报告排名以及累积遗憾，辅以分离度Δ_{1,2}。结果表明，PARWiS与RL PARWiS在所有数据集上均优于基线，尤其在Jester数据集（Δ_{1,2}较高）表现更显著；而在更难的MovieLens数据集（Δ_{1,2}较小）中性能差距缩小。上下文变体表现与PARWiS相当，说明上下文特征需进一步调优才能带来明显提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。