Near-Optimal Target Learning With Stochastic Binary Signals
This addresses a practical limitation in noisy bisection models for applications like active learning or preference elicitation, though it is incremental as it builds on prior Bayesian methods.
The paper tackles the problem of learning a target value from noisy binary comparisons, particularly when noise levels approach 1/2 near the target, by proposing a pseudo-Bayesian algorithm that provably converges and achieves near-optimal expected performance under a Gaussian prior assumption.
We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm's Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.