Thompson Sampling on Symmetric Alpha-Stable Bandits

Abhimanyu Dubey, Alex PentlandIJCAI 2019 · DOI

Introduction

The Multi-Armed Bandit (MAB) problem is a fundamental framework in machine learning for modeling the trade-off between exploration and exploitation. While standard algorithms like Thompson Sampling (TS) and Upper Confidence Bound (UCB) perform exceptionally well under Gaussian or bounded reward distributions, they often falter in environments characterized by heavy-tailed rewards. In domains such as finance, where stock prices exhibit extreme volatility, or social networks, where user engagement follows power-law distributions, the presence of frequent outliers can severely degrade the performance of traditional bandit algorithms.

This paper addresses the challenge of MAB problems where rewards follow symmetric $\alpha$-stable distributions. These distributions are particularly difficult to handle because they lack analytical probability density functions (PDFs) for most values of $\alpha$ and possess infinite variance when $\alpha < 2$. This paper introduces the first efficient Thompson Sampling framework designed specifically for these heavy-tailed settings.

Methodology

The primary technical hurdle in applying Thompson Sampling to $\alpha$-stable distributions is the intractability of the Bayesian posterior update due to the lack of a closed-form PDF. The authors overcome this by utilizing a Scale Mixture of Normals (SMiN) representation.

Scale Mixture of Normals (SMiN)

The core innovation lies in representing a symmetric $\alpha$-stable distribution as a Gaussian distribution with a stochastic variance. Specifically, an $\alpha$-stable variable $x$ can be decomposed as $x \sim N(\mu, \lambda\sigma^2)$, where $\lambda$ is an auxiliary variable drawn from a specific stable distribution. This decomposition transforms an intractable likelihood into a conditionally Gaussian one, enabling the use of standard conjugate priors for the mean $\mu$.

$\alpha$-TS and Robust $\alpha$-TS

Building on the SMiN representation, the authors propose two algorithms:

  1. $\alpha$-TS: This algorithm employs a Gibbs-sampling-like approach. It samples the auxiliary variable $\lambda$ via rejection sampling and subsequently updates the posterior of the mean $\mu$ using the Gaussian likelihood.
  2. Robust $\alpha$-TS: To mitigate the impact of extreme outliers, this version incorporates a truncated mean estimator. By ignoring rewards that exceed a time-dependent threshold, the algorithm prevents massive outliers from disproportionately influencing the posterior, which is a critical requirement in heavy-tailed environments.

Experimental Setup

The proposed algorithms were evaluated through extensive synthetic simulations designed to replicate heavy-tailed scenarios. The benchmarks included $\epsilon$-greedy, standard Gaussian Thompson Sampling (Gaussian-TS), and Robust-UCB. The experiments tested various characteristic exponents, specifically $\alpha = 1.3$ (highly heavy-tailed) and $\alpha = 1.8$ (closer to Gaussian), across a 50-arm bandit problem with a time horizon of $T=5000$. The sensitivity of the algorithms to prior information was also examined by varying the accuracy of the initial mean estimates.

Results and Discussion

The experimental results demonstrate the clear superiority of the proposed framework in heavy-tailed settings.

Performance comparison and sensitivity analysis of $\alpha$-TS and Robust $\alpha$-TS against baselines. (A) and (B) show time-normalized regret over time. (C) and (D) show regret sensitivity to $\alpha$ and prior parameters.

As shown in Figure 1, both $\alpha$-TS and Robust $\alpha$-TS significantly outperform Gaussian-TS and Robust-UCB when $\alpha = 1.3$. Gaussian-TS, in particular, often fails to converge to the optimal arm because it cannot distinguish between a high-mean arm and a "lucky" outlier from a suboptimal arm. Robust $\alpha$-TS exhibits the most stable performance, with lower variance in regret across trials, confirming that the truncation mechanism effectively handles extreme noise.

Theoretically, the authors prove that Robust $\alpha$-TS achieves a Bayesian Regret of $\tilde{O}((KT)^{\frac{1}{1+\epsilon}})$, matching the theoretical lower bounds for heavy-tailed bandits. This indicates that the algorithm is near-optimal for this class of problems. Furthermore, ablation studies revealed that $\alpha$-TS benefits significantly from accurate priors, highlighting its ability to leverage domain knowledge more effectively than frequentist UCB-style approaches.

Conclusion

This work provides a robust and computationally feasible Bayesian framework for multi-armed bandits with $\alpha$-stable rewards. By leveraging the SMiN representation, the authors have made Bayesian inference possible for a class of distributions previously considered "black boxes."

However, some limitations remain. The current implementation assumes that the distribution parameters $\alpha$ and $\sigma$ are known. Future work could involve online estimation of these parameters. Additionally, extending the framework to asymmetric $\alpha$-stable distributions would broaden its applicability to a wider range of real-world phenomena. The success of the SMiN-based approach also suggests potential extensions to more complex reinforcement learning problems in heavy-tailed environments.

Summary updated

BibTeX
@inproceedings{dubey2019thompson,
  author = {Abhimanyu Dubey and Alex Pentland},
  title = {{Thompson Sampling on Symmetric Alpha-Stable Bandits}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/792},
}
Figure