Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback

Introduction

The multi-armed bandit (MAB) setting is an extensively studied problem in statistics and machine learning (Robbins, 1952; Lattimore and Szepesvári, 2020). The environment consists of a set of arms, each characterized by an unknown reward distribution. An agent interacts with it by playing the arms sequentially in order to identify the arm with the highest expected reward.

Combinatorial bandits (Cesa-Bianchi and Lugosi, 2012; Chen et al., 2013) are a natural extension of the standard framework. The agent chooses actions (or super arms) which are defined by sets of arms satisfying certain constraints. The most studied families of actions stem from matroid theory (Kveton et al., 2014; Perrault et al., 2019). Matroids encompass the batch setting where actions are sets of size $k$ (Jun et al., 2016; Kuroki et al., 2020; Rejwan and Mansour, 2020) and graph-based structures where arms are edges and actions are spanning trees or matching trees. This formulation can model various application-specific structures such as paths taken in routing problems (Talebi et al., 2018). Another example is protein design, where experimental constraints force the agent to evaluate specific sequences of proteins. Instead of inducing a single mutation, a range of localized mutations are performed at once. The main challenge in combinatorial bandits is to cope with the exponential size of the action set. This renders standard approaches for the bandit setting computationally inefficient and also – without further assumptions like linearity – statistically inefficient. To overcome this hurdle, existing approaches assume the reward is linear over the set of arms, and leverage an efficient oracle which solves a linear optimization problem over the combinatorial set of feasible actions. Efficient combinatorial oracles are known for many constraint families such as matroid polytopes, intersections of matroids and path polytopes. Combinatorial bandit strategies vary depending on the received feedback. We consider semi-bandit feedback where the agent observes a reward for each selected arm. Moreover, we assume that the reward for each arm is independent.

We focus on the pure-exploration framework, in which the agent aims at maximizing the information gathered to answer a given query and disregards the accumulated cost. Two major theoretical frameworks exist (Gabillon et al., 2012, 2016; Jun et al., 2016; Kaufmann et al., 2016): the fixed-budget setting and the fixed-confidence setting. In the fixed-budget setting, the goal is to minimize the probability of misidentifying the correct answer given a fixed number of pulls. We consider the fixed-confidence setting where the objective is to minimize the number of pulls necessary to identify the correct answer with a given confidence $1-\delta$. The most studied problems are best-arm identification (BAI) (Karnin et al., 2013; Jamieson et al., 2014; Zaki et al., 2020) and top-$k$ identification (Gabillon et al., 2011; Kalyanakrishnan et al., 2012; Bubeck et al., 2013; Scarlett et al., 2019).

In the spirit of transductive bandits (Fiez et al., 2019) we consider a more general setting where answers are sets of arms. The set of actions and the set of answers can be different. For example, in a routing or transportation network the objective might be to identify a weak link in order to fix it. The agent evaluates a path (action) in the network and gets access to time-stamped data for each link (answer) of a played path. Similarly, in protein design, researchers often generate many mutant proteins in one experiment, but the goal is to identify the best mutant.

We adopt the recently popularized game approach of Degenne et al. (2019). The idea is to consider a sequential zero-sum game between two players. This game approximates the optimal allocation given by the lower bound (Kaufmann et al., 2016). The objective of our work is to design asymptotically optimal algorithms with finite-time guarantees. They should have computationally efficient implementations as long as the offline combinatorial problem can be solved efficiently.

(1) We use the game framework for pure exploration to study combinatorial bandits with semi-bandit feedback. The action and answer sets are arbitrary and the feedback is independent across arms. Despite its increasing popularity, the game framework has not yet been used in combinatorial bandits or in the transductive setting. (2) We develop a pure-exploration CombGame meta-algorithm whose instances are asymptotically optimal algorithms with finite time guarantees. The family of algorithms directly adapts the pure-exploration meta-algorithm of Degenne et al. (2019) to the combinatorial nature of the problem allowing for tractable implementation of the game framework. (3) To overcome the limitation of prior work, we employ the projection-free algorithm over convex polyhedral sets of Garber and Hazan (2013). This approach is the first computationally efficient algorithm which is asymptotically optimal and has competitive empirical performance.

1 Related Work

Combinatorial bandits have been introduced by Cesa-Bianchi and Lugosi (2012) and Chen et al. (2013). The emblematic examples of combinatorial actions are the basis of a matroid (Perrault et al., 2019) and the paths in a graph (Talebi et al., 2018). Semi-bandit feedback is extensively studied (Kveton et al., 2015; Wen et al., 2015). Other works have considered the bandit feedback where the agent observes an aggregated reward (Combes et al., 2015). Generalizing them both, the partial linear monitoring feedback has been studied for cumulative regret minimization (Kirschner et al., 2020) and for pure exploration (Chen et al., 2020). Combinatorial bandits have also been used to denote a different setting where the agent plays arms to identify the best action (Chen et al., 2014, 2016, 2017a; Cao and Krishnamurthy, 2019). Combinatorial bandits have also been generalized to consider submodular reward functions (Hazan and Kale, 2012a; Chen et al., 2017b).

Before the game approach was introduced, Jamieson and Nowak (2014) highlighted three important types of algorithms to solve BAI. They were based on action elimination (Karnin et al., 2013), upper confidence bound (UCB) (Audibert et al., 2010) or lower UCB (Kalyanakrishnan et al., 2012). Bayesian strategies have also been proposed with Thompson sampling like algorithms (Russo, 2016; Kaufmann et al., 2018; Shang et al., 2020). Generalizing the BAI problem to the identification of the $k$ best arms, top-$k$ identification has been studied for an agent playing arms (Gabillon et al., 2011; Kalyanakrishnan et al., 2012; Scarlett et al., 2019) or batches of arms (Jun et al., 2016; Kuroki et al., 2020; Rejwan and Mansour, 2020). The pure-exploration framework encompasses more complex queries such as maximin (Garivier et al., 2016) or minimum threshold (Degenne et al., 2019). Some problems admit multiple correct answers (Degenne and Koolen, 2019).

In the fixed-confidence pure-exploration setting the first known lower bounds on the sample complexity involve a characteristic time whose inverse is a complexity measure (Kaufmann et al., 2016). Those setting-dependent lower bounds have motivated the search for algorithms with matching upper bound, both in finite-time (Simchowitz et al., 2017) and asymptotic regime (Garivier and Kaufmann, 2016). Unfortunately, existing algorithms often require an expensive oracle to compute the optimal allocation weights which are used for sampling, such as Track-and-Stop (Garivier and Kaufmann, 2016) or RAGE (Fiez et al., 2019). Degenne et al. (2019) introduces the game framework which interprets the optimization problem as a zero-sum game between two players. In particular, it proposes a pure-exploration meta-algorithm which uses a cheaper best-response oracle. The game framework has inspired recent algorithms for linear bandits, such as PELEG (Zaki et al., 2020) or LinGame(-C) (Degenne et al., 2020a). PELEG extends the phased-elimination algorithm of Fiez et al. (2019). The idea has also been adapted to cumulative regret in Degenne et al. (2020b).

Preliminaries

In this section we formally define pure exploration for combinatorial bandits with semi-bandit feedback, and prove a lower bound on the sample complexity. We then use the lower bound to determine sampling strategies for our algorithm.

We define the answer set $\mathcal{I}\subset 2^{[d]}$ as a collection of sets of arms, possibly different from the set of actions $\mathcal{A}$. The setting where $\mathcal{I}$ and $\mathcal{A}$ differ is also known as the transductive bandit setting. Given a parameter $\lambda$, the reward of an answer $I\in\mathcal{I}$ is the sum of the rewards of each arm $\langle\lambda,\bm{1}_{I}\rangle\vcentcolon=\sum_{a\in[d]}\lambda_{a}\bm{1}_{(a\in I)}$. The correct answer is given by the function $I^{*}:\mathcal{M}\mapsto\mathcal{I}$ defined as $I^{*}(\lambda)\vcentcolon=\argmax_{I\in\mathcal{I}}\langle\lambda,\bm{1}_{I}\rangle$. For simplicity, we assume that $I^{*}(\lambda)$ is unique for all $\lambda\in\mathcal{M}$. A more careful analysis would allow to relax this assumption to: $I^{*}(\mu)$ is unique for the unknown $\mu$ characterizing the bandit $\nu$. The goal of the agent is to identify the correct answer $I^{*}(\mu)$ by interacting with the environment. BAI is a special case where $\mathcal{I}=\{\{a\}\}_{a\in[d]}$. Best-action identification is obtained for $\mathcal{I}=\mathcal{A}$.

The history $\mathcal{F}_{t}\vcentcolon=\sigma(A_{1},Y_{1,A_{1}},\cdots,A_{t},Y_{t,A_{t}})$ contains all the information available to the agent at step $t+1$. In the fixed-confidence setting a strategy is described by three rules: a sampling rule $(A_{t})_{t\geq 1}$ where $A_{t}\in\mathcal{A}$ is $\mathcal{F}_{t-1}$-measurable, a stopping rule, $\tau_{\delta}$ being the stopping time with respect to the filtration $(\mathcal{F}_{t})_{t\geq 1}$, and a recommendation rule $I_{\tau_{\delta}}$ which is $\mathcal{F}_{\tau_{\delta}}$-measurable.

2 Sample Complexity Lower Bound

Given an answer $I\in\mathcal{I}$, the cell $\Theta_{I}$ is the set of parameters for which the correct answer is $I$, $\Theta_{I}\vcentcolon=\{\lambda\in\mathcal{M}:I^{*}(\lambda)=I\}$. The alternative to $I$ is the set of parameters for which $I$ is not the correct answer, $\Theta_{I}^{\complement}$. It is also equal to the set of parameters for which there exists an answer $J\neq I$ having a higher reward, $\Theta_{I}^{\complement}=\bigcup_{J\in\mathcal{I}\setminus\{I\}}\bar{\Theta}_{J}^{I}$ where $\bar{\Theta}_{J}^{I}\vcentcolon=\{\lambda\in\mathcal{M}:\langle\bm{1}_{J}-\bm{1}_{I},\lambda\rangle\geq 0\}$. The neighbors to I is the set of answers whose cells’ boundaries intersect the boundary of the cell $I$, $N(I)\vcentcolon=\{J\in\mathcal{I}:\partial\Theta_{I}\cap\partial\Theta_{J}\neq\emptyset\}$.

Given any $\delta$-PAC strategy, Theorem 2.1 gives a finite-time and asymptotic lower bound on the sample complexity, see Appendix C for a proof. This result is a technical extension of previous work, see Theorem 1 in Garivier and Kaufmann (2016).

For any $\delta$-PAC strategy and any bandit $\nu$ characterized by $\mu$,

where the complexity $D_{\nu}$ is the inverse of the characteristic time, defined by

Algorithms

After introducing the game approach, we discuss two asymptotically optimal families of algorithms which instantiate our proposed pure-exploration CombGame meta-algorithm, see Algorithm 3.2. The learners used to instantiating it are either on $\Delta_{|\mathcal{A}|}$ or on $\mathcal{S}_{\mathcal{A}}$.

Allowing nature to play distributions over alternatives and using Sion’s minimax theorem, we can invert the order of the players to obtain the dual formulation of the complexity $D_{\nu}$,

where $\mathcal{P}\left(\Theta_{I^{*}(\mu)}^{\complement}\right)$ denotes the set of probability distributions over $\Theta_{I^{*}(\mu)}^{\complement}$.

In our work we focus on a sequential game where the agent, or $A$-player, plays first and nature, or the $\lambda$-player, is second. The $A$-player uses a learner that minimizes the cumulative regret. The $\lambda$-player has access to a best-response oracle that has no regret. This combination ensures a saddle-point property required to derive the finite-time upper bound on the sample complexity. Alternatively the order could be reversed, or they could play simultaneously (Degenne et al., 2019).

2 CombGame Meta-Algorithm

First, we briefly introduce the estimator, stopping and recommendation rules, which define the pure-exploration algorithm. Since $\mu$ (and the best answer $I^{*}(\mu)$) is unknown, we use the maximum likelihood estimator (MLE) $\mu_{t}$ as a plug-in estimator. The recommendation and the stopping rules are frequentist and use the value of $\mu_{t}$. Based on $\mu_{t}$, the sampling rule corresponds to playing an optimistic sequential game. Both the sample complexity and the computational efficiency depend on the learner used to approximate this game.

Given any sampling rule, this pair of rules is sufficient to obtain a $\delta$-PAC strategy, see Theorem 3.1. The proof leverages the concentration inequalities of Kaufmann and Koolen (2018) (Appendix D).

Let $\mathcal{M}$ be bounded. Regardless of the sampling rule, a strategy using the frequentist recommendation/stopping pair with the stopping threshold:

is $\delta$-PAC. In the above, $d_{0}\vcentcolon=\max_{I,J\in\mathcal{I},J\neq I}|(I\setminus J)\cup(J\setminus I)|$, $\mathcal{T}$ and $\mathcal{C}^{g_{G}}$ are the functions defined in Kaufmann and Koolen (2018), $\mathcal{C}^{g_{G}}(x)\approx x+\ln(x)$ and $\mathcal{T}(x)\approx x+4\ln(1+x+\sqrt{2x})$ for $x\geq 5$.

2.1 Sampling rule

Since a learner plays pulling proportion over actions $w_{t}$, we need to convert it into an action choice $A_{t}$. Introduced in Garivier and Kaufmann (2016), C-Tracking and D-Tracking allow to deterministically convert weights into pulls. Due to the non-uniqueness of the optimal allocation of weights, we consider C-Tracking, which ensures $1-|\mathcal{A}|\leq N_{t,A}-\sum_{s=1}^{t}w_{t,A}\leq 1$, see Appendix G.5.1. We obtain a sparse tracking procedure by limiting the choice of $A_{t}$ to the incremental support $B_{t}\vcentcolon=\text{supp}\left(\sum_{s=1}^{t}w_{s}\right)$: $A_{t}\in\argmin_{A\in B_{t}}\frac{N_{t-1,A}}{\sum_{s=1}^{t}w_{s,A}}$. Alternatives include D-Tracking or the rounding procedure in Fiez et al. (2019). For a non-deterministic algorithm we can directly sample the next action, $A_{t}\sim w_{t}$.

