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:
- 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.
- 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.
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.
- Superiority of Mortal-Aware Logic: The
STOCHASTICandADAPTIVEGREEDYalgorithms significantly outperformed UCB1 across all distributions. - Thresholding Works: The
DETOPTstrategy 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