On Thompson Sampling for Smoother-than-Lipschitz Bandits

James A. Grant, David S. LeslieAISTATS 2020

Introduction

Thompson Sampling (TS) is a cornerstone of Bayesian sequential decision-making, prized for its empirical performance in balancing exploration and exploitation. However, its theoretical foundations have primarily been established for simple parametric models. This paper addresses the Continuum-Armed Bandit (CAB) problem, where actions are chosen from a continuous space and reward functions are non-parametric but "smooth"—possessing multiple Lipschitz-continuous derivatives.

The authors provide the first theoretical regret bounds for TS in this setting, demonstrating that its performance improves significantly as the reward function's smoothness increases.

Methodology: Thompson Sampling in Continuous Spaces

The core of the Thompson Sampling approach involves maintaining a posterior distribution over the reward function. In each round, a sample is drawn from this posterior, and the action that maximizes this sample is selected.

The Thompson Sampling process in a continuum-armed bandit: from posterior distribution to sampling, action selection, and posterior update.

As shown in the figure above, the process follows a cycle:

  1. Posterior Distribution: Representing current uncertainty about the reward function.
  2. Thompson Sample: Drawing a candidate function from the posterior.
  3. Action and Observation: Selecting the optimal action 'a' based on the sample and observing the actual reward.
  4. Updated Posterior: Refining the model based on the new data point.

The analysis also generalizes previous TS frameworks to handle sub-exponential noise, a more realistic model than standard sub-Gaussian assumptions. The proof relies on decomposing Bayesian regret into the widths of high-probability confidence sets centered on a least-squares estimator of the reward function.

Theoretical Framework: Eluder Dimension and Smoothness

To analyze the regret of TS, the researchers extend the concept of the eluder dimension, a metric for the complexity of a function class. It quantifies how many observations are required to constrain the function's value at an unobserved point.

A major contribution of this work is deriving the first bounds on the eluder dimension for functions with $M$ Lipschitz derivatives. This involves complex mathematical constructions to show how smoothness limits the "wiggliness" of the function class.

Construction of functions used to derive bounds on the eluder dimension for smooth function classes.

By proving that the eluder dimension decreases as $M$ increases, the authors establish a direct link between the smoothness of the reward function and the efficiency of the learning process.

Key Insights and Results

The analysis yields several critical findings:

  • Smoothness Reduces Complexity: Higher smoothness (larger $M$) leads to a lower eluder dimension, resulting in faster learning rates.
  • Regret Bounds: The paper establishes an upper bound for Bayesian Regret: $$BR(T) = O\left(T^{\frac{2M^2+11M+10}{4M^2+14M+12}}\right)$$ For standard Lipschitz functions ($M=0$), this yields a rate of $O(T^{5/6})$, which improves to $O(T^{23/30})$ for functions with one Lipschitz derivative ($M=1$).

  • Asymptotic Optimality: As $M \to \infty$ (infinitely smooth functions), the regret rate approaches $O(\sqrt{T})$, matching the theoretical lower bound of $\Omega(T^{\frac{M+2}{2M+3}})$ in the limit and proving that exact Thompson Sampling is order-optimal.

Conclusion and Future Directions

While this work provides a significant theoretical leap, a gap remains between the derived upper and lower bounds for finite $M$. Future research is needed to determine if this gap stems from the inherent nature of Thompson Sampling or the tightness of eluder-dimension-based analysis. Additionally, since exact TS is often computationally prohibitive for non-parametric models, analyzing the regret of approximate TS methods (e.g., MCMC or Variational Inference) remains a vital open challenge.

Summary updated

BibTeX
@inproceedings{grant2020thompson,
  author = {James A. Grant and David S. Leslie},
  title = {{On Thompson Sampling for Smoother-than-Lipschitz Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure