Hédi Hadiji
email: hedi.hadiji@math.

Sébastien Gerchinovitz
email: sebastien.gerchinovitz@irt-saintexupery.

Gilles Stoltz
email: gilles.stoltz@math.

Diversity-Preserving K-Armed Bandits, Revisited

Keywords: Multi-armed bandits, UCB strategy, diversity, regret bounds: upper and lower bounds c Hadiji, Gerchinovitz, Loubes, Stoltz -October 2020

), who approached it mainly by a reduction to the setting of linear bandits. We design a UCB algorithm using the specific structure of the setting and show that it enjoys a bounded distribution-dependent regret in the natural cases when the optimal mixed actions put some probability mass on all actions (i.e., when diversity is desirable). Simulations illustrate this fact. We also provide regret lower bounds and briefly discuss distribution-free regret bounds.

Setting and literature review

We consider stochastic bandit models with finitely many arms. All of them are desirable actions, though some lead to higher payoffs. Effective (regret-minimizing) algorithms are bound to play the optimal arm(s) an overwhelming fraction of time. [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] refer to this effect as polarization and introduce a model to avoid it. We suggest the alternative terminology of preserving diversity. A general formulation of the diversity-preserving bandit model is provided below and is summarized in Protocol 1. Our aim in this article is to deepen and improve on the results obtained by the mentioned reference; see Sections 1.2 and 1.3 for details.

Extended literature review. A general discussion of the notions of diversity and fairness in stochastic and adversarial bandits is provided in Appendix B.

Diversity-preserving bandits As in traditional K-armed bandits, K probability distributions ν 1 , . . . , ν K associated with each arm are considered, with expectations denoted by µ 1 , . . . , µ K . These distributions are unknown to the learner but belong to a known set of possible distributions, called a model D. In this article we consider mainly the bandit model D [0,1] of all probability measures supported on [0, 1], that is, we assume that rewards can be distributed according to any distribution bounded in [0,1]. An exception to this is the lower bound in Section 3, which we formulate on a generic model D satisfying a mild assumption.

The learning protocol is the following. An arm A t ∈ [K] is picked among K choices at each round, where we denote by [K] the set {1, . . . , K}. The learner then obtains a payoff Y t drawn at random according to ν At given that choice. This is the only observation made (the learner does not know what it would have obtained with a different choice). However, the distinguishing feature of the bandit model by [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] is that the choice of A t is made in two steps, as follows. First, a distribution p t over the arms is picked, in some known closed set P, which quantifies diversity (specific examples are given below); then, the arm A t is drawn at random according to p t . Following game-theoretic terminology, we will call a ∈ [K] pure actions or ams, and p ∈ P mixed actions or probabilities.

We measure performance in terms of expected payoffs. The expected payoff at round t may be computed by repeated applications of the tower rule:

E[Y t | A t , p t ] = µ At , thus E Y t | p t = k∈[K] p t,k µ k def = p t , µ , thus E[Y t ] = E p t , µ .
Maximizing the cumulative expected payoff of a policy amounts to minimizing the expected regret defined as

R T = T max p∈P p, µ -E T t=1 p t , µ .
In the definition of the regret, the comparison is made with respect to the expected payoff that would have been obtained by picking at each round a best diversity-preserving distribution over the arms.

Protocol 1 summarizes the setting and aim.

Protocol 1 Diversity-preserving stochastic bandits [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] Known parameters Arms 1, . . . , K and model D of distributions for the arms Closed set P of diverse enough probability distributions over the arms Unknown parameters

Probability distributions ν = (ν 1 , . . . , ν K ) in D, with expectations µ = (µ 1 , . . . , µ K )

for t = 1, 2, . . . do Pick a distribution p t = (p t,1 , . . . , p t,K ) ∈ P over the arms Draw at random an arm A t ∼ p t Get and observe a payoff Y t ∼ ν At drawn at random according to ν At given A t end for

Aim

Minimize the expected regret

R T = T max p∈P p, µ -E T t=1 p t , µ
1.1. Examples of diversity-preserving sets P of distributions over the arms Simplest example. The simplest requirement is that each arm should be played with some minimal probability > 0, which corresponds to P = p : ∀a ∈ [K], p a . This constraint makes sense in online advertisement: all offers need to be displayed a significant fraction of the time and get a significant chance to be selected.

More generally, [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] indicate that one could group arms intro groups G 1 , . . . , G N of similar arms and impose minimal probabilities 1 , . . . , N > 0 as well as maximal probabilities u 1 , . . . , u N < 1 for each group defined as:

P = p : ∀g ∈ [N ], a∈Gg p a ∈ [ g , u g ] .
Note that the sets P considered above are finite polytopes 1 .

Maintaining a budget. The last example can be generalized as follows: every pure action a is associated with N costs c

(1) a , . . . , c (N ) a in R, accounting for limited resources or environmental costs like the amount of carbon emissions generated from taking the action. The model can handle negative costs (e.g., negative carbon emissions). When a player picks a pure action A t according to the mixed action p = (p 1 , . . . , p K ), the N expected costs associated with her choice are

a∈[K] p a c (1) a , . . . , a∈[K] p a c (N ) a .
In this case, a reasonable objective for the player is to maximize her payoff under the constraints that, for all n ∈ [N ], the n-th expected cost of her actions be kept under a certain level u n ∈ R. This amounts to playing under Protocol 1 with the probability set

P = p : ∀n ∈ [N ], K a=1 p a c (n) a u n .
This set is again a finite polytope. Note that the name "diversity-preserving" was inspired by the example of the previous paragraph and is perhaps less relevant in the present example. et al. (2011) and further studied by [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF]. They obtain regret bounds of order at best K(ln T ) 2 /∆, with the notation of Theorem 1, which is of the same order as our most general bound (Case 1 of Theorem 1). However, their algorithm is less computationally efficient, and the lower order terms, as well as the numerical factors in the bounds are worse than ours. The case of a bounded regret is also not covered, while it constitutes our main contribution; see Section 1.3 below.

The main reason behind these suboptimal bounds is related to a loss of information, due to discarding the pure action A t picked, which is known, and relating the reward Y t ∼ µ At to p t and not to A t . The considered setting can thus be described as a stochastic linear bandit setting with augmented feedback. See Appendix C for more details on these statements, including an intuition on why sharper regret bounds are achieved with the additional information of which arm A t was picked and a literature review on bandit models with augmented feedback (and thus, improved regret bounds), discussing contributions like the ones by [START_REF] Caron | Leveraging side observations in stochastic bandits[END_REF] and [START_REF] Degenne | Bandits with side observations: Bounded vs. logarithmic regret[END_REF].

Summary of our contributions and outline of the article

Section 2 introduces our main algorithm, a diversity-preserving variant of UCB, which is computationally efficient. Theorem 1 provides several regret bounds, the most interesting ones guaranteeing a bounded regret in the natural cases when some probability mass is put on all arms either just by the optimal mixed actions (non-explicit bound) or by all actions (closed-form bound); this corresponds to the cases when diversity is indeed desirable. Section 3 discusses lower bounds: Theorem 2, which relies on the approach introduced by [START_REF] Graves | Asymptotically efficient adaptive choice of control laws in controlled markov chains[END_REF], indicates that ln T rates are unavoidable in the case when some arms receive zero probability mass by optimal actions, if in addition the means of the distributions in D are not bounded from above. Section 4 illustrates the dual behavior of either a bounded regret or a ln T regret for our variant of UCB. Most of our claims are proved in the main body of this article. However, an appendix collects an extended literature review and technical considerations used in the proofs of Sections 2 and 3. It also briefly discusses distribution-free regret bounds (which are less challenging in this diversity-preserving setting), see Appendix A.

Diversity-preserving UCB: distribution-dependent regret upper bounds