3 Learners on the Simplex

Since we are playing pulling proportion over actions, the immediate approach is to consider Hedge-type algorithms. They constitute a family of learners on the probability simplex $\Delta_{|\mathcal{A}|}$. As examples from this family, we will use Hedge (Cesa-Bianchi et al., 2005) and the adaptive version AdaHedge (Rooij et al., 2014). An algorithm is said to be anytime if it is independent of the horizon $T$. Those learners require computations at the actions level to obtain a reward vector $U_{t}$: for all $A\in\mathcal{A}$, $U_{t,A}\vcentcolon=\langle\bm{1}_{A},r_{t}\rangle$. For both learners the update of $w_{t}$ is: for all $A\in\mathcal{A}$, $w_{t,A}=\frac{w_{n_{0},A}\exp\left(-\eta_{t}L_{t-1,A}\right)}{\sum_{A^{\prime}\in\mathcal{A}}w_{n_{0},A^{\prime}}\exp\left(-\eta_{t}L_{t-1,A^{\prime}}\right)}$ where $L_{t-1,A}=-\sum_{s=1}^{t-1}U_{s,A}$ is the cumulative loss, $\eta_{t}$ is the learning rate and $w_{n_{0}}=\frac{1}{|\mathcal{A}|}\bm{1}$ is the sampling parameter for a full initialization. In Hedge, $\eta_{t}$ is a constant depending on $T$. While in AdaHedge, $\eta_{t}$ is decreasing and defined as a function of a cumulative mixability gap. As shown in Lemmas F.1 and F.3, both Hedge and AdaHedge have optimal cumulative regret, $O\left(\ln(t)\sqrt{t}\right)$. The additional $\ln(t)$-factor originates from the unbounded losses.

4 Learners on the Transformed Simplex

Sample Complexity Upper Bound

In this section we present and sketch the proof of the finite-time upper bound on the sample complexity of our instantiated CombGame meta-algorithm.

Given a learner with sub-linear cumulative regret $R_{t}^{A}=o(t)$, Theorem 4.1 shows that the instances of Algorithm 3.2, the CombGame meta-algorithm, satisfy a finite-time upper bound on the sample complexity. The upper bound involves the complexity $D_{\nu}$. The leading constant is optimal in the asymptotic regime $\delta\rightarrow 0$. Those results and their proofs are inspired from Theorem 2 in Degenne et al. (2019). It also bares similarity with Theorem 2 of Degenne et al. (2020a).

Let $\mathcal{M}$ be bounded. The sample complexity of the instantiated CombGame meta-algorithm on bandit $\mu\in\mathcal{M}$ satisfies:

where $c>0$ is the parameter of the exploration bonus $f(t)$ when taking $b=1$. The reminder terms are: the approximation error $h(t)=O\left(\sqrt{t\ln(t)}\right)$, the learner’s cumulative regret $R_{t}^{A}$ and a constant $C_{\nu}$ depending on the distribution.

Moreover, the instantiated CombGame meta-algorithm is an asymptotically optimal algorithm.

Even though the upper bound in Theorem 4.1 holds for finite-time, it is an asymptotic result by nature. The additive term, which is independent of $\delta$, can’t be neglected in finite-time, and is likely to be loose due to the analysis. Therefore, we won’t compare the upper bounds of different learners.

Detailed in Appendix G, the proof of Theorem 4.1 uses Lemma 4.2, which is an adaptation of Lemma 1 in Degenne et al. (2019) with the same exploration bonus.

The challenging part of the proof is the characterization of $T_{0}(\delta)$ with an equation involving the complexity $D_{\nu}$, similarly to Appendix D in Degenne et al. (2019). We need to exhibit an upper bound $T_{0}(\delta)$ such that for $t\geq T_{0}(\delta)$, if $\mathcal{E}_{t}$ holds then the algorithm has already stopped, $\tau_{\delta}\leq t$. In contrast to Degenne et al. (2019), the particularity of our proof is to consider computations on $\mathcal{S}_{\mathcal{A}}$ and not on the simplex. Even though the idea of the proof is identical, we need different technical arguments such as the tracking and concentration results in Appendices G.5.1 and G.5.2. For sake of simplicity we suppose that $I_{t}=I^{*}(\mu)$ in the following informal exposition. This fails only for $o(t)$ rounds as shown in Appendix G.3.1. Using C-Tacking, we obtain that as long as the stopping criterion is not satisfied, under the concentration event $\mathcal{E}_{t-1}$,

Then, we leverage the approximate saddle-point property of the CombGame meta-algorithm. This property is obtained by combining the optimism, the no-regret $\lambda$-player and the cumulative regret of the $A$-player, see Appendix G.2:

Under the concentration event $\mathcal{E}_{t-1}$, the optimism implies $r_{s}\geq d_{\text{KL}}(\mu,\lambda_{s})$ for $s\leq t-1$. Combining the dual formulation of $D_{\nu}$ and the average of diracs, $\frac{1}{t-1}\sum_{s=1}^{t-1}\delta_{\lambda_{s}}\in\mathcal{P}\left(\Theta_{I^{*}(\mu)}^{\complement}\right)$, yields:

Experiments

The goal of our experiments is to validate the sample effectiveness and computational efficiency of CombGame’s instances for the finite-time regime, $\delta=0.1$. We will compare the sample complexity of our learners, the uniform sampling and GCB-PE (Chen et al., 2020). To our knowledge, GCB-PE is the only algorithm which can be used to solve the pure-exploration problem for combinatorial bandits with semi-bandit feedback. Other works consider bandit feedback, cumulative regret or MAB. In addition, we demonstrate that learners on $\mathcal{S}_{\mathcal{A}}$ have an exponentially smaller computational cost compared to the learners on $\Delta_{|\mathcal{A}|}$. As an illustrative example, we use the best-arm identification with batch size $k$ for a Gaussian bandit, $\nu=\mathcal{N}(\mu,\sigma^{2}I_{d})$. In BAI the informative actions are the ones containing the best arm $I^{*}$, $\mathcal{A}^{*}\vcentcolon=\{A\in\mathcal{A}:I^{*}\subset A\}$. They provide direct feedback on the best arm, while other actions are sampled to answer indirectly to our query. The batch setting is used in real-world applications and admits an efficient oracle, the greedy algorithm. The number of actions is $|\mathcal{A}|=\binom{d}{k}$ and the ratio of informative actions is $\frac{|\mathcal{A}^{*}|}{|\mathcal{A}|}=\frac{k}{d}$. By increasing the dimension $d$, we observe the effect of an exponential increase of $|\mathcal{A}|$ while the ratio of informative actions $\frac{|\mathcal{A}^{*}|}{|\mathcal{A}|}$ is decreasing harmonically. In Appendix I.1, additional experiments include BAI by playing paths in a graph (Figures 4 and 5).

