# Binary search on coin heads probability

Let $$f:[0,1] \to [0,1]$$ be a smooth, monotonically increasing function. I want to find the smallest $$x$$ such that $$f(x) \ge 1/2$$.

If I had a way to compute $$f(x)$$ given $$x$$, I could simply use binary search on $$x$$. However, I don't have a way to compute $$f(x)$$. Instead, I have a black box that, on input $$x$$, flips a biased coin and outputs 1 with probability $$f(x)$$ and 0 with probability $$1-f(x)$$. I can invoke the black box as many times as I want.

I'm looking for a query-efficient strategy to approximate $$x^* = \min \{x : f(x) \ge 1/2\}$$. Is there an efficient algorithm? I would be happy with strategies where we assume a fixed upper bound on $$f'(x)$$.

Informally, we can summarize the problem as: I have a coin whose heads probability depends in some unknown but monotonic way on a parameter; how can I choose the minimum value of that parameter to ensure the coin is biased in my favor?

A naive approach is to estimate $$f(x)$$ for any $$x$$ by invoking the black box $$k$$ times on the same input $$x$$, then use binary search with this estimator. However, I suspect this makes more queries than necessary. Intuitively, it makes many queries in regimes where $$|x-1/2|$$ is large, and the estimator for $$f(x)$$ doesn't use information from the black box on queries $$x'$$ that are near to $$x$$.

I suspect something like the following might be better, for some constant $$1/2 < \alpha < 1$$:

1. Set $$x := 1/2$$ and $$d := \alpha$$.
2. Repeat some fixed number of times:
• Query the black box on $$x$$. If it returns 1, set $$x := x + d$$, otherwise set $$x := x - d$$.
• Clip $$x$$ to the range $$[0,1]$$. Set $$d := \alpha d$$.

However I'm not sure how to set $$\alpha$$ or how to analyze this approach. (Note that if $$\alpha=1/2$$ and the black box returned whether or not $$f(x)\ge 1/2$$, this strategy would devolve to binary search.)

Is there a good way to choose $$\alpha$$? Or, is there a better strategy?