Abstract
Standard multi-armed bandit algorithms typically focus on maximizing average rewards. However, in high-stakes domains like medicine, consistency is as critical as performance. This paper introduces BESA+, a non-parametric algorithm that optimizes for "consistency-aware regret," balancing high average outcomes with low variability to identify the most reliable treatments in clinical trials.
Introduction
In the world of Multi-Armed Bandits (MAB), the goal is usually to find the "arm" (or treatment) that yields the highest expected reward. However, the authors argue that in clinical trials, the mean is a dangerous metric when used in isolation. A treatment might have a high average survival rate but also high variability—meaning it works wonders for some but fails catastrophically for others.
Most existing bandit algorithms are risk-neutral; they do not account for whether a reward distribution is stable or volatile, provided the average is high. This paper addresses the need for risk-averse learning, designing an algorithm that can identify "reliable" policies—those with a high positive response rate and low variability—especially when sample sizes are small and outliers are present.
Methodology: The BESA+ Algorithm
The authors build upon the Best Empirical Sampled Average (BESA) algorithm to introduce BESA+. The core innovations include:
- Consistency-Aware Value Function: Instead of just looking at the empirical mean ($\hat{\mu}$), BESA+ evaluates arms using the formula $\hat{\mu} - \rho\hat{\sigma}^2$. Here, $\rho$ is a risk-aversion parameter that allows the user to penalize variance ($\sigma^2$).
- Sub-sampling Without Replacement: To compare two arms with different numbers of observations, the algorithm randomly sub-samples the arm with more data to match the sample size of the smaller one. This non-parametric approach helps mitigate bias when data is scarce.
- Forced Exploration: BESA+ ensures that every arm is pulled at least $\log(t)$ times, preventing the algorithm from prematurely discarding an arm that suffered an unlucky initial pull.
Experimental Evaluation
The researchers evaluated BESA+ using synthetic simulations and real clinical trial data involving survival times for lung cancer patients. The clinical data compared a standard treatment against a test treatment that had a higher mean survival time but significantly higher variance (more early deaths), making it a perfect test case for a consistency-aware algorithm.
Key Results
Theoretical analysis proves that BESA+ achieves a regret bound of $O(\log T)$, meeting the gold standard for efficient bandit algorithms.
In empirical tests, BESA+ identified optimal risk-adjusted arms faster than existing risk-averse benchmarks. On the lung cancer dataset, BESA+ correctly identified the more reliable treatment. While the alternative had a higher average survival due to a few long-term survivors, it also carried a higher rate of early mortality. BESA+ recognized this risk and favored the more consistent option, outperforming standard UCB1 and Thompson Sampling.
Conclusion and Future Work
BESA+ provides a robust framework for identifying reliable treatments by balancing performance with consistency. Future work includes developing formal confidence intervals for chosen arms and extending the consistency-aware logic to other frameworks like Thompson Sampling. Validating the algorithm in active data acquisition scenarios remains a key priority for real-world clinical application.
Summary updated