As described in Appendix I, the empirical results of CombGame’s instances are similar in behavior if we adopt D-Tracking instead of C-Tracking, one learner $\mathcal{A}^{A}$ instead of $|\mathcal{I}|$ learners, stylized stopping threshold $\beta(t,\delta)=\ln\left(\frac{1+\ln(t)}{\delta}\right)$ and exploration bonus $f(t)=\ln(t)$ instead of the ones licensed by theory. Doubling trick is used for Hedge and LLOO. The results over $750$ runs are summarized in Figure 1 by plotting the mean of the empirical stopping time $\tau_{\delta}$ and the average running time to compute the next action. The error bars correspond to the first and third quartiles.

In Figure 1(a), we observe that the sample complexity of Hedge, AdaHedge and LLOO is similar and increases proportionally to the number of actions. They perform better than uniform sampling, which still works reasonably well thanks to the high number of informative actions when $k\ll d$, $|\mathcal{A}^{*}|=\binom{d-1}{k-1}$. OFW’s sample complexity is significantly higher than previous algorithms. This highlights the importance of cumulative regret’s guarantees in order to have competitive empirical performance. In Figure 3(c) in Appendix I.1.1, we empirically show that on this example, the sample complexity of GCB-PE is about an order of magnitude higher compared to the other sampling rules: the mean over $750$ runs of $\tau_{\delta}$ is $\{19914,85314,166179,316552\}$ for $d\in\{5,10,15,20\}$.

Despite the fact that there is no clear-cut ranking between all algorithms in Figure 1(a), Figure 1(b) highlights that, with a greatly lower computational cost, we obtain similar sample complexity.

Conclusion

In this paper we designed the first computationally efficient and asymptotically optimal algorithm to solve best-arm identification with combinatorial actions and semi-bandit feedback.

We highlight two directions to improve on our work. First, due to the learner’s central role in the empirical performance, a more thorough benchmark of the existing learners should be made. An interesting choice is SFTPL from Hazan and Minasyan (2020) which meets our requirements. Second, the best-reponse oracle used by the $\lambda$-player is not computationally efficient for combinatorial answer sets, as in best-action identification, since the computations per round scale with $|N(I_{t})|$ (which is usually lower than $|\mathcal{I}|$). In the spirit of Fiez et al. (2019); Zaki et al. (2020), this flaw could be mitigated by considering a phase-based algorithm discarding suboptimal answers.

Finally, as already noted in Degenne et al. (2020a), we observed that the stopping threshold is the major bottleneck in terms of finite-time empirical sample complexity. Using thresholds guarantying $\delta$-PAC algorithms is too conservative since empirical error rates are orders of magnitude below the theoretical confidence error $\delta$.

This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation program grant agreement No 815943. It was also supported by the Swiss National Science Foundation through the NCCR Catalysis.

References

Appendix A Notation

Appendix B Outline

The proof of Theorem 2.1 is detailed in Appendix C.

The proof of Theorem 3.1 is detailed in Appendix D.

The results concerning the optimistic reward are detailed in Appendix E: bounds on $\|r_{t}\|_{\infty}$ and explicit formulas for Gaussian bandit.

The upper bounds on the learners’ cumulative regret are proven in Appendix F.

The full proof of Theorem 4.1 is detailed in Appendix G.

In Appendix H, we sketch why the boundedness assumption is immaterial for Gaussian bandit.

The implementation details for the experiments are presented in Appendix I. Additional empirical results are also displayed.

Appendix C Proof of Theorem 2.1

Let kl$(x,y)$ be the KL divergence of a Bernoulli distribution. Let $\nu$ and $\nu^{\prime}$ be two bandit models such that for all $a\in[d]$ the distributions $\nu_{a}$ and $\nu_{a}^{\prime}$ are mutually absolutely continuous. The associated density are denoted $f_{\nu_{a}}$ and $f_{\nu_{a}^{\prime}}$. Given the history up to time $t$, the log-likelihood ratio of the independent observations is:

The proof of Theorem 2.1 is an adaptation of the proof of Theorem 1 in Garivier and Kaufmann (2016) to our setting. We use Lemma 19 of Kaufmann et al. (2016), which shows a lower bound on the expectation of the log-likelihood ratio. Combined with Wald’s lemma, we obtain the transportation inequality of Lemma C.1, which replaces the Lemma 1 in Kaufmann et al. (2016).

(Lemma 19 in Kaufmann et al. (2016)) Let $\tau$ be the almost-surely finite stopping time with respect to the filtration $(\mathcal{F}_{t})_{t\geq 1}$. For every event $\mathcal{E}\in\mathcal{F}_{\tau}$,

Let $\nu$ and $\nu^{\prime}$ be two bandit models with independent arms. For any almost-surely finite stopping time $\tau$ with respect to the filtration $(\mathcal{F}_{t})_{t\geq 1}$,

For any $\delta$-PAC strategy and any bandit $\nu$,

where the complexity $D_{\nu}$, inverse of a characteristic time, is defined by

This concludes the proof of the finite-time lower bound. Taking the limit $\delta\rightarrow 0$ in the previous lower bound yields directly the asymptotic lower bound.

Appendix D Proof of Theorem 3.1

The proof of Theorem 3.1 uses the deviation inequalities of Kaufmann and Koolen (2018), see Appendix D.1. The idea of the proof is similar to the proof of Proposition 21 in Kaufmann and Koolen (2018), as well as Theorem 2 in Shang et al. (2020).

Let $\mathcal{M}$ be bounded. Regardless of the sampling rule, a strategy using the frequentist recommendation/stopping pair with the stopping threshold:

is $\delta$-PAC. In the above, $d_{0}\vcentcolon=\max_{I,J\in\mathcal{I},J\neq I}|(I\setminus J)\cup(J\setminus I)|$, $\mathcal{T}$ and $\mathcal{C}^{g_{G}}$ are the functions defined in Kaufmann and Koolen (2018), $\mathcal{C}^{g_{G}}(x)\approx x+\ln(x)$ and $\mathcal{T}(x)\approx x+4\ln(1+x+\sqrt{2x})$ for $x\geq 5$.

The last inequality is obtained by considering a parameter $\lambda$ defined as: $\lambda_{a}=\mu_{a}$ when $a\in I^{*}(\mu)\triangle I$ and $\lambda_{a}=\mu_{t,a}$ else. Since $\mu\in\bar{\Theta}_{I^{*}(\mu)}^{I}$, we have that $\langle\bm{1}_{I^{*}(\mu)}-\bm{1}_{I},\lambda_{a}\rangle=\langle\bm{1}_{I^{*}(\mu)}-\bm{1}_{I},\mu_{a}\rangle\geq 0$. Therefore $\lambda\in\bar{\Theta}_{I^{*}(\mu)}^{I}$, hence it is a valid parameter. The upper bound rewrites as:

The last inequality is due to the fact that $h_{t}(x)=x\ln\left(c_{0}+\ln\left(\frac{t}{x}\right)\right)$ is increasing on $]0,d]$ when $t\gg d$. The higher $t$ is, the longer $h_{t}$ is increasing. Numerically, $h_{1}$ is increasing till $424$. Let $\mathcal{T}$ and $\mathcal{C}^{g_{G}}$ the functions defined in Kaufmann and Koolen (2018). Since $x\mapsto x\mathcal{T}\left(\frac{c}{x}\right)$ and $x\mapsto x\mathcal{C}^{g_{G}}\left(\frac{c}{x}\right)$ are increasing (Appendix D.1), we obtain:

Combining those inequalities with $c=1$ for (a) and $c=4$ for (b), we obtain that:

Let $\beta(t,\delta)$ be the stopping threshold defined as:

Therefore, we conclude that a strategy using the frequentist recommendation/stopping pair is $\delta$-PAC.

The deviation inequality for sub-Gaussian bandit is rewritten in Appendix D.1.1, while the deviation inequality for Gaussian bandit is presented in Appendix D.1.2.

Theorem 14 in Kaufmann and Koolen (2018) holds for sub-Gaussian bandits.

Let $\delta>0$, $\nu$ be independent one-parameter exponential families with mean $\mu$ and $S\subset[d]$. Then we have,

D.1.2 Gaussian Bandit

Corollary 10 in Kaufmann and Koolen (2018) holds for Gaussian bandits. Lemma D.2 gathers some properties of $\mathcal{C}^{g_{G}}$.

Let $\delta>0$, $\nu$ be a family of independent Gaussian with mean $\mu$ and $S\subset[d]$. Then we have,

