The Survival Bandit Problem

Charles Riou, Junya Honda, Masashi SugiyamaarXiv 2022 · DOI · arXiv

Authors: Charles Riou, Junya Honda, Masashi Sugiyama

Summary

The "Survival Bandit Problem" (S-MAB) introduces a high-stakes twist to the classic multi-armed bandit: if your cumulative reward ever hits a negative threshold, the game ends immediately. This research proves that standard exploration strategies are too risky for this setting and introduces a "doubling trick" algorithm that safely transitions from survival-first exploitation to reward-maximizing exploration.

Introduction: What Problem Does This Paper Address?

In the classic Multi-Armed Bandit (MAB) setting, an agent pulls arms to maximize rewards, balancing the need to explore (find better arms) and exploit (pull the best-known arm). While a few bad pulls might hurt your score, they don't end the game.

However, real-world scenarios like clinical trials or financial portfolio management have a "ruin" condition. In a medical trial, if a treatment causes too many adverse effects (negative rewards), the trial must be stopped for ethical reasons. In finance, if your losses exceed your budget, you go bankrupt.

The authors identify a gap: standard MAB theory assumes an infinite or fixed horizon where the agent can always keep playing. In S-MAB, the procedure is interrupted if the cumulative reward falls below a threshold $-B$. This creates a fundamental tension: you can't learn which arm is best without exploring, but exploring a suboptimal arm early on might lead to immediate ruin.

Methodology

The authors formalize the S-MAB and demonstrate that achieving "sublinear regret" (the standard benchmark for bandit success) is impossible because the risk of ruin is always present. Instead, they shift the goal to Pareto-optimality, seeking a policy that balances the probability of ruin against the expected cumulative reward.

The EXPLOIT Framework

Key components of their approach include a conservative set of policies that allocate a specific "safety budget" to each arm. These policies match the theoretical lower bound for the probability of ruin but tend to have lower total rewards because they are too cautious.

The Doubling Trick

To fix the low-reward issue, the authors introduce EXPLOIT-UCB-DOUBLE. This algorithm starts by playing safely (like the EXPLOIT framework). However, as it accumulates a "cushion" of positive rewards, it effectively "restarts" with a larger budget. This creates a three-stage lifecycle: exploit a safe arm to survive $\rightarrow$ explore to find the best arm $\rightarrow$ exploit the best arm to maximize gains.

Experimental Setup

As a theoretical reinforcement learning paper, the authors evaluate their algorithms using synthetic environments:

  • Synthetic Multinomial Distributions: Arms with rewards in $\{-1, 0, 1\}$. This is the primary testbed for their proofs.
  • Bernoulli Distributions: A simpler case used to illustrate why the problem is more complex than it first appears.
  • General Bounded Distributions: They extend their results to rewards within the continuous range $[-1, 1]$.

Key Insights and Results

  • The Death of Sublinear Regret: In S-MAB, every pull is a gamble with your existence. The authors show that no policy can be "perfect" across all possible scenarios; you must accept a trade-off between the risk of dying early and the reward of living long.
  • Survival Requires Early Bias: Standard bandits use early rounds to explore. S-MAB agents must do the opposite: they must pull arms that seem safe immediately to build a buffer, even if those arms aren't the long-term optimal choice.
  • Budget as a Cushion: The "doubling trick" is the core innovation. By treating accumulated rewards as an increased budget, the agent can gradually "unlock" the ability to use standard, aggressive algorithms like UCB (Upper Confidence Bound) without fearing immediate ruin.
  • Performance: In simulations (e.g., $T=20,000$, Budget $B=9$), standard UCB and Thompson Sampling suffered ruin in 10-30% of trials. In contrast, the EXPLOIT-based algorithms kept the ruin rate significantly lower (around 4-8%) while eventually catching up to or exceeding the rewards of standard methods.

Limitations and Future Work

  • Horizon Dependency: The most effective version of their algorithm requires knowing the time horizon ($T$) in advance. The authors conjecture that no "anytime" policy (one that doesn't know $T$) can be truly Pareto-optimal for all distributions.
  • Hyperparameter Tuning: The performance of the doubling trick depends on a hyperparameter $n$. While $\log T$ is theoretically sound, finding the best $n$ for practical, finite-time applications remains an open challenge.
  • Continuous Rewards: While they generalized the ruin probability to continuous rewards in $[-1, 1]$, proving Pareto-optimality for rewards that aren't integers is significantly more complex and remains a subject for future research.

Summary updated

Abstract

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).
BibTeX
@misc{riou2022survival,
  author = {Charles Riou and Junya Honda and Masashi Sugiyama},
  title = {{The Survival Bandit Problem}},
  year = {2022},
  eprint = {2206.03019},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.03019},
}
Figure