Antoine Salomon
email: salomona@imagine.enpc.fr

Jean-Yves Audibert
email: audibert@imagine.enpc.fr

Robustness of Anytime Bandit Policies

Keywords: exploration-exploitation tradeoff, multi-armed stochastic bandit, regret deviations/risk

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Bandit problems illustrate the fundamental difficulty of sequential decision making in the face of uncertainty: a decision maker must choose between following what seems to be the best choice in view of the past ("exploitation") or testing ("exploration") some alternative, hoping to discover a choice that beats the current empirical best choice. More precisely, in the stochastic multi-armed bandit problem, at each stage, an agent (or decision maker) chooses one action (or arm), and receives a reward from it. The agent aims at maximizing his rewards. Since he does not know the process generating the rewards, he does not know the best arm, that is the one having the highest expected reward. He thus incurs a regret, that is the difference between the cumulative reward he would have got by always drawing the best arm and the cumulative reward he actually got. The name "bandit" comes from imagining a gambler in a casino playing with K slot machines, where at each round, the gambler pulls the arm of any of the machines and gets a payoff as a result.

The multi-armed bandit problem is the simplest setting where one encounters the exploration-exploitation dilemma. It has a wide range of applications including advertisement [START_REF] Babaioff | Characterizing truthful multiarmed bandit mechanisms: extended abstract[END_REF][START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF], economics [START_REF] Bergemann | Bandit problems[END_REF][START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF], games [START_REF] Gelly | Exploration exploitation in go: UCT for Monte-Carlo go[END_REF] and optimization [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF][START_REF] Coquelin | Bandit algorithms for tree search[END_REF][START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF][START_REF] Bubeck | Online optimization in X-armed bandits[END_REF]. It can be a central building block of larger systems, like in evolutionary programming [START_REF] Holland | Adaptation in natural and artificial systems[END_REF] and reinforcement learning [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], in particular in large state space Markovian Decision Problems [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. Most of these applications require that the policy of the forecaster works well for any time. For instance, in tree search using bandit policies at each node, the number of times the bandit policy will be applied at each node is not known beforehand (except for the root node in some cases), and the bandit policy should thus provide consistently low regret whatever the total number of rounds is.

Most previous works on the stochastic multi-armed bandit [21, 17, 1, 3, among others] focused on the expected regret, and showed that after n rounds, the expected regret is of order log n. So far, the analysis of the upper tail of the regret was only addressed in Audibert et al. [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF]. The two main results there about the deviations of the regret are the following. First, after n rounds, for large enough constant C > 0, the probability that the regret of ucb1 (and also its variant taking into account the empirical variance) exceeds C log n is upper bounded by 1/(log n) C for some constant C depending on the distributions of the arms and on C (but not on n). Besides, for most bandit problems, this upper bound is tight to the extent that the probability is also lower bounded by a quantity of the same form. Second, a new upper confidence bound policy was proposed: it requires to know the total number of rounds in advance and uses this knowledge to design a policy which essentially explores in the first rounds and then exploits the information gathered in the exploration phase. Its regret has the advantage of being more concentrated to the extent that with probability at least 1 -1/n, the regret is of order log n. The problem left open by [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF] is whether it is possible to design an anytime robust policy, that is a policy such that for any n, with probability at least 1 -1/n, the regret is of order log n. In this paper, we answer negatively to this question when the reward distributions of all arms are just assumed to be uniformly bounded, say all rewards are in [0, 1] for instance (Corollary 3.4). We then study which kind of restrictions on the set of probabilities defining the bandit problem allows to answer positively. One of our positive results is the following: if the agent knows the value of the expected reward of the best arm (but does not know which arm is the best one), the agent can use this information to design an anytime robust policy (Theorem 4.3). We also show that it is not possible to design a policy such that the regret is of order log n with a probability that would significantly greater than 1 -1/n, even if the agent knows the total number of rounds in advance (Corollary 5.2). The paper is organised as follows: in the first section, we formally describe the problem we address and give the corresponding definitions and properties. Next we present our main impossibility result. In the third section, we provide restrictions under which it is possible to design anytime robust policies. In the fourth section, we study the robustness of policies that can use the knowledge of the total number of rounds. Then we provide experiments to compare our robust policy to the classical UCB algorithms. The last section is devoted to the proofs of our results.

Problem setup and definitions

In the stochastic multi-armed bandit problem with K ≥ 2 arms, at each time step t = 1, 2, . . . , an agent has to choose an arm I t in the set {1, . . . , K} and obtains a reward drawn from ν It independently from the past (actions and observations). The environment is thus parameterized by a K-tuple of probability distributions θ = (ν 1 , . . . , ν K ). The agent aims at maximizing his rewards. He does not know θ but knows that it belongs to some set Θ. We assume for simplicity that Θ ⊂ Θ, where Θ denotes the set of all K-tuple of probability distributions on [0, 1]. We thus assume that the rewards are in [0, 1].

For each arm k and all times t ≥ 1, let T k (t) = t s=1 1 Is=k denote the number of times arm k was pulled from round 1 to round t, and X k,1 , X k,2 , . . . , X k,T k (t) the sequence of associated rewards. For an environment parameterized by θ = ν 1 , . . . , ν K ), let P θ denote the distribution on the probability space such that for any k ∈ {1, . . . , K}, the random variables X k,1 , X k,2 , . . . are i.i.d. realizations of ν k , and such that these K infinite sequence of random variables are independent. Let E θ denote the associated expectation. Let µ k = xdν k (x) be the mean reward of arm k. Introduce µ * = max k µ k and fix an arm k * ∈ argmax k∈{1,...,K} µ k , that is k * has the best expected reward. The suboptimality of arm k is measured by ∆ k = µ *µ k . The agent aims at minimizing its regret defined as the difference between the cumulative reward he would have got by always drawing the best arm and the cumulative reward he actually got. At time n ≥ 1, its regret is thus

Rn = n t=1 X k * ,t - n t=1 X It,T I t (t) . (1)
The expectation of this regret has a simple expression in terms of the suboptimalities of the arms and the expected sampling times of the arms at time n. Precisely, we have

E θ Rn = nµ * - n t=1 E θ (µ It ) = nµ * -E θ K k=1 T k (n)µ k = µ * K k=1 E θ [T k (n)] - K k=1 µ k E θ [T k (n)] = K k=1 ∆ k E θ [T k (n)].
Other notions of regret exists in the literature: the quantity

K k=1 ∆ k T k (n)
is called the pseudo regret and may be more practical to study, and the quantity max k n t=1 X k,t -n t=1 X It,T I t (t) defines the regret in adverserial settings. Results and ideas we want to convey here are more suited to definition [START_REF] Audibert | Sample mean based index policies with o(log n) regret for the multi-armed bandit problem[END_REF], and taking another definition of the regret would only bring some more technical intricacies.

Our main interest is the study of the deviations of the regret Rn , i.e. the value of P θ ( Rn ≥ x) when x is larger and of order of E θ Rn . If a policy has small deviations, it means that the regret is small with high probability and in particular, if the policy is used on some real data, it is very likely to be small on this specific dataset. Naturally, small deviations imply small expected regret since we have

E θ Rn ≤ E θ max( Rn , 0) = +∞ 0 P θ Rn ≥ x dx.
To a lesser extent it is also interesting to study the deviations of the sampling times T n (k), as this shows the ability of a policy to match the best arm. Moreover our analysis is mostly based on results on the deviations of the sampling times, which then enables to derive results on the regret. We thus define below the notion of being f -upper tailed for both quantities. Define R * + = {x ∈ R : x > 0}, and let ∆ = min k =k * ∆ k be the gap between the best arm and second best arm.

Definition 1 (f -T and f -R). Consider a mapping f : R → R * + . A policy has f -upper tailed sampling Times (in short, we will say that the policy is f -T ) if and only if

∃C, C > 0, ∀θ ∈ Θ such that ∆ = 0, ∀n ≥ 2, ∀k = k * , P θ T k (n) ≥ C log n ∆ 2 k ≤ C f (n) .
A policy has f -upper tailed Regret (in short, f -R) if and only if

∃C, C > 0, ∀θ ∈ Θ such that ∆ = 0, ∀n ≥ 2, P θ Rn ≥ C log n ∆ ≤ C f (n) .
We will sometimes prefer to denote f (n)-T (resp. f (n)-R) instead of f -T (resp. f -R) for readability. Note also that, for sake of simplicity, we leave aside the degenerated case of ∆ being null (i.e. when there are at least two optimal arms).

In this definition, we considered that the number K of arms is fixed, meaning that C and C may depend on K. The thresholds considered on T k (n) and Rn directly come from known tight upper bounds on the expectation of these quantities for several policies. To illustrate this, let us recall the definition and properties of the popular ucb1 policy. Let Xk,s = 1 s s t=1 X k,t be the empirical mean of arm k after s pulls. In ucb1, the agent plays each arm once, and then (from t ≥ K + 1), he plays

I t ∈ argmax k∈{1,...,K} Xk,T k (t-1) + 2 log t T k (t -1) . ( 2
)
While the first term in the bracket ensures the exploitation of the knowledge gathered during steps 1 to t -1, the second one ensures the exploration of the less sampled arms. For this policy, Auer et al. [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] proved:

∀n ≥ 3, E[T k (n)] ≤ 12 log n ∆ 2 k and E θ Rn ≤ 12 K k=1 log n ∆ k ≤ 12K log n ∆ .
Lai and Robbins [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] showed that these results cannot be improved up to numerical constants. Audibert et al. [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF] proved that ucb1 is log 3 -T and log 3 -R where log 3 is the function x → [log(x)] 3 . Besides, they also study the case when 2 log t is replaced by ρ log t in (2) with ρ > 0, and proved that this modified ucb1 is log 2ρ-1 -T and log 2ρ-1 -R for ρ > 1/2, and that ρ = 1 2 is actually a critical value. Indeed, for ρ < 1/2 the policy does not even have a logarithmic regret guarantee in expectation. Another variant of ucb1 proposed by Audibert et al. is to replace 2 log t by 2 log n in (2) when we want to have low and concentrated regret at a fixed given time n. We refer to it as ucb-h as its implementation requires the knowledge of the horizon n of the game. The behaviour of ucb-h on the time interval [1, n] is significantly different to the one of ucb1, as ucb-h will explore much more at the beginning of the interval, and thus avoids exploiting the suboptimal arms on the early rounds. Audibert et al. showed that ucb-h is n-T and n-R (as it will be recalled in Theorem 3.5). As it will be confirmed by our results, whether a policy knows in advance the horizon n or not matters a lot, that is why we introduce the following terms. Definition 2. A policy that uses the knowledge of the horizon n (e.g. ucb-h) is a horizon policy. A policy that does not use the knowledge of n (e.g. ucb1) is an anytime policy.

We now introduce the weak notion of f -upper tailed as this notion will be used to get our strongest impossibility results.

Definition 3 (f -wT and f -wR). Consider a mapping f : R → R * + . A policy has weak f -upper tailed sampling Times (in short, we will say that the policy is f -wT ) if and only if

∀θ ∈ Θ such that ∆ = 0, ∃C, C > 0, ∀n ≥ 2, ∀k = k * , P θ T k (n) ≥ C log n ∆ 2 k ≤ C f (n) .
A policy has weak f -upper tailed Regret (in short, f -wR) if and only if

∀θ ∈ Θ such that ∆ = 0, ∃C, C > 0, ∀n ≥ 2, P θ Rn ≥ C log n ∆ ≤ C f (n) .
The only difference between f -T and f -wT (and between f -R and f -wR) is the interchange of "∀θ" and "∃C, C". Consequently, a policy that is f -T (respectively f -R) is f -T (respectively f -wR). Let us detail the links between the f -T , f -R, f -wT and f -wR. Proposition 2.1. Assume that there exists α, β > 0 such that f (n) ≤ αn β for any n ≥ 2. We have

