  We consider a multi-armed bandit problem motivated by situations where only
the extreme values, as opposed to expected values in the classical bandit
setting, are of interest. We propose distribution free algorithms using robust
statistics and characterize the statistical properties. We show that the
provided algorithms achieve vanishing extremal regret under weaker conditions
than existing algorithms. Performance of the algorithms is demonstrated for the
finite-sample setting using numerical experiments. The results show superior
performance of the proposed algorithms compared to the well known algorithms.
