Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits

Introduction

In CMAB, the whole joint distribution of the vector of outcomes ${\bf X}$ matters, contrary to standard MAB where only the marginals are sufficient to characterize a problem instance. For example, the following two extreme problem instances are distinct within the CMAB framework:

Those two settings are indeed different as two different lower bounds on the asymptotic (in $T$) regret can be derived. In particular, the regret scales as \Omega\mathopen{}\mathclose{{}\left(n\log(T)/\Delta}\right) for the setting LABEL:indep_setting, and as \Omega\mathopen{}\mathclose{{}\left(mn\log(T)/\Delta}\right) for LABEL:arb_cor_setting, where $\Delta$ is the minimum gap in the expected reward between an optimal super arm and any non-optimal super arm, and where m\triangleq\max_{A\in\mathcal{A}}\mathopen{}\mathclose{{}\left|A}\right|.

Many CMAB policies are based on the Upper Confidence Bound (UCB) approach, extending the classical ucb policy [Auer et al., 2002] from MAB to CMAB. This type of approach uses an optimistic estimate ${\boldsymbol{\mu}}_{t}$ of ${\boldsymbol{\mu}}^{*}$ (i.e., for which the reward function is overestimated), lying in a well-chosen confidence region. For setting LABEL:arb_cor_setting, there exist UCB-style policies that match the lower bound mentioned above. An example of such policy is Combinatorial Upper Confidence Bound (cucb) [Chen et al., 2013, Kveton et al., 2015], that uses a Cartesian product of the individual confidence intervals of each arm as a confidence region. For setting LABEL:indep_setting, Combes et al. provided the UCB-style policy Efficient Sampling for Combinatorial Bandit (escb), that uses the assumption of mutual independence between arm distributions in order to build a tighter ellipsoidal confidence region around the empirical mean, which helps to better restrict the exploration. Degenne and Perchet [2016b] gave the following generalization of setting LABEL:indep_setting:

In this case, they provided the policy ols-ucb, leveraging this additional assumption and such that it essentially reduces to escb in the specific case of diagonal matrix ${\bf C}$ with a regret bound of \mathcal{O}\mathopen{}\mathclose{{}\left(\log^{2}(m)n\log(T)/\Delta}\right)) (so it matches the above lower bound up to a polylogarithmic factor in $m$). We refer the reader to Table 1 for an overview of the above regret (lower) bounds.

The inefficiency of escb triggered some attempts to implement an efficient version: Perrault et al. [2019a] proposed an efficient approximation method for implementing escb in the case the action space has a matroid structure: they prove a time complexity of \mathcal{O}\mathopen{}\mathclose{{}\left(\text{poly}(n)}\right) while keeping the same regret rate. However, this improvement is mitigated by the fact that cucb reaches the optimal regret rate \mathcal{O}\mathopen{}\mathclose{{}\left(n\log(T)/\Delta}\right) for the special case of matroid semi-bandits [Anantharam et al., 1987, Kveton et al., 2014, Talebi and Proutiere, 2016]. Recently, Cuvelier et al. provided another approach for approximating escb for a wide variety of action spaces, including the matching bandit setting [Gai et al., 2010] and the online shortest path problem [Liu and Zhao, 2012], where cucb is not known to be better than escb. However, their policies are still computationally expensive when $T$ is large, since the time complexity at round $t$ is of order \mathcal{O}\mathopen{}\mathclose{{}\left(t\cdot\text{poly}(n)}\right).

Although the aforementioned upper bound in the linear reward case outperforms the one of cucb, it doesn’t match the one of escb. To summarize, and despite many efforts, the existence of a policy that is both optimal (up to a polylogarithmic factor in $m$) and efficient in the setting LABEL:indep_setting or LABEL:subgau_setting is still an open problem, which we tackle in this paper.

We refer the reader to Wang and Chen for further related work on ts for combinatorial bandits, and particularly for Gopalan et al. , that provided a frequentist high-probability regret bounds for ts with a general action space and a general feedback model — Komiyama et al. , that investigated ts for the $m$-sets action space — Wen et al. , that studied ts for contextual CMAB problems, using the Bayesian regret metric (see also Russo and Van Roy ).

1 Contributions

Model

where \Delta_{t}\triangleq\Delta\mathopen{}\mathclose{{}\left(A_{t}}\right)\triangleq r(A^{*},{\boldsymbol{\mu}}^{*})-r(A_{t},{\boldsymbol{\mu}}^{*}) with $A^{*}\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}r(A^{\prime},{\boldsymbol{\mu}}^{*})$. As stated in the introduction, we will assume the following:

Similar to Chen et al. , we assume that the function $r$ satisfies the following smoothness property.

