Alex Luedtke

Emilie Kaufmann

Antoine Chambaz

Asymptotically Optimal Algorithms for Budgeted Multiple Play Bandits

We study a generalization of the multi-armed bandit problem with multiple plays where there is a cost associated with pulling each arm and the agent has a budget at each time that dictates how much she can expect to spend. We derive an asymptotic regret lower bound for any uniformly efficient algorithm in our setting. We then study a variant of Thompson sampling for Bernoulli rewards and a variant of KL-UCB for both single-parameter exponential families and bounded, finitely supported rewards. We show these algorithms are asymptotically optimal, both in rate and leading problemdependent constants, including in the thick margin setting where multiple arms fall on the decision boundary.

Introduction

In the classical multi-armed bandit problem, an agent is repeatedly confronted with a set of K probability distributions ν 1 , . . . , ν K called arms and must at each round select one of the available arms to pull based on their knowledge from previous rounds of the game. Each played arm presents the agent with a reward drawn from the corresponding distribution, and the agent's objective is to maximize the expected sum of their rewards over time or, equivalently, to minimize the total regret (the expected reward of pulling the optimal arm at every time step minus the expected sum of the rewards corresponding to their selected actions). To play the game well, the agent must balance the need to gather new information about the reward distribution of each arm (exploration) with the need to take advantage of the information that they already have by pulling the arm for which they believe the reward will be the highest (exploitation).