f -T ⇒ f -R ⇒ f -wR ⇔ f -wT .
The proof of this proposition is technical but rather straightforward. Note that we do not have f -R ⇒ f -T , because the agent may not regret having pulled a suboptimal arm if the latter has delivered good rewards. Note also that f is required to be at most polynomial: if not some rare events such as unlikely deviations of rewards towards their actual mean can not be neglected, and none of the implications hold in general (except, of course, f -R ⇒ f -wR and f -T ⇒ f -wT ).

Impossibility result

Here and in section 4 we mostly deal with anytime policies, and the word policy (or algorithm) implicitly refers to anytime policy. In the previous section, we have mentioned that for any ρ > 1/2, there is a variant of ucb1 (obtained by changing 2 log t into ρ log t in (2)) which is log 2ρ-1 -T . This means that, for any α > 0, there exists a log α -T policy, and a hence log α -R policy. The following result shows that it is impossible to find an algorithm that would have better deviation properties than these ucb policies. For many usual settings (e.g., when Θ is the set Θ of all K-tuples of measures on [0, 1]), with not so small probability, the agent gets stuck drawing a suboptimal arm he believes best. Precisely, this situation arises when simultaneously: (a) an arm k delivers payoffs according to a same distribution ν k in two distinct environments θ and θ, (b) arm k is optimal in θ but suboptimal in θ, (c) in environment θ, other arms may behave as in environment θ, i.e. with positive probability other arms deliver payoffs that are likely in both environments.

If the agent suspects that arm k delivers payoffs according to ν k , he does not know if he has to pull arm k again (in case the environment is θ) or to pull the optimal arm of θ. The other arms can help to point out the difference between θ and θ, but then they have to be chosen often enough. This is in fact this kind of situation that has to be taken into account when balancing a policy between exploitation and exploration.

Our main result is the formalization of the leads given above. In particular, we give a rigorous description of conditions (a), (b) and (c). Let us first recall the following results, which are needed in the formalization of condition (c). One may look at [START_REF] Rudin | Real and complex analysis (3rd)[END_REF], p.121 for details (among others). Those who are not familiar with measure theory can skip to the non-formal explanation just after the results. Theorem 3.1 (Lebesgue-Radon-Nikodym theorem). Let µ 1 and µ 2 be σ-finite measures on a given measurable space. There exists a µ 2 -integrable function dµ1 dµ2 and a σ-finite measure m such that m and µ 2 are singular 1 and

µ 1 = dµ 1 dµ 2 • µ 2 + m.
The density dµ1 dµ2 is unique up to a µ 2 -negligible event.

We adopt the convention that dµ1 dµ2 = +∞ on the complementary of the support of µ 2 . Lemma 3.2. We have

• µ 1 dµ1 dµ2 = 0 = 0. • µ 2 dµ1 dµ2 > 0 > 0 ⇔ µ 1 dµ2 dµ1 > 0 > 0.
Proof. The first point is a clear consequence of the decomposition µ 1 = dµ1 dµ2 • µ 2 + m and of the convention mentioned above. For the second point, one can write by uniqueness of the decomposition:

µ 2 dµ 1 dµ 2 > 0 = 0 ⇔ dµ 1 dµ 2 = 0 µ 2 -a.s. ⇔ µ 1 = m ⇔ µ 1 and µ 2 are singular.
And by symmetry of the roles of µ 1 and µ 2 :

µ 2 dµ 1 dµ 2 > 0 > 0 ⇔ µ 1 and µ 2 are not singular ⇔ µ 1 dµ 2 dµ 1 > 0 > 0.
Let us explain what these results have to do with condition (c). One may be able to distinguish environment θ from θ if a certain arm delivers a payoff that is infinitely more likely in θ than in θ. This is for instance the case if X ,t is in the support of ν and not in the support of ν , but our condition is more general. If the agent observes a payoff x from arm , the quantity dν dν (x) represents how much the observation of x is more likely in environment θ than in θ. If ν k and νk admit density functions (say, respectively, f and f ) with respect to a common measure, then dν dν (x) = f (x) f (x) . Thus the agent will almost never make a mistake if he removes θ from possible environments when dν dν (x) = 0. This may happen even if x is in both supports of ν and ν , for example if x is an atom of ν and not of ν (i.e. ν (x) > 0 and ν (x)=0). On the contrary, if dν dν (x) > 0 both environments θ and θ are likely and arm 's behaviour is both consistent with θ and θ. Now let us state the impossibility result. Here and throughout the paper we find it more convenient to denote f +∞ g rather than the usual notation g = o(f ), which has the following meaning:

∀ε > 0, ∃N ≥ 0, ∀n ≥ N, g(n) ≤ εf (n). Theorem 3.3. Let f : N → R *
+ be greater than order log α , that is for any α > 0, f +∞ log α . Assume that there exists θ, θ ∈ Θ, and k ∈ {1, . . . , K} such that:

(a) ν k = νk , (b) k is the index of the best arm in θ but not in θ, (c) ∀ = k, P θ dν dν (X ,1 ) > 0 > 0.
Then there is no f -wT anytime policy, and hence no f -R anytime policy.

Let us give some hints of the proof (see Section 7 for details). The main idea is to consider a policy that would be f -wT , and in particular that would "work well" in environment θ in the sense given by the definition of f -wT . The proof exhibits a time N at which arm k, optimal in environment θ and thus often drawn with high P θ -probability, is drawn too many times (more than the logarithmic threshold C log(N ) ∆ 2 k ) with not so small P θ -probability, which shows the nonexistence of such a policy. More precisely, let n be large enough and consider a time N of order log n and above the threshold. If the policy is f -wT , at time N , sampling times of suboptimal arms are of order log N at most, with P θ -probability at least 1 -C/f (N ). In this case, at time N , the draws are concentrated on arm k. So T k (N ) is of order N , which is more than the threshold. This event holds with high P θ -probability. Now, from (a) and (c), we exhibit constants that are characteristic of the ability of arms = k to "behave as if in θ": for some 0 < a, η < 1, there is a subset ξ of this event such that P θ (ξ) ≥ a T for T = =k T (N ) and for which dP θ dPθ is lower bounded by η T . The event ξ on which the arm k is sampled N times at least has therefore a P θ -probability of order (ηa) T at least. This concludes this sketchy proof since T is of order log N , thus (ηa) T is of order log log(ηa) n at least. Note that the conditions given in Theorem 3.3 are not very restrictive. The impossibility holds for very basic settings, and may hold even if the agent has great knowledge of the possible environments. For instance, the setting

K = 2 and Θ = Ber 1 4 , δ 1 2 , Ber 3 4 , δ 1 2 ,
where Ber(p) denotes the Bernoulli distribution of parameter p and δ x the Dirac measure on x, satisfies the three conditions of the theorem. Nevertheless, the main interest of the result regarding the previous literature is the following corollary.

Corollary 3.4. If Θ is the whole set Θ of all K-tuples of measures on [0, 1], then there is no f -R anytime policy, where f is any function such that f +∞ log α for all α > 0.

This corollary should be read in conjunction with the following result for ucb-h which, for a given n, plays at time t ≥ K + 1,

I t ∈ argmax k∈{1,...,K} Xk,T k (t-1) + 2 log n T k (t -1)
.

Theorem 3.5. For any β > 0, ucb-h is n β -R.

For ρ > 1, Theorem 3.5 can easily be extended to the policy ucb-h(ρ) which starts by drawing each arm once, and then at time t ≥ K + 1, plays

I t ∈ argmax k∈{1,...,K} Xk,T k (t-1) + ρ log n T k (t -1) . (3)
Naturally, we have n β n→+∞ log α (n) for all α, β > 0 but this does not contradict our theorem, since ucb-h(ρ) is not an anytime policy. ucb-h will work fine if the horizon n is known in advance, but may perform poorly at other rounds.

Corollary 3.4 should also be read in conjunction with the following result for the policy ucb1(ρ) which starts by drawing each arm once, and then at time t ≥ K + 1, plays

I t ∈ argmax k∈{1,...,K} Xk,T k (t-1) + ρ log t T k (t -1) . ( 4
)
Theorem 3.6.

For any ρ > 1/2, ucb1(ρ) is log 2ρ-1 -R.
Thus, any improvements of existing algorithms which would for instance involve estimations of variance (see [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF]), of ∆ k , or of many characteristics of the distributions cannot beat the variants of ucb1 regarding deviations.

Positive results

The intuition behind Theorem 3.3 suggests that, if one of the three conditions (a), (b), (c) does not hold, a robust policy would consist in the following: at each round and for each arm k, compute a distance between the empirical distribution of arm k and the set of distribution ν k that makes arm k optimal in a given environment θ. As this distance decreases with our belief that k is the optimal arm, the policy consists in taking the k minimizing the distance. Thus, the agent chooses an arm that fits better a winning distribution ν k . He cannot get stuck pulling a suboptimal arm because there are no environments θ with ν k = νk in which k would be suboptimal. More precisely, if there exists such an environment θ, the agent is able to distinguish θ from θ: during the first rounds, he pulls every arm and at least one of them will never behave as if in θ if the current environment is θ. Thus, in θ, he is able to remove θ from the set of possible environments Θ (remember that Θ is a parameter of the problem which is known by the agent).

Nevertheless such a policy cannot work in general, notably because of the three following limitations:

• If θ is the current environment and even if the agent has identified θ as impossible (i.e. dν k dν k (X k,1 ) = 0), there still could be other environments θ that are arbitrary close to θ in which arm k is optimal and which the agent is not able to distinguish from θ. This means that the agent may pull arm k too often because distribution νk = ν k is too close to a distribution ν k that makes arm k the optimal arm.

• The ability to identify environments as impossible relies on the fact that the event dν k dν k (X k,1 ) > 0 is almost sure under P θ (see Lemma 3.2). If the set of all environments Θ is uncountable, such a criterion can lead to exclude the actual environment. For instance, assume an agent has to distinguish a distribution among all Dirac measures δ x (x ∈ [0, 1]) and the uniform probability λ over [0, 1]. Whatever the payoff x observed by the agent, he will always exclude λ from the possible distributions, as x is always infinitely more likely under δ x than under λ:

∀x ∈ [0, 1], dλ dδ x (x) = 0.
• On the other hand, the agent could legitimately consider an environment θ as unlikely if, for ε > 0 small enough, there exists θ such that dν k dν k (X k,1 ) ≤ ε. Criterion (c) only considers as unlikely an environment θ when there exists θ such that dν k dν k (X k,1 ) = 0. Despite these limitations, we give in this section sufficient conditions on Θ for such a policy to be robust. This is equivalent to finding conditions on Θ under which the converse of Theorem 3.3 holds, i.e. under which the fact one of the conditions (a), (b) or (c) does not hold implies the existence of a robust policy. This can also be expressed as finding which kind of knowledge of the environment enables to design anytime robust policies.

We estimate distributions of each arm by means of their empirical cumulative distribution functions, and distance between two c.d.f. is measured by the norm . ∞ , defined by

f ∞ = sup x∈[0,1] |f (x)| where f is any function [0, 1] → R.
The empirical c.d.f of arm k after having been pulled t times is denoted Fk,t .

The way we choose an arm at each round is based on confidence areas around Fk,T k (n-1) . We choose the greater confidence level (gcl) such that there is still Proceed as follows:

• Draw each arm once.

• Remove each θ ∈ Θ such that there exists θ ∈ Θ and ∈ {1, . . . , K} with dν dν (X ,1 ) = 0. • Then at each round t, play an arm an arm k and a winning distribution ν k such that F ν k , the c.d.f. of ν k , is in the area of Fk,T k (n-1) . We then select the corresponding arm k. By means of Massart's inequality (1990), this leads to the c.d.f. based algorithm described in Figure 1. Θ k denotes the set {θ ∈ Θ|k is the optimal arm in θ}, i.e. the set of environments that makes k the index of the optimal arm.

It ∈ argmin k∈{1,...,K} T k (t -1) inf θ∈Θ k Fk,T k (t-1) -Fν k 2 ∞ .

Θ is finite

