Bornes de risque pour les forêts purement uniformément aléatoires.

Résumé : Introduites par Leo Breiman en 2001, les forêts aléatoires sont une méthode statistique très performante. D'un point de vue théorique, leur analyse est difficile, du fait de la complexité de l'algorithme. Pour expliquer ces performances, des versions de forêts aléatoires simplifiées, et donc plus faciles à analyser, ont été introduites. Ces versions ont été appelées forêts purement aléatoires. Dans cet article, nous introduisons une autre version simplifiée, que nous appelons forêts purement uniformément aléatoires. Dans un contexte de régression, avec une seule variable explicative, nous montrons que les arbres aléatoires ainsi que les forêts aléatoires atteignent la vitesse de convergence minimax. De plus, nous prouvons que les forêts aléatoires améliorent les performances des arbres aléatoires, en réduisant la variance des estimateurs associés d'un facteur de trois quarts.

Mots-clés : Forêts aléatoires, Régression non-paramétrique, Vitesse de convergence, Randomisation.

Introduction

Random forests (RF), introduced by Leo Breiman in 2001 [START_REF] Breiman | Random Forests[END_REF], are a very effective statistical method. They give outstanding performances in a lot of situations for both regression and classification problems. Mathematical understanding of these good performances remains quite unknown. As defined by Leo Breiman, a random forest is a collection of tree-predictors {h(x, Θ l ), 1 l q}, where (Θ l ) 1 l q are i.i.d. random vectors, and a random forest predictor is obtained by aggregating this collection of trees. In addition to consistency results, one of the main theoretical challenges is to explain why a random forest improves so much the performance of a single tree.

In [START_REF] Breiman | Random Forests[END_REF], Leo Breiman introduced a specific instance of random forest, called random forests-RI, which has been adopted in many fields as a reference method. Indeed, random forests-RI are simple to use, and are efficiently coded in the popular R-package randomForest [START_REF] Liaw | Classification and Regression by randomForest[END_REF]. They are effective for a predictive goal and they can also be used for variable selection (see e.g. [START_REF] Díaz-Uriarte | Gene Selection and classification of microarray data using random forest[END_REF], [START_REF] Genuer | Variable selection using random forests[END_REF]).

However, forests-RI are very difficult to handle theoretically. This is why people are interested in simplified versions, called purely random forests (PRF). The main difference is that in PRF, the splits of tree nodes are randomly drawn independently of the learning sample; while in random forests-RI, the splits are optimized using the learning sample. This independence between splits and learning sample makes mathematical analysis easier. In [START_REF] Cutler | Pert -Perfect random tree ensembles[END_REF], Cutler and Zhao introduced PERT (Perfect Random Tree Ensemble), an algorithm which builds some purely random forests, and illustrated its good performance on benchmark datasets. More recently Biau et al. [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF] showed that both purely random trees and purely random forests are universally consistent.

Our paper offers to examine another simple variant of random forests, which can be put in the so-called purely random forests family. We call it purely uniformly random forests and we analyze its risk, only in a regression framework with a one-dimensional predictor space. The main goal is to emphasize the gain of using a forest instead of a tree. The results of this paper are twofold: first we show that both purely uniformly random trees and forests risks reach minimax rate of convergence on the Lipschitz functions class; second we show that forests improve the variance term by a factor of three fourths while not increasing the bias.

The paper is organized as follows. Section 2 presents the model. Section 3 and Section 4 give some risk bounds for purely uniformly random trees and purely uniformly random forests respectively. Section 5 concludes the paper, while proofs are collected in Section 6.

Framework

The framework we consider all along the paper is the classical random design regression framework.

More precisely, consider a learning set L n = {(X 1 , Y 1 ), . . . , (X n , Y n )} made of n i.i.d. observations of a vector (X, Y ) from an unknown distribution. Y is real-valued since we are in a regression framework. We consider the following statistical model:

Y i = s(X i ) + ε i for i = 1, . . . , n . (1)
s is the unknown regression function and the goal is to estimate s. We make the following assumptions on model (1):

• X ∈ [0, 1] with continuous density function µ;

• (ε 1 , . . . , ε n ) are i.i.d. observations of ε, independent of L n , with E[ε] = 0
and where Var(ε) = σ 2 is assumed to be known.

Note that we deal only with a one-dimensional predictor space. This paper aims at comparing performances in estimating s using a single random tree and a random forest of a special kind, described in the next section.

3 Risk bounds for Purely Uniformly Random Trees

Tree definition

The principle of Purely Uniformly Random Trees (PURT) is that we draw k uniform random variables, which form the partition of the input space [0, 1].

Then we build a regressogram on this partition, that we call a tree. Note that, unlike purely random forests or random forests-RI, the tree structure of individual predictors is not obvious. This comes from the fact that in PURT the partition is not obtained in a recursive manner. Nevertheless we keep the vocabulary of trees and forests to distinguish individual predictors from aggregated ones.

Let us mention that, all along the paper, we make a slight language abuse. Indeed, we refer to random tree, the tree himself (as a graph), the corresponding partition of [0, 1], as well as the corresponding estimator.

More precisely, let U = (U 1 , . . . , U k ) be k i.i.d. random variables of uniform distribution on [0, 1], where k is a natural integer which will depend on the number of observations n.

A Purely Uniformly Random Tree (PURT), associated with U, is defined for x ∈ [0, 1] as:

ŝU (x) = k j=0 βj 1 U (j) <x U (j+1) where βj = 1 ♯{i : U (j) < X i U (j+1) } i: U (j) <Xi U (j+1) Y i
and (U (1) , . . . , U (k) ) is the ordered statistics of (U 1 , . . . , U k ) and U (0) = 0, U (k+1) = 1. ♯ E denotes the cardinality of the set E.

Remark 1 Let us mention that if ♯{i : U (j) < X i U (j+1) } = 0, we set βj = 0. However as we will see in Section 3.2, our assumptions on k and n will make the probability of observing such an event tend to 0.

INRIA

In addition, let us define, for x ∈ [0, 1]:

sU (x) = k j=0 β j 1 U (j) <x U (j+1)
where

β j = E[Y | U (j) < X U (j+1) ] .
Conditionally on U, sU is the best approximation of s among all the regressograms based on U, but of course it depends on the unknown distribution of (X, Y ).

With these notations, we can write a bias-variance decomposition of the quadratic risk of ŝU as follows:

E[(ŝ U (X) -s(X)) 2 ] = E[(ŝ U (X) -sU (X)) 2 ] + E[(s U (X) -s(X)) 2 ]
(2)

= variance term + bias term

To clarify these variance and bias terms, we emphasize that for a given partition u and a given x, we have

E[ŝ u (x)] = su (x) so E[(ŝ u (x) -su (x)) 2 ]
is the variance of the estimator ŝu (x) and E[(s u (x)s(x)) 2 ] is its bias. We then integrate with respect to (w.r.t) X and U to get decomposition (2).

Variance of a tree

We start to deal with the variance term of decomposition [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF]. First, we work conditionally on U, then the problem reduces to the case of a regressogram on a deterministic partition, and we can apply the following proposition which comes from Arlot [START_REF] Arlot | V-fold cross-validation improved: V-fold penalization[END_REF].

Proposition 1 Conditionally on U, the variance term of decomposition [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF] satisfies:

E[(ŝ U (X) -sU (X)) 2 | U] = 1 n k j=0 (1 + δ n,pj )(σ 2 + (σ d j ) 2 ) ( 3
)
where

• p j = P(U (j) < X U (j+1) ), • (σ d j ) 2 = E[(s(X) -sU (X)) 2 | U (j) < X U (j+1) ],
• δ n,p -----→ np→+∞ 0.

RR n°7318

We now integrate equation (3) w.r.t. U, and we get the following equality:

E[(ŝ U (X) -sU (X)) 2 ] = 1 n k j=0 σ 2 + σ 2 E[δ n,pj ] + E[(σ d j ) 2 ] + E[(σ d j ) 2 δ n,pj ] (4)
Let us stress that equation ( 4) is general, since it does not depend on the distribution of U. Hence, it can be used for any random partition distributions. Finally, using the fact that, in our case, U is made of k i.i.d. random variables of uniform distribution on [0, 1], we deduce from equation ( 4) the following proposition:

Proposition 2 If k -----→ n→+∞ +∞, k n -----→ n→+∞ 0, µ > 0 and s is C-Lipschitz, the
variance of a PUR Tree satisfies:

E[(ŝ U (X) -sU (X)) 2 ] = σ 2 (k + 1) n + o n→+∞ k n ( 5
)
where the notation

o n→+∞ k n denotes a function f (n) such as f (n) k/n -----→ n→+∞ 0.
Details of the proof of Proposition 2 can be found in Section 6.1.

The first two hypotheses of Proposition 2 (k

-----→ n→+∞ +∞, k n -----→ n→+∞ 0) are
the same natural conditions found by Biau et al. [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF] for consistency of PRF. They guarantee that the number of splits of the tree must grow to infinity but slower than the number of samples.

Bias of a tree

We now turn to the bias term of decomposition [START_REF] Biau | Consistency of random forests and other averaging classifiers[END_REF]. Direct calculations (see Section 6.2 for details) lead to the following upper bound for the bias term of a PURT:

Proposition 3 If µ is bounded by M > 0 and s is C-Lipschitz, the bias of a PURT is upper bounded by:

E[(s U (X) -s(X)) 2 ] 6M C 2 (k + 1) 2 (6)

Risk bounds for a tree

Putting together ( 5) and ( 6) leads to the following risk bound for a PURT.

Theorem 1 If k -----→ n→+∞ +∞, k n -----→ n→+∞ 0, 0 < µ M and s is C-Lipschitz,
the risk of a PURT satisfies:

E[(ŝ U (X) -s(X)) 2 ] σ 2 (k + 1) n + 6M C 2 (k + 1) 2 + o n→+∞ k n (7)

INRIA

The balance between the two first terms of the right hand side (r.h.s.) of ( 7) leads to take (k + 1) = n 1/3 , and gives the following upper bound for the risk of a PURT.

Corollary 1 Under the assumptions of Theorem 1,

E[(ŝ U (X) -s(X)) 2 ] Kn -2/3 + o n→+∞ (n -2/3 )
where K is a positive constant.

Therefore, a PURT reaches the minimax rate of convergence associated with the class of Lipschitz functions (see e.g. Ibragimov and Khasminskii [START_REF] Ibragimov | Statistical Estimation: Asymptotic Theory[END_REF]).

Let us now analyze purely uniformly random forests. As a result, we emphasize an improvement given by a forest compared to a single tree.

Risk bounds for Purely Uniformly Random Forests 4.1 Forest definition

A random forest is the aggregation of a collection of random trees. So, in the context of Purely Uniformly Random Forests (PURF), the principle is to generate several PUR Trees by drawing several random partitions given by uniform random variables, and to aggregate them.

Let V = (U 1 , . . . , U q ) be q i.i.d. random vectors of the same distribution as U (defined in Section 3.1). That is for l = 1, . . . , q, U l = (U l 1 , . . . , U l k ) where the (U l j ) 1 j k are i.i.d. random variables of uniform distribution on [0, 1]. A PURF, associated with V, is defined for x ∈ [0, 1] as follows:

ŝ(x) = 1 q q l=1 ŝU l (x) .
Let us define, for x ∈ [0, 1]:

s(x) = 1 q q l=1 sU l (x) .
Again, we have a bias-variance decomposition of the quadratic risk of ŝ, given by:

E[(ŝ(X) -s(X)) 2 ] = E[(ŝ(X) -s(X)) 2 ] + E[(s(X) -s(X)) 2 ] (8)
= variance term + bias term RR n°7318

Variance of a forest

We first deal with the variance term of decomposition [START_REF] Graham | Concrete mathematics[END_REF]. We begin to show that when letting the number of trees q grow to infinity, the variance of a PURF is close to the covariance between two PURT.

Indeed, since ŝ(x) = 1 q q l=1 ŝU l (x), the variance term satisfies:

E[(ŝ(X) -s(X)) 2 ] = 1 q 2 q l=1 E[(ŝ U l (X) -sU l (X)) 2 ] + 1 q 2 l =q E[(ŝ U l (X) -sU l (X))(ŝ U m (X) -sU m (X))] = 1 q E[(ŝ U 1 (X) -sU 1 (X)) 2 ] + q(q -1) q 2 E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))]
where the last equality comes from the fact that the ((ŝ U l (X) -sU l (X)) 1 l q are of the same distribution. Now, if we let q grow to infinity, we get:

E[(ŝ(X) -s(X)) 2 ] = E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))] + o q→+∞ (1)
The next step is to upper bound the covariance between two PURT

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))]
(it is detailed in Section 6.3) and it leads to the following theorem, which gives the behavior of the variance of a PURF:

Theorem 2 If k -----→ n→+∞ +∞, k n -----→ n→+∞ 0, µ > 0, s is C-Lipschitz and q -----→ n→+∞
+∞, the variance of a PURF satisfies the following upper bound:

E[(ŝ(X) -s(X)) 2 ] 3 4
σ 2 (k + 1) n + o n→+∞ k n ( 9
)
Theorem 2 is to be compared with Proposition 2 and tells us that the variance of a PUR Forest is upper bounded by three fourths times the variance of a PUR Tree. So, the rate of decay (in terms of power of n) of the PUR Forest variance is the same as the PUR Tree variance, and the actual gain appears in the multiplicative constant. We mention that, as in the analysis of the variance of a tree (see equation ( 4)), we derive, in the proof of Theorem 2, a general statement (see equation (13) in Section 6.3), which does not depend on the distribution of the partition defining the random trees.

INRIA

Let us, finally, comment the hypotheses of Theorem 2. First, note that the hypotheses on k and n are the same as in Proposition 2, which allows a fair comparison between the two results. Second, the hypothesis on q allows to ensure that the upper bound on the covariance (given by Corollary 3 in Section 6.3) leads to the same upper bound for the variance of the forest. Finally, the other hypotheses (µ > 0, s is C-Lipschitz) are the same as in Proposition 2 and help to control negligible terms.

Bias of a forest

We now deal with the bias term of decomposition [START_REF] Graham | Concrete mathematics[END_REF]. A convex inequality gives that the bias of a forest is not larger than the bias of a single tree:

E[(s(X) -s(X)) 2 ] 1 q q l=1 E[(s U l (X) -s(X)) 2 ] = E[(s U 1 (X) -s(X)) 2 ] .
So from Proposition 3, we deduce that:

Proposition 4 If µ is bounded by M > 0 and s is C-Lipschitz, the bias of a PURF satisfies the same inequality as [START_REF] Díaz-Uriarte | Gene Selection and classification of microarray data using random forest[END_REF], that is:

E[(s(X) -s(X)) 2 ] 6M C 2 (k + 1) 2 (10)

Risk bounds for a forest

Putting together ( 9) and (10) leads to the following risk bound for a PURF.

Theorem 3 If k -----→ n→+∞ +∞, k n -----→ n→+∞ 0, 0 < µ M , s is C-Lipschitz and q -----→ n→+∞ +∞, the risk of a PURF satisfies: E[(ŝ(X) -s(X)) 2 ] 3 4
σ 2 (k + 1) n + 6M C 2 (k + 1) 2 + o n→+∞ k n
Again, taking (k + 1) = n 1/3 gives the upper bound for the risk:

Corollary 2 Under the assumptions of Theorem 3,

E[(ŝ(X) -s(X)) 2 ] Kn -2/3 + o n→+∞ (n -2/3 )
where K is a positive constant.

So, a PURF reaches the minimax rate of convergence for C-Lipschitz functions.

Secondly, as the variance of a PUR Forest is systematically reduced compared to a PUR Tree and the bias of a PUR Forest is not larger than the one of a PUR Tree, the risk of a PUR Forest is actually lower.

Conclusion

We emphasize, for a very simple version of random forests, the actual gain of using a random forest instead of using a single random tree. First, we showed that both trees and forests reach the minimax rate of convergence. Then, we manage to highlight a reduction of the variance of a forest, compared to the variance of a tree. This is, in this specific context, a proof of the well-known conjecture for random forests: "a random forest, by aggregating several random trees, reduces variance and leaves the bias unchanged" which can be found for example in Hastie et al. [START_REF] Hastie | The Elements of Statistical Learning[END_REF].

An interesting open problem would be to generalize this result, which could handle more complex versions of random forests and relax the hypotheses we made here. Obviously, a more ambitious goal would be to give some precise insights explaining the outstanding performances of random forests-RI.

Proofs

Proof of Proposition 2

We must show that the three last terms in the sum of equation ( 4) are negligible compared to the constant term σ 2 . Let us fix 0 j k. As it can be found e.g. in Chapter 6 of [START_REF] David | Order Statistics[END_REF], the probability density function of

U (j+1) -U (j) is the function t ∈ [0, 1] -→ k(1 -t) k-1 .
• For the second term E[δ n,pj ]: from [START_REF] Arlot | V-fold cross-validation improved: V-fold penalization[END_REF] we have δ n,pj κ 3 (np j ) -1/4 , where κ 3 is a positive constant. So,

E[δ n,pj ] κ 3 E[(np j ) -1/4 ] = κ 3 n -1/4 E[p -1/4 j ] κ 3 (mn) -1/4 E[(U (j+1) -U (j) ) -1/4 ] κ 4 m -1/4 k n 1/4
where m = min • For the third term

E[(σ d j ) 2 ]: (σ d j ) 2 = E[(s(X) -sU (X)) 2 | U (j) < X U (j+1) ] C 2 (U (j+1) -U (j) ) 2 because s is C -Lipschitz . So, E[σ d j ) 2 ] C 2 E[(U (j+1) -U (j) ) 2 ] = C 2 2 (k + 1)(k + 2)
which tends to 0 as k tends to infinity.

• For the last term, the following inequality is sufficient to conclude:

E[(σ d j ) 2 δ n,pj ] C 2 E[δ n,pj ], because U (j+1) -U (j) 1. INRIA 6.

Proof of Proposition 3

Function s is supposed to be C-Lipschitz, so

E[(s U (X) -s(X)) 2 ] = E[( k j=0 (s(X) -β j )1 U (j) <X U (j+1) ) 2 ] = E[ k j=0 (s(X) -β j ) 2 1 U (j) <X U (j+1) ] E[ k j=0 C 2 (U (j+1) -U (j) ) 2 1 U (j) <X U (j+1) ] = C 2 E[ k j=0 (U (j+1) -U (j) ) 2 P(U (j) < X U (j+1) )] C 2 E[ k j=0 M (U (j+1) -U (j) ) 3 ] because µ is bounded by M = M C 2 k j=0 E[(U (j+1) -U (j) ) 3 ] = M C 2 6 (k + 2)(k + 3) 6M C 2 (k + 1) 2 .

Proof of Theorem 2

Before entering into details of the proof of Theorem 2, we recall that in the proof of Proposition 1 (which can be found in [START_REF] Arlot | V-fold cross-validation improved: V-fold penalization[END_REF]), calculations lead to the following equality:

E[(ŝ U (X) -sU (X)) 2 | U] = k j=0 p j E 1 np j (σ 2 + (σ d j ) 2 ) ( 11
)
where pj = ♯{i : U

(j) < X i U (j+1) } n .
Then, an estimation of p j E 1 np j gives the expression

1 n (1 + δ n,pj ) in Proposi- tion 1. We note V ar j = p j E 1 np j (σ 2 + (σ d j ) 2 ) (12)
a generic term of the sum in the r.h.s. of [START_REF] Liaw | Classification and Regression by randomForest[END_REF].

We now address the proof of Theorem 2. We begin by introducing some notations and establish an intermediate result. The following proposition is not only useful to prove Theorem 2, but has its own interest. Indeed, it gives a general upper bound (to be compared to equation ( 3)) which does not depend on the distribution of random partitions defining the trees.

In the sequel we denote the covariance between two PURT by: ). Then we denote by (V (1) , . . . , V (2k) ) the ordered statistics of the complete vector

C(ŝ U 1 , ŝU 2 ) = E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))] Let us consider U 1 = (U 1 1 , . . . , U 1 k ) and U 2 = (U 2 1 , . . . , U 2
(U 1 1 , . . . , U 1 k , U 2 1 , . . . , U 2 k ), V (0) = 0 and V (2k+1) = 1. (Σ d,1,2 t ) 2 denotes a sum of terms E[(s U 1 (X) -s(X))(s U 2 (X) -s(X)) | V (t ′ ) < X V (t ′ +1) ] for several consecutive values of t ′ .
Finally pt denotes for some j ∈ {0, . . . , k} either p 1 j or p 2 j depending on the relative positions between the (U 1 1 , . . . , U 1 k ) and the (U 2 1 , . . . , U 2 k ) in (V (1) , . . . , V (2k) ) (see details below).

Proposition 5 The covariance between two PURT satisfies the following upper bound:

C(ŝ U 1 , ŝU 2 ) 1 n E   N1,2 t=0 (1 + δ n, pt )(σ 2 + (Σ d,1,2 t ) 2 )   ( 13
)
where

N 1,2 = k + 1 - k-2 r=1 k-1 s=1 1 U 2 (s) <U 1 (r) <U 1 (r+1) <U 1 (r+2) <U 2 (s+1) .
Remark 2 The gain in variance for a PURF comes from the fact that the number of terms in the sum of equation ( 13) is smaller than k + 1. Indeed, it is k + 1 -M 1,2 where M 1,2 is the number of times that 3 consecutive ordered statistics of U 1 are included in 2 consecutive ordered statistics of U 2 .

We now prove inequality (13) of Proposition 5. The term (ŝ

U 1 (X)-s U 1 (X))(ŝ U 2 (X)- sU 2 (X)) equals, by definition, to: k r=0 ( β1 r -β 1 r )1 U 1 (r) <X U 1 (r+1) k s=0 ( β2 s -β 2 s )1 U 2 (s) <x U 2 (s+1) = 2k t=0 ( β1 t,r -β 1 t,r )( β2 t,s -β 2 t,s )1 V (t) <X V (t+1) (14)
where (V (1) , . . . , V (2k) ) is the ordered statistics of the vector

(U 1 1 , . . . , U 1 k , U 2 1 , . . . , U 2 k ), V (0) = 0, V (2k+1) = 1,

and β1

t,r = β1 r and

β 1 t,r = β 1 r , if ]V (t) , V (t+1) ] ⊂]U 1 (r) , U 1 (r+1) ] β2 t,s = β2 s and β 2 t,s = β 2 s , if ]V (t) , V (t+1) ] ⊂]U 2 (s) , U 2 (s+1) ]
For l = 1, 2 and j = 0, . . . , k, we define pl

j = ♯{i : U l (j) < X i U l (j+1) } n .

INRIA

Now, let us give some details for the first term of ( 14), denoted by S 1 (X). Without loss of generality, we suppose that

V (1) = U 1 (1) (i.e. U 1 (1) < U 2 (1) ). So, S 1 (X) = (ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))1 0<X U 1 (1)
= ( β1

1 -β 1 1 )( β2 1 -β 2 1 )1 0<X U 1 (1) = 1 np 1 1 i: 0<Xi U 1 (1)
(Y i -β 1 1 ) 1 np 2 1 i: 0<Xi U 2 (1)
(Y i -β 2 1 ) 1 0<X U 1 (1) = 1 np 1 1 np 2 1 i 1 : 0<X i 1 U 1 (1) i 2 : 0<X i 2 U 2 (1)
(Y i 1 -β 1 1 )(Y i 2 -β 2 1 )1 0<X U 1 (1)
If we denote by E Λ1,2 [.] the conditional expectation

E[. | (1 0<X i 1 U 1 (1) ) 1 i 1 n , (1 0<X i 2 U 2 (1) ) 1 i 2 n ], we have: E[S 1 (X) | U 1 , U 2 ] = E p 1 1 E 1 np 1 1 np 2 1 i 1 : 0<X i 1 U 1 (1) i 2 : 0<X i 2 U 2 (1)
E Λ1,2 [(Y i 1 -β 1 1 )(Y i 2 -β 2 1 )] U 1 , U 2 but i 1 = i 2 =⇒ E Λ1,2 [(Y i 1 -β 1 1 )(Y i 2 -β 2 1 )] = 0 because Y i 1 and Y i 2 are independent. Hence: E[S 1 (X) | U 1 , U 2 ] = E p 1 1 E 1 np 1 1 np 2 1 i: 0<Xi U 1 (1) E Λ1 [(Y i -β 1 1 )(Y i -β 2 1 )] U 1 , U 2 = E p 1 1 E 1 np 1 1 np 2 1 i: 0<Xi U 1 (1) E[(Y i -β 1 1 )(Y i -β 2 1 ) | 0 < X i U 1 (1) ] U 1 , U 2 where E Λ1 [.] denotes the conditional expectation E[. | (1 0<Xi U 1 (1) ) 1 i n ]. Now, as E[(Y i -β 1 1 )(Y i -β 2 1 ) | 0 < X i U 1 (1) ] = E[(Y -β 1 1 )(Y -β 2 1 ) | 0 < X U 1 (1) ]
for all i, and