There exists a constant $B$, such that for every super arm $A\in\mathcal{A}$ and every pair of mean vectors ${\boldsymbol{\mu}}$ and ${\boldsymbol{\mu}}^{\prime}$, \mathopen{}\mathclose{{}\left|r(A,{\boldsymbol{\mu}})-r(A,{\boldsymbol{\mu}}^{\prime})}\right|\leq B\mathopen{}\mathclose{{}\left\|{\bf e}_{A}\odot\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}-{\boldsymbol{\mu}}^{\prime}}\right)}\right\|_{1}.

m^{*}\triangleq\min_{A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\mu}}^{*}}\mathopen{}\mathclose{{}\left|A}\right| is the minimum size of an optimal action,

\Delta_{i,\min}\triangleq\min_{A\in\mathcal{A},~{}\Delta\mathopen{}\mathclose{{}\left(A}\right)>0,~{}i\in A}\Delta\mathopen{}\mathclose{{}\left(A}\right), is the minimal gap of an action containing $i\in[n]$,

$\Delta_{\min}\triangleq\min_{i\in[n]}\Delta_{i,\min},$ is the minimal arm-gap and

\Delta_{\max}\triangleq\max_{A\in\mathcal{A}}\Delta\mathopen{}\mathclose{{}\left(A}\right) is the maximal gap.

Regret bound for cts-beta in setting LABEL:indep_setting

In this section, we consider the following assumption on top of the CMAB setting from section 2.

The outcomes $X_{i}$ are bounded (in $$, w.l.o.g.), and are mutually independent (we are thus in a special case of LABEL:indep_setting).

The main result of this section is Theorem 1, that improves the regret bound of Wang and Chen for cts-beta.

The policy $\pi$ described in Algorithm 1 has regret $R_{T}(\pi)$ of order

The proof of Theorem 1, as well as the complete non-asymptotic upper-bound is postponed to Appendix A. Our analysis incorporates two novelties that we detail in the two following paragraphs.

The second ingredient is a more careful handling of the square-root term in the above probability, based on a method similar to the one in Degenne and Perchet [2016b].

T𝑇T-independent term

(cf. Step 4 of the proof of Theorem 1 in Appendix A) Similarly to Wang and Chen , our regret bound also contains an exponential term that is constant in $T$. Note, however that the term of Wang and Chen is of order $\mathcal{O}(\varepsilon^{-2m^{*}-2})$, whereas ours is of order \mathcal{O}\mathopen{}\mathclose{{}\left(\varepsilon^{-4m^{*}-2}}\right), where $\varepsilon\in(0,1)$ is of order $\Delta_{\min}/{(m^{*})}^{2}$. This discrepancy is due to the correction of a minor negligence inaccuracy in their Lemma 7, where they assume, at the end of the proof, that one could decorrelate the counters from the outcomes received. We manage to circumvent this issue by doing a careful union bound over the counters. It is this union bound that brings a larger dependence in this constant term. An additional discussion is deferred to the end of Appendix A.

Regret bound for cts-gausian in setting LABEL:subgau_setting

Assumption 4 encompasses the $\kappa_{i}^{2}$-sub Gaussian outcomes with worst case dependencies between the arm distributions, taking $D_{i}=\kappa_{i}^{2}m$. It also captures ${\bf C}$-sub-Gaussian outcomes with a known sub-Gaussian matrix ${\bf C}$ (setting LABEL:subgau_setting), taking D_{i}=\max_{A\in\mathcal{A},~{}i\in A}\sum_{j\in A}\mathopen{}\mathclose{{}\left|C_{ij}}\right|.

The policy $\pi$ described in Algorithm 2 has regret $R_{T}(\pi)$ of order

The proof of Theorem 2, as well as the complete non-asymptotic upper-bound is postponed to Appendix C. Nonetheless, in the following paragraphs, we provide some insights and highlight the novelty of our analysis.

Main proof challenges

In the setting of the previous section, the outcomes are independent in $$ and an important step in Algorithm 1 was to transform the outcomes into binary variables in order to be consistent with the posterior. Here, outcomes are no longer independent. In addition to that, we cannot transform the outcomes into Gaussian variables in the same way as in Algorithm 1. These two points are the main technical challenges to address in our analysis.

Stochastic dominance

The first point applied to $g_{i}$’s (and up to the supremum over $t$) is a simple way to obtain the aforementioned wanted control. Thus, it’s enough to prove the second point, which is a consequence of the sub-Gaussianity of outcomes given by Assumption 4 and some concentration inequality. Finally, we circumvent the supremum over $t\geq 1$ issue thanks to Doob’s optional sampling theorem for non-negative super-martingales (see Durrett , Theorem 5.7.6).

Importance of using a factorized prior in our analysis

1 clip cts-gaussian for the linear reward case

In this subsection, we make the following assumptions on top of Section 2.

