Introduction
In reinforcement learning, the Multi-Armed Bandit (MAB) problem serves as a fundamental model for the exploration-exploitation trade-off. While traditional solutions often assume reward distributions are Gaussian or Bernoulli, real-world data—such as stock market returns or wireless network latencies—frequently exhibit "heavy tails" and "skewness." These characteristics are best captured by α-stable distributions. However, the lack of a closed-form probability density function (PDF) for asymmetric α-stable distributions makes traditional Bayesian updates in Thompson Sampling (TS) challenging.
A recent paper by researchers at the Tsinghua-Berkeley Shenzhen Institute introduces Asymmetric α-Thompson Sampling, a novel approach designed specifically for these complex, skewed reward environments.
The Challenge of Asymmetry
Standard MAB algorithms like Upper Confidence Bound (UCB) or vanilla TS typically assume finite variance or symmetry. When rewards follow an α-stable distribution, these assumptions fail. While prior research has addressed symmetric α-stable rewards, real-world data is often asymmetric. For instance, financial returns are notoriously skewed toward negative values.
In such cases, the "location parameter" (μ) does not correspond to the mean, and ignoring skewness leads to biased arm selection and suboptimal performance. The probability density function cannot be expressed analytically, making traditional Bayesian updates—the heart of Thompson Sampling—notoriously difficult.
The Asymmetric α-TS Framework
To address these complexities, the authors propose a specialized Thompson Sampling framework that handles the lack of a closed-form PDF and the presence of skewness through several key innovations:
- Location Parameter Estimation: The authors utilize a specific transformation to convert asymmetric variables into a non-skewed form, enabling an unbiased and consistent estimate of the location parameter μ.
- Auxiliary Variable Bayesian Inference: To bypass analytical complexity, the framework introduces auxiliary random variables (y). This allows the decomposition of the posterior distribution update into a more manageable integration formula.
- Theoretical Guarantees: The algorithm is supported by a finite-time Bayesian Regret bound of $O(N^{\frac{1}{1+\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}})$. Although this bound is super-linear, it accurately reflects the inherent uncertainty and difficulty of operating in heavy-tailed environments.
Experimental Evaluation
The algorithm was rigorously tested across three types of data:
- Synthetic Asymmetric Data: Controlled environments with specific impulsiveness (α) and skewness (β) parameters.
- Financial Data: Log returns of closing stock prices (specifically the AIV stock) from 2016 to 2020, exhibiting negative skewness and fat tails.
- Wireless Network Data: Latency measurements from visiting university home pages, representing real-world communication delays.
Key Results
The Asymmetric α-TS algorithm consistently outperformed standard baselines, including ε-greedy, Bootstrapped UCB, and the previously state-of-the-art Symmetric α-TS variant.
The results demonstrate that explicitly modeling the skewness parameter (β) is crucial. The performance gap between the asymmetric and symmetric versions of the algorithm widened as the data's skewness increased, proving that the proposed method more effectively identifies optimal arms in volatile environments.
Conclusion
Asymmetric α-Thompson Sampling provides a robust solution for MAB problems where rewards are heavy-tailed and skewed. By leveraging auxiliary variable inference and parameter transformations, the algorithm overcomes the analytical hurdles of α-stable distributions. While computationally more intensive than simpler heuristics, its ability to minimize regret in the face of "black swan" events makes it a valuable tool for financial modeling and network optimization.
Summary updated