Stochastic Multi-Armed Bandits with Strongly Reward-Dependent Delays

Yifu Tang, Yingfei Wang, Zeyu ZhengAISTATS 2024 · OpenReview

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:

  1. Observed Small Rewards: If a reward $r$ has arrived and $r \le m$, the actual value is used.
  2. Observed Large Rewards: If a reward $r$ has arrived and $r > m$, it is treated as $m$.
  3. 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

Abstract

There has been increasing interest in applying multi-armed bandits to adaptive designs in clinical trials. However, most literature assumes that a previous patient’s survival response of a treatment is known before the next patient is treated, which is unrealistic. The inability to account for response delays is cited frequently as one of the problems in using adaptive designs in clinical trials. More critically, the “delays” in observing the survival response are the same as the rewards rather than being external stochastic noise. We formalize this problem as a novel stochastic multi-armed bandit (MAB) problem with reward-dependent delays, where the delay at each round depends on the reward generated on the same round. For general reward/delay distributions with finite expectation, our proposed censored-UCB algorithm achieves near-optimal regret in terms of both problem-dependent and problem-independent bounds. With bounded or sub-Gaussian reward distributions, the upper bounds are optimal with a matching lower bound. Our theoretical results and the algorithms’ effectiveness are validated by empirical experiments.
BibTeX
@inproceedings{tang2024stochastic,
  author = {Yifu Tang and Yingfei Wang and Zeyu Zheng},
  title = {{Stochastic Multi-Armed Bandits with Strongly Reward-Dependent Delays}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=sPughSxwc7},
}

Loading related content...

Figure