Introduces transductive linear bandits, gives instance-dependent lower bounds, and presents an algorithm matching them up to logarithmic factors, including the first non-asymptotic near-optimal method for standard linear bandits.
On the Optimal Sample Complexity for Best Arm Identification
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We study the best arm identification (BEST-1-ARM) problem, which is defined as follows. We are given $n$ stochastic bandit arms. The $i$th arm has a reward distribution $D_i$ with an unknown mean $\mu_{i}$. Upon each play of the $i$th arm, we can get a reward, sampled i.i.d. from $D_i$. We would like to identify the arm with the largest mean with probability at least $1-\delta$, using as few samples as possible. We provide a nontrivial algorithm for BEST-1-ARM, which improves upon several prior upper bounds on the same problem. We also study an important special case where there are only two arms, which we call the sign problem. We provide a new lower bound of sign, simplifying and significantly extending a classical result by Farrell in 1964, with a completely new proof. Using the new lower bound for sign, we obtain the first lower bound for BEST-1-ARM that goes beyond the classic Mannor-Tsitsiklis lower bound, by an interesting reduction from Sign to BEST-1-ARM. We propose an interesting conjecture concerning the optimal sample complexity of BEST-1-ARM from the perspective of instance-wise optimality.
years
2019 2verdicts
UNVERDICTED 2representative citing papers
Action-outcome probabilities for rational choice can be grounded in causal models both when the causal structure is known and when it is unknown, with an extension to causal Nash Equilibrium.
citing papers explorer
-
Sequential Experimental Design for Transductive Linear Bandits
Introduces transductive linear bandits, gives instance-dependent lower bounds, and presents an algorithm matching them up to logarithmic factors, including the first non-asymptotic near-optimal method for standard linear bandits.
-
Choosing with unknown causal information: Action-outcome probabilities for decision making can be grounded in causal models
Action-outcome probabilities for rational choice can be grounded in causal models both when the causal structure is known and when it is unknown, with an extension to causal Nash Equilibrium.