E[(Y -β 1 1 )(Y -β 2 1 ) | 0 < X U 1 (1) ] = σ 2 + (σ d,1,2 0 ) 2 where (σ d,1,2 0 ) 2 = E[(s(X) -sU 1 (X))(s(X) -sU 2 (X)) | 0 < X V (1) ]
we get

E[S 1 (X) | U 1 , U 2 ] = p 1 1 E 1 np 2 1 (σ 2 + (σ d,1,2 0 ) 2 ) .

RR n°7318

If we suppose in addition that V (2) = U 2 (1) , we similarly get for the second term of ( 14):

E[S 2 (X) | U 1 , U 2 ] = E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))1 U 1 (1) <X U 2 (1) | U 1 , U 2 ] = q 2 E nq 2 np 1 2 np 2 1 (σ 2 + (σ d,1, 2 1 ) 2 )
where

q 2 = P(V (1) < X V (2) ) = P(U 1 (1) < X U 2 (1) ) nq 2 = ♯{i : V (1) < X i V (2) } and (σ d,1,2 1 ) 2 = E[(s(X) -sU 1 (X))(s(X) -sU 2 (X)) | V (1) < X V (2) ] . Since ]V (1) , V (2) ] is included in ]U 1 (1) , U 1 (2) ],
we have q2 p1 2 , so:

E[S 2 (X) | U 1 , U 2 ] q 2 E 1 np 2 1 (σ 2 + (σ d,1, 2 1
) 2 ) .

Finally, by summing the two terms S 1 (X) and S 2 (X), we deduce that

E[S 1 (X) + S 2 (X) | U 1 , U 2 ] p 2 1 E 1 np 2 1 (σ 2 + (σ d,1,2 0 ) 2 + (σ d,1, 2 1 ) 2 )
In conclusion, we succeeded to bound the sum of the first two terms of ( 14) by an expression very close to V ar j (defined in (12)). The only difference comes from the fact that instead of (σ d j ) 2 we have (σ d,1,2 0

) 2 +(σ d,1, 2 1
) 2 . But as we saw in proof of Proposition 2, these terms are negligible, so

p 2 1 E 1 np 2 1 (σ 2 + (σ d,1,2 0 ) 2 + (σ d,1,2 1
) 2 ) is of the same order than V ar j . We can easily generalize this fact by proving the following lemma. We denote by S j (X) the j-th term of (14), i.e. S j (X) = (ŝ

U 1 (X)-s U 1 (X))(ŝ U 2 (X)- sU 2 (X))1 V (j) <X V (j+1) .
Lemma 1 Let r be in {0, . . . , k} and denote by t, t ′ the integers such that

U 1 (r) = V (t) < V (t ′ +1) = U 1 (r+1) (15) then E t ′ j=t S j (X) | U 1 , U 2 p 1 r E 1 np 1 r (σ 2 + (Σ d,1,2 r ) 2 )
where

(Σ d,1,2 r ) 2 = t ′ j=t (σ d,1,2 j ) 2 .
INRIA Indeed for all j ∈ {t, t + 1, . . . , t ′ },

E[S j (X) | U 1 , U 2 ] q j E 1 np 1 r (σ 2 + (σ d,1,2 j ) 2 )
where q j = P(V (j) < X V (j+1) )

and

(σ d,1,2 j ) 2 = E[(s(X) -sU 1 (X))(s(X) -sU 2 (X)) | V (j) < X V (j+1) ] .
Thus,

E t ′ j=t S j (X) | U 1 , U 2 P(V (t) < X V (t ′ +1) ) E 1 np 1 r (σ 2 + (Σ d,1,2 r ) 2 ) .
From relation (15) we have P(V (t) < X V (t ′ +1) ) = p 1 r , which concludes the proof of Lemma 1.

Therefore, we can upper bound the initial sum (14) of 2k + 1 terms by a sum of k + 1 terms of the same order as V ar j only involving intervals of the partition U 1 . At this stage, we get an upper bound for the variance of a forest which is of the same order as the variance of a tree. But we can do better. With similar arguments, we can prove the following lemma: Lemma 2 If there exist r and s such as

U 2 (s) < U 1 (r) < U 1 (r+1) < U 1 (r+2) < U 2 (s+1)
the expression

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))1 U 1 (r) <X U 1 (r+2) | U 1 , U 2 ]
is upper bounded by

p 2 s E 1 np 2 s (σ 2 + (Σ d,1,2 s ) 2 ) .
where

(Σ d,1,2 s ) 2 = (σ d,1,2 r+s ) 2 + (σ d,1,2 r+s+1 ) 2 .
Indeed,

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))1 U 1 (r) <X U 1 (r+1) | U 1 , U 2 ] p 1 r E 1 np 2 s (σ 2 + (σ d,1,2 r+s ) 2 )
and

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))1 U 1 (r+1) <X U 1 (r+2) | U 1 , U 2 ] p 1 r+1 E 1 np 2 s (σ 2 + (σ d,1,2 r+s+1 ) 2 ) .

RR n°7318

Finally, since p

1 r + p 1 r+1 p 2 s , (σ d,1,2 r+s ) 2 (σ d,1,2 r+s ) 2 + (σ d,1,2 r+s+1 ) 2 and (σ d,1,2 r+s+1 ) 2 (σ d,1,2 r+s ) 2 + (σ d,1,2 r+s+1 ) 2
, the result is obtained by summing the two terms.

As in Proposition 1, we replace all p l j E 1 np l j by their estimates (1 + δ np l j ).

By repeatedly applying this lemma for all intervals, we can upper bound

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X)) | U 1 , U 2 ] by a sum of N 1,2 terms of the form (1 + δ n, pt )(σ 2 + (Σ d,1,2 t ) 2 )
, where pt denotes for some j ∈ {0, . . . , k} either p 1 j or p 2 j depending on the fact that we are in the situation of Lemma 1 or Lemma

2, N 1,2 = k + 1 -M 1,2 and M 1,2 = k-2 r=1 k-1 s=1 1 U 2 (s) <U 1 (r) <U 1 (r+1) <U 1 (r+2) <U 2 (s+1) .
This concludes the proof of Proposition 5. Now, using the fact that we deal with uniform partitions, we manage to prove the following corollary.

Corollary 3 If k -----→ n→+∞ +∞, k n -----→ n→+∞ 0, µ > 0 and s is C-Lipschitz, we have, C(ŝ U 1 , ŝU 2 ) σ 2 E[N 1,2 ] n + o n→+∞ k n 3 4 σ 2 (k + 1) n + o n→+∞ k n .
Because of the simple draws of random partitions, the number M 1,2 is explicitly computable (we know the distribution of the two ordered statistics) and it is shown to be equivalent to 1 4 (k + 1) as k tends to +∞ (see Lemma 3 below). As in Proposition 2, we have to prove that all terms of the sum are negligible compared to the constant one σ 2 . To deal with the fact that the number of terms in the sum is now random, we use the following simple inequality: INRIA So, we have

E[(ŝ U 1 (X) -sU 1 (X))(ŝ U 2 (X) -sU 2 (X))] σ 2 E[N 1,2 ] n + o n→+∞ k n .
Finally, the following technical result allows to conclude the proof of Corollary 3, and thus the proof of Theorem2.

Lemma 3

E[M 1,2 ] = (k -2)(k -3) 2(2k -1) 1 + 4 (k + 1)(k -3)
.

Hence,

E[M 1,2 ] = k + 1 4 + o k→+∞ (k) .
We then obtain that

    k-4 t=0     1 - t + 1 t + 1 2k -3 -(t + 1) k -3 -(t + 1) 2k -3 k -3     + 1     = k -2 2(2k -1) k -3 + 4 k + 1
.

  upper bound tends to 0 as n tends to infinity.