The $g_{G}$ is positive on $]1/2,1[$ and satisfies $g_{G}(y)\rightarrow_{y\rightarrow\{1/2,1\}}+\infty$. The function $x\mapsto xC^{g_{G}}\left(\frac{c}{x}\right)$ is increasing.

Since $\zeta(1)=\lim_{n\rightarrow\infty}\sum_{s=1}^{n}\frac{1}{s}=+\infty$ and $g_{G}(y)\sim_{1/2}\ln(\zeta(2y))$, we have $g_{G}(y)\rightarrow_{y\rightarrow 1/2}+\infty$. Since $\zeta(2)=\frac{\pi^{2}}{6}$ and $g_{G}(y)\sim_{1}-\frac{1}{2}\ln(1-y)$, we have $g_{G}(y)\rightarrow_{y\rightarrow 1}+\infty$.

Let $y\in]1/2,1[$ and $h(y)=2y-2y\ln(4y)-\frac{1}{2}\ln(1-y)$. We have $h^{\prime}(y)=\frac{1}{2}\frac{1}{1-y}-2\ln(4y)$, hence $h^{\prime}(y)\geq 0$ if and only if $1\geq 4(1-y)\ln(4y)$. Numerically, this condition is always true, hence $h$ is increasing. Since $h(y)\geq h(1/2)=1$, we obtain $g_{G}(y)\geq 1+\ln(\zeta(2y))$. Using that $\ln(\zeta(2))=\ln\frac{\pi^{2}}{6}>0$ and $x\mapsto\zeta(x)$ decreasing on $]1/2,1]$, we obtain that $\ln(\zeta(2y))\geq\ln(\zeta(2))$. Therefore we can conclude that $\forall y\in[1/2,1[,g_{G}(y)\geq 1\geq 0$.

Since $xC^{g_{G}}\left(\frac{c}{x}\right)=\min_{y\in]1/2,1]}\frac{xg_{G}(y)+c}{y}$ and $g_{G}$ is positive on $]1/2,1[$, we obtain directly that $x\mapsto xC^{g_{G}}\left(\frac{c}{x}\right)$ is increasing.

Appendix E Optimistic Reward

In Appendix E.1, we prove an upper and lower bound on the optimistic reward (Lemma E.1). The properties of $r_{t}$ for Gaussian bandit are studied in Appendix E.2

Due to the boundedness assumption, Lemma E.1 below shows that the optimistic reward $r_{t}$ is almost bounded. When an arm $a$ is sampled less than a logarithmic number of times, $r_{t,a}$ becomes large enough to stir the sampling towards actions containing it.

Let $\mathcal{M}$ bounded. Under the event $\{\mu\in\mathcal{C}_{t}\}$, we have:

The upper bound is a consequence of the boundedness assumption, $D_{\mathcal{M}}\vcentcolon=\sup_{(\phi,\lambda)\in\mathcal{M}^{2}}\|d_{\text{KL}}(\phi,\lambda)\|_{1}$. Since $\mu$ has a unique correct answer, the lower bound stems from the Chernoff information lower bound $\epsilon_{\nu}$ which holds for both (a) and (b): there exists $\epsilon_{\nu}>0$ such that,

where ch$(x,y)\vcentcolon=\inf_{u\in\Theta}\left(d_{\text{KL}}(u,x)+d_{\text{KL}}(u,y)\right)$.

Before proving Lemma E.1, let’s first prove that $\epsilon_{\nu}$ exists. For (a) sub-Gaussian, we have $d_{\text{KL}}(u,x)\geq\frac{(u-x)^{2}}{2\sigma_{a}^{2}}$, hence the chernoff information of the setting (a) is greater than the one for setting (b). For (b) Gaussian, we have: $\text{ch}(x,y)=\frac{1}{2\sigma_{a}^{2}}\inf_{u\in\Theta}((u-x)^{2}+(u-y)^{2})=\frac{(x-y)^{2}}{8\sigma_{a}^{2}}$.

Let $\mu\in\mathcal{M}$ and $\lambda\in\Theta_{I^{*}(\mu)}^{\complement}$. Since $\mu\in\Theta_{I^{*}(\mu)}$, which is an open set, the euclidean distance to $\Theta_{I^{*}(\mu)}^{\complement}$ is strictly positive: there exists $a\in[d]$ such that $|\lambda_{a}-\mu_{a}|\geq\epsilon>0$. Since $\text{ch}(x,y)\geq\frac{(x-y)^{2}}{8\sigma_{a}^{2}}$, we can conclude for both (a) and (b) that there exists $\epsilon_{\nu}>0$ as defined above.

Since $\mathcal{M}$ is bounded, $D_{\mathcal{M}}=\sup_{(\phi,\lambda)\in\mathcal{M}^{2}}\|d_{\text{KL}}(\phi,\lambda)\|_{1}$ and $\|\cdot\|_{\infty}\leq\|\cdot\|_{1}$, we obtain the desired upper bound.

Due to concentration events, with high probability we have $\mu\in\mathcal{C}_{t}=\bigtimes_{a\in[d]}[\alpha_{t,a},\beta_{t,a}]$. Assume $\{\mu\in\mathcal{C}_{t}\}$ holds. Combining the definition of $\phi_{t,a}$ and $\lambda_{t}\in\partial\Theta_{I_{t}}$, we obtain: $d_{\text{KL}}(\phi_{t,a},\lambda_{t,a})\geq d_{\text{KL}}(\mu_{a},\lambda_{t,a})\geq\min_{\lambda\in\partial\Theta_{I_{t}}}d_{\text{KL}}(\mu_{a},\lambda_{a})\geq\min_{I\in\mathcal{I},\lambda\in\partial\Theta_{I}}d_{\text{KL}}(\mu_{a},\lambda_{a})$. The function $y\mapsto d_{KL}(x,y)$ is not convex in general and is minimized in $x=y$. Hence, the geometry of the cells yields:

E.2 Gaussian Bandit

Let $\nu$ be independent Gaussian and $\lambda\in\mathcal{M}$. Then, for all $a\in[d]$,

where $\phi_{t,a}=\argmax_{\phi\in\{\alpha_{t,a},\beta_{t,a}\}}\frac{(\phi-\lambda_{a})^{2}}{2\sigma_{a}^{2}}$.

Let $\lambda\in\mathcal{M}$. Let $\phi_{t,a}=\argmax_{\phi\in\{\alpha_{t,a},\beta_{t,a}\}}\frac{(\phi-\lambda_{a})^{2}}{2\sigma_{a}^{2}}$ for all $a\in[d]$. Assume $\lambda_{a}\geq\mu_{t-1,a}$. Since $\lambda_{a}\geq\mu_{t-1,a}\geq\alpha_{t,a}$ and $\mu_{t-1,a}\leq\beta_{t,a}$, we have $(\alpha_{t,a}-\lambda_{a})^{2}\geq(\beta_{t,a}-\lambda_{a})^{2}$. Therefore $\phi_{t,a}=\alpha_{t,a}$. Assume $\lambda_{a}<\mu_{t-1,a}$. Since $\lambda_{a}<\mu_{t-1,a}\leq\beta_{t,a}$ and $\mu_{t-1,a}\geq\alpha_{t,a}$, we have $(\alpha_{t,a}-\lambda_{a})^{2}\leq(\beta_{t,a}-\lambda_{a})^{2}$. This concludes the first statement.

Appendix F Learner’s Cumulative Regret

In the Appendix F, we show upper bounds on the cumulative regret for the different learners: Hedge in Lemma F.1, AdaHedge in Lemma F.3, OFW in Lemma F.5 and LLOO in Lemma F.7.

The extended optimistic reward is defined as: $U_{t,A}\vcentcolon=\langle\bm{1}_{A},r_{t}\rangle$ for all $A\in\mathcal{A}$. The cumulative regret rewrites as:

Using Corollary 3 in Cesa-Bianchi et al. (2005), we obtain that Hedge has optimal cumulative regret (Lemma F.1).

where $L_{t}^{*}=\min_{A\in\mathcal{A}}\sum_{s=1}^{t}l_{s,A}$.

For scaled losses in $$, Corollary 3 in Cesa-Bianchi et al. (2005) yields that Hedge’s cumulative regret$R_{t}^{\prime}$satisfies:$R_{t}^{\prime}\leq 4\sqrt{\frac{L_{t}^{*}(\sigma t-L_{t}^{*})}{t}\ln(|\mathcal{A}|)}+39\sigma\max\{1,\ln(|\mathcal{A}|)\}$where$\sigma$is the range of observed loss. By definition of$l_{t}$, we have$\sigma=1$. Factorizing the maximum of the scale of the loss$\max_{s\leq t}b_{s}$, we obtain the upper bound on$R_{t}^{Hedge}$. In the worst case this algorithm has a regret of order$O(\sqrt{t})$, but it performs much better when the loss of the best expert$L_{t}^{*}$is close to either or$t$. Combined with$\max_{s\leq t}b_{s}=O\left(\ln(t)\right)$, this concludes the proof.

Using the results of Rooij et al. (2014), we obtain that AdaHedge has optimal cumulative regret (Lemma F.3).

For scaled losses in $$, Theorem 6 in Rooij et al. (2014) yields that AdaHedge’s cumulative regret$R_{t}^{\prime}$satisfies:$R_{t}^{\prime}\leq 2\sqrt{V_{t}\ln(|\mathcal{A}|)}+\frac{4}{3}\ln(|\mathcal{A}|)+2$where$V_{t}=\sum_{s\in[t]}v_{s}$with$v_{s}=\sum_{A\in\mathcal{A}}w_{s,A}(l_{s,A}-\langle w_{s},l_{s}\rangle)^{2}$. We have$v_{s}\leq\|l_{s}-\langle w_{s},l_{s}\rangle\|_{\infty}^{2}=\frac{\|\langle w_{s},U_{s}\rangle-U_{s}\|_{\infty}^{2}}{b_{s}^{2}}\leq\frac{b_{s}^{2}}{\sigma^{2}}$where$\sigma=\max_{s\leq t}b_{s}$. The upper bound on$R_{t}^{\prime}$rewrites as:$R_{t}^{\prime}\leq\frac{1}{\sigma}\sqrt{\sum_{s\leq t}b_{s}^{2}\ln(|\mathcal{A}|)}+\frac{4}{3}\ln(|\mathcal{A}|)+2$. Theorem 16 in Rooij et al. (2014) yields that$R_{t}^{A}=\sigma R_{t}^{\prime}$. Therefore, we conclude that:

Combined with $\max_{s\leq t}b_{s}=O\left(\ln(t)\right)$, this concludes the proof.

F.2 Learner on the Transformed Simplex

Slightly adapting the results of Hazan and Kale (2012b), we obtain that OFW has an upper bound on the cumulative regret in $O\left(\ln(t)^{2}t^{3/4}\right)$ (Lemma F.5). This is in general suboptimal for the online linear optimization setting.

OFW described in Section 3.4 is exactly the algorithm used in the proof of Theorem 4.4 in Hazan and Kale (2012b), which is a result for adversarial cost functions. In their notations, the Lipschitz constant $L$ satisfies: $L=\|r_{t}\|_{2}$. In order to conserve the anytime property of OFW, we use a different $\sigma_{t}$ which is independent of $L$, $\sigma_{t}=\frac{1}{\text{diam}(\mathcal{S}_{\mathcal{A}})}t^{-1/4}$. The decrease in $t^{-1/4}$ is optimal. This modification doesn’t change the idea of the proof and impact only the final bound by a multiplicative factor, $\max_{s\leq t}\|r_{s}\|_{2}$. A close examination of its proof shows that Theorem 3.1 in Hazan and Kale (2012b) still holds for time dependent Lipschitz constant $L_{t}$. Therefore, we follow the proof of Theorem 4.4 and apply Theorem 3.1 for $\hat{f}_{t}(x)=\langle l_{t},x\rangle+\frac{1}{\text{diam}(\mathcal{S}_{\mathcal{A}})}t^{-1/4}\|x-x_{1}\|_{2}^{2}$. The exact same steps and using that $L_{s}\leq\max_{s\leq t}\|r_{s}\|_{2}$ for all $s\in[t]$ yield that:

Combined with $\max_{s\leq t}\|r_{s}\|_{2}=O(\ln(t))$, this concludes the proof.

Using Theorem 3 in Garber and Hazan (2013), we obtain that OFW has optimal cumulative regret (Lemma F.7).

Let $T$ be the horizon and $\mu_{\mathcal{A}}$, defined in Garber and Hazan (2013). With $\gamma_{\mathcal{A}}=(3d\mu_{A}^{2})^{-1}$, $\eta_{\mathcal{A},T}=\frac{\text{diam}(\mathcal{S}_{\mathcal{A}})}{18\mu_{\mathcal{A}}\sqrt{dT}\max_{t\leq T}\|r_{t}\|_{2}}$ and $M_{\mathcal{A},T}=\min\left\{\mu_{\mathcal{A}}^{2}\frac{d}{\sqrt{T}}\left(1+\frac{1}{18d\mu_{\mathcal{A}}^{2}}\right),1\right\}$, LLOO satisfies:

Let $T$ be the horizon and $\mu_{\mathcal{A}}$ as defined in Garber and Hazan (2013) (see Appendix I.1 for an explicit formula), which depends on $\mathcal{S}_{\mathcal{A}}$. For a non strongly convex function $\sigma=0$, LLOO described in Section 3.4 is exactly the combination of Algorithm 5 and Algorithm 4 in Garber and Hazan (2013). The re-organization highlights the similarities with OFW. As parameters for the algorithm, we use the theoretically licensed: $\gamma_{\mathcal{A}}=(3d\mu_{A}^{2})^{-1}$, $\eta_{\mathcal{A},T}=\frac{\text{diam}(\mathcal{S}_{\mathcal{A}})}{18\mu_{\mathcal{A}}\sqrt{dT}\max_{t\leq T}\|r_{t}\|_{2}}$ and $M_{\mathcal{A},T}=\min\left\{\mu_{\mathcal{A}}^{2}\frac{d}{\sqrt{T}}\left(1+\frac{1}{18d\mu_{\mathcal{A}}^{2}}\right),1\right\}$. Theorem 3 in Garber and Hazan (2013) yields that: $R_{t}^{LLOO}=O\left(\text{diam}(\mathcal{S}_{\mathcal{A}})\mu_{\mathcal{A}}\sqrt{dt}\max_{s\leq t}\|r_{s}\|_{2}\right)=O\left(\ln(t)\sqrt{t}\right)$. Combined with $\max_{s\leq t}\|r_{s}\|_{2}=O(\ln(t))$, this concludes the proof.

Appendix G Proof of Theorem 4.1

In Appendix G.1, we prove the preliminary Lemma 4.2. The saddle-point property of the algorithm $\mathcal{A}_{I}^{A}$ associated to $I$ is proven in Appendix G.2. In Appendix G.3, we lower and upper bound the number of times when the candidate answer is correct. Combining them yields the definition of $T_{0}(\delta)$ and concludes the proof of Theorem 4.1. Technical arguments with respect to C-Tracking and concentration events are proven in Appendix G.5.

Let $t_{b}\vcentcolon=t^{1/(1+b)}$, with $b>0$, and $(\mathcal{E}_{t})_{t\geq 1}$ be a sequence of concentrations events for the exploration bonus $f$ with parameters $b$ and $c>0$: for all $t\geq 1$,

where $f(t)=\overline{W}((1+c)(1+b)\ln(t))$ with $c>0$, $b>0$ and $\overline{W}(x)\approx x+\ln(x)$. More precisely, for $x\geq 1$, $\overline{W}(x)=-W_{-1}(-e^{-x})$ where $W_{-1}$ denotes the negative branch of the Lambert $W$ function. This sequence is theoretically validated due to Lemmas 5 and 6 in Degenne et al. (2019).

Let $(Y_{s,a})_{s\in[t]}$ be i.i.d random variables in a canonical one-parameter exponential family with mean $\mu_{a}$. Then, for $\alpha>0$,

For independent $\nu$ and $(\mathcal{E}_{t})_{t\geq 1}$ defined in Equation 1, we obtain:

Let $(\mathcal{E}_{t})_{t\geq 1}$ be a sequence of concentrations events for the exploration bonus $f$ with parameters $c>0$ and $b>0$: for all $t\geq 1$,

G.2 Saddle-point Property

Let $T_{t,I}\vcentcolon=\{s\in[t]:I_{s}=I\}$ for all $I\in\mathcal{I}$. Let $I\in\mathcal{I}$. Similarly to Degenne et al. (2019), we prove the saddle-point property of the algorithm $\mathcal{A}_{I}^{A}$ associated to $I$.

Let $C_{s,a}=r_{s,a}-d_{\text{KL}}(\mu_{s-1,a},\lambda_{s,a})$ and $C_{s}=(C_{s,a})_{a\in[d]}$ be the slack between the optimistic reward and the reward for the parameter $\mu_{s-1}$. We have:

G.3 Candidate Answer

In Appendix G.3.1, we show that $I_{t}$ is not the correct answer for only $o(t)$ rounds. This provides a lower bound on the number of times the candidate answer is correct. An upper bound on the number of times the candidate answer is correct is proved in Appendix G.3.2.

Let $I^{*}=I^{*}(\mu)$, $t<\tau_{\delta}$, $T_{t,I}\vcentcolon=\{s\in[t]:I_{s}=I\}$ for all $I\in\mathcal{I}$ and $t_{b}\vcentcolon=t^{1/(1+b)}$. The number of time the recommended answer is not correct is $o(t)$ as a consequence of the following fact: when $I_{t}\neq I^{*}$ a quantity, denoted $\epsilon_{t}$, is increasing linearly while being $O(\sqrt{t})$ due to concentration arguments. The proof of this fact uses a consequence of the chernoff information lower bound $\epsilon_{\nu}$ (Appendix E.1): the Lemma 18 of Degenne et al. (2019).

Since $R^{A}_{|T_{t,I}|}\leq R^{A}_{t}$, we have $\sum_{I\in\mathcal{I}\setminus\{I^{*}\}}R^{A}_{|T_{t,I}|}\leq(|\mathcal{I}|-1)R^{A}_{t}$. For a concave cumulative regret such as $t\mapsto\sqrt{t}$, we would have $\sum_{I\in\mathcal{I}\setminus\{I^{*}\}}R^{A}_{|T_{t,I}|}\leq(|\mathcal{I}|-1)R^{A}_{\frac{t-|T_{t,I^{*}}|}{|\mathcal{I}|-1}}$. Since $\sum_{I\in\mathcal{I}\setminus\{I^{*}\}}(|T_{t,I}|-|T_{t_{b},I}|)=t-t_{b}-|T_{t,I^{*}}|$, summing these inequalities yields:

Combining these inequalities, we obtain a lower bound on $|T_{t,I^{*}}|$: for $t<\tau_{\delta}$, under $\mathcal{E}_{t}$,

G.3.2 Correct Answer

Combining C-Tracking, Lemma G.4 and $\langle\bm{1},d_{\text{KL}}(\mu,\lambda)\rangle=\|d_{\text{KL}}(\mu,\lambda)\|_{1}\leq D_{\mathcal{M}}$ ($\mathcal{M}$ bounded), we obtain:

Lemma 14 in Degenne et al. (2019) (Appendix Lemma) yields:

Combining the saddle-point property of $\mathcal{A}^{A}_{I^{*}}$ and $R_{t^{\prime}-1}^{A}\leq R_{t}^{A}$, we obtain:

Combining $\frac{1}{|T_{t^{\prime}-1,I^{*}}|-|T_{t_{b},I^{*}}|}\sum_{t_{b}\leq s\leq t^{\prime}-1,I_{s}=I^{*}}\delta_{\lambda_{s}}\in\mathcal{P}\left(\Theta_{I^{*}}^{\complement}\right)$ (average of diracs in $(\lambda_{s})_{s}$), the dual formulation of $D_{\nu}$ and the fact that $|T_{t^{\prime}-1,I^{*}}|\geq|T_{t,I^{*}}|-1$, we obtain that:

Combining these inequalities, we obtain an upper bound on $|T_{t,I^{*}}|$: for $t<\tau_{\delta}$, under $\mathcal{E}_{t}$,

G.4 Stopping Time Upper Bound

Combining the upper and lower bounds on $|T_{t,I^{*}}|$ (Appendices G.3.1 and G.3.2) yields: for $t<\tau_{\delta}$, under $\mathcal{E}_{t}$,

where $C_{\nu}\vcentcolon=\frac{1}{D_{\nu}}+\frac{2(|\mathcal{I}|-1)}{C_{b}\epsilon_{\nu}}$ and

Let $\mathcal{M}$ bounded. The sample complexity of the instantiated CombGame meta-algorithm on bandit $\mu\in\mathcal{M}$ satisfies:

where $c>0$ is the parameter of the exploration bonus $f(t)$ when taking $b=1$. The reminder terms are: the approximation error $h(t)=O\left(\sqrt{t\ln(t)}\right)$, the learner’s cumulative regret $R_{t}^{A}$ and a constant $C_{\nu}$ depending on the distribution.

The instantiated CombGame meta-algorithm is an asymptotically optimal algorithm.

By the absurd, we assume there exists $t>T_{0}(\delta)$ such that $\mathcal{E}_{t}\cap\{t<\tau_{\delta}\}\neq\emptyset$. Under event $\mathcal{E}_{t}$ combining $t>T_{0}(\delta)$ and $t<\tau_{\delta}$ yields the following contradiction:

Therefore, we have $\mathcal{E}_{t}\cap\{t<\tau_{\delta}\}=\emptyset$. Hence, for all $t>T_{0}(\delta)$, $\mathcal{E}_{t}\subset\{\tau_{\delta}\leq t\}$. Applying Lemma 4.2 concludes the proof of the finite-time upper bound. Taking the limit $\delta\rightarrow 0$ yields that the instantiated CombGame meta-algorithm is an asymptotically optimal algorithm.

G.5 Technical Arguments

In Appendix G.5, we prove technical arguments on C-Tracking (Appendix G.5.1) and on concentration events (Appendix G.5.2).

Using sparse C-Tracking, we have: for all $t\geq n_{0}$ and for all $A\in\mathcal{A}$, and all $a\in[d]$,

If $A\notin B_{t}$, we have $N_{t,A}=0$ and $\sum_{s=1}^{t}w_{s,A}=0$. Hence the first inequalities are immediate. Let $A\in B_{t}$ and $S_{t,A}=\sum_{s=1}^{t}w_{s,A}$. We will prove $N_{t,A}\leq 1+S_{t,A}$ by induction. At $t=n_{0}$, the result is true based on the initialization: $S_{n_{0},A}=1$ if $A\in B_{n_{0}}$ and $S_{n_{0},A}=0$ else. Assume that $N_{s,A}\leq S_{s,A}+1$ for all $A\in\mathcal{A}$ and all $s\leq t-1$. Let’s prove that it holds at round $t$ too. If $A\neq A_{t}$, the induction property yields: $N_{t,A}=N_{t-1,A}\leq S_{t-1,A}+1\leq S_{t,A}+1$. Assume $A=A_{t}$, then:

where the last inequality is shown by the absurd. If $\min_{A\in\mathcal{A}}\frac{N_{t-1,A}}{S_{t,A}}\leq 1$ doesn’t hold, we have for all $A\in\mathcal{A}$, $N_{t-1,A}>S_{t,A}$. Summing these strict inequalities yields a contradiction: $t-1=\sum_{A\in\mathcal{A}}N_{t-1,A}>\sum_{A\in\mathcal{A}}S_{t,A}=\sum_{s=1}^{t}\sum_{A\in\mathcal{A}}w_{s,A}=t$. Therefore, we have $N_{t,A_{t}}\leq 1+S_{t,A_{t}}$. This concludes the induction.

Combining the previous upper bound and $t=\sum_{A\in\mathcal{A}}N_{t,A}=\sum_{A\in\mathcal{A}}S_{t,A}$ yield the lower bound:

Applying the linear map $W_{\mathcal{A}}$ on the previous inequalities yield the counterpart at the arms level:

Lemma 8 from Degenne et al. (2019) is a technical lemma on summations.

For $t\geq t_{0}\geq 1$ and $(x_{s})_{s\in[t]}$ non negative real numbers such that $\sum_{s=1}^{t_{0}-1}x_{s}>0$,

G.5.2 Concentration Arguments

Let $t_{b}=t^{1/(1+b)}<t$, $L_{\mathcal{M}}$ the Lipschitz constant of $x\mapsto d_{KL}(x,y)$ ($\mathcal{M}$ bounded). The sequence of concentrations events $(\mathcal{E}_{t})_{t\geq 1}$ for the exploration bonus $f$ with parameters $c>0$ and $b>0$ was defined as:

Lemma 14 in Degenne et al. (2019) controls the deviation $\left|d_{\text{KL}}(\mu_{s-1,a},\lambda_{a})-d_{\text{KL}}(\mu_{a},\lambda_{a})\right|$. Its proof is similar to the beginning of the proof of Lemma G.8.

Let $\mathcal{M}$ bounded. Under $\mathcal{E}_{t}$, for all $s\in[t]$, $a\in[d]$ any $\lambda\in\mathcal{M}$,

Let $\mathcal{M}$ be bounded. Under $\mathcal{E}_{t}$, for any $\lambda\in\mathcal{M}$,

Under the event $\mathcal{E}_{t}$, for all $s\in[t]$: $\sup_{\phi\in[\alpha_{s,a},\beta_{s,a}]}(r_{s,a}-d_{\text{KL}}(\phi,\lambda_{s,a}))\leq D_{s,a}$. Let $C_{s,a}=r_{s,a}-d_{\text{KL}}(\mu_{s-1,a},\lambda_{s,a})$, we obtain: