Generic Exploration and K-armed Voting Bandits

By Tanguy Urvoy, Fabrice Clérot, Raphaël Féraud, Sami Naamane. 2013

111 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 Reinforcement Learning

Citations in the corpus

Contextual Dueling Bandits (2015, background): “Two of these are the Borda winner, the action that has the highest probability of winning a duel against a uniformly random action; and the Copeland winner, the action that wins the most pairwise comparisons (Urvoy et al., 2013).”
Active Ranking with Subset-wise Preferences (2018, background): “…models, such as those satisfying stochastic triangle inequalities and strong stochastic transitivity [Yue and Joachims, 2011], general utility-based preference models [Urvoy et al., 2013], the Plackett-Luce model [Sz¨or´enyi et al., 2015] and the Mallows model [Busa-Fekete et al., 2014a]].”
Maximum Selection and Ranking under Noisy Comparisons (2017, methodology): “And (Urvoy et al., 2013; Busa-Fekete et al., 2014b; Heckel et al., 2016) considered general comparison probabilities, without an underlying ranking assumption, and derived rankings based on Copeland- and Borda-counts, and random-walk procedures.”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “Experimental study of dueling 580 bandit algorithms have been limited to synthetic 581 simulations in a few works (Yue and Joachims, 582 2011; Urvoy et al., 2013).”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “We first propose the D-TS algorithm for general Copeland bandits, and show that it achieves O(K2 log T ) regret.”
Relative confidence sampling for efficient on-line ranker evaluation (2014, methodology): “Several algorithms have been proposed for this setting, including interleaved ﬁlter (IF) [37], beat the mean (BTM) [36], and sensitivity analysis of variables for generic exploration (SAVAGE) [32].”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, background): “[43] consider a setup similar to the one in [11].”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, unknown): “Other algorithms proposed for this problem are Interleaved Filter (IF) (Yue et al., 2012), Beat the Mean (BTM) (Yue & Joachims, 2011), and SAVAGE (Urvoy et al., 2013).”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “…descent (Yue and Joachims, 2009) Multiple-Point gradient descent (Zhao and King, 2016) Stochastic mirror descent (Kumagai, 2017) Voting bandits (Urvoy et al., 2013) Copeland conﬁdence bound (Zoghi et al., 2015a) Copeland winners relative minimum empirical divergence (Komiyama et al., 2016)…”
MergeDTS (2018, background): “, Borda winner [27, 46], Copeland winner [32, 53], von Neumann”
MergeRUCB: A Method for Large-Scale Online Ranker Evaluation (2015, methodology): “One version of SAVAGE, which we call Condorcet SAVAGE, assumes only the existence of a Condorcet winner and performed the best experimentally [28].”
Copeland Dueling Bandits (2015, methodology): “Most previous work assumes the existence of a Condorcet winner [10]: an arm, which without loss of generality we label a1, such that p1i > 12 for all i > 1.”
PAC Battling Bandits in the Plackett-Luce Model (2018, methodology): “…satisfying stochastic triangle inequalities and strong stochastic transitivity (Yue and Joachims, 2011), general utility-based preference models (Urvoy et al., 2013), the Plackett-Luce model (Sz¨or´enyi et al., 2015), the Mallows model (Busa-Fekete et al., 2014a), etc. Recent work in the PAC…”
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem (2015, background): “As is well known in the field of voting theory, there are several other criteria of winners that are incompatible with the Condorcet / Copeland bandits, such as the Borda winner (Urvoy et al., 2013).”
Random Forest for the Contextual Bandit Problem (2015, methodology): “This formulation has been studied for MAB problem in Even-Dar et al (2002); Bubeck et al (2009), for dueling bandit problem in Urvoy et al (2013), and for linear bandit problem in Soare et al (2014).”
Decentralized Exploration in Multi-Armed Bandits (2018, methodology): “This theoretical framework has been used to analyze the best arm identification problem in Even-Dar et al (2006), the dueling bandit problem in Urvoy et al (2013), the batched bandit problem in Perchet et al (2015), the linear bandit problem in Soare et al (2014), the contextual bandit problem in…”
Efficient Mechanisms for Peer Grading and Dueling Bandits (2018, background): “…the dueling bandit problem has been studied before, previous works seem to focus on minimizing the total number of competitions (see for example Urvoy et al. (2013); Zoghi et al. (2014)) or minimizing some notion of regret (see for example Ailon et al. (2014); Yue et al. (2012); Zoghi et al.…”