2 t) 2 2 t) 2 (σ 2 2 t) 2

 2222222 2 δ n,pt ] + E[(Σ d,1,] + E[(Σ d,1,δ n,pt ] .These quantities are of the same kind as the three last terms in the sum of equation 4. So with the same techniques we get that1 δ n,pt + (Σ d,1,+ (Σ d,1,2 t ) 2 δ n,pt )

1 2k -r - 2 -s k -r - 2 ( 3 (F

 1223 the distribution of ordered statistics (see e.g. Section 2.2 of[START_REF] David | Order Statistics[END_REF]), we can compute the following probability:j -i)!(k -j)! E[(U 2 (s) ) i (U 2 (s+1) -U 2 (s) ) j-i (1 -U 2 (s+1) ) k-j ] 1)!(k -(s + 1))! (i + s -1)!(2k -(j + s)by elementary properties of binomial coefficients (see e.g.[START_REF] Graham | Concrete mathematics[END_REF] p.160)) by defining t = r + s)(2k-3,t+1,k-3) (t) -F H(2k-3,t+1,k-3) (t -k + 1)](where F H(N,m,n) denotes the cumulative distribution function of the hyper-H(2k-3,t+1,k-3) (t) = k -2 2(2k -1)

RR n°7318


Emmanuel Filiot
email: efiliot@ulb.ac.betlegall@ulb.ac.bejraskin@ulb.ac.be

Tristan Le Gall

Jean-Franc ¸ois Raskin

Iterated Regret Minimization in Game Graphs ⋆

Iterated regret minimization has been introduced recently by J.Y. Halpern and R. Pass in classical strategic games. For many games of interest, this new solution concept provides solutions that are judged more reasonable than solutions offered by traditional game concepts -such as Nash equilibrium -. In this paper, we investigate iterated regret minimization for infinite duration two-player quantitative non-zero sum games played on graphs.

Introduction

The analysis of complex interactive systems like embedded systems or distributed systems is a major challenge of computer aided verification. Zero-sum games on graphs provide a good framework to model interactions between a component and an environment as they are strictly competitive. However in the context of modern interactive systems, several components may interact and be controlled independently. Non-zero sum games on graphs are more accurate to model such systems, as the objectives of the components are not necessarily antagonist. Because of the quantitative aspects of the components (like energy consumption), we need some solution concept to be able to synthesis a component that respects some formal specification and is, in some sense, optimal. In the context of non-zero sum games on graphs for verification and synthesis, Nash equilibria or particular classes of Nash equilibria have been studied for qualitative objectives [START_REF] Grädel | Solution concepts and algorithms for infinite multiplayer games[END_REF][START_REF] Chatterjee | Games with secure equilibria[END_REF][START_REF] Fisman | Rational synthesis[END_REF] or quantitative objectives [START_REF] Brihaye | Equilibria in quantitative reachability games[END_REF]. Recently, J.Y. Halpern and R. Pass defined the notion of iterated regret minimization (IRM) [START_REF] Halpern | Iterated regret minimization: A more realistic solution concept[END_REF] in the general framework of (single-shot) strategic games, where the players choose in parallel their strategy among a finite number of strategies, and their respective payoffs are given by a finite matrix. They show that for many games of interest, Nash equilibria suggest strategies that are rejected by common sense, while iterated regret is an alternative solution concept that sometimes proposes more intuitive solutions. In this paper we consider games where the matrix is not given explicitly but defined implicitly by a game graph and we study the algorithmic aspects of IRM on such games. While it is easy to compute the iterated regret on a finite matrix, it is not that simple for game played on trees or graphs, as the number of strategies (and therefore the underlying matrix) is exponential in the size of a tree and even infinite for a graph.

The IRM solution concept assumes that instead of trying to minimize what she has to pay, each player tries to minimize her regret. The regret is informally defined as the difference between what a player actually pays and what she could have payed if she knew the strategy chosen by the other player 1 . More formally, if c 1 (λ 1 , λ 2 ) represents what Player 1 pays 2 when the pair of strategies (λ 1 , λ 2 ) is played, reg 1 (λ 1 , λ 2 ) = c 1 (λ 1 , λ 2 ) -min λ ′ 1 c 1 (λ ′ 1 , λ 2 ). Consider the strategic game defined by the matrix of Figure 1. In this game, Player 1 has two strategies A 1 and B 1 and Player 2 has two strategies A 2 and B 2 . The two players choose a strategy at the same time and the pairs of strategies define what the two players have to pay. The regret of playing A 1 for Player 1 when Player 2 plays A 2 is equal to

1 because c 1 (A 1 , A 2 ) is 2 while c 1 (B 1 , A 2 ) is 1.
Knowing that Player 2 plays A 2 , Player 1 should have played B 1 instead of A 1 .

As players have to choose strategies before knowing how the adversary will play, we associate a regret with each strategy as follows. The regret of a strategy λ 1 of Player 1 is : reg 1 (λ 1 ) = max λ2 reg 1 (λ 1 , λ 2 ). In the example, the regret of strategy A 1 is 1, because when Player 2 plays A 2 , Player 1's regret is 1, and when Player 2 plays B 2 her regret is 0. A rational player should minimize her regret, so that Player 1's regret is defined as reg 1 =min λ1 reg 1 (λ 1 ), summarizing, we get reg

1 =min λ1 max λ2 (c 1 (λ 1 , λ 2 )- min λ ′ 1 c 1 (λ ′ 1 , λ 2 )).
A symmetrical definition can be given for Player 2's regret. Let us come back to the example. The regret attached to strategy B 1 is 1. So A 1 and B 1 are equivalent for Player 1 w.r.t. regret minimization. On the other hand, for Player 2, the regret of A 2 is 0, and the regret of B 2 is 3. So, if Player 1 assumes that Player 2 tries to minimize her regret, then she must conclude that Player 2 will play A 2 . Knowing that, Player 1 recomputes her regret for each action, and in this case, the regret of action A 1 is 1 while the regret of B 1 is 0. So rational players minimizing their regret should end up playing (B 1 , A 2 ) in this game.

Reasoning on rationality is formalized by Halpern and Pass by introducing a delete operator that removes strictly dominated strategies. This operator takes sets of strategies (Λ 1 , Λ 2 ) for each player and returns

D(Λ 1 , Λ 2 ) = (Λ ′ 1 , Λ ′ 2 ) the strategies that minimize regret. Then D(Λ ′ 1 , Λ ′ 2 )
returns the strategies that minimize regret under the hypothesis that adversaries minimize their regret i.e., choose their strategies in Λ ′ 1 and Λ ′ 2 respectively. We iterate this operator until we reach a fixpoint, which represents the strategies minimizing the iterated regret.

In this paper, we consider games where the matrix is not given explicitly but defined implicitly by a game graph. In particular, we use the same definition of iterated regret as Halpern and Pass. More precisely, we consider graphs where vertices are partitioned into vertices that belong to Player 1 and vertices that belong to Player 2. Each edge is annotated by a cost for Player 1 and one for Player 2. Additionally, there are two designated sets of vertices, one that Player 1 tries to reach and the other one that Player 2 tries to reach. The game starts in the initial vertex of the graph and is played for an infinite number of rounds as follows. In each round, the player who owns the vertex on which the pebble is placed moves the pebble to an adjacent vertex using an edge of the graph, and a new round starts. The infinite plays generate an infinite sequence of vertices and the amount that the players have to pay are computed as follows. Player 1 pays +∞ if the sequence does not reach the target set assigned to her, otherwise she pays the sum of edge costs assigned to her on the prefix up to the first visit to her target set. The amount to pay for Player 2 is defined symmetrically. Strategies in such games are functions from the set of histories of plays (sequences of visited vertices) to the set of edges (choice of moves for the pebble).

Contributions

We first consider target-weighted arenas, where the payoff function is defined for each state of the objectives. We give a PTIME algorithm to compute the regret by reduction to a min-max game (and in linear time for trees). We then consider edge-weighted arenas. Each edge is labeled by a pair of integers -one for each player -, and the payoffs are defined by the sum of the weights along the path until the first visit to an objective. We give a pseudo-PTIME algorithm to compute the regret in an edgeweighted arena, by reduction to a target-weighted arena. We then study the problem of IRM. We provide a delete operator that removes strictly dominated strategies. We show how to compute the effect of iterating this operator on tree arenas and on the general class of graphs where the weights are stricly positive. In the first case, we provide a quadratic time algorithm and in the second case, a pseudo-exponential time algorithm.

Related works

Regret mimimization is a popular notion to define a goal for a learning agent [START_REF] Hastie | The Elements of Statistical Learning[END_REF] (in the machine learning theory). One can consider the selection of some strategies as a learning process. IRM is however not a classical concept of machine learning, since this notion is meaningless when there is a single learning agent. Like [START_REF] Halpern | Iterated regret minimization: A more realistic solution concept[END_REF], our work is thus more related to game theory than learning theory.

[9] investigates how to find a strategy that "mimimizes" the regret in extensive games with imperfect information. This kind of games can be considered as games on a probabilistic finite tree arena. We also consider finite tree arenas in Section 5.1. However in that paper, the strategies that achieve the mimimal value for regret are not computed, but a strategy with a regret less than a bound depending on the range of utilities, the number of actions and the number of rounds. IRM is not considered neither.

There are several notions of equilibria for reasoning on 2-player non-zero-sum (strategic) games, for instance Nash equilibrium, sequential equilibrium, perfect equilibrium -see [START_REF] Osborne | A Course in Game Theory[END_REF] for an overview. Those equilibria formalize notions of rational behavior by defining optimality criteria for pairs of strategies. As it has be shown by Halpern and Pass for several examples like the Centipede game or the Traveller's dilemma, IRM proposes solutions that are more intuitive and natural than Nash equilibria.

Weighted Games and Regret

Given a cartesian product A × B of two sets, we denote by proj i the i-th projection, i = 1, 2. It is naturally extended to sequence of elements of A×B by proj i (c 1 . . . c n ) = proj i (c 1 ) . . . proj i (c n ). For all k ∈ N, we let [k] = {0, . . . , k}.

Reachability Games

Turn-based two-player games are played on game arenas by two players. A (finite) game arena is a tuple G = (S = S 1 ⊎ S 2 , s 0 , T ) where S 1 , S 2 are finite disjoint sets of player positions (S 1 for Player 1 and S 2 for Player 2), s 0 ∈ S is the initial position, and T ⊆ S × S is the transition relation. A finite play on G of length n is a finite word π = π 0 π 1 . . . π n ∈ S * such that π 0 = s 0 and for all i = 0, . . . , n -1, (π i , π i+1 ) ∈ T . Infinite plays are defined similarly. We denote by P f (G) (resp. P ∞ (G))

1. c G i (π) = 8 < : +∞ if π is not winning for Player i P min{k | π k ∈C i }-1 j=0 µi(πj, πj+1) otherwise cost of a play π 2. c G i (λ1, λ2) = c G i (Out G (λ1, λ2))
cost of two strategies λ1, λ2.

br

G i (λ-i) = min λ i ∈Λ i (G) c G i (λi, λ-i) best response of player i against λ-i 4. reg G i (λi, λ-i) = c G i (λi, λ-i) -br G i (λ-i).
regret of two strategies λ1, λ2

5. reg G i (λi) = max λ -i ∈Λ -i (G) reg G i (λi, λ-i) regret of a strategy λi 6. reg G i = min λ i ∈Λ i (G) reg G i (λi). regret of Player i
(G) = P f (G) ∪ P ∞ (G)
. For any node s ∈ S, we denote by (G, s) the arena G where the initial position is s.

Let i ∈ {1, 2}. We let -i = 1 if i = 2 and -i = 2 if i = 1. A strategy λ i : P f (G) → S ∪ {⊥}
for Player i is a mapping that maps any finite play π whose last positiondenoted last(π) -is in S i to ⊥ if there is no outgoing edge from last(π), and to a position

s such that (last(π), s) ∈ T otherwise. The set of strategies of Player i in G is denoted by Λ i (G). Given a strategy λ -i ∈ Λ -i (G), the outcome Out G (λ i , λ -i ) is the unique play π = π 0 . . . π n . . . such that (i) π 0 = s 0 , (ii) if π is finite,
then there is no outgoing edge from last(π), and (iii) for all 0 ≤ j ≤ |π| and all κ = 1, 2, if π j ∈ S κ , then

π j+1 = λ κ (π 0 . . . π j ). We also define Out G (λ i ) = {Out G (λ i , λ -i ) | λ -i ∈ Λ -i (G)}. A strategy λ i is memoryless if for any play h ∈ P f (G), λ 1 (h) only depends on last(h).
Thus λ i can be seen as a function S i → S ∪ {⊥}. It is finite-memory if λ 1 (h) only depends on last(h) and on some state of a finite state set (see [START_REF] Grädel | Automata, Logics and Infinite Games[END_REF] for formal definitions).

A reachability winning condition for Player i is given by a subset of positions C i ⊆ S -called the target set -. A play π ∈ P(G) is winning for Player i if some position of π is in C i . A strategy λ i for Player i is winning if all the plays of Out G (λ i ) are winning. In this paper, we often consider two target sets C 1 , C 2 for Player 1 and 2 respectively. We write (S 1 , S 2 , s 0 , T, C 1 , C 2 ) to denote the game arena G extended with those target sets. Finally, let λ i ∈ Λ i (G) be a winning strategy for Player i and

λ -i ∈ Λ -i (G). Let π 0 π 1 • • • ∈ P(G) be the outcome of (λ i , λ -i ). The outcome of (λ i , λ -i ) up to C i is defined by Out G,Ci (λ i , λ -i ) = π 0 . . . π n such that n = min{j | π j ∈ C i }.
We extend this notation to sets of plays Out G,Ci (λ i ) naturally.

Weighted Games We add weights on edges of arenas and include the target sets. A (finite) weighted game arena is a tuple

G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C 1 , C 2 ) where (S, s 0 , T ) is a game arena, µ i : T → N is a weight function for Player i and C i its target set, i = 1, 2. We let M G i be the maximal weight of Player i, i.e. M G i = max e∈T µ i (e) and M G = max(M G 1 , M G 2 )
. G is a target-weighted arena (TWA for short) if only the edges leading to a target node are weighted by strictly positive integers, and any two edges leading to the same node carry the same weight. Formally, for all (s, s

′ ) ∈ T , if s ′ ∈ C i , then µ i (s, s ′ ) = 0, otherwise for all (s ′′ , s ′ ) ∈ T , µ i (s, s ′ ) = µ i (s ′′ , s ′ ).
Thus for target-weighted arenas, we assume in the sequel that the weight functions map C i to N.

Plays, cost, best response and regret

Let π = π 0 π 1 . . . π n be a finite play in G. We extend the weight functions to finite plays, so that for all i = 1, 2,

