Almost Optimal Exploration in Multi-Armed Bandits

By Zohar S. Karnin, Tomer Koren, Oren Somekh. 2013

557 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, background): “[19], which solves the equivalent problem for (non-dueling) bandits in both fixed confidence and fixed budget settings, and that paper might provide a starting point for further theoretical investigation.”
Primer: Searching for Efficient Transformers for Language Modeling (2021, methodology): “This strategy is not unlike bandit algorithms such as Successive Halving[53] and Hyperband[54], however we do not use a static population of individuals created a priori, but integrate our halving with the changing evolutionary population.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “ch results in the lowest training error most quickly. This idea is relatively simple to try in practice, and ideas from bandit optimization can be applied to eﬃciently search with this heuristic cost [15,17]. From the theoretical perspective, understanding the sensibility of this heuristic would req”
Hyper-Parameter Optimization: A Review of Algorithms and Applications (2020, neutral): “SHA (Jamieson and Talwalkar, 2016) is based on multi-bandit problems (Karnin et al., 2013).”
Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, methodology): “When q = 1 /K this implies that the best arm is identiﬁed with about log(1 /δ ) log( K ) =2 ∆ − 2 i which matches known upperbounds Karnin et al. (2013); Jamieson et al. (2014) and lower bounds Kaufmann et al. (2015) up to log factors.”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “In fact, the algorithm we propose to use in this paper is the Successive Halving algorithm of [15], though the non-stochastic setting requires its own novel analysis that we present in Section 3.”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, background): “Karnin et al. (2013) and Jamieson et al. (2014)) exhibit δ -PAC algorithms for which there exists a constant C such that, with high probability, the number of samples used satisﬁes and Jamieson et al. (2014) show that the dependency in ∆ − 2 a log(log(∆ − 1 a )) is optimal when ∆ a goes to zero.”
A System for Massively Parallel Hyperparameter Tuning (2018, methodology): “Our algorithm is inspired by the Successive Halving algorithm (SHA) (Karnin et al., 2013; Jamieson & Talwalkar, 2015), a theoretically principled early stopping method that allocates more resources to promising conﬁgurations.”
Automated Machine Learning: From Principles to Practices (2018, methodology): “However, this method only addresses the coupling between 𝑤 and 𝛼 but the coupling problem in 𝑤 still remains.”
Bandit Algorithms (2020, methodology): “Katariya et al. [2016] study the dependent click model introduced by Guo et al.”
On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice (2020, methodology): “To overcome the limitations of GS and RS and to improve efficiency, successive halving algorithms were proposed in [92].”
Simple regret for infinitely many armed bandits (2015, background): “…recently attracted signiﬁcant attention (Even-Dar et al., 2006; Audibert et al., 2010; Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013; Karnin et al., 2013; Gabillon et al., 2012; Jamieson et al., 2014) and algorithms have been developed either in the setting of a ﬁxed budget which…”
Critical Hyper-Parameters: No Random, No Cry (2017, methodology): “We do not consider the possibility of saving computational resources by stopping some runs early based on an estimate of their ﬁnal performance, as is done by methods such as Sequential Halving [11] and Hyperband [14] or validation curves modeling as in [5].”
An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization (2020, methodology): “Based on this idea, Jamieson and Talwalkar (2016) proposed the Successive Halving algorithm originally introduced by Karnin et al. (2013) for HPO.”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “…PAC best-arm (or top-ℓ arm) identiﬁcation 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 utility information is assumed to be revealed upon playing a single arm or item.”
Blind Search for Atari-Like Online Planning Revisited (2016, background): “As another issue, if the number of actions examined for the current state does not decrease for a substantial chunk of the lookahead budget, then it seems natural to consider a mechanism for gradual “candidate rejection”, possibly in the spirit of algorithms for budgeted pure exploration in stochast”
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (2022, background): “…there is extensive literature on PAC-arm identiﬁcation problem (Even-Dar et al., 2006; Audibert and Bubeck, 2010; Kalyanakrishnan et al., 2012; Karnin et al., 2013; Jamieson et al., 2014), where the learner gets to see a noisy draw of absolute reward feedback of an arm upon playing a single…”
Meta-learning curiosity algorithms (2020, methodology): “This was inspired by the effective use of sequential halving (Karnin et al., 2013) in hyper-parameter optimization (Jamieson & Talwalkar, 2016).”
Massively Parallel Hyperparameter Tuning (2018, methodology): “Our algorithm is inspired by the Successive Halving algorithm (SHA) [Karnin et al., 2013, Jamieson and Talwalkar, 2015], a theoretically principled early-stopping method that allocates more resources to promising conﬁgurations.”