Ron Kupfer
We extend the Ting--Yao randomized maximum-finding algorithm [TY94] to inputs that need not be pairwise distinct: each parity test $P(i,B)=\prod_{a\in B}(x_i-x_a):0$ on $B\subseteq[n]\setminus\{i\}$ is simulated by $O(\log |B|)$ ordinary polynomial tests, raising depth from $O((\log n)^2)$ to $O((\log n)^3)$ while preserving the $O(n^{-c})$ failure probability for every fixed $c>0$.
Avinatan Hassidim, Ron Kupfer, Yaron Singer
We consider the classic problem of $(ε,δ)$-PAC learning a best arm where the goal is to identify with confidence $1-δ$ an arm whose mean is an $ε$-approximation to that of the highest mean arm in a multi-armed bandit setting. This problem is one of the most fundamental problems in statistics and learning theory, yet somewhat surprisingly its worst-case sample complexity is not well understood. In this paper, we propose a new approach for $(ε,δ)$-PAC learning a best arm. This approach leads to an algorithm whose sample complexity converges to \emph{exactly} the optimal sample complexity of $(ε,δ)$-learning the mean of $n$ arms separately and we complement this result with a conditional matching lower bound. More specifically: