Thompson Sampling on Symmetric α-Stable Bandits

Abhimanyu Dubey, Alex PentlandarXiv 2019 · arXiv

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.

Probability density functions of symmetric $\alpha$-stable distributions for varying stability parameters $\alpha$.

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

Abstract

Thompson Sampling provides an efficient technique to introduce prior knowledge in the multi-armed bandit problem, along with providing remarkable empirical performance. In this paper, we revisit the Thompson Sampling algorithm under rewards drawn from symmetric $α$-stable distributions, which are a class of heavy-tailed probability distributions utilized in finance and economics, in problems such as modeling stock prices and human behavior. We present an efficient framework for posterior inference, which leads to two algorithms for Thompson Sampling in this setting. We prove finite-time regret bounds for both algorithms, and demonstrate through a series of experiments the stronger performance of Thompson Sampling in this setting. With our results, we provide an exposition of symmetric $α$-stable distributions in sequential decision-making, and enable sequential Bayesian inference in applications from diverse fields in finance and complex systems that operate on heavy-tailed features.
BibTeX
@misc{dubey2019thompson,
  author = {Abhimanyu Dubey and Alex Pentland},
  title = {{Thompson Sampling on Symmetric α-Stable Bandits}},
  year = {2019},
  eprint = {1907.03821},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.03821},
}
Figure