When Θ is finite the limitations presented above do not really matter, so that the converse of Theorem 3.3 is true and our algorithm is robust. Theorem 4.1. Assume that Θ is finite and that for all θ = (ν 1 , . . . , ν K ), θ = (ν 1 , . . . , νK ) ∈ Θ, and all k ∈ {1, . . . , K}, at least one of the following holds:

• ν k = νk ,
• k is suboptimal in θ, or is optimal in θ.

• ∃ = k, P θ dν dν (X ,1 ) > 0 = 0.
Then gcl is n β -T (and hence n β -R) for all β > 0.

Bernoulli laws

We assume that any ν k (k ∈ {1, . . . , K}, θ ∈ Θ) is a Bernoulli law, and denote by µ k its parameter. We also assume that there exists γ ∈ (0, 1) such that µ k ∈ [γ, 1] for all k and all θ. 2 Moreover we may denote arbitrary environments θ, θ by θ = (µ 1 , . . . , µ K ) and θ = (μ 1 , . . . , μK ). In this case dν dν (1) = µ l μl > 0, so that for any θ, θ ∈ Θ and any l ∈ {1, . . . , K} one has

P θ dν dν (X ,1 ) > 0 ≥ P θ (X ,1 = 1) = μl > 0.
Therefore condition (c) of Theorem 3.3 holds, and the impossibility result only relies on conditions (a) and (b). Our algorithm can be made simpler: there is no

• Then at each round t, play an arm

It ∈ argmin k∈{1,...,K} T k (t -1) inf θ∈Θ k µ k -Xk,T k (t-1)

2

. need to try to exclude unlikely environments, and computing the empirical c.d.f. is equivalent to computing the empirical mean (see Figure 2). The theorem and its converse are expressed as follows. We will refer to our policy as gcl-b as it looks for the environment matching the observations at the Greatest Confidence Level, in the case of Bernoulli distributions.

Theorem 4.2. For any θ ∈ Θ and any k ∈ {1, . . . , K}, let us set

d k = inf θ∈Θ k |µ k -μk |.
gcl-b is such that:

∀β > 0, ∃C, C > 0, ∀θ ∈ Θ, ∀n ≥ 1, ∀k ∈ {1, . . . , K}, P θ T k (n) ≥ C log n d 2 k ≤ C n β .
Let f : N * → R * + be greater than order log α : ∀α > 0, f +∞ log α . If there exists k such that (a') inf

θ∈Θ\Θ k d k = inf θ ∈ Θ k θ ∈ Θ \ Θ k |µ k -μk | = 0,
then there is no anytime policy such that:

∃C, C > 0, ∀θ ∈ Θ, ∀n ≥ 2, ∀k = k * , P θ (T k (n) ≥ C log n) ≤ C f (n) .
Note that we do not adopt the former definitions of robustness (f -R and f -T ), because the significant term here is d k (and not ∆ k )3 , which represents the distance between Θ k and Θ Θ k . Indeed robustness lies on the ability to distinguish environments, and this ability is all the more stronger as the distance between the parameters of these environments is greater. Provided that the density dν dν is uniformly bounded away from zero, the theorem holds for any parametric model, with d k being defined with a norm on the space of

parameters (instead of |.|).

Note also that the second part of the theorem is a bit weaker than Theorem 3.3, because of the interchange of "∀θ" and "∃C, C". The reason for this is that condition (a) is replaced by a weaker assumption: ν k does not equal νk , but condition (a') means that such ν k and νk can be chosen arbitrarily close.

µ * is known

This section shows that the impossibility result also breaks down if µ * is known by the agent. This situation is formalized as µ * being constant over Θ. Conditions (a) and (b) of Theorem 3.3 do not hold: if a distribution ν k makes arm k optimal in an environment θ, it is still optimal in any environment θ such that νk = ν k . In this case, our algorithm can be made simpler (see Figure 3). At each round we choose the greatest confidence level such that at least one empirical mean Xk,T k (t-1) has µ * in its confidence interval, and select the corresponding arm k. This is similar to the previous algorithm, deviations being evaluated according to Hoeffding's inequality instead of Massart's one. There is one more refinement: the level confidence of arm k at time step t can be defined as

T k (t -1)(µ * -Xk,T k (t-1) ) 2
+ (where, for any x ∈ R, x + denotes max(0, x)) instead of T k (t -1)(µ * -Xk,T k (t-1) ) 2 . Indeed, there is no need to penalize an arm for his empirical mean reward being too much greater than µ * . We will refer to this policy as gcl * . Theorem 4.3. When µ * is known, gcl * is n β -T (and hence n β -R) for all β > 0.

gcl * relies on the use of Hoeffding's inequality. It is now well-established that in general, the Hoeffding inequality does not lead to the best factor in front of the log n in the expected regret bound. The minimax factor has been identified in the works of Lai and Robbins [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF], Burnetas and Katehakis [START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF] for specific families of probability distributions. This result has been strengthened in Honda and Takemura [START_REF] Honda | An asymptotically optimal bandit algorithm for bounded support models[END_REF] to deal with the whole set of probability distributions on [0, 1]. Getting the best factor in front of the log n term in the expected regret bound appeared there to be tightly linked with the use of Sanov's inequality. The recent work of Maillard et al. [START_REF] Maillard | A finite-time analysis of multiarmed bandits problems with kullback-leibler divergences[END_REF] builds on a non-asymptotic version of Sanov's inequality to get tight non-asymptotic bounds for probability distributions with finite support. Garivier and Cappé [START_REF] Garivier | The kl-ucb algorithm for bounded stochastic bandits and beyond[END_REF] adopts a different starting point: the Chernoff inequality. This inequality states that for i.i.d. random variables V, V 1 , . . . , V T , taking their values in [0, 1], for any τ < EV we have

P 1 T T i=1 V i ≤ τ ≤ exp -T K(τ, EV ) , (5)
where K(p, q) denotes the Kullback-Leibler divergence between Bernoulli distributions of respective parameter p and q. It is known to be tight for Bernoulli random variables (as discussed e.g. in [START_REF] Garivier | The kl-ucb algorithm for bounded stochastic bandits and beyond[END_REF]). A Chernoff version of GCL* would consist in the following:

I t ∈ argmin k∈{1,...,K} T k (t -1)K min( Xk,T k (t-1) , µ * ), µ * . ( 6
)
At the expense of a more refined analysis, it is easy to prove that Theorem 4.3 still holds for this algorithm. Getting a small constant in front of the logarithmic term being an orthogonal discussion to the main topic of this paper, we do not detail further this point.

Horizon policies

We now study regret deviation properties of horizon policies. Again, we prove that ucb policies are optimal. Indeed, deviations of ucb-h are of order 1/n α (for all α > 0) and our result shows that this cannot be improved in general. This second impossibility result holds for many settings, that is the one for which there exists θ, θ ∈ Θ such that: (b) an arm k is optimal in θ but not in θ, (c') in environment θ, all arms may behave as if in θ.

Indeed, draws have to be concentrated on arm k in environment θ. In particular, with large P θ -probability, the number of draws of arm k (and only of arm

k) exceed the logarithmic threshold C log n ∆ 2 at step N = K C log n ∆ 2
. Such an event only affects a small (logarithmic) number of pulls, so that in environment θ arms may easily behave as in θ, and arm k is pulled too often with not so small P θ -probability. More precisely, this event happens with at least P θ -probability 1

-(K-1) C f (n)
for a f -wT policy. Because arms under environment θ are able to behave as in θ, there exist constants 0 < a, η < 1 and a subset ξ of this event such that P θ (ξ) ≥ a N and for which dP θ dPθ is lower bounded by η N . The event ξ has then P θ -probability of order (ηa) N at least. As N is of order log n, the probability of arm k being pulled too often in θ is therefore at least of order 1/n to the power of a constant. Hence the following result.

Theorem 5.1. Let f : N → R * + be greater than order n α , that is for any α > 0, f (n) n→+∞ n α . Assume that there exists θ, θ ∈ Θ, and k ∈ {1, . . . , K} such that: (b) k is the index of the best arm in θ but not in θ, (c') ∀ ∈ {1, ..., K}, P θ dν dν (X ,1 ) > 0 > 0. Then there is no f -wT horizon policy, and hence no f -T horizon policy.

Note that the conditions under which the impossibility holds are far less restrictive than in Theorem 3.3. Indeed, conditions (b) and (c') are equivalent to:

(a") P θ dν k dν k (X ,1 ) > 0 > 0, (b) k is the index of the best arm in θ but not in θ, (c) ∀ = k, P θ dν dν (X ,1 ) > 0 > 0.
These are the same conditions as in Theorem 3.3, except for the first one, (a"), which is weaker than condition (a). As a consequence, corollary 3.4 can also be written in the context of horizon policies.

Corollary 5.2. If Θ is the whole set Θ of all K-tuples of measures on [0, 1], then there is no f -T horizon policy, where f is any function such that f (n) n→+∞ n α for all α > 0.

Moreover, the impossibility also holds for many basic settings, such as the ones described in section 4.2. This shows that gcl-b is not only better in terms of deviations than ucb anytime algorithms, but it is also optimal and, despite being an anytime policy , it is at least as good as any horizon policy. In fact, in most settings suitable for a gcl algorithm, gcl is optimal and is as good as ucb-h without using the knowledge of the horizon n.

Nevertheless, the impossibility is not strong enough to avoid the existence of f -R horizon policies, with f (n) n→+∞ n α and any α > 0. Proposition 2.1 does not enable to deduce the non-existence of f -R policy from the nonexistence of f -wT policy because it needs f to be less than a function of the form αn β . We believe that, in general, the impossibility still holds for f -R horizon policies, but the corresponding conditions will not be easy to write and the analysis will not be as clear as our previous results. Basically, the impossibility would require the existence of a pair of environments θ, θ such that • an arm k is optimal in θ but not in θ,

• in environment θ, all arms may behave as if in θ in such a way that best arm in θ would have actually given greater rewards than the other arms if it had been pulled more often.

Finally, as in section 4 one can wonder if there exists a converse to our result. Again, such an analysis would be tougher to perform and we only give some basic hints.

If Θ is such that for any θ, θ ∈ Θ either (b) or (c') does not hold, then one could actually perform very well. In this degenerated case, only one pull of each arm may make it possible to distinguish tricky pairs of environments θ, θ, and thus to learn the best arm k * . The agent then keeps on pulling arm k * , and its regret is almost surely less than K at any time step. The tricky part is that, as the distinction relies on the fact that the event dν k dν k (X k,1 ) > 0 is almost sure under P θ (see Lemma 3.2), this may not work if Θ is uncountable.

Experiments

Our goal is to compare anytime ucb policies, more precisely ucb1(ρ) for ρ ≥ 0 defined by ( 4), to the low-deviation policies ucb-h(ρ) for ρ ≥ 0, defined by (3), and gcl * introduced in Section 4 (see Figure 3). Most bandit policies contain a parameter allowing to tune the exploration-exploitation trade-off. To do a fair comparison with anytime ucb policies, we consider the full range of possible exploration parameters.

We estimate the distribution of the regret of a policy by running 100000 simulations. In particular, this implies that the confidence interval for the expected regret of a policy is smaller than the size of the markers for n = 100, and smaller than the linewidth for n ≥ 500. The reward distribution of the arms are here either the uniform (Unif), or the Bernoulli (Ber) or the Dirac distributions.

Tuning the exploration parameter in ucb policies for low expected regret

In ucb policies, the exploration parameter can be interpreted as the confidence level at which a deviation inequality is applied (neglecting union bounds issues). For instance, the popular ucb1 uses an exploration term (2 log t)/T k (t) = log(t 4 )/(2T k (t)) corresponding to a 1/t 4 confidence level in view of Hoeffding's inequality. Several studies [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Audibert | Sample mean based index policies with o(log n) regret for the multi-armed bandit problem[END_REF][START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF][START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF][START_REF] Honda | An asymptotically optimal bandit algorithm for bounded support models[END_REF] have shown that the critical confidence level is 1/t. In particular, [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF] have considered the policy ucb1(ρ) having the exploration term (ρ log t)/T k (t), and shown that this policy have polynomial regrets as soon as ρ < 1/2 (and have logarithmic regret for ρ > 1/2). Precisely, for ρ < 1/2, the regret of the policy can be lower bounded by n γ with 0 < γ < 1 which is all the smaller as ρ is close to 1/2.

The first experiments, reported in Figures 4 and5, show that for n ≤ 10 8 , taking ρ in [0.2, 0.5) generally leads to better performance than taking the critical ρ = 0.5. There is not really a contradiction with the previous results as for such ρ, the exponent γ is so small than there is no great difference between log n and n γ . For n ≤ 10 8 , the polynomial regret will appear for smaller values of ρ (i.e. ρ ≈ 0.1 in our experiments).

The numerical simulations exhibit two different types of bandit problems: in simple bandit problems (which contain the case where the optimal arm is a Dirac distribution, or the case when the smallest reward that the optimal arm can give is greater than the largest reward than the other arms can give), the performance of UCB policies is all the better as the exploration is reduced, that is the expected regret is an increasing function of the exploration parameter. In difficult bandit problems (which contain in particular the case when the smaller reward that the optimal arm is smaller than the mean of the second best arm), there is a real trade-off between exploration and exploitation: the expected regret of ucb1(ρ) decreases with ρ for small ρ and then increases. Both types of problems are illustrated in Figure 5.

The gain of knowing the horizon

There is consistently a slight gain in using ucb-h(ρ) instead of ucb1(ρ) both in terms of expected regret (see Figures 4 and5) and in terms of deviations (see Figures 6 to 13 in pages 20 to 22).

The latter figures also show the following. If the agent's target is not to minimize its expected regret, but to minimize a quantile function at a given confidence level, increasing the exploration parameter ρ (for instance taking ρ = 0.5 instead of ρ = 0.2) can lead to a large improvement in difficult bandit problems, but also a large decrement simple bandit problems. Besides, for large values of ρ or for simple bandit problems, ucb1(ρ) and ucb-h(ρ) behave similarly and thus, there is not much gain in using ucb-h policies instead of ucb1 policies.

The gain of knowing the mean reward of the optimal arm

When the mean reward µ * of the optimal arm is known, there is a strong gain in using this information to design the policy. In all our experiments comparing the expected regret of policies, summarized in Figures 4 and5, the parameter-free and anytime policy gcl * performs a lot better than ucb1(ρ) and ucb-h(ρ), even for the best ρ, except in one simulation (for n = 100, and K = 2 arms: a Bernoulli distribution of parameter 0.6 and a Dirac distribution at 0.5). In terms of thinness of the tail distribution of the regret, gcl * outperforms all policies in simple bandit problems, while in difficult bandit problems, it generally outperforms ucb1(0.2) and ucb-h(0.2) and performs similarly to ucb1(0.5) and ucb-h(0.5) (see Figures 6 to 13 in pages 20 to 22).

The gain of knowing µ * is more important than the gain of knowing the horizon. It is not clear to us that we can have a significant gain in knowing both µ * and the horizon n compared to just knowing µ * .

Proofs

Proof of Proposition 2.1

f -T ⇒ f -R: When a policy is f -T , by a union bound, the event

ξ 1 = ∃k ∈ {1, . . . , K}, T k (n) ≥ C log n ∆ 2 k occurs with probability at most K C f (n) . Introduce S k,s = s t=1 (X k,t -µ k ). Since we have n t=1 X It,T I t (t) = K k=1 S k,T k (n) + K k=1 T k (n)µ k ,
IP(r -1 ≤ Rn ≤ r + 1) GCL * UCB1(0.2) UCB-H(0.2) UCB1 (0.5)
UCB-H(0. we have

Rn = S k * ,n -S k * ,T k * (n) - k =k * S k,T k (n) + k =k * ∆ k T k (n). ( 7
) Let T = k =k * T k (n) = n-T k * (n), t * = k =k * C log n ∆ 2 k
, and

W = max 0≤s≤t * (S k * ,n - S k * ,n-s ). Since S k * ,n -S k * ,T k * (n) ≤ W on the complement ξ c 1 of ξ 1 , we have Rn ≤ n1 ξ1 + W - k =k * S k,T k (n) + k =k * ∆ k T k (n). (8)
Consider the events

ξ 2 = W > k =k * Cβ 2 log n ∆ k , ξ 3,k = max 1≤s≤ C log n ∆ 2 k (-S k,s ) > Cβ 2 log n ∆ k , and ξ = ξ 1 ∪ ξ 2 ∪ k =k * ξ 3,k
. From Hoeffding's maximal inequality, we have

P θ (ξ 2 ) ≤ exp - 2 k =k * Cβ/2 log n ∆ k 2 k =k * (C log n)/∆ 2 k ≤ exp -β log n = 1 n β ≤ α f (n) .
We also use Hoeffding's maximal inequality to control P θ (ξ 3,k ):

P θ (ξ 3,k ) ≤ exp - 2 Cβ/2 log n ∆ k 2 (C log n)/∆ 2 k = 1 n β ≤ α f (n)
.

By gathering the previous results using a union bound, we have P(ξ) ≤ 2α+ C f (n) . Besides on the complement of ξ, by using (8), we have

Rn < k =k * Cβ 2 log n ∆ k + k =k * Cβ 2 log n ∆ k + k =k * C log n ∆ k .
We have thus proved that

∀θ ∈ Θ, ∀n ≥ 1, P θ Rn ≥ (C + 2Cβ) log n ∆ ≤ C + 2α f (n) ,
hence the policy is f -R. f -wT ⇒ f -wR: it is exactly the same proof as for f -T ⇒ f -R since the core of the argument is independent of the position of "∀θ" with respect to "∃C, C".

f -wR ⇒ f -wT : let us prove the contrapositive. So we assume

∃θ ∈ Θ such that ∆ = 0, ∀C , C > 0, ∃n ≥ 1, ∃k = k * , P θ T k (n) ≥ C log n ∆ 2 k > C f (n) . (9)
It is enough to prove that for this θ, we have

∀C > 9K/∆, ∀ C > α, ∃n ≥ 1, P θ Rn ≥ C log n ∆ > C f (n) .
To achieve this, we consider C = (β+2)C/∆ and C = max 2 C, max m≤K f (m) in [START_REF] Devanur | The price of truthfulness for pay-perclick auctions[END_REF] and let k = k * be such that the event

ξ = T k (n) ≥ C log n ∆ 2 k
holds with probability greater than C /f (n) = 2 C/f (n). From (9) and using C ≥ max m≤K f (m), we necessarily have n ≥ K. Let L = log f (n) C nK and

ξ = ∀k = k * , ∀s ∈ {1, . . . , n}, |S k,s | ≤ sL 2 ∀s ∈ {1, . . . , n}, |S k * ,n -S k * ,n-s | ≤ sL 2 .
By Hoeffding's inequality and a union bound, this event holds with probability at least 1 -C/f (n). As a consequence, we have P(ξ ∩ ξ ) > C/f (n). We now prove that on the event ξ ∩ ξ , we have

Rn ≥ C log n ∆ .
First note that for any a > 0 the function s → as -√ 2sL is decreasing on 0, L 2a 2 and increasing on L 2a 2 , +∞ , and that

T k (n) ≥ C log n ∆ 2 k ≥ CL ∆ 2 k , since f (n) C nK ≤ αn β α n 2 = n β+2 ≤ n C /C
. Then, by using [START_REF] Burnetas | Optimal adaptive policies for sequential allocation problems[END_REF] and

T k * (n) = n -k =k * T k (n), we have Rn ≥ -|S k * ,n -S k * ,T k * (n) | - k =k * |S k,T k (n) | + k =k * ∆ k T k (n) ≥ - L k =k * T k (n) 2 - k =k * LT k (n) 2 + k =k * ∆ k T k (n) ≥ k =k * ∆ k T k (n) -2T k (n)L ≥ ∆ k T k (n) 2 + ∆ k T k (n) 2 -2LT k (n) + k =k * ,k =k min s≥1 ∆ k s - √ 2Ls ≥ C log n 2∆ k + C 2 - √ 2C L ∆ k - k =k * ,k =k L 2∆ k ≥ C log n 2∆ k + C 6 L ∆ k - KL 2∆ ≥ C log n 2∆ k ≥ C log n ∆ ,
which ends the proof of the contrapositive.

Proof of Theorem 3.3

Let us first notice that we can remove the ∆ 2 k denominator in the the definition of f -wT without loss of generality. This would not be possible for the f -T definition owing to the different position of "∀θ" with respect to "∃C, C". Thus, a policy is f -wT if and only if

∀θ ∈ Θ such that ∆ = 0, ∃C, C > 0, ∀n ≥ 2, ∀k = k * , P θ (T k (n) ≥ Clog n) ≤ C f (n) .
Let us assume that the policy has the f -upper tailed property in θ, i.e., there exists C, C > 0

∀N ≥ 2, ∀ = k, P θ T (N ) ≥ C log N ≤ C f (N ) . ( 10
)
Let us show that this implies that the policy cannot have also the f -upper tailed property in θ. To prove the latter, it is enough to show that for any C , C > 0

∃n ≥ 2, P θ T k (n) ≥ C log n > C f (n) . ( 11
)
since k is suboptimal in environment θ. Note that proving [START_REF] Gelly | Exploration exploitation in go: UCT for Monte-Carlo go[END_REF] for C = C is sufficient. Indeed if [START_REF] Gelly | Exploration exploitation in go: UCT for Monte-Carlo go[END_REF] holds for C = C, it a fortiori holds for C < C. Besides, when C > C, (10) holds for C replaced by C , and we are thus brought back to the situation when C = C . So we only need to lower bound P θ T k (n) ≥ C log n . From Lemma 3.2, P θ dν dν (X ,1 ) > 0 > 0 is equivalent to P θ dν dν (X ,1 ) > 0 > 0. By independence of X 1,1 , . . . , X K,1 under P θ , condition (c) in the theorem may be written as

P θ =k dν dν (X ,1 ) > 0 > 0. Since =k dν dν (X ,1 ) > 0 = ∪ m≥2 =k dν dν (X ,1 ) ≥ 1 m , this readily im- plies that ∃η ∈ (0, 1), P θ =k dν dν (X ,1 ) ≥ η > 0. Let a = P θ =k dν dν (X ,1 ) ≥ η . Let us take n large enough such that N = 4C log n satisfies N < n, C log N < N 2K and f (n)η t a t -(K-1) C f (N )
> C for t = C log N . For any C , such a n does exist since f +∞ log α for any α > 0.

The idea is that if until round N , arms = k have a behaviour that is typical of θ, then the arm k (which is suboptimal in θ) may be pulled about C log n times at round N . Precisely, we prove that ∀ = k,

P θ T (N ) ≥ C log N ≤ C f (N ) implies P θ T k (n) ≥ C log n > C f (n) . Let us denote A t = ∩ s=1...t =k dν dν (X ,s ) ≥ η .
By independence and by definition of a, we have P θ (A t ) = a t . We also have

P θ T k (n) ≥ C log n ≥ P θ T k (N ) ≥ N 2 ≥ P θ =k T (N ) ≤ N 2K ≥ P θ =k T (N ) < C log N ≥ P θ A t ∩ =k T (N ) < C log N .
Introduce B N = =k T (N ) < C log N , and the function q such that 1 At∩B N = q (X ,s ) =k, s=1..t , (X k,s ) s=1..N .

Since νk = ν k , by definition of A t and by standard properties of density functions dν dν , we have

P θ A t ∩ =k {T (N ) < C log N } = q (x ,s ) =k, s=1..t , (x k,s ) s=1..N = k s = 1..t dν (x ,s ) s=1..N dν k (x k,s ) ≥ η t q (x ,s ) =k, s=1..t , (x k,s ) s=1..N = k s = 1..t dν (x ,s ) s=1..N dν k (x k,s ) = η t P θ A t ∩ =k {T (N ) < C log N } ≥ η t a t - (K -1) C f (N ) > C f (n) ,
where the one before last step relies on a union bound with [START_REF] Garivier | The kl-ucb algorithm for bounded stochastic bandits and beyond[END_REF] and P θ (A t ) = a t , and the last inequality uses the definition of n. We have thus proved that (11) holds, and thus the policy cannot have the f -upper tailed property simultaneously in environment θ and θ. From Massart's inequality (see [START_REF] Massart | The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality[END_REF]) applied nK times corresponding to the different times and arms and a union bound to combine the inequalities, we have

P θ (ξ) ≥ 1 -nK(2e -(β+1) log n ) = 1 - 2K n β .
We show that on the event ξ, inequalities

T k (n) ≤ 2(β+1) log n δ 2 k +1 hold for any k = k * , where δ k = min θ∈Θ k F ν k -F νk ∞ . Note that δ k > 0: if not, it
would mean that k is suboptimal in θ and optimal in an other environment θ, with ν k = νk . In this case, by hypothesis there exists = k such that dν dν (X ,1 ) = 0 P θ -a.s. Thus θ is almost surely removed during the first rounds of the policy and, as Θ is finite, all of these problematic θ are removed almost surely. Note also that θ cannot be removed: it is readily seen that P θ dν dν (X ,1 ) > 0 = 1 for all θ ∈ Θ and, still because Θ is finite, it is almost sure that dν dν (X ,1 ) > 0 for all θ ∈ Θ. A last consequence of the finiteness of Θ is that terms δ k are uniformly bounded away from zero over Θ, and so are the terms ∆ k , so that the inequalities we are going to prove easily lead to the conclusion of the proof.

Assume by contradiction that there exists k

= k * such that T k (n) > 2(β+1) log n δ 2 k + 1. Then there exists t ≤ n such that I t = k and T k (t -1) > 2(β+1) log n δ 2 k .
As arm k is chosen at round t, we have:

T k * (t -1) inf θ∈Θ k * Fk * ,T * k (t-1) -F νk * 2 ∞ ≥ T k (t -1) inf θ∈Θ k Fk,T k (t-1) -F νk 2 ∞
On the one hand, we have:

β + 1 2 log n > T k * (t -1) inf θ∈Θ k * Fk * ,T * k (t-1) -F νk * 2 ∞ ,
and on the other hand

T k (t -1) inf θ∈Θ k Fk,T k (t-1) -F νk ∞ ≥ T k (t -1) δ k -Fk,T k (t-1) -F ν k ∞ ≥ T k (t -1) δ k - (β + 1) log n 2T k (t -1) = T k (t -1)δ k - β + 1 2 log n.
By combining the former inequalities, we get:

β + 1 2 log n > T k (t -1)δ k - β + 1 2 log n and T k (t -1) < 2(β + 1) log n δ 2 k ,
which is the contradiction expected.

Proof of Theorem 4.2

The proof of the first part of the theorem is the same as the previous section 7.3, except that one has to substitute δ k by d k and that the d k (k = k * ) are not necessarily non negative. Indeed, the distance Fk,T -

F ν k ∞ equals | Xk,T -µ k | in the context of Bernoulli laws.
The proof of the second part is similar to the one of Theorem 3.3: we assume by contradiction that there exists a policy such that

∃C, C > 0, ∀θ ∈ Θ, ∀n ≥ 2, ∀k = k * , P θ (T k (n) ≥ C log n) ≤ C f (n) .
The main difference is that we cannot fix θ, θ such that θ ∈ Θ k , θ ∈ Θ Θ k and µ k = μk . The hypothesis only allows us to take µ k and μk arbitrarily close. This means that we are allowed to consider two sequences (θ n ) n≥1 and ( θn ) n≥1 such that, for all n ≥ 1 (with obvious notations):

• θ n ∈ Θ k , θn ∈ Θ Θ k , • μn k ≥ 2 -1 N µ n k , • 1 -μn k ≥ 2 -1 N (1 -µ n k ),
  A t ∩    =k {T (N ) < C log N }      ≥ a t 2 a t - (K -1) C f (N ) .
By straightforward calculations, one can then show that f (n

)P θn (T k (n) ≥ C log n) -----→ N →+∞
+∞, which is the contradiction expected.

Proof of Theorem 4.3

The proof is similar the one of Theorem 4.1, except that we use Hoeffding's inequality rather than Massart's one. Consider the event ξ = ∀k ∈ {1, . . . , K}, s ∈ {1, . . . , n}, s( Xk,sµ k ) 2 < β + 1 2 log n .

From Hoeffding's inequality applied 2nK times corresponding to the different times and arms and a union bound to combine the inequalities, we have P(ξ) ≥ 1 -2nKe -(β+1) log n = 1 -2K n β . We will prove by contradiction that on the event ξ, we have T k (n) ≤ 1 + 2(β+1) log n (

) 12
Let us split the proof into two cases.

First case: Xk,T k (t-1) ≥ µ * .

Then Xk,T k (t-1)µ k ≥ ∆ k and T k (t -1) Xk,T k (t-1)µ k 2 ≥ T k (t -1)∆ 2 k . The contradiction readily comes from the definition of ξ.

Second case: Xk,T k (t-1) < µ * . From inequality [START_REF] Holland | Adaptation in natural and artificial systems[END_REF] one has Xk * ,T k * (t-1) < µ * , and ( 12) can be written as:

T k (t -1) Xk,T k (t-1)µ * 2 ≤ T k * (t -1) Xk * ,T k * (t-1)µ * 2 .

On the one hand, we have:

β + 1 2 log n > T k * (t -1) Xk * ,T k * (t-1) -µ * 2 ,
and on the other hand

T k (t -1) Xk,T k (t-1) -µ * ≥ T k (t -1) ∆ k -Xk,T k (t-1) -µ k ≥ T k (t -1) ∆ k - (β + 1) log n 2T k (t -1) = T k (t -1)∆ k - β + 1 2 log n.
The former inequalities leads to

β + 1 2 log n > T k (t -1)∆ k - β + 1 2 log n ⇒ T k (t -1) < 2(β + 1) log n ∆ 2 k .
Thus there is a contradiction, meaning that there is no k such that T k (n) > We assume by contradiction that there exists a f -wT policy. As in the proof of Theorem 3.3, on can remove the ∆ 2 k denominator, so that we have:

∃C, C > 0, ∀n ≥ 2, ∀ = k, P θ T (n) ≥ C log n ≤ C f (n) .
Let us show that this implies that the policy cannot have also the f -upper tailed property in θ. To prove the latter, it is enough to show that for any C , C > 0

∃n ≥ 2, P θ T k (n) ≥ C log n > C f (n) , ( 13
)
since k is suboptimal in environment θ.

Similarly to the proof of theorem 3.3, proving [START_REF] Honda | An asymptotically optimal bandit algorithm for bounded support models[END_REF] for C = C is sufficient.

Moreover, there exists η ∈ (0, 1) such that the event A = K =1 dν dν (X ,1 ) ≥ η has probability a > 0 under P θ . We denote A t = ∩ s=1...t K =1 dν dν (X ,s ) ≥ η , and by independence we have P θ (A t ) = a t .

Let us set N = KC log n , choose n large enough so that n > N , and denote Y a r.v. that equals the index of an arm among those that have been pulled the most after time step N , e.g. Y = min argmax l∈{1,...,K} T l (N ) . Obviously, such an arm has been pulled at least C log n at step N (i.e. T Y (N ) ≥ C log n a.s.), so that one has:

P θ (T k (n) ≥ C log n) ≥ P θ (T k (N ) ≥ C log n) ≥ P θ (Y = k) ≥ P θ (A N ∩ {Y = k}) .
Introduce the function q such that 1 A N ∩{Y =k} = q (X ,s ) 1≤ ≤K, s=1..N .

One has:

P θ (A N ∩ {Y = k}) = q (x ,s ) 1≤ ≤K, s=1..N , (x k,s ) s=1..N As N is of order log n, it is then readily seen that f (n)P θ (T k (n) ≥ C log n) -----→ n→+∞ +∞, hence the result.

Figure 1 :

 1 Figure 1: A c.d.f.-based algorithm: gcl.

Figure 2 :

 2 Figure 2: A c.d.f.-based algorithm in case of Bernoulli laws: gcl-b.

•

  Then at each round t, play an armIt ∈ argmin k∈{1,...,K} T k (t -1) µ * -Xk,T k (t-1) 2 + .

Figure 3 :

 3 Figure 3: gcl * : a variant of c.d.f.-based algorithm when µ * is known.

Figure 4 :Figure 5 :Figure 6 :Figure 7 :Figure 8 :

 45678 Figure 4: Expected regret of ucb1(ρ), ucb-h(ρ) and gcl * for various bandit settings (1/2).

Figure 9 :Figure 10 :

 910 Figure 9: Comparison of policies for n = 1000 and K = 2 arms: Ber(0.6) and Dirac(0.5). Left: smoothed probability mass function. Center and right: tail distribution of the regret.

Figure 11 :Figure 12 :Figure 13 :

 111213 Figure 11: Comparison of policies for n = 1000 and K = 2 arms: Unif([0.5,0.7]) and Unif([0.4,0.6]). Left: smoothed probability distribution function. Right: tail distribution of the regret. In this simple bandit problem, ucb1 and ucb-h curves are almost identical.

7. 3 .

 3 Proof of Theorem 4.1 Let θ be in Θ. Consider the event ξ = ∀k ∈ {1, . . . , K}, T ∈ {1, . . . , n}, T Fk,T -F ν k

µ l ≥ γ K- 1 .

 1 where N = 4C log n .On the other hand, the hypothesis readily implies that∀θ, θ ∈ Θ, ∀ ∈ {1, • • • , K}, Let us denote a = γ K-1 and A t = t s=1 =k dν dν (X ,s ) ≥ a . By independence, we have P θ (A t ) = a t .To find a contradiction, we set t = C log N and we adapt the reasoning of the former proof. If n is chosen large enough, one has N < n and C log N < N 2K , and then:P θn (T k (n) ≥ C log n) ≥ P θn T k (N ) ≥Let us denote B N = =k {T (N ) < C log N }.

∆ 2 k 2 k+ 1 . 2 k. 2 +

 22122 for all k = k * . For this, consider k = k * such that T k (n) > 2(β+1) log n ∆ Then there exists t ≤ n such that I t = k and T k (t -1) > 2(β+1) log n ∆ Since the arm k is chosen at time t, it means that T k (t -1) µ * -Xk,T k (t-1) ≤ T k * (t -1) µ * -Xk * ,T k * (t-1) 2 + .

2(β+1) log n ∆ 2 k + 1 . 7 . 6 .

 2176 Proof of Theorem 5.1

1

  ≤ ≤ K s = 1..N dν (x ,s ) ≥ η N q (x ,s ) 1≤ ≤K, s=1..N , (x k,s ) s=1..N 1 ≤ ≤ K s = 1..N dν (x ,s ) = η N P θ (A N ∩ {Y = k}) ≥ η N (P θ (A N ) -P θ (Y = k)) ≥ η N a Nη N P θ (∃l = k, T l (N ) ≥ C log n) ≥ η N a Nη N P θ (∃l = k, T l (n) ≥ C log n) ≥ (ηa) Nη N (K -1) C f (n) .

  B N is measurable w.r.t. X k,1 , . . . , X k,N and X ,1 , . . . , X ,t ( = k), and A t is measurable w.r.t. X ,1 , . . . , X ,t ( = k), so that we can write1 At∩B N = c t,N ((X ,s ) =k, s=1..t , (X k,s ) s=1..N ) . ((x ,s ) =k, s=1..t , (x k,s ) s=1..N ) ((x ,s ) =k, s=1..t , (x k,s ) s=1..N ) a t

	By properties of νn k and ν n k and by definition of A t we have
							 
		P θn	 A t ∩	 	=k	{T (N ) < C log N }	  
	=		c t,N = k	dν n (x ,s )	s=1..N	dν n k (x k,s )
							s = 1..t
	≥		c t,N = k	dν n (x ,s )	s=1..N	2 -1 N dν n k (x k,s )
							s = 1..t
	=	a t 2	P θ n

Two measures m 1 and m

on a measurable space (Ω, F ) are singular if and only if there exists two disjoint measurable sets A 1 and A 2 such that A 1 ∪ A 2 = Ω, m 1 (A 2 ) = 0 and m 2 (A 1 ) = 0.

The result also holds if all parameters µ k are in a given interval [0, γ], γ ∈ (0, 1).

There is no need to leave aside the case of d k = 0: with the convention 1 0 = +∞, the corresponding event has zero probability.


David Poulain
email: david.poulain@supelec.fr

Joanna Tomasik
email: joanna.tomasik@supelec.fr

Marc-Antoine Weisser
email: marc-antoine.weisser@supelec.fr

Dominique Barth
email: dominique.barth@prism.uvsq.fr

Minimization of the receiver cost in an all-optical ring with a limited number of wavelengths

A new all-optical node architecture, known as Packet Optical Add-Drop Multiplexer (POADM), may lead to a considerable cost reduction for the infrastructure of the all-optical metropolitan rings if associated with proper dimensioning studies. We present a dimensioning problem which consists of minimizing the total number of receivers located in POADMs for a metropolitan all-optical ring with a fixed number of wavelengths and a given traffic matrix. We prove that this problem is NPcomplete and provide a heuristic. The heuristic principle is to match and to group transmissions instead of considering them independently. We justify the transmission group matching approach by confronting the results of our algorithm with its simplified version. The results obtained allow us to recommend the heuristic in the planning of POADM configurations in alloptical rings with a limited number of wavelengths.

I. INTRODUCTION

An all-optical network is composed of equipment which can handle the optical signal from its origin to its destination as an opposition to an opto-electronic network where the signal must be stopped and regenerated at each node. All-optical networks offer both better performance and lower energy consumption than the classical opto-electronic networks [START_REF] Bonetto | Optical technologies can improve the energy efficiency of networks[END_REF]. For these reasons, they have been chosen to be the next generation of metropolitan networks. The DOROthéE 1 project aims to reduce the CAPital EXpenditure (CAPEX) of metropolitan networks with low ecological impact by properly dimensioning them. We focus our attention on all-optical rings. In an alloptical network, there are two main parameters that have to be taken into consideration in the dimensioning process, namely the number of wavelengths and the equipment required in the nodes. Thus, this is a bi-criteria optimization problem. The well studied Wavelength Assignment (WA) problem considers the first parameter only. Numerous works [START_REF] Chen | Traffic grooming in WDM ring networks with the min-max objective[END_REF], [START_REF] Dutta | On optimal traffic grooming in WDM rings[END_REF], [START_REF] Gerstel | Cost-effective traffic grooming in WDM rings[END_REF] considered networks equipped with Add-Drop Multiplexers (ADMs). An ADM is both a receiver and a transmitter. The defined problems treated the number of wavelengths and the number of ADMs. Nevertheless in [START_REF] Chiaroni | Novel optical packet switching nodes for metro and backbone networks[END_REF] the authors proposed a very promising node architecture, the Packet Optical Add-Drop Multiplexer (POADM), in which transmitters and receivers are independent. A node is composed of several receivers and one transmitter that can emit on each wavelength. Problems defined for ADM networks are no longer valid for POADM since the receivers and a transmitter are separated. The proper 1 DOROthéE is a Digiteo project financed by the Ile-de-France region.

dimensioning of a POADM network requires the consideration of two parameters : the number of wavelengths and the number of receivers.

In our previous work [START_REF] Poulain | Optimal receiver cost and wavelength number minimization in all-optical ring networks[END_REF], we provided a solution considering the number of receivers as a constraint. There, we defined a single criterium minimization problem known as the Minimum WaveLength Problem (MWLP). The problem was to find the minimum number of wavelengths needed for a given traffic matrix when the total number of receivers in the network is minimal. We showed that the problem is NP-complete and provided a heuristic. In the present work, we define the problem called the Minimum Receiver Problem (MRP) consisting in finding the minimum number of receivers needed for a given traffic matrix in a network where the total number of available wavelengths is fixed. Indeed, the maximum number of wavelengths that can be used is predetermined from the moment the fiber has been buried underground. As long as we do not use more than this number of wavelengths, the cost of using one more wavelength is negligible since the fiber is already present. In that case, the number of receivers becomes the only parameter, whereas the maximum number of wavelengths becomes an additional constraint. It should be noticed that there is a relation between these two problems. Indeed if a solution to the MWLP also respects the wavelength constraint (i.e. does not use more than a given number of wavelengths) then this solution is an optimal solution to the MRP. In the article we thus attempt to state formally and solve the MRP. We show that the problem is NP-complete and provides a heuristic.

The rest of this paper is organized as follows. Section II contains an overview of all-optical technology and a survey of the related research studies. In Section III we formally introduce the MRP. We study its complexity in Section IV and in Section V we present a heuristic algorithm which solves the MRP and comment on the results obtained in Section VI. Finally, we conclude and outline perspectives.

II. RELATED WORK

In this section we give an overview of all-optical technologies. In the first part, we explain the principle of traffic assignment and, in the second part, we present several node architectures which lead to different dimensioning problems. All but one of these architectures have been exhaustively studied.

Optical networks use Wavelength Division Multiplexing (WDM) to carry a vast amount of traffic through the fiber. Each wavelength is considered as a high speed channel with a fixed transmission rate. Since the wavelength capacity is large, most of the dimensioning solutions consist in grouping requests in order to reduce the number of wavelengths required. These methods, known as traffic grooming methods, use Time Division Multiplexing (TDM) to divide wavelengths into smaller channels. The number of channels that a wavelength contains is called grooming ratio.

In point-to-point opto-electronic networks the traffic is add/drop to/from a wavelength using electronic Add-Drop Multiplexers (ADMs). The optical signal is systematically stopped at each node and thus an ADM is needed on each wavelength. Since the cost of these devices represents a large part of the Capital Expenditure (CAPEX), it is a priority to reduce the number of required ADMs. In the first technology we present, all optical network nodes are equipped with Optical Add-Drop Multiplexers (OADMs) that, added to a node, allow the optical signal to bypass the node. When equipped with OADMs, a node requires ADM only on the wavelengths on which it has to add/drop traffic. By properly organizing the traffic flow it is thus possible to suppress ADMs and then reduce the CAPEX. The traffic grooming and wavelength assignment problem was, for OADM node architecture, proved NP-complete [START_REF] Chen | Traffic grooming in WDM ring networks with the min-max objective[END_REF] and heuristics were provided for mesh [START_REF] Hu | Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks[END_REF], ring [START_REF] Berry | Reducing electronic multiplexing costs in SONET/WDM rings with dynamically changing traffic[END_REF], [START_REF] Chen | Traffic grooming in WDM ring networks with the min-max objective[END_REF], [START_REF] Dutta | On optimal traffic grooming in WDM rings[END_REF], [START_REF] Gerstel | Cost-effective traffic grooming in WDM rings[END_REF], [START_REF] Simmons | Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic[END_REF], [START_REF] Gerstel | Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings[END_REF] and multiring [START_REF] Wang | Interconnected WDM ring networks strategies for interconnection and traffic grooming[END_REF] topologies. More recently, networks provided with Reconfigurable Optical Add-Drop Multiplexers (ROADMs) have been studied. A ROADM is a tunable device that can add/drop traffic onto/from different wavelengths over time. ROADM offers more flexibility than OADM and allows one to perform dynamic traffic grooming, saving both CAPEX and Operational Expenditure (OPEX). With dynamic traffic grooming, ROADM leads to new dimensioning constraints and thus to new dimensioning problems [START_REF] Cho | Architecture and protocols for packet communication in optical WDM metropolitain area networks using tunable wavelength add-drop multiplexors[END_REF]. In [START_REF] Wang | Interconnected WDM ring networks strategies for interconnection and traffic grooming[END_REF] the authors considered an architecture provided with Optical Cross Connect (OXC) that allows time-slot traffic switching. Based on the observation that a node may have to add but not drop (or, symmetrically, drop but not add) traffic from a wavelength, the authors of [START_REF] Chiaroni | Novel optical packet switching nodes for metro and backbone networks[END_REF] present another node architecture known as Packet Optical Add-Drop Multiplexer (POADM). This architecture, we study, is composed of several receivers and one tunable transmitter that can add traffic to different wavelengths over time. As for ADM based networks, the number of receivers used is a large part of the CAPEX. Once again, the flexibility provided by this technology should lead to better results if associated with effective traffic assignment heuristics. Nevertheless, there is no dimensioning process for this technology.

III. MINIMUM RECEIVER PROBLEM

We formally introduce the MRP. Given a traffic matrix and a number of available wavelengths, the MRP is the minimization problem which consists in finding an assignment of the traffic on the wavelengths that minimizes the number of receivers required. The problem presented below is the decision problem associated with the MRP.

Problem: MINIMUM RECEIVER PROBLEM

Data:

• An elementary circuit [START_REF] Berge | Graphs and hypergraphs[END_REF] G = (V, E) .

• A traffic matrix T where T [i, j] is an amount of traffic to be sent from a node i to a node j.

• A set λ = {λ 1 , λ 2 , ..., λ W } of wavelengths, W ∈ N. • A wavelength capacity C ∈ N. • A number of receivers z ∈ N.
We call assignment the operation which decomposes T into a set of W matrices T k of the same dimension as T and associates T k to a wavelength k ∈ λ of a ring. Question: Is it possible to find an assignment of the traffic T on the wavelengths λ that respects simultaneously the flow and capacity constraints and that does not use more than z receivers ?

Flow constraint: For any couple of nodes (i, j), the amount of traffic carried on each wavelength has to be equal to the total amount of traffic between i and j:

∀i, j ∈ V, k∈λ T k [i, j] = T [i, j].
Capacity constraint: Let load k (x) be the load of the arc x ∈ E for the wavelength k. In other words load k (x) is equal to the amount of traffic carried by the arc x on the wavelength k. load k (x) cannot exceed the capacity C:

∀k ∈ λ, ∀x ∈ E, load k (x) = i,j s.t. x∈path(i,j) T k [i, j] ≤ C.

IV. COMPLEXITY

We use the Partition Problem (PP) [START_REF] Garey | Computers and intractability : A Guide to the Theory of NP-Completeness[END_REF] to prove that the MRP is NP-Complete.

Problem: PARTITION PROBLEM

Data:

• A set of integers X = {x 1 , x 2 , ..., x m } Question: Is it possible to find A and B such that A∪B = X, A ∩ B = ∅ and x∈A x = x∈B x? Theorem 4.1: The MRP is NP-complete.

Proof: Given an instance of MRP and an assignment of traffic T on λ, we can determine whether this assignment involves less than z receivers and verify both the capacity and flow constraints in polynomial time. The certificate of MRP is in P.

Let us consider an instance of the PP. From this instance we build an instance of the MRP as follows. For each integer x i of X we create two vertices in an initially empty elementary circuit G. Those vertices are s i (source of the traffic) and d i (destination of the traffic). Nodes in G are ordered so that s 1 ≺ . . . ≺ s m ≺ d 1 ≺ . . . ≺ d m where X ≺ Y means that X is placed before Y in the ring. We build the traffic matrix so that the only non-zero elements are

T [s i , d i ] = x i . We fix W = 2, C = ( m k=1 x k )/2 and z = m.
For the given instances, if there is a solution to the PP then we are able to build a solution to the MRP and reciprocally. We associate the subset A (respectively B) with the first λ 1 (respectively the second λ 2 ) wavelength. In the PP solution, an integer x i is associated with one of the two subsets, A or B. The whole traffic x i = T [s i , d i ] is therefore assigned to the wavelength which corresponds to this subset. As we assign the entire traffic flow to a single wavelength, the flow constraint is respected. For the same reason the solution does not use more than z receivers. For each wavelength the amount of traffic passing through an arc is less than or equal to the amount of traffic passing through the arc (s m , d 1 ) on the same wavelength. Since load 1 (s m , d 1 ) = x∈A = C and load 2 (s m , d 1 ) = x∈B = C, the capacity constraint is respected. If the PP has a solution then the MRP has a solution too.

If we have a solution to the MRP, then each traffic flow is assigned to a single wavelength due to the number of receivers limited to z. The assignment of traffic on the arc (s m , d 1 ) directly provides the partition of integers, which is a solution to the PP. If there is a solution to the MRP, then there is also a solution to the PP.

We prove there is a polynomial reduction from the PP to the MRP and that the certificate of MRP is in P. Thus, we prove that MRP is NP-complete.

V. HEURISTIC

The algorithm we propose has three steps. First, it groups the requests, then selects groups and, finally, assigns them to wavelengths.

For a given n-node ring with nodes numbered from 1 to n, we consider each wavelength as an n-dimension cube. Dimension i is associated with the arc i (i.e. the arc between nodes i and i+1). The length of each edge of this cube is equal to C. Such a cube is called a box and the number of boxes available is equal to the number of wavelengths available, w. A request r (x,y) is a traffic flow between nodes x and y. It is represented as as an n-dimension vector. The height h(r) of request r is equal to the amount of traffic this request is carrying and its length l(r) is equal to the number of arcs between its origin and its destination. For example, in a 4-node ring we consider the request r (1,3) = (3, 3, 0, 0). This request passes through arcs 1 and 2 but not through arcs 3 and 4. Thus, we have h(r (1,3) ) = 3 and l(r (1,3) ) = 2. A unitary request is a request with height equal to one (i.e. the smallest amount of traffic to be transmitted). As non-unitary requests can be split over several wavelengths, we may consider without loss of generality that all requests are unitary requests.

A set of transmission requests with the same destination forms an element. Inside the element, requests are decreasingly ordered by length. An element e may be seen as a vector sum of the request vectors it contains. An element composed of all the requests towards a given destination is called a complete element. There are at most n complete elements numbered according to their destination node. The length of an element e is l(e) = max r∈e (l(r)) and its size is s(e) = r∈e l(r). Its height h(e) is equal to the number of unitary requests it contains. A rectangular element is a particular element that contains only requests of the same length.

In order to minimize the number of the receivers needed in the ring, the traffic associated with a given complete element should be carried by the smallest number of wavelengths. Our goal is therefore to cut the complete elements into elements that fit into the smallest number of available wavelengths. To discover the shape of a complete element e d , we have to compute the amount of traffic passing through each arc towards d. Let us note l d i the amount of traffic in the arc i destined to d. Under the assumption that a node does not send anything to itself and taking into account a circular network architecture we obtains a vector l d :

   l d i = 0 if i = d l d i = l d n + t i,d otherwise and if i = 1 l d i = l d i-1 + t i,d
otherwise The three steps, that compose our algorithm, are repeated until the assignment of all traffic. The variable C h represents the height of the cut.

Initialisation C h = C.

Step 1 Generally speaking, heuristics of packing obtain better results when the elements to be packed have regular shapes. A cut provides a partition of an element e into a set of k resultant elements {e 0 , e 1 , . . . , e k-1 } with k = ⌈h(e)/C h ⌉. Moreover, we want a cut to have some special properties in order to produce resultant elements with regular shape. Firstly, resultant elements should (as much as possible) be the same height. Ideally, this height is a sub-multiple of C. Secondly, resultant elements should be as low as possible in order to reduce the space they will take when packed into a box. Rectangular elements are, according to their definition, perfectly regular. We decide to measure how much an element is not "rectangular like". The measure of the irregularity of an element e is irr(e) = h•l(e)-s(e). The greater the irregularity number of an element is the harder it is to pack. The cut has to minimize i irr(e i ) = i (h • l(e i )s(e i )). The following method leads to a cut with these properties.

Informally, we form groups of C h requests from the bottom to the top of e. Since the requests are ordered in e according to their lengths, resultant element e i contains longer requests than a resultant element e i+1 . The element on the top can be smaller than h. Formally,

e i = {r iC h , r iC h +1 , . . . , r iC h +C h -1 } if i = k -1 {r (k-1)C h , . . .

r h(e) } otherwise

Step 2 only if C h > 1, We use here an acceptance-rejection method to select groups of elements. The acceptance rate is noted τ . Ideally, we would like to consider each possible set (group) of elements. Nevertheless, as we want the complexity to remain reasonable, we consider hereafter only pairs of elements (or single element). If the elements of a pair do not fit together in a virtual empty box of capacity C h then the pair is rejected regardless of τ . For elements a and b, from a non-rejected pair, we compute fit_rate(a, b) = s(a)+s(b) nC h which measures the fraction of space occupied by the elements a and b when packed in a virtual box of capacity C h . A pair of elements with a fit rate greater than τ is selected. As an element can appears into more than one pair, we use a maximum matching algorithm [START_REF] Gondran | Graphes et algorithmes[END_REF] (on the selected pairs) in order to get the biggest subset of accepted pairs that does not contain a same element twice. We notice that the elements of a same accepted pair are from this moment indivisible and will be treated as a single element. In the remaining subset of elements, an element a is accepted if fit_rate(a) = s(a) nC h > τ .

Step 3 We use a first fit decreasing method [START_REF] Yao | New algorithms for Bin Packing[END_REF] to pack all the accepted elements (or accepted pair of elements) into the w boxes. After the first iteration the boxes can already contain elements. The height of the cut is modified so that h = ⌊h/2⌋.

VI. RESULTS

In this section we discuss the performance of the heuristic algorithm. Firstly, we show, on instances, influence of the acceptance rate τ . Afterwards we compare two variants of our heuristic: with and without pairing the elements in step 2 of the proposed algorithm. We show, thereby, the influence of the pairing of elements and explain in which cases it should be used. The experiments presented below have been made for 16-node ring networks with wavelength capacity C = 32. We use All-To-All (ATA) spatial traffic distribution, in which the sizes of the connections are generated following uniform or normal (N(µ,0.2µ), µ = 16) distribution. In another simulation series we use Rich-Get-Richer (RGR) [START_REF] Barabási | Emergence of scaling in random networks[END_REF] spatial distribution for which the mean volume of traffic received by each node is equal to µ. The latter is chosen to represent a realistic traffic condition, as in a metropolitan ring some nodes may attract more traffic (e.g. video base server, backbone access node).

A. Influence of the acceptance rate

As we have said before, the number of receivers required for a given node is equal to the number of parts in which the associated complete element has to be cut. In order to minimize the number of receivers we want this number of parts to be as small as possible. In other words we want the resultant elements to be as high as possible. Nevertheless a too high resultant element may be difficult to pack if it does not fit well with other resultant elements. The acceptance rate τ allow us to select elements that, despite their height, do not lead to the degradation of the wavelength utilization. Figure 1 depicts the evolution of the ratio z/W (number of receivers / number of wavelengths) depending on the acceptance rate. We see that if τ increases then the ratio z/W increases too.

If the acceptance rate is high then the pairs of elements tend to be rejected and packed later. The number of receivers thus increases whereas the number of wavelengths decreases. So, we know that when the load of traffic is high in the ring (i.e. the number of available wavelengths is small), solutions can be found by increasing the acceptance rate. Symmetrically if the number of wavelengths is large, then we can save receivers by decreasing the acceptance rate.

B. Influence of the pairing method

Figure 2 and 3 depict the influence of using or not the pairing method in step 2 of our heuristic. Figure 2 has been computed on an instance with ATA spatial distribution and normal (N(µ, 0.2µ)) distribution for the size of the connection whereas Figure 3 has been computed on an instance with RGR traffic distribution. On each we compare three curves. The straight line represents the minimal number of receivers (z min ) for a given traffic.

z min = i∈V j T [j, i] C
We notice that this lower bound, as it is not dependant on the number of available wavelengths, may not be close to the optimal solution when the number of available wavelengths is small. The two other curves represent the number of receivers required for a given traffic and a given number of wavelengths using both with and without the method of pairing.

We see with these curves, that the solution without pairing is not highly affected by the number of available wavelengths. On the other hand, the solution with pairing performs extremely well when the wavelength constraint is not tight but leads to worse results when the assignment of traffic becomes the bigger problem. As we want to statut on the performance of the heuristic with pairing, we have to study a large number of instances. Nevertheless, for a given traffic matrix T , it is difficult to say if the wavelength constraint is either tight or open as the wavelength assignment problem is itself a difficult problem.

The MWLP heuristic, presented in [START_REF] Poulain | Optimal receiver cost and wavelength number minimization in all-optical ring networks[END_REF], provides a solution that have the minimum number of receivers z min and a number of wavelengths that we note W max . For each MRP instance that has more than/exactly W max available wavelengths we are able to find an optimal solution. Thus, our interest is in the MRP instances that have less than W max available wavelengths.

Let W min be the number of wavelengths used by a solution of a efficient wavelength assignment heuristic for the given matrix T . Such a solution can be provided, for instance, by the arc-colouring based heuristic presented in [START_REF] Kumar | Approximating circular arc colouring and bandwidth allocation in all optical ring networks[END_REF]. It seems reasonable to consider W min as the minimal number of wavelengths required. In other word, we will consider the MRP instances which have more than W min available wavelengths.

We generated 500 random traffic matrix for 16-node ring networks using RGR distribution. From a same matrix we generated three types of instances. In the first type, the number of available wavelengths is hardly constraint (i.e. W ∈ (W min , W min + Wmax-Wmin

3

)). In the second type, the number of available wavelength is tight (i.e. W ∈ [W min + Wmax-Wmin 3 , W min + 2(Wmax-Wmin) 3 ]) and finally in the third one, the number of available wavelengths is open (i.e. W ∈ (W min + 2(Wmax-Wmin) 3 , W max )). In all three cases C = 32. The results of this experiment is showed in Figure 4. In this figure, x% means that the average solution has x% more receivers than the optimal solution for a number of available wavelength equals to W max (W max is provided by the MWLP heuristic).

Open Tight

Hard With pairing 5.6% 20% 29.7% Without pairing 14% 23.5% 27.5% As expected the results presented in Figure 4 confirm the observations made on the instance of Figures 2 and3 when the wavelength constraint is opened. In that case the heuristic with pairing performs well, increasing the minimum number of receivers by only 5.6 percent whereas the heuristic without paring get a 14 percent. When the wavelength constraint is tight the pairing method get also slightly better results than its opponent. Finally, the experience shows that the performance of the pairing method is comparable when the wavelength constraint is hard.

CONCLUSION AND FURTHER WORK

The paper presents a part of our work dedicated to the dimensioning of all-optical ring networks with POADM node architecture. A POADM node can emit on all available wavelengths but it can only read on a subset of available wavelengths. The network infrastructure cost (CAPEX) of such a network can therefore be brought down by reducing the number of receivers present in the nodes. Our goal was to minimize this number when the number of available wavelengths is limited. We proved that the corresponding optimization problem is NP-complete. The heuristic we proposed is based upon a preliminary matching of pairs of grouped transmission which attempts to "wipe out" their shape irregularities. We proposed this coupling in order to obtain an efficient wavelength assignment. The exhaustive simulation results show the advantage of the introduction of pairing. They also exhibit that the heuristic results converge to the optimal solution when the number of available wavelengths is unlimited.

As a further work we consider studying together the problem we discussed here with the one which we treated before in [START_REF] Poulain | Optimal receiver cost and wavelength number minimization in all-optical ring networks[END_REF], and which consisted of minimizing the wavelength number with the given, minimal number of receivers. We will want thus to formulate and solve a bi-criteria problem.

Fig. 1 .

 1 Fig. 1. Influence of the acceptance rate τ on [z, W ]

Fig. 2 .Fig. 3 .

 23 Fig. 2. Influence of the pairing method (ATA spatial distribution, Size of connections normally distributed)

Fig. 4 .

 4 Fig. 4. Influence of the pairing method (Exhaustive simulations)


G L J A Rikken

B A Van Tiggelen

Magneto-electric momentum transfer to atoms and molecules

Keywords: numbers: 03.50.De, 42.50.Nn, 42.50.Wk

We report the first observation of mechanical momentum transferred to atoms and molecules upon application of crossed electric and magnetic fields. We identify this momentum as the microscopic analogue of the classical Abraham force. Several predictions of additional magneto-electrically induced mechanical momentum are addressed. One of them, proposed to result from the interaction with the quantum vacuum, is experimentally refuted, others are found to be currently below experimental detection.

It has been shown that in crossed electric and magnetic field E and B, the optical and electrical properties of matter become anisotropic along the axis E × B [1] [2] [3]. As this anisotropy manifests itself in the dispersion law and thus in the momentum of the photons and the charge carriers respectively, one may wonder whether a similar anisotropy can exist in the mechanical momentum of particles in crossed fields.

Invariance under time, charge and parity reversal straightforwardly shows it to be symmetry allowed for a particle to acquire a mechanical momentum p upon applying a crossed electric and magnetic field E and B p = aE × B

If we assume the particles to be in a gaseous phase in a container, and the collisions between the particles to be elastic, the momentum imparted to each of the particles by the application of the fields will be conserved within the gas as a whole, and ultimately transferred to the wall perpendicular to E × B. If we apply a harmonically oscillating electric field E(t) = E sin ωt and a static magnetic field B, each particle will contribute a force on this wall given by

F p = dp dt = aωE × B (2)
Such a force exerted on individual atoms would be the microscopic equivalent of the so-called Abraham force density which was first formulated for macroscopic media, and has been the subject of a long-standing controversy [4][5][6][7]. In the so-called Abraham version one finds a macroscopic force density (in SI units)

f A = ε 0 (ε r -1/µ r ) E × B [8]
, whereas in the Minkowski version f M = ε 0 (ε r -1) E × B (ε r and µ r are the relative dielectric permittivity and magnetic permeability respectively). This can be compared to the quantummechanical conserved pseudo-momentum of a neutral atom in a homogeneous magnetic field, K = i m i ṙi + i q i B × r i [START_REF] Kawka | [END_REF]. An additional electric field creates a finite polarization < P >= i q i r i = αE (α is the static electric polarizability of the particle with SI unit Cm 2 /V ) in the ground state so that 0 = K = i m i ri -α∂ t E×B. This would lead to a force density f = N α∂ t E×B (where N is the particle density) and which is consistent with the Minkowski version, since ǫ 0 (ǫ r -1) = N α, and we deduce a = α in Eq. (1). Note that the pseudo-momentum in this model equals neither the conjugated momentum P = i m i ṙi + 1 2 i q i B × r i , nor the kinetic momentum P kin = i m i ṙi . Both were proposed by Barnett [7] to solve the Abraham-Minkowski controversy.

The observation of the Abraham force due to a crossed oscillating electric field and a static magnetic field was reported by James [START_REF] James | Force on Permeable Matter in Time-varying Fields[END_REF] and by Walker et al [START_REF] Walker | [END_REF] [12] in solid dielectrics. It should be noted that the Abraham force due to a static electric field and an oscillating magnetic field was reported not to be observed, against all expectation [13][14][15]. For a discussion of these and related experiments, see [4] and [6].

Feigel was the first to consider the interaction of a macroscopic magneto-electric material with the quantum vacuum [16]. The so-called Feigel effect implies that momentum from the vacuum fluctuations can be transferred to matter by the intermediary of the optical magnetoelectric anisotropy and that therefore an QED contribution exists to the classical Abraham force, corresponding to a 'Feigel' momentum p F :

p F = 1 32N π 2 ∆n MEA ω c c 4 (3)
where ∆n MEA ≡ χ MEA EB is the magneto-electric optical anisotropy [1] [2]. In order to avoid the notorious UV catastrophe, Feigel was obliged to introduce an empirical cut-off frequency ω c for the material's response. Particularly this cut-off procedure was contested by several groups, since it is widely believed that the UV catastrophe should somehow be absorbed in the parameter values attributed to bulk media [START_REF] Milton | The Casimir Effect[END_REF]. It was shown [START_REF] Van Tiggelen | [END_REF][19][20] that such a transfer would then only occur in a geometry of finite size, similar to that of the Casimir effect, albeit with much smaller values than obtained by Feigel. Obukhov and Hehl [21] also argued that no net momentum transfer from vacuum fluctuations to bulk media can exist. However, very recently, Croze has forwarded new theoretical support in favour of Feigel's claim [22], correcting in the process a minor numerical error. Kawka and Van Tiggelen have proposed a nonrelativistic quantum theory of a harmonic oscillator in crossed electric and magnetic fields [START_REF] Kawka | [END_REF], in which the UV catastrophe was shown to be absorbed in a mass renormalisation of the oscillator. Applying this model to a hydrogen atom predicts a reduction of a by 2%.

For the ratio between the Feigel and Abraham momenta we find

p F p A = π 2 2 χ MEA N α 1 λ c 4 ( 4
)
where λ c = 2πc/ω c . Feigel proposed λ c = 0, 1 nm as the limit of the matter response to the vacuum fluctuations. Using the experimental results of Roth and Rikken [1] for large organometallic molecules, Croze predicts p F /p A ≈ 7, i.e. the magneto-electrically particle momentum would be dominated by the contribution from the quantum vacuum. Clearly the magneto-electrical momentum, in spite of its long history, still poses fundamental problems. In this Letter we will describe a new method to accurately measure the momentum transferred to atoms or molecules in crossed oscillating electric fields and static magnetic fields. We experimentally confirm the prediction of the classical Abraham force. More specifically, we do not observe any deviations from the Abraham prediction for media where the predicted contribution from the Feigel effect should be observable.

Since the work by James and by Walker et al, no new experiments to measure the Abraham force have been reported. Very recently, a proposition was made to measure it at optical frequencies using whispering gallery modes [23]. The method used here measures directly the pressure exerted by an atomic or molecular gas on the wall of the container if it is exposed to crossed electric magnetic and magnetic fields, E x sin ωt and B y respectively. If we define the effective length of the E × B region as L = E(z)B(z)dz/EB, the momentum change due to the Abraham force exerts an oscillating pressure P on the wall perpendicular to E × B given by

P (t) = αωN LEB cos ωt (5)
Such a pressure can be detected by a microphone located at the wall. By tuning ω to a longitudinal acoustic resonance of the system, the pressure can by multiplied by the Q factor of the resonance. Using values of N = 2, 7.10 25 m -3 (1 bar ideal gas), E = 10 5 V /m, B = 1 T , ω = 3.10 4 s -1 , L = 2 cm, Q = 10 and α = 2, 2.10 -41 Cm 2 /V we find P = 4.10 -7 P a and a velocity of 0, 3 nm/s. (values for He, [24]). The typical sensitivity of an electret microphone is S =10 mV/Pa, so microphone signal voltages of around 5 nV can be expected which are within experimental reach when using phase sensitive detection (PSD). Figure 1 shows schematically the setup used. It consists of a 3 mm diameter, 5 cm long glass tube, with commercial electret microphones butt coupled to its ends, carefully shielded in thick-walled copper housings. The electric field was supplied by a high voltage amplifier (HV amp), generating voltages up to 1000 V, and the magnetic field was provided by an electromagnet, with fields up to 1,5 T. The Q factor was determined from the acoustic resonance lineshape. The systematic inaccuracy of our setup is estimated to be 3 %, mostly due to the inaccuracy of the microphone sensitivity calibration. Typical results for nitrogen gas are shown in Figure 2, confirming the linear dependencies of the magnetoelectrically induced pressure on magnetic field strength, gas pressure (∝ particle density) and electric field oscillation frequency. The linear dependence on electric field strength is intrinsic because of the phase sensitive detection of the pressure signal. The dashed lines in the two top panels are the theoretical predictions, based on Eq. 5. Within the experimental accuracy, the experimental results agree with the theory. The slope in the bottom panel of Figure 2 allows to determine α, using Eq. 5. Figure 3 shows the results for α obtained this way for several gazes, as a function of the literature value for α. All gazes were measured at room temperature and atmospheric pressure, except furan, which was measured at its room temperature vapor pressure. Table 1 summarizes these results, and shows also the calculated contribution of the Feigel momentum, expressed as a fraction of the Abraham momentum, and based on experimental or theoretical values for χ MEA . Only the value for nitrogen is experimental [25], but it is in good agreement with the calculated value [26], giving confidence in the other values calculated by the same authors. For the two molecules in the table with the highest magneto-electric anisotropy, the predicted contributions for the Feigel effect are much larger than the experimental uncertainties on α MEMT , up to 7,5 times for furan. As α MEMT and α LIT agree within the experimental uncertainties, we conclude from these results that the prediction for the Feigel effect as expressed by Eq. 3 is not observed. Note that the Feigel prediction contains one adjustable parameter, the response cutoff wavelength λ c , and that increasing its value to 0,17 nm decreases the prediction of the Feigel momentum contribution to below our experimental uncertainty. However, strong magneto-electric anisotropy was still reported at 0,16 nm wavelength [30], the shortest wavelength at which its observation was ever attempted. Our experimental results therefore unambiguously contradict Feigel's prediction. Recent theoretical work on simple models suggests that χ MEA decays algebraically as ω -2 at high frequencies, in much the same way as the dynamic electrical polarizability [31]. This makes the UV catastrophe in the macroscopic description as proposed by Feigel, unavoidable and unrepairable.

In a QED version of the Feigel effect by Kawka and Van Tiggelen [START_REF] Kawka | [END_REF], this UV catastrophe was removed by mass regularization. Our current experimental accuracy does not allow to make quantitative statements concerning this prediction, but our setup could be improved to attain the 1% accuracy estimated to be necessary for the observation of this regularization. We hope that this perspective will stimulate realistic calculations of this regularization, beyond the harmonic oscillator approximation and in a relativistic context.

In order to make a contribution to the Abraham-Minkowski debate, our experiment would have detect the difference between 1 and 1/µ r . The gas with the largest µ r to our knowledge is oxygen, with µ r -1 = 3, 4 10 -3 at room temperature and 1 atm. [24]. Attaining such a precision is a considerable experimental challenge, but going to lower temperatures or higher pressures could increase µ r -1 to accessible values.

In summary, we have reported the first observation of mechanical momentum transferred to atoms and molecules by applying crossed time-varying electric fields and static magnetic fields. We quantitatively identify this momentum as the microscopic analogue of the classical Abraham force. We exclude the existence of additional magneto-electrically transferred momentum, as proposed by Feigel to result from the optical magnetoelectric anisotropy interacting with the quantum vacuum fluctuations. Other predictions for additional contributions to the Abraham force are currently beyond our experimental resolution, but the new method described in this Letter has potential to successfully address these issues.

FIG. 1 :

 1 FIG. 1: Schematic setup of the experiment.

FIG. 2 :

 2 FIG. 2: Magneto-electric acoustic pressure observed in nitrogen gas. Top panel; 6,15 kHz, 1 atm, E = 370 kV/m, Middle panel; 6,15 kHz, 1 atm, B = 1,14 T. Bottom panel; 1 atm. Solid lines are linear fits to the data, dashed lines theoretical predictions.

FIG. 3 :

 3 FIG. 3: Polarizability for different atoms and molecules as deduced from magneto-electrically generated pressure, as a function of the literature values. Solid line corresponds to the classical Abraham force prediction.

TABLE I :

 I -40 Cm 2 V ) Polarizabilities deduced from magneto-electric momentum transfer, the corresponding literature values, the experimental or calculated magneto-electric anisotropy, and the calculated ratio of Feigel and Abraham momenta for the gazes studied.

			αLIT (10 -40 Cm 2 V )	χMEA (10 -22 m V T )	pF /p A
	He	0, 20 ± 10%	0, 22 [24]	0, 017 [26] 1, 5%
	N2	1, 9 ± 5%	1, 89 [24]	0, 47 [25]	4, 8%
	C2H2 4, 4 ± 5%	4, 4 [24]	3, 7 [26]	16%
	furan	7, 8 ± 4%	7, 9 [29]	12 [28]	29%

This work was supported by the ANR contract PHO-TONIMPULS ANR-09-BLAN-0088-01. We gratefully acknowledge helpful discussions and calculations by Antonio Rizzo.