Abstract
Piecewise stationary stochastic multi-armed bandits have been extensively explored in the risk-neutral and sub-Gaussian setting. In this work, we consider a multi-armed bandit framework in which the reward distributions are heavy-tailed and non-stationary, and evaluate the performance of algorithms using general risk criteria. Specifically, we make the following contributions: (i) We first propose a non-parametric change detection algorithm that can detect general distributional changes in heavy-tailed distributions. (ii) We then propose a truncation-based UCB-type bandit algorithm integrating the above regime change detection algorithm to minimize the regret of the non-stationary learning problem. (iii) Finally, we establish the regret bounds for the proposed bandit algorithm by characterizing the statistical properties of the general change detection algorithm, along with a novel regret analysis.
1. Introduction
In the Multi-Armed Bandit (MAB) framework, an agent must pull a sequence of arms to maximize total rewards from unknown payout distributions. While standard MAB models assume stationarity and light-tailed rewards, real-world applications such as high-frequency trading or healthcare management often face non-stationary environments where the optimal arm changes over time, and heavy-tailed distributions where extreme outliers are common. Furthermore, decision-makers in these fields are often risk-averse, prioritizing the avoidance of significant losses over simple mean maximization.
This paper addresses the "triple threat" of non-stationarity, heavy tails, and general risk criteria. We propose a unified framework, the Risk-Sensitive Switching Confidence Bound (RS-SCB) algorithm, to navigate these complex environments effectively.
2. Methodology
The proposed solution integrates two primary components designed to handle distributional shifts and outliers.
2.1 Risk-sensitive Heavy-tail Detection (RHD)
To address non-stationarity, we introduce RHD, a non-parametric change detection module. RHD employs a sliding window to monitor reward streams. A critical feature is its window-driven truncation mechanism, which filters out extreme values based on the window size. This prevents heavy-tailed outliers from triggering false alarms while maintaining sensitivity to genuine shifts in the underlying risk profile.
2.2 Risk-Sensitive Switching Confidence Bound (RS-SCB)
RS-SCB is the core bandit algorithm, extending the Upper Confidence Bound (UCB) approach to risk-sensitive and heavy-tailed settings. It utilizes:
- Policy-Driven Truncation: Rewards are truncated based on the number of times an arm has been pulled, ensuring tight concentration bounds despite heavy tails.
- Active Adaptation: By continuously running the RHD module, the algorithm can detect regime changes and reset the history for affected arms, allowing for rapid adaptation to new environments.
The framework is general and can accommodate any risk measure $U$ that satisfies certain mathematical properties, such as quasi-convexity and continuity. This allows RS-SCB to be applied to a wide range of risk-sensitive objectives beyond mean-variance or CVaR.
3. Experimental Evaluation
The performance of RS-SCB was evaluated using synthetic simulations mimicking challenging real-world data. We utilized three heavy-tailed distributions: Student’s-t distribution (degree 2), standard log-normal distribution, and Pareto distribution (power index 2). These were tested against two primary risk measures: Linear Risk (standard mean) and Conditional Value at Risk (CVaR), which focuses on tail-end outcomes.
4. Results and Discussion
Theoretical analysis confirms that RS-SCB achieves near-optimal regret bounds. In simulations, the algorithm demonstrated a consistent ability to identify the optimal arm as the environment shifted.
As illustrated in the figure above, the percentage of optimal arm selections increases steadily with the horizon $T$, regardless of the specific distribution or risk measure. The plots show performance for different numbers of regimes ($M = 2, 4, 8$), indicating that while more frequent changes make the problem harder, the algorithm maintains a positive learning trajectory. The RHD module proved highly effective, achieving nearly 100% detection of change points once sufficient data was accumulated. Key insights include the necessity of truncation for handling heavy-tailed data and the superiority of active adaptation over passive sliding-window approaches.
5. Conclusion
RS-SCB provides a robust framework for decision-making in non-stationary, heavy-tailed, and risk-sensitive environments. Future research will focus on making the algorithm parameter-free (removing the need for prior knowledge of the number of regimes or tail heaviness) and extending the framework to contextual and adversarial bandit settings.
Summary updated