The bandit problem first started receiving rigorous mathematical attention slightly under a century ago [START_REF] W R Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]. This early work focused on Bernoulli rewards, that are relevant in the simplest modeling of a sequential clinical trial, and presented a Bayesian algorithm now known as Thompson sampling. Since that time, many authors have contributed to a deeper understanding of the multi-armed bandit problem, both with Bernoulli and other reward distributions and either from a Bayesian [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF] or frequentist [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] perspective. [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] established a lower bound on the (frequentist) regret of any algorithm that satisfies a general uniform efficiency condition. This lower bound provides a concise definition of asymptotic (regret) optimality for an algorithm: an algorithm is asymptotically optimal when it achieves this lower bound. [START_REF] Lai | Adaptive treatment allocation and the multi-armed bandit problem[END_REF] introduced what are known as upper confidence bound (UCB) procedures for deciding which arm to pull at a given time step. In short, these procedures compute a UCB for the expected reward of each arm at each time and pull the arm with the highest UCB. Many variants of UCB algorithms have been proposed since then (see the Introduction of Cappé et al., 2013a for a thorough review), with more explicit indices and/or finite-time regret guarantees. Among them the KL-UCB algorithm [Cappé et al., 2013a] is proved to be asymptotically optimal for rewards that belong to a one-parameter exponential family and finitely-supported rewards. Meanwhile, there has been a recent interest in the theoretical understanding of the previously discussed Thompson sampling algorithm, whose first regret bound was obtained by Agrawal and [START_REF] Goyal | Analysis of thompson sampling for the multi-armed bandit problem[END_REF]. Since then, Thompson Sampling has been proved to be asymptotically optimal for Bernoulli rewards [Kaufmann et al., 2012b, Agrawal and[START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF] and for reward distributions belonging to univariate exponential families [START_REF] Korda | Thompson sampling for 1-dimensional exponential family bandits[END_REF].

There has recently been a surge of interest in the multi-armed bandit problem, due to its applications to (online) sequential content recommendation. In this context each arm models the feedback of an agent to a specific item that can be displayed (e.g. an advertisement). In this framework, it might be relevant to display several items at a time, and some variants of the classical bandit problems that have been proposed in the literature may be considered. In the multi-armed bandit with multiple plays, m ≥ 1 out of K arms are sampled at each round and all the associated rewards are observed by the agent, who receives their sum. [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: IID rewards[END_REF] present a regret lower bound for this problem, together with a (non-explicit) matching strategy. More explicit strategies can be obtained when viewing this problem as a particular instance of a combinatorial bandit problem with semi-bandit feedback. Combinatorial bandits, originally introduced by [START_REF] Cesa | Combinatorial Bandits[END_REF] in a non-stochastic setting, present the agent with possibly structured subsets of arms at each round: once a subset is chosen, the agent receives the sum of their rewards. The semi-bandit feedback corresponds to the case where the agent is able to see the reward of each of the sampled arms [START_REF] Audibert | Minimax policies for combinatorial prediction games[END_REF]. Several extensions of UCB procedures have been proposed for the combinatorial setting (see e.g. [START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF], Combes et al. [2015b]), with logarithmic regret guarantees. However, existing regret upper bounds do not match the lower bound of [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: IID rewards[END_REF]. In particular, despite the strong practical performance of KL-UCB-based algorithms in some combinatorial settings (including multiple-plays), their asymptotic optimality has never been established. Extending the optimality result from the single-play setting has proven challenging, especially in settings where the optimal set of m arms in non-unique. Recently, [START_REF] Komiyama | Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[END_REF] proved the asymptotic optimality of Thompson sampling for multiple-play bandits with Bernoulli rewards in the case where the arm with the m th largest mean is unique. An important consequence of the uniqueness of the m th largest mean is that the optimal set of m arms is necessarily unique, which may not be plausible in practice.

In this paper, we extend the multiple plays model in two directions, incorporating a budget constraint and an indifference point. Given a known cost c a associated with pulling each arm a, at each round a subset of arms Â(t) is selected, so that the expected cost of pulling the chosen arms is at most the budget B. More formally, letting C(t) ≡ a∈ Â(t) c a , one requires E[C(t)] ≤ B, where the expectation over the random selection of the subset Â(t) is taken conditionally on past observations. The agent observes the reward associated to the selected arms and receives a total reward R(t) = K a=1 Y a (t)1 (a∈ Â(t)) , where Y a (t) is drawn from ν a . This reward is then compared to what she could have obtained, had she spent the same budget on some other activity, for which the expect reward per cost unit is ρ ≥ 0 (that is, the agent may prefer to use that money for some purpose that has reward to cost ratio greater than ρ and is external to the bandit problem). We note that, for positive reward distributions, choosing ρ = 0 corresponds to taking an action at every round. The agent's gain at round t is thus defined as

G(t) = R(t) -ρC(t) = a∈ Â(t) (Y a (t) -c a ρ) .
The goal of the agent is to devise a sequential subset selection strategy that maximizes the expected sum of her gains, up to some horizon T and for which the budget constraint E[C(t)] ≤ B is satisfied at each round t ≤ T . In particular, arm a is "worth" drawing (in the sense that it increases the expected gain) only if its average reward per cost unit, µ a /c a (where µ a is the expectation of ν a ), is at least the indifference point ρ.

This new framework no longer requires the number of arm draws to be fixed. Rather, the number of arm draws is selected to exhaust the budget, which makes sense in several online marketing scenarios. One can imagine for example a company targeting a new market on which it is willing to spend a budget B per week. Each week, the company has to decide which products to advertise for, and the cost of the advertising campaign may vary. After each week, the income associated to each campaign a is measured and compared to the minimal income of ρc a that can be obtained when targeting other (known) markets or investing the money in some other well-understood venture. Another possible scenario is that the same item can be displayed on several marketplaces never explored before for different costs, and the seller has to sequentially choose the different places he wants to display the items on while keeping the total budget spend smaller than B and maintaining a profitability larger than what can be obtained on a reference market place with reward per cost unit ρ.

Our first contribution is to characterize the best attainable performance in terms of regret (with respect to the gain G(t), not the total reward R(t)) in this multiple-play bandit scenario with cost constraints, thanks to a lower bound that generalizes that of [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: IID rewards[END_REF]. We then study natural extensions of two existing bandit algorithms (KL-UCB and Thompson sampling) to our setting. We prove both rate and problem-dependent leading constant optimality for KL-UCB and Thompson sampling. The most difficult part of the proof is to show that the optimal arms away from the margin are pulled in almost every round (specifically, they are pulled in all but a sub-logarithmic number of rounds). [START_REF] Komiyama | Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[END_REF] studied this problem for Thompson sampling in multiple-play bandits using an argument different than that used in this paper. We provide a novel proof technique that leverages the asymptotic lower bound on the number of draws of any suboptimal arm. While this lower bound on suboptimal arm draws is typically used to prove an asymptotic lower bound on the regret of any reasonable algorithm, we use it as a key ingredient for our proof of an asymptotically optimal upper bound on the regret of KL-UCB and Thompson sampling, i.e. to prove the asymptotic optimality of these two algorithms. Also, throughout the manuscript, we do not assume that the set of optimal arms is unique, unlike most of the existing work on (standard) multiple-play bandits.

The rest of the article is organized as follows. Section 2 outlines our problem of interest. Section 3 provides an asymptotic lower bound on the number of suboptimal arm draws and on the regret. Section 4 presents the two sampling algorithms we consider in this paper and theorems establishing their asymptotic optimality: KL-UCB (Section 4.1) and Thompson sampling (Section 4.2). Section 5 presents numerical experiments supporting our theoretical findings. Section 6 presents the proofs of our asymptotic optimality (rate and leading constant) results for KL-UCB and Thompson Sampling. Section 7 gives concluding remarks. Technical proofs are postponed to the Appendix.

Multiple plays bandit with cost constraint

We consider a finite collection of arms a ∈ {1, . . . , K}, where each arm has real-valued marginal reward distribution ν a whose mean we denote by both µ a and E(ν a ). Each arm belongs to a (possibly nonparametric) class of distributions D. We use V to denote (ν 1 , . . . , ν K ), where V belongs to any model D K that is variation-independent in the sense that, for each a ∈ {1, . . . , K}, knowing the joint distribution of the rewards a = a places no restrictions on the collection of possible marginal distributions of ν a , i.e. ν a could be equal to any element in D. More formally, letting D -a denote the collection of joint distributions of the rewards a = a implied by at least one distribution in D K , variation independence states that, for each a ∈ {1, . . . , K} it is true that, for every joint distribution V -a ∈ D -a and every distribution ν a ∈ D, there exists a distribution in D K whose joint distribution of the rewards a = a is equal to V -a and whose marginal distribution of reward a is equal to ν a . An example of a statistical model satisfying this variation-independence assumption is the distribution in which the rewards of all of the arms are independent and the marginal distributions ν a fall in D for all a, though this assumption also allows for high levels of dependence between the rewards of the arms, i.e. is not to be confused with the much stronger model assumption of independence between the different arms.

The sequential decision problem

Let {(Y 1 (t), . . . , Y K (t))} ∞ t=1 be an independent and identically distributed (i.i.d.) sample from the distribution V. In the multiple-play bandit with cost constraint, each arm a is associated with a known cost c a > 0. The model also depends on a known budget per round B and indifference parameter ρ ≥ 0. At round t, the agent selects a subset Â(t) of arms and subsequently observes the action-reward pairs {(a, Y a (t)) : a ∈ Â(t)}. We emphasize that the agent is aware that reward Y a (t) corresponds to the action a ∈ Â(t). This subset Â(t) is drawn from a distribution Q(t -1) over S K , the set of all subsets of {1, . . . , K}, that depends on the observations gathered at the (t -1) previous rounds. More precisely, Q(t) is F(t)-measurable, where F(t) is the σ-field generated by all action-reward pairs seen at times 1, . . . , t, and possibly also some exogenous stochastic mechanism. We use q a (t) to denote the probability that arm a falls in Â(t + 1) ∼ Q(t).

Given the budget B and the indifference parameter ρ, at each round (t + 1) the distribution Q(t) must respect the budget constraint

E A∼Q(t) a∈A c a ≤ B, or, equivalently, K a=1 c a q a (t) ≤ B.
(1)

Upon selecting the arms, the agent receives a reward R(t + 1) = a∈ Â(t+1) Y a (t + 1) and incurs a gain

G(t + 1) = a∈ Â(t+1) (Y a (t + 1) -c a ρ).
Given a (possibly unknown) horizon T , the goal of the agent is to adopt a strategy for sequentially selecting the distributions Q(t) that maximizes

E T t=1 G(t) ,
while satisfying, at each round t = 0, . . . , T -1 the budget constraint (1). This constraint may be viewed as a 'soft' budget constraint, as it allows the agent to (slightly) exceed the budget at some rounds, as long as the expected cost remains below B at each round. We shall see below that considering a 'hard' budget constraint, that is selecting at each round a deterministic subset Â(t) that satisfies K a=1 c a 1 (a∈ Â(t)) ≤ B, is a much harder problem. Besides, in the marketing examples described in the introduction, it makes sense to consider a large time horizon and to allow for minor budget crossings. Under the soft budget constraint (1), if we knew the vector of expected mean rewards µ ≡ (µ 1 , . . . , µ K ), at each round t we would draw a subset from a distribution

Q ∈ argmax Q E S∼Q a∈S (µ a -c a ρ) such that E S∼Q a∈S c a ≤ B. (2)
Above, the argmax is over distributions Q with support on the power set of {1, . . . , K}. Noting that the two expectations only depend on the marginal probability of inclusions q a = P S∼Q (a ∈ S), it boils down to finding a vector q = (q a ) K a=1 that satisfies

q ∈ argmax q∈[0,1] K K a=1 q a (µ a -c a ρ) such that K a=1 q a c a ≤ B. (3)
An oracle strategy would then draw S from a distribution Q with marginal probabilities of inclusions given by q (e.g. including independently each arm a with probability q a ). The optimization problem (3) is known as a fractional knapsack problem [START_REF] Dantzig | Discrete-variable extremum problems[END_REF], and its solution is a greedy strategy, that is described below. It is expressed in terms of the reward-to-cost ratio of each arm a, defined as ρ a ≡ µ a /c a .

Proposition 1. Introduce ρ ≡ ρ if a:ρa>ρ c a < B, sup{r ≥ 0 : a:ρa>r c a ≥ B} ≥ ρ otherwise, and define the three sets optimal arms away from the margin: L ≡ {a : ρ a > ρ }, arms on the margin: M ≡ {a : ρ a = ρ }, suboptimal arms away from the margin: N ≡ {a : ρ a < ρ }.

Then q is solution to (3) if and only if q a = 1 for all a ∈ L, q b = 0 for all b ∈ N and a∈M c a q a = B -a∈L c a if ρ > ρ.

We would like to emphasize that, just like the quantities Q , q or ρ a defined above, the quantity ρ defined in Proposition 1 depends on the value of ρ, the vector of cost and on the vector of means µ. When we need to materialize this dependency in µ we shall use the notation ρ (µ), but it is sometimes omitted for the sake of readability.

From Proposition 1, proved in Appendix A, the optimal strategy sorts the items by decreasing order of ρ a , and includes them one by one (q a = 1), as long as the value increases and the budget is not exceeded. Then we can identify two situations: if ρ (µ) = ρ, there are not enough interesting items (i.e. such that ρ a > ρ) to saturate the budget, and the optimal strategy is to include all the interesting items. If ρ (µ) > ρ, some probability of inclusion is further given to the items on the margin in order to saturate the budget constraint. In that case, the margin is always non-empty: there exist items a such that ρ (µ) = ρ a .

Recovering the multiple-play bandit model. By choosing c a = 1 for all arm a, B = m and ρ = 0, we recover the classical multiple-play bandit model. In that case ρ (µ) = µ [m] , where [m] is the arm with the m th largest mean and [m]} is a solution to (2): the corresponding oracle strategy always plays the m arms with largest means.

Q = δ {[1],...,
Hard and soft constraints. Under hard budget constraints, if we knew the vector of expected mean rewards µ, at each round t we would pick a subset

S ∈ argmax S∈S K a∈S (µ a -c a ρ) such that a∈S c a ≤ B. (4)
This is a 0/1 knapsack problem, that is much harder to solve than the above fractional knapsack problem.

In fact, 0/1 knapsack problems are NP-hard, though they are, admittedly, some of the easiest problems in this class, and reasonable approximation schemes exist [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Nonetheless, the greedy strategy (including arms by decreasing order of ρ a while the budget is not exceeded, with ties broken arbitrarily) is not generally a solution to (4). However, using Proposition 1, one can identify some examples where there exist deterministic solutions to (3), i.e. solutions such that q a ∈ {0, 1} that are therefore solutions to (4): if ρ (µ) = ρ or if there exists m ∈ M such that a∈L∪{m} c a = B. Hence the multiple-play bandit model can be viewed as a particular instance of the multiple plays model under both hard or soft budget constraint. In the rest of the article, we only consider soft budget constraints, as there is generally no tractable oracle under hard budget constraints.

High-probability bound on the budget spent by a finite horizon T . In Appendix ??, we outline how one could analyze the regret of algorithms that respect the soft budget constraint (1) at each time t in a finite-horizon problem in which the requirement that (1) hold at each time t is replaced by the hard budget constraint that T t=1

a∈ Â(t) c a ≤ BT almost surely. Our argument suggests that the regret in these settings should be no worse than O( √ T ).

Regret decompositions

The best achievable (oracle) performance consists in choosing, at every round t, Q(t) to be the optimal distribution Q whose probabilities of inclusions are described in Proposition 1. Using the definitions introduced in Proposition 1, such a strategy ensures an expected gain at each round of

G ≡ K a=1
q a (µ ac a ρ).

(5)

The quantity above is the reward from pulling the chosen arms relative to the reward from reallocating the expected cost of the strategy, namely K a=1 q a c a , to pursue the action (which is external to the bandit problem) that has reward-to-cost ratio equal to the indifference point ρ. We prove the following identity in Appendix A.

Proposition 2. It holds that

G = a∈L µ a + ρ B - a∈L c a -Bρ.
Maximizing the expected total gain is equivalent to minimizing the regret, that is the difference in performance compared to the oracle strategy:

Regret(T, V, Alg) ≡ T G -E V T t=1 G(t) ,
where the sequence of gains G(t) is obtained under algorithm Alg. The following statement, proved in Appendix A, provides an interesting decomposition of the regret, as a function of the number of selections of each arm, denoted by N a (T ) ≡ T t=1 1{a ∈ Â(t)}. Proposition 3. With ρ = ρ (µ), L, N defined as in Proposition 1, for any algorithm Alg

Regret(T, V, Alg) = a ∈L c a (ρ a -ρ ) (T -E V [N a (T )]) + a∈N c a [ρ -ρ a ] E V [N a (T )] +(ρ -ρ) BT - K a=1 c a E V [N a (T )] . (6)
This decomposition writes the regret as a sum of three non-negative terms. In order for the regret to be small, each optimal arm a ∈ L should be drawn very often (of order T times, to make the first term small) and each suboptimal arm a ∈ N should be drawn seldomly (to make the second term small). Finally if ρ > ρ, that is if there are sufficiently many 'worthwhile' arms to exceed the budget, then the third term appears as a penalty for not using the whole budget at every round. It means that arms on the margin M have to be drawn sufficiently often so as to saturate the budget constraint.

An extended bandit interpretation. Here we propose another view on this regret decomposition, by means of an extended bandit game with an extra arm, which we term a pseudo-arm, that represents the choice not to pull arms. Whenever an algorithm does not saturate the budget constraint (1), one can view this algorithm as putting weight on a pseudo-arm in the bandit, that yields zero gain but permits saturation of the budget. Letting µ K+1 = Bρ and c K+1 = B, the gain associated with drawing arm (K + 1) (whose distribution is a point mass at Bρ) is indeed zero (as µ K+1ρc K+1 = 0) and, for any q(t) such that K a=1 q a (t)c a ≤ B, there exists q K+1 (t) such that K+1 a=1 q a (t)c a = B, as c K+1 = B. Any algorithm for the original bandit problem selecting Ŝ(t) ∈ S K at time t can thus be viewed as an algorithm selecting S(t) ∈ S K+1 , that additionally includes arm (K + 1) with probability q K+1 (t). As the pseudo-arm is associated with a null gain, the cumulated gain and regret are similar in both settings. Moreover, as q K+1 (t) = (B -K a=1 c a q a (t))/B, one easily sees that the number of (artificial) selections of the pseudo-arm is such that

BE[N K+1 (T )] = BT - K a=1 c a E[N a (T )],
which equals the third term in the regret decomposition, up to the factor (ρρ).

In this extended bandit model, the three sets of arms introduced in Proposition 1 remain unchanged, with L ≡ {a ∈ {1, . . . , K + 1} : ρ a > ρ }, M ≡ {a ∈ {1, . . . , K + 1} : ρ a = ρ } and N ≡ {a ∈ {1, . . . , K + 1} : ρ a < ρ }. As ρ K+1 = ρ ≤ ρ , the pseudo-arm may only belong to M or N , and the margin M is always non-empty. Considering the extended bandit model, the regret decomposition can be rewritten in a more compact way:

Regret(T, V, Alg) = a ∈L c a (ρ a -ρ ) (T -E[N a (T )]) + a∈N c a [ρ -ρ a ] E[N a (T )].
Our proofs make use of this extended bandit model, since many of the results we present apply to both the "actual" arms a = 1, . . . , K and the pseudo-arm (K + 1). Our proofs also make use of a set S, which, in the extended bandit model, refers to all arms in (L ∪ M)\{K + 1} whereas, in the unextended bandit model, it refers simply to all optimal arms both on and away from the margin.

Related work

There has been considerable work on various forms of "budgeted" or "knapsack" bandit problems [START_REF] Tran-Thanh | Knapsack Based Optimal Policies for Budget-Limited Multi-Armed Bandits[END_REF][START_REF] Badanidiyuru | Bandits with knapsacks[END_REF][START_REF] Devanur | Bandits with concave rewards and convex knapsacks[END_REF][START_REF] Xia | Thompson Sampling for Budgeted Multi-Armed Bandits[END_REF], 2016a[START_REF] Li | Infinitely Many-Armed Bandits with Budget Constraints[END_REF]. The main difference between our work and these works is that we consider a round-wise budget constrain, and allow for several arms to be selected at each round, possibly in a randomized way in order to satisfy the budget constraint in expectation. In contrast, in most existing works, one arm is (deterministically) selected at each round, and the game ends when a global budget is exhausted. The work of Xia et al. [2016b] appears to be the most closely related to ours: in their setup the agent may play multiple arms at each round, though the number of arms pulled at each round is fixed and the cost of pulling each arm is random and observed upon pulling each arm. [START_REF] Sankararaman | Combinatorial semi-bandits with knapsacks[END_REF] also consider a framework in which a subset of arms is selected at each round, but this subset is chosen from a list of candidate subsets (as in a combinatorial bandit problem) and there is a global budget constraint. Compared to all these mentioned budgeted bandit problems, the focus of our analysis differs substantially, in that our primary objective is to not only prove rate optimality, but also leading constant optimality of our regret bounds. Proving constant optimality is especially challenging in situations where the set of optimal arms is non-unique, but we give careful arguments that overcome this challenge.

Several other extensions of the multiple-play bandit model have been studied in the literature. UCB algorithms have been widely used in the combinatorial semi-bandit setting, in which at each time step a subset of arms has to be select among a given class of subsets, and the rewards of every individual arms in the subset are observed. The most natural use of UCBs and the "optimism in face of uncertainty principle" is to choose at every time step the subset that would be the best if the unknown means were equal to the corresponding UCBs. This was studied by [START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF], [START_REF] Kveton | Matroid Bandits: Fast Combinatorial Optimization with Learning[END_REF], [START_REF] Wen | Efficient Learning in Large-Scale Combinatorial Semi-Bandits[END_REF], who exhibit good empirical performance and logarithmic regret bounds. Combes et al. [2015b] further study instance-dependent optimality for combinatorial semi bandits, and propose an algorithm based on confidence bounds on the value of each subset, rather than on confidence bounds on the arms' means. Their ESCB algorithm is proved to be order-optimal for several combinatorial problems. As a by product of our results, we will see that in the multiple-play setting, using KL-based confidence bounds on the arms' means is sufficient to achieve asymptotic optimality. Another interesting direction of extension is the possibility to have only partial feedback over the m proposed item. Variants of KL-UCB and Thompson Sampling were proposed for the Cascading bandit model [Kveton et al., 2015a,b], Learning to Rank [Combes et al., 2015a] or the Position-Based model [START_REF] Lagrée | Multiple-Play Bandits in the Postition-Based Model[END_REF]. It would be interesting to try to extend the results presented in this work to these partial feedback settings.

Regret Lower Bound

We first give in Lemma 4 asymptotic lower bounds on the number of draws of suboptimal arms, either in high-probability or in expectation, in the spirit of those obtained by [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF], [START_REF] Anantharam | Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: IID rewards[END_REF]. Compared to these works, the lower bounds obtained here hold under our more general assumptions on the arm distributions, which is reminiscent of the work of [START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF].

To be able to state our regret lower bound, we now introduce the following notation. We let KL(ν, ν ) denote the KL-divergence between distributions ν and ν . If ν and ν are uniquely parameterized by their respective means µ and µ as in a canonical single parameter exponential family (e.g. Bernoulli distributions), then we abuse notation and let KL(µ, µ ) ≡ KL(ν, ν ). For a distribution ν ∈ D and a real µ, we define

K inf (ν, µ) ≡ inf {KL(ν, ν ) : ν ∈ D and µ < E(ν ) and ν ν } , (7)
with the convention that K inf (ν, µ) = ∞ if there does not exist a ν ν with µ < E(ν ). We will also use the convention that, for finite constants

d 1 , d 2 , d 1 /(d 2 + K inf (ν, µ)) = 0 when K inf (ν, µ) = ∞.
We make one final assumption, and introduce two disjoint sets N and N , whose union is N . The assumption is that, for each arm a ∈ {1, . . . , K}, µ a falls below the upper bound of the expected reward parameter space, i.e. µ a < µ + ≡ sup{E(ν) : ν ∈ D}. We define the sets N and N respectively as the subsets of N for which optimality is and is not feasible given our parameter space, namely

N ≡ [N ∩ {a : c a ρ < µ + }] \{K + 1} N ≡ [N ∩ {a : c a ρ ≥ µ + }] \{K + 1}.
By defining N and N in this way, these sets agree in the extended and unextended bandit models. The lower bounds presented in this section will also agree in these two models.

We now define a uniformly efficient algorithm, that generalizes the class of algorithms considered in [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. An algorithm Alg is uniformly efficient if, for all V ∈ D K and α ∈ (0, 1), Regret(T, V, Alg) = o(T α ) as T goes to infinity (from now on, the limits in T will be for T → ∞). From the regret decomposition (6), this is equivalent to

1. T -E V [N a (T )] = o (T α ) for all arms a such that ρ a > ρ (µ); 2. E V [N a (T )] = o(T α ) for all arms a such that ρ a < ρ (µ); 3. if ρ (µ) > ρ, BT - K a=1 c a E V [N a (T )] = o(T α ),
where above and throughout we write E V when we wish to emphasize that the expectation is over V.

Lemma 4 (Lower bound on suboptimal arm draws). If an algorithm is uniformly efficient, then, for any arm a ∈ (M ∪ N )\{K + 1} and any δ ∈ (0, 1) and > 0,

lim T P N a (T ) < (1 -δ) log T K inf (ν a , c a ρ ) + = 0. ( 8
)
One can take = 0 if a ∈ N . Furthermore, for any suboptimal arm a ∈ N ,

lim inf T E[N a (T )] log T ≥ 1 K inf (ν a , c a ρ ) . ( 9
)
We defer the proof of this result to Appendix B. We note that, while (9) could also easily be obtained using the recent change-of-distribution tools introduced by [START_REF] Garivier | Explore First, Exploit Next: The True Shape of Regret in Bandit Problems[END_REF], we need to go back to Lai and Robbins' technique to prove the high-probability result (8), which will be crucial in the sequel. Indeed, we will use it to prove optimal regret of our algorithms: in essence we need to ensure that we have enough information about arms in M ∪ N to ensure that we pull the optimal arms in L sufficiently often.

We now present a corollary to Lemma 4 which provides a regret lower bound, as well as sufficient conditions for an algorithm to asymptotically match it. As already noted by [START_REF] Komiyama | Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[END_REF] in the Bernoulli case for the bandit with multiple-play problems, an algorithm achieving the asymptotic lower bound (9) on the expected number of draws of arms in N does not necessarily achieve optimal regret, unlike in classic bandit problems. Thus, we emphasize that the upcoming condition (11) alone is not sufficient to prove asymptotic optimality. The conditions of this proof can be easily obtained from the regret decomposition (6), and so the proof is omitted.

Theorem 5 (Regret lower bound). If an algorithm Alg is uniformly efficient, then

lim inf T Regret(T, V, Alg) log T ≥ a∈N c a (ρ -ρ a ) K inf (ν a , c a ρ ) . ( 10
)
Moreover, any algorithm Alg satisfying for arms a ∈ N :

E V [N a (T )] = log T K inf (ν a , c a ρ ) + o(log T ), ( 11
)
for arms a ∈ N E V [N a (T )] = o(log T ), ( 12
)
for arms a ∈ L:

E V [N a (t)] = T -o(log T ), ( 13
)
and, if ρ (µ) > ρ, BT - K a=1 c a E V [N a (T )] = o(log(T )), (14)
is asymptotically optimal, in the sense that it satisfies

lim sup T Regret(T, V, Alg) log T ≤ a∈N c a (ρ -ρ a ) K inf (ν a , c a ρ ) . ( 15
)
4 Algorithms

Algorithms rely on estimates of the arm distributions and their means, that we formally introduce below.

For each arm a and natural number n, define τ a,n = min{t ≥ 1 : N a (t) = n} to be the (stopping) time at which the n th draw of arm a occurs. Let X a,n ≡ Y a (τ a,n ) denote the n th draw from ν a . One can show that {X a,n } ∞ n=1 is an i.i.d. sequence of draws from ν a for each a, though we note that our variation independence assumption is too weak to ensure that these sequences are independent for two arms a = a (this is not problematic -most of our arguments end up focusing on arm-specific sequences {X a,n } ∞ n=1 ) [1] . We denote the empirical distribution function of observations drawn from arm a by any time T by

νa (T ) ≡ 1 N a (T ) T t=1 δ Ya(t) 1{a ∈ Â(t)} = 1 N a (T ) Na(T ) n=1 δ Xa,n .
We similarly define νa,n to be the empirical distribution function of the observations X a,1 , . . ., X a,n . Thus, νa (t) = νa,Na(t) . We further define μa (t) to be the empirical mean of observations drawn from arm a by time t and μa,Na(t) = μa (t).

KL-UCB

At time t, UCB algorithms leverage high probability upper bound U a (t) on µ a for each a. The methods used to build these confidence bounds vary, as does the way the algorithm uses these confidence [1] It is a priori possible that τa,n = ∞ for all n large enough (though, as we showed in Section 3, this event will occur with probability zero for any reasonable algorithm). To deal with this case, let Xa,n ≡ Ya(τa,n) denote the n th draws from νa for all τa,n < ∞ and let {Xa,n}n:τ a,n =∞ denote an i.i.d. sequence independent of {Xa,n}n:τ a,n<∞ .

Algorithm KL-UCB

Parameters A non-decreasing function f : N → R and an operator Π D mapping each empirical distribution functions νa (t) to an element of the model D.

Initialization Pull each arm of {1, . . . , K} once. [2] for t = K, K + 1, . . . , T -1 do For a = 1, . . . , K, let U a (t) be defined as in ( 16). Let ρ (t) ≡ ρ (U a (t) : a = 1, . . . , K).

For a ∈ {1, . . . , K}, let q a (t) = 1{U a (t) > c a ρ (t)}. if M(t) ≡ {a : U a (t) = c a ρ (t)} is non-empty then if ρ (t) > ρ then For a ∈ M(t), let q a (t) = B -a:Ua(t)>ca ρ (t) c a / a∈ M(t) c a .
else Let q a (t) = 0 for all a ∈ M(t) [3] . Draw Â(t + 1) from any distribution Q(t) with marginal probabilities q a (t) [4] . Draw arms in Â(t + 1) and observe Y a (t + 1), a ∈ Â(t + 1). bounds. In our setting, we derive these bounds using the same technique as for KL-UCB in Cappé et al. [2013a]. At the beginning of round (t + 1), the KL-UCB algorithm computes an optimistic oracle strategy (q a (t)) a=1,...,K , that is an oracle strategy assuming the unknown mean of each arm a is equal to its best possible value, U a (t). From Proposition 1, this optimistic oracle depends on ρ (t) = ρ (U a (t) : a = 1, . . . , K), where ρ (µ) is the function defined in Proposition 1. Then each arm is included in Â(t + 1) independently with probability q a (t). Due to the structure of an oracle strategy, KL-UCB can be rephrased as successively drawing the arms by decreasing order of the ratio U a (t)/c a until the point that the budget is exhausted, with some probability to include the arms on the margin. We choose to keep the name KL-UCB for this straightforward generalization of the original KL-UCB algorithm.

The definition of the upper bound U a (t) is closely related to that of K inf given in (7). Let Π D be a problem-specific operator mapping each empirical distribution function νa (t) to an element of the model D. Furthermore, let f : N → R be a non-decreasing function, where this function is usually chosen so that f (t) ≈ log t. The UCB is then defined as

U a (t) ≡ sup E(ν) : ν ∈ D and KL (Π D (ν a (t)) , ν) ≤ f (t) N a (t) , a = 1, . . . , K. (16)
As we will see, the closed form expression for U a (t) can be made slightly more explicit for exponential family models, though the expression still has the same general flavor. If a number µ satisfies µ ≥ U a (t), then this implies that, for every ν ∈ D for which

E(ν) > µ, KL (Π D (ν a (t)), ν) > f (t) Na(t) . Consequently, K inf (Π D (ν a (t)), µ) ≥ f (t)
Na(t) . We now describe two settings in which the algorithm that we have described achieves the optimal asymptotic regret bound. These two settings and the presentation thereof follows Cappé et al. [2013a]. The first family of distributions we consider for D is a canonical one-dimensional exponential family E. For some dominating measure λ (not necessarily Lebesgue), open set H ⊆ R, and twice-differentiable [2] If ca ≤ B for all a, then it is always possible to do this with K draws and respect the budget. In particular, at time t = a, draw arm a with probability one. If, for some a, ca > B, then this strategy will violate the budget constraint, though a stochastic strategy that draws these arms a with probability ca/B until the (random) stopping time at which the first draw occurs would respect the budget. Whether we use this strategy or just pull each arm once has essentially no effect on our analysis, and so for simplicity we assume the agent draws each arm once to initialize the algorithm.

[3] While presumably not necessary, this restriction aids our arguments in Section 6.1, and seems very mild given that at ρ the agent is indifferent to whether she pulls an arm or a pseudo-arm.

[4] An easy choice is to make Q(t) a product measure with marginal probabilities q 1 (t), . . . , q K+1 (t), but this choice is not necessary, and more careful choices may reduce the probability of overspending the budget at any given time point.

strictly convex function b : H → R, E is a set of distributions ν η such that dν η dλ (x) = exp [xη -b(η)] .
We assume that the open set H is the natural parameter space, i.e. the set of all η ∈ R such that exp(xη)dλ(x) < ∞. We define the corresponding (open) set of expectations by I ≡ {E(ν η ) : η ∈ H} ≡ (µ -, µ + ) and its closure by Ī = [µ -, µ + ]. We have omitted the dependence of E on λ and b in the notation. It is easily verified that K inf (µ a , c a ρ ) = KL(ν a , c a ρ ).

For the moment suppose that νa (t) is such that μa (t) ∈ I. In this case we let Π D denote the maximum likelihood operator so that Π D (ν a (t)) returns the unique distribution in D indexed by the η satisfying b (η) = μa (t). Thus, in this setting where μa (t) ∈ I, the UCB U a (t) then takes the form of the expression in ( 16).

More generally, we must deal with the case that μa (t) equals µ + or µ -. For µ ∈ I, define by convention KL(µ -, µ) = lim µ →µ-KL(µ -, µ), KL(µ + , µ) = lim µ →µ+ KL(µ , µ), and analogously for KL(µ, µ -) and KL(µ, µ + ). Finally, define KL(µ -, µ -) and KL(µ + , µ + ) to be zero. This then gives the following general expression for U a (t) that we use to replace ( 16) in the KL-UCB Algorithm:

U a (t) ≡ sup µ ∈ Ī : KL (μ a (t), µ) ≤ f (t) N a (t) , a = 1, . . . , K. (17)
Note that this definition of U a (t) does not explicitly include a mapping Π D mapping any empirical distribution function to an element of the model D. Thus we have avoided any problems that could arise in defining such a mapping when μa (t) falls on the boundary of Ī. The above optimization problem can be solved by noting that µ → KL (μ a (t), µ) is convex, and so one can first identify the µ 0 minimizing this function, and then perform a root-finding method for monotone functions to (approximately) identify the largest µ ≥ µ 0 at which KL (μ a (t), µ) -f (t) Na(t) = 0. The KL-UCB variant that we have presented achieves the asymptotic regret bound in the setting where D = E.

Theorem 6 (Optimality for single parameter exponential families). Suppose that D = E. Further let f (t) = log t + 3 log log t for t ≥ 3 and f (1) = f (2) = f (3). This variant of KL-UCB satisfies (11), ( 12), ( 13) and (14). Thus, KL-UCB achieves the asymptotic regret lower bound (10) for uniformly efficient algorithms.

Another interesting family of distributions for D is a set B of distributions on [0, 1] with finite support. If the support of D is instead bounded in some [-M, M ], then the observations can be rescaled to [0, 1] when selecting which arm to pull using the linear transformation x → (x + M )/(2M ).

If D is equal to B, then Cappé et al. [2013a] observe that ( 16) rewrites as

U a (t) = sup E(ν) : Support[ν] ⊆ Support [ν a (t)] ∪ {1} and KL (ν a (t), ν) ≤ f (t) N a (t)
where, for a measure ν , we use Support [ν ] to denote the support of ν . They furthermore observe that this expression admits an explicit solution via the method of Lagrange multipliers.

Theorem 7 (Optimality for finitely supported distributions). Suppose that D = B. Let Π D denote the identity map and f (t) = log t + log log t for t ≥ 2 and f (1) = f (2). Suppose that µ a ∈ (0, 1) for all a = 1, . . . , K. The variant of KL-UCB satisfies (11), ( 12), ( 13) and (14). Thus, KL-UCB achieves the asymptotic regret lower bound (10) for uniformly efficient algorithms.

In both theorems, the little-oh notation hides the problem-dependent but T -independent quantities. In the proofs of Theorems 6 and 7 we refer to equations in Cappé et al. [2013b] where the reader can find explicit finite-sample, problem-dependent expressions for the o(log T ) term in (11) for the settings of Theorems 6 and 7. The argument used to establish (12) considers similar o(log T ) terms to those that appear in the proof of (11), though the simplest argument for establishing (12) (which, for brevity, is the one that we have elected to present here) invokes asymptotics. The argument used to establish (13) in these settings, on the other hand, seems to be fundamentally asymptotic and does not appear to easily yield finite sample constants. Nonetheless, this is to our knowledge the first handling of thick margins in the multiple-play bandit literature, and so we believe that our rate-and constant-optimal regret guarantee is of interest despite its asymptotic nature.

Moreover, though not presented in detail here, our proof techniques can be used to establish a finitetime regret guarantee that is rate-optimal, namely is O(log T ), but is constant-suboptimal. To obtain this bound, we note that, by Proposition 3, it suffices to combine (i) the previously-discussed finite-time variants of ( 11) and ( 12) that can result from the proof of Theorem 7 and (ii) the following finite-time variant of ( 13), which must hold for all T ≥ 1 and some C > 0:

for arms a ∈ L: E V [N a (t)] = T -C log T. ( 18
)
This guarantee is asymptotically weaker than that in (13) in the sense that the o(log T ) term has been replaced by O(log T ), but is stronger than (13) in the sense that we require a finite-time bound on the O(log T ) term rather than only an asymptotic guarantee. Though we did not explicitly establish the above in our proof of Theorem 7, only a minor modification to the proof is needed. Specifically, by (29), it suffices to obtain a finite-time upper bound on E[M a a (T )] for all a ∈ M ∪ N and a ∈ L. This upper bound can be found by noting that the proof of Lemma 18 shows that E[M a a (T )] ≤ O(log T ), and explicit finite-sample constants can be computed for this bound just as they can for (11). Plugging this into (29) then establishes (18), which in turn establishes a finite-time O(log T ) regret bound. This finite-time regret bound will be valid even if M contains more than one arm.

Thompson Sampling

Algorithm Thompson Sampling

Parameters For each arm a = 1, . . . , K, let Π a (0) be a prior distribution on µ a . for t = 0, 1, . . . do For each arm a = 1, . . . , K, draw

θ a (t) ∼ Π a (t). Let ρ (t) ≡ ρ ((θ a (t) : a = 1, . . . , K)). For a ∈ {1, . . . , K}, let q a (t) = 1{θ a (t) > c a ρ (t)}. if M(t) ≡ {a : θ a (t) = c a ρ (t)} is non-empty then For a ∈ M(t), let q a (t) = B -a:θa(t)>ca ρ (t) c a / a∈ M(t) c a .
Draw Â(t + 1) from any distribution Q(t) with marginal probabilities q a (t).

Draw the corresponding rewards Y a (t + 1), a ∈ Â(t + 1).

For each a ∈ Â(t + 1), obtain a new posterior Π a (t + 1) by updating Π a (t) with the observation Y a (t + 1).

For each a ∈ Â(t + 1), let Π a (t + 1) = Π a (t).

Thompson sampling uses Bayesian ideas to account for the uncertainty in the estimated reward distributions. In a classical bandit setting, one first posits a (typically non-informative) prior over the means of the reward distributions, and then at each time updates the posterior and takes a random draw of the K means from the posterior and pulls the arm whose posterior draw is the largest. In our setting, this corresponds to drawing the subset of arms for which the posterior draw to cost ratio is largest (up until the budget constraint is met), which generalizes the idea initially proposed by [START_REF] W R Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]. In the above algorithm, we focus on independent priors so that the only posteriors updated at time (t + 1) are those of arms in Â(t + 1). At time (t + 1), Thompson Sampling first draws one sample θ a (t) from the posterior distribution on the mean of each arm a, and then selects a subset according an oracle strategy assuming (θ a (t)) a=1,...,K are the true parameters.

We prove the optimality of Thompson sampling for Bernoulli rewards, for the particular choice of a uniform prior distribution on the mean of each arm. Note that the algorithm is easy to implement in that case, since Π a (t) is a Beta distribution with parameters N a (t)μ a (t) + 1 and N a (t)(1μa (t)) + 1. Our proof relies on the same techniques as those used to prove the optimality of Thompson sampling in the standard bandit setting for Bernoulli rewards by Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF]. We note that [START_REF] Komiyama | Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[END_REF] also made use of some of the techniques in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF] to prove the optimality of Thompson sampling for Bernoulli rewards in the multiple-play bandit setting.

Theorem 8 (Optimality for Bernoulli rewards). If the reward distributions are Bernoulli and Π a (0) is a standard uniform distribution for each a, then Thompson sampling satisfies (11), ( 12), ( 13) and (14). Thus, Thompson sampling achieves the asymptotic regret lower bound (10) for uniformly efficient algorithms.

For any > 0 and a ∈ N , the proof shows that Thompson sampling satisfies

E[N a (T )] ≤ (1 + ) 2 f (T ) KL(µ a , c a ρ ) + o(log T ).
The proof gives an explicit bound on the o(log T ) term that depends on both the problem and the choice of . We conclude by noting that, similarly as for KL-UCB, our proof techniques can be easily adapted to give a rate-optimal but constant-suboptimal finite-time regret bound, where this bound will be valid even if M contains more than one arm.

Numerical Experiments

We now run four simulations to evaluate our theoretical results in practice, all with Bernoulli reward distributions, a horizon of T = 100 000, and K = 5. The simulation settings are displayed in Table 1.

Simulations 1-3 are run using 5 000 Monte Carlo repetitions, and Simulation 4 was run using 50 000 repetitions to reduce Monte Carlo uncertainty.

µ c B ρ L M N Sim 1 (0.5, 0.45, 0.45, 0.4, 0.3) (1, 1, 1, 1, 1) 2 0 {1} {2, 3} ∅ Sim 2 (0.7, 0.6, 0.5, 0.3, 0.2)
(1, 1, 1, 1, 1) 3 0 {1, 2} {3} ∅ Sim 3 (0.5, 0.45, 0.45, 0.4, 0.3) (0.8, 1, 1, 0.8, 0.6) 2 0.5 {1} {4, 5, 6} ∅ Sim 4 (0.7, 0.6, 0.5, 0.3, 0.2)

(1.5, 1, 1, 1, 2.5) 3 0.4 {2, 3} {1} {5}

Table 1: Simulation settings considered. Simulations 1 and 3 have non-unique margins so that q a must be less than one for at least one arm a ∈ M for the budget constraint to be satisfied. In Simulation 3, the pseudo-arm (K + 1) = 6 is in M, and in Simulation 4 arm 5 is in N .

For d ∈ R, we define the KL-UCB d algorithm as the instance of KL-UCB using the function f (t) = log t + d log log t. Note that the use of both KL-UCB 3 and KL-UCB 1 are theoretically justified by the results of Theorems 6 and 7, as Bernoulli distributions satisfy the conditions of both theorems. In the settings of Simulations 1 and 2, which represent multiple-play bandit instances as B is an integer in [1, K] and the cost of pulling each arm is one, we compare Thompson sampling and KL-UCB to the ESCB algorithm of Combes et al. [2015b]. As quickly explained earlier, ESCB is a generalization of the KL-UCB algorithm, designed for the combinatorial semi-bandit setting (that includes multiple-play). This algorithm computes an upper confidence bound for the sum of the arm means for each of the K B candidate sets S, defined by the optimal value to sup

(µ1,...,µ K )∈[0,1] K a∈S µ K subject to a∈S N a (t) KL (μ a (t), µ a ) ≤ f (t) ( 19
)
and draws the arms in the set S with the maximal index. Figure 1 displays the regret of the four algorithms with theoretical guarantees. All but ESCB 4B have been proven to be asymptotically optimal, and thus are guaranteed to achieve the theoretical lower bound asymptotically. In our finite sample simulation, Thompson sampling performs better than this theoretical guarantee may suggest (the regret lower bounds at time T = 100 000 are approximately equal to 150 and 45 in Simulations 1 and 2, respectively). Indeed, Thompson sampling outperforms the KL-UCB algorithms in all but Simulation 4, while KL-UCB 1 outperforms KL-UCB 3 and KL-UCB 3 outperforms ESCB 4B in Simulations 1 and 2. To give the reader intuition on the relative performance of KL-UCB variants, note that in the proofs of Theorems 6 and 7 we prove that the number of pulls on each suboptimal arm a is upper bounded by f (T )/ K inf (ν a , c a ρ ) + o(log T ), with an explicit finite sample constant for the o(log T ) term. While f (T ) = log T + o(log T ) for KL-UCB 1 and KL-UCB 3, for finite T the quantities log T and log T +c log log T , c = 1, 3, are quite different. At T = 10 5 , log T +log log T is 20% larger than log T , and log T +3 log log T is 60% larger. This difference does not decay quickly with sample size: at T = 10 15 , these two quantities are still respectively 10% and 30% larger than log T . This makes clear the practical benefit to choosing f (t) as close to log t as is theoretically justifiable: for Bernoullis, the choice of f (t) in Theorem 7 yields much better results than the choice of f (t) in Theorem 6.

We also compared the performance of KL-UCB 0 and ESCB 0 in Simulations 1 and 2 (details omitted here, but the exact results of this simulation are given in Figure 2 of the earlier technical report [START_REF] Luedtke | Asymptotically Optimal Algorithms for Multiple Play Bandits with Partial Feedback[END_REF]. Though not theoretically justified, this choice of f (t) = log t has been used quite a lot in practice. The ordering of the three algorithms is the same in Simulations 1 and 2: Thompson Sampling performs best while ESCB 0 slightly outperforms KL-UCB 0. This should however be mitigated by the gap of numerical complexity between the two algorithms, especially when B and K are large and B/K is not close to 0 or 1: while KL-UCB only requires running K univariate root-finding procedures regardless of B, the current proposed ESCB algorithm requires running K B univariate root-finding procedures. For K = 100 and B = 10, this is a difference of running 100 root-finding procedures versus more than 10 13 of them. Figure 2 displays the number of optimal and suboptimal arm draws in Simulation 4. None of the algorithms pulled the arm in N (arm 5) often. Thompson Sampling pulled the indifference point pseudoarm surprisingly often in the first 10 3 draws, and as a result arm 3 (above the margin) was also not pulled as often as would be expected in these early draws. By time 10 4 , the regret of Thompson sampling appears to have stabilized, and soon outperforms that of the two KL-UCB algorithms. We also checked what would happen if the indifference point were increased from 0.4 to 0.45 (details not shown). In this case, it takes even longer for the algorithm to differentiate between arm 3 (with ρ 3 = 0.5) and the pseudo-arm, though by time 10 5 the algorithm again appears to have succeeded in learning that pulling arm 3 is to be preferred over pulling the peudo-arm.

Proofs of Optimality of KL-UCB and Thompson Sampling

We now outline our proofs of optimality for the KL-UCB and Thompson sampling schemes. We break this section into three subsections. Section 6.1 establishes that the arms in N , i.e. the suboptimal arms, are not pulled often (satisfy Equations 11 and 12). Due to the differences in proof methods, we consider the KL-UCB and Thompson sampling schemes separately in this subsection. Section 6.2 justifies that when ρ > ρ, the budget constraint is most often saturated, that is the third term in the regret is negligible. Finally Section 6.3 establishes that the arms in L, i.e. the optimal arms away from the margin, are pulled often (satisfy Equation 13). We give the outline of the proofs for the KL-UCB and Thompson sampling schemes simultaneously, though we provide the detailed arguments separately in Appendices C and D, respectively. We note that the order of presentation of the two subsections is important: the arguments used in Section 6.3 rely on the validity of ( 11) and ( 12), which is established in Section 6.1.

To ease the presentation, we find it convenient to consider the extended bandit model presented in Section 2.2, in which a pseudo-arm K + 1 of cost B is added to the bandit instance, with a positive probability of pulling arm K + 1 representing the decision not to spend the entire budget on pulling arms 1, . . . , K. Though both the KL-UCB and Thompson Sampling algorithms were presented without this extra arm, we already noted that for each t, q K+1 (t) = 1 -1 B K a=1 c a q a (t). The UCB index U K+1 (t) and posterior draw θ K+1 (t) for arm K + 1 are both equal to Bρ for all t. For the sake of condensing notation in our study of (expected) regret, it will be convenient to consider a hypothetical scenario in which arm K + 1 is pulled with probability q K+1 (t) at each time point, even though the outcome of these pulls has no effect on the behavior of the algorithms.

Suboptimal arms not pulled often

In this section, we establish ( 11) and ( 12) for KL-UCB and Thompson Sampling.

For a fixed arm a, the KL-UCB and Thompson sampling proofs will both rely on a quantity ρ † ∈ (ρ a , µ + /c a ), though we note that the value that we select for ρ † will vary between the proofs.

KL-UCB

Preliminary: a general analysis. We start by giving a general analysis of KL-UCB in our setting, and then use it to prove Theorems 6 and 7. Fix a ∈ N \{K + 1}. The arguments in this section generalize those given in Cappé et al. [2013a,b] for the case where one arm is drawn at each time point and there is no budget constraint. Let µ † ∈ (µ a , µ + ) be some real number. If a ∈ N , then we will choose µ † = c a ρ . If, on the other hand, a ∈ N , then we will choose µ † to be less than µ + . Let ρ † be a constant that is either equal to or slightly less than µ † /c a . Below we take minimums over a ∈ S ≡ (L ∪ M)\{K + 1}: if S = ∅, then we take these minimums to be equal to negative infinity. When we later take sums over a ∈ S, we let empty sums equal zero.

We now establish that, for all t ≥ K,

a ∈ Â(t + 1) ⊆ ∪ a ∈S c a ρ † ≥ U a (t) ∪ a ∈ Â(t + 1), c a ρ † < U a (t) . ( 20
)
We separately handle the cases that ρ > ρ and ρ = ρ. If ρ > ρ, playing all of the arms in S would spend at least the allotted budget B. Hence, on the event ∀a ∈ S, U a (t)/c a > ρ † , it holds that ρ (t) > ρ † . If moreover a ∈ Â(t + 1), one has U a (t) ≥ c a ρ (t) > c a ρ † . If ρ = ρ , it holds that {a ∈ Â(t + 1)} ⊆ {a ∈ Â(t + 1), c a ρ † < U a (t)}. Indeed, if ρ (t) > ρ the algorithm only pulls arms a if U a (t) ≥ ρ (t)c a > ρc a and if ρ (t) = ρ, then the algorithm only pulls arm a if U a (t) > c a ρ, see Footnote [3]. As ρ † is smaller or equal to ρ = ρ, it follows that U a (t) > c a ρ † in both cases.

For each ζ > 0 and μ < µ + , we now introduce the set C μ,ζ . In the setting of Theorem 6,

C μ,ζ ≡ ν : Support[ν ] ⊆ Ī ∩ {ν : ∃ µ ∈ (μ, µ + ] with KL(E(ν ), µ) ≤ ζ} ,
where above KL(E(ν ), µ) is the KL-divergence in the canonical exponential family E. In the setting of Theorem 7,

C μ,ζ ≡ {ν : Support[ν ] ⊆ [0, 1]} ∩ {ν : ∃ ν ∈ B with μ < E(ν) and KL(Π D (ν ), ν) ≤ ζ} .
In both settings, we will invoke this set at μ = c a ρ † < µ + . The set C μ,ζ is defined in both settings so that μ < U a (t) if and only if νa (t

) ∈ C μ,f (t)/Na(t) . Recalling that E[N a (T )] = T -1 t=0 P{a ∈ A(t + 1)}, a union bound gives E[N a (T )] ≤ 1 + a ∈S T -1 t=K P c a ρ † ≥ U a (t) + T -1 t=K P a ∈ Â(t + 1), νa,Na(t) ∈ C caρ † ,f (t)/Na(t) .
In analogue to Equation 8 in Cappé et al. [2013a], the above rightmost term satisfies

T -1 t=K P a ∈ Â(t + 1), νa,Na(t) ∈ C caρ † ,f (t)/Na(t) ≤ T -1 t=K P a ∈ Â(t + 1), νa,Na(t) ∈ C caρ † ,f (T )/Na(t) = T -1 t=K T -K+1 n=2 P νa,n-1 ∈ C caρ † ,f (T )/(n-1) , τ a,n = t + 1 (21) ≤ T -K n=1 P νa,n ∈ C caρ † ,f (T )/n ,
where the final inequality holds because, for each n, τ a,n = t + 1 for at most one t in {K, . . . , T -1}. We will upper bound the terms with n = 1, . . . , b a (T ) in the sum on the right by 1, where

b a (T ) ≡ f (T ) K inf (ν a , µ † ) ≤ f (T ) K inf (ν a , µ † ) + 1.
This gives the bound

T -K n=1 P νa,n ∈ C caρ † ,f (T )/n ≤ f (T ) K inf (ν a , µ † ) + 1 + ∞ n=b a (T )+1 P νa,n ∈ C caρ † ,f (T )/n .
Hence,

E[N a (T )] ≤ f (T ) K inf (ν a , µ † ) + ∞ n=b a (T )+1 P νa,n ∈ C caρ † ,f (T )/n Term 1 + a ∈S T -1 t=K P c a ρ † ≥ U a (t) Term 2a
+2. ( 22)

Up until this point we have not committed to any particular choice of µ † , ρ † , or non-decreasing function f : N → R. We now give proofs of ( 11) and ( 12) in the settings of Theorems 6 and 7. For each proof we use the choice of f from the theorem statement and make particular choices of µ † and ρ † .

Lemma 9. Eq. 11 holds in the settings of Theorems 6 and 7

Proof. Fix a ∈ N \{K + 1}. If a ∈ N , then let µ † = c a ρ and, if a ∈ N , then let µ † ∈ (µ a , µ + ). In the setting of Theorem 6 let ρ † = µ † /c a and in the setting of Theorem 7 let ρ † = 1log(T ) -1/5 µ † /c a . Lemma A.1 shows that Term 1 is o(log T ) and includes references on where to find an explicit finite sample upper bound, where this upper bound will rely on the choice of

µ † < µ + if a ∈ N . Fix a ∈ S.
Noting that ρ † ≤ 1log(T ) -1/5 ρ a (Theorem 6) and ρ † ≤ ρ a (Theorem 7), Term 2a is o(log T ) in both settings by Lemma A.2, with an exact finite sample upper bound given in the proof thereof. Thus, a ∈S Term 2a = o(log T ). This completes the proof of (11). Lemma 10. Eq. 12 holds in the settings of Theorems 6 and 7

Proof. For a ∈ N , so far we have established that, for arbitrary µ † ∈ (µ a , µ + ),

E[N a (T )] ≤ log T K inf (ν a , µ † ) + r(T, µ † ),
where r(T, µ † )/ log T → 0 for fixed µ † . As this holds for every µ † , there exists a sequence µ † (T ) → µ + such that r(T, µ † (T ))/ log T → 0. In both settings lim inf µ † →µ+ K inf (ν a , µ † ) = +∞, and so using this µ † (T ) sequence shows that E[N a (T )] = o(log T ).

Thompson Sampling

This proof is inspired by the analysis of Thompson sampling proposed by Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF]. We work with a suboptimal arm a ∈ N \{K + 1} in most of this section, though we state one of the results (Lemma 11) for general arms a ∈ {1, . . . , K + 1} since it will prove useful later. We will let ρ † and ρ ‡ be numbers (to be specified later) satisfying ρ a < ρ † < ρ ‡ < 1/c a . Observe that a ∈ Â(t + 1) equals

a ∈ Â(t + 1), θ a (t) ≤ c a ρ ‡ ∪ a ∈ Â(t + 1), θ a (t) > c a ρ ‡ ⊆ ∪ a ∈L∪M a ∈ Â(t + 1), θ a (t) ≤ c a ρ ‡ , θ a (t) ≤ c a ρ ∪ a ∈ Â(t + 1), θ a (t) > c a ρ ‡ .
By the absolute continuity of the beta distribution, with probability one at most one a ∈ {1, . . . , K + 1} satisfies θ a (t) = c a ρ , and hence, conditional on F(t), the leading event above is almost surely equivalent to the event

∪ a ∈L∪M a ∈ Â(t + 1), θ a (t) ≤ c a ρ ‡ , θ a (t) < c a ρ .
If K + 1 ∈ M, then the fact that a ∈ Â(t + 1) implies that θ a (t)/c a (t) ≥ ρ (t) shows that the event in the union above at a = K + 1 never occurs, since on this event ρ K+1 = θ K+1 (t)/c K+1 < ρ ‡ , which contradicts our choice that ρ ‡ < ρ = ρ K+1 . Hence, the union above can be taken over S regardless of whether or not K + 1 ∈ M. Furthermore,

a ∈ Â(t + 1), θ a (t) > c a ρ ‡ ⊆ a ∈ Â(t + 1), θ a (t) > c a ρ ‡ , μa (t) ≤ c a ρ † ∪ a ∈ Â(t + 1), μa (t) > c a ρ † .

Recalling that E[N a (T )] =

T -1 t=0 P a ∈ Â(t + 1) ,

E[N a (T )] ≤ a ∈S T -1 t=0 P a ∈ Â(t + 1), θ a (t) ≤ c a ρ ‡ , θ a (t) < c a ρ Term Ia + T -1 t=0 P a ∈ Â(t + 1), θ a (t) > c a ρ ‡ , μa (t) ≤ c a ρ † Term II + T -1 t=0 P a ∈ Â(t + 1), μa (t) > c a ρ † Term III . ( 23
)
The above decomposition does not depend on the algorithm. Bounding Terms Ia , a ∈ S, and Term II will rely on arguments that are specific to Thompson Sampling. Fix a ∈ S and let p ρ ‡ a (t

) ≡ P(θ a (t) > c a ρ ‡ | F(t)). Note that p ρ ‡ a (t) = p ρ ‡ a (t+1) implies a ∈ Â(t+1). Thus p ρ ‡ a (t) is equal to p ρ ‡ a ,n ≡ p ρ ‡ a (τ a ,n
) for all t such that N a (t) = n. We now state Lemma 11, that generalizes Lemma 1 in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF].

Lemma 11. If a ∈ {1, . . . , K + 1}, a ∈ S, and ρ ‡ satisfies c a ρ ‡ < 1, then, for all t ≥ 0,

P a ∈ Â(t + 1), θ a (t) ≤ c a ρ ‡ , θ a (t) < c a ρ F(t) ≤ 1 -p ρ ‡ a (t) p ρ ‡ a (t) P ( θ a (t)/c a ≥ ρ (t)| F(t)) .
The proof can be found in Appendix D. Observe that the upper bound in the above lemma does not rely on a. We have another lemma, that relies on a lower bound on the probability qa , to be defined shortly, that is possible for q a (t) given that θ a (t)/c a ≥ ρ (t). By the absolute continuity of the beta distribution, we also have that

P a ∈ Â(t + 1) F(t) = P a ∈ Â(t + 1), θ a (t) c a ≥ ρ (t) F(t) = P a ∈ Â(t + 1) θ a (t) c a ≥ ρ (t), F(t) P θ a (t) c a ≥ ρ (t) F(t) .
We lower bound the leading term in the product on the right by qa ≡ min 1, min H⊆{1,...,K}\{a }:

ã∈H cã<B B -ã∈H c ã c a .
Because c K+1 = B, one could equivalently take the minimum over H ⊆ {1, . . . , K + 1}\{a }. To see that this is a lower bound, consider two cases. If θ a (t)/c a > ρ (t), then a ∈ Â(t + 1) with probability one, and so the above is a lower bound. If θ a (t)/c a = ρ (t), then the numerator B -ã∈H c ã of the inner minimum (over H) above represents the minimum possible amount of remaining budget when arm a is the unique arm on the estimated margin. The estimated margin is almost surely (over the draws of θ(t)) singleton. Clearly, qa > 0. As a consequence,,

P θ a (t) c a ≥ ρ (t) F(t) ≤ q-1 a P a ∈ Â(t + 1) F(t) . (24)
We have the following lemma, whose proof can be found in Appendix D.

Lemma 12. If a ∈ S and c a ρ ‡ < 1, then, for all t ≥ 0,

E T -1 t=0 1 -p ρ ‡ a (t) p ρ ‡ a (t) P ( θ a (t)/c a ≥ ρ (t)| F(t)) ≤ q-1 a E T -1 n=0 1 -p ρ ‡ a ,n p ρ ‡ a ,n
.

Combining the two preceding lemmas yield the inequality

Term Ia ≤ q-1 a E T -1 n=0 1 -p ρ ‡ a ,n p ρ ‡ a ,n . (25)
Note crucially that we have upper bounded the sum over time on the left-hand side by a sum over the number of pulls of arm a on the right-hand side. There appears to be a steep price to pay for this transfer from a sum over time to a sum over counts: the right-hand side inverse weights by a conditional probability, which may be small for certain realizations of the data. Lemma 2 in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF], that we restate below using our modified notation, establishes that this inverse weighting does not cause a problem for Thompson sampling with Bernoulli rewards and independent beta priors. If ρ ‡ < ρ , then the proceeding lemma implies that, for each a ∈ S, Term Ia is O(1), i.e. is o(log T ) with much to spare. Obviously, this implies that a ∈S Term Ia = o(log T ) as well.

Lemma 13 (Lemma 2 from Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF]. If a ∈ S and ρ ‡ < ρ a , then, with

∆ ≡ µ a -c a ρ ‡ , E 1 -p ρ ‡ a ,n p ρ ‡ a ,n = 3 ∆ , for n < 8 ∆ Θ e -∆ 2 n/2 + 1 (n+1)∆ 2 e -KL(c a ρ ‡ ,µ a )n + 1 exp(∆ 2 n/4)-1 , for n ≥ 8 ∆ .
Above Θ(•) is used to represent big-Theta notation.

We now turn to Term II. The following result mimics Lemma 4 in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF], and is a consequence of the close link between beta and binomial distributions and the Chernoff-Hoeffding bound. We provide a proof of this result in Appendix D.

