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 $\hat{I}´$, the goal is…