µ i (π) = n-1 j=0 µ i (π j , π j+1 ). Let i ∈ {1, 2}, the cost c G i (π) of π (for Player i) is +∞ if π is not
winning for Player i, and the sum of the weights occuring along the edges defined by π until the first visit to a target position otherwise, see Fig. 2(1). In Fig. 2(2), we extend this notion to the cost of two strategies λ 1 , λ 2 of Player 1 and 2 respectively. The best response of Player i to λ -i , denoted by br G i (λ -i ), is the least cost Player i can achieve against λ -i (Fig. 2(3)). The regret for Player i of playing λ i against λ -i is the difference between the cost Player i pays and the best response to λ -i (Fig. 2

(4)). Note that reg G i (λ i , λ -i ) ≥ 0, since br G i (λ -i ) ≤ c G i (λ i , λ -i ).
The regret of λ i for Player i is the maximal regret she gets for all strategies of Player -i (Fig. 2(5)). Finally, the regret of Player i in G is the minimal regret she can achieve (Fig. 2 Proof. If Player i has no winning strategy, then for all

λ i ∈ Λ i (G), there is λ -i ∈ Λ -i (G) s.t. c G i (λ i , λ -i ) = +∞. Thus reg G i (λ i , λ -i ) = +∞. Therefore reg G i = +∞. If Player i has a winning strategy λ i , then for all λ -i ∈ Λ -i (G), c G i (λ i , λ -i ) < +∞ and br G i (λ -i ) ≤ c G i (λ i , λ -i ) < +∞. Thus reg G i ≤ reg G i (λ i ) < +∞. ⊓ ⊔ Example 1.
Consider the game arena G of Fig. 3. Player 1's positions are circle nodes and Player 2's positions are square nodes. The target nodes are represented by double circles. The initial node is A. The weights are given by pairs of integers for Player 1 and 2 respectively. In this example, we first compute Player 1's regret.

Let λ 1 be the memoryless strategy defined by λ 1 (B) = C and λ

1 (C) = E. For all λ 2 ∈ Λ 2 (G), Out G 1 (λ 1 , λ 2 )
is either ACE or ABCE, depending on whether Player 2 goes directly to C or passes by B. In both cases, the outcome is winning and

c G 1 (λ 1 , λ 2 ) = 3.
What is the regret of playing λ 1 for Player 1? To compute reg 1 G (λ 1 ), we should consider all possible strategies of Player 2, but a simple observation allows us to restrict this range. Indeed, to maximize the regret of Player 1, Player 2 should cooperate in subtrees where λ 1 prevents to go, i.e. in the subtrees rooted at D and F . Therefore we only have to consider the two following memoryless strategies λ 2 and λ ′ 2 : both λ 2 and λ ′ 2 move from F to J and from D to

H, but λ 2 (A) = B while λ ′ 2 (A) = C. In both cases, going to F is a best response to λ 2 and λ ′ 2 for Player 1, i.e. br G 1 (λ 2 ) = br G 1 (λ ′ 2 ) = 0. Therefore we get reg G 1 (λ 1 , λ 2 ) = c G 1 (λ 1 , λ 2 ) -br G 1 (λ 2 ) = 3 -0 = 3. Similarly reg G 1 (λ 1 , λ ′ 2 ) = 3. Therefore reg G 1 (λ 1 ) = 3.
As a matter of fact, the strategy λ 1 minimizes the regret of Player 1. Indeed, if she chooses to go from B to D, then Player 2 moves from A to B and from D to G (so that Player 1 gets a cost 3) and cooperates in the subtree rooted at C by moving from F to J. The regret of Player 1 is therefore 3. If Player 1 moves from B to C and from C to F , then Player 2 moves from A to C and from F to I (so that Player 1 gets a cost 4), and from D to H, the regret of Player 1 being therefore 4. Similarly, one can show that all other strategies of Player 1 have a regret at least 3. Therefore reg G 1 = 3. Note that the strategy λ 1 does not minimize the regret in the subgame defined by the subtree rooted at C. Indeed, in this subtree, Player 1 has to move from C to F , and the regret of doing this is 4 -3 = 1. However the regret of λ 1 in the subtree is 3. This example illustrates a situation where a strategy that minimizes the regret in the whole game does not necessarily minimize the regret in the subgames. Therefore we cannot apply a simple inductive bottom-up algorithm to compute the regret. As we will see in the next section, we first have to propagate some information in the subgames.

Regret Minimization on Target-Weighted Graphs

In this section, our aim is to give an algorithm to compute the regret of Player i. This is done by reduction to a min-max game, defined in the sequel. We say that we solve the regret minimization problem (RMP for short) if we can compute the minimal regret and a (finite representation of a) strategy that achieves this value. We first introduce the notion of games with minmax objectives. Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C 1 , C 2 ) be a TWA and i = 1, 2. We let

minmax G i = min λi∈Λi(G) max λ-i∈Λ-i(G) c G i (λ i , λ -i ). Proposition 2. Given a TWA G = (S, s 0 , T, µ 1 , µ 2 , C 1 , C 2 ), i ∈ {1, 2} and K ∈ N, one can decide whether minmax G i ≤ K in time O(|S|+|T |).
The value minmax G i and a memoryless strategy that achieves it can be computed in time

O(log 2 (M G i )(|S| + |T |)).
Since the player have symmetric roles, wlog we can focus on computing the regret of Player 1 only. Therefore we do not consider Player 2's targets and weights. Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , C 1 ) be a TWA (assumed to be fixed from now on). Let λ 1 ∈ Λ 1 (G) be a winning strategy of Player 1 (if it exists). Player 2 can enforce Player 1 to follow one of the paths of Out G,C1 (λ 1 ) by choosing a suitable strategy. When choosing a path π ∈ Out G,Ci (λ 1 ), in order to maximize the regret of Player 1, Player 2 cooperates (i.e. she minimizes the cost) if Player 1 would have deviated from π. This leads to the notion of best alternative along a path. Informally, the best alternative along π is the minimal value Player 1 could have achieved if she deviated from π, assuming Player 2 cooperates. Since Player 2 can enforce one of the paths of Out G,C1 (λ 1 ), to maximize the regret of Player 1, she will choose the path π with the highest difference between c G 1 (π) and the minimal best alternative along π. As an example consider the TWA arena of Fig. 3. In this example, if Player 1 moves from C to E, then along the path ACE, the best alternative is 0. Indeed, the other alternative was to go from C to F and in this case, Player 2 would have cooperated.

We now formally define the notion of best alternative. Let s ∈ S 1 . The best value that can be achieved from s by Player 1 when Player 2 cooperates is defined by: best

G 1 (s) = min λ1∈Λ1(G,s) min λ2∈Λ2(G,s) c (G,s) 1 (λ 1 , λ 2 )
Let (s, s ′ ) ∈ T . The best alternative of choosing s ′ from s for Player 1, denoted by ba G 1 (s, s ′ ), is defined as the minimal value she could have achieved by choosing another successor of s (assuming Player 2 cooperates). Formally:

ba G 1 (s, s ′ ) = +∞ if s ∈ S 2 min (s,s ′′ )∈T,s ′′ =s ′ best G 1 (s ′′ ) if s ∈ S 1
with min ∅ = +∞. Finally, the best alternative of a path π = s 0 s 1 . . . s n is defined as +∞ if n = 0 and as the minimal best alternative of the edges of π otherwise:

ba 1 G (π) = min 0≤j<n ba 1 G (s j , s j+1 )
We first transform the graph G into a graph G ′ such that all the paths that lead to a node s have the same best alternative. This can be done since the number of best alternatives is bounded by |C 1 |. The construction of G ′ is done inductively by storing the best alternatives in the positions.

Definition 1. The graph of best alternatives of G is the

TWA G ′ = (S ′ = S ′ 1 ⊎ S ′ 2 , s ′ 0 , T ′ , µ ′ 1 , C ′ 1 ) where S ′ i = S i × ([M G 1 ] ∪ {+∞}), s ′ 0 = (s 0 , +∞), C ′ 1 = S ′ 1 ∩ (C 1 × [M G 1 ]), for all (s, b) ∈ C ′ 1 , µ ′ 1 (s, b) = µ 1 (s)
, and for all (s, b 1 ), (s

′ , b ′ 1 ) ∈ S ′ , ((s, b 1 ), (s ′ , b ′ 1 )) ∈ T ′ iff (s, s ′ ) ∈ T and b ′ 1 = min(b 1 , ba G 1 (s, s ′ )) if s ∈ S 1 b 1 if s ∈ S 2
The best alternative along the paths that lead to the same node is unique. Moreover, as the number of best alternatives is bounded by |C 1 |, G ′ can be constructed in PTime: Since the best alternative information depends only on the paths, the paths of G and those of G ′ are in bijection. This bijection can be extended to strategies. In particular, we define two mappings Φ i from Λ i (G) to Λ i (G ′ ), for all i = 1, 2. For all path π = s 0 s 1 . . . in G (finite or infinite), we denote by B(π) the path of G ′ defined by (s 0 , b 0 )(s 1 , b 1 ) . . . where b 0 = +∞ and for all j > 0, b j = ba 1 G (s 0 . . . s j-1 ). The mapping B is bijective, and its inverse corresponds to proj 1 .

The mapping Φ i maps any strategy λ i ∈ Λ i (G) to a strategy Φ i (λ i ) ∈ Λ i (G ′ ) such that Φ i (λ i ) behaves as λ i on the first projection of the play and adds the best alternative information to the position. Let h ∈ S ′ * such that last(h

) ∈ S ′ i . Let s = λ i (proj 1 (h)). Then Φ i (λ i )(h) = (s, ba 1 G (proj 1 (h).s)). The inverse mapping Φ -1 i
just projects the best alternative information. In particular, for all λ ′ i ∈ Λ i (G ′ ), and all h ∈ S * such that last(h)

∈ S i , Φ -1 i (λ i )(h) = proj 1 (λ i (B(h)))
. Clearly, the mappings Φ i are bijective. The best alternative information is crucial. This is a global information that allows us to compute the regret locally. For all (s, b)

∈ C ′ 1 , we let ν 1 (s, b) = µ 1 (s) - min(µ 1 (s), b), and extend ν 1 to strategies naturally (ν 1 (λ 1 , λ 2 ) = +∞ if λ 1 is losing). Lemma 1. Let H = (S ′ , s ′ 0 , T ′ , ν 1 , C ′ 1 )
where S ′ , s ′ 0 , T ′ , C ′ 1 are defined in Definition 1. For all λ 1 ∈ Λ 1 (G) and all λ ′ 1 ∈ Λ 1 (G ′ ), the following holds:

1. reg G 1 (λ 1 ) = reg G ′ 1 (Φ 1 (λ 1 )) 2. reg G ′ 1 (λ ′ 1 ) = max λ ′ 2 ∈Λ2(G ′ ) ν 1 (λ ′ 1 , λ ′ 2 ) 3. reg G 1 = minmax H 1
Proof. 1 and 2 are in the full version of the paper. For 3, we have

reg G 1 = min λ1∈Λ1(G) reg G 1 (λ 1 ) (by definition) = min λ1∈Λ1(G) reg H 1 (Φ 1 (λ 1 )) (by 1) = min λ1∈Λ1(H) reg H 1 (λ 1 ) (by 1) = min λ1∈Λ1(H) max λ2∈Λ2(H) ν 1 (λ 1 , λ 2 ) (by 2)
As a consequence of Lemma 1, we can solve the RMP on TWAs. We first compute the graph of best alternatives and solve a minmax game. This gives us a memoryless strategy that achieves the minimal regret in the graph of best alternatives. To compute a strategy in the original graph, we apply the inverse mapping Φ -1

1 : this gives a finitememory strategy whose memory is exactly the best alternative seen along the current finite play. Therefore the needed memory is bounded by the number of best alternatives, which is bounded by

|C 1 |. Theorem 1. The RMP on a TWA G = (S, s 0 , T, µ 1 , C 1 ) can be solved in time O(|C 1 |• log 2 (M G 1 ) • (|S| + |T |)), where M G 1 = max e∈T µ i (e).

Regret Minimization in Edge-Weighted Graphs

In this section, we give a pseudo-polynomial time algorithm to solve the RMP in weighted arenas (with weights on edges). In a first step, we prove that if the regret is finite, the strategies minimizing the regret generates outcomes whose cost is bounded by some value which depends on the graph. This allows us to reduce the problem to the RMP in a TWA, which can then be solved by the algorithm of the previous section. Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , C 1 ) be a weigthed game arena with objective C 1 . As in the previous section, we assume that we want to minimize the regret of Player 1, so we omit the weight function and the target of Player 2.

Definition 2 (Bounded strategies). Let B ∈ N and λ

1 ∈ Λ 1 (G). The strategy λ 1 is bounded by B if for all λ 2 ∈ Λ 2 (G), c G 1 (λ 1 , λ 2 ) ≤ B.
Note that a bounded strategy is necessarily winning, since by definition, the cost of some outcome is infinite iff it is loosing. The following lemma states that the winning strategies that minimize the regret of Player 1 are bounded. Lemma 2. For all weighted arena G = (S, s 0 , T, µ 1 , C 1 ) and for any strategy λ 1 ∈ Λ 1 (G) winning in G for Player 1 that minimizes her regret, λ 1 is bounded by 2M G |S|.

Proof (Sketch).

If there is a winning strategy, there is a memoryless winning strategy

γ 1 ([4]). Then reg G 1 ≤ reg G 1 (γ 1 ). For any λ 2 , Out G,C1 (γ 1 , λ 2 ) does not contain twice the same position. Thus c 1 G (γ 1 , λ 2 ) ≤ M G |S|. Moreover, br G 1 (λ 2 ) ≤ c 1 G (γ 1 , λ 2 ) ≤ M G |S|. Thus reg G 1 ≤ reg G 1 (γ 1 , λ 2 ) ≤ M G |S|. Let λ 1 minimizing reg G 1 (λ 1 ). Then reg G 1 (λ 1 , λ 2 ) ≤ M G |S|, so c G 1 (λ 1 , λ 2 ) ≤ M G |S| + br 1 (λ 2 ) ≤ 2M G |S|, for any λ 2 .
Let B = 2M G |S|. Thanks to Lemma 2 we can reduce the RMP in a weighted arena into the RMP in a TWA. Indeed, it suffices to enrich every position of the arena with the sum of the weights occuring along the path used to reach this position. A position may be reachable by several paths, therefore it will be duplicated as many times as they are different path utilities. This may be unbounded, but Lemma 2 ensures that it is sufficient to sum the weights up to B only. This may results in a larger graph, but its size is still pseudo-polynomial (polynomial in the maximal weight and the size of the graph).

