  In a typical optimization problem, the task is to pick one of a number of
options with the lowest cost or the highest value. In practice, these
cost/value quantities often come through processes such as measurement or
machine learning, which are noisy, with quantifiable noise distributions. To
take these noise distributions into account, one approach is to assume a prior
for the values, use it to build a posterior, and then apply standard stochastic
optimization to pick a solution. However, in many practical applications, such
prior distributions may not be available. In this paper, we study such
scenarios using a regret minimization model.
  In our model, the task is to pick the highest one out of $n$ values. The
values are unknown and chosen by an adversary, but can be observed through
noisy channels, where additive noises are stochastically drawn from known
distributions. The goal is to minimize the regret of our selection, defined as
the expected difference between the highest and the selected value on the
worst-case choices of values. We show that the na\"ive algorithm of picking the
highest observed value has regret arbitrarily worse than the optimum, even when
$n = 2$ and the noises are unbiased in expectation. On the other hand, we
propose an algorithm which gives a constant-approximation to the optimal regret
for any $n$. Our algorithm is conceptually simple, computationally efficient,
and requires only minimal knowledge of the noise distributions.
