Abstract
Thompson Sampling (TS) is widely recognized as a powerful heuristic for multi-armed bandit (MAB) problems, often achieving theoretical lower bounds for regret in light-tailed distributions. However, its performance on heavy-tailed distributions, such as the two-parameter Pareto distribution, remains less understood. This paper investigates the behavior of Sequential Thompson Sampling (STS) under various noninformative priors. We demonstrate that the standard Jeffreys prior leads to suboptimal polynomial regret due to excessive optimism. To address this, we prove that a specific family of conservative priors ($k \ge 2$) or a novel truncation mechanism (STS-T) can restore asymptotic optimality, achieving the theoretical regret lower bound.
Introduction
In the Multi-Armed Bandit (MAB) framework, an agent seeks to maximize cumulative rewards by balancing the exploration of unknown arms with the exploitation of known high-performing arms. Thompson Sampling (TS) has emerged as a preferred Bayesian approach for this task. While its optimality is well-documented for single-parameter or light-tailed distributions (e.g., Gaussian, Bernoulli), real-world data—ranging from insurance claims to network traffic—frequently exhibits heavy-tailed behavior, often modeled by the Pareto distribution.
The Pareto Type 1 distribution is characterized by two parameters: a scale parameter ($\kappa$) and a shape parameter ($\alpha$). The presence of two unknown parameters and the heavy-tailed nature of the distribution present significant challenges for standard Bayesian exploration strategies. This study explores whether TS can maintain optimality in this setting and how the choice of "noninformative" priors influences long-term performance.
Methodology: Sequential Thompson Sampling
The authors propose Sequential Thompson Sampling (STS) to handle the two-parameter Pareto model. In this approach, the parameters are sampled sequentially from the posterior distribution: first, the shape parameter ($\alpha$) is sampled from a marginalized posterior, followed by the scale parameter ($\kappa$) conditioned on the sampled $\alpha$.
The research evaluates a family of noninformative priors defined by the parameter $k$: $$\pi(\kappa, \alpha) \propto \frac{\alpha^{-k}}{\kappa}$$
Two primary versions of the algorithm are analyzed:
- Standard STS: Utilizes the prior directly. This includes the Jeffreys prior ($k=0$) and the reference prior ($k=1$).
- STS-T (Truncated): This variant introduces a truncation step for the shape parameter $\alpha$. By capping the estimator based on the number of times an arm has been played, the algorithm prevents the "over-optimism" that typically leads to high regret in heavy-tailed scenarios.
The Jeffreys Prior Trap and the Necessity of Conservatism
A central finding of this work is the failure of the Jeffreys prior ($k=0$). While the Jeffreys prior is often considered the default noninformative prior in Bayesian statistics, the authors prove it is suboptimal for Pareto bandits. It tends to overestimate the shape parameter early in the process, causing the agent to remain stuck on suboptimal arms for an excessive duration, resulting in polynomial regret.
Conversely, the authors show that more "conservative" priors—specifically those where $k \ge 2$—provide a natural safeguard. These priors slightly overestimate the probability that a suboptimal arm might be beneficial, ensuring sufficient exploration without the catastrophic over-optimism seen with $k=0$. For $k \ge 2$, STS is proven to achieve the asymptotic lower bound for regret: $$R(T) \approx \sum \frac{\Delta_a \log T}{KL_{inf}(a)}$$ where $\Delta_a$ is the gap between the optimal arm and arm $a$, and $KL_{inf}$ represents the Kullback-Leibler divergence.
Experimental Validation
The theoretical findings were validated through Monte Carlo simulations involving 100,000 independent trials. The experiments focused on 4-armed bandit models, including configurations with infinite variance to test the limits of the heavy-tail handling.
The results confirmed that:
- STS with $k=3$ significantly outperformed the Jeffreys prior ($k=0$).
- STS-T (Truncated STS) successfully rescued the performance of the Jeffreys and reference priors. By applying truncation, these previously suboptimal priors achieved performance levels comparable to the optimal $k=3$ prior and significantly reduced the variance (the "tail") of the regret distribution.
Conclusion and Future Work
This research provides the first proof of asymptotic optimality for two-parameter Pareto bandits using Thompson Sampling. It highlights a critical nuance in Bayesian reinforcement learning: the choice of a noninformative prior is not neutral. In heavy-tailed environments, standard priors like Jeffreys can lead to failure, but optimality can be recovered through conservative prior selection or algorithmic truncation.
While this study focuses on Pareto Type 1 distributions, future research may extend these insights to other heavy-tailed classes, such as Fréchet or Levy distributions. Additionally, while the current results are asymptotically optimal, further investigation is needed to optimize the "initialization" phase to improve short-term performance without sacrificing long-term efficiency.
Summary updated