The reward function is linear, defined as $r(A,{\boldsymbol{\mu}})\triangleq{\bf e}_{A}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\mu}}$.

The policy clip cts-gaussian has regret of order

The leading term in the regret bound given from Theorem 3 is comparable to the one for ols-ucb from Degenne and Perchet [2016b]. Indeed, we recall that they obtained a factor of order \Gamma_{ii}\mathopen{}\mathclose{{}\left((1-\gamma)\log^{2}(m)+\gamma m}\right), with \gamma\triangleq\max_{A\in\mathcal{A}}\max_{(i,j)\in A^{2},i\neq j}\mathopen{}\mathclose{{}\left(0\vee\Gamma_{ij}}\right)/\sqrt{\Gamma_{ii}\Gamma_{jj}}, where we have \mathopen{}\mathclose{{}\left(D_{i}\log^{2}(m)\wedge m\Gamma_{ii}}\right). When \gamma\in\mathopen{}\mathclose{{}\left\{0,1}\right\} (this is the case when we are in the settings LABEL:indep_setting and LABEL:arb_cor_setting respectively), these two terms coincide. When $\gamma\in(0,1)$, they are incomparable in general. We can still see that our variance term $D_{i}$ is always lower than their \Gamma_{ii}\mathopen{}\mathclose{{}\left((1-\gamma)+\gamma m}\right), i.e., that our bound rate is lower than $\log^{2}(m)$ times theirs.

Experiments

Before describing the experiments carried out, notice that in the cts-gaussian policies, $\beta>1$ is an artefact of the analysis and can in practice be taken equal to $1$. This is what we did in our experiments.

Comparison to escb for the matching problem

Correlated vs independent prior in practice

We briefly discussed the use of a correlated prior in footnote 3, with covariance \mathopen{}\mathclose{{}\left(C_{ij}N_{ij,t-1}N^{-1}_{i,t-1}N^{-1}_{j,t-1}}\right)_{ij}, mentioning that the policy would perform better than using an independent prior. We ran additional empirical comparisons to assess this, plotting the results in Figure 3 where we also compared with a common prior policy approach [Agrawal et al., 2017], i.e., with covariance \mathopen{}\mathclose{{}\left({N^{-1/2}_{i,t-1}N^{-1/2}_{j,t-1}}}\right)_{ij}.We also tried the policy (without displaying the results, for the sake of clarity) with covariance \mathopen{}\mathclose{{}\left(C_{ij}{N^{-1/2}_{i,t-1}N^{-1/2}_{j,t-1}}}\right)_{ij}, and observed about the same performance as the correlated prior approach. As expected, the correlated prior policy is better than the independent one (when outcomes are correlated). This motivates the theoretical study of such policy for future work. The common prior approach is comparable to the correlated prior one on the matching problem, but it is outperformed in the worst-case scenario of a separate action space \mathcal{A}=\mathopen{}\mathclose{{}\left\{\mathopen{}\mathclose{{}\left\{km+1,\dots,(k+1)m}\right\}\mid k\in\mathopen{}\mathclose{{}\left\{0,\dots,\frac{n}{m}-1}\right\}}\right\} with independent outcomes. This is because such problem reduces to a classical MAB problem with a covariance scaled up by a factor $m$, whereas the common prior approach has a variance scaled up by a factor $m^{2}$.

Conclusion and future work

Broader Impact

This work does not present any foreseeable societal consequence.

Acknowledgments and Disclosure of Funding

The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, French National Research Agency project BOLD (ANR19-CE23-0026-04).

It was also supported in part by a public grant as part of the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program for optimization, operations research and their interactions with data sciences.

References

Appendix A Proof of Theorem 1

We first restate the complete non-asymptotic upper-bound as follows.

The policy $\pi$ described in Algorithm 1 has regret $R_{T}(\pi)$ bounded by

where $C,C^{\prime}$ are two universal constants, and $\varepsilon\in(0,1)$ is such that ${\Delta_{\min}}/(2B)-({m^{*}}^{2}+1)\varepsilon>~{}0.$

In order to prove Theorem 1, we modify two lemmas from Wang and Chen : first, in their Lemma 3, we replace $\varepsilon$ by {\Delta_{\min}}/\mathopen{}\mathclose{{}\left(2B}\right)-({m^{*}}^{2}+1)\varepsilon>0, which gives the following Lemma 1.

Then, we modify Lemma 4 from Wang and Chen as follows, leveraging on the mutual independence of $\theta_{1,t},\dots,\theta_{n,t}$ to get a tighter confidence region for the sample ${\boldsymbol{\theta}}_{t}$.

In Algorithm 1, for all round $t$, we have

From [Marchal et al., 2017], the Beta random variable from $\theta_{i,t}$ is sub-Gaussian with variance $1/(4N_{i,t-1})$. Thus, defining the functions

