Abstract
Standard Multi-Armed Bandit (MAB) algorithms often fail when rewards exhibit heavy-tailed behavior, such as those found in financial markets or social media dynamics. This paper addresses the challenge of applying Thompson Sampling to symmetric $\alpha$-stable reward distributions, which lack analytical density functions. By leveraging a Scale Mixture of Normals (SMiN) representation, the authors introduce $\alpha$-TS and Robust $\alpha$-TS. These algorithms utilize auxiliary variables to make posterior inference tractable and incorporate truncation techniques to handle extreme outliers. Theoretical analysis and empirical simulations demonstrate that these methods achieve near-optimal regret bounds in heavy-tailed environments where traditional Gaussian-based approaches falter.
Introduction
In the classic Multi-Armed Bandit (MAB) framework, an agent seeks to maximize cumulative rewards by balancing exploration and exploitation. While standard algorithms like Upper Confidence Bound (UCB) and Thompson Sampling (TS) perform well under light-tailed assumptions (e.g., Gaussian or bounded rewards), they are ill-equipped for "Black Swan" events. In domains like finance or signal processing, rewards often follow heavy-tailed distributions where extreme outliers are frequent.
The authors focus on the family of $\alpha$-stable distributions. These distributions are characterized by a stability parameter $\alpha \in (0, 2]$, where $\alpha=2$ corresponds to the Gaussian distribution and lower values indicate heavier tails.
As shown in the figure above, as $\alpha$ decreases, the distribution develops a sharper peak and significantly heavier tails, making standard Bayesian inference—which requires a tractable likelihood—computationally difficult.
Methods
To overcome the intractability of the $\alpha$-stable density function, the authors propose two primary innovations:
1. Scale Mixture of Normals (SMiN) Representation
A symmetric $\alpha$-stable distribution can be represented as a Gaussian distribution with a stochastic variance component. By introducing an auxiliary variable $\lambda$, the reward becomes conditionally Gaussian. This "trick" allows the use of Gibbs-sampling-like routines to update the posterior of the mean reward, bypassing the need for an explicit $\alpha$-stable likelihood.
2. Proposed Algorithms
- $\alpha$-TS: This algorithm directly applies the SMiN framework. It uses rejection sampling to handle the auxiliary variables, enabling Thompson Sampling in the $\alpha$-stable setting.
- Robust $\alpha$-TS: To further mitigate the impact of extreme outliers, this variant incorporates a truncated mean estimator. By ignoring rewards that exceed a specific threshold, the algorithm prevents "Black Swan" events from disproportionately biasing the agent's beliefs.
Key Results and Insights
The paper provides both theoretical guarantees and empirical evidence for the proposed methods.
Theoretical Regret Bounds
While standard MAB problems often aim for logarithmic regret, the authors prove that heavy-tailed environments generally necessitate polynomial regret. They provide the first finite-time polynomial bound on Bayesian Regret for Thompson Sampling in this setting. Notably, the bound for Robust $\alpha$-TS matches known optimal bounds for $\alpha \in (1, 2)$ within logarithmic factors.
Empirical Performance
Simulations were conducted using 100 independent experiments with 50 arms across different "tail fatness" levels ($\alpha=1.8$ and $\alpha=1.3$).
- Superiority: Both $\alpha$-TS and Robust $\alpha$-TS significantly outperformed standard Gaussian TS and Robust-UCB, particularly in the extremely heavy-tailed case ($\alpha=1.3$).
- Robustness: Robust $\alpha$-TS exhibited faster convergence and greater stability than the basic $\alpha$-TS, confirming that explicit truncation is a theoretically sound and practically effective strategy.
Conclusion
This work bridges the gap between Thompson Sampling and heavy-tailed reward distributions. By utilizing auxiliary variables and robust estimation techniques, the authors provide a computationally feasible and theoretically grounded framework for complex real-world decision-making. Future research may extend these results to asymmetric distributions ($\beta \neq 0$) or cases where the mean is undefined ($\alpha \le 1$), as well as applying these concentration results to Reinforcement Learning in heavy-tailed environments.
Summary updated