Learning to be safe, in finite time
  This paper aims to put forward the concept that learning to take safe actions
in unknown environments, even with probability one guarantees, can be achieved
without the need for an unbounded number of exploratory trials, provided that
one is willing to relax its optimality requirements mildly. We focus on the
canonical multi-armed bandit problem and seek to study the
exploration-preservation trade-off intrinsic within safe learning. More
precisely, by defining a handicap metric that counts the number of unsafe
actions, we provide an algorithm for discarding unsafe machines (or actions),
with probability one, that achieves constant handicap. Our algorithm is rooted
in the classical sequential probability ratio test, redefined here for
continuing tasks. Under standard assumptions on sufficient exploration, our
rule provably detects all unsafe machines in an (expected) finite number of
rounds. The analysis also unveils a trade-off between the number of rounds
needed to secure the environment and the probability of discarding safe
machines. Our decision rule can wrap around any other algorithm to optimize a
specific auxiliary goal since it provides a safe environment to search for
(approximately) optimal policies. Simulations corroborate our theoretical
findings and further illustrate the aforementioned trade-offs.