A.2 Main proof

With the two lemmas from the previous subsection, we are ready to demonstrate Theorem 1. We consider the following events.

\mathfrak{Z}_{t}\triangleq\mathopen{}\mathclose{{}\left\{\Delta_{t}>0}\right\}

\mathfrak{B}_{t}\triangleq\mathopen{}\mathclose{{}\left\{\exists i\in A_{t},~{}{\mathopen{}\mathclose{{}\left|A_{t}}\right|}\cdot\mathopen{}\mathclose{{}\left|\overline{\mu}_{i,t-1}-\mu_{i}^{*}}\right|>{{\Delta_{\min}}/\mathopen{}\mathclose{{}\left(2B}\right)-({m^{*}}^{2}+1)\varepsilon}}\right\}

\mathfrak{C}_{t}\triangleq\mathopen{}\mathclose{{}\left\{{\mathopen{}\mathclose{{}\left\|{\bf e}_{A_{t}}\odot\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}_{t}-{\boldsymbol{\mu}}^{*}}\right)}\right\|_{1}}>\Delta_{t}/B-\mathopen{}\mathclose{{}\left({m^{*}}^{2}+1}\right)\varepsilon}\right\}

\mathfrak{D}_{t}\triangleq\mathopen{}\mathclose{{}\left\{\mathopen{}\mathclose{{}\left\|{\bf e}_{A_{t}}\odot\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}_{t}-\overline{\boldsymbol{\mu}}_{t-1}}\right)}\right\|_{1}\geq\sqrt{{0.5}\cdot{\log\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left|\mathcal{A}}\right|2^{m}T}\right)}\sum_{i\in{A_{t}}}{1}/{N_{i,t-1}}}}\right\}.

We break down our analysis into 4 steps. The main novelties are in the last two steps: Step 3 gives us the tighter dependence in $m$, and Step 4, that contains the main difficulties, gives the new exponential constant term.

So we have that the following event holds

We can thus apply Theorem 4 (see Appendix E) to get the bound

We consider the following events for a subset $Z\subset[n]$

We can state the three following lemmas. Note that Lemma 3 is exactly the Lemma 1 from Wang and Chen . The other two replace their Lemma 7.

In Algorithm 1, for all round $t$, we have

Given $Z\subset A^{*},~{}Z\neq\emptyset$, let $\tau_{q}$ be the round at which \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right)\wedge\neg\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right) occurs for the $q$-th time, and let $\tau_{0}=0$. Then, in Algorithm 1, we have

where $c$ and $c^{\prime}$ are two universal constants.

These lemmas allow us to get a constant regret under the event $\mathfrak{Z}_{t}\wedge\neg\mathfrak{C}_{t}$. Indeed, we have from Lemma 3 that

Lemma 4 and 5 gives that the above is further upper bounded by

where $C$ and $C^{\prime}$ are two universal constants. This concludes the proof of the theorem.

Since \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right),\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right) are independent conditioned on the history $\mathcal{H}_{t}$, the LHS is

is lower than all the success probabilities of the time-varying geometric distribution. This gives the result by monotonicity of the expectation, and rewriting the expectation of the geometric distribution. ∎

for some universal constant $c^{\prime\prime}$. Since \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right)\wedge\neg\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right) implies that $Z\subset A_{t}$, we know that for $\tau\geq\tau_{q}+1$, $N_{i,\tau-1}\geq q$ for all $i\in Z$. Using the mutual independence of outcomes, and the fact that the distribution of $\theta_{i,\tau}$ depends only on the history of arm $i$, we have

From this point, there are two cases: If $q>8/\varepsilon^{2}$,

where $c,c^{\prime}$ are two universal constant. ∎

A.3 Discussion on the new exponential constant term (step 4 in the above proof)

We give here an explanation concerning the modification of Lemma 7 from Wang and Chen . First, we respectfully disagree with the end of their proof, where the expected number of time slots for \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right)\wedge\neg\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right) to occur is a weighted mean of expectations where the counters are fixed and non-random. To obtain such a weighted mean, they have conditioned on the value of the counters. However, counters depend on the chosen action, and thus on the outcomes previously obtained, so conditioning on it would modify the expectation, since the term inside the expectation not only depends on counters, but also on outcomes obtained so far. To illustrate more clearly this point, let us focus on one arm $i$, and consider the extreme case where we get a new sample (i.e. the counter is incremented) only if samples $Y_{i,t}$ previously obtained from $i$ were all , say. Then conditioning on the fact that the counter is incremented would remove all the randomness of samples $Y_{i,t}$, and we thus can’t consider an expectation on those samples as if their randomness was not impacted.

