Beat the Mean Bandit

By Yisong Yue, Thorsten Joachims. 2011

140 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

Human Preferences as Dueling Bandits (2022, neutral): “Beat the Mean [39] and Interleaved Filtering [38] are two of the early dueling bandit algorithms.”
Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Yue and Joachims (2009, 2011); Saha and Krishnamurthy (2022); Ghoshal and Saha (2022); Saha and Gopalan (2018a) The setting is relevant in various realworld systems which aim to collect information from user preferences, including recommender systems, retail management, search engine optimization,…”
Contextual Dueling Bandits (2015, methodology): “Numerous algorithms have been proposed for the (non-contextual) dueling bandits problem: Interleaved Filter (Yue et al., 2009); Beat the Mean (BTM) (Yue and Joachims, 2011); Sensitivity Analysis of VAriables for Generic Exploration (SAVAGE) (Urvoy et al., 2013); Relative Confidence Sampling (Zoghi e”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[75], was proposed by Yue and Joachims [174].”
Reducing Dueling Bandits to Cardinal Bandits (2014, methodology): “To formalize the problem of learning from preferences, we consider the following interactive online learning model, which we call the Utility-Based Dueling Bandits Problem (UBDB) similar to Yue et al. (2012); Yue & Joachims (2011).”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “In previous works (e.g., (Yue and Joachims, 2011; BusaFekete et al., 2014; Szörényi et al., 2015; Falahatgar et al., 2017b; 2018; Saha and Gopalan, 2019a;b)), the problem of best item selection has been studied in different settings.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, background): “The most frequently used benchmark is the Condorcet winner, which is an arm a⋆ that beats all others on average [Yue et al., 2012; Zoghi et al., 2014, 2015b; Komiyama et al., 2015; Yue and Joachims, 2011].”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, methodology): “In a subsequent work, Yue and Joachims [46] relax the strong stochastic transitivity property and only require a so-called relaxed stochastic transitivity for the pairwise probabilities: There is a γ ≥ 1 such that, for any triplet of arms such that ai∗ ai aj with respect to the total order ,”
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.”
Copeland Dueling Bandits (2015, background): “Examples include ranker evaluation [2–4] in information retrieval, ad placement and recommender systems.”
Maximum Selection and Ranking under Noisy Comparisons (2017, methodology): “We change Equations (7) and (8) in Yue & Joachims [2011] to c δ ( t ) = 1 t log n 3 and N = ⌈ 1 ǫ 2 log n 3 ⌉ , respectively. q We believe the same guarantees hold even with the updated constants.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “Interleaved ﬁltering (Yue et al., 2012) Beat-the-mean (Yue and Joachims, 2011) Knockout tournaments (Falahatgar et al., 2017b) Sequaential elimination (Falahatgar et al., 2017a) Single elimination tournament (Mohajer et al., 2017) Successive elimination (Jamieson et al., 2015) RUCB (Zoghi et al.,…”
Active Ranking with Subset-wise Preferences (2018, background): “…objective for different pairwise preference 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 [Szörényi et al., 2015] and the…”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “Dueling bandits [33, 10] is essentially the one-state version of PbRL, and has been extensively studied in the literature [34, 17, 16, 32].”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…of dueling bandit , one compares two actions and aims to minimize regret based on pairwise comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009, 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al., 2014a;…”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “Experimental study of dueling bandit algorithms have been limited to synthetic simulations in a few works (Yue and Joachims, 2011; Urvoy et al., 2013).”
MergeDTS (2018, methodology): “ we compare them by drawing a sample from a Bernoulli distribution with mean p ij, i.e., 1 means that a i beats a j and vice versa. This is a standard approach to evaluating dueling bandit algorithms [39, 41, 45]. Moreover, the proxy approach has been shown to have the same quality as interleaving i”
PAC Battling Bandits in the Plackett-Luce Model (2018, methodology): “We show an information-theoretic lower bound on sample complexity for ( ǫ, δ )-PAC of Ω (cid:18) nǫ 2 ln 1 δ (cid:19) rounds (Section 4.1), which is of the same order as that for the dueling bandit ( k = 2) (Yue and Joachims, 2011).”