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$:
- Set $x := 1/2$ and $d := \alpha$.
- 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?