We now expose our approach to overcome this issue. We first rewrite the above mentioned expected number of time slots as the expectation (over the history) of the expectation of a time-varying geometric distribution, where the time-varying success probability depends on the history. The inner expectation can be bounded by the expectation of a geometric distribution whose success probability is the infimum over all the success probabilities of the time-varying geometric distribution. Let’s note that this gives us the inverse success probability minus one, as in Wang and Chen , but that counters are still random. We use that this inverse probability can be factorized: from the relation \prod_{i\in A}a_{i}-1=\sum_{A^{\prime}\subset A,~{}A^{\prime}\neq\emptyset}\prod_{i\in A^{\prime}}\mathopen{}\mathclose{{}\left(a_{i}-1}\right), valid for any vector ${\bf a}=(a_{i})$ on a set $A$, and from the mutual independence of outcomes, we’re reduced to bounding the expectation in the one-dimensional case. To overcome the randomness of the counters, we use an union bound. It is this union bound that brings a larger dependence on the constant term, because it forces us to look at a sum of the form $\sum_{q}\sum_{k\geq q}x_{k}$, instead of a simply $\sum_{q}x_{q}$. Let’s remark that Wang and Chen use the eventual exponential decreasing of the sequence \mathopen{}\mathclose{{}\left(x_{q}}\right) in order to get their final bound. We manage to deal with the sequence \mathopen{}\mathclose{{}\left(\sum_{k\geq q}x_{k}}\right) instead, by noticing that the eventual exponential decreasing of the sequence \mathopen{}\mathclose{{}\left(x_{q}}\right) implies the eventual exponential decreasing of the sequence \mathopen{}\mathclose{{}\left(\sum_{k\geq q}x_{k}}\right).

Appendix B Proof of Proposition 1

Assumption 4 encompasses $\kappa_{i}^{2}$-sub Gaussian outcomes with $D_{i}=\kappa_{i}^{2}m$ for all $i\in[n]$. Indeed, let ${\boldsymbol{\lambda}}={\boldsymbol{\lambda}}\odot{\bf e}_{A}$ for some action $A$ and observe that

Appendix C Proof of Theorem 2

We beginning by stating the complete version of Theorem 2.

The policy $\pi$ described in Algorithm 2 has regret $R_{T}(\pi)$ bounded by

where $C,C^{\prime}$ are two universal constants, and $\varepsilon\in(0,1)$ is such that ${\Delta_{\min}}/(2B)-({m^{*}}^{2}+1)\varepsilon>~{}0.$

For the proof of Theorem 2, we consider the same events as in the proof of Theorem 1, except for the event $\mathfrak{D}_{t}$, that becomes

Step 1 is unchanged. Step 2 and Step 3 are modified only through the event $\mathfrak{D}_{t}$, using the following modification of Lemma 2.

We rely on the fact that conditionally on the history, the sample ${\boldsymbol{\theta}}_{t}$ is Gaussian of mean $\overline{\boldsymbol{\mu}}_{t-1}$ and of diagonal covariance given by $\beta D_{i}N_{i,t-1}^{-1}$. We thus define the functions

The final bound on the regret in Step 3 is obtained using the same derivation as in Theorem 1, which gives the following leading term:

In the following, we consider the last step, consisting in bounding the regret under the event $\mathfrak{Z}_{t}$ and $\neg\mathfrak{C}_{t}$. From the initialization phase, we also assume that the event

We use the independence of the prior, as for Theorem 1, to obtain the following upper bound, using $\mathfrak{M}_{t}$ to be able to start from $q=1$.

However, the expectation can’t be put inside the product since outcomes are not mutually independent. We can still take a union bound on counters:

In particular, we can consider the inverse function $g_{i}^{-1}$. We now want to use a stochastic dominance argument in order to treat the outcomes as if they were Gaussian: we have for any ${\bf k}\in[q..\infty)^{Z^{\prime}}$,

Now, we want to use the following fact (see Chang et al. ): if $\eta\sim\mathcal{N}(0,1)$, then with $\beta>1$,

where ${\boldsymbol{\eta}}\sim\mathcal{N}(0,1)^{\otimes Z^{\prime}}$. Thus,

We first bound $A_{1}$. With the change of variable $u=y-x$, we get:

Note that for $x\geq\alpha\varepsilon_{i}$ and $u\in[-\varepsilon_{i},0]$, $-u^{2}/2-ux\geq-(1-\frac{1}{2\alpha})ux$ and thus:

We distinguish two regimes. First, if $\varepsilon_{i}^{2}\geq 12$, then

We now bound $A_{2}$. As $x\in[-\alpha\varepsilon_{i},\alpha\varepsilon_{i}]$, it comes that $[-(1-\alpha)\varepsilon_{i},(1-\alpha)\varepsilon_{i}]\subset[x-\varepsilon_{i},x+\varepsilon_{i}]$. This implies that

