R Migliore

M Scala

A Napoli

K Yuasa

H Nakazato

A Messina

Dissipative effects on a scheme of generation of a W state in an array of coupled Josephson junctions

Keywords: numbers: 03.65.Yz, 42.50.Dv, 42.50.Lc, 03.65.Ud, 03.67.Mn

 Phys. Rev. B 74, 104503]. To this end a microscopic master equation is constructed and its exact resolution predicts the generation of a Werner-like state instead of the W state. A comparison between our model and a more intuitive phenomenological model is also considered, in order to find the limits of the latter approach in the case of structured reservoirs.

Introduction

The recent progress during the last decade in the context of superconducting solid-state devices, whose system parameters can be controlled in situ to manipulate quantum states coherently, has strengthened the idea that Josephson architectures are among the best candidates both for the search of experimental evidence of nonclassical features at mesoscopic level and for the practical implementation of logic gates and circuits. Superconducting circuits indeed work well, and experiments have demonstrated singlequbit operations [1,2,3,4,5,6,7] with reasonably long coherence times (of the order of 1 µs [8,9]) and that two-qubit entanglement can be produced [10,11,12,13,14] and detected [15,16,17]. A current challenge is the generation of maximally entangled states of more than two solid-state qubits, a powerful resource in quantum information processing and communication. Numerous theoretical protocols for the preparation of such states have been proposed [18,19,20] and very recently also some experimental successes have been achieved. Indeed, tripartite interactions between two phase qubits and a resonant cavity in circuit QED were demonstrated [21], as well as the generation and detection of GHZ-class entanglement between three superconducting phase qubits [22] and three charge qubits [23]. Quite often, the samples were designed with four qubits to allow for future expansion of the multipartite entanglement generation schemes [21,22]. All these goals clearly highlight the need of theoretical analyses of the dynamics of superconductive architectures on the basis of more realistic models, including the effects of external environments which are unavoidably coupled to the systems under study.

Indeed, every quantum system is coupled to one or more external environments. Such a coupling may dramatically affect the predictions done under the hypothesis of perfect isolation. When the external environment is included, the dynamics of the open quantum system under study becomes non-unitary, and may suffer dissipation and decoherence. In this context, the open system dynamics is usually described by means of a Markovian master equation. Many master equations for interacting qubits have been recently introduced in the literature, which may turn out to be useful for the study of dissipative effects on multipartite entanglement [24,25,26,27].

Very recently, in the framework of Josephson flux qubits, some of us have proposed a scheme for the generation of multipartite entangled states [19]. This scheme operates in such a way that, exploiting the sequential inductive interaction of each qubit with one of them playing the role of an entanglement mediator, it generates an entangled W state after a finite number of steps without requiring conditional measurements. Two key requirements are the possibilities of both preparing the initial state of the qubits and of switching on and off, at properly selected instant of times, the coupling constant describing the interaction between each qubit and the mediator. The proposed scheme, however, neglects the presence of external degrees of freedom.

In this paper we analyze the theoretical protocol presented in Ref. [19], focussing in particular our attention on the case of three qubits. In our analysis we take into account from the very beginning the coupling between each qubit and the external world by means of a generalization of a previous microscopic master equation for the study of the dissipative dynamics of two coupled qubits [24].

The aim of this paper is twofold. On one hand we investigate the robustness of the theoretical scheme against losses that, generally speaking, waste unitary scheme. On the other hand, the study we develop allows us to give some insights on the general problem of the choice of the effective master equation for the description of open system dynamics. Indeed, while in this paper we propose to study the effects of losses by means of a model microscopically derived, one may wonder what would be the prediction of the phenomenological master equations which are usually adopted in the literature on leaky coupled quantum systems. In particular, while our model involves transitions between stationary states of the whole three-qubit system, the phenomenological approach just describes those between the bare states of the system, i.e., each transition involves one single qubit only. By means of a systematic comparison between the predictions of these two models, we show that, while the models are actually equivalent in the case of flat reservoir spectra, they give very different predictions in the case of structured environments, so that a naive introduction of a phenomenological model can be inappropriate.

The paper is organized as follows. In Sec. II we briefly describe the main features of a tripartite flux qubit system and of a possible coupling scheme which allow us to control at will the interaction between each flux qubit and one of them playing the role of a mediator. We moreover give the microscopic master equation describing this tripartite system. Section III is devoted to the solution of the master equation at zero temperature whereas Sec. IV the analysis of the dynamics starting from appropriate initial conditions exploiting both the microscopic and phenomenological approaches. Concluding remarks are finally summarized in Sec. V.

The physical system and the microscopic Master equation

Let us begin by briefly illustrating the main features of the tripartite system sketched in Fig. 1, extensively described in Ref. [19]. Two spatially separated flux qubits (named 2 and 3) are connected by tunable flux transformers to a third qubit (M) which plays the role of an entanglement mediator.

Each qubit loop is interrupted by three Josephson junctions. Two of them are characterized by the same Josephson energy E J and the third one possesses a lower Josephson energy αE J , with α < 1. If the operating flux bias φ (i)

x (i = M, 2, 3) applied by a coil to each qubit is close to φ 0 /2, φ 0 = h/2e being the flux quantum, a 3JJ qubit can be described in terms of two quantum states |L (i) and |R (i) corresponding to a clockwise and a counterclockwise supercurrent circulating in the loop, ±I

(i) p = 2παE (i)
J /φ 0 . In other words, in such conditions it is possible to realize an effective two state system whose Hamiltonian, in the basis of the energy eigenstates φx (2) φx (3) Figure 1. Schematic of the system setup.

|0 i = 1 √ 2 [|L (i) + |R (i) ] and |1 i = 1 √ 2 [|L (i) -|R (i) ], assumes the form H (i) = ω i σ (i) + σ (i) -with σ (i) + = |1 i 0| and
σ (i) -= |0 i 1|.
Here the energy splitting ω i = ∆ 2 i + 2 i , typically of the order of 5 ÷ 10 GHz, depends on the tunneling frequency ∆ i between the two wells of the qubit potential and on the corresponding asymmetry i = 2I

(i) p (φ (i)
x -φ 0 /2). An inductive coupling between the qubits 2 or 3 and the mediator M can be realized via the tunable flux transformer described in Ref. [28]. As shown indeed by M. G. Castellano et al. [28] it is possible to control the flux-transfer function R(φ (i) cx ), and therefore the inductivecoupling constants, g M 2 and g M 3 , by properly setting the critical current of the inner dc-SQUID of each transformer via the additional bias fluxes φ In this way we may turn on and off at will the coupling between each qubit and the mediator, to realize as extensively discussed in Ref. [19], a unitary step-by-step scheme which allows us to generate the following W state of the whole system:

|W = 1 √ 3 |100 -i |010 -i |001 . (1)
Here we want to investigate the effects of dissipation on this generation scheme caused by environments. Let us start by briefly summarizing the scheme for the generation of the state (1) starting from the initial condition |100 of the three qubits, in which only the first qubit is excited, whereas the other two are in their ground states. Calling M the first qubit and 2 and 3 the other two, the scheme consists of two steps: in the first step the qubit M interacts for an interval of time τ 1 with the qubit 2 and the qubit 3 evolves freely, while in the second step the qubit M interacts for a time τ 2 with the qubit 3 and the qubit 2 evolves freely. The Hamiltonian models corresponding to these two steps are respectively:

H 1st = i=M,2,3 ω i σ (i) + σ (i) -+ g M 2 σ (M ) + σ (2) -+ σ (M ) -σ (2) + , (2)
and

H 2nd = i=M,2,3 ω i σ (i) + σ (i) -+ g M 3 σ (M ) + σ (3) -+ σ (M ) -σ (3) + . (3)
The explicit expressions for the eigenstates of

H 1st (H 2nd ) denoted by |a ⊗ |k 3 , |b ⊗ |k 3 , |c ⊗ |k 3 and |d ⊗ |k 3 (|a ⊗ |k 2 , |b ⊗ |k 2 , |c ⊗ |k 2 and |d ⊗ |k 2 )
, where k = 0, 1, and the corresponding eigenvalues are given in the Appendix. During these two steps, the three qubits suffer from environmental perturbations. We assume that each qubit interacts with a reservoir which is independent from the others, since the three qubits are spatially separated, and we exploit the results presented in Ref. [24], where a master equation for the evolution of two coupled qubits has been derived from a microscopic Hamiltonian, following the standard approach [START_REF] Breuer | The Theory of Open Quantum Systems[END_REF]. More in detail, given the Hamiltonian of a generic quantum system, the microscopically derived master equation, in the Born-Markov and rotating wave approximations, describes jumps occurring between the eigenstates of the Hamiltonian. Moreover in Ref. [24] the reservoirs are assumed to be independent, which is justified in the case of spatially separated Josephson qubits, since the noise in each device is due to impurities belonging to different parts of the whole superconducting circuit.

Our idea is now to use the dissipator appearing in that paper to describe the losses of the pair of coupled qubits both in the first and in the second step, while the dissipation relative to the free i-th qubit (i is equal either to 2 or 3, depending on the step considered) will be described as usual by terms like γ i (σ

(i) -ρσ (i) + -1 2 {σ (i) + σ (i)
-, ρ}). More in detail, exploiting the results presented in Ref. [24], in correspondence to the first step we can write:

ρ = -i[H 1st , ρ] + D M 2 (ρ) + D 3 (ρ), (4)
while for the second step the master equation can be given as:

ρ = -i[H 2nd , ρ] + D M 3 (ρ) + D 2 (ρ). (5)
The two dissipators D M 2 and D M 3 describe the losses of the combined systems of qubits M and 2, and qubits M and 3 respectively, and their structure can be directly obtained starting from Ref. [24]. In particular the dissipator in Eq. ( 4) can be written as:

D M 2 (ρ) = c I |a b|ρ(t)
where |a , |b , |c and |d are given by Eqs. (A.1) in the Appendix. The decay rates appearing in Eq. ( 6) are defined as:

c I = γ I,M cos 2 θ 2 + γ I,2 sin 2 θ 2 , (7)
c II = γ II,M sin 2 θ 2 + γ II,2 cos 2 θ 2 , (8)
c cr,I = γ I,M cos 2 θ 2 -γ I,2 sin 2 θ 2 , (9)
c cr,II = -γ II,M sin 2 θ 2 + γ II,2 cos 2 θ 2 , ( 10
)
where for brevity we have put γ I,j = γ j (ω I ) and γ II,j = γ j (ω II ), with

ω I = 1 2 (ω M + ω 2 ) - 1 2 (ω 2 -ω M ) 2 + g 2 M 2 , (11)
the Bohr frequency relative to the transitions |d → |c and |b → |a and

ω II = 1 2 (ω M + ω 2 ) + 1 2 (ω 2 -ω M ) 2 + g 2 M 2 , (12)
the Bohr frequency relative to the transitions |c → |a and |d → |b . The functions γ j (ω) are the Fourier transforms of the bath correlation functions of the jth reservoir (with j = M, 2, 3) [24], and are related to the j-th reservoir spectral density J j (ω) through the relation:

γ j (ω) = J j (ω)[1 + N j (ω)], (13)
with N j (ω) being the average number of photons in the mode of frequency ω. The excitation rates cI , cII , ccr,I and ccr,II can be directly obtained from Eqs. ( 7)-( 10) correspondingly substituting γ I,j by γI,j = γ I,j e -β j ω I and γ II,j by γII,j = γ II,j e -β j ω II , with β j the inverse temperature of the j-th reservoir.

In the same way, the dissipator in Eq. ( 5) is given by:

D M 3 (ρ) = c I |a b |ρ(t)|b a | - 1 2 {|b b |, ρ(t)} +c II |a c |ρ(t)|c a| - 1 2 {|c c |, ρ(t)} +c I |b d |ρ(t)|d b | - 1 2 {|d d |, ρ(t)} +c II |c d |ρ(t)|d c | - 1 2 {|d d |, ρ(t)} +c I |b a |ρ(t)|a b | - 1 2 {|a a |, ρ(t)} +c II |c a |ρ(t)|a c | - 1 2 {|a a |, ρ(t)} +c I |d b |ρ(t)|b d | - 1 2 {|b b |, ρ(t)} +c II |d c |ρ(t)|c d | - 1 2 {|c c |, ρ(t)} +c cr,I |a b |ρ(t)|d c | + |c d |ρ(t)|b a | +c cr,II |a c |ρ(t)|d b | + |b d |ρ(t)|c a | +c cr,I |d c |ρ(t)|a b | + |b a |ρ(t)|c d | +c cr,II |d b |ρ(t)|a c | + |c a |ρ(t)|b d | , (14)
where |a , |b , |c and |d are given by Eqs. (A.4) and:

c I = γ I,M cos 2 θ 2 + γ I,2 sin 2 θ 2 , ( 15
)
c II = γ II,M sin 2 θ 2 + γ II,2 cos 2 θ 2 , (16)
c cr,I = γ I,M cos 2 θ 2 -γ I,2 sin 2 θ 2 , (17)
c cr,II = -γ II,M sin 2 θ 2 + γ II,2 cos 2 θ 2 . (18)
The excitation rates c I , c II , c cr,I and c cr,II can be directly obtained from Eqs. ( 15)-( 18) correspondingly substituting γ I,j by γ I,j = γ I,j e -β j ω I and γ II,j by γ II,j = γ II,j e -β j ω II , where

ω I = 1 2 (ω M + ω 3 ) - 1 2 (ω 3 -ω M ) 2 + g 2 M 3 , (19)
ω II = 1 2 (ω M + ω 3 ) + 1 2 (ω 3 -ω M ) 2 + g 2 M 3 . (20)
Finally, we define the single qubit dissipators appearing in Eqs. ( 4) and ( 5)

D 3 (ρ) = γ 3 σ (3)
-ρσ

+ -

1 2 {σ (3) + σ (3)
-, ρ}

+ γ3 σ (3)
+ ρσ

--

1 2 {σ (3) -σ (3)
+ , ρ} , (21)
D 2 (ρ) = γ 2 σ (2)
-ρσ

+ -

1 2 {σ (2) + σ (2)
-, ρ}

+ γ2 σ (2)
+ ρσ

--

1 2 {σ (2) -σ (2)
+ , ρ} ,

where γ 3 = γ 3 (ω 3 ) and γ 2 = γ 2 (ω 2 ) (γ 3 = γ 3 e -β j ω 3 and γ2 = γ 2 e -β j ω 2 ) are the decay (excitation) rates of the qubits 3 and 2, which evolve freely during the first and second step, respectively.

Having at our disposal the master equation microscopically derived, we can analyze the dynamics of the system putting into evidence the effects of the presence of the external world on the generation of W states. In addition, the knowledge of such a master equation gives us the possibility to test the validity of phenomenological master equations generally used to describe physical systems like the one examined in the present paper. A phenomenological approach would suggest us to adopt the following equation to describe the dynamics of the system under scrutiny

ρ = -i[H, ρ] + i=M,2,3 γ i σ (i) -ρσ (i) + - 1 2 {σ (i) + σ (i) -, ρ} + i=M,2,3 γi σ (i) + ρσ (i) -- 1 2 {σ (i) -σ (i) + , ρ} , (23)
where H is equal to either H 1st or H 2nd depending on the step considered, while the dissipator is the same for both steps. In what follows we refer to Eq. ( 23) as the phenomenological master equation.

Solution of the microscopic model at zero temperature

From now on, we will call a microscopic model the set of master equations ( 4) and ( 5), while we will call a phenomenological model the master equation (23).

Let us start with the microscopic model. We will focus on the zero-temperature case, i.e., we will put all the excitation rates equal to zero. The initial state we consider is |100 , which, in terms of the eigenstates of the first step corresponds to a density operator where the only nonzero matrix elements are between |b0 and |c0

|100 100| = cos θ 2 |b + sin θ 2 |c cos θ 2 b| + sin θ 2 c| ⊗ |0 3 0| = cos θ 2 |b0 + sin θ 2 |c0 cos θ 2 b0| + sin θ 2 c0| . (24)
Thus the only differential equations of interest, derivable from the master equation ( 4), are the following ones:

ρc0,c0 = γ 3 ρ c1,c1 -c II ρ c0,c0 , ρc1,c1 = -(γ 3 + c II )ρ c1,c1 , (25)
ρb0,b0 = γ 3 ρ b1,b1 -c I ρ b0,b0 ,

ρb1,b1 = -(γ 3 + c I )ρ b1,b1 , (26)
ρa0,a0 = γ 3 ρ a1,a1 + c I ρ b0,b0 + c II ρ c0,c0 ,

ρa1,a1 = -γ 3 ρ a1,a1 + c I ρ b1,b1 + c II ρ c1,c1 , (27) ρb0
,c0 = iω cb - c I + c II 2 ρ b0,c0 + γ 3 ρ b1,c1 , ρb1,c1 = iω cb -γ 3 - c I + c II 2 ρ b1,c1 , (28)
where

ω cb = E c -E b .
Solving these equations, we are able to demonstrate that at t = τ 1 , namely at the end of the first step, the state of the system reads as ρ(τ 1 ) = ρ a0,a0 (τ 1 )|a0 a0| + ρ b0,b0 (τ 1 )|b0 b0| + ρ c0,c0 (τ 1 )|c0 c0|

+ ρ b0,c0 (τ 1 )|b0 c0| + ρ * b0,c0 (τ 1 )|c0 b0|, (29)
where

ρ c0,c0 (τ 1 ) = ρ c0,c0 (0) e -c II τ 1 , (30)
ρ b0,b0 (τ 1 ) = ρ b0,b0 (0) e -c I τ 1 , (31)
ρ a0,a0 (τ 1 ) = 1 -ρ b0,b0 (0) e -c I τ 1 -ρ c0,c0 (0) e -c II τ 1 , (32)
ρ b0,c0 (τ 1 ) = ρ b0,c0 (0) e (iωcb-c I +c II 2 ) τ 1 . (33)
The state described by Eq. ( 29) represents the initial condition for step 2. In the basis of the eigenstates of the Hamiltonian (3), it reads:

ρ(τ 1 ) = ρ a 0,a 0 (τ 1 )|a 0 a 0| + ρ b 0,b 0 (τ 1 )|b 0 b 0| + ρ c 0,c 0 (τ 1 )|c 0 c 0| + ρ a 1,a 1 (τ 1 )|a 1 a 1| + ρ b 0,c 0 (τ 1 )|b 0 c 0| + ρ * b 0,c 0 (τ 1 )|c 0 b 0| + ρ b 0,a 1 (τ 1 )|b 0 a 1| + ρ * b 0,a 1 (τ 1 )|a 1 b 0| + ρ c 0,a 1 (τ 1 )|c 0 a 1| + ρ * c 0,a 1 (τ 1 )|a 1 c 0|, (34)
where

ρ a 1,a 1 (τ 1 ) = ρ b0,b0 (τ 1 ) sin 2 θ 2 + ρ c0,c0 (τ 1 ) cos 2 θ 2 -2 Re[ρ b0,c0 (τ 1 )] sin θ 2 cos θ 2 , ( 35
) sin θ 2 . ( 41
)
Starting from this initial condition, it is straightforward to see that the only differential equations of interest, derivable from the master equation ( 5), describing the dynamics of the system during the second step at

T = 0 K, are ρc 0,c 0 = γ 2 ρ c 1,c 1 -c II ρ c 0,c 0 , ρc 1,c 1 = -(γ 2 + c II ) ρ c 1,c 1 , ( 42
) ρb 0,b 0 = γ 2 ρ b 1,b 1 -c I ρ b 0,b 0 , ρb 1,b 1 = -(γ 2 + c I ) ρ b 1,b 1 , (43)
ρa 0,a 0 = γ 2 ρ a 1,a 1 + c I ρ b 0,b 0 + c II ρ c 0,c 0 ,

ρa 1,a 1 = -γ 2 ρ a 1,a 1 + c I ρ b 1,b 1 + c II ρ c 1,c 1 , (44)
for the populations and for the coherences

