Prior-free and prior-dependent regret bounds for Thompson Sampling

Introduction

where the expectation is taken with respect to the parameter $\theta$, the rewards $(X_{i,s})_{s\geq 1}$, and the external source of randomness $(U_{s})_{s\geq 1}$. We will also be interested in the individual regret $R_{n}(\theta)$ which is defined similarly except that $\theta$ is fixed (instead of being integrated over $\pi_{0}$). When it is clear from the context we drop the dependency on $\theta$ in the various quantities defined above.

In other words the value of the best arm is known as well as a non-trivial lower bound on the gap between the values of the best and second best arms. For this problem a new algorithm was proposed in Bubeck et al. (2013) (which we call the BPR policy), and it was shown that the BPR policy satisfies

Thus the BPR policy attains a regret uniformly bounded over time in the BPR setting, a feature that standard bandit algorithms such as UCB of Auer et al. (2002) cannot achieve. It is natural to view the assumptions of the BPR setting as a prior over the reward distributions and to ask what regret guarantees attains Thompson Sampling in that situation. More precisely we consider Thompson Sampling with Gaussian reward distributions and uniform prior over the possible range of parameters. We then prove individual regret bounds for any sub-Gaussian distributions (similarly to Bubeck et al. (2013)). We obtain that Thompson Sampling uses optimally the prior information in the sense that it also attains uniformly bounded over time regret. Furthermore as an added bonus we remove the extraneous log-log factor of the BPR policy’s regret bound.

The results presented in Section 3 and 4 can be viewed as a first step towards a better understanding of prior-dependent regret bounds for Thompson Sampling. Generalizing these results to arbitrary priors is a challenging open problem which is beyond the scope of our current techniques.

Optimal prior-free regret bound for Thompson Sampling

In this section we prove the following result.

For any prior distribution $\pi_{0}$ over reward distributions in $$, Thompson Sampling satisfies

Remark that the above result is unimprovable in the sense that there exist prior distributions $\pi_{0}$ such that for any algorithm one has $R_{n}\geq\frac{1}{20}\sqrt{nK}$ (see e.g. [Theorem 3.5, Bubeck and Cesa-Bianchi (2012)]). This theorem also implies an optimal rate of identification for the best arm, see Bubeck et al. (2009) for more details on this.

Step 1: rewriting of the Bayesian regret in terms of upper confidence bounds. This step is given by [Proposition 1, Russo and Roy (2013)] which we reprove for the sake of completeness. Let $B_{i,t}$ be a random variable measurable with respect to $\sigma(H_{t})$. Note that by definition $\theta^{(t)}$ and $\theta$ are identically distributed conditionally on $H_{t}$. This implies by the tower rule:

Inspired by the MOSS strategy of Audibert and Bubeck (2009) we will now take

where $\widehat{\mu}_{i,s}=\frac{1}{s}\sum_{t=1}^{s}X_{i,t}$, and $\log_{+}(x)=\log(x)\mathds{1}_{x\geq 1}$. In the following we denote $\delta_{0}=2\sqrt{\frac{K}{n}}$. From now on we work conditionally on $\theta$ and thus we drop all the dependency on $\theta$.

Next we extract the following inequality from Audibert and Bubeck (2010) (see p2683–2684), for any $i\in[K]$,

Next we use the following simple inequality:

Now for $u\geq\delta_{0}$ let $s(u)=\lceil 3\log\left(\frac{nu^{2}}{K}\right)/u^{2}\rceil$ where $\lceil x\rceil$ is the smallest integer large than $x$. Let $c=1-\frac{1}{\sqrt{3}}$. It is easy to see that one has:

Using an integration already done in Step 2 we have

Next using Hoeffding’s inequality and the fact that the rewards are in $$one has for$u\geq\delta_{0}$

Now using that $1-\exp(-x)\geq x-x^{2}/2$ for $x\geq 0$ one obtains

which concludes the proof together with the results of Step 1 and Step 2.

Thompson Sampling in the two-armed BPR setting

In order to derive the Thompson Sampling strategy for this problem we further assume that the reward distributions are in fact Gaussian with variance $1$. In other words let $\Theta=\{\theta_{1},\theta_{2}\}$, $\pi_{0}(\theta_{1})=\pi_{0}(\theta_{2})=1/2$, and under $\theta_{1}$ one has $X_{1,s}\sim\mathcal{N}(\mu^{*},1)$ and $X_{2,s}\sim\mathcal{N}(\mu^{*}-\Delta,1)$ while under $\theta_{2}$ one has $X_{2,s}\sim\mathcal{N}(\mu^{*},1)$ and $X_{1,s}\sim\mathcal{N}(\mu^{*}-\Delta,1)$. Then a straightforward computation (using Bayes rule and induction) shows that one has for some normalizing constant $c>0$:

Recall that Thompson Sampling draws $\theta^{(t)}$ from $\pi_{t}$ and then pulls the best arm for the environment $\theta^{(t)}$. Observe that under $\theta_{1}$ the best arm is arm $1$ and under $\theta_{2}$ the best arm is arm $2$. In other words Thompson Sampling draws $I_{t}$ at random with the probabilities given by the posterior $\pi_{t}$. This leads to a general algorithm for the two-armed BPR setting with sub-Gaussian reward distributions that we summarize in Figure 1. The next result shows that it attains optimal performances in this setting up to a numerical constant (see Bubeck et al. (2013) for lower bounds), for any sub-Gaussian reward distribution (not necessarily Gaussian) with largest mean $\mu^{*}$ and gap $\Delta$.

The policy of Figure 1 has regret bounded as $R_{n}\leq\Delta+\frac{578}{\Delta}$, uniformly in $n$.