To state our main algorithm, we first introduce estimations of the means µ a of the arms a ∈ [K]. We define

N a (t) = t s=1 1 {As=a} and µ a (t) =      1 if N a (t) = 0 1 N a (t) t s=1 Y s 1 {As=a} if N a (t) 1
Note that in the diversity-preserving setting, we cannot ensure that arm a be picked even once. Therefore, contrary to the vanilla bandit setting, it is important to handle the case when N a (t) = 0. We thus set a default value of 1 (the maximal average reward) for µ a (t) in this case. For the same reason, we put a maximum in the denominator of the upper confidence bounds U a (t), see Algorithm 1 below.

We assume that P is a finite polytope (see Footnote 1): it is the convex hull of a finite set of points Ext(P). The natural extension of the UCB algorithm to our setting is stated next. Note that the maximum of the linear functional p ∈ P → p, U (t -1) is reached for some p in Ext(P). The requirement that p t be chosen among Ext(P) only is made for technical reasons.

Algorithm 1 Diversity-preserving UCB for rewards in [0, 1] and when P is a finite polytope 1: Initialization: The analysis relies on the suboptimality gaps. To define them, we first define the optimal expected payoff and the set of optimal mixed actions as

U (0) = (1, . . . ,
M (µ, P) = max p∈P p, µ and Opt(ν) = argmax p∈P p, µ . (1)
The suboptimality gap of a given mixed action p ∈ P and the suboptimality gap of the set Ext(P) are in turn defined as ∆(p) E N p (T ) .

∆(p) = M (
(3) In this setting, that decomposition of the regret in terms of gaps of mixed actions p is more useful than the classical decomposition in terms of gaps for each pure action a ∈ [K].

To state our main bound, we define some minimal values of probabilities of playing each arm a, as far as optimal mixed actions and all mixed actions are concerned, respectively: p a .

p min (ν) = min p∈Opt(ν) min a∈[K]
The fact that p min (ν) > 0 (respectively, > 0) corresponds to the case when Opt(ν) (respectively, P) is in the relative interior of the simplex. The assumption > 0 of Case 3 in the theorem below is more stringent than the assumption p min (ν) > 0 of Case 2 (and Case 1 comes with no assumption).

Theorem 1 Assume that the diversity-preserving set P is a finite polytope and the bandit model is D [0,1] , the set of all distributions over [0, 1]. Then, the regret of diversity-preserving UCB (Algorithm 1) is bounded as follows, for all bandit problems ν:

1. In all cases, R T (ν) 24K ln(1 + T ) 2 + K + 2 ∆ .
2. If P and ν are such that p min (ν) > 0, then the regret is bounded, lim

T →∞ R T (ν) < +∞ .
3. If P is such that > 0, then the regret is bounded by the closed-form bound

R T (ν) 24K ∆ ln 1 + 32 ∆ 2 ln 16 ∆ 2 + 7K + 3 min{∆, 2 } .
The theorem is proved in the rest of this section. For now, we issue two series of comments. Comment 1: The assumption of Case 2, which reads p a > 0 for all a ∈ [K] and all optimal mixed actions p , is a natural assumption, which models the fact that preserving diversity is desirable (all arms are somewhat useful). We show that bounded regret is possible in this case.

Comment 2: Of course, running a classical UCB on the mixed actions in Ext(P) would guarantee a regret bound of order p∈Ext(P) 1/∆(p) ln T . This would even improve asymptotically over the (ln T ) 2 rate of Case 1. However it would come at a price of huge impractical constants when P has many vertices, and would not cover the case of bounded regret. Importantly, our algorithm is also more elegant and computationally slightly more efficient.

Common part of the proofs

We consider the events

E(t) = For all a ∈ [K], µ a -µ a (t) 2 ln t max N a (t), 1 (4)
and

E (t) = For all a ∈ [K], 2 ln t max N a (t), 1 < ∆ 2 .
When both E(t) and E (t) hold, for any suboptimal p ∈ Ext(P) and any optimal mixed action p , we have the following chain of inequalities, where we use ∆ ∆(p):

U (t), p = µ(t), p + K a=1 p a 2 ln t max N a (t), 1 µ, p + 2 K a=1 p a 2 ln t max N a (t), 1 < µ, p +∆ µ, p +∆(p) = µ, p µ(t), p + K a=1 p a 2 ln t max N a (t), 1 = U (t), p .
In that case, by construction of our algorithm as an index policy, no suboptimal mixed action is picked; put differently, and writing B for the complement of any event B,

p t+1 / ∈ Opt(ν) ⊆ E(t) ∪ E (t) .
Since the (non-expected) instantaneous regrets r t = p -p t , µ are always smaller than 1 given that the considered bandit problem lies in D [0,1] , and for a time t 0 1 to be defined by the analysis,

R T (ν) = R t 0 (ν) + T t=t 0 +1 E[r t ] R t 0 (ν) + T t=t 0 +1 P p t / ∈ Opt(ν) R t 0 (ν) + T -1 t=t 0 P E(t) 2Kt -3 + T -1 t=t 0 P E (t) R t 0 (ν) + 3K + T -1 t=t 0 P E (t) , (5)
where, for the final inequality, we used Lemma 4 of Appendix D (which is a direct application of Hoeffding's inequality together with a union bound) to get P E(t) 2Kt -3 for t 2 (true also for t = 1), together with the fact that the series of the 1/t 3 sums up over t 1 to ζ(3) < 1.21.

Proof of Case 3 of Theorem 1

Let t 0 = max t ∈ {2, 3, 4, . . .} : (8 ln t)/∆ 2 > t /2 , which is well defined since (8 ln 2)/∆ 2 > 1 and (ln t)/t → 0 as t → +∞. We have, for t t 0 + 1,

E (t) = ∃a ∈ [K] : N a (t) 8 ln t ∆ 2 ⊆ a∈[K] N a (t) t 2 ⊆ a∈[K] N a (t) - t s=1 p s,a - t 2 ,
where we used, for the last inclusion, the fact that p s,a by definition of . By the Hoeffding-Azuma inequality (see, e.g., Lemma A.7 in [START_REF] Cesa | Prediction, Learning, and Games[END_REF], for all t 1 and all ε > 0,

P N a (t) - t s=1 p s,a -ε exp -2ε 2 /t .
Therefore,

+∞ t=t 0 P E (t) 1+ +∞ t=t 0 +1 a∈[K] exp - 2 t t 2 2 1+K +∞ t=t 0 +1 exp - t 2 2 1+ K 1 -e -2 /2 .
We substitute the above bound into (5) together with

R t 0 24K ln(1 + t 0 ) 2 /∆ + (2 + K)/∆,
which follows from Case 1 of Theorem 1 (later proved in Appendix D.3); we get

R T (ν) 24K ln(1 + t 0 ) 2 ∆ + 3K + 2 + K ∆ + 1 + K 1 -e -2 /2 .
The proof of Case 3 is concluded by proving (see Appendix D.1)

t 0 32 ∆ 2 ln 16 ∆ 2 (6)
and by performing crude boundings to improve readability, like 1/(1 -e -u ) 1 + 1/u for u > 0.

Proof of Case 2 of Theorem 1

Based on (5) with t 0 = 1, we only need to prove that the sum of the P E (t) over t 1 is finite.

To do so, we denote, for t 1,

N (t) = p∈Opt(ν) N p (t)
the number of times up to round t an optimal mixed action was pulled. We decompose events based on whether N (t) is larger or smaller than t/2: by several applications of the union bound,

P E (t) P N (t) t 2 ∩ E (t) + P N (t) t 2 = K a=1 P N (t) t 2 ∩ N a (t) 8 ln t ∆ 2 + P N (t) t 2 . ( 7
)
We prove in Appendix D.2 that optimal mixed actions are pulled an overwhelming fraction of the time, typically more than half of the time:

+∞ t=1 P N (t) t 2 < +∞ . ( 8
)
As for the other sum, we fix a ∈ [K] and first note that by the Hoeffding-Azuma inequality, for each t 1 and all δ t ∈ (0, 1],

P N a (t) - t s=1 p s,a - t 2 ln 1 δ t δ t .
Note that p s,a 1 {p s ∈Opt(ν)} p min (ν) by definition of p min (ν). Therefore, choosing δ t = 1/t 2 ,

P N a (t) -p min (ν) N (t) - √ t ln t 1/t 2 .
Now, as -√ t ln t (8 ln t)/∆ 2 -tp min (ν)/2 for all t larger than some t 0 , we finally get, for t t 0 ,

P N (t) t 2 ∩ N a (t) 8 ln t ∆ 2 P N a (t) -p min (ν) N (t) 8 ln t ∆ 2 - tp min (ν) 2 1/t 2 .
This shows that the first sum in ( 7) is also bounded, which concludes the proof of this case.

Proof of Case 1 of Theorem 1

It follows closely the standard proof scheme for linear bandits, see Lattimore and Szepesvári (2020, Chapter 19) and earlier references therein; thanks to the knowledge of the pure actions A t played we are able to simplify the proof and get a more readable bound, see Appendix D.3.

Distribution-dependent lower bounds for finite polytopes P

This section considers general models D for the distributions of the considered bandit problems ν = (ν 1 , . . . , ν K ), with finite first moments, and satisfying a mild assumption (see below). Our aim is to discuss the optimality of the regret upper bounds exhibited in the previous section. To do so, we rely on and adapt the approach introduced by [START_REF] Graves | Asymptotically efficient adaptive choice of control laws in controlled markov chains[END_REF].

We first describe the assumptions that we make in this section. We only consider diversitypreserving sets P given by finite polytopes, i.e., sets which are the convex hull of a finite set of points denoted by Ext(P). Recall from (1) that Opt(ν) refers to the set of optimal mixed actions of a bandit problem ν. We will assume that there is a unique optimal mixed action: Opt(ν) = p (ν) ; this mixed action then necessarily belongs to Ext(P). This assumption is common in bandit analyses (it is also made, e.g., in Lattimore andSzepesvári, 2017, Combes et al., 2017), and it is arguably harmless as generic problems will typically have a unique optimal mixed action. Another, harmless, assumption is that P, or equivalently, Ext(P), puts some probability mass on each arm a ∈ [K], that is: for each a ∈ [K], there exists a mixed action p ∈ Ext(P) with p a > 0. If this is not the case, then no mixed action in P puts a positive mass on a and a will never be played, thus should be discarded.

Finally, we make the following technical assumption on D, where the set of confusing alternative problems ALT(ν) is defined in (9) below.

Assumption 3.1 For all ν in D, the set ALT(ν) defined in (9) is either empty or contains some ν

such that KL(ν a , ν a ) < +∞ for all a ∈ [K].
This technical assumption is immediately satisfied in many common situations: when D is a convex subset of the set of all probability distributions on the real line (see Appendix E.3 for a proof) or when D is such that KL(ν 0 , ν 0 ) < +∞ for all distributions ν 0 and ν 0 in D, as is the case, for instance, for canonical exponential families indexed by an open interval (this follows from the closed-form expression of KL in that case, see, e.g., Garivier and Cappé, 2011, Lemma 6).

Given the regret upper bounds exhibited in Section 2, it is natural to restrict our attention to uniformly fast convergent [UFC] strategies over D given the diversity-preserving set P: by definition, such strategies ensure that for any bandit problem ν in D, their diversity-preserving regret satisfies R T (ν ) = o(T α ) for all α > 0.

In this section (and its corresponding Appendix E), we index the regret by the underlying bandit problem ν for the sake of clarity and write R T (ν). Whenever needed, we also index expectations E by the underlying bandit problem ν, by writing E ν .

Theorem 2 Assume that the diversity-preserving set P is a finite polytope, generated by the finite set Ext(P), and that it puts some probability mass on each arm a ∈ [K]. For all models D with finite first moments and satisfying Assumption 3.1, for all strategies that are uniformly fast convergent [UFC] over D given P, for all bandit problems ν = (ν 1 , . . . , ν K ) in D with a unique optimal mixed action p (ν), lim inf

T →∞ R T (ν) ln T c Ext(P), ν ,
where c Ext(P), ν ∈ [0, +∞) is defined below in Definition 3 as a constrained infimum.

If p (ν) is such that p a (ν) > 0 for all a ∈ [K], then c Ext(P), ν = 0. The converse implication, that is, the fact that p a (ν) = 0 for some a ∈ [K] entails c Ext(P), ν > 0, also holds when the means of the distributions in D are not bounded from above.

The most interesting part of this theorem is its second part. We know from Case 2 of Theorem 1 that bounded regret is achievable when D = D [0,1] and p a > 0 for all a ∈ [K], which is consistent with c Ext(P), ν = 0. Theorem 2 indicates that the ln T rates are unavoidable in the case when p a = 0 for some a ∈ [K] and when the means of the distributions in D are not bounded from above, which is not the case for the model D [0,1] . Theorems 1 and 2 could cover a common case given by a model D σ 2 -SG composed sub-Gaussian distributions with known variance factor σ 2 with no upper bound on the means; we indeed feel that Theorem 1 could be extended to also cover that case. If so, we would have a true dual behavior for the regret: either bounded or growing as ln T .

Proof of Theorem 2

We provide a rather detailed sketch of proof; two omitted arguments may be found in Appendix E.

Reduction argument. The first step of the proof consists in noting that any strategy picking mixed distributions in the finite polytope P can be converted into a (randomized) strategy picking mixed distributions in the finite set Ext(P) only and providing the same expected cumulative reward, thus suffering the same expected regret R T . This is achieved by an extra randomization step and crucially relies on the fact that any strategy ultimately needs to play a pure action A t at each step (this reduction would not work in linear bandits). Details are to be found in Appendix E.1. We therefore only need to prove the lower bound for (possibly randomized) strategies playing in the finite set Ext(P).

First part of the theorem: à la [START_REF] Graves | Asymptotically efficient adaptive choice of control laws in controlled markov chains[END_REF]. Some of the notation used below was defined earlier in the article, e.g., Opt(ν ) and ∆(p) were defined in (1) and (2), respectively.

We introduce the set of confusing alternative problems associated with the bandit problem ν, denoted by ALT(ν). Problems in ALT(ν) are the ones in which p (ν) is suboptimal, but that the player cannot discriminate from ν by only playing p (ν). Formally, for each arm a, either p a (ν) = 0 and selecting the optimal probability p (ν) never results in picking arm a, or ν a = ν a and observing a reward associated with a does not provide discriminative information:

ALT(ν) = ν in D p (ν) / ∈ Opt(ν ) and ∀ 1 a K, p a (ν) = 0 or ν a = ν a . ( 9
)
Thanks to Theorem 1, we know that the correct scaling of the suboptimal pulls is at most logarithmic; we therefore define the normalized allocations, for all p ∈ Ext(P),

n T (p) = E ν N p (T ) ln T , so that R T ln T = p∈P ∆(p) E ν N p (T ) ln T = p∈P ∆(p) n T (p) . (10)
A UFC algorithm facing the problem ν will eventually focus on the unique optimal mixed action p (ν). Because of this, most of its observations will correspond to pure actions a ∈ [K] such that p a (ν) > 0, which provide no information that is useful to distinguish ν from problems ν ∈ ALT(ν).

A measure of this useful information is the Kullback-Leibler divergence between the distributions of arms A 1 , . . . , A T picked and the rewards Y 1 , . . . , Y T obtained in the first T rounds, P ν,T and P ν ,T , when the underlying problems are ν and ν , respectively. It may be computed thanks to a chain rule, see Equation ( 9) in [START_REF] Garivier | Explore first, exploit next: The true shape of regret in bandit problems[END_REF] for the first equality below, followed by an application of the tower rule for the second equality:

I T = KL P ν,T , P ν ,T = T t=1 E ν KL(ν At , ν At ) = T t=1 E ν K a=1 p t,a KL(ν a , ν a ) . (11)
This quantity can be factored as a sum over the mixed actions p ∈ Ext(P):

I T = p∈Ext(P) E ν N p (T ) a∈[K]
p a KL(ν a , ν a ) = (ln T )

p∈Ext(P) n T (p) a∈[K] p a (ν)=0 p a KL(ν a , ν a ) , (12)
where the final equality holds as by definition, problems ν ∈ ALT(ν) are such that ν a = ν a when p a (ν) > 0. Asymptotically, the algorithm must maintain this amount of information above ln T in order to satisfy the UFC assumption, see details in Appendix E. This puts a constraint on the limit of n T (p) for all p, which may be read in Equation ( 13) below. Given the rewriting (10) of the regret we then get the following definition for the quantity c Ext(P), ν contemplated in Theorem 2.

Definition 3 The constrained infimum c Ext(P), ν in Theorem 2 is defined as:

inf n∈R Ext(P) + p∈Ext(P) ∆(p) n(p) under the constraint that ∀ ν ∈ ALT(ν), p∈Ext(P) p =p (ν) n(p) a∈[K] p a (ν)=0 p a KL(ν a , ν a ) 1 . ( 13
)
We conveyed some intuition on the lower bound indicated by the first part of Theorem 2 and could state the definition of c Ext(P), ν . The rest of the proof, which follows standard techniques introduced by [START_REF] Graves | Asymptotically efficient adaptive choice of control laws in controlled markov chains[END_REF], may be found in Appendix E.2. We now turn to the second part of Theorem 2.

Second part of the theorem: checking whether ALT(ν) is empty or not. We rely on the following equivalence: in the setting and under the conditions of Theorem 2,

c Ext(P), ν = 0 ⇐⇒ ALT(ν) = ∅ . ( 14
)
Proof of (14). Indeed, if ALT(ν) = ∅, then the linear program ( 13) is unconstrained and yields c Ext(P), ν = 0. If ALT(ν) is non-empty, by Assumption 3.1, there exists at least one ν ∈ ALT(ν) such that KL(ν a , ν a ) < +∞ for all a ∈ [K], which we fix. For a vector n ∈ R Ext(P) + to satisfy the constraint (13), it is necessary that

p∈Ext(P) p =p (ν) n(p) a∈[K] p a (ν)=0 p a KL(ν a , ν a ) 1 . ( 15
)
Since

p∈Ext(P) p =p (ν) n(p) a∈[K] p a (ν)=0 p a KL(ν a , ν a ) C ν,ν p∈Ext(P) p =p (ν) ∆(p)n(p) , where C ν,ν = max p∈Ext(P) p =p (ν) 1 ∆(p) a∈[K] p a (ν)=0 p a KL(ν a , ν a ) 1 ∆ max a∈[K]
KL(ν a , ν a ) < +∞ , the constraint (15) entails that p∈Ext(P)

∆(p) n(p) 1 C ν,ν > 0 ,
proving that c Ext(P), ν 1/C ν,ν > 0.

Exploitation of (14). If p a > 0, then the only ν such that p a = 0 or ν a = ν a for all a ∈ [K] is ν itself; that is, ALT(ν) = ∅ and therefore, by ( 14), we have c Ext(P), ν = 0 as stated in the second part of Theorem 2. We now assume that the means of the distributions in D are not bounded from above and show that p a (ν) = 0 for some a ∈ [K] entails that ALT(ν) is non-empty, thus c Ext(P), ν > 0 by ( 14). We fix such an a. By assumption, P thus Ext(P) put some probability mass on this arm a: there exists p ∈ Ext(P) with p a > 0. Since p (ν) is the unique optimal arm of ν, the gap ∆(p) is positive. Now, by the assumption of unbounded means in D, there exists a distribution ν a ∈ D with expectation µ a > µ a + ∆(p)/p a . We denote by ν the bandit problem such that ν k = ν k for all k = a, and whose a-th distribution is ν a . The mixed action p (ν) is suboptimal for ν : we have indeed, by construction of all quantities, by definition of ∆(p), and since p a (ν) = 0 while ν and ν only differ at a,

p, µ = p, µ +(µ a -µ a ) p a > p, µ + ∆(p) p a p a = p, µ +∆(p) = p (ν), µ = p (ν), µ .
That is, p (ν) / ∈ Opt(ν ). We thus proved that ν ∈ ALT(ν), so that ALT(ν) is non-empty.

Some experiments on synthetic data

In this section, we perform some experiments that illustrate the dual behavior of the regret: either bounded or growing at a ln T rate. More precisely, we consider bandit problems ν with a unique optimal mixed action p (ν) and illustrate that in the Bernoulli model considered, either a ln T rate for regret is suffered when p a (ν) = 0 for some arm a ∈ [K], while a bounded regret is achieved when p a (ν) > 0 for all arms a ∈ [K].

Setting considered. We consider K = 3 arms and the diversity-preserving set

P = (p 1 , p 2 , p 3 ) ∈ S : p 1 and p 2 ,
where ∈ (0, 1/2) is a parameter. The set P is a finite polytope generated by

p (1) = , 1 -, 0 , p (2) = 1 -, , 0 , and p (1,2) = , , 1 -2 .
The model D is given by Bernoulli distributions. We will consider bandits problems ν α in D, each of them indexed by α ∈ (-1/6, 1/6). For α < 0, the unique optimal mixed action will be p (1,2) , which satisfies p (1,2) a > 0 for all a ∈ [3], and bounded regret will be achieved. For α > 0, the unique optimal mixed action will be p (2) , which satisfies p

(2) 3 = 0, and a ln T regret will be illustrated. More precisely,

ν α = Ber(1/2 + α), Ber(1/3), Ber(1/2 -α) , with µ α = (1/2 + α, 1/3, 1/2 -α) .
The mixed action p (1) is always dominated by p (2) and p (1,2) : for all α ∈ (-1/6, 1/6),

p (2) -p (1) , µ α = (1 -2 ) 1 2 + α + (2 -1) 1 3 + 0 = (1 -2 ) 1 6 + α > 0 , p (1,2) -p (1) , µ α = 0 + (2 -1) 1 3 + (1 -2 ) 1 2 -α = (1 -2 ) 1 6 -α > 0 .
We now compare the mixed actions p (2) and p (1,2) :

p (1,2) -p (2) , µ α = 2 -1 1 2 + α + 0 + 1 -2 1 2 -α = -2α(1 -2 ) .
Numerical experiments. We set = 0.1 and let α vary in {-0.1, -0.05, 0.05, 0.1}. We run the diversity-preserving UCB algorithm (Algorithm 1) on each of these four problems ν α , over T = 20,000 time steps, for N = 75 runs. The expected regret suffered by the algorithm is estimated by the empirical pseudo-regrets observed on the N = 75 runs:

R T (ν α ) = 1 N N i=1 R T (ν α , i) , where R T (ν α , i) = T t=1 p (ν α ) -p t (α, i), µ α ,
and where we denoted by p t (α, i) the mixed action chosen at round t, during the i-th run, and for problem ν α . The figures below report the estimations obtained (solid lines); we also shaded areas corresponding to ±2 standard errors of the estimates. As expected, the algorithm yields logarithmic regret when α < 0 (the optimal mixed action is on the border of the simplex) and bounded regret when α > 0 (the optimal mixed action lies in the interior of the simplex). where m 2 is a known upper bound on µ 2 2 , and where the gap ∆(x) of an action x ∈ A and the overall gap ∆ among suboptimal actions are defined as

∆(x) = max y∈A y -x, µ and ∆ = min ∆(x) : x ∈ A finite s.t. ∆(x) > 0 .
Note that for a fair comparison with our bounds, we should take m 2 = d = K, as we assume that µ ∞ 1, which only implies µ 2 √ d. A second stream of the linear bandit literature improves asymptotically on the treatment of the situation where A is finite or is a polytope and obtains optimal distribution-dependent bounds that only scale with ln T , but at the cost of computational efficiency. Of course, ln T bounds could have been obtained by playing a plain UCB on A finite , but they would not involve optimal constant in front of the ln T . The results of [START_REF] Lattimore | The end of optimism? An asymptotic analysis of finite-armed linear bandits[END_REF], [START_REF] Combes | Minimal exploration in structured stochastic bandits[END_REF] and [START_REF] Hao | Adaptive exploration in linear contextual bandit[END_REF] fall in this category.

C.2. Other reductions? Literature review on bandits with augmented feedback.

Actually, linear bandits are a particular case of structured bandits, in which observing the reward associated with an action may provide information about the reward of other actions. This is to be opposed to the vanilla K-armed bandit setting. A lot of recent work (discussed below) has been devoted to general structured bandits, sometimes obtaining bounded regret. Since all these approaches apply to the linear bandit setting, they can also be applied to the diversity-bandit setting. However, each come with some limitations, which may be avoided as the diversity-preserving setting is in fact an easier setting than linear bandits. We may cite the works by [START_REF] Hao | Adaptive exploration in linear contextual bandit[END_REF], [START_REF] Jun | Crush optimism with pessimism: Structured bandits beyond asymptotic optimality[END_REF], [START_REF] Tirinzoni | A novel confidence-based algorithm for structured bandits[END_REF], and [START_REF] Lattimore | Bounded regret for finite-armed structured bandits[END_REF]: they all exhibit models (natural exploration in linear contextual bandits and worst-case structures, respectively) in which the introduced algorithms yield bounded regret. However, when applied to the linear bandit problems that emerge from the linear bandit setting, these approaches cannot give bounded regret.

Indeed, and this is the fundamental caveat of applying linear bandit methods, when neglecting the knowledge of A t , the problem faced by the player becomes exactly a linear bandit problem. Therefore, these methods are subject to the linear bandit lower bounds. In particular, for typical (fixed) finite action sets, the lower bound of [START_REF] Lattimore | The end of optimism? An asymptotic analysis of finite-armed linear bandits[END_REF] implies that the regret incurred by linear bandit algorithms must grow logarithmically as T → ∞ on any problem. By contrast, we show that our approach which, uses the knowledge of A t , can yield finite regret. Note also that [START_REF] Caron | Leveraging side observations in stochastic bandits[END_REF] and [START_REF] Degenne | Bandits with side observations: Bounded vs. logarithmic regret[END_REF] consider K-armed bandit models with some extra feedback and provide bounded regret guarantees then. In the rest of this section, we provide some more insights and intuitions on the nature of the improvements obtained when taking this extra piece of information into account.

C.3. Intuitions on why taking A t into account helps

We provide two intuitions, one linked to lower bounds on the regret and the other one linked to the upper bounds on the regret.

As far as lower bounds are concerned. As is clear from the proofs in Section 3, see, e.g., Equation (11), lower bounds rely on the ability to discriminate between two bandit problems ν and ν . Under the problem ν and conditionally to the choice of a distribution p t over the arms, the learner sees the payoff Y t as distributed according to some unconditional distribution when A t is not taken into account, and the conditional distribution ν At when A t is taken into account:

Y t ∼ a∈[K] p t,a ν a and Y t | A t ∼ ν At ,
respectively. Conditionally to the choice of p t , the Kullback-Leibler divergences between the distributions of Y t under ν and ν are therefore given by

KL   a∈[K] p t,a ν a , a∈[K] p t,a ν a   without At E KL(ν At , ν At ) with At = a∈[K] p t,a KL(ν a , ν a ) ,
where the inequality is by convexity of KL. We of course prefer the larger quantity to derive the largest possible limiting constant.

As far as upper bounds are concerned. Here, we discuss more concretely how the knowledge of A t can improve our algorithms: using A t helps building tighter confidence bounds on µ. As a reminder, the confidence region considered in Section 2 is the hyper-rectangle

(µ 1 , . . . , µ K ) ∈ R K : ∀a ∈ [K], | µ a (t) -µ a | 2 ln t max(N a (t), 1) (16)
obtained from the Hoeffding-Azuma inequality and by treating each coordinate separately. Now, LinUCB for linear bandits (see references above) rather relies on an ellipsoid of confidence, constructed as indicated below in (17). Figure 1 compares the confidence regions ( 16) and ( 17) on some simulated data.

Figure 1: Comparison of confidence sets for Bernoulli observations generated from the three probability vectors p 1 = (0.1, 0.9), p 2 = (0.2, 0.8), p 3 = (0.4, 0.6) and true mean vector (µ 1 , µ 2 ) = (0.2, 0.3). Each p i , for i ∈ {1, 2, 3}, was selected 100 times to draw actions A t ∈ {1, 2}, after which rewards Y t ∼ Ber(µ At ) were generated; this thus provided T = 300 observations. The true mean vector is shown as a cross. The red area depicts the ellipsoid defined in (17) without the knowledge of the A t , whereas the green rectangle is the one from ( 16) and relies on the A t . max N a (t), 1

P ∃n ∈ {0, 1, . . . , t} : µ a -µ a,n 2 ln t max{n, 1} t n=1 P µ a -µ a,n 2 ln t max{n, 1} t n=1 2t -4 = 2t -3 ,
where the case n = 0 was dropped for reasons explained below, where the second inequality follows from a union bound and the third inequality, from Hoeffding's inequality. Note indeed that n = 0 and t 2 are incompatible given the event considered: we defined µ a,0 to be 1; when n = 0, the event considered amounts to |1 -µ a | √ 2 ln t, where √ 2 ln t is larger than √ 2 ln 2 > 1 when t 2. The claimed inequality follows from a final union bound over a ∈ [K].

D.1. Case 3: Proof of the upper bound (6) on t 0

We actually also prove a lower bound on t 0 :

16 ∆ 2 -1 t 0 32 ∆ 2 ln 16 ∆ 2 .
This result is a special case of the following more general result, with a = ∆2 /16 < ln(2)/2. Lemma 5 Let a ∈ 0, ln(2)/2 . Define x 0 = sup x ∈ (0, +∞) : ln x > ax and n 0 = max n ∈ {1, 2, 3, . . .} : ln n > an .

Then x 0 -1 n 0 x 0 and 1 a < x 0 < 2 a ln 1 a .

Proof First note that n 0 and x 0 are well defined since ln(2) > 2a (by assumption) and the function ψ : x → ax -ln x satisfies ψ(x) → +∞ as x → +∞. Note also that ψ is continuous, decreasing on (0, 1/a], and increasing on [1/a, +∞).

The inequality x 0 > 1/a follows from ψ(1/a) = 1 + ln a < 0 (since a < ln(2)/2 < 1/e) and by continuity of ψ.

For the stated upper bound on x 0 , we first note that

ψ 2 a ln 1 a = a 2 a ln 1 a -ln 2 a ln 1 a = 2 ln 1 a -ln 1 a -ln 2 ln 1 a <ln(1/a) > 0 ,
where we used that 2 ln u < u for all u > 0. Given that a < 1 and thus that (2/a) ln(1/a) > 1/a, and since ψ is continuous and increasing on [1/a, +∞), the inequality above indeed shows that x 0 < (2/a) ln(1/a). The inequality n 0 x 0 is straightforward by definitions. We now prove that x 0 -1 n 0 . By definition, n 0 is the largest integer n 1 such that ψ(n) < 0, so that ψ(n 0 ) < 0 while ψ(n 0 + 1) 0. Given the variations of ψ, we therefore have that n 0 + 1 is on the increasing branch of ψ, that is, n 0 + 1 1/a. Again since ψ increases on [1/a, +∞) and given that x 0 > 1/a, as well as ψ(x 0 ) = 0 by continuity of ψ, we proved that x 0 n 0 + 1. D.2. Case 2: Proof of the finite sum (8)

We will actually prove a stronger result, namely

P N (t) t 2 = O(1/t 2 ) .
We first tie the number of optimal pulls N (t) to the (non-expected) instantaneous regret: by definition of the minimal gap ∆,

t s=1 p -p s , µ ∆ t s=1 1 {p s ∈Opt(ν)} = ∆ t-N (t) , thus N (t) t- 1 ∆ t s=1 p -p s , µ ,
where p denotes any optimal mixed action. Therefore, we only need to prove that

P t s=1 p -p s , µ ∆t 2 = O(1/t 2 ) . ( 18
)
This is a weak high-probability bound on the non-expected cumulative regret: we only want to show that it grows, with high probability, slower than the linear quantity ∆t/2. We consider to that end the following lemma (which will also be used for the proof of Case 1).

Lemma 6 For s 2, under the event E(s -1) defined in (4),

p -p s , µ 2 a∈[K]
p s,a 2 ln(s -1) max N a (s -1), 1 .

Proof By definition of the algorithm, we have p -p s , U (s -1) 0, so that p -p s , µ = p , µ -U (s -1) + p -p s , U (s -1)

0 + p s , U (s -1) -µ . Now, under E(s -1), ∀a ∈ [K], 0 U a (s -1) -µ a = µ a (s -1) + 2 ln(s -1) max N a (s -1), 1 -µ a 2 2 ln(s -1) max N a (s -1), 1
.

Therefore, under E(s -1), substituting in the first bound of this proof, we get

p -p s , µ p , µ -U (s -1) + p s , U (s -1) -µ 0 + 2 a∈[K]
p s,a ln(s -1) max N a (s -1), 1 .

Recall the aim (18). Since the events E(s -1) in Lemma 6 might have a non-negligible probability for small values of s, we leave out the first τ t := ∆t/4 rounds (note that τ t 1 for t 4/∆). More precisely, in order to prove (18), noting that p -p s , µ lies in [-1, 1] as ν lies in D [0,1] , it suffices to show that

P t s=τt p -p s , µ ∆t 4 = O(1/t 2 ) .
By Lemma 6, and noting that τ t 2 for t 8/∆, we thus only need to prove that

P t s=τt E(s -1) + P    2 t s=τt a∈[K]
p s,a 2 ln(s -1) max N a (s -1), 1 ∆t 4

   = O(1/t 2 ) .
By a union bound and given the fact that P E(s) 2Ks -3 by Lemma 4, the first probability above is at most of K(τ t -1) -2 = O(1/t 2 ). Therefore, it suffices to prove that: 3

P    2 t s=2 a∈[K] p s,a 2 ln(s -1) max N a (s -1), 1 ∆t 4    = O(1/t 2 ) . ( 19
)
We apply the Hoeffding-Azuma inequality (see, e.g., Lemma A.7 in [START_REF] Cesa | Prediction, Learning, and Games[END_REF] to the martingale

M t def = 2 t s=2 a∈[K]
p s,a -1 {As=a} 2 ln(s -1) max N a (s -1), 1 with (predictable) increments lying in a range of width smaller than 2 √ 2 ln t and by picking a risk level of δ t = t -4 ; we obtain:

P M t 2 √ 2 ln t √ 2t ln t t -4 . (20)
Now, for each a ∈ [K], as N a (s-1) only increases (by 1) when A s = a, and since N a (t-1) t-1, we have the deterministic (crude) bound

C t def = 2 t s=2 1 {As=a} 2 ln(s -1) max N a (s -1), 1 2 √ 2 ln t t s=2 1 {As=a} max N a (s -1), 1 2 √ 2 ln t t-1 n=0 1 max{n, 1} 2
√ 2 ln t 1 + 2 √ t -1 . (21)
All in all, with the processes M t and C t introduced above,

   2 t s=2 a∈[K] p s,a 2 ln(s -1) max N a (s -1), 1 ∆t 4    = C t + M t ∆t 4 . The sum 2 √ 2 ln t √ 2t ln t + 2 √ 2 ln t 1 + 2 √ t -1 = O √ t ln t
of the high-probability bound exhibited on M t and of the deterministic bound exhibited on C t is smaller than ∆t/4 after some step t 0 . Hence, for t t 0 , the value ∆t/4 cannot be achieved unless the high-probability bound on M t does not hold:

C t + M t ∆t 4 ⊆ M t 2 √ 2 ln t √ 2t ln t .
This remark, together with the deviation bound (20), proves that the sufficient aim ( 19) is true. This concludes the proof of Case 2.

D.3. Case 1: Complete proof

The beginning of this proof follows a standard proof scheme for linear bandits. For t 1, we denote by r t = p -p t , µ the (non-expected) instantaneous regret; it was already considered in Lemma 6. The regret to be controlled corresponds to

R T (ν) = E T t=1 r t .
We requested in the definition of Algorithm 1 that mixed actions be selected only in Ext(P). Doing so, the (non-expected) instantaneous regret suffered from playing p t ∈ Ext(P) is either 0, if p t is optimal, or at least ∆ if p t is suboptimal. This simple observation leads to the crude upper bound

r t r 2 t ∆ .
Now, under E(t -1), Lemma 6 followed by an application of the Cauchy-Schwarz inequality yield

r 2 t   2 a∈[K] p t,a 2 ln(t -1) max N a (t -1), 1   2 8   a∈[K] p t,a max N a (t -1), 1     a∈[K] p t,a ln(t -1)   8   a∈[K] p t,a max N a (t -1), 1   ln T .
Since A t is drawn at random given p t , which is determined by the information available at the beginning of round t, just as N a (t -1) is, the tower rule indicates that for all t 1 and a ∈

[K], E p t,a max N a (t -1), 1 = E 1 {At=a} max N a (t -1), 1 .
Taking into account the fact that when E(t -1) is not satisfied, we have r 2 t 1 as ν lies in D [0,1] , we proved so far

E r 2 t P E(t -1) + 8 a∈[K] E 1 {At=a} max N a (t -1), 1 ln T.
Lemma 4 shows that P E(t -1) 2K(t -1) -3 for t 3 (and we resort to the trivial bound 1 for t = 1 or t = 2). Now come the final steps of the proof: they are specific to our diversity-preserving setting and short-cut the classical proof scheme. The same kind of deterministic argument as used in (21) shows that for each a ∈

[K], T t=1 1 {At=a} max N a (t -1), 1 = Na(T -1) n=0 1 max{n, 1} 2 + ln max N a (T -1), 1 2 + ln 1 + N a (T -1) ,
where we used that 1 + 1/2 + . . . + 1/N 1 + ln N for N 1. Collecting all bounds together, we proved

T t=1 E r 2 t 2 + 2K T t=3 (t -1) -3 <1/2 +8 a∈[K] 2 + E ln 1 + N a (T -1) ln T .
By concavity of the logarithm,

1 K a∈[K] ln 1 + N a (T -1) ln 1 + 1 K a∈[K] N a (T -1) =T -1 ln(1 + T /K) .
Proof We denote by kl(p, q) = p ln(p/q) + (1 -p) ln (1 -p)/(1 -q) the Kullback-Leibler divergence between two Bernoulli distributions with parameters p and q. By the data-processing inequality for [0, 1]-valued random variables (see Section 2.1 in [START_REF] Garivier | Explore first, exploit next: The true shape of regret in bandit problems[END_REF] and by the standard inequality kl(p, q) p ln(1/q) -ln 2,

KL P ν,T , P ν ,T kl E ν N p (ν) (T ) T , E ν N p (ν) (T ) T E ν N p (ν) (T ) T ln   T E ν N p (ν) (T )   -ln 2 .
The strategy is UFC, we therefore have R T (ν)/T → 0. Given the decomposition (3) of the regret and given that ∆(ν) > 0 for all ν ∈ Ext(P) with ν = p (ν) since p (ν) is the only optimal action for ν, we have, on the one hand,

E ν N p (ν) (T ) T ----→ T →∞
1 .

On the other hand, given that p (ν) is suboptimal for ν , the suboptimality gap ∆ ν p (ν) of p (ν) in the bandit problem ν is positive and

R T (ν ) ∆ ν p (ν) E ν N p (ν) (T ) , or equivalently, E ν N p (ν) (T ) R T (ν ) ∆ ν p (ν)
.

The strategy being UFC, we have R T (ν ) = o(T α ) for all α > 0; in particular, for all ε > 0, for all T large enough, E ν N p (ν) (T ) T ε . Putting all inequalities together, we proved is defined in some arbitrary way (its value will be irrelevant). Now, given ν ∈ ALT(ν), the quantity I T defined in (11) and rewritten in (12) satisfies, in view of Lemma 7: Note that because of the inner summation over the a such that p a (ν) = 0, the summation in the left-most term can be restricted to p ∈ Ext(P) with p = p (ν): All in all, considering rather the subsubsequence (T m k ) k 1 , we get, by identity of the lim inf, This holds for all ν ∈ ALT(ν) and shows that the vector n(p) p∈Ext(P) thus satisfies the constraints (13).

In conclusion and in view of the decomposition (10), we have just shown that all finite cluster points c of R T / ln T are of the form p∈Ext(P)

∆(p) n(p)

for some n(p) p∈Ext(P) ∈ R

Ext(P) +

satisfying the constraints (13).

Note that the value for n(p ) is irrelevant as ∆ p (ν) = 0. Hence, the lim inf is in particular larger than or equal to the infimum over these quantities, which is exactly the quantity c Ext(P), ν defined in Definition 3.

E.3. Proof that Assumption 3.1 holds true when D is convex

In this section we assume that D is a convex subset of the set of all probability distributions on the real line, and show that Assumption 3.1 holds true.

Let ν be a bandit problem in D, assume that the set ALT(ν) is non-empty, and consider any ν ∈ ALT(ν). Next we show that for λ ∈ (0, 1) sufficiently small, the modified problem

ν = (1 -λ)ν + λν (22)
(which still belongs to D by convexity of D) meets the requirements of Assumption 3.1. Indeed, first note that for all λ ∈ (0, 1) and all a ∈ [K], the Radon-Nikodym derivative dν a /dν a is bounded by 1/λ, so that KL(ν a , ν a ) ln(1/λ) < +∞ .

To conclude, it suffices to show that ν ∈ ALT(ν). First, for all actions a ∈ [K] such that p a (ν) > 0, we have ν a = ν a = ν a since ν ∈ ALT(ν) and given the definition (22). Second, p (ν) / ∈ Opt(ν ) for λ small enough: as ν ∈ ALT(ν), we have by definition p (ν) / ∈ Opt(ν ), which means that there exists p ∈ P such that p, µ > p (ν), µ , while p, µ p (ν), µ .

However, taking λ ∈ (0, 1) small enough will still guarantee p, µ > p (ν), µ for λ. We thus showed that ν ∈ ALT(ν) for λ > 0 small enough. All the above entails that ν meets the requirements of Assumption 3.1, which concludes the proof.

  result follows by taking ε → 0.Part B: Considering cluster points. We conclude the proof of the first part of Theorem 2. Let c be a cluster point of the sequence R T / ln T . If c = +∞ is the only value, then R T / ln T → +∞ and the result is proved. Otherwise, take a finite c. We denote by (T m ) m 1 an increasing sequence such that R Tm / ln T m → c. In view of the decomposition (10) and since ∆(p) > 0 and n Tm (p) 0 for all p ∈ Ext(P) with p = p (ν), these sequences n Tm (p) are bounded. Hence, we may extract a subsequence (T m k ) k 1 from (T m ) such that all sequences n Tm k (p) converge as k → ∞, to limits denoted by n(p). This only holds for p ∈ Ext(P) with p = p (ν). The final component n p (ν)

  p a (ν)=0 p a KL(ν a , ν a ) .

  p a KL(ν a , ν a ) 1 .

Sometimes called optional sampling.

Adding the (nonnegative) terms from s = 2 to s = τt -1 in the sum makes the goal only harder.

Acknowledgments

The work of Sébastien Gerchinovitz and Jean-Michel Loubes has benefitted from the AI Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future -PIA3" program under the Grant agreement ANR-19-PI3A-0004. Sébastien Gerchinovitz gratefully acknowledges the support of the DEEL project (https://www.deel.ai/).

Outline of the appendix

Appendix A discusses distribution-free regret upper bounds. Appendix B provides an extended literature review on the notions of diversity and fairness in bandits. Appendix C is an extended comparison to the linear bandit setting used by [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] and also provides a literature review on structured stochastic bandits. Appendix D includes all remaining parts of the proofs of the regret upper bounds of Theorem 1. Appendix E does so for the lower bound of Theorem 2.

Appendix A. Distribution-free regret upper bounds

We say that a strategy enjoys a distribution-free regret bound B(D, P, T ) on the model D given the diversity-preserving set P when it guarantees, for all T 1, sup ν in D R T (ν) B(D, P, T ) .

All claims that follow are extracted from Hadiji (2020, Chapter 5).

The diversity-preserving UCB (Algorithm 1) enjoys a distribution-free regret bound of order √ KT ln T , while a variant based on the MOSS strategy of [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF] achieves a √ KT bound.

A follow-the-regularizer-leader [FTRL] approach, similar to the one considered by [START_REF] Chen | Fair contextual multi-armed bandits: Theory and experiments[END_REF] and relying on a regularization function

p a ln p a , achieved a distribution-free regret bound of order diam H (P) KT , where diam H (P) = max H(p) -H(q) : p, q ∈ P is the diameter of P for the regularizer H. (It is in particular smaller than ln K.) This FTRL bound actually also holds for adversarial bandits. Our results are incomparable with the ones by Chen et al. ( 2020): on the one hand, we consider more general diversity-preserving sets (they essentially consider the first and simplest example of Section 1.1, with minimal probabilities); on the other hand, they consider a contextual bandit setting.

A distribution-free regret lower bound of order

may be proved, using standard techniques from [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF].

Statement of an open question. The optimal dependency of the distribution-free regret bounds on K and T is therefore √ KT for worst-case P. However we were unable so far to identify the optimal dependency on the geometry of P in general.

Appendix B. Literature review on the notions of diversity and fairness in bandits Diversity. Closest to our work is the recent article of [START_REF] Chen | Fair contextual multi-armed bandits: Theory and experiments[END_REF], that studies a particular case of the diversity-preserving setting, which essentially corresponds to our example called "Maintaining a budget" described in Section 1. While their framework is the same as ours, they only study distribution-free bounds and provide numerical experiments, making their focus orthogonal to our one. Note also that their algorithm, inspired by the mirror descent framework, actually applies to the rewards generated in an adversarial manner.

In the domain of stochastic bandits, we may cite the contributions of [START_REF] Patil | Achieving fairness in the stochastic multi-armed bandit problem[END_REF] and [START_REF] Claure | Reinforcement learning with fairness constraints for resource distribution in human-robot teams[END_REF]. They derive bandit algorithms that ensure that the proportion of times each action is selected is lower bounded, i.e., with our notation that N a (T )/T α almost surely. Although the objective is similar in spirit, this constraint leads to design issues for the algorithm that are quite different from ours, and are arguably less mathematically elegant. Our setting enforces similar guarantees while bypassing these issues. Finally, [START_REF] Li | Combinatorial sleeping bandits with fairness constraints[END_REF] consider a problem called combinatorial sleeping bandits, in which the player may pick multiple actions among the K available at every step. The authors also impose that their algorithms satisfy some diversity preserving condition on the choice of the actions, but this condition is only asymptotical.

Note that all these articles refer to "fairness", although we prefer the term "diversity-preserving" to distinguish them from the stream of work discussed below.

Fairness. The framework of individual fairness from [START_REF] Dwork | Fairness through awareness[END_REF] relies on the idea that "similar individuals should be treated similarly" (there, actions correspond to individuals). This was modeled in stochastic bandits by imposing constraints on the unknown problem, with constraints dictated by the very nature of the problem, hence, being unknown as well. Therefore, the algorithms will need to explore some more in order to learn the constraints while playing the bandit game. The usual tradeoff between exploration and exploitation is therefore modified. We may cite contributions by [START_REF] Joseph | Fairness in learning: Classic and contextual bandits[END_REF], [START_REF] Amani | Linear stochastic bandits under safety constraints[END_REF], [START_REF] Liu | Calibrated fairness in bandits[END_REF] and [START_REF] Gillen | Online learning with an unknown fairness metric[END_REF]. This approach is mathematically quite different from the setting considered in this article.

Appendix C. Extended comparison to the linear bandit setting used by [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] and literature review on structured stochastic bandits [START_REF] Celis | Controlling polarization in personalization: An algorithmic framework[END_REF] suggest using linear bandit algorithms in the diversity-preserving setting, unlocking a wide array of methods and regret guarantees. Indeed, they observe that one can discard the knowledge of the true played action A t and only play using the observation of the rewards Y t and of the mixed action p t . Doing so, the player plays a game where the expected reward associated with the played action p t depends linearly on the said action: this setting is known as linear bandits and is recalled below. An exception to this approach is their CONSTRAINED-ε-GREEDY algorithm, which does use the knowledge of A t but suffers from two limitations: its regret bound scales as 1/∆ 2 instead of 1/∆ and, more importantly, it requires a lower bound on the unknown minimal gap ∆, which makes it quite impractical compared to other knowledge-independent algorithms.

In this appendix, we recall the setting of linear bandits and provide a brief account of the relevant literature on it. We also review the existing literature on other structured bandit settings and bandits with augmented feedback. We then provide intuitions on the limitations of using a reduction to linear bandits for the diversity-preserving bandit game.

C.1. The setting of linear bandits

We refer the interested reader to the monograph by Lattimore and Szepesvári, 2020, Chapter 19 for a longer description. An action set A ⊂ R d is given to the learner. Some parameter µ ∈ R d is set but remains unknown to the learner. The latter selects at each step an action X t ∈ A and gets and observes a random reward Y t such that E[Y t | X t ] = X t , µ . The expected regret is defined as

Reduction. The diversity-preserving bandit protocol described in Section 1 can be put in this setting, by having the chosen probability vector p t play the role of X t . The ambient dimension is then essentially d = K. (Notice in particular that the notions of regret coincide.) Therefore, the learner can choose to ignore completely the observation of A t and use a linear bandit algorithm of her choice, thus transferring the regret guarantees to the diversity-preserving setting. We now discuss the typical regret guarantees achieved in linear bandits.

is sub-Gaussian (with constant less than 1/4, say). They obtain finite-time distribution-dependent bounds in the case where A is finite or is a finite polytope; we denote by A finite a finite set of points generating A when it is a finite polytope and let A finite = A when A is finite. These finite-time distribution-dependent bounds are of the form: there exists a numerical constant C such that for each bandit problem in L,

We denote by X t the matrix whose rows are the mixed actions used over time, p 1 , . . . , p t , and let Y 1:t = (Y 1 , . . . , Y t ) be the column vector of rewards obtained. Then, for a parameter λ > 0, we define

The ellipsoid considered is then of the form

where f √ ln (t) is some closed-form function of order √ ln t.

Appendix D. Full proof of the upper bounds

For the common part of the proofs of Cases 2 and 3, the following lemma was used. It is standard in the literature of vanilla K-armed bandits: we simply note that it also holds in our setting. As we have no direct control on arms pulled, we cannot ensure in a deterministic manner that N a (t) 1 a.s., hence we take the maximum between N a (t) and 1.

Lemma 4 Consider a bandit problem ν in D [0,1] . For t 2, if the actions A 1 , . . . , A t and rewards Y 1 , . . . , Y t were generated according to Protocol 1, then

Proof By optional skipping 2 (see Theorem 5.2 of Doob, 1953, Chapter III, p. 145, see also Chow and Teicher, 1988, Section 5.3), we can replace the random quantities depending on the observations from a fixed arm by their i.i.d. analogue. More precisely, for each arm a ∈ [K], by defining µ a,n as an empirical average of n i.i.d. random variables with distribution ν a , we have

We summarize all calculations performed so far into:

The final bound is transformed into the stated 2+K +24K ln(1+T ) 2 /∆ for better readability.

Appendix E. Full proof of the lower bound

E.1. Proof of the reduction

We first note that in Protocol 1, whether a strategy picks a deterministic mixed action p t (based on the past) or a distribution ρ t over mixed actions in P is irrelevant, as the strategy needs to draw an arm A t and only observes the payoff obtained by picking A t . In the first case, A t is drawn in a one-step randomization, while in the second case, A t is drawn in a two-step randomization which is equivalent to picking the deterministic mixed action

When a strategy picks mixed actions in P, whether it is deterministic or randomized is irrelevant.

Based on the same intuition, we now show that it suffices to restrict one's attention to strategies playing in the finite set Ext(P) generating P. Any mixed action q = p t may be decomposed as a convex combination of elements of Ext(P). We may define a function Φ : q ∈ P -→ Φ(q) = Φ p (q) p∈Ext(P) ∈ [0, 1] Ext (P) such that all images Φ(q) are actually convex weights and ∀q ∈ P, q = p∈Ext(P)

Φ p (q) p .

We may interpret convex weights Φ(q) as probability distributions over Ext(P). With this in mind, we note that a (deterministic) strategy ψ picking mixed actions p t (based on the information available: past actions A s and rewards Y s , with s t -1) gets the same expected payoffs as the (randomized) strategy ψ Φ that first picks a mixed action P t in Ext(P) at random according to Φ(p t ), and then draws the action A t according to P t . This, again, holds because only the choice of the pure action A t matters. In particular, if the strategy ψ is UFC over D given P, then so is ψ Φ . The final issue to clarify is that the proof of Theorem 2 following this reduction holds for deterministic and randomized strategies ψ Φ (again because only the actions A t drawn matter).

E.2. Rest of the proof of the first part of Theorem 2

This proof scheme is standard and was introduced by [START_REF] Graves | Asymptotically efficient adaptive choice of control laws in controlled markov chains[END_REF].

Part A: The divergence I T is larger than ln T in the limit. We prove that I T = KL P ν,T , P ν ,T is asymptotically larger than ln T .

Lemma 7 For all models D with finite first moments, for all diversity-preserving sets P, for all strategies that are uniformly fast convergent [UFC] over D given P, for all bandit problems ν in D with a unique optimal action p (ν), for all bandit problems ν in D for which p (ν) is suboptimal, lim inf T →∞ KL P ν,T , P ν ,T ln T 1 .