A recommender choosing which news story to show faces two problems. The appeal of each story changes over time, and each story stops existing after a few hours. The best current algorithms for changing environments handle the first problem with a safety net. They spend a fixed fraction of decisions sampling every option uniformly at random, regardless of its past performance, so that a monitor can notice when a neglected option has improved. That fraction stays constant for the whole run, and the random pulls are spread evenly over all options. As a result, the algorithm keeps paying to check stories that will vanish before any improvement it found could be used.
This note proposes that the rate of forced uniform exploration should depend on how long each option has left to live. "Left to live" means the shorter of two things: the option's own remaining lifetime, and the remaining global horizon. An option should be forced into the sample only when an improvement detected now could still be exploited long enough to repay the checking cost. The resulting rule has a cutoff. Below a remaining life set by the change detector's reaction time, forced exploration of that option should stop entirely. Above it, the rate should grow with the remaining life. The cost of ignoring this shows up continuously whenever options have short or uneven lifetimes, which is exactly the regime of news, ads and other ephemeral content. It is not limited to the final rounds of a fixed horizon.
Core Claim
Change-detection bandits combine a standard upper-confidence-bound (UCB) learner with forced uniform sampling at a constant rate and a statistical test that resets an arm's statistics when its reward distribution shifts. M-UCB in Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit and CD-UCB in A Change-Detection Based Framework for Piecewise-Stationary Multi-Armed Bandit Problem are the two examples. They achieve near-$\sqrt{T}$ regret, but they set the forced rate once, as a function of the total horizon $T$ and the number of changes. Finite-horizon work points the other way. Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits and Nearly optimal exploration-exploitation decision thresholds show that the value of information shrinks with the steps remaining and should reach zero at the deadline. When to Make and Break Commitments? proves the same "decreasing optimism" toward a deadline for costly commitments.
Our claim joins these two lines in a specific way. The quantity that should govern forced exploration of arm $i$ is its remaining exploitable life, $\ell_i(t)=\min(e_i-t,\,T-t)$, where $e_i$ is the arm's expiry time (known, or replaced by its expectation $1/p$ under timed death with per-round probability $p$). The global time-to-go $T-t$ alone is the wrong quantity.
A simple accounting makes this concrete. Let $n_\delta \approx c\log(1/\eta)/\delta^2$ be the number of samples the detector needs to confirm a change of size $\delta$ at false-alarm level $\eta$. With forced rate $\alpha_i$ on arm $i$, detection lags by about $n_\delta/\alpha_i$ rounds. Arm $i$'s per-round forced rate should then approximately maximize
$$ J_i(\alpha_i)=\rho\,\ell_i\,\delta\left(\tfrac{\ell_i}{2}-\tfrac{n_\delta}{\alpha_i}\right)_{+}-\alpha_i\,\ell_i\,\bar g_i , $$
where $\rho$ is the per-round change rate, $\delta$ is the typical size of an upward change, and $\bar g_i$ is the current gap between arm $i$ and the leader. The first term is the expected reward recovered from detecting changes that occur during the remaining life. The second is the price of the forced pulls. Two predictions follow. First, $J_i$ is maximized at $\alpha_i=0$ whenever $\ell_i$ falls below a threshold of order $n_\delta/\alpha_{\max}$. Second, above that threshold the optimal rate rises with $\ell_i$ instead of staying flat.
Under equal, long lifetimes this reduces to near-constant forcing plus a terminal cutoff. In that case the gain over M-UCB is lower order, because the terminal waste is about $\alpha\, n_\delta/\alpha$ forced pulls against an $O(\sqrt{T})$ total. We state this openly because it pins down where the method should and should not help. The gain should be first-order exactly when lifetimes are short or heterogeneous.
The same accounting addresses an apparent contradiction. Exploration Unbound proves that for any finite horizon an optimal policy explores with nonzero probability at every step. That result lives in an environment with unbounded discoverable reward, where exploring can itself pay off immediately. In a bounded piecewise-stationary bandit, a forced pull whose information arrives after the arm's death or after $T$ is worthless by construction. Exploration must vanish per arm. Across the whole pool, however, it persists as long as long-lived arms keep arriving. This is consistent with the permanent exploration floor proved in Mortal Multi-Armed Bandits. The proposal therefore turns the question of when to stop exploring into the question of which arms deserve a check, given their remaining life.
Research Program
We will build a lifetime-aware forced exploration algorithm, LAFE, on top of the M-UCB structure. LAFE keeps M-UCB's sliding-window two-sample test and its UCB1 action selection. It replaces the single uniform rate with per-arm rates obtained by maximizing $J_i$. The estimates of $\rho$ and of the change-size distribution behind $\delta$ are updated from detected alarms, starting from a weak prior. This keeps the algorithm from needing the change count in advance, which is open problem 2 in the forced-exploration literature summarized in the file.
The detector's window is shrunk jointly with the rate, so that $n_\delta/\alpha_i$ never exceeds $\ell_i$. This is a direct response to the observation that a fixed window $w$ cannot even be filled once $T-t<w$.
The theoretical part has two goals. The first is a regret bound for piecewise-stationary mortal bandits, a setting that mortal-bandit work explicitly leaves open (Gap 5 in the file). The bound should replace the dependence on $T$ in $O(\sqrt{MKT\log T})$ with a dependence on the distribution of arm lifetimes. The second goal is a matching lower-bound construction. It would show that any algorithm forcing exploration at a lifetime-independent rate pays an extra cost proportional to the forced pulls spent on arms whose $\ell_i$ falls below the detection lag. We expect the analysis to adapt the M-UCB proof, with the window and rate made functions of $\ell_i$, which avoids building new detection machinery.
Baselines
The naive reference point is M-UCB run as published, with its constant forced rate and fixed window, both tuned to $T$ and the true number of breakpoints. This is the strongest existing method on the question. Cao et al. report that on the Yahoo! Front Page and digital marketing logs it achieves a 50% to 60% reduction in regret relative to discounted UCB and sliding-window UCB (Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit). The file gives no absolute regret value, so we will re-run it ourselves. Giving M-UCB oracle knowledge of the number of changes, which LAFE does not get, makes the comparison conservative.
The second baseline is CUSUM-UCB from A Change-Detection Based Framework for Piecewise-Stationary Multi-Armed Bandit Problem, which uses a different detector and probabilistic forcing. The third is SW-FE-Exp from Forced Exploration in Bandit Problems, which forces exploration through deterministic non-pull counters rather than random sampling. The fourth is the subset heuristic $UCB1_{K/C}$ from Mortal Multi-Armed Bandits, the strongest method designed for expiring arms. No reported numerical result was found on Lacuna for $UCB1_{K/C}$, or for CUSUM-UCB on Yahoo!, beyond qualitative statements of sublinear regret. We also include plain UCB1, which that paper describes as "barely better than picking arms at random" on its ad data, along with discounted and sliding-window UCB.
Three ablations isolate the key ingredient. The first, a hard cutoff, runs M-UCB but sets an arm's forced rate to zero once its remaining life drops below the window length. The second, global-horizon decay, makes the rate a function of $T-t$ only, with arm lifetimes ignored. The third is LAFE with a fixed rather than lifetime-matched window.
For fairness, every method uses the same environments, seeds and change sequences. Each tunable parameter (rate, window, threshold, $c$) gets the same grid of 20 settings, selected on held-out seeds and then frozen. LAFE counts as having beaten the baselines only if its cumulative regret is lower than the best-tuned M-UCB and the hard-cutoff ablation by more than the 95% confidence interval across 50 seeds, in the heterogeneous-lifetime regimes.
Why not just…?
Why not just switch off forced exploration near the end, or near each arm's death? This hard cutoff is the real threat, because the accounting above says the optimal schedule does contain a cutoff. Above the cutoff, the theory predicts that rates should still scale with remaining life, so long-lived newcomers should be checked more often than middle-aged arms. The hard-cutoff ablation tests this directly. If it matches LAFE within noise across the lifetime-heterogeneity sweep, we will report that the cutoff is all that matters. The contribution then narrows to the lower bound and the cutoff rule, and the smooth schedule is dropped.
Why not just tune a smaller constant rate when $T$ is known? M-UCB already sets its rate as a function of $T$. A single constant must compromise between short-lived arms, which need no checking, and long-lived arms, which need more. The prediction is that the best constant rate falls further behind as lifetime heterogeneity grows. The sweep below measures exactly this gap.
Why not just use passive forgetting such as sliding-window or discounted UCB? The file gives direct evidence against this. Cao et al. report a 50–60% regret reduction for M-UCB over both methods on Yahoo!, and Liu et al. show that passive methods degrade to linear regret when changes are small. We keep both methods as baselines but do not expect them to compete.
Why not just use the subset heuristic for mortal arms? $UCB1_{K/C}$ permanently ignores most of the pool, so it cannot detect upward shifts in the arms it ignores. The piecewise-stationary mortal environment is designed to show whether that blind spot costs more than the exploration it saves.
Proposed Experiments
The first environment extends the synthetic mortal bandits from Mortal Multi-Armed Bandits. It uses that paper's Uniform[0,1] and Beta(1,3) arrival distributions, both budgeted and timed death, and abrupt mean shifts while arms are alive. We sweep the coefficient of variation of lifetimes from zero to large. The decisive check has two parts. LAFE's advantage over best-tuned M-UCB should be near zero when all lifetimes are equal and long, and it should grow with lifetime heterogeneity. A flat advantage in either direction would falsify the mechanism.
The second environment is the 5-arm, $T=100{,}000$, five-breakpoint setup from Forced Exploration in Bandit Problems, with immortal arms. There LAFE should reduce to roughly M-UCB plus a terminal cutoff and gain little. This is a negative control.
We then shorten $T$ until it is comparable to the detection lag. In this regime the theory predicts a first-order gain over constant forcing.
The third test uses the Yahoo! Front Page Today Module click log, following the evaluation protocol of Cao et al. Article availability windows serve as arm lifetimes. The metric is cumulative regret and click-through rate relative to M-UCB.
The secondary metric everywhere is the fraction of forced pulls spent on arms that die before the next alarm on them could be acted on. This directly measures the waste the method targets.
References
- Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit
- A Change-Detection Based Framework for Piecewise-Stationary Multi-Armed Bandit Problem
- Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
- Nearly Optimal Exploration-Exploitation Decision Thresholds
- When to Make and Break Commitments?
- Exploration Unbound
- Mortal Multi-Armed Bandits
- Forced Exploration in Bandit Problems