Lemma 14. If a ∈ (M ∪ N )\{K + 1} and ρ a < ρ † < ρ ‡ , where c a ρ ‡ < 1, then

Term II ≡ T -1 t=0 P a ∈ Â(t + 1), θ a (t) > c a ρ ‡ , μa (t) ≤ c a ρ † ≤ log T KL(c a ρ † , c a ρ ‡ )
.

We now turn to Term III. Note that

Term III = E T -1 t=0 1 a ∈ Â(t + 1), μa,Na(t) > c a ρ † = E T -1 t=0 T -1 n=0 1 τ a,n+1 = t + 1, μa,n > c a ρ † ≤ T -1 n=0 P μa,n > c a ρ † , ( 26
)
where the latter inequality holds because τ a,n+1 = t + 1 for at most one t in {0, . . . , T -1}. The following lemma controls the right-hand side of the above.

Lemma 15. Fix an arm a ∈ {1, . . . , K}. If ρ † > ρ a and c a ρ † < 1, then

T -1 n=0 P μa,n > c a ρ † ≤ 1 + 1 KL(c a ρ † , µ a )
.

The proof is omitted, but is an immediate consequence of the Chernoff-Hoeffding bound and the additional bounding from the proof of Lemma 3 in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF]. Thus we have shown that Term III is o(log T ), with much to spare as well.

