Abstract
Thompson Sampling (TS) is a widely adopted Bayesian heuristic for the multi-armed bandit problem, known for its empirical efficiency and simplicity. However, its application and theoretical guarantees in the full-information online learning setting—specifically with linear experts—have remained less understood. This paper introduces a variant of Thompson Sampling, denoted as TSG($\epsilon$), which utilizes a time-varying Gaussian likelihood. We demonstrate that this Bayesian approach is mathematically equivalent to the frequentist Follow-the-Perturbed-Leader (FPL) strategy. By establishing this connection, we prove that TSG($\epsilon$) achieves the optimal $O(\sqrt{T})$ expected regret bound, providing a robust theoretical foundation for Thompson Sampling in full-information linear optimization environments.
1. Introduction
In online learning, a learner must make a sequence of decisions to maximize cumulative rewards or minimize regret against the best fixed decision in hindsight. Two primary feedback models dominate the literature: the bandit setting, where only the reward of the chosen action is observed, and the full-information setting, where the rewards for all possible actions are revealed after each step.
While Thompson Sampling has become a "gold standard" for bandit problems due to its natural balance of exploration and exploitation, frequentist methods like Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FPL) have traditionally dominated the full-information landscape. This paper bridges the gap between these two paradigms, showing that a carefully constructed Bayesian sampling procedure can recover the optimal performance of frequentist perturbation methods in linear settings.
2. Problem Formulation
We consider the problem of online linear optimization. At each time step $t = 1, \dots, T$:
- The learner chooses a decision vector $d_t$ from a convex set $\mathcal{D} \subset \mathbb{R}^n$.
- The environment reveals a state vector $s_t \in \mathbb{R}^n$.
- The learner receives a reward $\langle d_t, s_t \rangle$.
The learner's goal is to minimize the expected regret $R_T$, defined as: $$R_T = \mathbb{E} \left[ \max_{d \in \mathcal{D}} \sum_{t=1}^T \langle d, s_t \rangle - \sum_{t=1}^T \langle d_t, s_t \rangle \right]$$ In this full-information setting, the learner observes the entire vector $s_t$ at the end of each round, allowing them to update their strategy based on the complete history of rewards for all possible decisions.
3. The TSG($\epsilon$) Algorithm
The authors propose TSG($\epsilon$), a Thompson Sampling variant tailored for linear experts. The algorithm is defined by two primary Bayesian components:
- Gaussian Prior: The learner maintains a prior belief that the underlying mean reward vector $\mu$ follows a Gaussian distribution $\mathcal{N}(0, \frac{1}{\epsilon} I_n)$, where $\epsilon$ is a tuning parameter.
- Time-Varying Likelihood: Unlike standard TS, which often assumes a fixed noise level, TSG($\epsilon$) employs a likelihood where the variance of observations $s_k$ decreases over time. Specifically, the noise scales with $1/\sqrt{t-1}$.
At each time step $t$, the learner performs the following:
- Posterior Update: Update the distribution of $\mu$ based on the history of observations $S_{t-1} = \sum_{k=1}^{t-1} s_k$.
- Sampling: Draw a parameter $\theta_t$ from the resulting posterior distribution.
- Greedy Action: Choose the action $d_t = \arg \max_{d \in \mathcal{D}} \langle d, heta_t \rangle$.
4. Theoretical Analysis and Equivalence
The core contribution of the paper is the mathematical proof that the posterior sampling step in TSG($\epsilon$) is equivalent to adding Gaussian noise to the cumulative reward vector $S_{t-1}$. This reveals that TSG($\epsilon$) is essentially a Bayesian implementation of the Follow-the-Perturbed-Leader (FPL) algorithm.
While classic FPL often utilizes exponential or Gumbel noise to achieve optimal regret, the authors demonstrate that the Gaussian noise inherent in the TS framework is sufficient. By setting the hyperparameter $\epsilon = 1/T$, the algorithm ensures that the magnitude of the perturbation is correctly scaled relative to the time horizon $T$.
Key Results
- Optimal Regret Bound: The paper proves that the expected regret of TSG($\epsilon$) is bounded by $O(\sqrt{T})$. This matches the theoretical lower bounds for this class of problems, indicating that the learner's average regret vanishes at an optimal rate as $T \to \infty$.
- Bayesian-Frequentist Bridge: The work provides a formal link between Bayesian posterior sampling and frequentist leader-following strategies, suggesting that many successful frequentist algorithms can be reinterpreted through a Bayesian lens with specific likelihood structures.
5. Discussion and Limitations
While the paper provides a strong theoretical result, several considerations remain for practical application:
- Linearity: The derivation relies on the properties of linear reward functions and Gaussian distributions. Extending these results to non-linear reward structures or non-Gaussian noise models remains an open challenge.
- Computational Complexity: At each step, the learner must solve a linear optimization problem over the set $\mathcal{D}$. For high-dimensional or complex decision sets, the computational cost of this argmax operation may be significant.
- Full Information Requirement: The specific equivalence to FPL shown here depends on the learner having access to the full state vector $s_t$. While Thompson Sampling is effective in bandit settings, the $O(\sqrt{T})$ bound in this paper is specific to the full-information context.
6. Conclusion
This paper demonstrates that Thompson Sampling is not merely a heuristic for bandit problems but a theoretically sound algorithm for full-information online learning with linear experts. By introducing a time-varying Gaussian likelihood, the authors align TS with the optimal FPL framework, achieving the $O(\sqrt{T})$ regret bound that is the hallmark of efficient online learning algorithms.
Summary updated