  The probabilistic bisection algorithm (PBA) solves a class of stochastic
root-finding problems in one dimension by successively updating a prior belief
on the location of the root based on noisy responses to queries at chosen
points. The responses indicate the direction of the root from the queried
point, and are incorrect with a fixed probability. The fixed-probability
assumption is problematic in applications, and so we extend the PBA to apply
when this assumption is relaxed. The extension involves the use of a power-one
test at each queried point. We explore the convergence behavior of the extended
PBA, showing that it converges at a rate arbitrarily close to, but slower than,
the canonical "square root" rate of stochastic approximation.
