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

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

Read An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces by Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael Skoglund (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02140.txt.

Introduction

Amaury Gouverneur and co-authors bound the regret of a classic trial and learn algorithm when choices are endless. Their paper from 2025 studies Thompson sampling for bandit problems, where each round picks one action and learns from its payoff. Past sharp bounds assumed a finite action set.

The work extends a rate distortion frame to infinite and continuous action spaces. For payoff rules that vary smoothly with the action, the new bound shows the action space size cost in plain form. That closes a gap in the theory of a widely used method. The frame builds on a known information based line of work and keeps its near best rates in the linear case.

Catalog record

CREATORAmaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael Skoglund
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02140

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Information-Theoretic Analysis of Thompson Sampling with Infinite Action Spaces Thanks: This work was supported by the Knut and Alice Wallenberg Foundation. Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, and Mikael Skoglund Abstract This paper studies the Bayesian regret of the Thompson Sampling algorithm for bandit problems, building on the information-theoretic framework introduced by Russo and Van Roy [ 1 ] . Specifically, it extends the rate-distortion analysis of Dong and Van Roy [ 2 ] , which provides near-optimal bounds for linear bandits. A key limitation of these results is the assumption of a finite action space. We address this by extending the analysis to settings with infinite and continuous action spaces. Additionally, we specialize our results to bandit problems with expected rewards that are Lipschitz continuous with respect to the action space, deriving a regret bound that explicitly accounts for the complexity of the action space. I Introduction Bandit problems are a class of sequential decision-making problems where agents interact with an unknown environment by selecting actions and receiving rewards in return. The agent’s objective is to maximize its expected cumulative reward, which is the expected sum of rewards obtained during its interaction with the environment. This requires balancing exploration—trying different actions to gather information for future rewards—with exploitation, where the agent leverages known actions to maximize its immediate gain. Bandit problems have attracted significant attention due to their wide range of applications in fields such as healthcare, finance, recommender systems, and telecommunications (see [ 3 , 4 ] for surveys on various applications). The theoretical evaluation of an algorithm’s performance in bandit problems is typically done by studying the expected regret , which measures the gap between the cumulative reward earned by the algorithm and the reward an oracle would achieve by always selecting the optimal action [ 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ] . One effective method for achieving small regret is the Thompson Sampling (TS) algorithm [ 13 ] , which, despite its simplicity, has demonstrated remarkable performance [ 6 , 14 , 15 ] . Studying the Thompson Sampling regret, Russo and Van Roy [ 1 ] introduced the concept of information ratio . This statistic captures the trade-off between achieving immediate low regret and gaining information about the optimal action. Using this concept, they provide a general upper bound that depends on the prior entropy of the optimal action \textup{H}(A^{\star}) . A limitation of this result is that the prior entropy of the optimal action can grow arbitrarily large with the number of actions or get infinite if the action space is continuous. Combining the previous techniques with a rate-distortion analysis, Dong and Van Roy [ 2 ] were able to control the regret of Thompson Sampling via the entropy of a statistic of the parameter \Theta . This approach provides Bayesian regret bounds that remain sharp with large action spaces. In particular, they derived a near-optimal regret rate of O(d\sqrt{T\log T}) for d -dimensional linear bandit problems. However, their results are limited to bandit problems with finite action and environment space. In this work, we extend the results of [ 2 ] to settings with infinite and continuous action and parameter spaces. For bandit problems where the expected rewards are Lipschitz continuous with respect to a metric action space, we derive a regret bound that explicitly depends on the complexity of the action space. II Preliminaries II-A General Notation We denote random variables by capital letters (e.g., X ), their specific realizations by lowercase letters (e.g., x ), and their outcome spaces using calligraphic notation (e.g., \mathcal{X} ). The distribution of a random variable X is represented as \mathbb{P}_{X} . II-B Problem setup We consider a sequential decision-making problem where, at each time step t\in{1,\ldots,T} , an agent interacts with the environment by selecting an action A_{t}\in\mathcal{A} from a set of available actions \mathcal{A} . Based on the chosen action, the agent receives a real-valued reward R_{t}\in\mathbb{R} . The action-reward pair (A_{t},R_{t}) is then added to the history, updating it to H^{t+1}=H^{t}\cup\{A_{t},R_{t}\} , which will be available for decision-making in the next round. This process continues until t=T . In the Bayesian framework, the environment is characterized by a parameter \theta\in\mathcal{O} , which is unknown to the agent and drawn from a known prior distribution \mathbb{P}_{\Theta} . Together with the reward distribution \mathbb{P}_{R|A,\Theta} , this prior fully defines the bandit problem. Since the reward depends on the chosen action and the parameters, it can be expressed as R_{t}=R(A_{t},\Theta) for some possibly random function R:\mathcal{A}\times\mathcal{O}\to\mathbb{R} . The goal of the agent is to select actions that maximize the total accumulated reward. Specifically, the agent aims to learn a policy \pi=\{\pi_{t}:\mathcal{H}^{t}\to\mathcal{A}\}_{t=1}^{T} that, at each time t\in\{1,\ldots,T\} , selects an action A_{t} based on the history H^{t} . The objective is to find a policy that maximize the expected cumulative reward R_{T}(\pi)\coloneqq\mathbb{E}\left[\sum_{t=1}^{T}R(\pi_{t}(H^{t}),\Theta)\right] . If the agent had access to the parameter \Theta , it could always select the action that maximizes the expected reward defined by the mapping \pi_{\star}:\mathcal{O}\rightarrow\mathcal{A} as \pi_{\star}(\theta)=\textnormal{argmax}_{a\in\mathcal{A}}\mathbb{E}[R(a,\theta)] . We refer to such an action as the optimal action A^{\star}\coloneqq\pi_{\star}(\Theta) . To ensure such a policy exists, we make the technical assumption that the set of actions \mathcal{A} is compact. Following [ 16 ] , we assume that there exists a mapping \pi_{\star} is one-to-one 1 1 1 Note that Thompson Sampling disregards actions that are not optimal for any parameter. If a particular action is optimal for several parameters, we can include duplicate versions in the action set to ensure a one-to-one correspondence between each parameter and its optimal action (and similarly if a particular parameter is optimal for several actions). . We evaluate the performance of a policy \pi with its Bayesian regret, defined as: \mathbb{E}[\textnormal{Regret}(T)]\coloneqq\mathbb{E}\left[\sum_{t=1}^{T}R(A^{\star},\Theta)-R(A_{t},\Theta)\right], where the actions A_{t} are selected by the policy \pi , and the expectation is taken over the randomness of the action selection, the reward distribution, and the distribution of \Theta . II-C Thompson Sampling algorithm Thompson Sampling is an efficient algorithm for solving bandit problems. It works by selecting actions randomly based on their posterior probability of being optimal. Specifically, at each time step t\in\{1,\ldots,T\} , the agent samples a parameter estimate \hat{\Theta}_{t} from the posterior distribution, conditioned on the history H^{t} . The agent then selects the action that is optimal for the sampled parameter, A_{t}=\pi_{\star}(\hat{\Theta}_{t}) , receives a reward R_{t} , and updates the history to H^{t+1}=H^{t}\cup\{\hat{A}_{t},R_{t}\} . The pseudocode for Thompson Sampling is given in Algorithm 1 . Algorithm 1 Thompson Sampling algorithm 1: Input: parameter prior \mathbb{P}_{\Theta} . 2: for t=1 to T do 3: Sample a parameter estimate \smash{\hat{\Theta}_{t}\sim\mathbb{P}_{\Theta|H^{t}}} . 4: Take the corresponding optimal action A_{t}=\pi_{\star}(\hat{\Theta}_{t}) . 5: Collect the reward R_{t}=R(A_{t},\Theta) . 6: Update the history H^{t+1}=H^{t}\cup\{A_{t},R_{t}\} . 7: end for II-D Notations Specific to Bandit Problems Since the \sigma -algebras of the history are often used in conditioning, we introduce the notations \mathbb{E}_{t}[\cdot]\coloneqq\mathbb{E}[\cdot|H^{t}] and \mathbb{P}_{t}[\cdot]\coloneqq\mathbb{P}[\cdot|H^{t}] to denote the conditional expectation and probability given H^{t} . Additionally, we define \textup{I}_{t}(A^{\star};R_{t}|A_{t})\coloneqq\mathbb{E}_{t}[\textup{D}_{\textnormal{KL}}(\mathbb{P}_{R_{t}|H^{t},A^{\star},A_{t}}\|\mathbb{P}_{R_{t}|H^{t},A_{t}})] as the disintegrated conditional mutual information between the optimal action A^{\star} and the reward R_{t} conditioned on action A_{t} , given the history H^{t} . III

Read the complete text