The proof of ( 11) and ( 12) in the setting of Theorem 8 is now straightforward.

Lemma 16. Eq. 11 holds in the setting of Theorem 8.

Proof. Fix a ∈ N \{K + 1}. Let µ † = c a ρ if a ∈ N , and let µ † be slightly less than µ + if a ∈ N . Fix ρ † < ρ ‡ and ρ ‡ (to be specified shortly) so that ρ a < ρ † < ρ ‡ < µ † /c a and ∈ (0, 1] a constant. Plugging our results on each Term Ia and on Terms II and III into (23) then yields that

E [N a (T )] ≤ log T KL(c a ρ † , c a ρ ‡ ) + 1 + 1 KL(c a ρ † , µ a ) + O(1). Select ρ † so that KL(c a ρ † , µ † ) = KL(µa,µ † ) 1+ and ρ ‡ so that KL(c a ρ † , c a ρ ‡ ) = KL(caρ † ,µ † ) 1+
, since this gives

KL(c a ρ † , c a ρ ‡ ) = KL(µa,µ † ) (1+ ) 2 . Hence, E[N a (T )] ≤ (1 + ) 2 f (T ) KL(µ a , µ † ) + r(T, µ † ),
where r(T, µ † )/ log T → 0 for fixed µ † .

Lemma 17. Eq. 12 holds in the setting of Theorem 8.