ρc 0,a 1 = -iω II -ω 2 + γ 2 + c II 2 ρ c 0,a 1 + c cr,I ρ d 0,b 1 , ρd 0,b 1 = -iω II + ω 2 + γ 2 + 2c I + c II 2 ρ d 0,b 1 , ( 45
) ρb 0,a 1 = -iω I + ω 2 + γ 2 + c I 2 ρ b 0,a 1 + c cr,II ρ d 0,c 1 , ρd 0,c 1 = -iω I + ω 2 + γ 2 + c I + 2c II 2 ρ d 0,c 1 , ( 46
) ρb 0,c 0 = iω c b - c I + c II 2 ρ b 0,c 0 + γ 2 ρ b 1,c 1 , ρb 1,c 1 = iω c b -γ 2 - c I + c II 2 ρ b 1,c 1 , (47)
where ω c b = E c -E b . Also in this case, it is possible to verify that the solutions of these differential equations are given by ρ a 1,a 1 (t) = ρ a 1,a 1 (τ 1 ) e -γ 2 (t-τ 1 ) , (48)

ρ c 0,c 0 (t) = ρ c 0,c 0 (τ 1 ) e -c II (t-τ 1 ) , ( 49
)
ρ b 0,b 0 (t) = ρ b 0,b 0 (τ 1 ) e -c I (t-τ 1 ) , ( 50
)
ρ a 0,a 0 (t) = 1 -ρ b 0,b 0 (τ 1 ) e c I (t-τ 1 ) -ρ c 0,c 0 (0) e c II (t-τ 1 )
-ρ a 1,a 1 (τ 1 ) e -γ 2 (t-τ 1 ) , (51)

ρ c 0,a 1 (t) = ρ c 0,a 1 (τ 1 ) e " -iω II +iω 2 - γ 2 +c II 2 « (t-τ 1 ) , ( 52
)
ρ b 0,a 1 (t) = ρ b 0,a 1 (τ 1 ) e " -iω I +iω 2 - γ 2 +c I 2 « (t-τ 1 ) , ( 53
)
ρ b 0,c 0 (t) = ρ b0,c0 (τ 1 ) e " iω c b - c I +c II 2 « (t-τ 1 )
.

At this point it is convenient to write the density matrix describing the system during the second step, i.e. at a generic instant of time t > τ 1 in the basis of the qubits eigenstates {|klm } ≡ {|k 1 ⊗ |l 2 ⊗ |m 3 } with k, l, m = 0, 1:

ρ(t) = ρ 000,
where ρ 000,000 (t) = ρ a 0,a 0 (t), (56)

ρ 100,100 (t) = ρ b 0,b 0 (t) cos 2 θ 2 + ρ c 0,c 0 (t) sin 2 θ 2 + 2 Re[ρ b 0,c 0 (t)] sin θ 2 cos θ 2 , ( 57
)
ρ 010,010 (t) = ρ a 1,a 1 (t), ( 58
)
ρ 001,001 (t) = ρ b 0,b 0 (t) sin 2 θ 2 + ρ c 0,c 0 (t) cos 2 θ 2 -2 Re[ρ b 0,c 0 (t)] sin θ 2 cos θ 2 , ( 59
)
ρ 100,010 (t) = ρ b 0,a 1 (t) cos θ 2 + ρ c 0,a 1 (t) sin θ 2 , ( 60
)
ρ 100,001 (t) = [-ρ b 0,b 0 (t) + ρ c 0,c 0 (t)] sin θ 2 cos θ 2 + ρ b 0,c 0 (t) cos 2 θ 2 -ρ * b 0,c 0 (t) sin 2 θ 2 , ( 61
)
ρ 001,010 (t) = -ρ b 0,a 1 (t) sin θ 2 + ρ c 0,a 1 (t) cos θ 2 . ( 62
)
From Eqs. ( 55)-( 62) one can obtain all the information about the effects of dissipation on the system dynamics.

The system dynamics: microscopic and phenomenological approaches

Exploiting the results obtained in the previous section, we now analyze the effects of the reservoirs on the generation of the W state given in Eq. (1). In what follows we assume g M 2 = g M 3 and ω M = ω 2 = ω 3 = 10g M 2 , which are typical values for the current superconducting technology [START_REF] You | [END_REF].

The scope of the analysis will be twofold. On one hand we want to point out how the losses affect the scheme for the generation of the W state. On the other hand, we want to compare the predictions of our model given by Eqs. ( 4)-( 5) with those predicted by the phenomenological model in Eq. ( 23), in order to understand the limits of validity of the latter. We calculate the fidelity F = W |ρ(τ 1 , τ 2 )|W of the density matrix of the system at the time t = τ 1 + τ 2 with respect to the target state |W in Eq. ( 1). Figure 2 displays the time dependence of this function with respect to the durations τ 1 and τ 2 of the two steps of the generation scheme. The maximum of the fidelity, which is around 0.76, is calculated by considering decay rates of the order of 0.1g M 2 and corresponds to a choice of times very close to that in Ref. [19], i.e., τ1 = 2g -1 M 2 arcsin(1/ √ 3) and τ2 = 2g -1 M 3 arccos(1/ √ 2). As foreseeable the interaction of each qubit with the reservoir significantly affects the W-state generation scheme. For this reason, even if for some purposes a value of 75% can be reasonable, it can be of interest to identify the state reached at the time instants considered. A reasonable guess would be to assume that, at the time instants τ1 = 2g -1 M 2 arcsin(1/ √ 3) and τ2 = 2g -1 M 3 arccos(1/ √ 2) the state is described by a Werner-like state ρ W = p|000 000| + (1 -p)|W W |, where p is the (time-dependent) probability that at t = τ1 + τ2 the system is found in its ground state |000 [31]. In order to verify that this is indeed the case, we calculate the fidelity

F (τ 1 , τ2 ) = T r √ ρ W ρ(τ 1 , τ2 ) √ ρ W ,
finding that it is about 0.98. We may thus conclude that, when dissipative effects are not negligible, the step-by-step scheme described in Ref. [19] can be exploited to generate the Werner-like state ρ W instead of the W state defined in Eq. ( 1). Since one can wonder how the predictions change if one uses the phenomenological model to describe losses, let us now compare the predictions of the microscopic model just analyzed and the numerical solution of the phenomenological master equation (23). A good measure of the discrepancy between the predictions of the two models is the Here ω M = ω 2 = ω 3 = 10g M 2 , the decay rates are of the order of 0.1g M 2 and the times are in units of g -1

M 2 = g -1 M 3 .
trace distance [START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF]

D(ρ mic , ρ phen ) = 1 2 Tr(|ρ mic -ρ phen |), (63)
which quantifies the imbalance between the probability distributions described by the states ρ mic , predicted by the microscopic model, and ρ phen , predicted by the phenomenological one. We choose the same Lorentzian shape for the spectra of the three reservoirs

J(ω) = γ 0 λ 2 (ω -ω 0 ) 2 + λ 2 (64)
with ω 0 = ω M = ω 2 = ω 3 . For very large values of the width λ one recovers the results for flat spectrum and the decay rates are all equal to the qubit-reservoir coupling constant γ 0 . We calculate the trace distance (63) for two cases: a) λ = 1000 g M 2 and γ 0 = 0.1g M 2 , which corresponds to losses with flat spectrum; b) λ = 0.01 g M 2 and γ 0 = 0.1g M 2 , which corresponds to losses for a very structured reservoir. Numerical simulations of the phenomenological model in the first case (not shown in figures), clearly demonstrate that, when the spectra of the reservoirs are equal and flat, the distance between the two states is very small. Therefore the effect of losses are essentially the same for both models, so that we may claim that the microscopically derived master equation is equivalent to the phenomenological one in such a case. A similar conclusion was previously found in the context of cavity-QED, where a phenomenological model of cavity losses, with the dissipative part of the master equation depending only on the single-mode operators, turns out to be microscopically justifiable in the case of flat reservoir spectrum [START_REF] Scala | [END_REF]34].

In the second case of structured spectrum, instead, the values of the decay rates are very sensitive to the Bohr frequencies at which they are evaluated. As a consequence, as shown in Fig. 3, the trace distance between the states predicted by the phenomenological and microscopic models can reach very large values. In order to understand the origin of the large distance between the states predicted in this last case, one can look at the dynamical behavior of the populations of the states of the system predicted by the two models. Figures 4 (a), (b) and (c) show, as a function of the interaction times τ 1 and τ 2 , the populations of the states |000 , |010 and |001 , correspondingly, calculated exploiting the phenomenological (top) and the microscopic (bottom) models. From Fig. 4(a) it is clear that, while in the phenomenological model (top), all the excitations decay exponentially with the same rate with respect to both τ 1 and τ 2 , in the microscopic model (bottom) the role of the two interaction times is very asymmetric: indeed, by varying the duration τ 1 of the first step, one obtains initial states for the second step characterized by very different decay rates, so that some excitation is trapped or not in the system according to the value of τ 1 .

Consider now the decay properties of the population of the state |010 for the the phenomenological and microscopic models. Figure 4(b) (bottom) in particular shows that, depending on the choice of τ 1 , the initial condition of the second step oscillates with almost no damping, and then the state decays with the single-qubit decay rate.

As far as the decay properties of the state |001 are concerned, Figs. 4 (c) show that, while in the phenomenological model the oscillations between qubits M and 3 decay rapidly, in the microscopic model the oscillations are conserved for much longer times: this is due to the fact that in the microscopic model the decay rates are proportional to the value of the spectrum at the Bohr frequencies between dressed states, as one can see from Eqs. ( 13)-( 12) and ( 15)- (20), and therefore, for the spectrum chosen in our example, they are much smaller than the decay rates in the phenomenological model, which are proportional to the value of the spectrum at the single-qubit frequencies, i.e., to its maximum. More in detail, for the spectrum and the value of λ we are considering here (namely λ = 0.01g M 2 ), the single qubit decay rate is equal to γ 0 = 0.1g M 2 , while it is straightforward to show that the decay rates of the states involving the second qubit in the first step are equal to J(ω I ) J(ω II ) 0.4 • 10 -4 g M 2 . The very small decay rates for the states involving the second qubit in the first step give rise to phenomena of population trapping, whose consequence is the conservation of the population oscillations with respect to the interaction time τ 1 in Fig. 4(b) (bottom). This point is analogous to what was previously found during the study of a microscopic non-Markovian model for cavity losses in cavity-QED [35].

