Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem

2016/05/29 by Alexandra Carpentier, Carpentier, Alexandra, Andrea Locatelli +1 · 6 citations
Computer Science · Decision Sciences · #Machine Learning and Algorithms #Advanced Bandit Algorithms Research #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1605.09004

Abstract

We consider the problem of best arm identification with a fixed budget T, in the K-armed stochastic bandit setting, with arms distribution defined on [0,1]. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity H, will misidentify the best arm with probability lower bounded by exp(-(T)/(log(K)H)), where H is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by exp(-T/H). This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.

Cited by

• Short-Term Pain for Long-Term Gain: Adaptive Experiment with Post-Commitment Reward Shift
• Beyond the Lower Bound: Bridging Regret Minimization and Best Arm Identification in Lexicographic Bandits
• Optimal Arm Elimination Algorithms for Combinatorial Bandits
• Price of Safety in Linear Best Arm Identification
• Secure Best Arm Identification in the Presence of a Copycat
• Bandit Pareto Set Identification in a Multi-Output Linear Model

Related

• Optimal Best-arm Identification in Linear Bandits
• Optimal Best Arm Identification with Fixed Confidence
• Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap
• Bayesian Fixed-Budget Best-Arm Identification
• Best Arm Identification in Stochastic Bandits: Beyond β-optimality