Proof. If a ∈ N , then dividing both sides by log T , and then taking T → ∞ followed by → 0 gives (11). If, on the other hand, a ∈ N , then we use that there exists a sequence µ † (T ) such that r(T, µ † (T ))/ log T → 0. Because lim inf µ † →µ+ = +∞, then dividing both sides by log T , taking the limit as T → ∞, followed by → 0, gives (12) in the case where a ∈ N .

Budget saturation when ρ > ρ

Assuming ρ > ρ, we prove ( 14) for KL-UCB and Thompson Sampling in the setting of Theorems 6 and 7 and Theorem 8 respectively. Recall that the third term in the regret decomposition ( 6) can be expressed in terms of the number of draws of the supplementary arm K + 1 in the extended bandit model:

BT - K a=1 c a E ν [N a (T )] = BE[N K+1 (T )].
We prove below for each algorithm that E[N K+1 (T )] = o(log(T )), as a by product from specific elements already established when controlling the number of suboptimal draws.

KL-UCB

For any ρ † ∈ (ρ, ρ ] and any t ≥ K, it holds that, for T large enough,

K + 1 ∈ Â(t + 1) ⊆ a ∈S {c a ρ ≥ U a (t)} ⊆ a ∈S c a ρ † ≥ U a (t) .
The first inclusion must hold because if all the arms in S had satisfied U a /c a ≥ ρ, then including all of those arms in Â(t + 1) would have been enough to saturate the budget and K + 1 would not have been selected. The second inclusion holds because ρ † > ρ. Hence, E[N K+1 (T )] ≤ a ∈S Term 2a (see Equation 22for its definition). This condition is always satisfied by the choice ρ † = ρ that we have used in the setting of Theorem 6, and it holds for all T sufficiently large for the choice ρ † = 1log(T ) -1/5 ρ that we have used in the setting of Theorem 7. Lemma A.2 shows that each Term 2a is again o(log T ).

Thompson Sampling

We have that

{K + 1 ∈ Â(t + 1)} ⊆ a ∈S {K + 1 ∈ Â(t + 1), θ a (t) ≤ c a ρ }.
As ρ < ρ and θ K+1 (t) = c K+1 ρ with probability one, E[N a (T )] ≤ a ∈S Term Ia provided ρ † ∈ (ρ, ρ ) (see Equation 23for its definition). Thus, we can invoke Lemma 11 (that holds for a = K + 1), followed by Lemmas 12 and 13, to show that E[N K+1 (T )] = O(1), and therefore is o(log T ) with much to spare.

Optimal arms away from margin pulled To(log T ) times

We now show that the optimal arms away from the margin (a ∈ L) are pulled often. We start by giving an analysis that applies to any algorithm that, to decide which arms to draw at time t + 1, based on F(t) and possibly some external stochastic mechanism, defines indices I a (t), a = 1, . . . , K + 1, and then defines the threshold ρ (t) ≡ ρ (c a I a (t) : a = 1, . . . , K + 1), and, for all arms a with I a (t) = ρ (t), assigns mass q a (t) = 1{I a (t) > ρ (t)}. The arms with I a (t) = ρ (t) are assumed to be drawn so that K+1 a=1 c a q a (t) = B. We then specialize the discussion to KL-UCB and Thompson sampling, where I a (t) is respectively equal to U a (t)/c a and θ a (t)/c a . For the remainder of this section, we fix an optimal arm a ∈ L. Observe that, for t ≥ K (KL-UCB) or t ≥ 0 (Thompson sampling),

{I a (t) < ρ (t)} = ∪ a∈M∪N {I a (t) ≥ ρ (t), I a (t) < ρ (t)} = ∪ a∈(M∪N )\{K+1} {I a (t) ≥ ρ (t), I a (t) < ρ (t), I K+1 (t) < ρ (t)} ∪ {I K+1 (t) ≥ ρ (t), I a (t) < ρ (t)} .
Recalling (24), we see that, for Thompson sampling,

T -E[N a (T )] = T -E T -1 t=0 P a ∈ Â(t + 1) F(t) 21 = E T -1 t=0 P a ∈ Â(t + 1) F(t) ≤ E T -1 t=0 P {I a (t) < ρ (t)|F(t)} ≤ a∈(M∪N )\{K+1} T -1 t=0 P {I a (t) ≥ ρ (t), I a (t) < ρ (t), I K+1 (t) < ρ (t)} + T -1 t=0 P {I K+1 (t) ≥ ρ (t), I a (t) < ρ (t)} , (27)
where the first inequality holds because {a ∈ Â(t + 1)} ⊆ {I a (t) < ρ (t)} and the second inequality holds by the preceding display. We have a similar identity for KL-UCB, though the identity is slightly different due to the initiation of each of the K arms. Specifically,

T -K + 1 -E[N a (T )] ≤ a∈(M∪N )\{K+1} T -1 t=0 P {I a (t) ≥ ρ (t), I a (t) < ρ (t), I K+1 (t) < ρ (t)} + T -1 t=0 P {I K+1 (t) ≥ ρ (t), I a (t) < ρ (t)} . (28)
For a ∈ M∪N , let H denote the collection of all subsets H of {1, . . . , K}\{a, a } for which ã∈H c ã < B.

For a ∈ M ∪ N , we then define Above "Thompson Sampling" and "KL-UCB" in the conditioning statements refers to which of the two algorithms is under consideration. The latter condition represents the extreme scenario where the arms in ã ∈ H have I ã(t) > ρ (t), whereas the arms ã outside of H ∪ {a , K + 1} have I ã(t) = ρ (t). One can verify that qa a > 0. Similarly to (24), for each a ∈ (M ∪ N )\{K + 1} and t ≥ K (KL-UCB) or t ≥ 0 (Thompson sampling),

P {I a (t) ≥ ρ (t), I a (t) < ρ (t), I K+1 (t) < ρ (t)|F(t)} ≤ 1 qa a P a ∈ Â(t + 1), I a (t) < ρ (t) F(t) ,
and thus

T -1 t=0 P {I a (t) ≥ ρ (t), I a (t) < ρ (t), I K+1 (t) < ρ (t)} ≤ 1 qa a T -1 t=0 P a ∈ Â(t + 1), I a (t) < ρ (t) .
For a = K + 1, we similarly have