Conclusions

In this paper, we have analyzed the effects of losses on a scheme of generation of multipartite entanglement. At the time instants of interest, the fidelity between the actual state of the system and the target state |W is about 75%. The deviation from unity can simply be understood as due to the fact that the system has decayed to the ground state |000 . Thus, the scheme becomes a protocol aimed at the generation of a Werner-like state ρ W = P |000 000| + (1 -P ) |W W |. We wish to underline that this statement is true when we consider a flat spectrum at T = 0 K. Moreover, the comparison between our microscopic model and a naiver but more popular phenomenological master equation has given us an occasion to understand the limit of a phenomenological approach in the context of our problem. In fact, we found that the predictions of the phenomenological and the microscopic approaches do not differ much when the spectra of the reservoirs are flat. However, when the reservoirs are structured the two models predict very different results, and in the microscopic model, the population trapping phenomena can occur, due to the very different values of the various decay rates involved, which cannot be predicted by the phenomenological master equation. This is an example in which the phenomenological model can lead to very different phenomena from those predicted by the master equation derived from the microscopic Hamiltonian.

Of course, at this stage of our study of structured reservoirs, we have only considered effects which occur at times much longer than the correlation times of the reservoirs. When this is not the case, a more complete non-Markovian theory must be adopted, for instance by means of a time-convolutionless master equation. In this case, the various decay rates would be time dependent, and would become stationary, and proportional to the value of the spectra at the relevant Bohr frequencies, only at times much longer than the memory times of the baths. This issue, as well as the study of other sources of noise typical of Josephson junctions, such as 1/f and single impurity noise, will be the subject of future work.

, cos θ = |ω 2 -ω M | (ω 2 -ω M ) 2 + g 2 M 2
.

(A.

2)

The corresponding eigenvalues are

E a = 0, E b = 1 2 (ω M + ω 2 ) - 1 2 (ω 2 -ω M ) 2 + g 2 M 2 , E c = 1 2 (ω M + ω 2 ) + 1 2 (ω 2 -ω M ) 2 + g 2 M 2 , E d = ω M + ω 2 .
(A.3)

2 Figure 2 .

 22 Figure 2. Dependence of the fidelity F on the durations of the two steps τ 1 and τ 2 .Here ω M = ω 2 = ω 3 = 10g M 2 , the decay rates are of the order of 0.1g M 2 and the times are in units of g -1 M 2 = g -1 M 3 .

2 Figure 3 .

 23 Figure 3. Distance between the microscopically and phenomenologically derived states for λ = 0.01g M 2 and γ 0 = 0.1g M 2 as a function of τ 1 and τ 2 . The times are in units of g -1 M 2 = g -1 M 3 .

Figure 4 .

 4 Figure 4. Populations of states (a) |000 , (b) |010 and (c) |100 calculated by the phenomenological (top) and microscopic (bottom) models with λ = 0.01g M 2 and γ 0 = 0.1g M 2 , as functions of the interaction times τ 1 and τ 2 (in units of g -1 M 2 = g -1 M 3 ).

Acknowledgements

This work is partly supported by the bilateral Italian-Japanese Project II04C1AF4E. Support from MIUR Projects No. II04C0E3F3 and PRIN 2008 (2008C3J43 003) is also acknowledged.

Appendix A.

In this Appendix, we list the eigenstates and eigenvalues of the Hamiltonians (2) and ( 3), corresponding to the first and second steps, respectively. Both sets of eigenstates and eigenvalues can be obtained by a straightforward diagonalization of the Hamiltonians.

The eigenstates of the Hamiltonian (2) are |a ⊗ |k 3 , |b ⊗ |k 3 , |c ⊗ |k 3 and (A.4)

The corresponding eigenvalues are

(A.6)


M Richter
email: mathias.richter@ptb.de

Atomic plasma excitations in the field of a soft x-ray laser

Keywords: numbers: 32.80.Aa, 32.80.Rm, 41.60.Cr, 42.50.Hz

The interaction of atoms with short-wavelength radiation at ultra-high intensities is described by plasma excitation. In contrast to former works on optical radiation and ponderomotive motion of quasi-free electrons, the excitation of correlated and bound electrons is considered here. The ponderomotive motion of a free electron is included as a special case. Values for the energy transfer from the radiation field to an atom are obtained in fair agreement with the unexpectedly high charge states of xenon recently observed at the soft x-ray free electron laser FLASH.

Introduction

With the recent set-up of the first x-ray free-electron laser (FEL) facilities in Europe [1], Japan [2], and the United States [3], a long-cherished vision of the science community has come true. The highly intense and ultra-short soft and hard x-ray laser pulses allow time-resolved imaging of advanced materials with femtosecond resolution for many applications [4][5][6][7]. It concerns, for example, the investigation of fast chemical reactions on surfaces or within biological systems by means of microscopic snapshots. The first experiments in microbeams have, however, demonstrated that the mechanisms of photon-matter interaction with high-intensity x-rays may be affected by nonlinear processes which elude a description by the current theoretical models developed for high-intensity radiation in the optical regime [8,9]. The latter concerns, in particular, the semi-classical theories based on the ponderomotive motion of individual quasi-free Rydberg electrons driven by the oscillating field of the electromagnetic wave [10][11][START_REF] Delone | Multiphoton Processes in Atoms[END_REF].

In the present theoretical work, the specific aspects of x-rays, namely excitations of correlated and bound inner-shell electrons are considered. It was initiated by the surprising results of the Xe photoionization experiments performed at the free electron laser FLASH [8,9]. In the so-called extreme ultra-violet (EUV) spectral sub-range at around 90 eV photon energy and at irradiance levels in the order of 10 16 W cm -2 , charge states up to Xe 21+ were observed whose generation, starting from neutral Xe atoms, requires a total energy of more than 5,000 eV. Thus, almost 60 EUV photons must have been absorbed by an individual atom within the estimated FLASH pulse duration of 10 to 20 fs.

In a first theoretical study, this high degree of photoionization was explained by a sequence of oneand multiphoton ionization processes in which an ion created in a preceding step represents the target for a subsequent step [START_REF] Makris | [END_REF]. Sequential multiphoton ionization has explained fairly well recent experiments at soft or hard X-ray lasers [14][15][16][17]. In the case of Xe 21+ , however, this approach has to consider at least 19 steps to generate the high charge state from neutral Xe, which is related to 19 coupled differential rate equations with 19 individual multiphoton ionization cross sections. So far, the latter could not be calculated from first principles but were only obtained through a technique of scaling, with occasional adjustment to the experimental data. An ab initio calculation which describes the interaction of 60 individual photons with the 54 electrons of the Xe atom within the framework of perturbation theory seems to be, in fact, a challenging task, in particular if electron-electron correlation is taken into account.

In the spectral range of optical radiation, photon-electron interactions at ultra-high intensities may also be described by so-called non-perturbative theories [10][11][START_REF] Delone | Multiphoton Processes in Atoms[END_REF]. Their applicability depends on the ponderomotive energy U p :

I U p ≈ (1)
which represents the quiver energy transferred from the oscillating field of an electromagnetic wave with frequency ω and irradiance I to a free electron. To a good approximation, this expression is valid also for a weakly bound electron, e.g. in a Rydberg state, but not for a bound inner-shell electron. In the EUV and (soft) X-ray regime, however, the photoelectric effect [18], i.e. the photoexcitation of bound inner and outer electrons into the continuum is the dominant process. Weakly bound electrons and Rydberg states generally play a minor role. Thus, semi-classical theories which are based on the ponderomotive motion of quasi-free electrons are not adequate to describe strong-field phenomena in the EUV and soft X-ray range. In the present work, therefore, the idea of the individual motion of a quasi-free outer-shell electron in the field of an optical wave is extended to collective plasma oscillations of correlated bound inner-shell electrons.

Outline of the model

The idea of plasma excitations has initially been developed for the electron gas in a solid metal as described in textbooks [START_REF] Ch | Introduction to Solid State Physics[END_REF]. For many years, however, models of collective electron oscillations have already been applied to describe also the so-called atomic giant resonances of Xe and the subsequent elements in the EUV at low photon intensities [START_REF] Fano | [END_REF][21][START_REF]Giant Resonances in Atoms, Molecules, and Solids[END_REF][START_REF] Amusia | [END_REF]. These strong and broad continuum resonances represent prime examples for the impact of electron correlation on inner-shell photoionization. In the following, the simplest approximations for plasma oscillations, i.e. the equations of a damped harmonic oscillator are used to express the energy transfer from a high-intensity EUV field to the Xe atom in terms of its giant resonance. For this purpose, we start with the displacement of the negative electron charge distribution of an atom from its equilibrium position as shown in figure 1. Binding to the positive nucleus induces a reset force which in first order approximation is proportional to the displacement. It results in a square binding potential and the differential equation of a damped harmonic oscillator, here excited by an oscillating force F cos(ωt):

( ) t m N F x x x cos 2 2 res = +
Equation 2 relates to the displacement in x-direction of a charge distribution of N electrons with the electron mass m whose structure is not affected. The resonance frequency is denoted by ω res and the damping ratio by γ/ω res so that the solution of equation 2 may be expressed by:

( ) ( ) ( ) ( ) ( ) 2 2 2 2 res 0 0 2 cos + - = - = m N F x t x t x φ (3)
with the phase φ. In the case of an electromagnetic force with irradiance I:

2 2 0 2 0 2 2 F e c E c I = = , (4)
where c denotes the speed of light, ε 0 the vacuum permittivity, E the electric field strength, and e the elementary charge, the kinetic energy of the electrons is given by:

