Abstract
In Multi-Armed Bandit (MAB) problems, traditional algorithms prioritize maximizing expected rewards, often neglecting the inherent risks in high-stakes environments like finance or medicine. This paper introduces a unified theoretical framework for risk-averse Thompson Sampling by defining a broad class of "continuous and dominant" risk functionals. We prove that the proposed algorithm, $\rho$-MTS, is asymptotically optimal for a wide range of popular risk measures, effectively consolidating years of fragmented research into a single, cohesive theory.
Introduction
Standard bandit algorithms are typically risk-neutral, focusing solely on the average reward. However, real-world decision-makers frequently need to account for tail risks or high volatility. Historically, researchers developed bespoke algorithms for specific risk measures, such as Conditional Value-at-Risk (CVaR) or Mean-Variance. This fragmentation obscured the underlying mathematical principles of risk-averse learning. This paper addresses this gap by identifying the common properties that allow Thompson Sampling to succeed across diverse risk-averse objectives.
The Unified Framework of Risk Functionals
The core contribution of this work is the definition of continuous and dominant risk functionals ($\rho$).
- Continuity: This ensures that minor fluctuations in the reward distribution result in only small changes to the calculated risk value.
- Dominance: A technical property governing how the risk measure behaves at the distribution's tails.
By establishing these criteria, the authors demonstrate that most ubiquitous risk measures—including Expected Value, CVaR, Entropic Risk, and Proportional Hazard—can be optimized using a single algorithmic approach. Notably, Value-at-Risk (VaR) is identified as an exception because it lacks continuity, explaining its historical difficulty in bandit optimization.
Proposed Algorithms: $\rho$-MTS and $\rho$-NPTS
The paper introduces two primary algorithms to handle different reward scenarios:
- $\rho$-MTS (Multinomial Thompson Sampling): Designed for discrete reward categories, this algorithm utilizes a Dirichlet distribution to maintain a posterior over possible outcomes.
- $\rho$-NPTS (Nonparametric Thompson Sampling): A flexible, distribution-free variant for general reward distributions. It samples directly from the history of observed rewards, making it highly adaptable to complex real-world data.
To support these algorithms, the authors developed new analytical toolkits, including generalized concentration bounds that describe the convergence speed of risk estimates.
Empirical Validation
The theory was tested using synthetic simulations involving a 3-arm bandit with rewards following various Beta distributions. The experiments, conducted over a horizon of $n = 5,000$ time steps and averaged over 50 runs, focused on the performance of the nonparametric $\rho$-NPTS variant.
The results demonstrate that the cumulative regret—the gap between the algorithm's performance and the optimal strategy—tracks remarkably close to the theoretical lower bounds. This empirical evidence supports the paper's primary theoretical highlight, Theorem 2, which establishes the asymptotic optimality of the $\rho$-MTS framework.
Key Insights and Future Directions
This research proves that the "machinery" of Thompson Sampling is robust enough to handle complex, hybrid risk measures (e.g., a weighted combination of Mean-Variance and CVaR) provided they meet the continuity criteria.
However, some limitations remain. While $\rho$-MTS is proven optimal, the optimality of the nonparametric $\rho$-NPTS currently relies on empirical evidence rather than a formal proof. Additionally, the current framework assumes bounded rewards (e.g., [0, 1]). Future work aims to extend these proofs to unbounded distributions, such as Gaussians, and explore "smoothed" versions of VaR to bring it within the unified framework.
Summary updated