Abstract
In many real-world applications of multi-armed bandits (MAB), such as clinical trials, the reward of an action is not observed immediately. While existing literature often treats these delays as independent stochastic noise, this paper addresses a more critical scenario where the delay is directly tied to the reward itself. We formalize the Stochastic MAB with Strongly Reward-Dependent Delays, where the time taken to observe a reward is a function of the reward's magnitude. We introduce Censored-UCB, an algorithm that leverages "censored" observations—treating the absence of a reward as a lower-bound signal—to achieve near-optimal regret. Our results demonstrate that for bounded or sub-Gaussian rewards, the algorithm achieves $O(\log T)$ regret, matching the performance of standard non-delayed bandits up to an additive constant.
Introduction
The multi-armed bandit framework is a cornerstone of sequential decision-making, yet its application in clinical trials is often hindered by the assumption of immediate feedback. In survival analysis, specifically regarding Progression-Free Survival (PFS), the "reward" (how long a patient survives without disease progression) is identical to the "delay" (the time we must wait to record that survival duration).
This dependency introduces a significant selection bias. Poor treatments yield short survival times and are reported quickly, while highly effective treatments yield long survival times and remain "hidden" in the pipeline for extended periods. Standard bandit algorithms that ignore this dependency tend to underestimate the value of superior treatments, potentially leading to suboptimal clinical outcomes. This paper formalizes this challenge and provides a theoretically grounded solution.
Problem Formulation
We consider a stochastic MAB problem where, at each round $t$, the learner chooses an arm $i_t$ and a reward $r_t$ is generated. Unlike the standard setting, the reward is only observed after a delay $d_t$. In this "strongly reward-dependent" model, we assume $d_t = \lceil r_t \rceil$.
The primary challenge is the "Stick-Together" phenomenon: a sub-optimal arm may appear competitive with an optimal arm for a long duration because the optimal arm's highest rewards are consistently the most delayed. A naive Upper Confidence Bound (UCB) approach, which only averages observed rewards, will be negatively biased toward arms with higher mean rewards.
The Censored-UCB Algorithm
To address this bias, we propose Censored-UCB. The core innovation lies in how the algorithm estimates the mean reward of an arm by incorporating "information in silence." Instead of relying solely on completed observations, the algorithm uses a censoring threshold $m$ that evolves over time.
For each arm, the estimator considers three types of data:
- Observed Small Rewards: If a reward $r$ has arrived and $r \le m$, the actual value is used.
- Observed Large Rewards: If a reward $r$ has arrived and $r > m$, it is treated as $m$.
- Censored Observations: If a reward has not yet arrived, but the time elapsed since the arm was pulled is at least $m$, the algorithm knows the reward must be at least $m$. It counts this as an observation of value $m$.
By setting the censoring threshold $m$ as a function of the horizon (e.g., $m(T) = \log T$), the algorithm balances the bias of censoring against the need to wait for high-value rewards. For scenarios where the horizon $T$ is unknown, a "doubling trick" is employed to maintain anytime performance.
Theoretical and Empirical Results
Regret Analysis
The paper provides rigorous regret bounds for Censored-UCB:
- General Distributions: For rewards with finite expectation, the algorithm achieves near-optimal regret.
- Bounded/Sub-Gaussian Rewards: The algorithm achieves $O(\log T)$ regret. Crucially, the "price" of the reward-dependent delay is shown to be an additive constant rather than a multiplicative factor, meaning that in the limit, the learning rate matches that of a bandit with no delays.
Experimental Validation
The authors evaluated the algorithm using synthetic environments simulating Poisson, Exponential, Binomial, and Gaussian distributions. These experiments confirmed that:
- Naive UCB often suffers linear regret, failing to identify the optimal arm because it consistently underestimates arms with long delays.
- Censored-UCB significantly outperforms existing state-of-the-art methods like OPSE (Optimistic Profile Sampling), which are designed for independent delays and struggle with the systematic bias of reward-dependent lags.
Conclusion and Future Work
Censored-UCB provides a robust framework for adaptive clinical trials where survival is the primary metric. By treating the absence of a response as a informative lower bound rather than missing data, the algorithm overcomes the inherent bias of reward-dependent delays.
Future research directions include relaxing the strong dependency assumption ($d_t = \lceil r_t \rceil$) to accommodate "noisy" dependencies and extending the framework to Contextual Bandits. Incorporating patient-specific covariates would allow for personalized medicine applications where the relationship between treatment, survival, and delay is modulated by individual genetic or clinical profiles.
Summary updated