Definition 3. Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , C 1 ) be a weigthed game arena. The graph of cost is the TWA G ′ = (S ′ = S ′ 1 ⊎ S ′ 2 , s ′ 0 , T ′ , µ ′ 1 , C ′ 1 ) defined by: (i) S ′ i = S i × [B] and s ′ 0 = (s 0 , 0); (ii) for all (s, u), (s ′ , u ′ ) ∈ S ′ , ((s, u), (s ′ , u ′ )) ∈ T ′ iff (s, s ′ ) ∈ T and u ′ = u + µ 1 (s, s ′ ); (iii) C ′ 1 = (C 1 × [B]) ∩ S ′ and ∀(s, u) ∈ C ′ 1 , µ ′ 1 (s, u) = u. Lemma 3. reg G 1 = reg G ′ 1
Proof (Sketch). We define a mapping Φ that maps the strategies of Player i in G to the strategies of Player i in G ′ , for all i ∈ {1, 2}, which satisfies Φ(Λ i (G)) = Λ i (G ′ ) and preserves the regret of Player 1's strategies bounded by

B, i.e. reg G 1 (λ 1 ) = reg G 1 (Φ(λ 1 )), for all λ 1 ∈ Λ 1 (G) bounded by B. ⊓ ⊔
To solve the RMP for a weighted arena G, we first construct the graph of cost G ′ , and then apply Theorem 1, since G ′ is a TWA. Correctness is ensured by Lemma 3. This returns a finite-memory strategy of G ′ that minimizes the regret, whose memory is the best alternative seen so far. To obtain a strategy of G minimizing the regret, one applies the inverse mapping Φ -1 . This gives us a finite-memory strategy whose memory is the cost of the current play up to M G and the best alternative seen so far.

Theorem 2. The RMP on a weighted arena

G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , C 1 ) can be solved in time O (M G ) 2 • log 2 (|S| • M G ) • |S| • |C 1 | • (|S| + |T |) .

Iterated Regret Minimization (IRM)

In this section, we show how to compute the iterated regret for tree arenas and for weighted arenas where weights are strictly positive (by reduction to a tree arena).

Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C 1 , C 2 ) be a weighted arena. Let i ∈ {1, 2}, P i ⊆ Λ i (G) and P -i ⊆ Λ -i (G). The regret of Player i when she plays strategies of P i and when Player -i plays strategies of P -i is defined by:

reg G,Pi,P-i i = min λi∈Pi max λ-i∈P-i c G i (λ i , λ -i ) -br G,Pi i (λ -i ) br G,Pi i (λ -i ) = min λ * i ∈Pi c G i (λ * i , λ -i )
For all λ i ∈ P i and λ -i ∈ P -i , we define reg G,Pi,P-i i (λ i ) and reg G,Pi,P-i i (λ i , λ -i ) accordingly. We now define the strategies of rank j, which are the ones that survived j times the deletion of strictly dominated strategies. The strategies of rank 0 for Player i is Λ i (G). The strategies of rank 1 for both players are those which minimize their regret against strategy of rank 0. More generally, the strategies of rank j for Player i are the strategies of rank j -1 which minimize her regret against Player -i's strategies of rank j -1. Formally, let i ∈ {1, 2}, P 1 ⊆ Λ 1 (G) and all P 2 ⊆ Λ 2 (G). Then D i (P 1 , P 2 ) is the set of strategies λ i ∈ P i such that reg G,Pi,P-i i = reg G,Pi,P-i i (λ i ). Then the strategies of rank j are obtained via a delete operator D

: 2 Λ1(G) × 2 Λ2(G) → 2 Λ1(G) × 2 Λ2(G) such that D(P 1 , P 2 ) = (D 1 (P 1 , P 2 ), D 2 (P 1 , P 2 )). We let D j = D • • • • • D (j times).
Definition 4 (j-th regret). Let j ≥ 0. The set of strategies of rank j for Player i is

P j i = proj i (D j (Λ 1 (G), Λ 2 (G))). The j + 1-th regret for Player i is defined by reg G,j+1 i = reg G,P j i ,P j -i i . In particular, reg G,1 i = reg G i . Proposition 4. Let i ∈ {1, 2}. For all j ≥ 0, P j+1 i ⊆ P j i and reg G,j+1 i ≤ reg G,j i . Moreover, there is ⋆ ≥ 1 such that for all j ≥ ⋆, for all i ∈ {1, 2}, reg G,j i = reg G,⋆ i .
Definition 5 (iterated regret). For all i = 1, 2, the iterated regret of Player i is reg G,⋆ i .

Example 2. Consider the example of Fig. 3. We already saw that the strategies that minimize Player 1's regret are B → C → E and B → D, in which cases we have

reg G 1 = reg G,1 1 = 3.
The strategies that minimize Player 2's regret are λ 2 : A → C, F → I and λ ′ 2 : A → C, F → J, in which cases her regret is 0. If Player 1 knows that Player 2 plays according to λ 2 or λ ′ 2 , she can still play C → E but now her regret is 0, so that reg G,⋆ 1 = 0. Similarly, reg G,⋆ 2 = 0.

IRM in Tree Arenas

In this section, we let i ∈ {1, 2} and G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C 1 , C 2 ) be a finite edge-weighted tree arena. We can transform G into a target-weighted tree arena such that C 1 = C 2 (denoted by C in the sequel) is the set of leaves of the tree, if we allow the functions µ i to take the value +∞. This transformation results in a new targetweighted tree arena G ′ = (S = S 1 ⊎ S 2 , s 0 , T, µ ′ 1 , µ ′ 2 , C) with the same set of states and transitions as G and for all leaf s ∈ C, µ ′ i (s) = c G ′ i (π), where π is the root-to-leaf path leading to s. The time complexity of this transformation is O(|S|).

We now assume that G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C) is a target-weighted tree arena where C is the set of leaves. Our goal is to define a delete operator D such that D(G) is a subtree of G such that for all i = 1, 2, Λ i (D(G)) are the strategies of Λ i (G) that minimize reg G i . In other words, any pairs of subsets of strategies for both players in G can be represented by a subtree of G. This is possible since all the strategies in a tree arena are memoryless. A set of strategies P i ⊆ Λ i (G) is therefore represented by removing from G all the edges (s, s ′ ) such that there is no strategy λ i ∈ P i such that λ i (s) = s ′ . In our case, one first computes the set of strategies that minimize regret. This is done as in Section 3 by constructing the tree of best alternatives H (but in this case with the best alternative of both players) and by solving a min-max game. From H we delete all edges that are not compatible with a strategy that minimize the minmax value of some player. We obtain therefore a subtree D(H) of H such that any strategy of H is a strategy of D(H) for Player i iff it minimizes the minmax value in H for Player i. By projecting away the best alternative information in D(H), we obtain a subtree D(G) of G such that any Player i's strategy of G is a strategy of D(G) iff it minimizes Player i's regret in G. We can iterate this process to compute the iterated regret, and we finally obtain a subtree D * (G) such that any strategy of G minimizes the iterated regret for Player i iff it is a Player i's strategy in D * (G).

Definition 6. The tree of best alternatives of G is the tree H

= (S ′ 1 , S ′ 2 , s ′ 0 , T ′ , µ ′ 1 , µ ′ 2 , C ′ ) where: (i) S ′ = S ′ 1 ⊎ S ′ 2 with S ′ i = {(s, b 1 , b 2 ) | s ∈ S i , b κ = ba G κ (π s ), κ = 1, 2}
where π s is the path from the root s 0 to s, (ii) s ′ 0 = (s 0 , +∞, , +∞), (iii) for all s, s ′ ∈ S ′ , (s, s ′ ) ∈ T ′ iff (proj 1 (s), proj 1 (s ′ )) ∈ T , (iv)

C ′ = {s ∈ S ′ | proj 1 (s) ∈ C}, (v) for all (s, b 1 , b 2 ) ∈ C ′ , µ ′ i (s, b 1 , b 2 ) = µ i (s) -min(µ i (s), b i ).
Note that H is isomorphic to G. There is indeed a one-to-one mapping Φ between the states of G and the states of H: for all s ∈ S, Φ(s) is the only state s ′ ∈ S ′ of the form s ′ = (s, b 1 , b 2 ). Moreover, this mapping is naturally extended to strategies. Since all strategies are memoryless, any strategy

λ i ∈ Λ i (G) is a function S i → S. Thus, for all s ′ ∈ S ′ i , Φ(λ i )(s ′ ) = Φ λ i (Φ -1 (s ′ ))
. Without loss of generality and for a technical reason, we assume that any strategy λ i is only defined for states s ∈ S i that are compatible with this strategy, i.e. if s is not reachable under λ i then the value of λ i does not need to be defined. The lemmas of Section 3 still hold for the tree H. In particular, for all i ∈ {1, 2}, Φ(Λ i (G)) = Λ i (H) and any strategy

λ i ∈ Λ i (G) minimizes reg G i iff Φ(λ i ) minimizes minmax H i . Moreover reg G i = minmax H i .
As in Section 3, the RMP on a tree arena can be solved by a min-max game. For all s ∈ S ′ , we define minmax H i (s) = minmax (H,s) i

and compute these values inductively by a bottom-up algorithm that runs in time O(|S|). This algorithm not only allows us to compute minmax H i for all i ∈ {1, 2}, but also to compute a subtree D(H) that represents all Player i's strategies that achieve this value. We actually define the operator D in two steps. First, we remove the edges (s, s ′ ) ∈ T ′ , such that s ∈ S ′ i and minmax H i (s ′ ) > minmax H i for all i = 1, 2. We obtain a new graph H ′ consisting of several disconnected tree components. In particular, there are some states no longer reachable from the root s ′ 0 . Then we keep the connected component that contains s ′ 0 and obtain a new tree D(H). Since there is a one-to-one correspondence between the strategies minimizing the regret in G and the strategies minimizing the minmax value in H, we can define D(G) by applying to D(H) the isomorphism Φ -1 , in other words by projecting the best alternatives away, and by restoring the functions µ i . We obtain a new tree D(G) whose Player i's strategies minimize the regret of Player i, i = 1, 2. We can iterate the regret computation on D(G) and get the Player i's strategies that minimize the regret of rank 2 of Player i, i = 1, 2. We continue iteration until we get a tree G ′ such that D(G ′ ) = G ′ . We let D 0 (G) = G and D j+1 (G) = D(D j (G)).

Proposition 5. Let i ∈ {1, 2} and j > 0. We have reg G,j i = reg

D j-1 (G) i . Theorem 3. Let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C) be a tree arena. For all i = 1, 2, the iterated regret of Player i, reg G,⋆ i , can be computed in time O(|S| 2 ). Proof. There is an integer j such that reg G,⋆ i = reg D j (G) i
. According to the definition of D(G), j ≤ |S| because we remove at least one edge of the tree at each step. Since D(G) can be constructed in time O(|S|), the whole time complexity is O(|S| 2 ). ⊓ ⊔

IRM in Positive Weighted Arenas

A weighted arena G is said to be positive if all edges are weighted by strictly positive weights only. In this section, we let G = (S = S 1 ⊎ S 2 , s 0 , T, µ 1 , µ 2 , C 1 , C 2 ) be a positive weighted arena. Remind that P j i (G) is the set of strategies that minimize reg G,j i , for all j ≥ 0 and i = 1, 2. As for the regret computation in edge-weighted graphs, we define a notion of boundedness for strategies. Then the iterated regret is computed on the unfolding of the graph, up to some cost bound. Definition 7 (j-winning and j-bounded strategies).

Let i ∈ {1, 2} and λ i ∈ Λ i (G). The strategy λ i is j-winning if for all λ -i ∈ P j -i (G), Out G (λ i , λ -i ) is winning. It is j-bounded by some B ≥ 0 if it is j-winning, and for all λ -i ∈ P j -i (G) and all κ ∈ {i, -i}, µ κ (Out G,Ci (λ i , λ -i )) ≤ B.