T -1 t=0 P {I K+1 (t) ≥ ρ (t), I a (t) < ρ (t)} ≤ 1 qa a T -1 t=0 P a ∈ Â(t + 1), I a (t) < ρ (t) .
For each a ∈ M ∪ N , let

M a a (T ) ≡ T -1 t=0 1{a ∈ Â(t + 1), I a (t) < ρ (t)}.
The bounds ( 28) and ( 27) yield the key observation that we use in this section:

for KL-UCB:

T -K + 1 -E[N a (T )] ≤ a∈M∪N 1 qa a E[M a a (T )];
for Thompson sampling:

T -E[N a (T )] ≤ a∈M∪N 1 qa a E[M a a (T )]. (29)
We note that, for most models D K , there will generally not be a positive lower bound on qa a uniformly over distributions V in D K , where we note that the dependence of qa a on V is suppressed in the notation. Therefore, on the one hand, if one were pursuing a worst-case analysis of the regret of our algorithms, where the maximal regret is studied over all V ∈ D, then it would typically not be possible to control the right-hand sides above. On the other hand, in our setting, in which we study the regret at a fixed V, it is true that qa a > 0, and so one can control the right-hand sides above provided they can control E[M a a (T )] for arms a ∈ M ∪ N . In what follows, we will show that we can indeed control E[M a a (T )] for these arms.