After the summation on ${\bf k}$, on $Z^{\prime}$, on $q$, and on $Z$, we obtain that there exists two constants $C,C^{\prime}$ such that

Appendix D Proof of Theorem 3 (clip cts-gaussian for linear rewards)

In this section, we provide an analysis for the regret bound of clip cts-gaussian, which is stated completely as follows.

The policy clip cts-gaussian has regret bounded by

where $C,C^{\prime}$ are two universal constants, and $\varepsilon\in(0,1)$ is such that ${\Delta_{\min}}/(2B)-({m^{*}}^{2}+1)\varepsilon>~{}0.$

More precisely, notice that the modification on the sample ${\boldsymbol{\theta}}_{t}$ has an impact only in two places in the analysis: in the concentration bound and in the event controlling optimism. We detail these two points in the following.

In this subsection, we provide the concentration bound of clip cts-gaussian. Our strategy here is to either use the concentration from ${\boldsymbol{\mu}}_{t}$ or from ${\boldsymbol{\theta}}_{t}$, depending on which regime is the best for each arm. Thus, we define S\triangleq\mathopen{}\mathclose{{}\left\{i\in[n],~{}\Gamma_{ii}m\mathopen{}\mathclose{{}\left(\log(T)+4\log\log(T)}\right)\geq 4\log^{2}_{2}(4\sqrt{m})\beta D_{i}\log\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left|A}\right|2^{m}T}\right)}\right\}. We have the following lemma.

We now use the definition of ${\boldsymbol{\mu}}_{t}$ to have

We can thus apply Theorem 5 and Theorem 4 (see Appendix E) to get the bound

D.2 Optimism

In this subsection, we examine the theoretical impact of considering clip cts-gaussian on the optimism-controlling event (event $\neg\mathfrak{C}_{t}$), in the case of linear rewards. For this purpose, we modify the beginning of Step 4 in the analysis by considering the following events.

\mathfrak{Z}_{t}\triangleq\mathopen{}\mathclose{{}\left\{\Delta_{t}>0}\right\}

\mathfrak{C}_{t}\triangleq\mathopen{}\mathclose{{}\left\{{{{\bf e}_{A_{t}}^{\mathsf{\scriptscriptstyle T}}\widetilde{\boldsymbol{\theta}}_{t}}}>{\bf e}_{A^{*}}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\mu}}^{*}-\mathopen{}\mathclose{{}\left(m^{*}\mathopen{}\mathclose{{}\left(m^{*}+1}\right)/2+1}\right)\varepsilon}\right\}

\mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right)\triangleq\mathopen{}\mathclose{{}\left\{\forall{\boldsymbol{\theta}}^{\prime}\text{ s.t. }0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime}}\right)\odot{\bf e}_{Z}\leq\varepsilon{\bf e}_{Z},~{}\mathfrak{R}({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{Z}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{Z^{c}},Z)\text{ holds}}\right\}

\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right)\triangleq\mathopen{}\mathclose{{}\left\{\exists i\in Z,~{}{{\mu^{*}_{i}-\mu^{*}_{i}\wedge\widetilde{\theta}_{i,t}}}>\varepsilon}\right\}.

\mathfrak{J}_{t}\triangleq\mathopen{}\mathclose{{}\left\{\forall i\in[n],\mu^{*}_{i}\leq\mu_{i,t}}\right\}

In the above events, $\widetilde{\boldsymbol{\theta}}_{t}$ is ${\boldsymbol{\mu}}_{t}\wedge{\boldsymbol{\theta}}_{t}\vee\overline{\boldsymbol{\mu}}_{t}$. The last event $\mathfrak{J}_{t}$ holds with probability at least $1-n/(t\log^{2}(t))$ from Hoeffding’s inequality [Hoeffding, 1963]. We thus assume that this event hods in the following, since the regret under the complementary event is bounded by $3.2n\Delta_{\max}$. We first state the following lemma.

because $\neg\mathfrak{C}_{t}$ and \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right) together imply \mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right). Indeed, see that from \neg\mathfrak{T}_{t}\mathopen{}\mathclose{{}\left(Z}\right), we can plug ${\boldsymbol{\theta}}^{\prime}={\boldsymbol{\mu}}^{*}\wedge\widetilde{\boldsymbol{\theta}}_{t}$ into \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z}\right) to get

giving $\mathfrak{C}_{t}$. To prove (8), we first consider the choice $Z=Z_{1}=A^{*}$. Two cases can be distinguished:

$\forall{\boldsymbol{\theta}}^{\prime}$ s.t. 0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime}}\right)\odot{\bf e}_{A^{*}}\leq\varepsilon{\bf e}_{A^{*}}, we have $A^{*}\subset A$ for any action A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{A^{*}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{A^{*}}^{c}}}\right).

$\exists{\boldsymbol{\theta}}^{\prime}$ s.t. 0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime}}\right)\odot{\bf e}_{A^{*}}\leq\varepsilon{\bf e}_{A^{*}} such that $A^{*}\not\subset A$ for some action A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{A^{*}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{A^{*}}^{c}}}\right).

where (LABEL:rel1lem1) is from (LABEL:rel0lem1), and (LABEL:rel2lem1) is from (LABEL:finfirstlemm1). This rewrites as

so $\mathfrak{R}_{t}({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{A^{*}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{A^{*}}^{c}},A^{*})$ holds. Therefore, we have proved that \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(A^{*}}\right) holds.

1b) For the second case, we have some vector ${\boldsymbol{\theta}}^{\prime}$ such that 0\ltx@label{lastlemma01}\overset{(13)}{\leq}\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime}}\right)\odot{\bf e}_{A^{*}}\ltx@label{lastlemma1}\overset{(14)}{\leq}\varepsilon{\bf e}_{A^{*}}, and some action A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{A^{*}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{A^{*}}^{c}}}\right) such that $A^{*}\not\subset A$. We consider $Z_{2}=A^{*}\cap A$. We first prove that $Z_{2}\neq\emptyset$ by showing that if an action $S^{\prime}$ is such that $S^{\prime}\cap A^{*}\ltx@label{relS^{\prime}lem1}\overset{(15)}{=}\emptyset$, then $A\neq S^{\prime}$:

where (LABEL:relS'lem1bis) is from (LABEL:relS'lem1), (LABEL:relStlem1) is from the definition of $A_{t}$, (LABEL:relCtlem1) is from $\neg\mathfrak{C}_{t}$ and (LABEL:relepsslem1) is from (LABEL:lastlemma1). Now, we again distinguish two cases:

$\forall{\boldsymbol{\theta}}^{\prime\prime}$ s.t. 0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime\prime}}\right)\odot{\bf e}_{Z_{2}}\leq\varepsilon{\bf e}_{Z_{2}}, we have $Z_{2}\subset B$ for any action B\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}^{\prime\prime}\odot{\bf e}_{Z_{2}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{Z_{2}}^{c}}}\right).

$\exists{\boldsymbol{\theta}}^{\prime\prime}$ s.t. 0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime\prime}}\right)\odot{\bf e}_{Z_{2}}\leq\varepsilon{\bf e}_{Z_{2}} such that $Z_{2}\not\subset B$ for some action B\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\theta}}^{\prime\prime}\odot{\bf e}_{Z_{2}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{Z_{2}}^{c}}}\right).

Notice that when 0\leq\mathopen{}\mathclose{{}\left({\boldsymbol{\mu}}^{*}-{\boldsymbol{\theta}}^{\prime\prime}}\right)\odot{\bf e}_{Z_{2}}\ltx@label{rellem1eps}\overset{(20)}{\leq}\varepsilon{\bf e}_{Z_{2}}, then

where we used (LABEL:rellem1eps), (LABEL:lastlemma01) and that $Z_{2}$ is strictly included in $A^{*}$.

where (LABEL:releps21lem1) uses (21) and (LABEL:otherlem1) uses (LABEL:lastlemma1). This rewrites as

so $\mathfrak{R}_{t}({\boldsymbol{\theta}}^{\prime}\odot{\bf e}_{{Z_{2}}}+\widetilde{\boldsymbol{\theta}}_{t}\odot{\bf e}_{{{Z_{2}}}^{c}},{Z_{2}})$ holds, and thus we proved that $\mathfrak{S}_{t}(Z_{2})$ holds.

where the last inequality is obtained in the same way as in inequalities from (LABEL:releps21lem1) to (LABEL:otherlem1).

We could repeat the above argument and each time the size $Z_{i}$ is decreased by at least $1$. Thus, after at most $m^{*}-1$ steps, since m^{*}+(m^{*}-1)+(m^{*}-2)+\dots+1=m^{*}\mathopen{}\mathclose{{}\left(m^{*}+1}\right)/2 is still less than m^{*}\mathopen{}\mathclose{{}\left(m^{*}+1}\right)^{2}/2+1, we could reach the end and find a $Z_{i}\neq\emptyset$ such that \mathfrak{S}_{t}\mathopen{}\mathclose{{}\left(Z_{i}}\right) holds. ∎

Let’s prove that \operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\eta}}+{\boldsymbol{\delta}}\odot{\bf e}_{Z}}\right)\subset\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\eta}}. Consider any action A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\eta}}+{\boldsymbol{\delta}}\odot{\bf e}_{Z}}\right). If $A\notin\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\eta}}$, then there exists $B\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}{\boldsymbol{\eta}}$ such that

