Maxing and Ranking with Few Assumptions

By Moein Falahatgar, Yi Hao, Alon Orlitsky, Venkatadheeraj Pichapati, V. Ravindrakumar. 2017

46 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Human Preferences as Dueling Bandits (2022, background): “For example, strategies that repeatedly compare two arms until a winner is found may require too many independent assessors to be feasible when arms are nearly equal [12, 13, 26].”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “We note that assumptions A1) to A3) are common in the literature (e.g., (Szörényi et al., 2015; Shah and Wainwright, 2017; Falahatgar et al., 2017a;b; 2018; Heckel et al., 2018; Katariya et al., 2018; Heckel et al., 2019; Saha and Gopalan, 2019a;b; Ren et al., 2019)).”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “For example, under SST, OPT-Maximize [16] achieves the minimax optimal rate for dueling bandits.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “Beyond ﬁxed-benchmark regret, notions involving Borda [Busa-Fekete and Hüllermeier, 2014; Jamieson et al., 2015; Falahatgar et al., 2017] and Copeland scores [Zoghi et al., 2015a; Komiyama et al., 2016; Wu and Liu, 2016] have also been considered.”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “…work in the PAC setting focuses on learning objectives other than identifying the single (near) best arm, e.g. recovering a few of the top arms (Busa-Fekete et al., 2013; Mohajer et al., 2017; Chen et al., 2017), or the true ranking of the items (Busa-Fekete et al., 2014b; Falahatgar et al., 2017).”
Active Ranking with Subset-wise Preferences (2018, background): “recovering a few of the top arms [10, 28, 13], or the true ranking of the items [12, 18].”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “1189 Knockout, Seq Elim, Single Elim: Knockout1190 (Falahatgar et al., 2017b), Sequential Elimination1191 (Falahatgar et al., 2017a), Single Elimination (Mo-1192 hajer et al., 2017) are all algorithms that proceed in1193 a knockout tournament fashion where the systems1194 are randomly paired, and…”