Note that j-boundedness differs from boundedness as we require that the utilities of both players are bounded. We let b G = 6(M G ) 3 |S|. We get a similar result than the boundedness of strategies that miminize the regret of rank 1, but for any rank: Lemma 4. For all i = 1, 2 and all j ≥ 0, all j-winning strategies of Player i which minimize the (j + 1)-th regret are j-bounded by b G . For all i = 1, 2, the procedure of Section 5.1 returns a finite-memory strategy λ i minimizing the iterated regret in G ′ whose memory is the best alternatives seen so far by both players. From λ i we can compute a finite-memory strategy in G minimizing the iterated regret of Player i, the needed memory is the best alternatives seen by both players and the current finite play up to B G . When the cost is greater than B G , then any move is allowed. Therefore one needs to add one more bit of memory expressing whether the cost is greater than B G .

Conclusion

The theory of infinite qualitive non-zero sum games over graphs is still in an initial development stage. We adapted a new solution concept from strategic games to game graphs, and gave algorithms to compute the regret and iterated regret. The strategies returned by those algorithms have a finite memory. One open question is to know whether this memory is necessary. In other words, are memoryless strategies sufficient to minimize the (iterated) regret in game graphs? Another question is to determine a lower bound on the complexity of (iterated) regret minimization. Iterated regret minimization over the full class of graphs is still open. In the case of (strictly) positive arenas, the unfolding of the graph arena up to some cost bound can be seen as a finite representation of (possibly infinite) set of strategies of rank j in G. Finding such a representation is not obvious for the full class of weighted arenas, since before reaching its objective, a player can take a 0-cost loop finitely many times without affecting her minimal regret. This suggests to add fairness conditions on edges to compute the IR.

A 2 B 2 A 1 ( 2

 212 Fig. 1.

Fig. 2 .

 2 Fig. 2. Cost, best response, and regretthe set of finite (resp. infinite) plays on G, and we let P(G) = P f (G) ∪ P ∞ (G). For any node s ∈ S, we denote by (G, s) the arena G where the initial position is s.Let i ∈ {1, 2}. We let -i = 1 if i = 2 and -i = 2 if i = 1.A strategy λ i : P f (G) → S ∪ {⊥} for Player i is a mapping that maps any finite play π whose last positiondenoted last(π) -is in S i to ⊥ if there is no outgoing edge from last(π), and to a position s such that (last(π), s) ∈ T otherwise. The set of strategies of Player i in G is denoted byΛ i (G). Given a strategy λ -i ∈ Λ -i (G), the outcome Out G (λ i , λ -i ) is the unique play π = π 0 . . . π n . . . such that (i) π 0 = s 0 , (ii) if π is finite,then there is no outgoing edge from last(π), and (iii) for all 0 ≤ j ≤ |π| and all κ = 1, 2, if π j ∈ S κ , thenπ j+1 = λ κ (π 0 . . . π j ). We also define Out G (λ i ) = {Out G (λ i , λ -i ) | λ -i ∈ Λ -i (G)}.A strategy λ i is memoryless if for any play h ∈ P f (G), λ 1 (h) only depends on last(h). Thus λ i can be seen as a function S i → S ∪ {⊥}. It is finite-memory if λ 1 (h) only depends on last(h) and on some state of a finite state set (see[START_REF] Grädel | Automata, Logics and Infinite Games[END_REF] for formal definitions).A reachability winning condition for Player i is given by a subset of positions C i ⊆ S -called the target set -. A play π ∈ P(G) is winning for Player i if some position of π is in C i . A strategy λ i for Player i is winning if all the plays of Out G (λ i ) are winning. In this paper, we often consider two target sets C 1 , C 2 for Player 1 and 2 respectively. We write (S 1 , S 2 , s 0 , T, C 1 , C 2 ) to denote the game arena G extended with those target sets. Finally, let λ i ∈ Λ i (G) be a winning strategy for Player i and λ -i ∈ Λ -i (G). Let π 0 π 1 • • • ∈ P(G) be the outcome of (λ i , λ -i ). The outcome of (λ i , λ -i ) up to C i is defined by Out G,Ci (λ i , λ -i ) = π 0 . . . π n such that n = min{j | π j ∈ C i }. We extend this notation to sets of plays Out G,Ci (λ i ) naturally.

Fig. 3 .

 3 Fig. 3. Weighted Graph Arena

Proposition 3 .

 3 For all (s, b) ∈ S ′ and all finite path π in G ′ from (s 0 , +∞) to (s, b), ba G ′ 1 (π) = b. G ′ can be constructed in time O (|C 1 | + log 2 (M G 1 )) × (|S| + |T |) .

Lemma 4

 4 allows us to reduce the problem to the IRM in a weighted tree arena, by unfolding the graph arena G up to some maximal cost value. Lemma 4 suggests to take b G for this maximal value. However the best responses to a strategy j-bounded by b G are not necessarily bounded by b G , but they are necessarily j-bounded by b G • M G , since the weights are strictly positive. Therefore we let B G = b G • M G and take B G as the maximal value. Since the j-winning strategies are j-bounded by b G and the best responses are j-bounded by B G , we do not lose information by taking the unfolding up to B G . Finally we apply Theorem 3 on the unfolding. One of the most technical result is to prove the correctness of this reduction.

Theorem 4 .

 4 The iterated regret for both players in a positive weighted arena G can be computed in pseudo-exponential time (exponential in |S|, |T | and M G ).

We only consider

2-player games, but our work can be easily extended to n-player games.[START_REF] Chatterjee | Games with secure equilibria[END_REF] We could have considered rewards instead of penalties, everything is symmetrical.

⋆ Work supported by the projects: (i) Quasimodo: "Quantitative System Properties in Model-Driven-Design of Embedded", http://www.quasimodo.aau.dk/, (ii) Gasics: "Games for Analysis and Synthesis Software", http://moves.ulb.ac.be, a PAI program funded by the Federal Belgian Government.


Muhammad Nauman Qureshi

Unai Arrieta

Christophe Baudet

Alain H Cartellier

Yves Gagne

Mickaël Bourgoin
email: mickael.bourgoin@hmg.inpg.fr

Nauman M Qureshi

Acceleration statistics of inertial particles in turbulent flow

come

Introduction

Turbulent transport of material inclusions plays an important role in many natural and industrial processes. In marine ecosystem for instance, interactions between the turbulent sea and the gametes of marine animals is determinant for the efficiency of the reproduction and the spreading of the species (1). Industrial stakes concern mixing and combustion, while environmental issues such as pollutants dispersion (2) and pollenization (3) are more than ever crucial. In spite of decades of active theoretical, numerical and experimenal research, being able to accurately model and predict the dynamics of dispersed inclusions transported by a turbulent flow, still remains a challenge with important scientific, environmental and economical issues.

One critical and difficult point is to find a model which would correctly describe particles dynamics over a wide range of sizes and densities. The dynamics of particles transported by a turbulent flow is indeed known to be affected by size and density effects. If particles are neutrally buoyant and small (namely with their diameter D much smaller than the smallest turbulent eddies, at the energy dissipation scale η of the flow), they behave as fluid tracers and their dynamics reflects fluid particles dynamics. This property is commonly used to characterize single phase flows from tracer particles imaging techniques [START_REF] Mei | [END_REF] (such as Particle Image Velocimetry, Laser Doppler Velocimetry, Particle Tracking Velocimetry, etc.). However, when particles density is larger or smaller than the surrounding fluid and/or when particles size becomes comparable to turbulent eddies', their dynamics deviates from that of fluid particles and tends to be affected by so called inertial effects. Among them some can be qualitatively described in terms of particles interaction with turbulent eddies. For instance, centrifugal forces are generally expected to cluster heavier particles in low vorticity regions (and lighter in high vorticity ones), an effect known as preferential concentration (6). However, from a quantitative point of view no reliable model has emerged yet to describe and predict accurately the statistical properties of particles advected by a turbulent flow. For instance we are unable today to ν 0 ν 0 + δν Emitter excitation emitter Fig. 2 Turbulence is generated downstream a grid in a wind tunnel. The measurement volume is located 2.75m downstream the grid, in a region where turbulence is fully developped, homogeneous and isotropic. Particles are injected individually at the grid with a bubble nozzle and tracked individually by Doppler velocimetry. An ultrasonic plane wave of frequency ν0 is emitted by a transducer and a receiver records the wave scattered by a moving particle with velocity v in the measurement volume (which is the intersection of the emmitting and receiving acoustical beams, represented by the light cloroed tubes on the sketch). The component v of the particle velocity along the scattering vector is directly given by the Doppler shift δν of the frequency of the recorded scattered wave. In the present experiment, transuducers are arranged in order to measure the sreamwise component vz of particles velocity.

predict correctly the dynamics of water droplets in a cloud (7; 8), what considerably limits our understanding of rain mechanisms. Actually, even writing an appropriate equation of motion for a particle transported by a turbulent flow remains a theoretical challenge which has only been approached in some limit cases, assuming generally point like particles (9; 10; 11; 12; 13; 14; 15). The range of validity of such models for real particles, with finite size and finite density, as well as the minimal forcing terms for a model to be pertinent remain unclear. In this context, the study of particles Lagrangian acceleration, which directly reflects the turbulent forcing exerted on the particles, has been particularly active in the past decade (16; 17; 18; 19; 20; 21; 22). It is now well known that fluid particles exhibit highly nongaussian acceleration probability density function (PDF) with broad probability tails at high acceleration events (16). Direct numerical simulations in the limit of highly inertial point particles suggest that acceleration PDF tends to narrow and to gaussianize as particles inertia increases. On the experimental side, studies in the limit of very small (D ≪ η) and highly inertial particles (10 3 denser than the carrier flow) seem to confirm this trend (18; 19). However, recent measurements with finite size (D η) weakly inertial particles (up to 2.5 times denser than the carrier flow) do not show any significant change of acceleration PDF with inertia (21; 22).

In the present article, we report an exhaustive experimental investigation of material particles acceleration in a turbulent air flow, over a wide range of sizes and densities. In particular we consider the so far unexplored regime of finite size (D > η) and highly inertial particles (much denser than the carrier fluid). We consider a turbulent carrier flow generated downstream a grid in a wind tunnel experiment.

The article is organized as follows : in section 2 we present the particles parameter space, which describes the range of particles size and density we have effectively explored ; in section 3 we describe the wind tunnel setup and the characteristic scales of the carrier turbulent field ; in section 4 we present the results obtained concerning particles acceleration statistics ; we finally propose a discussion of these results in section 5 before concluding in section 6.

Particles Parameter Space

The aim of the present work is to explore acceleration statistics of inertial particles over a wide range of sizes and densities. In order to do so, we have developped a versatile particle generator which produces in situ adjustable spherical soap bubbles. Their density can be adjusted from neutrally buoyant to about 70 times denser than air. Neutrally buoyant particles are obtained by inflating the bubbles with Helium in order to compensate the weight of the soap film. Heavier particles are inflated with air, and their density is essentially controled by the thickness of the soap film. In all cases the bubbles Weber number remains extremely small, so that they do not deform and behave as rigid spheres. The seeding density is extremely low (particles are injected individually) so that particles can be considered as isolated and do not backreact on the carrier flow. Particles are therefore only characterized by two parameters : the ratio φ of their diameter D to the dissipative scale of the flow (φ = D/η) and the ratio Γ of their density ρ p to the carrier fluid (air in our case) density ρ air (Γ = ρ p /ρ air ). Figure 1 summarizes all the particle classes (in the (φ, Γ ) parameter space) that we have investigated. As far as we know this represents the most exhaustive exploration over such a wide range of particles sizes and densities.

Experimental Setup

Our experiment runs in a large wind tunnel (figure 2) with a measurement section of 0.75 m × 0.75 m where the turbulence is generated downstream a grid with a mesh size of 6 cm and reproduces almost ideal isotropic turbulence. The results reported here were obtained with a mean velocity of the fluid U = 15 m • s -1 and a turbulence level u rms /U ≃ 3%. The corresponding Reynolds number, based on Taylor microscale, is of the order of R λ = 160. The dissipation scale η = (ν 3 /ǫ) 1/4 is 240 µm (where ν is the kinematic viscosity of air and ǫ the tur-bulent energy dissipation rate per unit mass) and the energy injection scale L is 6 cm. The carrier turbulent field has been characterized using classical hotwire anemometry. In particular, using a Taylor hypothesis, this gives access to the Eulerian correlation function and to the turbulent velocity gradients from which we estimate the integral scale L and the dissipation rate ǫ respectively. Particles are individually tracked using 1D Lagrangian acoustic Doppler velocimetry (see figure 2), where the instantaneous Doppler shift is obtained by a maximum of likelyhood parametric algorithm (24; 25; 26). We measure the streamwise velocity component v z of the particles as they are tracked along their trajectories. The streamwiase acceleration component a z is obtained by differentiating the velocity using a convolution with a differentiated gaussian kernel (27). Each particle is tracked during approximately 50 ms, which corresponds to several dissipation time scales τ η = (ν/ǫ) 1/2 ≃ 3.8 ms. For each point in the (φ, Γ ) parameter space we record about 4000 tracks at a samplimg rate of 32768 Hz, giving more than 10 6 data points per set. ), for all studied particles. Remarkably we find that all the PDFs almost collapse onto a single curve, indicating that, over the (φ, Γ ) range considered, normalized acceleration statistics depends significantly neither on particle size, nor on particle density. In particular, contrary to predictions from point particle models, we do not observe any trend to gaussianization, even for particles with Stokes number St (see caption of figure 1 for the definition of St) as large as 40 ; within statistical errorbars, we do not observe any systematic trend of acceleration flatness, which keeps a constant value F ≃ 8.3 with 10% standard deviation among the different particle classes. This result extends to the case of heavy particles the robustness of acceleration PDF which we have previously reported for neutrally buoyant particles [START_REF] Qureshi | [END_REF]. It is also qualitatively consistent with recent measurements, in water von Kármán flows with weakly inertial particles (28; 21; 22), although an unambiguous quantitative comparison with those results cannot be made due to experimental specificities (grid turbulence and von Kármán flows have very different large scale anisotropy and confinement characteristics which are known to affect particles Lagrangian dynamics (29; 30)). A quantitative comparison is however possible with recent measurements obtained by Z. Warhaft's group at Cornell University in a turbulent air flow with comparable characteristics to ours (both are windtunnel experiments with similar isotropy levels), although at a slightly higher Reynolds number (R λ ∼ 250). Using high speed optical tracking, they have measured acceleration statistics of sub-kolmogorov water droplets (φ ∼ 5×10 -2 ; Γ ∼ 1000 ; St ∼ 0.1), a regime of size which we cannot reach at present due to technical limitations of our bubble generator. We have superimposed on figure 3 the normalized acceleration PDF from their measurements (black dashed line). We find it to be almost undistinguishable from our measurements with larger particles. This suggests that acceleration of inertial particles as small as φ ∼ 5 × 10 -2 already exhibit the same robust statistical signature as finite size particles ; point particle models may therefore only apply to even smaller particles [START_REF] Ayyalasomayajula | Lagrangian Measurements of Fluid and Inertial Particles in Decaying Grid Generated Turbulence[END_REF].

