Identifying Approximate Minimizers under Stochastic Uncertainty

Hessa Al-Thani, Viswanath Nagarajan

We study a fundamental stochastic selection problem involving $n$ independent random variables, each of which can be queried at some cost. Given a tolerance level $\delta$, the goal is…