( ) φ - = = t x m N x m N U kin sin 2 2 2 2 2 0 2 & (5a) ( ) ( ) ( ) ( ) 2 2 2 2 res 2 2 2 2 2 0 res res 4 h h h h h h h h h h + + + - = = I N a R x m N U B y kin . ( 5b
)
Here, a B denotes the Bohr radius, R y the Rydberg energy, and α the fine structure constant. For a single free electron without any binding, one obtains the kinetic energy from equation 5b by setting N=1, ω res =0 and γ=0 which leads directly to equation 1. Hence, the present model so far represents also an extension for the classical treatment of ponderomotive motion from a single free electron to many correlated electrons which are bond.

In the presence of a binding (ω res 0), the potential energy is given by:

( ) φ - = = t x m N x m N U pot cos 2 2 2 2 res 2 0 2 2 res (6a) kin pot U x m N U 2 2 res 2 res 2 0 4 = = . ( 6b
)
Moreover, for a damped oscillation (ω res 0, γ 0), the damping energy may be calculated according to:

( ) ′ - = ′ = = t t damp t d t x m N t d x m N dx x m N U 0 2 2 2 0 0 2 sin 2 2 2 φ & & (7a) kin damp U t x m N t U 4 2 2 0 = = . ( 7b
)
According to equation 7b, the mean damping energy absorbed by the system increases linearly with time, whereas the averaged kinetic and potential energies, according to equations 5b and 6b, remain constant in the case of a stationary oscillation as discussed here. For the total energy of the oscillation, one obtains therefore:

+ + = + + = t U U U U U kin damp pot kin tot 4 1 2 2 res (8a) ( ) ( ) ( ) ( ) . 4 4 1 4 4 2 2 2 2 res 2 2 2 1 2 2 res res res h h h h h h h h h h & & + + - + - = + + = = = I N a R t U U U U B y tot kin damp tot (8b)
Finally, the total energy of our damped plasma oscillation is related to the cross section of the corresponding photoexcitation process which is defined as the rate of absorbed photons per atom at abs N N & normalized to the photon flux density h I :

( ) ( ) ( ) ( ) 2 2 2 2 res 2 2 2 res res 4 h h h h h h h h h h & h & + + + - = = = N a R I U I N N B y tot at abs . ( 9
)

Application of the model

Equation 9 may now be applied to fit the data points of the photoabsorption cross section of Xe in the range of the 4d giant resonance, as shown by the thick solid line in figure 2. The agreement between the model curve and the experimental data is fairly well. As a result, one obtains within 1 % standard uncertainty the fitting parameters hω res = 100.0 eV, hγ = 17.2 eV, and N = 14. The latter value is higher than the oscillator strength of the ten 4d electrons only but lower than the oscillator strength of the eighteen 4d, 5p, and 5s electrons which are known to all couple to the 4d giant resonance [START_REF] Fano | [END_REF][21][START_REF]Giant Resonances in Atoms, Molecules, and Solids[END_REF][START_REF] Amusia | [END_REF].

In a further step, one may calculate now the total energy of the oscillating 4d, 5p, and 5s shells in Xe according to the equations 8a and 5b and obtains in the resonance case (hω= hω res ):

tot U / eV 1.79 × (I / 10 13 W cm -2 ) × (t / fs). (10) Equation 10 is valid for t >> (2γ) -1 0.02 fs, e.g. for sufficiently long photon pulses as in the case for FLASH with a pulse duration of /10 fs at about 100 eV photon energy [1]. At FLASH, furthermore, the basic assumption for the present model of a stationary oscillation is valid because the FLASH pulse duration is also more than two orders of magnitude longer than the oscillation period of 2π/ω res = h /100 eV 0.04 fs.

The linear temporal increase of the total energy with time in equation 10 is due to the accumulation of damping energy within the system as already expressed by equation 7b. Apart from radiative and nonradiative emissions, internal friction within the plasma due to electron-electron correlation and coupling may, cause damping, in particular if the damping is as high as for the very broad 4d giant resonance in Xe with γ/ω res = 0.172. The accumulation of damping energy by the atom leads, then, to the heating of its electron system which, thus, becomes a sort of hot sub-nano electron plasma from which, statistically, electrons may gain sufficient energy to leave the atom. The mean FLASH pulse duration scales with the wavelength and may meanwhile be estimated to amount to t = (15 ± 5) fs in the EUV at about 13 nm for the period from 2006 to 2009 when the Xe results [8,9] were obtained. It is, thus, about 50 % longer than previously assumed [24]. With this value for t, one may, hence, according to equation 10, calculate the absorbed plasma heating energy of the 4d (and 5p and 5s) electrons in Xe as a function of irradiance I and from that, using literature data for the respective ionization potentials [25], the highest Xe charge state which may be reached at FLASH at about 100 eV photon energy as a function of irradiance. The result is shown by the rectangles in figure 3 in comparison to the corresponding experimental data obtained at 90.5 and 93 eV photon energy [8,9], which are shown by the filled circles.

Since the total energy absorbed by an atom may be partially transferred also as excess energy to the emitted photoelectrons and -as a result of subsequent non-radiative decay of inner-shell vacancies -to emitted Auger electrons, the measured highest charges must be lower than those calculated from the total energy absorbed and the respective ionization potentials. This is the case for all irradiances except for the lowest at 1.4 × 10 14 W cm -2 , as can be seen in figure 3. However, this point is already close to the lower limit for the classical calculation of energy absorbed per atom from a radiation field which, since Einstein [18], has been defined by: tot U >> hω (11) and for the present case, according to equation 10 with t = 15 fs, by I >> 4 × 10 13 W cm -2 . For lower irradiances, the distribution of energy among the target atoms is no longer homogeneous but rather statistical and those atoms which are hit by photons absorb more than the mean absorption energy per atom. Accordingly, the achievable charge states here should be, in fact, generally higher than predicted by the present model. It should be noted that the limit of the present semi-classical approach as defined by equation 11 corresponds also to the limit for ponderomotive energy of (quasi-)free electrons to, again, distinguish the non-perturbative from the perturbative regime [10][11][START_REF] Delone | Multiphoton Processes in Atoms[END_REF].

At high irradiances, the measured highest charge states of Xe shown in figure 3 seem to be limited to about 22 (dashed line in figure 3), which is not the case for the calculated values. The latter just increase monotonically with the mean energy absorbed per atom. In practice, however, the highest charge state is limited by the number of electrons which may be involved, either in the primary photoionization process or in the subsequent Auger decay. In the present case of the 4d giant resonance in Xe, these are the ten 4d electrons and the eight 5s and 5p electrons, i.e. 18, which might be slightly further increased by 4p-4d mixing [START_REF] Wendin | Breakdown of the One-Electron Pictures in Photoelectron Spectra[END_REF].

Conclusion

In conclusion, the present semi-classical model represents a straightforward extension of theories for ponderomotive motion of outer quasi-free electrons in strong laser fields to strongly correlated innershell electrons in the approximation of a harmonic potential for binding. In the resulting solution of a damped harmonic plasma oscillation, damping is interpreted to be mainly due to electron-electron correlation. In this view, the damping energy absorbed from the field leads to a sort of electron heating and, consequently, to electron emission. Fair agreement with experimental data is obtained for the total energy absorbed and the highest charge state achievable in the case of Xe excited in the extreme ultraviolet at ultra-high intensities. The model may be used as a starting point to calculate from the energy transfer to the atom also the intensity dependences of the individual charge states by means of a suitable statistical model in analogy to recent cluster theories [27].

Figure captions

Figure 1 .

 1 Figure 1. Negative electron charge distribution of an atom (blue) oscillating in x-direction with respect to the positive nucleus (red).

Figure 2 .

 2 Figure 2. Photoabsorption cross section of Xe at the 4d giant resonance (experimental data: points; Relativistic Time-Dependent Local Density Approximation (RTDLDA): thin solid line; Relativistic Random Phase Approximation (RRPA): dashed line) [21]. The thick solid line shows the fitting result of the present model (equation 9) with hω res = 100.0 eV, hγ = 17.2 eV, and N = 14. ω = 1 a.u. corresponds to hω 27.2 eV, 1 Mb = 10 -18 cm 2 .

Figure 3 .

 3 Figure 3. Highest charge states of Xe generated by (15 ± 5) fs EUV pulses as a function of irradiance (filled circles: experimental data [8, 9]; rectangles: calculated within the present model for the pulse duration range from 10 to 20 fs).

