Mortal Multi-Armed Bandits

Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, Eli UpfalNeurIPS 2008 · OpenReview

Introduction

Standard multi-armed bandit (MAB) models assume that once you find a "winning" option, you can exploit it forever. In the classic $k$-armed bandit problem, an agent chooses between several options with unknown reward distributions to maximize total reward over time. In this static setting, the "regret" (the difference between the optimal strategy and the algorithm) grows logarithmically, meaning the algorithm eventually identifies the best arm with near-certainty and stops exploring.

However, this paper introduces Mortal Multi-Armed Bandits, a more realistic framework where arms (like online ads) have finite lifetimes and eventually expire. Ads have limited budgets, seasonal relevance, or campaign end dates—they are "mortal." If an algorithm spends too much time "exploring" an ad to precisely determine its click-through rate, the ad might expire before the algorithm can actually "exploit" that knowledge. The core challenge is that in a mortal setting, an algorithm must continuously balance exploration with rapid exploitation before an arm "dies."

Methods: Modeling Mortality

The authors formalize "mortality" through two primary models:

  1. Budgeted Death: An arm expires after it has been pulled a certain number of times ($L$). This mimics an ad with a fixed financial budget.
  2. Timed Death: An arm has a probability $p$ of expiring at every time step, regardless of whether it was pulled. This mimics seasonal or time-sensitive content.

To handle these constraints, they propose several new algorithms:

  • DETOPT (Deterministic Optimal): Designed for "state-aware" cases where the reward is known immediately after one pull. It uses a calculated payoff threshold ($\mu^*$); if an arm's reward is above this threshold, the algorithm exploits it until it dies.
  • STOCHASTIC: For the more realistic "state-oblivious" case where rewards are probabilistic (e.g., a click or no click). It pulls a new arm $n$ times to estimate its value. If the estimate exceeds a threshold, it commits to that arm.
  • The Subset Heuristic ($UCB1_{K/C}$): A clever modification of the standard UCB1 algorithm. Instead of trying to manage all $k$ available arms (which might be millions), it picks a small random subset ($k/c$) and runs UCB1 on only those. This forces the algorithm to converge faster on a "good enough" arm before the arms in the subset expire.

Datasets

The researchers evaluated their algorithms using three types of reward distributions:

  • Uniform Distribution: Payoffs drawn uniformly from $[0, 1]$.
  • Beta Distribution: Specifically $Beta(1, 3)$, which simulates an environment where most arms are mediocre and high-performing arms are rare.
  • Real-World Ad Data: A dataset derived from a large ad broker consisting of click-through rates for ~300 real ads in a shopping category. This provided a unimodal, tightly concentrated distribution to test the algorithms in a production-like scenario.
Real-world ad payoff distribution showing a unimodal, concentrated spread.

Key Insights and Ideas

  • The Futility of Perfection: In a mortal world, searching for the best arm is a trap. The "exploration tax" required to find the absolute top performer often exceeds the total potential reward that arm can give before it dies.
  • Linear Regret is Inevitable: Unlike static bandits where average regret goes to zero, mortal bandits have a "regret floor." Because arms are constantly dying and being replaced, the algorithm must always spend a portion of its time exploring, leading to linear regret ($\Omega(t)$).
  • Less is More: The success of the subset heuristic ($UCB1_{K/C}$) is a major takeaway. By intentionally ignoring the vast majority of available arms, the algorithm reduces its exploration burden, allowing it to find and use a "pretty good" arm much faster.

Key Results

  • Standard Algorithms Fail: The gold-standard UCB1 algorithm performed poorly in mortal settings. Because it tries to explore every arm at least logarithmically, it spends almost all its time exploring arms that die before they can be exploited. In some tests, UCB1 was barely better than picking arms at random.
Regret per time step vs. expected arm lifetime. UCB1 performs poorly compared to mortal-aware algorithms.
  • Superiority of Mortal-Aware Logic: The STOCHASTIC and ADAPTIVEGREEDY algorithms significantly outperformed UCB1 across all distributions.
  • Thresholding Works: The DETOPT strategy proved that having a "good enough" threshold is mathematically optimal for deterministic rewards, providing a clear target for how much exploration is "enough."

Limitations and Future Work

  • Known Distributions: The theoretical bounds and some algorithms assume the underlying distribution of arm payoffs ($F(\mu)$) is known. In a truly "cold start" scenario, this might not be the case.
  • Stationarity: The paper assumes the distribution of new arms arriving is stationary. Future work could explore "evolving" mortal bandits where the quality of new arrivals changes over time (e.g., during a holiday shopping surge).
  • Restless Mortality: The authors suggest looking into cases where an arm's payoff might change while it is alive, combining the "mortal" problem with the "restless" bandit problem.

Summary updated

Abstract

We formulate and study a new variant of the $k$-armed bandit problem, motivated by e-commerce applications. In our model, arms have (stochastic) lifetime after which they expire. In this setting an algorithm needs to continuously explore new arms, in contrast to the standard $k$-armed bandit model in which arms are available indefinitely and exploration is reduced once an optimal arm is identified with near-certainty. The main motivation for our setting is online-advertising, where ads have limited lifetime due to, for example, the nature of their content and their campaign budget. An algorithm needs to choose among a large collection of ads, more than can be fully explored within the ads' lifetime. We present an optimal algorithm for the state-aware (deterministic reward function) case, and build on this technique to obtain an algorithm for the state-oblivious (stochastic reward function) case. Empirical studies on various reward distributions, including one derived from a real-world ad serving application, show that the proposed algorithms significantly outperform the standard multi-armed bandit approaches applied to these settings.
BibTeX
@inproceedings{chakrabarti2008mortal,
  author = {Deepayan Chakrabarti and Ravi Kumar and Filip Radlinski and Eli Upfal},
  title = {{Mortal Multi-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=H1WyV_ZuZH},
}
Figure