Acceleration Statistics

For a deeper insight into specific effects associated to particles size and density, one has to investigate acceleration variance. Since the statistics of acceleration normalized to variance one is found essentially independent of particles size and density, an effect of those parameters can indeed only be expected to affect acceleration variance itself a 2 z . Figure 4 represents the true acceleration PDF (not normalized to variance one) for neutrally buoyant (Γ ∼ 1) and heavy (Γ ∼ 5) particles, with varying sizes. It appears that heavy particles have a much narrower and peaked PDF, indicating a global decrease of acceleration variance with increasing density. The spreading of the curves for a given density indicates that size also influences particles acceleration variance.

A closer analysis of acceleration variance shows a non-trivial dependence with size and density. We report in figure 5 the acceleration variance for all the measurements we have performed (in the following, we consider the dimensionless acceleration variance normalized according to Heisenberg-Yaglom's scaling :

A 0 (φ, Γ ) = a 2 z ǫ -3/2 ν 1/2
). The mapping of the (φ, Γ ) parameter space that we have been able to explore, allows us to infer a rough interpolation of the evolution of A 0 (φ, Γ ), represented by the surface in figure 5. Though only the Fig. 5 Acceleration variance for all particles studied in the (φ, Γ ) parameter space (dots). The surface represents a rough interpolation based on the available measurements (a biharmonic spline interpolation (31) has been used). The dot dashed lines materialize the interpolation along the best resolved constant φ-lines and Γ -lines. For the Γ = 1 set, the dot-dashed line coincide with a φ -2/3 decay for φ 15 (20; 16). coarse tendency of this interpolation is relevant, several important qualitative features can still be observed. If we consider the effect of an increasing density at a fixed particle size (along constant φ-lines), A 0 is always found to decrease and to saturate to a finite limit (noted a ∞ 0 (φ)) for the largest densities. This is better quantified in a 2D projection (figure 6). The φ ≃ 16.5 set of measurements (which is our most complete set of density effects at fixed size) shows that the evolution of acceleration variance with density exhibits two different regimes (see inset in figure 6): (i) for low densities A 0 (φ, Γ ) = a 0 (φ)Γ -α (a 0 (φ) corresponds to size effects for the neutrally buoyant case which we have previously studied in [START_REF] Qureshi | [END_REF]) with α ≃ 0.6 (ii) for large densities A 0 saturates to a finite limit, here a ∞ 0 (φ ≃ 16.5) ≃ 0.7 ; the transition between these two regimes occurs for a characteristic density ratio Γ * ∼ 10. Although we don't have as many systematic measurements for varying densities for other values of φ, the few available points are compatible with the existence of such two regimes (figure 6), with a size dependent saturation value a ∞ 0 (φ) and very likely a size dependent transition density ratio Γ * (φ).

If we focus now on size effects at fixed particle density (along constant Γ -lines), as seen on figure 5, the scenario is rather complex: depending on the density ratio Γ , A 0 can either decrease or increase with particles size. For neutrally buoyant particles (Γ = 1) larger than about φ ∼ 15, A 0 decreases monotically as a 0 (φ) ∼ φ -2/3 (20; 16). We have shown in a previous study [START_REF] Qureshi | [END_REF] that this is the expected scaling for inertial range sized particles when the main forcing simply comes from the spatial pressure differences of the unperturbed flow around 6 2D-Projection on the (Γ -A0) plane of measurements data points on figure 5, showing the evolution of acceleration variance with density ratio Γ for different particle sizes (φ ≃ 16.5 set (circles) is the best resolved). The inset shows the same data in a log-log plot. Errorbars are mostly due to experimental uncertainties in the determination of particles size and density.

the particle. As we move to larger density ratios we then observe a continuous transition toward a drastically changed size dependence where a ∞ 0 (φ) exhibit a sharp increase for sizes around 17 < φ < 19. Outside this transition region (i.e. for φ 17 and φ 19), a ∞ 0 doesn't exhibit significant dependence on φ (at least in the accessible range of sizes) as also seen on figure 6, where we have a ∞ 0 (13) ≃ a ∞ 0 (16.5) and a ∞ 0 (19) ≃ a ∞ 0 (21).

Discussion

Our measurements have important consequences in terms of the development of accurate models for the turbulent transport of finite sized inertial particles. The robustness of normalized acceleration PDF, regardless of particles size and density, and the non trivial size and density dependence of acceleration variance impose strong constraints on the statistical properties of the forcing terms to be included in the equation of motion of particles. For instance models based on Maxey & Riley equation (9; 10) for inertial point particles are contradictory with our observations as they predict a continuous trend of acceleration PDF to gaussianity as well as a monotonic decrease of acceleration variance (13; 21; 32) both mostly consequence of a filtering effect due to increasing particles response time as inertia (only parametrized in such models by a Stokes number) increases. Our findings therefore show that turbulent transport of finite sized inertial particles cannot be simply described in terms of Stokes number and filtering effects only. The concrete statistical constraints that we have identified give a first clear experimental diagnose of point-particle models limitations (already analyzed theoretically by Lumley in 1978 (33)), and of the requirement for density and finite size effects to be simultaneously and specifically modeled.

With this goal, finally, we briefly discuss a simple qualitative phenomenology for the observed trends of acceleration variance based on the idea that particles tend to reside longer in the quietest regions of the flow. This intuitive statement can be related to the tendency of inertial particles to preferentially concentrate in low vorticity and low acceleration regions of the carrier turbulent field along which they are then advected folowing a sweep-stick scenario (34; 35). In this context, the decrease of particles acceleration variance naturally results from the under-sampling of intense regions of the carrier flow. Then, a possible interpretation for the increase of acceleration variance with particle size observed for high density ratios can be that while small enough particles can indeed be expected to efficiently hide in the quietest regions of the flow, when particles become larger than the typical size L * of these regions, the sampling effect is damped as particles start experiencing again the influence of more active regions of the turbulent field. Though the existence of such a typical scale is still controversial, recent measurements of preferential concentration suggest that the quiet sticking regions might have a characteristic size L * in the range 10 -20η (36) consistent with the 17 φ 19 range for which we observe the sudden increase of a ∞ 0 (φ). Our measurements of inertial effects for finite size particles can therefore be consistently interpreted as a dominant role of sampling rather than filtering, contrary to the point particle case (13; 32). The dominant role of sampling is also consistent with the fact that velocity statistics of our particles (not shown here) are found identical to that of the carrier flow (obtained from classical hotwire anemometry), a feature also shown numerically in the context of sweep-stick mechanism (35) but which is at odds from usual predictions based for instance on the Tchen-Hinze theory or extensions of this theory [START_REF] Deutsch | Turbulence Modification in Multiphase Flow[END_REF].

Conclusion

To summarize, using a versatile material particle generator we have been able to explore the simultaneous influence of size and density on the turbulent transport of material particles. For fixed carrier flow conditions, acceleration statistics of finite size inertial particles are found very robust to size and density variations, the influence of which is mostly carried by acceleration variance only. In particular the shape of acceleration probability density function remains unchanged over the whole range of sizes and densities explored. Concerning acceleration variance, we find that, for heavy particles, finite size effects can be trivially extrapolated neither from the heavy point particle limit nor from the finite size neutrally buoyant case as both of these limits predict a monotonic decrease of acceleration variance with increasing inertia, contradictory with the trends measured for finite size heavy particles. Observed finite size and density effects cannot be accounted by simple filtering arguments only based on Stokes number effects as in the point particle case. A sampling scenario, in the spirit of sweep-stick mechanisms seems more adequate to possibly describe the simultaneous influence of density and size. We believe this should stimulate further experimental and numerical investigations of acceleration fields in turbulent flows as well as of inertial particles concentration fields. It is our hope that these measurements will contribute bridging experimental observations and developments of accurate models for the turbulent transport of particles.

Fig. 1

 1 Fig.1Particle classes considered in the present study, described in the (φ, Γ ) phase space. φ = D/η is the ratio of particles diameter to kolmogorov scale and Γ = ρp/ρ air is the particle to fluid density ratio. The countour lines indicate an estimation of the particles Stokes number St = τp/τD, where the respone time τp of the particle has been corrected for added mass and for finite Reynolds number effects according to Schiller and Nauman (4) and τD is the flow eddy turnover time at the scale of the particle diameter D.

Figure 3 2 z 1 / 2

 3212 Figure 3 represents acceleration PDFs normalized to variance one, (a z / a 2 z 1/2 ), for all studied particles. Remark-

1 Γ ~ 5 Fig. 4

 154 Fig. 4 Non normalized component acceleration PDF for Γ ∼ 1 (outer bundle, green tone) and Γ ∼ 5 (inner bundle, red tone) particles and various values of φ.

  Fig.

1/2) PDF

	φ	Γ						φ Γ
	12.5 1						16.8 12.6
	14.6 1						16.8 30
	16.7 1						12.4 47
	18.8 1						16.4 50
	20.8 1						19	52
	22.3 1						21	41
	25	1						16.8 65
	16.7 2.7
	13.5 6.34						0.05 1000
	15.3 4.67 16.7 4.58 18.5 5.9 20.8 4.23						(from [18]) Lognormal fit
	22.8 4.0
		4 √	3	»	1 -erf	"	ln(|x/ √ √ 3|)+2s 2 2s	«-	associ-

Fig. 3 Normalized component acceleration probability density function (PDF) of material particles transported in a turbulent air flow. Dashed line corresponds to the measurement by Ayyalasomayajula et al. (18) for water droplets (with size φ ∼ 5 × 10 -2 and Γ ∼ 1000). To help the comparison with previous and future studies the dot-dashed line shows a fit by the relation P(x) = e 3s 2 /2 ated to a lognormal distribution of the acceleration amplitude (23; 20) ; best fit is found for s ∼ 0.62, corresponding to a distribution flatness F = 9 5 e 4s 2 ∼ 8.3.

Acknowledgements We deeply acknowledge E. Calzavarini, J.-F. Pinton, R. Volk, and Z. Warhaft for fruitful discussions.