Figure 1 (Figure 2 (Figure 3 (

 123 Figure 1 (Fig1_(new)Displacement.eps)

& & &(2)

Acknowledgement

The author would like to thank S. V. Bobashev, A. Kato, B. F. Sonntag, A. A. Sorokin, K. Tiedtke, G.

Ulm, and P. Zimmermann for support und many helpful discussions.


Sébastien Bubeck

Gilles Stoltz

Jia Yuan

Lipschitz Bandits without the Lipschitz Constant

We consider the setting of stochastic bandit problems with a continuum of arms indexed by [0, 1] d . We first point out that the strategies considered so far in the literature only provided theoretical guarantees of the form: given some tuning parameters, the regret is small with respect to a class of environments that depends on these parameters. This is however not the right perspective, as it is the strategy that should adapt to the specific bandit environment at hand, and not the other way round. Put differently, an adaptation issue is raised. We solve it for the special case of environments whose mean-payoff functions are globally Lipschitz. More precisely, we show that the minimax optimal orders of magnitude L d/(d+2) T (d+1)/(d+2) of the regret bound over T time instances against an environment whose mean-payoff function f is Lipschitz with constant L can be achieved without knowing L or T in advance. This is in contrast to all previously known strategies, which require to some extent the knowledge of L to achieve this performance guarantee.

Introduction

In the (stochastic) bandit problem, a gambler tries to maximize the revenue gained by sequentially playing one of a finite number of arms that are each associated with initially unknown (and potentially different) payoff distributions [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF]. The gambler selects and pulls arms one by one in a sequential manner, simultaneously learning about the machines' payoff-distributions and accumulating rewards (or losses). Thus, in order to maximize his gain, the gambler must choose the next arm by taking into consideration both the urgency of gaining reward ("exploitation") and acquiring new information ("exploration"). Maximizing the total cumulative payoff is equivalent to minimizing the (total) regret, that is, minimizing the difference between the total cumulative payoff of the gambler and that of another clairvoyant gambler who chooses the arm with the best mean-payoff in every round. The quality of the gambler's strategy can be characterized by the rate of growth of his expected regret with time. In particular, if this rate of growth is sublinear, the gambler in the long run plays as well as his clairvoyant counterpart.

Continuum-armed bandit problems. Although the early papers studied bandits with a finite number of arms, researchers soon realized that bandits with infinitely many arms are also interesting, as well as practically significant. One particularly important case is when the arms are identified by a finite number of continuous-valued parameters, resulting in online optimization problems over continuous finite-dimensional spaces. During the last decades numerous contributions have investigated such continuum-armed bandit problems, starting from the early formulations of [START_REF]The continuum-armed bandit problem[END_REF][START_REF] Cope | Regret and convergence bounds for immediate-reward reinforcement learning with continuous action spaces[END_REF][START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF] to the more recent approaches of [AOS07, [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF][START_REF] Bubeck | X -armed bandits[END_REF]. A special case of interest, which forms a bridge between the case of a finite number of arms and the continuum-armed setting, is the problem of bandit linear optimization, see [START_REF] Dani | Stochastic linear optimization under bandit feedback[END_REF] and the references therein.

Not the right perspective! We call an environment f the mapping that associates with each arm x ∈ X the expectation f (x) of its associated probability distribution. The theoretical guarantees given in the literature mentioned above are of the form: given some tuning parameters, the strategy is competitive, and sometimes even minimax optimal, with respect to a large class of environments that unfortunately depends on these parameters. But of course, this is not the right perspective: it is the strategy that should adapt to the environment, not the other way round! More precisely, these parameters describe the smoothness of the environments f in the class at hand in terms of a global regularity and/or local regularities around the global maxima of f . The issues raised by some of the works mentioned above can be roughly described as follows:

-The class of environments for the CAB1 algorithm of [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF] is formed by environments that are (α, L, δ)-uniformly locally Lipschitz and the strategy CAB1 needs to know α to get the optimal dependency in the number T of arms pulled; -For the Zooming algorithm of [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], it is formed by environments that are 1-Lipschitz with respect to a fixed and known metric L; -The HOO algorithm of [START_REF] Bubeck | X -armed bandits[END_REF] basically needs to know the pseudo-metric ℓ with respect to which f is weakly Lipschitz continuous, with Lipschitz constant equal to 1; -Other examples include the UCB-air algorithm (which relies on a smoothness parameter β, see [START_REF] Wang | Algorithms for infinitely manyarmed bandits[END_REF]), the OLOP algorithm (smoothness parameter γ, see [START_REF] Bubeck | Open-loop optimistic planning[END_REF]), the LSE algorithm (smoothness parameter C L , see [START_REF] Yu | Unimodal bandits[END_REF]), the algorithm presented in [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] and so on.

Adaptation to the unknown smoothness is needed. In a nutshell, adaptive methods are required. By adaptive methods, we mean-as is done in the statistical literature-agnostic methods, i.e., with minimal prior knowledge about f , that nonetheless obtain almost the same performance against a given environment f as if its smoothness were known beforehand. More precisely, given a fixed (possibly vector-valued) parameter L lying in a set L and a class of allowed environments F L , where L ∈ L, existing works present algorithms that are such that their worst-case regret bound over T time steps against environments in F L , sup

f ∈FL R T (f ) ϕ(T, L) ,
is small and even minimax optimal, i.e., such that it has the optimal dependencies on T and L. However, to do so, the knowledge of L is required. In this work, we are given a much larger class of environments F = ∪ L∈L F L , and our goal is an algorithm that adapts in finite time to every instance f of F , in the sense that for all T and f ∈ F , the regret R T (f ) is at most of the order of min ϕ(T, L), where the minimum is over the parameters L such that f ∈ F L .

Since we are interested in worst-case bounds, we will have to consider distribution-free bounds (i.e., bounds that only depend on a given class F L ); of course, the orders of magnitude of the latter, even when they are minimax optimal, are often far away -as far as the dependencies in T are concerned-with respect to distribution-dependent bounds (i.e., bounds that may depend on a specific instance f ∈ F L ).

Links with optimization algorithms. Our problem shares some common points with the maximization of a deterministic function f (but note that in our case, we only get to see noisy observations of the values of f ). When the Lipschitz constant L of f is known, an approximate maximizer can be found with well-known Lipschitz optimization algorithms (e.g., Shubert's algorithm). The case of unknown L has been studied in [START_REF] Jones | Lipschitzian optimization without the Lipschitz constant[END_REF][START_REF] Horn | Optimal algorithms for global optimization in case of unknown Lipschitz constant[END_REF]. The DIRECT algorithm of [START_REF] Jones | Lipschitzian optimization without the Lipschitz constant[END_REF] carries out Lipschitz optimization by using the smallest Lipschitz constant that is consistent with the observed data; although it works well in practice, only asymptotic convergence can be guaranteed. The algorithm of [START_REF] Horn | Optimal algorithms for global optimization in case of unknown Lipschitz constant[END_REF] iterates over an increasing sequence of possible values of L; under an additional assumption on the minimum increase in the neighborhood of the maximizers, it guarantees a worst-case error of the order of L 2 T -2/d after taking T samples of the deterministic function f . Adaptation to a global Lipschitz smoothness in bandit problems. We provide in this paper a first step toward a general theory of adaptation. To do so, we focus on the special case of classes F L formed by all environments f that are L-Lipschitz with respect to the supremum norm over a subset of R d : the hypercube [0, 1] d for simplicity. This case covers partially the settings of [START_REF] Bubeck | X -armed bandits[END_REF] and [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], in which the Lipschitz constant was equal to 1, a fact known by the algorithms. (Extensions to Hölderian-type assumptions as in [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF][START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] will be considered in future work.)

As it is known, getting the minimax-optimal dependency on T is easy, the difficult part is getting that on L without knowing the latter beforehand.

Our contributions. Our algorithm proceeds by discretization as in [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF]. To determine the correct discretization step, it first resorts to an uniform exploration yielding a rather crude estimate of the Lipschitz constant (that is however sufficient for our needs); in a second phase, it finds the optimal interval using a standard exploration-exploitation strategy. Our main assumptions are (essentially) that f and its derivative are Lipschitz continuous in the hypercube.

We feel that this two-step approach can potentially be employed in more general settings well beyond ours: with the notation above, the uniform-exploration phase performs a model-selection step and recommends a class F L , which is used in the second phase to run a continuum-armed bandit strategy tuned with the optimal parameters corresponding to L ∈ L. However, for the sake of simplicity, we study only a particular case of this general methodology.

Outline of the paper. In Section 2, we describe the setting and the classes of environments of interest, establish a minimax lower bound on the achievable performance (Section 2.1), and indicate how to achieve it when the global Lipschitz parameter L is known (Section 2.2). Our main contribution (Section 3) is then a method to achieve it when the Lipschitz constant is unknown for a slightly restricted class of Lipschitz functions.

Setting and notation

We consider a d-dimensional compact set of arms, say, for simplicity, X = [0, 1] d , where d 1. With each arm x ∈ [0, 1] d is associated a probability distribution ν x with known bounded support, say [0, 1]; this defines an environment. A key quantity of such an environment is given by the expectations f (x) of the distributions ν x . They define a mapping f : [0, 1] d → [0, 1], which we call the mean-payoff function.

At each round t 1, the player chooses an arm I t ∈ [0, 1] d and gets a reward Y t sampled independently from ν I t (conditionally on the choice of I t ). We call a strategy the (possibly randomized) rule that indicates at each round which arm to pull given the history of past rewards.

We write the elements x of [0, 1] d in columns; x T will thus denote a row vector with d elements.

Assumption 1 We assume that f is twice differentiable, with Hessians uniformly bounded by M in the following sense: for all x ∈ [0, 1] d and all y ∈ [0, 1] d ,

y T H f (x) y M y 2 ∞ .
The ℓ 1 -norm of the gradient ∇f 1 of f is thus continuous and it achieves its maximum on [0, 1] d , whose value is denoted by L. As a result, f is Lipschitz with respect to the ℓ ∞ -norm with constant L (and L is the smallest4 constant for which it is Lipschitz): for all x, y ∈

[0, 1] d , f (x) -f (y) L x -y ∞ .
In the sequel we denote by F L,M the set of environments whose mean-payoff functions satisfy the above assumption.

We also denote by F L the larger set of environments whose mean-payoff functions f is only constrained to be L-Lipschitz with respect to the ℓ ∞ -norm.

The minimax optimal orders of magnitude of the regret

When f is continuous, we denote by

f ⋆ = sup x∈[0,1] d f (x) = max x∈[0,1] d f (x)
the largest expected payoff in a single round. The expected regret R T at round T is then defined as

R T = E T f ⋆ - T t=1 Y t = E T f ⋆ - T t=1 f (I t )
where we used the tower rule and where the expectations are with respect to the random draws of the Y t according to the ν I t as well as to any auxiliary randomization the strategy uses.

In this article, we are interested in controlling the worst-case expected regret over all environments of F L . The following minimax lower bound follows from a straightforward adaptation of the proof of [BMSS11, Theorem 13], which is provided in Section A in appendix. (The adaptation is needed because the hypothesis on the packing number is not exactly satisfied in the form stated in [START_REF] Bubeck | X -armed bandits[END_REF].) Theorem 1. For all strategies of the player and for all

T max L d , 0.15 L 2/(d+2) max{d, 2} d ,
the worst-case regret over the set F L of all environments that are L-Lipschitz with respect to the ℓ ∞ -norm is larger than

sup FL R T 0.15 L d/(d+2) T (d+1)/(d+2) .
The multiplicative constants are not optimized in this bound (a more careful proof might lead to a larger constant in the lower bound).

How to achieve a minimax optimal regret when L is known

In view of the previous section, our aim is to design strategies with worst-case expected regret sup FL R T less than something of order L d/(d+2) T (d+1)/(d+2) when L is unknown. A simple way to do so when L is known was essentially proposed in the introduction of [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF] (in the case d = 1); it proceeds by discretizing the arm space. The argument is reproduced below and can be used even when L is unknown to recover the optimal dependency T (d+1)/(d+2) on T (but then, with a suboptimal dependency on L).

We consider the approximations f m of f with m d regular hypercube bins in the ℓ ∞ -norm, i.e., m bins are formed in each direction and combined to form the hypercubes. Each of these hypercube bins is indexed by an element k = (k 1 , . . . , k d ) ∈ {0, . . . , m -1} d . The average value of f over the bin indexed by k is denoted by

f m (k) = m d k/m+[0,1/m] d f (x) dx .
We then consider the following two-stage strategy, which is based on some strategy MAB for multi-armed bandits; MAB will refer to a generic strategy but we will instantiate below the obtained bound. Knowing L and assuming that T is fixed and known in advance, we may choose beforehand m = L 2/(d+2) T 1/(d+2) . The decomposition of [0, 1] d into m d bins thus obtained will play the role of the finitely many arms of the multi-armed bandit problem. At round t 1, whenever the MAB strategy prescribes to pull bin K t ∈ {0, . . . , m -1} d , then first, an arm I t is pulled at random in the hypercube K t /m + [0, 1/m] d ; and second, given I t , the reward Y t is drawn at random according to ν I t . Therefore, given K t , the reward Y t has an expected value of f m (K t ). Finally, the reward Y t is returned to the underlying MAB strategy.

Strategy MAB is designed to control the regret with respect to the best of the m d bins, which entails that

E T max k f m (k) - T t=1 Y t ψ T, m d ,
for some function ψ that depends on MAB. Now, whenever f is L-Lipschitz with respect to the ℓ ∞ -norm, we have that for all k ∈ {0, . . . , m -1} d and all

x ∈ k/m + [0, 1/m] d , the difference f (x) -f m (k) is less than L/m; so that 5 max x∈[0,1] d f (x) -max k f m (k) L m .
All in all, for this MAB-based strategy, the regret is bounded by the sum of the approximation term L/m and of the regret term for multi-armed bandits,

sup FL R T T L m + ψ(T, m d ) L d/(d+2) T (d+1)/(d+2) + ψ T, L 2/(d+2) T 1/(d+2) d . (1)
We now instantiate this bound.

The INF strategy of [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF] (see also [START_REF] Audibert | Minimax policies for combinatorial prediction games[END_REF]) achieves ψ(T, m ′ ) = 2 √ 2T m ′ and this entails a final O L d/(d+2) T (d+1)/(d+2) bound in (1). Note that for the EXP3 strategy of [START_REF] Auer | The non-stochastic multi-armed bandit problem[END_REF] or the UCB strategy of [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF], extra logarithmic terms of the order of ln T would appear in the bound.

3 Achieving a minimax optimal regret not knowing L In this section, our aim is to obtain a worst-case regret bound of the minimaxoptimal order of L d/(d+2) T (d+1)/(d+2) even when L is unknown. To do so, it will be useful to first estimate L; we will provide a (rather crude) estimate suited to our needs, as our goal is the minimization of the regret rather than the best possible estimation of L. Our method is based on the following approximation results.

For the estimation to be efficient, it will be convenient to restrict our attention to the subset F L,M of F L , i.e., we will consider the additional assumptions on the existence and boundedness of the Hessians asserted in Assumption 1. However, the obtained regret bound (Theorem 2) will suffer from some (light) dependency on M but will have the right orders of magnitude in T and L; the forecaster used to achieve it depends neither on L nor on M and is fully adaptive.

Some preliminary approximation results

We still consider the approximations f m of f over [0, 1] d with m d regular bins. We then introduce the following approximation of L:

L m = m max k∈{1,...,m-2} d max s∈{-1,1} d f m (k) -f m (k + s) .
This quantity provides a fairly good approximation of the Lipschitz constant, since m f m (k)f m (k + s) is an estimation of the (average) derivative of f in bin k and direction s.

The lemma below relates precisely L m to L: as m increases, L m converges to L.

Lemma 1. If f ∈ F L,M and m 3, then L - 7M m L m L .
Proof. We note that for all k ∈ {1, . . . , m -2} d and s ∈ {-1, 1} d , we have by definition

f m (k) -f m (k + s) = m d k/m+[0,1/m] d f (x) -f x + s/m dx m d k/m+[0,1/m] d f (x) -f x + s/m dx . Now, since f is L-Lipschitz in the ℓ ∞ -norm, it holds that f (x) -f x + s/m L s/m ∞ = L m ;
integrating this bound entails the stated upper bound L on L m .

For the lower bound, we first denote by x ⋆ ∈ [0, 1] d a point such that ∇f (x ⋆ ) 1 = L. (Such a point always exists, see Assumption 1.) This point belongs to some bin in {0, . . . , m-1} d ; however, the closest bin

k ⋆ m in {1, . . . , m-2} d is such that ∀x ∈ k ⋆ m /m + [0, 1/m] d , x -x ⋆ ∞ 2 m . (2)
Note that this bin k ⋆ m is such that all k ⋆ m + s belong to {0, . . . , m -1} d and hence legally index hypercube bins, when

s ∈ {-1, 1} d . Now, let s ⋆ m ∈ {-1, 1} d be such that ∇f (x ⋆ ) • s ⋆ m = ∇f (x ⋆ ) 1 = L , (3)
where • denotes the inner product in R d . By the definition of L m as some maximum,

L m m f m k ⋆ m -f m k ⋆ m + s ⋆ m = m × m d k ⋆ m /m+[0,1/m] d f (x) -f x + s ⋆ m /m dx . (4)
Now, Taylor's theorem (in the mean-value form for real-valued twice differentiable functions of possibly several variables) shows that for any x ∈ k ⋆ m /m + [0, 1/m] d , there exists two elements ξ and ζ, belonging respectively to the segments between x and x ⋆ , on the one hand, between x ⋆ and x + s ⋆ m /m on the other hand, such that

f (x) -f x + s ⋆ m /m = f (x) -f (x ⋆ ) + f (x ⋆ ) -f x + s ⋆ m /m = ∇f (x ⋆ ) • (x -x ⋆ ) + 1 2 (x -x ⋆ ) T H f (ξ) (x -x ⋆ ) -∇f (x ⋆ ) • x + s ⋆ m /m -x ⋆ - 1 2 x + s ⋆ m /m -x ⋆ T H f (ζ) x + s ⋆ m /m -x ⋆ = -∇f (x ⋆ ) • s ⋆ m m + 1 2 (x -x ⋆ ) T H f (ξ) (x -x ⋆ ) - 1 2 x + s ⋆ m /m -x ⋆ T H f (ζ) x + s ⋆ m /m -x ⋆ .
Using (3) and substituting the bound on the Hessians stated in Assumption 1, we get

f (x) -f x + s ⋆ m /m - L m + M 2 x -x ⋆ 2 ∞ + M 2 x + s ⋆ m /m -x ⋆ 2 ∞ ;
substituting (2), we get

f (x) -f x + s ⋆ m /m - L m + M 2m 2 2 2 + 3 2 - L m + 7M m 2 0 ,
where the last inequality holds with no loss of generality (if it does not, then the lower bound on L m in the statement of the lemma is trivial). Substituting and integrating this equality in (4) and using the triangle inequality, we get

L m L - 7M m .
This concludes the proof. ⊓ ⊔

A strategy in two phases

Our strategy is described in Figure 1; several notation that will be used in the statements and proofs of some results below are defined therein. Note that we proceed in two phases: a pure exploration phase, when we estimate L by some L m , and an exploration-exploitation phase, when we use a strategy designed for the case of finitely-armed bandits on a discretized version of the arm space.

(The discretization step depends on the estimate obtained in the pure exploration phase.) The first step in the analysis is to relate L m and L m to the quantity they are estimating, namely L m .

Lemma 2. With probability at least

1 -δ, L m -L m m 2 E ln 2m d δ .
Proof. We consider first a fixed k ∈ {0, . . . , m -1} d ; as already used in Section 2.2, the Z k,j are independent and identically distributed according to a distribution on [0, 1] with expectation f m (k), as j varies between 1 and E. Therefore, by Hoeffding's inequality, with probability at least 1

-δ/m d µ k -f m (k) 1 2E ln 2m d δ .
Performing a union bound and using the triangle inequality, we get that with probability at least 1δ,

∀k, k ′ ∈ {0, . . . , m -1}, µ k -µ k ′ -f m (k) -f m (k ′ ) 2 E ln 2m d δ .
This entails the claimed bound.

⊓ ⊔

By combining Lemmas 1 and 2, we get the following inequalities on L m , since the latter is obtained from L m by adding a deviation term.

Parameters:

-Number T of rounds; -Number m of bins (in each direction) considered in the pure exploration phase; -Number E of times each of them must be pulled; -A multi-armed bandit strategy MAB (taking as inputs a number m d of arms and possibly other parameters).

Pure exploration phase:

1. For each k ∈ {0, . . . , m -1} d pull E arms independently uniformly at random in k/m + [0, 1/m] d and get E associated rewards Z k,j , where j ∈ {1, . . . , E}; -compute the average reward for bin k, T 1/(d+2) .

µ k = 1 E E j=1 Z k,j ; 2. Set Lm = m max k∈{1,...,m-2} d max s∈{-1,1} d

Exploration-exploitation phase:

Run the strategy MAB with m d arms as follows; for all t = Em + 1, . . . , T , 1. If MAB prescribes to play arm K t ∈ 0, . . . , m -1 d , pull an arm I t at random in K t /m + [0, 1/m] d ; 2. Observe the associated payoff Yt, drawn independently according to νI t ; 3. Return Yt to the strategy MAB. Corollary 1. If f ∈ F L,M and m 3, then, with probability at least 1 -1/T ,

L - 7M m L m L + 2m 2 E ln 2m d T .
We state a last intermediate result; it relates the regret of the strategy of Figure 1 to the regret of the strategy MAB that it takes as a parameter.

Lemma 3. Let ψ(T ′ , m ′ ) be a distribution-free upper bound on the expected regret of the strategy MAB, when run for T ′ rounds on a multi-armed bandit problem with m ′ arms, to which payoff distributions over [0, 1] are associated. The expected regret of the strategy defined in Figure 1 is then bounded from above as

sup FL R T Em d + E LT m + ψ T -Em d , m d .
Proof. As all payoffs lie in [0, 1], the regret during the pure exploration phase is bounded by the total length Em d of this phase. Now, we bound the (conditionally) expected regret of the MAB strategy during the exploration-exploitation phase; the conditional expectation is with respect to the pure exploration phase and is used to fix the value of m. Using the same arguments as in Section 2.2, the regret during this phase, which lasts T -Em d rounds, is bounded against any environment in F L by

L T -Em d m + ψ T -Em d , m d .
The tower rule concludes the proof.

⊓ ⊔

We are now ready to state our main result. Note that it is somewhat unsatisfactory as the main regret bound (8) could only be obtained on the restricted class F L,M and depends (in a light manner, see comments below) on the parameter M , while having the optimal orders of magnitude in T and L. These drawbacks might be artifacts of the analysis and could be circumvented, perhaps in the light of the proof of the lower bound (Theorem 1), which exhibits the worst-case elements of F L (they seem to belong to some set F L,ML , where M L is a decreasing function of L).

Note howewer that the dependency on M in (8) is in the additive form. On the other hand, by adapting the argument of Section 2.2, one can prove distributionfree regret bounds on F L,M with an improved order of magnitude as far as T is concerned but at the cost of getting M as a multiplicative constant in the picture. While the corresponding bound might be better in some regimes, we consider here F L,M instead of F L essentially to remove pathological functions, and as such we want the weakest dependency on M . as soon as

m 8M L . (6)
In particular, for

0 < γ < d(d + 1) (3d + 2)(d + 2) and α = 1 d + 2 d + 1 d + 2 -γ 3d + 2 d > 0 , (7)
the choices of m = ⌊T α ⌋ and E = m 2 T 2γ(d+2)/d yield the bound

sup FL,M R T max 8M L + 1 1/α , L d/(d+2) T (d+1)/(d+2) 9 + ε(T, d) , (8)
where

ε(T, d) = 5T -γ ln(2T d ) d/(d+2) + T -γ + 2 √ 2d d T + 1 T -(d+1)/(d+2)
vanishes as T tends to infinity.

Note that the choices of E and m solely depend on T , which may however be unknown in advance; standard arguments, like the doubling trick, can be used to circumvent the issue, at a minor cost given by an additional constant multiplicative factor in the bound.

Remark 1. There is a trade-off between the value of the constant term in the maximum, (1+8M/L) 1/α , and the convergence rate of the vanishing term ε(T, d) toward 0, which is of order γ. For instance, in the case d = 1, the condition on γ is 0 < γ < 2/15; as an illustration, we get a constant term of a reasonable size, since 1/α 4.87, when the convergence rate is small, γ = 0.01; -a much larger constant, since 1/α = 60, when the convergence rate is faster, γ = 2/15 -0.01.

Proof. For the strategy INF, as recalled above, ψ(T ′ , m ′ ) = 2 √ 2T ′ m ′ . The bound of Lemma 3 can thus be instantiated as sup

FL,M R T Em d + E LT m + 2 √ 2T m d .
We now substitute the definition

m = L 2/(d+2) m T 1/(d+2) L 2/(d+2) m T 1/(d+2) 1 + 1 L 2/(d+2) m T 1/(d+2)
and separate the cases depending on whether L 2/(d+2) m

T 1/(d+2) is smaller or larger than d to handle the second term in the expectation. In the first case, we simply bound m by d and get a 2 √ 2T d d term. When the quantity of interest is larger than d, then we get the central term in the expectation below by using the fact that

(1 + 1/x) d (1 + 1/d) d e whenever x d. That is, sup FL,M R T is less than Em d + E T (d+1)/(d+2) L L 2/(d+2) m + 2 2T e T 1/(d+2) L 2/(d+2) m d + 2 √ 2T d d .
We will now use the lower and upper bounds on L m stated by Corollary 1. In the sequel we will make repeated use of the following inequality linking α-norms and 1-norms: for all integers p, all u 1 , . . . , u p > 0, and all α ∈ [0, 1],

u 1 + . . . + u p α u α 1 + . . . + u α p . (9)
By resorting to (9), we get that with probability at least 1 -1/T ,

2 2T e T 1/(d+2) L 2/(d+2) m d = 2 √ 2e T (d+1)/(d+2) L d/(d+2) m 2 √ 2e T (d+1)/(d+2) L + 2m 2 E ln 2m d T d/(d+2) 2 √ 2e T (d+1)/(d+2)   L d/(d+2) + 2m 2 E ln 2m d T d/(d+2)   .
On the other hand, with probability at least 1 -1/T ,

L m L - 7M m L 8 ,
where we assumed that m and E are chosen large enough for the lower bound of Corollary 1 to be larger than L/8. This is indeed the case as soon as

7M m 7L 8 , that is, m 8M L ,
which is exactly the condition (6). Putting all things together (and bounding m by T in the logarithm), with probability at least 1 -1/T , the regret is less than

Em d + T (d+1)/(d+2) L (L/8) 2/(d+2) + 2 √ 2T d d + 2 √ 2e T (d+1)/(d+2)   L d/(d+2) + 2m 2 E ln 2T d+1 d/(d+2)   ; (10)
on the event of probability smaller than δ = 1/T where the above bound does not necessarily hold, we upper bound the regret by T . Therefore, the expected regret is bounded by (10) plus 1. Bounding the constants as 8 2/(d+2) 8 2/3 = 4 and 2 √ 2e 5 concludes the proof of the first part of the theorem.

The second part follows by substituting the values of E and m in the expression above and by bounding the regret by T 0 for the time steps t T 0 for which the condition (6) is not satisfied.

More precisely, the regret bound obtained in the first part is of the desired order L d/(d+2) T (d+1)/(d+2) only if E ≫ m 2 and Em d ≪ T (d+1)/(d+2) . This is why we looked for suitable values of m and E in the following form: which yields the proposed expression (7). The fact that α needs to be positive entails the constraint on γ given in (7). When condition (6) is met, we substitute the values of m and E into (5) to obtain the bound (8); the only moment in this substitution when taking the upper or lower integer parts does not help is for the term Em d , for which we write (using that T 1)

Em d = m d+2 T 2γ(d+2)/d
T α(d+2) 1 + T 2γ(d+2)/d 2 T α(d+2) T 2γ(d+2)/d = 2 T (d+1)/(d+2)-γ .

When condition (6) is not met, which can only be the case when T is such that T α < 1 + 8M/L, that is, T < T 0 = (1 + 8M/L) 1/α , we upper bound the regret by T 0 .

⊓ ⊔

A Proof of Theorem 1 (Omitted from the Proceedings of ALT'11)

Proof. We slightly adapt the (end of the) proof of [BMSS11, Theorem 13]; we take the metric ℓ(x, y) = L xy ∞ . For ε ∈ (0, 1/2), the ε-packing number of We take ε of the form ε = γ L d/(d+2) T -1/(d+2)

for some constant γ < 1 to be defined later on. The lower bound then equals γ L d/(d+2) T (d+1)/(d+2) 0.5-4.4 γ 1+d/2 γ L d/(d+2) T (d+1)/(d+2) 0.5-4.4 γ 3/2

where we used the fact that γ < 1 and d 1 for the last inequality. Taking γ such that 0.5 -4.4 γ 3/2 = 1/4, that is, γ = 1/(4 × 4.4) 2/3 0.14, we get the stated bound.

It only remains to see that the indicated condition on T proceeds from the value of ε provided above, the constraint ε < min 1/2, L/d, L/2 , and the upper bound γ 0.15.

⊓ ⊔

µ

  k -µ k+s and define Lm = Lm + m 2 E ln(2m d T ) as well as m = L 2/(d+2) m

Fig. 1 .

 1 Fig. 1. The considered strategy.

Theorem 2 .+

 2 When used with the multi-armed strategy INF, the strategy of Figure 1 ensures that sup FL,M R T T (d+1)/(d+2)   9 L d/(d+2) Em d + 2 √ 2T d d + 1 (5)

m

  = ⌊T α ⌋ and E = m 2 T 2γ(d+2)/d ,where α and γ are positive. We choose α as a function of γ so that the termsEm d = ⌊T α ⌋ d+2 T 2γ(d+2)/d and T (d+1)/(d+2) m √ E d/(d+2) = T (d+1)/(d+2) T 2γ(d+2)/d -d/(2(d+2))are approximatively balanced; for instance, such that α(d + 2) + 2γ(d + 2)/d = (d + 1)/(d + 2)γ ,

  [0, 1] d with respect to ℓ equalsN [0, 1] d , ℓ, ε = ⌊L/ε⌋ d 2 provided that L/ε 2, that is, ε L/2. Therefore, Step 5 of the mentioned proof shows that sup FL R T T ε 0.5 -2.2 ε T ⌊L/ε⌋d for all 0 < ε < min{1, L} 2. We now optimize this bound. Whenever L/ε max{d, 2}, we have⌊L/ε⌋ L/ε -1 1 2 L/εin the case where d = 1, while for d 2, the fact that (1-1/x) d (1 -1/d) d (1 -1/2) 2 =1/4 for all x d and d 2. Therefore, whenever 0 < ε < min 1/2, L/d, L/2 , sup FL R T T ε 0.5 -4.4 ε 1+d/2 T L d .

The proof of the approximation lemma will show why this is the case.

Here, one could object that we only use the local Lipschitzness of f around the point where it achieves its maximum; however, we need f to be L-Lipschitz in an 1/m-neighborhood of this maximum, but the optimal value of m depends on L. To solve the chicken-egg problem, we restricted our attention to globally L-Lipschitz functions, which, anyway, in view of Theorem 1, comes at no cost as far as minimaxoptimal orders of magnitude of the regret bounds in L and T are considered.

Acknowledgements

This work was supported in part by French National Research Agency (ANR, project EXPLO-RA, ANR-08-COSI-004) and the PASCAL2 Network of Excellence under EC grant no. 216886.