Furthermore, since $Z\subset B$ and ${\boldsymbol{\delta}}\geq 0$, we also have

contradicting that A\in\operatorname*{arg\,max}_{A^{\prime}\in\mathcal{A}}{\bf e}_{A^{\prime}}^{\mathsf{\scriptscriptstyle T}}\mathopen{}\mathclose{{}\left({\boldsymbol{\eta}}+{\boldsymbol{\delta}}\odot{\bf e}_{Z}}\right). ∎

Appendix E General CMAB results

Let $t\geq 1$. We define \Lambda_{t}\triangleq\mathopen{}\mathclose{{}\left\|\sum_{i\in A_{t}}{\beta_{i,T}^{1/2}}{N_{i,t-1}^{-1/2}{\bf e}_{i}}}\right\|_{2}. We start by a simple lower bound on $\Lambda_{t}$, holding for any $j\in A_{t}$,

We then use the same reverse amortisation technique than in Wang and Chen .

We now decompose the interval [2,{1}/{\mathopen{}\mathclose{{}\left\|{\bf e}_{A_{t}}}\right\|_{2}}] using a peeling:

This induces a partition of the set of indices:

where for all interger 1\leq k\leq{\mathopen{}\mathclose{{}\left\lceil\log_{2}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\|{\bf e}_{A_{t}}}\right\|_{2}}\right)}\right\rceil},

We can thus upper bound $\Lambda_{t}^{2}$ using this decomposition

So we get, using \mathopen{}\mathclose{{}\left\lceil\log_{2}(m)/2}\right\rceil+1\leq\log_{2}(4\sqrt{m}),

The following Proposition 2 is a standard and general result in CMAB, that was first proved in Chen et al. .

Consider $\Delta_{i,\max}=\Delta_{i,1}\geq\Delta_{i,2}\geq\dots\geq\Delta_{i,K_{i}}=\Delta_{i,\min}$ being all possible values for $\Delta_{t}$ when $i\in A_{t}$. We define a dummy gap $\Delta_{i,0}=\infty$ and let f_{i}\mathopen{}\mathclose{{}\left(\Delta_{i,0}}\right)=0. In (26), we first break the range $(0,f_{i}(\Delta_{t})]$ of the counter $N_{i,t-1}$ into sub intervals:

where $k_{t}$ is the index such that $\Delta_{i,k_{t}}=\Delta_{t}$. This index $k_{t}$ exists by assumption that the subdivision contains all possible values for $\Delta_{t}$ when $i\in A_{t}$. Notice that in (26), we do not explicitly use $k_{t}$, but instead sum over all $k\in[K_{i}]$ and filter against the event \mathopen{}\mathclose{{}\left\{\Delta_{i,k}\geq\Delta_{t}}\right\}, which is equivalent to summing over $k\in[k_{t}].$

Over each event that $N_{i,t-1}$ belongs to the interval $(f_{i}(\Delta_{i,k-1}),f_{i}(\Delta_{i,k})]$, we upper bound the suffered gap $\Delta_{t}$ by $\Delta_{i,k}$.

Then, we further upper bound the summation by adding events that $N_{i,t-1}$ belongs to the remaining intervals $(f_{i}(\Delta_{i,k-1}),f_{i}(\Delta_{i,k})]$ for $k_{t}<k\leq K_{i}$, associating them to a suffered gap $\Delta_{i,k}$. This is equivalent to removing the filtering against the event \mathopen{}\mathclose{{}\left\{\Delta_{i,k}\geq\Delta_{t}}\right\}.

Now, we invert the summation over $t$ and the one over $k$.

We then simply expand the summation, and some terms are cancelled (remember that f_{i}\mathopen{}\mathclose{{}\left(\Delta_{i,0}}\right)=0).

Let $t\geq 1$. The first step is the reverse amortisation technique, that allows us to modify the upper bound on $\Delta_{t}$ in such a way that indices $i$ such that $N_{i,t-1}$ is high enough are removed. Assuming that $\mathfrak{A}_{t}$ holds, we get

Let $i\in[n]$ and $f_{i}(x)=\beta_{i,T}x^{-1/\alpha_{i}}$, $\alpha_{i}\in(0,1]$ and $\beta_{i,T}\geq 0$. Then

We upper bound f_{i}\mathopen{}\mathclose{{}\left(\delta_{t}}\right) by f_{i}\mathopen{}\mathclose{{}\left(\delta_{i,\min}}\right) directly in the event, and then simply count the number of integers in (0,f_{i}\mathopen{}\mathclose{{}\left(\delta_{i,\min}}\right)]. For each such integer $s$, the regret suffered is f_{i}^{-1}\mathopen{}\mathclose{{}\left(s}\right). We then upper bound the sum by an integral (using the fact that $f_{i}^{-1}$ is decreasing), to get the final result.