PAC Subset Selection in Stochastic Multi-armed Bandits

By Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, Peter Stone. International Conference on Machine Learning, 2012

423 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/bda27e969e43a1e93026981afff57b8d46be008e

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

Simple regret for infinitely many armed bandits (2015, background): “The problem of minimizing the simple regret in a multi-armed bandit setting (with finitely many arms) has recently attracted significant 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”
Optimal Best Arm Identification with Fixed Confidence (2016, unknown): “…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); Gabillon et al. (2012); Kaufmann and Kalyanakrishnan (2013); Jamieson et al. (2014)).”
Preference-based Evolutionary Direct Policy Search (2013, methodology): “Recently, a PAC-bandit algorithm which is based on the widely-known UCB index-based muli-armed bandit method of [5] was introduced in [18].”
Learning to Hire Teams (2015, background): “Based on Theorem 6 from Kalyanakrishnan et al. (2012), the expected sample complexity of LUCB-1( , δ) for one instance of the problem with N actions for a particular task oj is given by:”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, methodology): “An expected sample complexity bound is calculated for the -sensitive Copeland ranking procedure along with the MRD distance in a similar way like in [29, 30].”
lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits (2013, methodology): “Also, in some analyses of best arm algorithms the upper confidence bounds of each arm are designed to hold with high probability for all arms uniformly, incurring a log(n) term in the confidence bound as a result of the necessary union bound over the n arms (Even-Dar et al., 2002; Kalyanakrishnan et”
Almost Optimal Exploration in Multi-Armed Bandits (2013, background): “The related works of Kalyanakrishnan & Stone (2010) and Kalyanakrishnan et al. (2012) studied the same problem in a fixed confidence PAC setup.”
Information Complexity in Bandit Subset Selection (2013, background): “As another gap between regret and pureexploration, one might consider that no counterpart of the Thompson Sampling algorithm, recently shown to be optimal in the regret setting Kaufmann et al. (2012) as well as practically very efficient, has yet been found for Explore-m.”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “We prove this bound by reducing the pure exploration multi-armed bandit (PEMAB) problem (e.g., (Mannor and Tsitsiklis, 2004; Kalyanakrishnan et al., 2012)) to the PAC k-selection problem under the MNL model and using the lower bounds for the PEMAB problem of Mannor and Tsitsiklis (2004);…”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “For ∈ (0, 1− π), we say arm k is -optimal if Qk(π + ) ≥ Qj(π) for all j 6= k. Kalyanakrishnan et al. (2012) introduced the LUCB algorithm for highest mean identification, for which Jamieson and Nowak (2014) gave a simplified analysis in the = 0 case.”
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].”
Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting (2014, methodology): “The second set of experiments is more quantitative and compares the stopping times of the state-of-the-art algorithms.”
Active Ranking with Subset-wise Preferences (2018, background): “where the above analysis follows from a similar result proved by [24] to derive sample complexity lower bound for classical multi-armed bandit setting towards recovering top-q items (see Theorem 8, [24]).”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, background): “> , K , hence the complexity term does not involve a sum over all the For m 1, the only lower bound available in the literature is the worst-case result of Kalyanakrishnan et al. (2012).”
Multiple Identifications in Multi-Armed Bandits (2012, methodology): “In particular, the algorithm LUCB designed in (Kalyanakrishnan et al., 2012) is based on fundamentally different ideas (confidence intervals and UCB type algorithms) than the one developed in this paper.”
Decentralized Exploration in Multi-Armed Bandits (2018, methodology): “LUCB Kalyanakrishnan et al (2012), KL-LUCB Kaufmann and Kalyanakrishnan (2013), UG AP E C Gabillon et al (2013) can also be used as ArmSelection subroutines by returning the set of eliminated arms when the stopping event occurs ( L = 1 and f ( l n ) = 1 ).”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, background): “The problem of regret minimization for multiarmed bandits (MAB) is very well studied in the online learning literature [7, 2, 6, 20, 25], where the learner gets to see a noisy draw of absolute reward feedback of an arm upon playing a single arm per round.”
PAC Battling Bandits in the Plackett-Luce Model (2018, background): “…work concerned with 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…”