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.
As shown in the figure above, the process follows a cycle:
- Posterior Distribution: Representing current uncertainty about the reward function.
- Thompson Sample: Drawing a candidate function from the posterior.
- Action and Observation: Selecting the optimal action 'a' based on the sample and observing the actual reward.
- 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.
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