  We introduce and study a new variant of the multi-armed bandit problem (MAB),
called the survival bandit problem (S-MAB). While in both problems, the
objective is to maximize the so-called cumulative reward, in this new variant,
the procedure is interrupted if the cumulative reward falls below a preset
threshold. This simple yet unexplored extension of the MAB follows from many
practical applications. For example, when testing two medicines against each
other on voluntary patients, people's health are at stake, and it is necessary
to be able to interrupt experiments if serious side effects occur or if the
disease syndromes are not dissipated by the treatment. From a theoretical
perspective, the S-MAB is the first variant of the MAB where the procedure may
or may not be interrupted. We start by formalizing the S-MAB and we define its
objective as the minimization of the so-called survival regret, which naturally
generalizes the regret of the MAB. Then, we show that the objective of the
S-MAB is considerably more difficult than the MAB, in the sense that contrary
to the MAB, no policy can achieve a reasonably small (i.e., sublinear) survival
regret. Instead, we minimize the survival regret in the sense of Pareto, i.e.,
we seek a policy whose cumulative reward cannot be improved for some problem
instance without being sacrificed for another one. For that purpose, we
identify two key components in the survival regret: the regret given no ruin
(which corresponds to the regret in the MAB), and the probability that the
procedure is interrupted, called the probability of ruin. We derive a lower
bound on the probability of ruin, as well as policies whose probability of ruin
matches the lower bound. Finally, based on a doubling trick on those policies,
we derive a policy which minimizes the survival regret in the sense of Pareto,
giving an answer to an open problem by Perotto et al. (COLT 2019).
