Information Complexity in Bandit Subset Selection

By Emilie Kaufmann, Shivaram Kalyanakrishnan. 2013

195 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

Anchors: High-Precision Model-Agnostic Explanations (2018, methodology): “After generating all the possible candidates rules, we select the B-best candidates to keep based on the KL-LUCB approach with multiple arms (the Explore-m setting).”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “By analogy with the result of Theorem 5 we conjecture that the analysis of Kaufmann and Kalyanakrishnan (2013) —on which the result of Lemma 8 is based– is too conservative and that the use of and exploration rate of order log(log( t ) /δ ) should also lead to a δ -PAC algorithm.”
Optimal Best Arm Identification with Fixed Confidence (2016, methodology): “While racing strategies are based on successive eliminations of apparently sub-optimal arms (Even-Dar et al. (2006); Kaufmann and Kalyanakrishnan (2013)), another family of strategies exploits the use of upper and lower conﬁdence bounds on the means of the arms (Kalyanakrishnan et al. (2012);…”
On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning (2014, background): “In this same vein, it is important to take into account that a recommendation must be made at time T in order to properly allocate actions and explore the space of possible optima.”
Simple regret for infinitely many armed bandits (2015, background): “An example where efﬁcient strategies for minimizing the simple regret of an inﬁnitely many armed ban-dit are relevant is the search of a good biomarker in biology, a single feature that performs best on average (Hauskrecht et al., 2006).”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “See Kim and Nelson [2006], Kim and Nelson [2007] or Hong et al.”
Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting (2014, methodology): “1 δ ) ) 2Ti(t) as prescribed in [12].”
Post-hoc Interpretability for Neural NLP: A Survey (2021, methodology): “(2018b) model prec(A) ≥ τ probabilistically (Kaufmann and Kalyanakrishnan, 2013) and then use a bottom-up approach, where they add a new word to the k-best anchor candidate in each iteration similar to beam-search.”
Decentralized Exploration in Multi-Armed Bandits (2018, methodology): “S UCCESSIVE E LIMINATION ( L = K and f ( l n ) = 1 /K ) Even-Dar et al (2006), KL-R ACING ( L = K and f ( l n ) = 1 /K ) Kaufmann and Kalyanakrishnan (2013) are successive elimination algorithms which can be used as ArmSelection subroutines.”