Sharp Noisy Binary Search with Monotonic Probabilities

Abstract

We revisit the noisy binary search model of Karp and Kleinberg, in which we have $n$ coins with unknown probabilities $p_i$ that we can flip. The coins are sorted by increasing $p_i$, and we would like to find where the probability crosses (to within $\varepsilon$) of a target value $τ$. This generalized the fixed-noise model of Burnashev and Zigangirov , in which $p_i = \frac{1}{2} \pm \varepsilon$, to a setting where coins near the target may be indistinguishable from it. Karp and Kleinberg showed that $Θ(\frac{1}{\varepsilon^2} \log n)$ samples are necessary and sufficient for this task. We produce a practical algorithm by solving two theoretical challenges: high-probability behavior and sharp constants. We give an algorithm that succeeds with probability $1-δ$ from \[ \frac{1}{C_{τ, \varepsilon}} \cdot \left(\lg n + O(\log^{2/3} n \log^{1/3} \frac{1}δ + \log \frac{1}δ)\right) \] samples, where $C_{τ, \varepsilon}$ is the optimal such constant achievable. For $δ> n^{-o(1)}$ this is within $1 + o(1)$ of optimal, and for $δ\ll 1$ it is the first bound within constant factors of optimal.