PAC Bounds for Multi-armed Bandit and Markov Decision Processes

By Eyal Even-Dar, Shie Mannor, Yishay Mansour. Annual Conference Computational Learning Theory, 2002

462 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/27d48fd1367b0c08c7bd3a8f8e79b7bfef0bc81d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

The Sample Complexity of Exploration in the Multi-Armed Bandit Problem (2004, methodology): “We note that the median elimination algorithm of Even-Dar et al. (2002) is a (q,ε,δ)-correct policy whose pathwise sample complexity is of the form (c1n/ε(2)) log(c2/δ).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, unknown): “[75], was proposed by Yue and Joachims [174].”
Multi-armed Bandit Algorithms and Empirical Evaluation (2005, methodology): “show in [7] that a total of O ( K α(2) log ( K δ )) random pulls suffices to find an α-optimal arm with probability at least 1−δ.”
Speedy Q-Learning (2011, methodology): “Finite sample bounds for both model-based and model-free (Phased Q-learning) QI have been derived in [12] and [7].”
The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond (2011, unknown): “Recently, Audibert and Bubeck (2010) introduced an improved UCB algorithm, termed MOSS, which achieves the distribution-free optimal rate.”
Bandits with Knapsacks (2013, methodology): “003, Besbes and Zeevi,2009, Babaioff et al., 2015]). However, bounding the discretization error in BwKis much more difﬁcult. OurBalancedExplorationalgorithmextendsthe“activearmselimination” algorithm[Even-Dar et al., 2002]forthestochastic MABproblem, whereone iterates overarmsthatarenotobviously sub”
Preference-based Evolutionary Direct Policy Search (2013, background): “In the context of multi-armed bandits, a slightly different setup was introduced in [9], where an -optimal random variable has to be chosen with probability at least 1− δ; here, -optimality of Xi means that μi + ≥ maxj∈[K] μj .”
Generic Exploration and K-armed Voting Bandits (2013, methodology): “(5) With this predicate, we fall-back almost to the ”arm elimination” of (Even-Dar et al., 2002).”
Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm (2014, methodology): “Our analysis is similar to the sample complexity analysis of PAC -bandit algorithms [9].”
Multiple Identifications in Multi-Armed Bandits (2012, methodology): “Another possible formulation is the one of the PAC model studied in (Even-Dar et al., 2002; Mannor & Tsitsiklis, 2004) where an accuracy ε and a probability of correctness δ are prespecified, and one wants to minimize the number of evaluations to attain this prespecified accuracy”
An analysis of model-based Interval Estimation for Markov Decision Processes (2008, methodology): “In [4], it was shown that an algorithm called Successive Elimination will perform much better than the naïve algorithm when there is a significant difference in the mean payoffs of different arms.”
Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting (2014, methodology): “In 2002, the successive elimination procedure of [4] was shown to find the best arm with or- der ∑ i6=i∗ ∆ −2 i log(n∆ −2 i ) samples, where ∆i = µi∗ − µi, coming within a logarithmic factor of the lower bound of∑ i6=i∗ ∆ −2 i , shown in 2004 in [5].”
Introduction to Multi-Armed Bandits (2019, methodology): “The weighted majority algorithm is from Littlestone and Warmuth (1994), and Hedge algorithm is from Littlestone and Warmuth (1994); Freund and Schapire (1997). Sequential prediction with experts advise has a long history in economics and statistics, see Cesa-Bianchi and Lugosi (2006, Chapter 2) for ”
A unifying framework for computational reinforcement learning theory (2009, background): “See Moore and Atkeson [1995] and Bernstein and Shimkin [2008] for more examples.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “SPAR2 follows the action elimination principle of Even-Dar et al. (2002), in which actions that cannot belong to the support of the von Neumann winner are eliminated based on conﬁdence bounds on probability estimates.”
Almost Optimal Exploration in Multi-Armed Bandits (2013, methodology): “The fixed confidence setting was first considered by Even-Dar et al. (2002), who presented the Successive Elimination strategy for the best-arm and ε-best arm identification problems.”
A Contextual-Bandit Algorithm for Mobile Context-Aware Recommender System (2012, methodology): “Therefore it may not be desirable to perform the exploration all at once at the beginning as in [6] or to decrease monotonically the effort on exploration as the decreasing strategy in [10].”
Active Model Selection (2004, background): “These differences changes the nature of the task significantly, and sets it apart from typical finite or infinite-horizon bandit problems and their analyses (e.g., [KL00, EDMM02 , HS02, ACBFS02]).”