Note that we did not try to optimize the numerical constant in the above bound. Figure 2 shows an empirical comparison of the policy of Figure 1 with Policy 1 of Bubeck et al. (2013). Note in particular that a regret bound of order $16/\Delta$ was proved for the latter algorithm and the (limited) numerical simulation presented here suggests that Thompson Sampling outperforms this strategy.

Proof Without loss of generality we assume that arm $1$ is the optimal arm, that is $\mu_{1}=\mu^{*}$ and $\mu_{2}=\mu^{*}-\Delta$. Let $\widehat{\mu}_{i,s}=\frac{1}{s}\sum_{t=1}^{s}X_{i,t}$, $\widehat{\gamma}_{1,s}=\mu_{1}-\widehat{\mu}_{1,s}$ and $\widehat{\gamma}_{2,s}=\widehat{\mu}_{2,s}-\mu_{2}$. Note that large (positive) values of $\widehat{\gamma}_{1,s}$ or $\widehat{\gamma}_{2,s}$ might mislead the algorithm into bad decisions, and we will need to control what happens in various regimes for these $\gamma$ coefficients. We decompose the proof into three steps.

Step 1. This first step will be useful in the rest of the analysis, it shows how the probability ratio of a bad pull over a good pull evolves as a function of the $\gamma$ coefficients introduced above. One has:

Step 2. We decompose the regret $R_{n}$ as follows:

We use Hoeffding’s inequality to control the first term:

For the second term, using the rewriting of Step 1 as an upper bound on $p_{t}(2)$, one obtains:

The third term is more difficult to control, and we further decompose the corresponding event as follows:

The cumulative probability of the first event in the above decomposition is easy to control thanks to Hoeffding’s maximal inequalityIt is an easy exercise to verify that Azuma-Hoeffding holds for martingale differences with sub-Gaussian increments, which implies Hoeffding’s maximal inequality for sub-Gaussian distributions. which states that for any $m\geq 1$ and $x>0$ one has

where the last inequality follows from Step 1. The last step is devoted to bounding from above this last term.

Step 3. By integrating the deviations and using again Hoeffding’s maximal inequality one obtains

which concludes the proof by putting this together with the results of the previous step.

Optimal strategy for the BPR setting inspired by Thompson Sampling

Similarly to the previous section we assume that the reward distributions are Gaussian with variance $1$ for the derivation of the Thompson Sampling strategy (but we do not make this assumption for the analysis of the resulting algorithm). Then the set of possible parameters is described as follows:

Assuming a uniform prior over the index of the best arm, and a prior $\lambda$ over the mean of a suboptimal arm one obtains by Bayes rule that the probability density function of the posterior is given by:

Now remark that with Thompson Sampling arm $i$ is played at time $t$ if and only if $\theta^{(t)}\in\Theta_{i}$. In other words $I_{t}$ is played at random from probability $p_{t}$ where

Taking inspiration from the above calculation we consider the following policy, where $\lambda$ is the Lebesgue measure and we assume a slightly larger value for the variance (this is necessary for the proof).

The following theorem shows that this policy attains the best known performance for the BPR setting, shaving off a log-log term in the regret bound of the BPR policy.

The policy of Figure 3 has regret bounded as $R_{n}\leq\sum_{i:\Delta_{i}>0}\left(\Delta_{i}+\frac{80+\log(\Delta_{i}/\varepsilon)}{\Delta_{i}}\right)$, uniformly in $n$.

Proof The general structure of the proof is superficially similar to the proof of Theorem 2 but many details are different. Without loss of generality we assume that arm $1$ is the optimal arm, that is $\mu_{1}=\mu^{*}$ and $\forall i\geq 2,\mu_{i}=\mu^{*}-\Delta_{i}$. Let $\widehat{\gamma}_{1,s}=\mu_{1}-\widehat{\mu}_{1,s}$ and $\widehat{\gamma}_{i,s}=\widehat{\mu}_{i,s}-\mu_{i}$ for $i\geq 2$. We decompose the proof into four steps.

Step 1: Rewriting of the ratio $\frac{p_{i,t}}{p_{1,t}}$. Let $i\geq 2$, the following rewriting will be useful in the rest of the proof:

where the last step follows by a simple change of variable.

Step 2: Decomposition of $R_{n}$. For $i\geq 2$. Let $A_{i}=\lceil\frac{6}{\Delta_{i}^{2}}\log(\frac{e^{6}\Delta_{i}}{\varepsilon})\rceil$ where $\lceil x\rceil$ is the smallest integer larger than $x$. We decompose the regret $R_{n}$ as follows.

The first expectation can be bounded by using Hoeffding’s inequality.

The second expectation is more difficult to bound from above and the next two steps are dedicated to this task.

We have now to control the term $\frac{p_{t}(i)}{p_{t}(1)}$ on the event $\{\widehat{\gamma}_{i,T_{i}(t-1)}\leq\frac{\Delta_{i}}{4},T_{i}(t-1)\geq A_{i}\}$. The following bounds on the tail of the standard Gaussian distribution will be useful, for any $x>0$ one has

Next, using the fact that the function $x\rightarrow\frac{1}{x}e^{\frac{1}{6}x\Delta_{i}^{2}}$ is increasing on $[\frac{6}{\Delta_{i}^{2}},+\infty)$, we get

Plugging into the expression of $\frac{p_{t}(i)}{p_{t}(1)}$, we obtain

The first term is straightforward to compute:

For the second term, we first integrate the deviations and we use Hoeffding’s inequality to obtain

Putting together all the steps finishes the proof.

References