Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk
  We investigate a natural but surprisingly unstudied approach to the
multi-armed bandit problem under safety risk constraints. Each arm is
associated with an unknown law on safety risks and rewards, and the learner's
goal is to maximise reward whilst not playing unsafe arms, as determined by a
given threshold on the mean risk.
  We formulate a pseudo-regret for this setting that enforces this safety
constraint in a per-round way by softly penalising any violation, regardless of
the gain in reward due to the same. This has practical relevance to scenarios
such as clinical trials, where one must maintain safety for each round rather
than in an aggregated sense.
  We describe doubly optimistic strategies for this scenario, which maintain
optimistic indices for both safety risk and reward. We show that schema based
on both frequentist and Bayesian indices satisfy tight gap-dependent
logarithmic regret bounds, and further that these play unsafe arms only
logarithmically many times in total. This theoretical analysis is complemented
by simulation studies demonstrating the effectiveness of the proposed schema,
and probing the domains in which their use is appropriate.
