The Sample Complexity of Exploration in the Multi-Armed Bandit Problem

By Shie Mannor, John N. Tsitsiklis. Journal of machine learning research, 2004

506 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/70e55528a8328969b7b2aee4e466f2958fda75e7

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

Almost Optimal Exploration in Multi-Armed Bandits (2013, background): “Mannor & Tsitsiklis (2004) provided tight, distribution-dependent lower bounds for several variants of the PAC model.”
Optimal Best Arm Identification with Fixed Confidence (2016, background): “In particular, T ∗ ( µ ) cannot be written as a sum over the arms of individual complexity terms as in previous works ( Mannor and Tsitsiklis (2004); Kaufmann et al. (2015)).”
Autonomously Acquiring Instance-Based Object Models from Experience (2015, methodology): “Existing algorithms for best arm identification require pulling all the arms as an initialization step [27, 1, 5]; in the case of identifying grasp points, where each grasp takes more than 15 seconds and there are more than 1000 potential arms, this is a prohibitive expense.”
Algorithms for Reinforcement Learning (2010, methodology): “Apart from constant factors and using estimated variances in the confidence bounds, this algorithm is unimprovable (Even-Dar et al., 2002; Tsitsiklis and Mannor, 2004; Mnih et al., 2008).”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, background): “The ranges of possible δ and are of similar order than in other state-of-the-art lower bounds for multi-armed bandits [19] and discounted MDPs [14, 6].”
Multi-armed Bandit Algorithms and Empirical Evaluation (2005, methodology): “The -first strategy has been analyzed within the PAC framework by [7] and [16].”
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);…”
Decentralized Exploration in Multi-Armed Bandits (2018, background): “Ω ( K 2 log 1 δ ) (Mannor and Tsitsiklis, 2004), holds for the decentralized exploration problem, since a message can be sent at each time an arm is sampled by a player.”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “Mannor and Tsitsiklis (2004) show that if an algorithm is δ -PAC, then in the bandit model ν = ( ( µ 1 ) , . . . , B ( µ K )) such that ∀ a , µ a ∈ [0 , α ] for some α ∈ ]0 , 1[, there exists two sets M α ( ν ) ⊂ S ∗ 1 and N α ( ν ) ⊂ { 1 , . . . , K ∗ 1 and a positive constant C α such that This…”
Pure exploration in finitely-armed and continuous-armed bandits (2011, unknown): “Indeed, some forecasters are sensitive to the ordering of the distributions and might get a zero regret for a significant fraction of the ordered K–tuples simply because, e.g., their strategy is to constantly pull a given arm, which is sometimes the optimal strategy just by chance.”
UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem (2010, result): “Further, this is consistent with the lower bounds on the regret derived by Mannor and Tsitsiklis [10].”
Random Forest for the Contextual Bandit Problem (2015, background): “Finally, Lemma 4 states that the action selection stump is optimal up to logarithmic factors (see Mannor and Tsitsiklis (2004) Theorem 1 for the proof).”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, background): “s well known that in order to distinguish r 1 and r 2 with probability at least 0:9, any algorithm requires (d^H) samples. See e.g. Lemma 5.1 in [Anthony and Bartlett, 2009]. See also [Cherno, 1972, Mannor and Tsitsiklis, 2004]. Remark 4. The key in our construction is the state sd^+1 h in each leve”
The K-armed Dueling Bandits Problem (2012, background): “Upper confidence bounds are also central to the design of multi-armed bandit problems in the PAC setting [EDMM06, MT04 ], where the algorithm’s objective is to identify an arm that is "-optimal with probability at least 1 . Our work adopts a very different feedback model (pairwise comparisons rathe”