An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces

Amaury Gouverneur, Borja Rodríguez Gálvez, Tobias J. Oechtering, Mikael Skoglund

Abstract

This paper extends the information-theoretic analysis of Thompson Sampling (TS) to multi-armed bandit problems with infinite and continuous action spaces. By leveraging rate-distortion theory and introducing a novel "compressed" statistic of the optimal action, the authors derive near-optimal Bayesian regret bounds that explicitly account for the geometric complexity of the action space. This approach resolves a significant theoretical gap where previous entropy-based bounds became vacuous in continuous settings.

Introduction

In sequential decision-making, Thompson Sampling (TS) is a highly popular and effective algorithm for multi-armed bandit problems. To understand why TS performs so well, researchers previously introduced the "information ratio," which bounds the algorithm's Bayesian regret based on the entropy of the optimal action. However, a major theoretical hurdle exists: if the action space is continuous or infinite, the entropy of the optimal action can become infinite, rendering these bounds useless.

While subsequent work attempted to bypass this using rate-distortion theory to compress the environment parameter, those proofs strictly required finite action or parameter spaces. This paper provides a rigorous framework to bound the regret of Thompson Sampling in environments where both the action space and the parameter space are infinite and continuous.

The Challenge of Infinite Action Spaces

Algorithm 1: The standard Thompson Sampling algorithm. An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces, page 2

Algorithm 1: The standard Thompson Sampling algorithm.

The standard Thompson Sampling algorithm, as shown in Algorithm 1, relies on sampling a parameter estimate $\hat{\Theta}_t$ from the posterior distribution and taking the corresponding optimal action. In finite settings, the regret is controlled by the amount of information the agent learns about the optimal action. In continuous settings, the "amount of information" (entropy) is not well-defined in the same way. Previous attempts to compress the environment parameter $\Theta$ faced mathematical breakdowns in continuous spaces without finite support.

Methodology: Compressing the Optimal Action

The authors' primary innovation is a shift in the compression target. Instead of trying to compress the complex environment parameter $\Theta$, they construct a compressed statistic, $A^\star_\epsilon$, of the optimal action $A^\star$.

To achieve this, they introduce a novel technical lemma (Proposition 1) that partitions the continuous action space. This partitioning ensures that the compressed statistic provides just enough information to bound the regret—staying "$\epsilon$-close" to standard TS regret—without revealing more information about the optimal action than standard TS would naturally acquire. By applying this framework to environments where the reward function is Lipschitz continuous, they can use covering numbers (a topological measure of space complexity) to finalize their bounds. This elegantly bypasses the technical roadblocks that limited previous proofs to finite spaces.

Key Results and Theoretical Bounds

The paper establishes several significant new bounds for Thompson Sampling:

  • General Regret Bound: The authors derived a general Bayesian regret bound for TS of $\sqrt{\tilde{\Gamma} T H(A^\star_\epsilon)} + \epsilon T$, where $\tilde{\Gamma}$ is the information ratio bound, $T$ is the time horizon, and $H(A^\star_\epsilon)$ is the entropy of the compressed optimal action.
  • Lipschitz Regret Bound: For $L$-Lipschitz reward functions, the regret is bounded by $\sqrt{\tilde{\Gamma} T \log(\mathcal{N}(\mathcal{A}, \rho, \epsilon))} + L\epsilon T$. Here, $\mathcal{N}$ is the covering number, which explicitly ties the algorithm's performance to the dimensionality and size of the action space.
  • Improved Linear Bandit Bounds: When applied to $d$-dimensional linear bandits with actions in a unit ball, the technique achieves a near-optimal regret bound of $2d\sqrt{T \log(\sqrt{2} + \frac{4\sqrt{T}}{d})}$. This actually improves upon previous state-of-the-art bounds by reducing the constant factors inside the logarithmic terms by a factor of 2.

Conclusion and Future Work

This research provides a critical bridge between information theory and continuous-space bandit problems. By focusing on the compression of the optimal action rather than the environment parameters, the authors have created a more flexible and precise tool for analyzing Bayesian regret.

While the paper is strictly theoretical, it sets the stage for future empirical validation and extensions. The authors suggest that these information-theoretic results could be extended to other classes of problems, such as "semi-bandit" feedback scenarios, where agents observe rewards for multiple individual actions within a chosen set.

Summary updated

BibTeX
@inproceedings{gouverneur2025information,
  author = {Amaury Gouverneur and Borja Rodríguez Gálvez and Tobias J. Oechtering and Mikael Skoglund},
  title = {{An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10888239},
}
Figure