Let G be some integer in [0, +∞( and δ ∈ (0, 1) be a constant to be specified shortly. For convenience, we let T (g) ≡ T (1-δ) g for g ∈ N. We also define

U ≡ {a ∈ (M ∪ N )\{K + 1} : c a ρ a ≥ µ + } , U ≡ {a ∈ (M ∪ N )\{K + 1} : c a ρ a < µ + } ,
where we note that U ∪ U = (M ∪ N )\{K + 1}. Our analysis relies on the following bound (for which we provide the arguments below):

a∈M∪N E[M a a (T )] ≤ E[N K+1 (T )] + a∈U E[M a a (T )] + a∈U E[M a a (T )] = o(log T ) + a∈U E[M a a (T )] + a∈U E[M a a (T (G) )] Term A + G g=1 a∈U E[M a a (T (g-1) ) -M a a (T (g) )] Term B . (30)
The inequality uses that E[M a K+1 (T )] ≤ E[N K+1 (T )], and the equality holds using (i) a telescoping series and (ii) the fact that the algorithm achieves (12): indeed, this was proven for both KL-UCB and Thompson sampling in Section 6.2.

We now present the key ingredients to bound Term A and B. Each lemma stated below holds for both KL-UCB in the settings of Theorems 6 and 7 and for Thompson sampling in the setting of Theorem 8. Though these lemmas hold for both algorithms, the methods of proof for KL-UCB and for Thompson sampling are quite different. Thus we give the proofs of the lemmas in the settings of Theorems 6 and 7 in Appendix C and the proofs in the setting of Theorem 8 in Appendix D.

Lemma 18. In the settings of Theorem 6, 7, and 8, E[M a a (T )] = o(log T ) for a ∈ U and, for fixed

G ≥ 0, E[M a a (T (G) )] ≤ (1 -δ) G log T K inf (ν a , c a ρ a )
for a ∈ U. As a consequence,

Term A ≤ (1 -δ) G a∈U log T K inf (ν a , c a ρ a ) + o(log T ).
The proof of Lemma 18 borrows a lot from the proofs of ( 11) and ( 12) for each algorithm. Controlling Term B relies on a careful choice of δ > 0, which is specified in Lemma 19 below. The proof of this lemma is highly original: indeed we first prove that the considered algorithm is uniformly efficient, which allows to exploit the lower bound (8) given in Theorem 5. Its proof is provided in the appendix for both KL-UCB and Thompson Sampling, and we sketch it below.

Lemma 19. Let d ∈ (0, 1) and δ chosen such

δ = d 1 -max a∈N ∩U K inf (ν a , c a ρ ) K inf (ν a , c a ρ a ) 1/2 , ( 31
)
and δ = d if N ∩ U = ∅.
Then in the setting of Theorems 6, 7, and 8, Term B is o(log T ).

Sketch of proof of Lemma 19. We first show that the algorithms are uniformly efficient in the sense defined in Section 3. This result is an immediate consequence of the results in Section 6.1, which show that the arms in N \{K + 1} are not pulled too often, plus the preliminary results in this section, which show that arms in L are pulled often.

Lemma 20. KL-UCB is uniformly efficient in the settings of Theorems 6 and 7 and Thompson sampling is uniformly efficient in the setting of Theorem 8.

Proof. Fix an arbitrary reward distribution V. By by Lemma 18 and the already proven ( 11) and ( 12) in the settings of Theorems 6, 7, and 8 (see Lemmas 9, 10, 16, and 17), both of which hold for V,

T -E V [N a (T )] ≤ a∈M∪N 1 qa a E V [M a a (T )] + O(1) ≤ o(log T ) + a∈U 1 qa a E V [M a a (T )] + a∈U 1 qa a E V [M a a (T )] + O(1)
for any a ∈ L, where the O(1) term is equal to zero for Thompson sampling and, by (29), is K -1 for KL-UCB. The right-hand side is O(log T ) by applying the results of Lemma 18 to control the sums over U and U. Section 6.1 showed that arms in N are not pulled often (at most O(log T ) times). By (6), it follows that R(T ) = O(log T ), which is o(T α ) for any α > 0.

Fix g ∈ N and an arm a ∈ N ∩ U. By the uniform efficiency of the algorithm established in Lemma 20, we will be able to apply (8) from Lemma 4 to show that N a (T (g) ) ≥ (1δ) log T (g) K inf (νa,caρ ) with probability approaching 1. For now suppose this holds almost surely (in the proofs we deal with the fact that this happens with probability approaching rather than exactly 1). Our objective will be to show that this lower bound on N a (T (g) ) suffices to ensure that M a a (T (g-1) ) -M a a (T (g) ) is o(log T ), in words that arm a is pulled while arm a is pulled with probability zero (I a (t) < ρ (t)) at most o(log T ) times from time t = T (g) , . . . , T (g-1) .

We will see that log T (g-1) K inf (νa,caρ a ) pulls of arm a by time T (g) suffices to ensure this in both settings. Using that (1δ) log T (g) ≈ (1δ) 2 log T (g-1) , it will follow that we can control the sum in Term B for each a ∈ N provided we choose δ ∈ (0, 1) so that

(1 -δ) 2 1 K inf (ν a , c a ρ ) > 1 K inf (ν a , c a ρ a ) for all a ∈ N . ( 32
)
It is easy to check to for any d ∈ (0, 1), δ as defined in Lemma 19 satisfies this inequality. Note that K inf (ν a , c a ρ a ) ≥ K inf (ν a , c a ρ ), and thus δ ∈ (0, 1). So far we have only considered suboptimal arms a ∈ N ∩ U, but the fact that, for any a ∈ M ∩ U, Lemma 4 ensures that N a (T (g) ) > log T (g) / with probability approaching 1 for any > 0 shows that a ∈ N ∩ U is indeed the harder case. Indeed, this is what we see in our proofs controlling Term B for the two algorithms.

We now conclude the analysis. Combining Equations ( 29) and ( 30) with the bounds on Term A and B obtained in Lemma 18 and Lemma 19 yield, for any finite G and for the particular choice of δ ∈ (0, 1) given in ( 31)

lim sup T T -E[N a (T )] log T ≤ (1 -δ) G a∈U 1 qa a K inf (ν a , c a ρ a ) . ( 33
)
Taking G to infinity yields the result.

Conclusion

We have established the asymptotic efficiency of KL-UCB and Thompson sampling for budgeted multipleplay bandit problem in which the cost of pulling each arm is known and, in each round, the agent may use any strategy for which the expected cost is no more than their budget. We have also introduced a pseudo-arm so that the agent has the option of reserving the remainder of their budget if the remaining arms have reward-to-cost ratios that fall below a prespecified indifference point. Thompson sampling outperforms KL-UCB in three of our four simulations scenarios. Despite the strong performance of Thompson sampling for Bernoulli rewards, we have been able to prove stronger results about KL-UCB in this work, dealing with more general distributions. Understanding for which distributions one of these algorithms is preferable to the other is an interesting area for future work.

All of the proofs in this work can handle the case that the set of optimal arms is not unique. In an earlier work, [START_REF] Komiyama | Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays[END_REF] established the optimality of Thompson sampling under a multiple play bandit model in which the set of optimal arms is unique. A potential area for future work would be to extend their arguments to the special case of our budgeted bandit setting in which the set of optimal arms is unique -it would be interesting to see if their technique yields a shorter proof in this special case.

In future work, it would be interesting to consider an extension of our setting where the budget (B t ), indifference points (ρ t ), and costs (c t ) are random over time according to some exogeneous source of randomness. If only the budget is random over time, then, under some regularity conditions, the regret lower bound and regret of our algorithms would seem to be driven by the behavior of our algorithm for the fixed budget representing the upper edge of the support for the random budget, since this is the setting in which the most information is learned about the arm distributions (arms that are otherwise suboptimal can be optimal in this setting). If only the indifference point is variable over time, then the behavior of our algorithm will similarly be driven by the lowest indifference point, since the most information is available in this case. Combinations of variable budgets and indifference points will result in a similar analysis. Variable but known costs are more complex, because they have the potential to change the order and indices of the optimal arms. For sufficiently variable costs, we in fact expect that all arms will be pulled more than order log T times, since all arms will be optimal for certain cost realizations. Therefore, a careful study of a variable cost budgeted bandit problem may require very different techniques than those used in this work. The common value M of these two optimization problem, that is the maximal achievable reward, can be rearranged a bit, using that K+1 a=1 q a c a ρ = ρB:

Structure of the Supplementary Material

M = K+1 a=1
q a µ a -ρB, where q K+1 ∈ [0, 1] K+1 is the solution to

q K+1 ∈ argmax q∈[0,1] K+1 K+1 a=1 q a µ a such that K+1 a=1 q a c a = B. (A.2) Now introduce L ≡ a∈L µ a + ρ B - a∈L c a .
The optimal weights are also defined by

q K+1 ∈ argmin q ∈ [0, 1] K+1 L - K+1 a=1 q a µ a such that K+1 a=1 q a c a = B.
The new objective can be rewritten as follows, where the 'virtual' arm K + 1 that has characteristics µ K+1 = Bρ and c K+1 = B is added to either the set M (if

ρ K+1 = ρ = ρ ) or N (if ρ K+1 = ρ < ρ ). L - K+1 a=1 q a µ a = a∈L µ a + ρ B - a∈L c a - a∈L c a q a ρ a - a∈M c a q a ρ - b∈N c b q b ρ b = a∈L c a ρ a + ρ B - a∈L c a - a∈L c a q a ρ a -ρ B - a∈L c a q a - b∈N c b q b - b∈N c b q b ρ b = a∈L c a (ρ a -ρ ) >0 (1 -q a ) + b∈N c b (ρ -ρ b ) >0 q b .
This shows that the objective function is always non negative, and that it can actually be set to the zero by choosing weights that satisfy q a = 1 for all a ∈ L and q b = 0 for all b ∈ L.

It remains to justify that such a choice is indeed feasible for some choices of weights on the arms in the margin M. This margin is never empty, as in the case ρ = ρ, it does contain the 'pseudo-arm' mentioned above. By definition of the sets L and M, a∈L c a < B and a∈L∪M c a ≥ B hence, the solution can be "completed" by putting weight on the margin such that a∈L c a + a∈N q a c a = B.

If ρ < ρ , then the arm K + 1 belongs to N and as such q K+1 = 0 and the first K marginals indeed satisfy the statement of Proposition 1, with a non-empty margin. If ρ = ρ , our 'extended' margin only contains arm K + 1, while the original margin is empty. As such the only arms with non-zero weights among the first K marginals are the arms in L, for which the weight is one.

A.2 Proof of Proposition 3

Regret(T, V) = E T t=1 (G -G(t)) = E T t=1 (G - K a=1 q a (t)(µ a -c a ρ))

29

The proof follows from a rewriting of

G - K a=1 q a (t)(µ a -c a ρ) = a∈L c a ρ a + ρ B - a∈L c a -Bρ - K a=1 q a (t)(µ a -c a ρ) = a∈L c a ρ a + ρ B - a∈L c a -Bρ - K+1 a=1 q a (t)(µ a -c a ρ),
where we define µ K+1 = ρB, c K = B and let q K+1 (t) be such that K+1 a=1 q a (t)c a = B. This is possible as K a=1 q a (t)c a ≤ B due to the soft budget constraints and c K+1 = B and

q K+1 (t) = B - K a=1 c a q a (t) B .
Thus one can further write

G - K a=1 q a (t)(µ a -c a ρ) = a∈L c a ρ a + ρ B - a∈L c a - K+1 a=1 q a (t)µ a = a∈L c a ρ a + ρ B - a∈L c a - a∈L q a (t)c a ρ a -ρ a∈M q a (t)c a - a∈N q a (t)c a ρ a -q K+1 (t)ρB Using that a∈M q a (t)c a = B - a∈L q a (t)c a - a∈M q a (t)c a -q K+1 (t)B, one obtains G - K a=1 q a (t)(µ a -c a ρ) = a∈L c a (ρ a -ρ )(1 -q a (t)) + a∈N c a (ρ -ρ a )q a (t) + B(ρ -ρ)q K+1 (t) = a∈L c a (ρ a -ρ )(1 -q a (t)) + a∈N c a (ρ -ρ a )q a (t) + (ρ -ρ) B - K a=1 c a q a (t)
Summing over t, the regret can be decomposed as

a∈L c a (ρ a -ρ ) T -E T t=1 q a (t) + a∈N c a (ρ -ρ a )E T t=1 q a (t) + (ρ -ρ) B - K a=1 c a E T t=1 q a (t)
and the conclusion follows by noting that N a (T ) = E T a=1 q a (t) .

B Proof of Lower Bound on Suboptimal Arm Draws

Proof of Lemma 4. Fix some arm a ∈ (M∪N )\{K +1}, natural number T , and δ ∈ (0, 1). By definition, c a ρ < µ + for all a ∈ N , and, for a ∈ M the same property holds by our assumption that c a ρ = µ a < µ + . Hence, the set {ν a ∈ D : E(ν a ) > c a ρ } is non-empty. If the intersection of this set with the set of distributions {ν a ∈ D : ν a νa } is empty, then the bounds are trivial by our convention that d/∞ = 0 for finite d. Otherwise, let V be some distribution that is equal to V except in the a th component, where its a th component ν a ∈ D is such that µ a ≡ E(ν a ) > c a ρ and ν a ν a . Furthermore, one can select V to fall in the statistical model for the joint distribution of the arm-specific rewards by our variation-independence assumption. For each b, let ρ b = ρ b , b = a, and let ρ a = µ a /c a . Observe that µ a > c a ρ ≥ µ a implies that KL(ν a , ν a ) > 0. Define the log-likelihood ratio random variable L a (T ) ≡ L a,Na(T ) ≡ Na(T ) n=1 log dνa dν a (X a,n ). Let b a (T ) ≡ (1δ) log T KL(νa,ν a ) and d(T ) ≡ (1δ/2) log T . We have that

P V {N a (T ) < b a (T )} ≤ P V {N a (T ) < b a (T ), L a (T ) ≤ d(T )} + P V {N a (T ) < b a (T ), L a (T ) > d(T )} ≤ e d(T ) P V {N a (T ) < b a (T )} + P V {N a (T ) < b a (T ), L a (T ) > d(T )} , (A.3)
where the final inequality holds because, for any event D ⊆ {N a (T ) = b, L a (T ) ≤ d(T )}, a change of measure shows that P V {D} = E V e L a,b 1 {D} ≤ e d(T ) P V {D} [see Equation 2.6 in [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF]. Let ρ ≡ ρ (c a ρ a : a = 1, . . . , K + 1). Observe that arm a under the reward distribution involving a satisfies either (i) ρ a > ρ or (ii) ρ a = ρ and g a ≡ Bã =a:ρã≥ ρ c ã > 0, where the sum over the empty set is zero. Under (i), we note that the uniform efficiency of the algorithm and Markov's inequality yield that

P V {N a (T ) < b a (T )} = P V {T -N a (T ) > T -b a (T )} = o T δ/2-1 .
Thus, the first term in (A.3) converges to zero as T → ∞ when (i) holds. We now show the same result when (ii) holds. We first note that

g a T -c a E[N a (T )] ≥ BT - ã =a:ρã≥ ρ c ã E[N ã(T )] -c a E[N a (T )] = BT - ã:ρã≥ ρ c ã E[N ã(T )].
The right-hand side is o(T δ/2 ) by the uniform efficiency of the algorithm. Hence, Markov's inequality yields that,

P V {N a (T ) < b a (T )} = P V {g a T -c a N a (T ) > g a T -c a b a (T )} = o T δ/2-1 .
Thus, the first term in (A.3) also converges to zero as T → ∞ when (ii) holds. For the second term, observe that

{N a (T ) < b a (T ), L a (T ) > d(T )} ⊆ max n≤ba(T ) L a,n b a (T ) > d(T ) b a (T ) = max n≤ba(T ) L a,n b a (T ) > 1 -δ/2 1 -δ KL(ν a , ν a ) > KL(ν a , ν a ) .
By the strong law of large numbers, b a (T ) -1 L a, ba(T ) → KL(ν a , ν a ) almost surely under ν a . Further, max n≤ba(T ) b a (T ) -1 L a,n → KL(ν a , ν a ) almost surely as T → ∞. It follows that the second term in (A.3) converges to zero as T → ∞ so that

P V N a (T ) < (1 -δ) log(T ) KL(ν a , ν a ) → 0. (A.4)
For convenience, we let K ≡ K inf (ν a , c a ρ ) in what follows. By the definition of the infimum, for every > 0 there exists some ν a such that K + > KL(ν a , ν a ). This proves (8). If a ∈ N so that K > 0, then take = (1δ) -1/2 -1 K and write

P V N a (T ) < (1 -δ) 3/2 log(T ) K inf (ν a , c a ρ ) → 0.
Applying the above to δ = 1 -(1δ) 2/3 (such that (1δ ) 3/2 = (1δ)) yield the result for a ∈ N . For a ∈ N , it also follows that for all δ ∈ (0, 1) one has

E[N a (T )] ≥ (1 -δ) log T K inf (ν a , c a ρ ) P V N a (T ) ≥ (1 -δ) log T K inf (ν a , c a ρ ) ∼ T →∞ (1 -δ) log T K inf (ν a , c a ρ ) ,
which yields (9), letting δ go to zero.

C Supplementary Proofs for KL-UCB

Lemma A.1. Fix an a ∈ {1, . . . , K} and a fixed µ † (not relying on T ) with µ a < µ † . In the setting of Theorem 6 with ρ † = µ † /c a or in the setting of Theorem 7 with ρ † = 1log(T ) -1/5 µ † /c a , it holds that

∞ n=b(T )+1 P νa,n ∈ C caρ † ,f (T )/n = o(log T ), where b(T ) is any number satisfying b(T ) ≥ f (T ) K inf (ν a , µ † )
.

An explicit finite sample bound on the o(log T ) term can be found in Cappé et al. [2013b].

Proof. In the setting of Theorem 6, Equation 25in Cappé et al. [2013b] gives result for ρ † = µ † /c a . We refer the readers to that equation for the explicit finite sample bound that we are summarizing with little-oh notation.

In the setting of Theorem 7, Equation 33 combined with the unnumbered equation preceding Equation 36in Section B.4 of Cappé et al. [2013b] gives the result for ρ † = 1log(T ) -1/5 µ † /c a . An explicit finite sample upper bound on this quantity can be found in Section B.4 of Cappé et al. [2013b].

Lemma A.2. Fix an arm a ∈ S. In the setting of Theorem 6 with ρ † ≤ ρ a or in the setting of Theorem 7 with ρ † ≤ 1log(T ) -1/5 ρ a , it holds that

T -1 t=K P c a ρ † ≥ U a (t) = o(log T ).
Explicit finite sample constants can be found in the proof.

Proof. In the setting of Theorem 6, it holds that {c a ρ † ≥ U a (t)} ⊆ {µ a ≥ U a (t)}. Hence,

T -1 t=K P c a ρ † ≥ U a (t) ≤ T -1 t=K P{µ a ≥ U a (t)}. Furthermore, {µ a ≥ U a (t)} ⊆ t-K+1 n=1 µ a ≥ μa ,n , KL(μ a ,n , µ a ) ≥ f (t) n .
Using the above, Equations 17 and 18 in Cappé et al. [2013b] show that

T -1 t=K P{µ a ≥ U a (t)} is upper bounded by 3 + 4e log log T = o(log T ) provided T ≥ 3.
In the setting of Theorem 7, it holds that {c a

ρ † ≥ U a (t)} ⊆ { 1 -log(T ) -1/5 µ a ≥ U a (t)}. Hence, T -1 t=K P c a ρ † ≥ U a (t) ≤ T -1 t=K P 1 -log(T ) -1/5 µ a ≥ U a (t) . (A.5)
Let ≡ log(T ) -1/5 µ a > 0. Arguments given in Section B.2 of Cappé et al. [2013b] show that

{µ a -≥ U a (t)} ⊆ K inf (ν a (t), µ a -) ≥ f (t) N a (t) ⊆ K inf (ν a (t), µ a ) ≥ f (t) N a (t) + 2 2 ⊆ ∪ t-K+1 n=1 K inf (ν a ,n , µ a ) ≥ f (t) n + 2 2 .
The remainder of the proof is now the same as in Cappé et al. [2013b]. In particular, their Equation 26combined with the bounds given after their Equation 35shows that the right-hand side of (A.5) is upper bounded by 36µ -4 a (2 + log log T ) (log T ) 4/5 = o(log T ).

Proof of Lemma 18 for KL-UCB in the settings of Theorems 6 and 7. Fix a ∈ U ∪ U. For ease of notation, we analyze E[M a a (T )] rather than E[M a a (T (G) )], but for fixed G < ∞ there is no loss of generality in doing so. If a ∈ U, then let µ † = c a ρ a , and otherwise, fix µ † ∈ (µ a , µ + ). Let ρ † ≡ µ † /c a (setting of Theorem 6) or ρ † ≡ 1log(T ) -1/5 µ † /c a (setting of Theorem 7). Note that ρ † < µ + /c a . Analogous arguments to those used for (20) show that

a ∈ Â(t + 1), U a (t) c a < ρ (t) ⊆ a ∈ Â(t + 1), U a (t) c a < ρ (t), ρ † ≥ U a (t) c a ∪ a ∈ Â(t + 1), U a (t) c a < ρ (t), ρ † < U a (t) c a ⊆ ρ † ≥ U a (t) c a ∪ a ∈ Â(t + 1), ρ † < U a (t) c a . (A.6) Let b a a (T ) ≡ f (T ) K inf (ν a , µ † ) .
Similarly to ( 22), we have that

E[M a a (T )] ≤ f (T ) K inf (ν a , µ a ) + ∞ n=b a a (T )+1 P νa,n ∈ C caρ † ,f (T )/n + T -1 t=K P ρ † ≥ U a (t) c a + 2. By Lemmas A.1 and A.2, E[M a a (T )] ≤ log T K inf (ν a , µ † ) + o(log T ). (A.7)
In what follows we refer to this o(log T ) term as r(T, µ † ), where we note that r(T, µ † )/ log T → 0 for each fixed µ † ∈ (µ a , µ + ). If a ∈ U, we will obtain our result by letting µ † → µ + . Thus, there exists a sequence µ † (T ) → µ + such that r(T, µ † (T ))/ log T → 0. Noting lim inf µ † →µ+ K inf (ν a , µ † ) = +∞ in the setting of both theorems, we see that

E[M a a (T )] ≤ log T K inf (ν a , µ † (T )) + r(T, µ † (T )) = o(log T ).
This is the desired result when a ∈ U. If, instead, a ∈ U, then replacing T by T (G) in (A.7) (for T large enough so that T (G) > 1), and recalling that µ † = c a ρ a when a ∈ U, gives the desired result.

Proof of Lemma 19 for KL-UCB in the settings of Theorems 6 and 7. Fix g ∈ N, a ∈ U ⊂ M ∪ N , and T (g) such that T (g) > 1. In the setting of Theorem 6 let ρ † = ρ a , and in the setting of Theorem 7 let ρ † = [1log(T ) -1/5 ]ρ a . By (A.6) and the fact that {ρ

† < U a (t)/c a } = νa,Na(t) ∈ C caρ † ,f (t)/Na(t) , E[M a a (T (g-1) ) -M a a (T (g) )] ≤ T (g-1) -1 t=T (g) P ρ † ≥ U a (t) c a + T (g-1) -1 t=T (g) P a ∈ Â(t + 1), νa,Na(t) ∈ C caρ † ,f (t)/Na(t) .
The first term in the right hand side is upper bounded by the same sum from t = K to T -1, and is thus o(log T ) by Lemma A.2. For the second term, let b a (T, g) ≡ (1δ) f (T (g) ) K inf (νa,caρ ) if a ∈ N and let b a (T, g) ≡ f (T (g) )

(1-δ) K inf (νa,caρ a ) if a ∈ M. Similar arguments to those used to derive (21) in Section 6.1 show that, for T large enough so that T (g) ≥ K,

T (g-1) -1 t=T (g) P a ∈ Â(t + 1), νa,Na(t) ∈ C caρ † ,f (t)/Na(t) ≤ T (g-1) -K n=1 T (g-1) -1 t=T (g) P νa,n ∈ C caρ † ,f (T (g-1) )/n , τ a,n+1 = t + 1 .
We split the sum over n into a sum S 1 from n = 1 to b a (T, g) and a sum S 2 from n = b a (T, g) + 1 to T (g-1) -K. For the latter sum, the fact that, for each n, τ a,n+1 = t + 1 for at most one t in a given interval, yields that

S 2 ≤ T (g-1) -K n=b a (T,g)+1 P νa,n ∈ C µ † ,f (T (g-1) )/n . If a ∈ N , then δ satisfying (32) yields that b a (T, g) > f (T (g-1) )
K inf (νa,caρ a ) , and so the above sum is o(log T ) by Lemma

A.1. If a ∈ M, then b a (T, g) = f (T (g-1) )
K inf (νa,caρ a ) , and so again the above sum is o(log T ). We now bound S 1 . Note that if N a (T (g) -1) > b a (T, g), then, for every n ≤ b a (T, g), τ a,n+1 < T (g) and S 1 = 0 (the sum over t is void). Therefore,

S 1 ≤ b a (T,g) n=1 P N a (T (g) -1) ≤ b a (T, g) = b a (T, g) P N a (T (g) -1) ≤ b a (T, g) .
From Lemma 20, KL-UCB is uniformly efficient. Thus, by (8), for any a ∈ M one has lim

T →∞ P N a (T (g) -1) ≤ 2 log(T (g) ) (1 -δ) K inf (ν a , c a ρ a ) = 0,
where we use the fact that K inf (ν a , c a ρ ) = 0 and choose = (1δ) K inf (ν a , c a ρ a )/2 > 0. This yields that P N a T (g) -1 < b a (T, g) → 0 as T → ∞ and S 1 = o(log T ). If a ∈ N , then Lemma 20 and (8) from Lemma 4 yield that

P N a T (g) -1 < (1 -δ) log T (g) K inf (ν a , c a ρ ) → 0 as T → 0.
The fact that lim T f (T )/ log T = 1 shows that b a (T, g) = (1δ) log T (g) K inf (νa,caρ ) + o(log T ). Plugging this into (8) from Lemma 4 (which holds for every δ between 0 and 1) yields that P N a T (g) -1 < b a (T, g) → 0 as T → ∞. It follows that S 1 = o(log T ).

We have then shown that E[M a a (T (g-1) ) -M a a (T (g) )] = o(log T ) for each a ∈ U ⊂ M ∪ N and each g ≤ G. As Term B is a sum of finitely many such terms, Term B is o(log T ).

D Supplementary Proofs for Thompson Sampling

We begin with a lemma.

Lemma A.3. For any fixed real number L, arm a, µ a < µ † < θ † , and t ≥ 1, I μa (t) ≤ µ † , N a (t) ≥ L P θ a (t) > θ † F(t) ≤ e -(L+1) KL(µ † ,θ † ) .

Proof. From Fact 3 in Agrawal and [START_REF] Goyal | Further optimal regret bounds for thompson sampling[END_REF]] [also used in Agrawal and Goyal, 2011, Kaufmann et al., 2012a,b] Using that µ † < θ † , the Chernoff-Hoeffding bound gives that P θ a (t) > θ † F(t) is no larger than e -[Na(t)+1] KL(μa(t),θ † ) . Multiplying the left-hand side by I μa (t) ≤ µ † , N a (t) ≥ L , this yields the upper bound e -(L+1) KL(µ † ,θ † ) .

Proof of Lemma 11. Let θã (t) = θ ã(t) for all ã = a and let θa (t) = -∞. Define the event B ≡ ρ ( θa (t) : a = 1, . . . , K + 1) < θ a (t)/c a ≤ ρ

= E

T -1 t=0

1 N a (t) < L † (T ) -1, μa (t) ≤ c a ρ † P a ∈ Â(t + 1), θ a (t) > c a ρ ‡ F(t)

+ E T -1 t=0
1 N a (t) ≥ L † (T ) -1, μa (t) ≤ c a ρ † P a ∈ Â(t + 1), θ a (t) > c a ρ ‡ F(t)

≤ E

T -1 t=0

1 N a (t) < L † (T ) -1 P a ∈ Â(t + 1) F(t)

+ E T -1 t=0
1 N a (t) ≥ L † (T ) -1, μa (t) ≤ c a ρ † P θ a (t) > c a ρ ‡ F(t) .

(A.9)

The first term in the right hand side equals E

T -1 t=0 1 N a (t) < L † (T ) -1, a ∈ Â(t + 1) . Hence it is no larger than L † (T )-1 (the sum has at most L † (T )-1 nonzero terms). For the second term, Lemma A.3 yields 1 μa (t) < c a ρ † , N a (T ) ≥ L † (T ) -1 P θ a (t) > c a ρ ‡ F(t) ≤ e -L † (T ) KL(caρ † ,caρ ‡ ) = T -1 .

It follows that the second term on the right of (A.9) is upper bounded by T -1 t=0 T -1 = 1. This completes the proof.

Proof of Lemma 18 for Thompson sampling in the setting of Theorem 8. Fix a ∈ U ∪ U and ∈ (0, 1). For ease of notation, we analyze E[M a a (T )] rather than E[M a a (T (G) )], but for fixed G < ∞ there is no loss of generality in doing so. If a ∈ U, then let µ † = c a ρ a , and otherwise, fix µ † ∈ (µ a , µ + ). Let ρ † and ρ ‡ satisfy ρ a < ρ † < ρ ‡ < µ † /c a (exact quantities to be specified at the end of the proof Note that the right-hand side of the above is almost identical to (23). Note that all of the results used to control the three terms on the right-hand side of ( 23) hold for any a with ρ a ≤ ρ provided ρ a < ρ † < ρ ‡ < µ † /c a . In particular, we are referring to Lemma 11, (25), Lemma 13, (26), Lemma 15, and Lemma 14. Hence, E[M a a (T )] ≤ log T KL(caρ † ,caρ ‡ ) + o(log T ). Selecting ρ † and ρ ‡ as in the proof of ( 11) and ( 12) from Theorem 8 yields E[M a a (T )] ≤ (1 + ) 2 log T KL(µa,µ † ) + o(log T ). As was arbitrary, dividing both sides by log T and taking T → ∞ followed by → 0 yields that E[M a a (T )] ≤ log T KL(µa,µ † ) + o(log T ). If a ∈ U, then replacing T by T (G) (for T large enough so that T (G) > 1) gives the desired E[M a a (T (G) )] ≤ (1δ) G log T K inf (νa,µ † ) + o(log T ) in light of the fact that µ † = c a ρ a . If, on the other hand, a ∈ U, then the same arguments used to conclude the a ∈ U result in the proof of Lemma 18 for KL-UCB, namely selecting an appropriate sequence µ † (T ) → µ + , can be used to show that E[M a a (T (G) )] = o(log T ). Proof of Lemma 19 for Thompson sampling in the setting of Theorem 8. Fix g ∈ N, an arm a ∈ U ⊂ M ∪ N , and T (g) such that T (g) > 1. Let ρ † and ρ ‡ satisfy ρ a < ρ † < ρ ‡ < ρ a and KL(c a ρ † , c a ρ ‡ ) ≥ (1δ) KL(µ a , c a ρ a ). By the same arguments used for (A.10), E[M a a (T (g-1) ) -M a a (T (g) )]

≤ T (g-1) -1 t=T (g) P a ∈ Â(t + 1), θ a (t) c a ≤ ρ ‡ , θ a (t) c a < ρ (t) + T (g-1) -1 t=T (g) (1-δ) KL(µa,caρ a ) . We have that If a ∈ N , then Lemma A.3 and KL(c a ρ † , c a ρ ‡ ) ≥ (1δ) KL(µ a , c a ρ a ) yield that the first term on the right is upper bounded by T (g-1) -1 t=T (g) exp -(1δ) 2 log T (g-1) KL(µ a , c a ρ ) KL(µ a , c a ρ a )

≤ T (g-1) exp -(1δ) 2 log T (g-1) KL(µ a , c a ρ ) KL(µ a , c a ρ a ) ≤ 1, where the second inequality holds because δ satisfies (32). If a ∈ M, then we instead have that this term is no larger than T (g-1) -1 t=T (g) exp -log T (g-1) KL(µ a , c a ρ a ) KL(µ a , c a ρ a ) ≤ 1.

For the second term in (A.12), note that Plugging this into (A.11) yields that E[M a a (T (g-1) ) -M a a (T (g) )] = o(log T ) for each a ∈ U ⊂ M ∪ N and each g ≤ G. As Term B is a sum of finitely many such terms, Term B is o(log T ).

Figure 1 :

 1 Figure 1: Regret of the four algorithms with theoretical guarantees. ESCB only run for Simulations 1 and 2 for which the cost is identically one for all arms.

Figure 2 :

 2 Figure 2: Time minus the number of optimal arm draws (top) and number of suboptimal arm draws (bottom) in Simulation 4.

  cã ã∈{1,...,K}\[H∪{a }] cã if a = K + 1 and KL-UCB.

  Appendix A focuses on oracle strategy and regret decomposition. Appendix B contains proofs establishing the asymptotic lower bound on the number of suboptimal arm draws. Appendices C and D contain technical proofs for KL-UCB and the Thompson sampling, respectively.

  , P θ a (t) > θ † F(t) = P {Z n } is an i.i.d. sequence (independent of all other quantities under consideration) of Bernoulli random variables with mean θ † . Upper bounding the right-hand side yieldsP θ a (t) > θ † F(t) ≤ P   1 N a (T ) + 1 Na(T )+1 n=1 Z n ≤ μa (T ) F(t)   .

  sums are trivially upper bounded by the sums from t = 0 to T -1, and thus are o(log T ) by Lemma 11, (25), Lemma 13, (26), and Lemma 15. If a ∈ N , then let b a (T, g) ≡ (1δ) log T (g)KL(µa,caρ ) , and if a ∈ M then let b a (T, g) ≡ log T(g)

11

  ρ † , N a (t) < b a (T, g) P a ∈ Â(t + 1), θ a (t) {N a (t) < b a (T, g)} P a ∈ Â(t + 1) F(t) N a (t) < b a (T, g), a ∈ Â(t + 1) a T (g) < b a (T, g) T (g-1) -1 t=T (g) 1 N a (t) < b a (T, g), a ∈ Â(t + 1)   ≤ b a (T, g) P N a T (g) < b a (T, g) ,where the final inequality uses that the sum inside the expectation is at most b a (T, g). By the uniform efficiency of the algorithm established in Lemma 20 and (8) from Lemma 4, the probability in the final inequality is o(1), and thus the above is o(b a (T, g)) = o(log T ). Thus (A.12) is o(log T ).

  Just like KL-UCB, ESCB uses confidence bounds whose level rely on a function f such that f (t) ≈ log t. Because the optimization problem solved to compute the indices (17) and (19) are different, the f functions used by KL-UCB and ESCB are not directly comparable. Nonetheless, a side-by-side comparison of the two algorithms seems to indicate that f (t) = log t + cB log log t for ESCB is comparable to f (t) = log t + c log log t for KL-UCB. Combes et al. prove an O(log T ) regret bound (with a sub-optimal constant) for the version of ESCB corresponding to the constant c = 4, that we refer to as ESCB 4B.

  The event {θ a (t)/c a > ρ ‡ } is independent of the event B conditional on F(t), and so the fact thatθ a (t)/c a > ρ ‡ ∩ B ⊆ {θ a (t)/c a ≥ ρ (t)} yields P(B|F(t)) ≤ P ( θ a (t)/c a ≥ ρ (t)| F(t)) P ( θ a (t)/c a > ρ ‡ | F(t)). note that P θ a (t) > c a ρ ‡ F(t) is positive (a beta distribution with at least one success is larger than c a ρ ‡ < 1 with positive probability). Finally, since a ∈ Â(t + 1) implies that θ a (t)/c a ≥ ρ (t), (A.8) yieldsP a ∈ Â(t + 1), θ a (t)/c a ≤ ρ ‡ , θ a (t)/c a < ρ (t) F(t) ≤ P θ a (t)/c a ≤ ρ ‡ ∩ B F(t), where the latter inequality holds because τ a ,n+1 = t + 1 for at most one t in {0, . . . , T -1}.

	P ρ (t) ≤ = P ρ (t) ≤ θ a (t) c a ≤ P θ a (t) c a ≤ ρ ‡ ∩ B F(t) . ≤ ρ ‡ , θ a (t) c a < ρ (t) F(t) θ a (t) c a , θ a (t) c a < ρ (t) ∩ B F(t) E T -1 t=0 1 -p ρ ‡ a (t) p ρ ‡ a (t) P θ a (t) c a ≥ ρ (t) F(t) ≤ q-1 a E T -1 t=0 1 -p ρ ‡ a (t) p ρ ‡ a (t) P a ∈ Â(t + 1) F(t) = q-1 a E T -1 t=0 1 -p a ,N a (t) p a ,N a (t) 1 a ∈ Â(t + 1) = q-1 a E T -1 t=0 T -1 n=0 1 -p ρ ‡ a ,n p ρ ‡ a ,n 1 {τ a ,n+1 = t + 1} We Proof of Lemma 12. Using (24), one can write ≤ q-1 a E T -1 n=0 a ,n 1 -p ρ ‡ p ρ ‡ a ,n	(A.8)

‡ . Observe that = P θ a (t)/c a ≤ ρ ‡ F(t) P ( B| F(t)) ≤ P θ a (t)/c a ≤ ρ ‡ F(t) P ( θ a (t)/c a ≥ ρ (t)| F(t)) P ( θ a (t)/c a > ρ ‡ | F(t)) . Proof of Lemma 14. Let L † (T ) ≡ log T KL(caρ † ,caρ ‡ ) . We have that T -1 t=0 P a ∈ Â(t + 1), θ a (t) > c a ρ ‡ , μa (t) ≤ c a ρ †

  ). Note that

	⊆ a ∈ Â(t + 1),	θ a (t) c a	≤ ρ ‡ ,	θ a (t) c a	< ρ (t) ∪ a ∈ Â(t + 1),	θ a (t) c a	> ρ ‡ .
	Recalling that E[M a a (T )] is equal to			T -1 t=0 P a ∈ Â(t + 1), θ a (t)/c a < ρ (t) , the above yields
	E[M a a (T )] ≤	T -1 t=0	P a ∈ Â(t + 1),	θ a (t) c a	≤ ρ ‡ ,	θ a (t) c a	< ρ (t)
				+	T -1 t=0	P a ∈ Â(t + 1),	μa (t) c a	> ρ †
				+	T -1 t=0	P a ∈ Â(t + 1),	θ a (t) c a	> ρ ‡ ,	μa (t) c a	≤ ρ † .	(A.10)
	a ∈ Â(t + 1),	θ a (t) c a	< ρ (t)

  † , N a (t) < b a (T, g) P a ∈ Â(t + 1), θ a (t) c a > ρ ‡ F(t)

	+ E	  T (g-1) -1 t=T (g)	1	μa (t) c a	≤ ρ   .	(A.12)
	T (g-1) -1 t=T (g)	P a ∈ Â(t + 1),	θ a (t) c a	> ρ ‡ ,	μa (t) c a	≤ ρ †
	= E	  T (g-1) -1 t=T (g)	1		μa (t) c  

a ≤ ρ † , N a (t) ≥ b a (T, g) P a ∈ Â(t + 1), θ a (t) c a > ρ ‡ F(t)

Acknowledgements

The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-13-BS01-0005 (project SPADRO) and ANR-16-CE40-0002 (project BADASS). Alex Luedtke gratefully acknowledges the support of a Berkeley Fellowship.

Appendix

We begin with an outline of the results proven in this appendix and how they are related to one another. Lemma 4 gives a lower bound on the number of draws of each suboptimal arm for a uniformly efficient algorithm. Deduced from Lemma 4, Theorem 5 gives an asymptotic regret lower bound (10) for a uniformly efficient algorithm. The asymptotic lower bound is achieved whenever the expected number of draws of each suboptimal arm satisfies the appropriate asymptotic condition, either (11) or ( 12) depending on the arm, and the expected number of draws of each optimal arm away from the margin satisfies the asymptotic condition (13). Theorems 6 and 7 state that the variants of KL-UCB are uniformly efficient and achieve (10) for rewards sampled either from a single parameter exponential family or from bounded and finitely supported distributions. Theorem 8 states that Thompson sampling is uniformly efficient and achieves (10) for Bernoulli distributed rewards.

The first step of the proof of Theorems 6, 7, and 8 consists in showing that KL-UCB and Thompson sampling achieve the asymptotically optimal expected number of suboptimal arm draws, i.e. that ( 11) and ( 12) hold in their contexts. For KL-UCB, this is a consequence of a preliminary analysis given in Lemmas A.1 and A.2. For Thompson sampling, this is a consequence of another preliminary analysis given in Lemmas 11 through 14. The proof of Lemma 14 relies on a link between the beta and binomial distributions given in Lemma A.3.

The second step of the proof of Theorems 6, 7, and 8 consists in showing that KL-UCB and Thompson sampling are uniformly efficient in their respective contexts. This is a consequence of yet another preliminary analysis, ( 11), ( 12), and Lemma 18.

The third step of the proof of Theorems 6, 7, and 8 consists in showing that KL-UCB and Thompson sampling achieve the asymptotically optimal expected number of optimal draws away from the margin, i.e. that (13) holds in their contexts. This is a consequence of the preliminary analysis undertaken in step two and of Lemmas 18 and 19. The proofs of Lemmas 18 and 19 hinge on Lemmas 11 through 14. The proof of Lemma 19 also relies on Lemma A.3.

The fourth and final step of the proof of Theorems 6, 7, and 8 boils down to applying Theorem 5.

A Oracle strategy and regret decomposition

A.1 Proof of Proposition 1

Recall that

Introducing c K+1 = B and µ K+1 = Bρ, one can prove that q coincides with the first K components of q K+1 ∈ [0, 1] K+1 , that is defined as the solution to

and that the two optimization problems have the same value. This is because as µ K+1c K+1 ρ = 0, the two objective functions coincide:

and if q satisfies the first constraint, there exists q K+1 such that q K+1 = (q, q K+1 ) satisfies the second constraint: K+1 a=1 q a c a = B (as c K+1 = B). Conversely, if q K+1 satisfies the second constraint, its first K marginals clearly satisfy the first constraint.