Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems

By Eyal Even-Dar, Shie Mannor, Yishay Mansour. 2006

815 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.

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “The pure-exploration multi-armed bandit problem has a long history in the stochastic setting (Bubeck and CesaBianchi, 2012; Even-Dar et al., 2006), and was recently extended to the non-stochastic setting by Jamieson and Talwalkar (2015).”
The offset tree for learning with partial labels (2008, background): “The problem considered here is a non-interactive version of the contextual bandit problem (see [2, 3, 5, 15, 20] for background on the bandit problem).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “[76].”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “This idea was later used for example by Jennison et al. (1982); Maron and Moore (1997) or by Even-Dar et al. (2006) in the context of bounded bandit models, in which each arm ν a is a probability distribution on [0 , 1]. m best arm identiﬁcation with m > 1 was considered for example by…”
Decentralized Exploration in Multi-Armed Bandits (2018, methodology): “…2009; Audibert et al, 2010; Gabillon et al, 2013); • the ﬁxed conﬁdence setting: the objective is to minimize the number of rounds needed to achieve a ﬁxed conﬁdence to return the best arm (Even-Dar et al, 2006; Kalyanakrishnan et al, 2012; Gabillon et al, 2013; Kaufmann and Kalyanakrishnan, 2013).”
Machine learning applications in drug development (2019, background): “This was studied for example under the name ‘‘ranking and selection” [70,71] and later best arm identiﬁcation [72,73].”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “[2013], Graepel et al. [2010], Chapelle and Li [2011], Agrawal and Goyal [2012], Kauffmann et al.”
Counterfactual Data-Fusion for Online Reinforcement Learners (2017, background): “, [14, 10, 6, 15, 4]), an agent is faced with K ∈ N,K ≥ 2 discrete action choices (often called “arms”), each with its own, independent, and initially unknown reward distribution.”
Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (2018, background): “The fixed-confidence Best Arm Identification problem (concerned with finding the arm with largest mean) is one such example [9, 23], of which several variants have been studied [19, 17, 12].”
PAC Battling Bandits in the Plackett-Luce Model (2018, methodology): “In the online setting, there is a fairly mature body of work concerned with PAC bestarm (or top-l arm) identification in the classical multi-armed bandit (Even-Dar et al., 2006; Audibert and Bubeck, 2010; Kalyanakrishnan et al., 2012; Karnin et al., 2013; Jamieson et al., 2014), where absolute utili”
Introduction to Multi-Armed Bandits (2019, background): “However, improvements are possible in some regimes (e.g., Mannor and Tsitsiklis, 2004; Even-Dar et al., 2006; Bubeck et al., 2011a; Audibert et al., 2010).”
Automating model search for large scale machine learning (2015, methodology): “Our bandit selection strategy is a variant of the action elimination algorithm of [19], and to our knowledge this is the first time this algorithm has been applied to hyperparameter tuning.”
AutoFL: Enabling Heterogeneity-Aware Energy Efficient Federated Learning (2021, background): “The fine balance between exploitation versus exploration is at the heart of RL [30, 64].”
UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem (2010, methodology): “However, the analysis of [6] concentrated on PAC bounds for identifying an optimal arm instead of regret bounds as in our case.”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, background): “• Bounds that depend on gap between policies: (Even-Dar et al., 2006) has bounds dependent on the minimum gap in the optimal state action values between the best and second best action, and UCRL2 has bounds as function of the gap in the difference in the average reward between the best and second…”