A P Burger
email: apburger@sun.ac.za

J H Van Vuuren

Avoidance colourings for small nonclassical Ramsey numbers

Keywords: Mixed Ramsey number, nonclassical Ramsey number, extremal colouring

The irredundant Ramsey number s = s(m, n) [upper domination Ramsey number u = u(m, n), respectively] is the smallest natural number s [u, respectively] such that in any red-blue edge colouring (R, B) of the complete graph of order s [u, respectively], it holds that

where Γ and IR denote respectively the upper domination number and the irredundance number of a graph. Furthermore, the mixed irredundant Ramsey number

where β denotes the independent domination number of a graph. These four classes of non-classical Ramsey numbers have previously been studied in the literature. In this paper we introduce a new Ramsey number w = w(m, n), called the irredundant-domination Ramsey number, which is the smallest natural number w such that in any red-blue edge colouring (R, B) of the complete graph of order w, it holds that IR(B) ≥ m or Γ(R) ≥ n. A computer search is employed to determine complete sets of avoidance colourings of small order for these five classes of nonclassical Ramsey numbers. In the process the fifteen previously unknown Ramsey numbers t(4, 4) = 14, t(6, 3) = 17, u(4, 4) = 13, v(4, 3) = 8, v(4, 4) = 14, v(5, 3) = 13, v(6, 3) = 17, w(3, 3) = 6, w(3, 4) = w(4, 3) = 8, w(4, 4) = 13, w(3, 5) = w(5, 3) = 12 and w(3, 6) = w(6, 3) = 15 are established.

Introduction

A bi-colouring of the edges of a graph, using the colours red and blue, is called a red-blue edge colouring of the graph. If R and B are the subgraphs induced by respectively the red and the blue edges of such a colouring, the colouring is denoted by the ordered pair (R, B), and R is referred to as the red subgraph, while B is called the blue subgraph. For any natural numbers m and n, the (classical) Ramsey number r = r(m, n) is the smallest natural number r such that, for any red-blue edge colouring (R, B) of the complete graph K r on r vertices, it holds that either K m ⊆ R or K n ⊆ B, or perhaps both.

The notion of a Ramsey number may also be defined in terms of independent sets in graphs. A subset I of vertices of a graph G is said to be independent if no two vertices in I are adjacent in G. The cardinality of a largest independent set of G is denoted by β(G), called the independent domination number of G. If, for some red-blue edge colouring (R, B), it holds that K m ⊆ R, then there is an independent set of order m in B, and hence β(B) ≥ m. Similarly, K n ⊆ B implies that β(R) ≥ n. The classical Ramsey number r(m, n) may therefore be redefined as the smallest natural number r such that in any red-blue edge colouring (R, B) of the complete graph K r of order r, it holds that β(B) ≥ m or β(R) ≥ n (or perhaps both). For this reason the classical Ramsey number r(m, n) is often referred to as the independent Ramsey number. This definition has been generalised in many ways. Four generalisations that arose during the period 1989-1992 involve the so-called upper domination number and the irredundance number of a graph -parameters that are closely related to the independent domination number of a graph.

A subset D of the vertices of a graph G is said to be dominating if every vertex v of G is an element of D or is adjacent in G to an element of D. A dominating set D of G is said to be minimal if no proper subset of D is a dominating set in G. The cardinality of a largest minimal dominating set of G is denoted by Γ(G), called the upper domination number of G.

The closed neighbourhood of a graph vertex v, denoted by N [v], is defined as the subset of all vertices of G that are adjacent to v in G, together with the vertex v itself. The closed neighbourhood of a set of vertices S = {v 1 , . . . , v m } in G, denoted by N [S], is simply defined as

N [S] = ∪ m i=1 N [v i ]. The set of private neighbours of a vertex v ∈ V G with respect to some subset S ⊂ V G is defined as PN(v, S) = N [v]\N [S\{v}]. A subset X of the vertices of G is said to be irredundant if every vertex v ∈ X has at least one private neighbour in G with respect to X (that is, if PN(v, X ) = ∅ for all v ∈ X ). Finally, the cardinality of a largest maximal irredundant set of G is denoted by IR(G), called the irredundance number of G. It holds for any graph G that β(G) ≤ Γ(G) ≤ IR(G). (1)
This result dates back to 1978 and is due to Cockayne et al. [START_REF] Cockayne | Properties of hereditary hypergrphs and middel graphs[END_REF]. The following four so-called nonclassical Ramsey numbers have previously been studied in the literature:

The irredundant Ramsey number s = s(m, n) is the smallest natural number s such that in any red-blue edge colouring (R, B) of the complete graph K s of order s, it holds that IR(B) ≥ m or IR(R) ≥ n (or perhaps both). This definition is due to Brewster et al. [START_REF] Brewster | Irredundant Ramsey numbers for graphs[END_REF].

The mixed irredundant Ramsey number t = t(m, n) is the smallest natural number t such that in any red-blue edge colouring (R, B) of the complete graph K t of order t, it holds that IR(B) ≥ m or β(R) ≥ n (or perhaps both). This definition is due to Cockayne et al. [START_REF] Cockayne | Mixed Ramsey numbers and irredundant Turán numbers for graphs[END_REF].

The upper domination Ramsey number u = u(m, n) is the smallest natural number u such that in any red-blue edge colouring (R, B) of the complete graph K u of order u, it holds that Γ(B) ≥ m or Γ(R) ≥ n (or perhaps both). This definition is due to Oellermann and Shreve [START_REF] Oellermann | [END_REF].

The mixed domination Ramsey number v = v(m, n) is the smallest natural number v such that in any red-blue edge colouring (R, B) of the complete graph K v of order v, it holds that Γ(B) ≥ m or β(R) ≥ n (or perhaps both). This definition is also due to Oellermann and Shreve [START_REF] Oellermann | [END_REF].

Finally, the following Ramsey number seems not to have been considered previously:

The irredundant-domination Ramsey number w = w(m, n) is the smallest natural number w such that in any red-blue edge colouring (R, B) of the complete graph K w of order w, it holds that IR(B) ≥ m or Γ(R) ≥ n (or perhaps both).

The arguments of the classical, irredundant and upper domination Ramsey numbers may be interchanged without altering the values of these numbers, i.e. r(m, n) = r(n, m), s(m, n) = s(n, m) and u(m, n) = u(n, m) for any integers m, n ≥ 2. However, in the case of the mixed Ramsey numbers t(m, n), v(m, n) and w(m, n), the arguments m and n do not necessarily commute, i.e. t(m, n) = t(n, m), v(m, n) = v(n, m) and w(m, n) = w(n, m) in general. Furthermore, the Ramsey numbers defined above are related to each other and to the classical Ramsey number r(m, n) by means of the inequality chains

s(m, n) ≤ w(m, n) ≤ u(m, n) t(m, n) ≤ v(m, n) ≤ r(m, n), (2)
which are easily shown to hold for all m, n ≥ 2 in view of (1

r(m, n) ≤ r(m -1, n) + r(m, n -1) (3) s(m, n) ≤ s(m -1, n) + s(m, n -1) (4) and t(m, n) ≤ t(m -1, n) + t(m, n -1) (5)
hold, and any one of these inequalities is strict if both terms on the right hand side are even.

To the best knowledge of the authors, the numbers listed in For any integer q < s(m, n), a red-blue edge colouring (R, B) of the complete graph K q for which

v(2, n) v(n, 2) v(3, 3) v(3, 4) v(4, 3) v(3, 5) v(5, 3) v(3, 6) v(6, 3) v(4,
IR(B) < m and IR(R) < n (6)
is called an avoidance s(m, n)-colouring. The two inequalities in ( 6) are called avoidance conditions associated with the Ramsey number s(m, n). Furthermore, an avoidance s(m, n)-colouring is said to be

extremal if q = s(m, n) -1. (Extremal) avoidance t(m, n)-, u(m, n)-, v(m, n)-and w(m, n)-colourings
are defined similarly. The degree restrictions below hold for any avoidance s(m, n)-colouring and are due to Hattingh [START_REF] Hattingh | On irredundant Ramsey numbers for graphs[END_REF].

Theorem 1 Let m, n > 2 be integers. Then, ∆(R) < s(m -1, n) and ∆(B) < s(m, n -1) in any avoidance s(m, n)-colouring (R, B).
The following corollary therefore holds by [START_REF] Brewster | The irredundant Ramsey number s(3, 6)[END_REF].

Corollary 1 Let m, n ≥ 2 be integers and let x ∈ {s, t, u, v, w} be a nonclassical Ramsey number. Then,

∆(R) < x(m -1, n) and ∆(B) < x(m, n -1) in any avoidance x(m, n)-colouring (R, B).
Finally, the following useful corollary immediately follows from Corollary 1.

Corollary 2 Let m, n ≥ 2 be integers and let x ∈ {s, t, u, v, w} be a nonclassical Ramsey number. Then, δ(R) ≥ p -x(m, n -1) and δ(B) ≥ p -x(m -1, n) in any avoidance x(m, n)-colouring (R, B) of the complete graph of order p.

The objective in this paper is to determine the values of the outstanding nonclassical Ramsey numbers in Table 1 and to describe all the extremal avoidance colourings related to the Ramsey numbers in the table. The paper is organised as follows. We show analytically in §2 that unique avoidance colourings are associated with each of the Ramsey numbers x(2, n), x(n, 2) and x [START_REF] Chen | The irredundant Ramsey number s(3, 7)[END_REF][START_REF] Chen | The irredundant Ramsey number s(3, 7)[END_REF], where x ∈ {s, t, u, v, w}. In §3 we then describe a recursive algorithmic procedure for computing the values of the parameters β(G), Γ(G) and IR(G) of a small graph G. This procedure is applied in §4 to search for (extremal) avoidance colourings associated with small Ramsey numbers. In §5 it is shown that the search space may be reduced by considering only complete sets of avoidance colourings for the classical Ramsey number r(m, n)this reduction renders the search procedure of §4 feasible for uncovering (extremal) avoidance colourings associated with larger Ramsey numbers. We close, in §6, with a summary of the contributions in this paper.

2 The Ramsey numbers x(2, n) and x(3, 3), x ∈ {s, t, u, v, w} It is easy to establish the extremal avoidance colourings associated with the Ramsey numbers x(2, n) = n and x(n, 2) = n, where x ∈ {s, t, u, v, w}.

Theorem 2 The red-blue edge colouring (R, B) of the complete graph K n-1 such that R ∼ = K n-1 and B ∼ = K n-1 is the only extremal avoidance colouring associated with each of the Ramsey numbers x(2, n), while the reverse edge bi-colouring (B, R) of K n-1 is the only extremal avoidance colouring associated with each of the Ramsey numbers x(n, 2), where x ∈ {s, t, u, v, w}.

Proof: Let C 1 = (R, B) be the red-blue edge colouring of the complete graph K n-1 for which R ∼ = K n-1 and B ∼ = K n-1 . Then clearly β(B) = Γ(B) = IR(B) = 1 < 2 and β(R) = Γ(R) = IR(R) = n -1 < n,
so that C 1 is indeed an extremal avoidance colouring associated with any one of the Ramsey numbers x(2, n), x ∈ {s, t, u, v, w}. Similarly, for the reverse red-blue edge colouring

C 1 of K n-1 (i.e. where R ∼ = K n-1 and B ∼ = K n-1 ) it holds that β(B) = Γ(B) = IR(B) = n -1 < n and β(R) = Γ(R) = IR(R) = 1 < 2,
so that C 1 is indeed an extremal avoidance colouring associated with any one of the Ramsey numbers x(n, 2), x ∈ {s, t, u, v, w}.

Conversely, let C 2 = (R , B ) be an extremal avoidance colouring associated with any one of the Ramsey numbers x(2, n), x ∈ {s, t, u, v, w}. Then one of the inequalities β(B ) < 2, Γ(B ) < 2 or IR(B ) < 2 must hold. In any one of these cases B must therefore be complete (since the omission of an edge in B would imply the existence of an independent set, a minimal dominating set and an irredundant set of cardinality at least 2 in B ), and hence

C 2 = C 1 . Similarly, if C 3 = (R , B
) is an extremal avoidance colouring associated with any one of the Ramsey numbers x(n, 2), x ∈ {s, t, u, v, w}, then one of the inequalities β(R ) < 2, Γ(R ) < 2 or IR(R ) < 2 must hold, in which case R must again be complete for the same reason as above. Hence

C 3 = C 1 .
2

It is also possible to show that a unique extremal avoidance colouring is associated with each of the Ramsey numbers x(3, 3), x ∈ {s, t, u, v, w}.

(R) = Γ(R) = IR(R) = 2 < 3, so that C 1
is indeed an extremal avoidance colouring associated with any one of the Ramsey numbers x(3, 3) = 6, x ∈ {s, t, u, v, w}.

Conversely, let C 2 = (R , B ) be any extremal avoidance colouring associated with any one of the Ramsey numbers x(3, 3) = 6, x ∈ {s, t, u, v, w}. It follows by Corollaries 1 and 2 that every vertex in R and every vertex in B has degree 2. But then R and B are both cycles, in which case they must both be isomorphic to C 5 , since R and B are both of order 5. 2

3 Computing the graph parameters β, Γ and IR

In this section we describe our recursive algorithmic approach towards computing the parameters β(G), Γ(G) and IR(G) for a given graph G in order to compute avoidance colourings for the Ramsey numbers in Table 1. Although the discussion in this section is mainly for the parameter IR(G), the other two graph parameters were computed in a similar manner, as we outline at the end of the section.

A pseudocode listing of our recursive Boolean approach towards determining whether or not a given subset of vertices S of a labelled graph G with vertex set {v 0 , . . . , v n-1 } may be augmented (i.e. enlarged) and still remain irredundant in G is given in Algorithm 1. The algorithm takes the set S as input and produces the Boolean value True as output if an irredundant set S ∪ T in G of cardinality Ψ can be found such that the index of every vertex in T is larger than the largest index of any vertex in S, or False otherwise, where Ψ is any valid upper bound on the parameter IR(G). The algorithm generates a branching-search tree by branching on the inclusion of all possible vertices v i with indices i larger than the largest vertex index in S, calling itself with the set S ∪ {v i } as input (instead of the original set S) at each branch.

Algorithm 1: IRSetQ(S)

Input : A subset S ⊆ {v 0 , . . . , v n-1 } of the vertex set of a labelled graph G of order n. Output: True if there is an irredundant set S ∪ T in G of cardinality Ψ such that the index of every vertex in T is larger than the largest index of any vertex in S, or False otherwise.

if S is not irredundant then return False; The root of the search tree is generated with a call to Algorithm 1 in which S = ∅. This call occurs in Step 2 of Algorithm 2. The input to Algorithm 2 is the adjacency matrix A(G) of the graph G as well as a user-specified upper bound Ψ on the value of IR(G); both these input parameters are defined globally outside the scope of the various calls to the recursive algorithm IRSetQ(S) and are never altered during construction of the search tree. Algorithm 2 yields as output the exact value of IR(G), employing a lower bound on the value of IR(G), which is initially taken as zero (Step 1 of Algorithm 2). This lower bound is updated globally as larger and larger irredundant sets are encountered in the search tree.

Computation of the parameter β(G) occurs exactly as in the case of IR(G), the only change being replacement of the requirement that S "is not irredundant" in Step 1 of Algorithm 1 by the requirement that S "is not independent". However, care should be taken with the computation of the parameter Γ(G), since it is not the cardinality of a largest dominating set in G, but of a largest minimal dominating set in G. However, it is well known that a dominating set is minimal if and only if it is dominating and irredundant [START_REF] Haynes | Fundamentals of domination in graphs[END_REF]Proposition 3.8]. Hence the computation of the parameter Γ(G) proceeds exactly as in the case of IR(G), the only changes being replacement of the requirement that "|S| = Ψ" in Step 2 of Algorithm 1 by the requirement that "|S| = Ψ and S is dominating," and replacement of the requirement that "|S| > ψ" in Step 3 by the requirement that "|S| > ψ and S is dominating."

Ramsey numbers not exceeding the value 9

A natural, brute-force approach towards determining a complete set of extremal avoidance colourings of a small Ramsey number x(m, n) in Table 1, where x ∈ {s, t, u, v, w}, is to step through each of the nonisomorphic unlabelled graphs of order x(m, n) -1 and to test, for each possible graph R and its graph complement B, whether or not both avoidance conditions associated with the Ramsey number x(m, n) are satisfied by the edge colouring (R, B). Such a brute-force approach is facilitated by repositories of the various non-isomorphic graph structures of small orders, such as the one on McKay's website [START_REF] Mckay | Graphs[END_REF]. By adopting such a brute-force search involving all 1 044 graphs of order 7 it is possible to prove the following theorem.

Theorem 4 v(4, 3) = 8.
Taking the nine graphs E 1 -E 9 in Figure 1(a)-(i) as blue subgraphs produces complete sets of extremal avoidance v(4, 3)-colourings and extremal avoidance t(4, 3)-colourings. The above exhaustive search also shows that taking the eight graphs E 1 -E 8 in Figure 1(a)-(h) as red subgraphs produces complete sets of extremal avoidance s(3, 4)-colourings, extremal avoidance u(3, 4)-colourings and extremal avoidance w(3, 4)-colourings. However, taking the eight graphs E 1 -E 8 in Figure 1(a)-(h) as blue subgraphs produces a complete set of extremal avoidance w(4, 3)-colourings. We also immediately have the following corollary from Theorem 4.

(a) E 1 (b) E 2 (c) E 3 (d) E 4 (e) E 5 (f) E 6 (g) E 7 (h) E 8 (i) E 9 (j) E 10 (k) E 11 (l) E 12
Corollary 3 v(5, 3) = 13.

Proof: Suppose that an avoidance v(5, 3)-colouring (R, B) of K 13 exists. Then it follows by Theorem 4 and Corollaries 1-2 that δ(R) ≥ 13 -v(5, 2) = 8 but that ∆(R) < v(4, 3) = 8. This contradiction shows that no avoidance v(5, 3)-colouring of K 13 exists and hence that v(5, 3) ≤ 13, yielding the desired result by Table 1. 2

Finally, an exhaustive search involving all 12 346 graphs of order 8 shows that taking the two graphs E 10 and E 11 in Figure 1(j)-(k) as red subgraphs produces complete sets of extremal avoidance t(3, 4)colourings and extremal avoidance v(3, 4)-colourings, while it is known that taking the three graphs E 10 -E 12 in Figure 1(j)-(l) as red subgraphs produces a complete set of extremal avoidance r(3, 4)-colourings [START_REF] Mckay | Graphs[END_REF].

Unfortunately the brute-force search approach described above is only feasible for small Ramsey numbers. In fact, we were only able to implement the brute-force search approach described above for cases where the relevant Ramsey number does not exceed the value 9, in view of the rapid growth of the number of non-isomorphic graphs of order n as n increases. A reduced search space is therefore required in order to find a complete set of extremal avoidance colourings for Ramsey numbers larger than 9.

We close this section by remarking that although the brute-force search approach considered here is very primitive and certainly not interesting of its own accord, it is nevertheless a useful validation mechanism for results uncovered by other search techniques.

Computing avoidance colourings from the classical case

A search technique capable of finding complete sets of avoidance colourings for larger Ramsey numbers stems from the following result which states that avoidance colourings are transferred from left to right between the Ramsey numbers in the inequality chains [START_REF] Brewster | The irredundant Ramsey number s(3, 6)[END_REF].

Theorem 5 Let m, n > 2 be integers, and let x(m, n) and y(m, n) be any two Ramsey numbers in (2) satisfying x(m, n) ≤ y(m, n). Then any avoidance x(m, n)-colouring is also an avoidance y(m, n)colouring.

Proof: Let (R, B) be an avoidance x(m, n)-colouring. Then ξ x (B) < m and ζ x (R) < n, where ξ x and ζ x are the parameters in (1) that are relevant to the Ramsey number x(m, n

). Since x(m, n) ≤ y(m, n) in (2), it follows that ξ y (B) ≤ ξ x (B) and ζ y (B) ≤ ζ x (B) in (1), so that (R, B) is also an avoidance y(m, n)-colouring. 2
The significance of Theorem 5 is that we do not have to consider all possible colourings, but rather only those for the classical Ramsey number r(m, n) when seeking avoidance colourings for the nonclassical numbers s(m, n), t(m, n), u(m, n), v(m, n) or w(m, n) by virtue of the inequality chains [START_REF] Brewster | The irredundant Ramsey number s(3, 6)[END_REF]. McKay [START_REF] Mckay | Ramsey graphs[END_REF] provides complete sets of avoidance colourings of all orders p < r(m, n) for the small classical Ramsey numbers r(3, 3) = 6, r(3, 4) = 9, r(3, 5) = 14, r(3, 6) = 18 and r(4, 4) = 18. By considering each of these avoidance colourings and testing via the algorithmic approach described in §3 in which cases the avoidance conditions associated with the nonclassical Ramsey numbers are satisfied, we were able to establish the cardinalities of complete sets of avoidance colourings shown in Tables 34. The values in the columns labelled "r(m, n)" in Tables 34(i.e. the cardinalities of complete sets of extremal avoidance colourings for the classical Ramsey numbers) are not our results; they are due to McKay [START_REF] Mckay | Ramsey graphs[END_REF], but we reproduce these values here for completeness. We also verified that our computation approach yields the same cardinalities as those reported by McKay for small orders. As final verification mechanism we ensured that the same (extremal) avoidance colourings were obtained for the Ramsey numbers r(m, n), s(m, n) and t(m, n) where m = n when interchanging the values of m and n. By considering the zero-entries in these tables, the following two new, off-diagonal Ramsey numbers are established. Theorem 6 t(6, 3) = v(6, 3) = 17.

p s(3, 3) w(3, 3) u(3, 3) t(3, 3) v(3, 3) r(3, 3) 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 2 2 2 2 2 2 4 3 3 3 3 3 3 5 1 1 1 1 1 1 p s(3, 4) w(3, 4) u(3, 4) t(3, 4) v(3, 4) r(3, 4) w(4, 3) t(4, 3) v(4, 3) 1 1 1 1 1 1 1 1 1 1 2 2 2 2
In addition, the following four new, diagonal Ramsey numbers are established in a similar fashion.

Theorem 7 u(4, 4) = w(4, 4) = 13 and t(4, 4) = v(4, 4) = 14.

Taking the six graphs F 1 -F 6 in Figure 2(a)-(f) as red subgraphs produces complete sets of extremal avoidance v(3, 5)-colourings and extremal avoidance t(3, 5)-colourings. Of these graphs F 6 as red (blue, respectively) subgraph produces the only extremal avoidance s(3, 5)-colouring, extremal avoidance u(3, 5)-colouring and extremal avoidance w(3, 5)-colouring (extremal avoidance w(5, 3)-colouring, respectively). Furthermore, taking the graph F 7 in Figure 2(g) as blue subgraph produces the only extremal avoidance t(5, 3)-colouring and the only extremal avoidance v(5, 3)-colouring. There are 415 extremal avoidance s(4, 4)-, u(4, 4)and w(4, 4)-colourings; these are too numerous to show here, but taking the graph F 8 in Figure 2(h) as red subgraph produces the extremal avoidance colouring with the smallest number of red edges in all three cases (while the complement of F 8 as red subgraph produces the extremal avoidance colouring with the smallest number of blue edges in all three cases). However, the adjacency matrices of all 415 extremal avoidance s(4, 4)-, u(4, 4)and w(4, 4)-colourings are available online [START_REF] Van Vuuren | Repositories[END_REF].

(a) F 1 (b) F 2 (c) F 3 (d) F 4 (e) F 5 (f) F 6 (g) F 7 (h) F 8
It is well known that taking the graph G 1 in Figure 3(a) as red subgraph produces the only extremal avoidance r(3, 5)-colouring [START_REF] Mckay | Ramsey graphs[END_REF]. Furthermore, taking the eight graphs G 2 -G 9 in Figure 3 In addition, taking the two graphs H 1 -H 2 in Figure 4(a)-(b) as blue subgraphs produces complete sets of extremal avoidance t(6, 3)and v(6, 3)-colourings. It is known that there are seven extremal avoidance r(3, 6)-colourings; these colourings are obtained by taking the graphs H 3 -H 9 in Figure 4(c)-(i) as red subgraphs. Finally, it is also well known that taking the graph H 10 in Figure 4(j) as red subgraph produces the only extremal avoidance r(4, 4)-colouring [START_REF] Mckay | Ramsey graphs[END_REF].

Conclusion

In this paper we determined the values of all the outstanding nonclassical Ramsey numbers in Table 1 and described all the extremal avoidance colourings related to the Ramsey numbers in the table, save for the Ramsey number s(3, 7). The extremal avoidance colourings of these Ramsey numbers are summarised in Table 5 and were computed from the avoidance colourings of the corresponding classical Ramsey numbers, which are available online [START_REF] Mckay | Ramsey graphs[END_REF]. The reason for not computing the extremal avoidance s(3, 7)colourings is that the corresponding colourings are not available for the corresponding classical Ramsey number r(3, 7).

Theorem 3

 3 The red-blue edge colouring (R, B) of the complete graph K 5 of order 5 for which R ∼ = C 5 and B ∼ = C 5 is the only extremal avoidance colouring associated with each of the Ramsey numbers s(3, 3) = t(3, 3) = u(3, 3) = v(3, 3) = w(3, 3) = 6. Proof: Let C 1 = (R, B) be the red-blue edge colouring of the complete graph K 5 for which R ∼ = C 5 and B ∼ = C 5 . Then clearly β(B) = Γ(B) = IR(B) = 2 < 3 and β

1 else 3 R 4 for all v ∈ R do 5 if 8 Algorithm 2 : 1 if 2 else return ψ; 3

 134582123 if |S| = Ψ then return True; 2 else if |S| > ψ then ψ ← |S|; ← list of vertices in G with indices larger than the largest vertex index in S; IRSetQ(S ∪ {v}) then return True; IR(A(G), Ψ) Input : The adjacency matrix A(G) of a labelled graph G of order n with vertex set {v 0 , . . . , v n-1 }, and an upper bound IR(G) ≤ Ψ. Output: The cardinality of a largest irredundant set in G. ψ ← 0; IRSetQ(∅) then return Ψ;

Fig. 1 :

 1 Fig. 1: Extremal avoidance graphs of orders 7 and 8.

Fig. 2 :

 2 Fig. 2: Extremal avoidance graphs of orders 11 and 12.

  (b)-(i) as red subgraphs produces complete sets of extremal avoidance t(4, 4)-colourings and extremal avoidance v(4, 4)-colourings. There are 34 extremal avoidance t(3, 6)-colourings; these are too numerous to show here, but taking the graph G 15 in Figure3(n) as red subgraph produces the extremal avoidance t(3, 6)colouring with the smallest number of red edges, while taking the graph G 16 in Figure3(o) as red subgraph produces the extremal avoidance t(3, 6)-colouring with the smallest number of blue edges. The adjacency matrices of all 34 extremal avoidance s(3, 6)-colourings are, however, available online[START_REF] Van Vuuren | Repositories[END_REF]. There are 37 extremal avoidance v(3, 6)-colourings, namely all 34 extremal avoidance s(3, 6)-colourings together with the three colourings obtained by taking the graphs G 10 -G 12 in Figure3(j)-(l) as red subgraphs. Furthermore, taking the two graphs G 13 -G 14 in Figure3(m)-(n) as red subgraphs [blue subgraphs, respectively] produces complete sets of extremal avoidance t(3, 6)-, u(3, 6)and w(3, 6)-colourings [extremal avoidance w(6, 3)-colourings, respectively].

G 15 Fig. 3 :

 153 Fig. 3: Extremal avoidance graphs of orders 13 and 14.

(

Fig. 4 :

 4 Fig. 4: Extremal avoidance graphs of orders 16 and 17.

  Table 1 are the only known nonclassical Ramsey numbers and the bounds listed in the table are the best currently available. Using the inequality chains (2) it is possible to derive the values of and bounds on the Ramsey numbers w(m, n) shown in Table 2 from the corresponding Ramsey number values in Table 1.

		s(2, n) s(3, 3) s(3, 4) s(3, 5) s(3, 6) s(3, 7) s(4, 4)
		n	6 a	8 a	12 a	15 b	18 c	13 d
	t(2, n) t(n, 2) t(3, 3) t(3, 4) t(4, 3) t(3, 5) t(5, 3) t(3, 6)	t(6, 3)	t(4, 4)
	n	n	6 e	9 e	8 e	12 e	13 e	15 f	15 : 18 g 13 : 17 g
		u(2, n) u(3, 3) u(3, 4) u(3, 5) u(3, 6) u(3, 7)	u(4, 4)
		n	6 h	8 h	12 h		15 h	18 : 22 g 13 : 15 h

  Cardinalities of complete sets of avoidance colourings of order p for small Ramsey numbers. Cardinalities of complete sets of extremal avoidance colourings are underlined.Tab. 4: Cardinalities of complete sets of avoidance colourings of order p for small Ramsey numbers (continued). Cardinalities of complete sets of extremal avoidance colourings are underlined.

	2 3 6 9 14 8 2 s(3, 5) w(3, 5) u(3, 5) t(3, 5) v(3, 5) r(3, 5) w(5, 3) t(5, 3) v(5, 3) 2 2 2 2 2 3 3 3 3 3 3 3 3 6 6 6 6 6 6 6 6 9 9 9 9 9 9 9 9 14 14 14 14 15 14 15 15 8 8 8 8 9 8 9 9 0 0 0 2 3 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 7 7 7 7 7 7 7 7 7 13 13 13 13 13 13 13 13 13 31 31 31 31 31 32 31 32 32 66 66 66 66 66 71 66 71 71 147 147 148 147 148 179 148 179 179 184 184 185 186 187 290 185 287 287 69 69 70 93 94 313 70 221 221 1 1 1 6 6 105 1 16 16 0 0 0 0 0 12 0 1 1 0 0 0 0 0 1 0 0 0 s(3, 6) w(3, 6) u(3, 6) t(3, 6) v(3, 6) r(3, 6) w(6, 3) t(6, 3) v(6, 3) 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 7 7 7 7 7 7 7 7 7 14 14 14 14 14 14 14 14 14 36 36 36 36 36 37 36 37 37 95 95 95 95 95 100 95 100 100 311 311 312 311 312 356 312 356 356 1 058 1 058 1 065 1 058 1 065 1 407 1 065 1 407 1 407 3 680 3 680 3 738 3 682 3 740 6 657 3 738 6 654 6 654 9 306 9 306 9 550 9 341 9 585 30 395 9 550 30 275 30 275 9 464 9 464 9 887 10 277 10 705 116 792 9 887 106 701 106 701 1 167 1 167 1 245 2 039 2 135 275 086 1 245 155 472 155 472 2 2 2 34 37 263 520 2 39 049 39 049 0 0 0 0 0 64 732 0 508 508 0 0 0 0 0 2 576 0 2 2 0 0 0 0 0 7 0 0 0 t(4, 4) v(4, 4) r(4, 4) 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 9 9 9 9 9 9 5 24 24 24 24 24 24 6 84 84 84 84 84 84 7 360 360 360 361 361 362 8 2 026 2 026 2 026 2 052 2 052 2 079 9 12 915 12 915 12 915 13 775 13 775 14 701 10 58 700 58 700 58 700 77 801 77 801 103 706 11 56 034 56 034 56 034 180 404 180 404 546 356 12 415 415 415 36 080 36 080 1 449 166 13 0 0 0 8 8 1 184 231 14 0 0 0 0 0 130 816 15 0 0 0 0 0 640 16 0 0 0 0 0 2 Tab. 3: p s(4, 4) w(4, 4) u(4, 4) 3 4 5 6 7 8 p 1 2 3 4 5 6 7 8 9 10 11 12 13 p 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 0 0 0 0 0 1

Acknowledgements

The authors thank Martin Kidd who produced the graphics in this paper.

Ramsey number

Source Extremal avoidance colourings s(3, 3) = 6 [START_REF] Brewster | Irredundant Ramsey numbers for graphs[END_REF] 1 Red subgraph C5 (and blue C5) by Theorem 3 s(3, 4) = 8

[1] 8 Red subgraphs E1-E8 in Figure 1(a)-(h) s(3, 5) = 12 [START_REF] Brewster | Irredundant Ramsey numbers for graphs[END_REF] 1 Red subgraph F6 in Figure 2(f) s(3, 6) = 15 [START_REF] Brewster | The irredundant Ramsey number s(3, 6)[END_REF] 2 Red subgraphs G13-G14 in Figure 3(m)-(n) s(3, 7) = 18 [START_REF] Chen | The irredundant Ramsey number s(3, 7)[END_REF][START_REF] Cockayne | The irredundant Ramsey number s(3, 7)[END_REF] Unknown s(4, 4) = 13 [START_REF] Cockayne | The irredundant Ramsey number s(4, 4)[END_REF] 415 Red subgraphs available online [START_REF] Van Vuuren | Repositories[END_REF]; the smallest is F8 in Figure 2(h) while the largest is the complement of F8 t(3, 3) = 6

[5]

1 Red subgraph C5 (and blue C5) by Theorem 3 t(3, 4) = 9

[5] 2 Red subgraphs E10-E11 in Figure 1(j)-(k) t(4, 3) = 8

[5] 9 Blue subgraphs E1-E9 in Figure 1(a)-(i) t(3, 5) = 12 [START_REF] Cockayne | Mixed Ramsey numbers and irredundant Turán numbers for graphs[END_REF] 6 Red subgraphs F1-F6 in Figure 2(a)-(f) t(5, 3) = 13 [START_REF] Cockayne | Mixed Ramsey numbers and irredundant Turán numbers for graphs[END_REF] 1 Blue subgraph F7 in Figure 2(g) t(3, 6) = 15 [START_REF] Grobler | Irredundant ramsey numbers[END_REF] 34 Red subgraphs available online [START_REF] Van Vuuren | Repositories[END_REF]; the smallest and largest are G15-G16 in Figure 3

1 Red subgraph C5 (and blue C5) by Theorem 3 u(3, 4) = 8

[15] 8 Red subgraphs E1-E8 in Figure 1

New 415 Red subgraphs available online [START_REF] Van Vuuren | Repositories[END_REF]; the smallest is F8 in Figure 2(h) while the largest is the complement of F8 v(3, 3) = 6 Tab. 5: The extremal avoidance colourings associated with the nonclassical Ramsey numbers in Table 1. Corresponding results for the classical Ramsey numbers are also included for completeness.


Mohamad El-Abed
email: mohamad.elabed@ensicaen.fr

Patrick Lacharme
email: patrick.lacharme@ensicaen.fr

Christophe Rosenberger
email: christophe.rosenberger@ensicaen.fr

Security EvaBio: An Analysis Tool for the Security Evaluation of Biometric Authentication Systems

Biometric systems present several drawbacks that may significantly decrease their utility. Nowadays, several platforms (such as the FVC-onGoing) exist to assess the performance of such systems. Despite this, none platform exists for the security evaluation of biometric systems. Hence, the aim of this paper is to present an on-line platform for the security evaluation of biometric systems. The key benefits of the presented platform are twofold. First, it provides biometrics community an evaluation tool to assess biometric systems in term of security. Second, the platform provides a database of common threats and vulnerabilities of biometric systems that can be updated by researchers feedbacks. The presented tool is modality-independent. A keystroke dynamics system is used to illustrate the benefits of the presented platform.

Introduction

Biometrics is a promising candidate to either enhance or replace traditional authentication systems based on "what we own" (such as a key) or "what we know" (such as a password). Many biometric authentication systems have been proposed in the last decade going from morphological (such as fingerprint), behavioral (such as keystroke dynamics) and even biological (such as DNA) modalities. They are mainly used to manage the physical (such as border control) and logical (such as e-commerce) access to resources. Despite the obvious advantages of biometric authentication systems in comparison to traditional ones, they are still vulnerable to several kinds of attacks which may deeply affect their utility and functionality. Ratha et al. [START_REF] Ratha | An analysis of minutiae matching strength[END_REF] have identified eight locations of possible attacks in a generic biometric system as illustrated in Figure 1. Maltoni et al. [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF] present several drawbacks of biometric systems related to circumvention, repudiation, contamination, collusion and coercion threats. The works presented by Ratha et al., Maltoni et al. clearly show the weakness of biometric systems which may decrease their utility. Therefore, it is important that biometric systems be designed to withstand the presented threats when employed in security-critical applications and to achieve an end to end security. Towards this goal, the aim of this work is to present a web-based automated evaluation platform towards the security evaluation of biometric authentication systems. The goal of this platform is to let researchers to easily evaluate their systems in a quantitative manner, and to enhance the presented database of common threats and vulnerabilities based on their feedbacks and publications. Since researchers may overestimate the efficiency of their developed systems, the platform should be then used by an independent party (as the case of competitions) in order to produce accurate assessment results.

The outline of the paper is as follows. We present in Section 2 related previous research works focusing on the security evaluation of biometric systems. Section 3 presents the security assessment method implemented within the proposed platform. A synopsis of the database of common threats and vulnerabilities of biometric systems is given in Section 4. The security analysis tool is then presented in Section 5. Section 6 gives a conclusion and some perspectives of this work.

Previous works

The International Organization for Standardization ISO/IEC FCD 19792 [START_REF]Information technology -security techniques -security evaluation of biometrics[END_REF] presents a list of several threats and vulnerabilities of biometric systems. In addition to the threats addressed by Maltoni et al., the standard addresses other typical threats related to system performance and the quality of the acquired biometric raw data. The standard also addresses privacy concerns when dealing with biometric systems. The standard does not present a security evaluation of biometric systems. It aims to guide the evaluators by giving suggestions and recommendations that should be taken into account during the evaluation process. Dimitriadis et al. [START_REF] Dimitriadis | Application of multi-criteria analysis for the creation of a risk assessment knowledgebase for biometric systems[END_REF] present a security comparison study of several biometric technologies in order to be used as an access control system for stadiums. The presented method can be used easily in comparing biometric systems since it is a quantitative-based method. However, an extended research work should be done in order to take into account the recent threats vulnerabilities of biometric systems (especially those presented by the ISO/IEC FCD 19792 standard). Attack tree technique introduced by Schneier [START_REF] Schneier | Attack trees[END_REF], provides a structure tree to conduct security analysis of protocols, applications and networks. However, attack trees are dependent from the intended system and its context of use. Therefore, it is infeasible to be used for a generic evaluation purpose. Matyás et al. [START_REF] Matyás | Biometric authentication -security and usability[END_REF] propose a security classification of biometric systems. Their proposal classifies biometric systems into four categories according to their security level. However, their model could not be considered as discriminative to compare the security level of biometric systems.

Discussion

The evaluation of biometric systems is now carefully considered. Many platforms have been proposed (such as FVC-onGoing) whose objective is mainly to compare biometric systems. Nevertheless, these platforms are dedicated to quantify the performance technology (algorithms, processing time, memory required, etc.) without testing the robustness of the target system against fraud. The previous section showed the vulnerabilities of biometric systems which may deeply affect its functionality. Therefore, a dedicated platform towards the security evaluation of biometric systems is a promising solution for two main reasons: first, we need a reliable evaluation methodology to quantify the benefits of new systems. Second, such kind of platforms will not only allow researchers to easily test their new systems, it will also enhance this research topic based on the biometric community feedbacks. We present in the next section the quantitative-based security assessment method implemented within the on-line platform. It is a modality-independent method based on the database of common threats and vulnerabilities of biometric systems (see Section 4) and the notion of risk factors.

Risk assessment method

According to ISO/IEC FCD 19792, the security evaluation of biometric systems is generally divided into two complementary assessments: type-1 assessment of the biometric system (devices and algorithms), and type-2 assessment of the environmental (e.g., is the system is used indoor or outdoor?) and operational conditions (e.g., tasks done by system administrators to ensure that the claimed identities during enrollment of the users are valid). We present in this paper a type-1 assessment method for the security evaluation of biometric systems. The presented method is inspired from the security audit methodology EBIOS (Expression of Needs and Identification of Security Objectives) [START_REF]Expression des besoins et identification des objectifs de sécurité (EBIOS)[END_REF]. The principle of the proposed approach contains four steps: study of the context, expression of security needs, risk analysis and security index.

Study of the context

The first step consists of identifying the utility and the characteristics of the target system. This step consists also of detailing its different components and essential elements (known by assets). Using the generic architecture of biometric systems as illustrated in Figure 1 by Ratha et al., the identified assets to be protected are divided into three types as presented in Table 1: an information (I ), a function (F ) and a material (M ).

Expression of security needs

After describing the target system and identifying its assets, the next step consists of identifying the security requirements that will contribute to the risk assessment process. These identified requirements are also used during the risk reduction process (a perspective step of this work). As any IT system, the security requirements should include classical properties in terms of confidentiality (C), integrity (I) and availability (D). In addition, the security requirements of biometric systems should also contain the authenticity (A) property. This property is defined as the fact of ensuring that the user presenting the biometric raw data is who he/she claims to be.

Risk analysis

Risk analysis is considered as a key factor to be taking into account during the development of any IT system. It consists of two steps: identifying the possible threats or events that could have a harmful impact, followed by a risk estimation step. Several works exist in the literature to the risk analysis of an IT system and they are generally divided into two approaches: quantitative or qualitative approaches. A comparison study of both approaches and their advantages and limitations is presented by Arthur Rot [START_REF] Rot | IT risk assessment: Quantitative and qualitative approach[END_REF]. The proposed method is quantitative and based on the notion of risk factors. The choice of the quantitative is mainly retained to its easiness in evaluating and comparing biometric systems, and also it is more exploitable lately during the risk reduction process. A risk factor, for each identified threat and vulnerability, is considered as an indicator of its importance. The computation of risk factors in the presented method is given in both Sections 3.3.1 (identified threats) and 3.3.2 (retained vulnerabilities).

Risk factor computation of the identified threats

In order to compute the risk factors of the identified threats, we use a quantitative approach based on the multi-criteria analysis (MCA). More generally speaking, we use two criteria for the risk factor computation of each identified threat (risk f actor = f 1 × f 2 ):

• Impact (f 1 ): represents the impact of the threat in terms of criticality. It is defined between 0 and 10 (the highest score 10 corresponds to a critical attack). This factor is arbitrary fixed due to the four security requirements (confidentiality, integrity, availability and authenticity) presented in Section 3.2. In this work, we penalize the impact (f 1 ) of threats affecting the confidentiality property more, since such kind of threats affect the privacy and civil liberties of legitimate users.

• Easiness (f 2 ): represents the easiness to make a successful attack. It is defined between 0 and 10 (the lowest score 0 corresponds to an impossible attack, while the highest score 10 corresponds to an easy attack). This factor is arbitrary fixed using two types of informations: first, the weakness of the target system (e.g., weakness related to its architecture), second, the cost in terms of specific equipments and required expertise to implement the attack.

Risk factor computation of the vulnerabilities

For the three retained system overall vulnerabilities (see Section 4.2), we use a set of rules for the risk factors com-putation process as depicted in Table 2. For the system performance vulnerability, we multiply by 2 since a biometric system providing a performance measure (such as the EER, AUC, etc.) more than or equal to 50% is not usable.

For such systems, we put then its risk factor for the highest score 100. For the quality aspect, we define four rules according to whether the system implements quality checks during the enrollment step. For the templates database protection, we also define a set of rules according to whether the system implements protection mechanisms (such as encryption schemes, cancelable techniques, etc.).

Security index

The overall security level of a biometric system, is typically made up of several areas of variable risks. If any of these areas are omitted during the evaluation process, then an unreliable result will be concluded. At this time, such kind of evaluation is considered as a complicated task since the number of actors involved within the process is important. Therefore, an agreed methodology for illustrating the overall system security of a biometric system by an index would facilitate the evaluation and the comparison of such systems [START_REF] Ashbourn | Vulnerability with regard to biometric systems[END_REF]. Towards this goal, we use the notion of the area under curve of the curve resulting from the retained risk factors to compute the security index of the target system. It is calculated using the trapezoid rule. The main benefit of using this approach is it permits to take into account all the risks of a biometric system and their relationships in the processing chain. The security index of the target system is then defined as follows:

Index = α 1 - AU C(f (x)) AU C(g(x)) = α 1 - n 1 f (x) dx n 1 g(x) dx (1
) where α =100, n = r + s with r the number of locations of possible attacks in a generic biometric system and s the number of the retained system overall vulnerabilities (in our case, r = 8 and s = 3); f(x) is the curve resulting from the set of risk factors retained from the n points (the maximal risk factor is retained from each point); and g(x) is the curve resulting from a set of the highest risk factors we can have from each point (according to our model, they are equal to 100). The use of the security index in comparing and evaluating biometric systems is used as follows: the more the index is near 100%, the better is the robustness of the target system against attacks.

Common threats and vulnerabilities of biometric systems

We present in this section a synopsis of the database of common threats and vulnerabilities of biometric systems. The presented database is collected due to the results of desk research, and take into account the known threats presented in previous works (such as those presented in [START_REF] Maltoni | Handbook of Fingerprint Recognition[END_REF][START_REF] Roberts | Biometric attack vectors and defences[END_REF]). The database followed also the concerns and the recommendations presented by the International Organization for Standardization ISO/IEC FCD 19792. Our main objective here is to present an enhanced and unified knowledge base of threats and vulnerabilities to be used by the community in biometrics. We present in Section 4.1 a synopsis (one threat per point as an illustration) of the threats of a generic biometric system, while in Section 4.2 the retained system overall vulnerabilities.

System threats

The presented threats are related to the locations of possible attacks in a generic biometric system as illustrated in Figure 1. Each threat is presented as the following form: "Description" (D) which define the threat, and "Affect" (A) describes which couples (security requirement on asset) will be affected in the case of a successful attack. This representation allows us to compute the risk factor of each identified threat during the evaluation process (see Section 3.3.1). In other words, the "Affect" information permits us to compute the "Impact" criterion (f 1 ) of each identified threat according to the security requirements presented in Section 3.2. The on-line platform contains a total of 19 threats, the number of threats on each identified point is given between two brackets.

System overall vulnerabilities

Point 9. Performance limitations By contrast to traditional authentication methods based on "what we know" or "what we own" (0% comparison error), biometric systems are subject to errors such as False Acceptance Rate (FAR) and False Rejection Rate (FRR). This inaccuracy illustrated by statistical rates would have potential implications regarding the level of security provided by a biometric system. Doddington et al. [START_REF] Doddington | Sheep, goats, lambs and wolves: A statistical analysis of speaker performance in the NIST 1998 speaker recognition evaluation[END_REF] assigns users into four categories: sheep, lambs, goats and wolves. The sheep correspond to users who are easily recognized (contribute to a low FRR). The lambs correspond to users who are easy to imitate (contribute to a high FAR). The goats represent users who are difficult to recognize (contribute to a high FRR). The wolves represent users who have the capability to spoof the biometric characteristics of other users (contribute to a high FAR). A poor biometric in terms of performance, may be easily attacked by lambs and wolves users.

Point 10. Quality limitations during the enrollment process The quality of the acquired biometric samples is considered as an important factor during the enrollment process. It is a generic organizational point of view in the deployment of the biometric system. The absence of a quality test increases the possibility of enrolling authorized users with weak templates. Such templates increase the probability of success of zero-effort impostor, hill-climbing and brute force attempts [START_REF] Uludag | Attacks on biometric systems: A case study in fingerprints[END_REF].

Point 11. Protection schemes of the biometric templates database The use of biometric systems presents concerns in terms of privacy. The fact of storing biometric data in a central database is considered as a violation of civil liberties. Biometric template security is becoming a major concern in biometrics field since, unlike traditional systems (e.g., password-based solutions), compromised templates cannot be revoked and reissued.

Security tool 5.1. Overview and key benefits

The aim of the presented security platform is twofold. First, it provides biometrics community an assessment tool towards the security evaluation of biometric systems. As argued before, such kind of tool should be used by an independent party in order to avoid biased assessment results. Second, it aims to enhance the presented database of common threats and vulnerabilities of biometric systems based on researchers feedbacks. Such kind of databases is useful since it could be exploited by the evaluators in other (quantitative or qualitative) assessment methods. A snapshot of the tool is given in Figure 2.

Architecture and functionality

The security evaluation platform provides three levels of users: evaluator, contributor and administrator level. The evaluator level, allows researchers to easily assess their developed systems using the on-line evaluation platform. The contributor level, provides the contributors dedicated pages to send to us their suggestions and recommendations in order to enhance the platform. It mainly concerns their feedbacks towards enhancing the presented database (e.g., adding new threats) and the implemented security assessment method. The administrator level, allows us to manage and to keep up-to-date the on-line platform (the presented database, risk assessment method, ergonomic interface) based on contributors feedbacks. The platform functionalities are defined as follows: In order to use the platform, a user account (login & password) is created. Then, the user chooses the modality of its target system. After choosing the modality, a list of questions for the identified threats and a set of rules for the system overall vulnerabilities (Sections 4.1 and 4.2, respectively) is presented related to the chosen modality. For the list of requested questions, the evaluator has to rate each question according to a ten-point Likert-type scale. This representation allows us to compute the "Easiness" criterion (f 2 ) of each identified threat. For the "Impact" criterion (f 1 ), it is automatically rated and managed by the platform according to the security requirements presented in Section 3.2. In the presented method, we have more penalized the identified threats affecting the "confidentiality" security requirement factor, since it is related to the privacy issues of the legitimate users. After rating all the requested questions, the result of the security analysis is displayed on a dedicated webpage, or even downloadable as a PDF result file (or latex file). The result file contains a description of the possible threats and vulnerabilities of the target system, a radar presentation of the highest risk factor obtained on each assessment point (according to our model, 11 assessment points), and the security index illustrating the overall system robustness of the target system against attacks. An example of the use of the presented platform on a keystroke dynamics system [START_REF] Giot | Greyc keystroke : a benchmark for keystroke dynamics biometric systems[END_REF] is presented Section 5.3. In addition, the common database of threats and vulnerabilities is also downloadable as a file, which allow researchers to analyze their systems using other security assessment methods (quantitative or qualitative).

Practical results

A keystroke dynamics system [START_REF] Giot | Greyc keystroke : a benchmark for keystroke dynamics biometric systems[END_REF] has been evaluated using the presented security evaluation platform. Table 3 presents the security analysis of the target system. For the "Impact" and "Easiness" criteria (f 1 and f 2 , respectively), we have put the symbol "-" in the last three lines since the corresponding risk factors are computed according to the set of rules presented in Table 2. For the sensor assessment (point 1), we have identified three threats such as A 16 threat defined by: -D: The attacker physically destroy the biometric sensor.

-A: Availability on M SENSOR. For this threat, the "Impact" criterion (f 1 ) is automatically rated by the platform to the value 2 since such kind of threat does not affect the "confidentiality" property. For the "Easiness" criterion (f 2 ), we have rated (using the ten-point Likert-type scale) at 10, since there is no physical protection of the keyboard. Using the computed risk factors and Equation 1, the security index of the target system is equals to 56.7%. This index shows that the target system is vulnerable against attacks. In addition to this index, the comparison of biometric systems should take into account the 11 assessment points in order to achieve a better comparison accuracy. This comparison may be easily done by a radar presentation which compares the highest risk factor of each assessment point. Table 3. Security analysis of the target system

Conclusion and perspectives

The evaluation of biometric systems is a major challenge in biometric research field. Despite the existing evaluation works (databases, competitions and platforms), few are the works dedicated to the security evaluation of biometric systems. Moreover, none platform exists towards the security evaluation of such systems. Nowadays, the security evaluation is considered as a complicated task since the number of actors involved (users behavior, softwares and hardwares) within the biometric process is important. However, an agreed security tool to the security evaluation of biometric systems would be important in order to quantify the benefits of new systems. Towards this goal, we have presented in this paper an on-line evolutive platform to the security evaluation of biometric systems. The platform implements a quantitative-based security assessment method to allow easily the evaluation and comparison of biometric systems. We have also presented a database of common threats and vulnerabilities of biometric systems which may be used by other researchers to quantify their developed systems in a quantitative or qualitative way. We have shown the benefits of the presented platform using a keystroke dynamics system.

For the perspective, many works should be done in order to enhance the presented database of common threats and vulnerabilities of biometric systems (which is one of the main utility of the on-line platform). A list of countermeasures for each modality would be identified to the risk reduction purpose. Finally, the main inconvenience of the presented platform is that it is based on evaluator estimation to compute the "Easiness" criterion (f 2 ). Hence, it would be useful that the estimation of this criterion to be done automatically by the platform.

Figure 1 .

 1 Figure 1. Possible attack points in a generic biometric system: Ratha et al. model [1]

Point 1 .

 1 Sensor (6) A 11 -D: The attacker presents a fake biometric data to the sensor (e.g., prosthetic fingers created out of latex). Such kind of attack is known by spoofing.-A: Authenticity on I DECISION.Points 2 and 4. Transmission channels (5) A 241 -D: The attacker intercepts an authorized biometric sample from a communication channel in order to be replayed (replay attack), bypassing the biometric sensor, at another time for gaining access. -A: Confidentiality on I DATA BIO; Authenticity on I DECISION. Points 3 and 5. Software components (1) A 351 -D: Biometric system components may be replaced with a Trojan horse program that functions according to its designers' specifications. -A: Confidentiality on I DATA BIO; Confidentiality on I TEMPLATE; Availability on F EXTRACTION; Availability on F MATCHER. Point 6. Template database (2) A 61 -D: The attacker illegally reads the biometric templates. -A: Confidentiality on I TEMPLATE; Authenticity on I DECISION. Point 7. Transmission channel (3) A 71 -D: The attacker reads biometric templates from a communication channel in order to be replayed (replay attack). -A: Confidentiality on I TEMPLATE; Authenticity on I DECISION. Point 8. Transmission channel (2) A 81 -D: The attacker alters the transported information (yes or no) in order to deny access of a legitimate user, or even allow access to an impostor. -A: Integrity on I DECISION; Authenticity on I DECISION.

Figure 2 .

 2 Figure 2. A snapshot of the on-line evaluation platform

Table 1 .

 1 The identified assets of a generic biometric system

	Reference	Description
	I DATA BIO	Acquired biometric raw data
	I TEMPLATE	User template
	I DECISION	System decision (yes or no)
	F EXTRACTION	Processing data function implemented on the feature ex-
		tractor component
	F MATCHER	Matcher function between the acquired biometric data
		and its corresponding template
	M SENSOR	Biometric sensor
	M COMPONENT	Materials in which the F EXTRACTION and
		F MATCHER are implemented
	M BD	Storage medium of the biometric templates
	M CHANNELS	Transmission channels connecting the different compo-
		nents of the target system

Table 2 .

 2 General scheme of risk computation for the system overall vulnerabilities. The value Θ illustrates the system overall performance such as the Equal Error Rate (EER)

	Point	Rules	Risk factor
	9	Sufficient panel of users	2 × Θ
	10	-Multiple captures with quality assessment	0
		-One capture with quality assessment	40
		-Multiple captures without quality assessment	60
		-One capture without quality assessment	100
	11	-Secure database and local storage	0
		-Secure database and central storage	40
		-Unsecure database and local storage	60
		-Unsecure database and central storage	100


Manel Tagorti
email: manel.tagorti@inria.fr

Bruno Scherrer
email: bruno.scherrer@inria.fr

Rate of Convergence and Error Bounds for LSTD(λ)

. It computes a linear approximation of the value function of a fixed policy in a large Markov Decision Process. Under a β-mixing assumption, we derive, for any value of λ ∈ (0, 1), a high-probability estimate of the rate of convergence of this algorithm to its limit. We deduce a high-probability bound on the error of this algorithm, that extends (and slightly improves) that derived by Lazaric et al. (2010) in the specific case where λ = 0. In particular, our analysis sheds some light on the choice of λ with respect to the quality of the chosen linear space and the number of samples, that complies with simulations.

Introduction

In a large Markov Decision Process context, we consider LSTD(λ), the least-squares temporal-difference algorithm with eligibility traces proposed by [START_REF] Boyan | Technical update: Least-squares temporal difference learning[END_REF]. It is a popular algorithm for estimating a projection onto a linear space of the value function of a fixed policy. Such a value estimation procedure can for instance be useful in a policy iteration context to eventually estimate an approximately optimal controller [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF][START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF].

The asymptotic almost sure convergence of LSTD(λ) was proved by [START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF]. Under a β-mixing assumption, and given a finite number of samples n, [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] derived a high-probability error bound with a Õ(1 √ n ) rate 1 in the restricted situation where λ = 0. To our knowledge, however, similar finite-sample error bounds are not known in the literature for λ > 0. The main goal of this paper is to fill this gap. This is all the more important that it is known that the parameter λ allows to control the quality of the asymptotic solution of the value: by moving λ from 0 to 1, one can continuously move from an oblique projection of the value [START_REF] Scherrer | Should one compute the temporal difference fix point or minimize the bellman residual? the unified oblique projection view[END_REF] to its orthogonal projection and consequently improve the corresponding guarantee [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF] (restated in Theorem 2, Section 3).

The paper is organized as follows. Section 2 starts by describing the LSTD(λ) algorithm and the necessary background. Section 3 then contains our main result (Theorem 1): for all λ ∈ (0, 1), we will show that LSTD(λ) converges to its limit at a rate Õ( 1 √ n ). We shall then deduce a global error (Corollary 1) that sheds some light on the role of the parameter λ and discuss some of its interesting practical consequences. Section 4 will go on by providing a detailed proof of our claims. Finally, Section 5 concludes and describes potential future work.

LSTD(λ) and Related background

We consider a Markov chain M taking its values on a finite or countable state space 2 X , with transition kernel P . We assume M ergodic 3 ; consequently, it admits a unique stationary distribution µ. For any K ∈ R, we denote B(X , K) the set of measurable functions defined on X and bounded by K. We consider a reward function r ∈ B(X , R max ) for some R max ∈ R, that provides the quality of being in some state. The value function v related to the Markov chain M is defined, for any state i, as the average discounted sum of rewards along infinitely long trajectories starting from i:

∀i ∈ X , v(i) = E   ∞ j=0 γ j r(X j ) X 0 = i   ,
where γ ∈ (0, 1) is a discount factor. It is well-known that the value function v is the unique fixed point of the linear Bellman operator T :

∀i ∈ X , T v(i) = r(i) + γE [v(X 1 )|X 0 = i] .
It can easily be seen that v ∈ B(X , V max ) with V max = Rmax 1-γ . When the size |X | of the state space is very large, one may consider approximating v by using a linear architecture. Given some d |X |, we consider a feature matrix Φ of dimension |X | × d. For any x ∈ X , φ(x) = (φ 1 (x), ..., φ d (x)) T is the feature vector in state x. For any j ∈ {1, ..., d}, we assume that the feature function φ j : X → R belongs to B(X , L) for some finite L. Throughout the paper, and without loss of generality4 we will make the following assumption.

Assumption 1. The feature functions (φ j ) j∈{1,...,d} are linearly independent.

Let S be the subspace generated by the vectors (φ j ) 1≤j≤d . We consider the orthogonal projection Π onto S with respect to the µ-weighed quadratic norm

f µ = x∈X |f (x)| 2 µ(x).
It is well known that this projection has the following closed form

Π = Φ(Φ T D µ Φ) -1 Φ T D µ , (1)
where D µ is the diagonal matrix with elements of µ on the diagonal. The goal of LSTD(λ) is to estimate a solution of the equation v = ΠT λ v, where the operator T λ is defined as a weighted arithmetic mean of the applications of the powers T i of the Bellman operator T for all i > 1:

∀λ ∈ (0, 1), ∀v, T λ v = (1 -λ) ∞ i=0 λ i T i+1 v.
(2)

Note in particular that when λ = 0, one has T λ = T . By using the facts that T i is affine and P µ = 1 [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF][START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF], it can be seen that the operator T λ is a contraction mapping of modulus (1-λ)γ 1-λγ ≤ γ; indeed, for any vectors u, v:

T λ u -T λ v µ ≤ (1 -λ) ∞ i=0 λ i (T i+1 u -T i+1 v) µ = (1 -λ) ∞ i=0 λ i (γ i+1 P i+1 u -γ i+1 P i+1 v) µ ≤ (1 -λ) ∞ i=0 λ i γ i+1 u -v µ = (1 -λ)γ 1 -λγ u -v µ .
Since the orthogonal projector Π is non-expansive with respect to µ [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF], the operator ΠT λ is contracting and thus the equation v = ΠT λ v has one and only one solution, which we shall denote v LST D(λ) since it is what the LSTD(λ) algorithm converges to [START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF]. As v LST D(λ) belongs to the subspace S, there exists a θ ∈ R d such that

v LST D(λ) = Φθ = ΠT λ Φθ.
If we replace Π and T λ with their expressions (Equations 1 and 2), it can be seen that θ is a solution of the equation Aθ = b [START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF], such that for any i,

A = Φ T D µ (I -γP )(I -λγP ) -1 Φ = E X-∞∼µ i k=-∞ (γλ) i-k φ(X k )(φ(X i ) -γφ(X i+1 )) T (3) and b = Φ T D µ (I -γλP ) -1 r = E X-∞∼µ i k=-∞ (γλ) i-k φ(X k )r(X i ) , (4)
where u T is the transpose of u. Since for all x, φ(x) is of dimension d, we see that A is a d × d matrix and b is a vector of size d. Under Assumption 1, it can be shown [START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF] that the matrix A is invertible, and thus v LST D(λ) = ΦA -1 b is well defined.

The LSTD(λ) algorithm that is the focus of this article is now precisely described. Given one trajectory X 1 , ...., X n generated by the Markov chain, the expectation-based expressions of A and b in Equations ( 3)-( 4) suggest to compute the following estimates:

 = 1 n -1 n-1 i=1 z i (φ(X i ) -γφ(X i+1 )) T and b = 1 n -1 n-1 i=1 z i r(X i )
where

z i = i k=1 (λγ) i-k φ(X k ) (5)
is the so-called eligibility trace. The algorithm then returns vLST D(λ) = Φ θ with5 θ = Â-1b , which is a (finite sample) approximation of v LST D(λ) . Using a variation of the law of large numbers, [START_REF] Nedic | Least squares policy evaluation algorithms with linear function approximation[END_REF] showed that both  and b converge almost surely respectively to A and b, which implies that vLST D(λ) tends to v LST D(λ) . The main goal of the remaining of the paper is to deepen this analysis: we shall estimate the rate of convergence of vLST D(λ) to v LST D(λ) , and bound the approximation error vLST D(λ) -v µ of the overall algorithm.

Main results

This section contains our main results. Our key assumption for the analysis is that the Markov chain process that generates the states has some mixing property6 .

Assumption 2. The process (X n ) n≥1 is β-mixing, in the sense that its i th coefficient

β i = sup t≥1 E sup B∈σ(X ∞ t+i ) P (B|σ(X t 1 )) -P (B)
tends to 0 when i tends to infinity, where X j l = {X l , ..., X j } for j ≥ l and σ(X j l ) is the sigma algebra generated by X j l . Furthermore, (X n ) n≥1 mixes at an exponential decay rate with parameters β > 0, b > 0, and κ > 0 in the sense that β i ≤ βe -bi κ .

Intuitively the β i coefficients measure the degree of dependence of samples separated by i times step (the smaller the coefficient the more independence). We are now ready to state the main result of the paper, that provides a rate of convergence of LSTD(λ).

Theorem 1. Let Assumptions 1 and 2 hold and let X 1 ∼ µ. For any n ≥ 1 and δ ∈ (0, 1), define:

I(n, δ) = 32Λ(n, δ) max Λ(n, δ) b , 1 1 κ
where Λ(n, δ) = log 8n 2 δ + log(max{4e 2 , nβ}).

Let n 0 (δ) be the smallest integer such that

∀n ≥ n 0 (δ), 2dL 2 (1 -γ)ν    2 √ n -1       log(n -1) log 1 λγ     + 1   I(n -1, δ)+ 1 (n -1)(1 -λγ) + 2 (n -1)     log(n -1) log 1 λγ       < 1 (6)
where ν is the smallest eigenvalue of the Gram matrix Φ T D µ Φ. Then, for all δ, with probability at least 1 -δ, for all n ≥ n 0 (δ), Â is invertible and we have:

v LST D(λ) -vLST D(λ) µ ≤ 4V max dL 2 √ n -1(1 -γ)ν   1 +     log(n -1) log 1 λγ       I(n -1, δ) + h(n, δ) with h(n, δ) = Õ( 1 n ).
The constant ν is strictly positive under Assumption 1. For all δ, it is clear that the finite constant n 0 (δ) exists since the l.h.s. of Equation ( 6) tends to 0 when n tends to infinity. As 1 + log(n-1) log( 1 λγ )

I(n- 1, δ n 2 ) = Õ(1)
, we can see that LSTD(λ) estimates v LST D(λ) at the rate Õ 1 √ n . Finally, we can observe that since the function λ →

1 log( 1 λγ )
is increasing, the rate of convergence deteriorates when λ increases.

This negative effect can be balanced by the fact that, as shown by the following result from the literature, the quality of v LST D(λ) improves when λ increases.

Theorem 2 [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF]). The approximation error satisfies 7 :

v -v LST D(λ) µ ≤ 1 -λγ 1 -γ v -Πv µ .
Since the constant equals 1 when λ = 1, one recovers the well-known fact that LSTD(1) computes the orthogonal projection Πv of v. By using the triangle inequality, one deduces from Theorems 1 and 2 the following global error bound.

Corollary 1. Let the assumptions and notations of Theorem 1 hold. For all δ, with probability 1 -δ, for all n ≥ n 0 (δ), the global error of LSTD(λ) satisfies:

v -vLST D(λ) µ ≤ 1 -λγ 1 -γ v -Πv µ + 4V max dL 2 √ n -1(1 -γ)ν         log(n -1) log 1 λγ     + 1   I(n -1, δ)   1 2 + h(n, δ).
7 As suggested by V. Papavassilou [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF], this bound can in fact be improved by using the Pythagorean theorem to

v -v LST D(λ) µ ≤ 1 -λγ (1 -γ)(1 + γ -2λγ) v -Πv µ.
We keep the simple form of Theorem 2 for simplicity. We generated 1000 random Garnet MDPs [START_REF] Archibald | On the generation of Markov decision processes[END_REF] with 100 states, random uniform rewards and γ = 0.99. We also generated 1000 random feature spaces of dimension 20 (by taking random matrices with random uniform entries). For all values of λ ∈ {0.0, 0.3, 0.5, 0.7, 0.9, 1.0}, we display (left) the average of the real error and (right) the standard deviation with respect to the number of samples. Empirically, the best value of λ appears to be a monotonic function of the number of samples n, that tends to 1 asymptotically. This is in accordance with our results in Corollary 1.

Remark 1. The form of the result stated in Corollary 1 is slightly stronger than the one of [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF]: for some property P (n), our result if of the form "∀δ, ∃n 0 (δ), such that ∀n > n 0 (δ), P (n) holds with probability 1 -δ" while theirs is of the form "∀n, ∀δ, P (n) holds with probability 1 -δ". Furthermore, under the same assumptions, the global error bound obtained by [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF], in the restricted case where λ = 0, has the following form:

ṽLST D(0) -v µ ≤ 4 √ 2 1 -γ v -Πv µ + Õ 1 √ n ,
where ṽLST D(0) is the truncation (with V max ) of the pathwise LSTD solution8 , while we get in this analysis

vLST D(0) -v µ ≤ 1 1 -γ v -Πv µ + Õ 1 √ n .
The term corresponding to the approximation error is a factor 4 √ 2 better with our analysis. Moreover, contrary to what we do here, the analysis of [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] does not imply a rate of convergence for LSTD(λ) (a bound on v LST D(0) -vLST D(0) µ ). Their arguments, based on a model of regression with Markov design, consists in directly bounding the global error. Our two-step argument (bounding the estimation error with respect to • µ , and then the approximation error with respect to • µ ) allows us to get a tighter result.

As we have already mentioned, λ = 1 minimizes the bound on the approximation error v -v LST D(λ) (the first term in the r.h.s. in Corollary 1) while λ = 0 minimizes the bound on the estimation error v LST D(λ) -vLST D(λ) (the second term). For any n, and for any δ, there exists hence a value λ * that minimizes the global error bound by making an optimal compromise between the approximation and estimation errors. Figure 1 illustrates through simulations the interplay between λ and n. The optimal value λ * depends on the process mixing parameters (b, κ and β) as well as on the quality of the policy space v -Πv µ , which are quantities that are usually unknown in practice. However, when the number of samples n tends to infinity, it is clear that this optimal value λ * tends to 1.

The next section contains a detailed proof of Theorem 1.

Proof of Theorem 1

In this section, we develop the arguments underlying the results of the previous section. The proof is organized in two parts. In a first preliminary part, we prove a concentration inequality for vector processes: a general result that is based on infinitely-long eligibility traces. Then, in a second part, we actually prove Theorem 1: we apply this result to the error on estimating A and b, and relate these errors with that on v LST D(λ) .

Concentration inequality for infinitely-long trace-based estimates

One of the first difficulties for the analysis of LSTD(λ) is that the variables

A i = z i (φ(X i ) -γφ(X i+1 )) T (respectively b i = z i r(X i ))
are not independent. Thus standard concentration results (like Lemma 6 we will describe in the Appendix A) for quantifying the speed at which the estimates converge to their limit cannot be used. As both terms  and b have the same structure, we will consider here a matrix that has the following general form:

Ĝ = 1 n -1 n-1 i=1 G i (7) with G i = z i (τ (X i , X i+1 )) T (8)
with z i , defined in Equation ( 5), satisfies

z i = i k=1 (λγ) i-k φ(X k ) and τ : X 2 → R k is such that for 1 ≤ i ≤ k, τ i belongs to B(X 2 , L
) for some finite L9 . The variables G i are computed from one single trajectory, they are then significantly dependent. Nevertheless with the mixing assumption (Assumption 2), we can overcome this difficulty, and this by using a blocking technique due to [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF]. This technique leads us back to the independent case. However the transition from the mixing case to the independent one requires stationarity (Lemma 5) while G i as a σ(X i+1 ) measurable function of the non-stationary vector (X 1 , . . . , X i+1 ) does not define a stationary process. In order to satisfy the stationarity condition we will approximate G i by it truncated stationary version G m i . This is possible if we approximate z i by its m-truncated version:

z m i = i k=max(i-m+1,1) (λγ) i-k φ(X k ).
Since the function φ is bounded by some constant L and the influence of the old events are controlled by some power of λγ < 1, it is easy to check that z

i -z m i ∞ ≤ L 1-λγ (λγ) m . If we choose m such that m > log(n-1) log 1 λγ , we obtain z i -z m i 2 = O 1 n .
Therefore it seems reasonable to approximate Ĝ with the process Ĝm satisfying Ĝm

= 1 n -1 n-1 i=1 G m i , (9)
with

G m i = z m i (τ (X i , X i+1 )) T . ( 10
)
For all i ≥ m, G m i is a σ(X m+1 ) measurable function of the stationary vector Z i = (X i-m+1 , X i-m+2 , . . . , X i+1 ). So we can apply the blocking technique of [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF] to G m i , but before to do so we have to check out whether G m i well defines a β-mixing process. It can be shown [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF]) that any mesurable function f of a β-mixing process is a β f -mixing process with β f ≤ β, so we only have to prove that the process Z i is a β-mixing process. For that we need to relate its β coefficients to those of (X i ) i≥1 on which Assumption 2 is made. This is the purpose of the following Lemma.

Lemma 1. Let (X n ) n≥1 be a β-mixing process, then

(Z n ) n≥1 = (X n-m+1 , X n-m+2 , . . . , X n+1 ) n≥1 is a β-mixing process such that its i th β mixing coefficient β Z i satisfies β Z i ≤ β X i-m .
Proof. Let Γ = σ(Z 1 , ..., Z t ), by definition we have Γ = σ(Z -1 j (B) : j ∈ {1, ..., t}, B ∈ σ(X m+1 )). For all j ∈ {1, ..., t} we have

Z -1 j (B) = {ω ∈ Ω, Z j (ω) ∈ B} . For B = B 0 × ... × B m , we observe that Z -1 j (B) = {ω ∈ Ω, X j (ω) ∈ B 0 , ..., X j+m (ω) ∈ B m }. Then we have Γ = σ(X -1 j (B) : j ∈ {1, ..., t + m}, B ∈ σ(X )) = σ(X 1 , ..., X t+m ). Similarly we can prove that σ(Z ∞ t+i ) = σ(X ∞ t+i ).
Then let β X i be the i th β-mixing coefficient of the process (X n ) n≥1 , we have

β X i = sup t≥1 E sup B∈σ(X ∞ t+i ) |P (B|σ(X 1 , ..., X t )) -P (B)| .
Similarly for the process (Z n ) n≥1 we can see that

β Z i = sup t≥1 E sup B∈σ(Z ∞ t+i ) |P (B|σ(Z 1 , ..., Z t )) -P (B)| .
By applying what we developped above we obtain

β Z i = sup t≥1 E sup B∈σ(X ∞ t+i )
|P (B|σ(X 1 , ..., X t+m )) -P (B)| .

Denote t = t + m then for i > m we have

β Z i = sup t ≥m+1 E sup B∈σ(X ∞ t +i-m ) |P (B|σ(X 1 , ..., X t )) -P (B)| ≤ β X i-m . Let . F denote the Frobenius norm satisfying : for M ∈ R d×k , M 2 F = d l=1 k j=1 (M l,j ) 2 .
We are now ready to prove the concentration inequality for the infinitely-long-trace β-mixing process Ĝ.

Lemma 2. Let Assumptions 1 and 2 hold and let X 1 ∼ µ. Define the d × k matrix G i such that

G i = i k=1 (λγ) i-k φ(X k )(τ (X i , X i+1 )) T . ( 11
)
Recall that φ = (φ 1 , . . . , φ d ) is such that for all j, φ j ∈ B(X , L), and that τ ∈ B(X 2 , L ). Then for all δ in (0, 1), with probability 1 -δ,

1 n -1 n-1 i=1 G i - 1 n -1 n-1 i=1 E[G i ] 2 ≤ 2 √ d × kLL (1 -λγ) √ n -1       log(n -1) log 1 λγ     + 1   J(n -1, δ) + (n),
where

J(n, δ) = 32Γ(n, δ) max Γ(n, δ) b , 1 1 κ , Γ(n, δ) = log 2 δ + log(max{4e 2 , nβ}), (n) = 2     log(n -1) log 1 λγ     √ d × kLL (n -1)(1 -λγ)
.

Note that with respect to the quantities I and Λ introduced in Theorem 1, the quantities we introduce here are such that J(n, δ) = I(n, 4n 2 δ) and Γ(n, δ) = Λ(n, 4n 2 δ).

Proof. The proof amounts to show that i) the approximation due to considering the estimate Ĝm with truncated traces instead of Ĝ is bounded by (n), and then ii) to apply the block technique of [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF] in a way somewhat similar to-but technically slightly more involved than-what [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] did for LSTD(0). We defer the technical arguments to Appendix A for readability.

Using a very similar proof, we can derive a (simpler) general concentration inequality for β-mixing processes:

Lemma 3. Let Y = (Y 1 , . . . , Y n ) be random variables taking their values in the space R d , generated from a stationary exponentially β-mixing process with parameters β, b and κ, and such that for all i,

Y i -E[Y i ] 2 ≤ B 2 almost surely. Then for all δ > 0, P 1 n n i=1 Y i - 1 n n i=1 E[Y i ] 2 ≤ B 2 √ n J(n, δ) > 1 -δ
where J(n, δ) is defined as in Lemma 2.

Remark 2. If the variables Y i were independent, we would have β i = 0 for all i, that is we could choose β = 0 and b = ∞, so that J(n, δ) reduces to 32 log 8e 2 δ = O(1) and we recover standard results such as the one we describe in Lemma 6 we will describe in the Appendix A. Furthermore, the price to pay for having a β-mixing assumption (instead of simple independence) lies in the extra coefficient J(n, δ) which is Õ(1); in other words, it is rather mild.

Proof of Theorem 1

After having introduced the corresponding concentration inequality for infinitely-long trace-based estimates we are ready to prove Theorem 1. The first important step to Theorem 1 proof consists in deriving the following lemma.

v LST D(λ) -vLST D(λ) µ ≤ 1 -λγ (1 -γ) √ ν (I + A A -1 ) -1 2 A θ -b 2 .
Furthermore, if for some and C, A 2 ≤ < C ≤ 1 A -1 2 , then  is invertible and

(I + A A -1 ) -1 2 ≤ 1 1 -C .
Proof. Starting from the definitions of v LST D(λ) and vLST D(λ) , we have

vLST D(λ) -v LST D(λ) = Φ θ -Φθ = ΦA -1 (A θ -b). (12)
On the one hand, with the expression of A in Equation ( 3), writing M = (1 -λ)γP (I -λγP ) -1 and M µ = Φ T D µ Φ, and using some linear algebra arguments, we can observe that

ΦA -1 = Φ Φ T D µ (I -γP )(I -λγP ) -1 Φ -1 = Φ Φ T D µ (I -λγP -(1 -λ)γP )(I -λγP ) -1 Φ -1 = Φ(M µ -Φ T D µ M Φ) -1 .
10 When  is not invertible, we take vLST D(λ) = ∞ and the inequality is always satisfied since, as we will see shortly, the invertiblity of  is equivalent to that of (I + A A -1 ).

Since the matrices A and M µ are invertible, the matrix (I -

M -1 µ Φ T D µ M Φ) is also invertible, then ΦA -1 = Φ(I -M -1 µ Φ T D µ M Φ) -1 M -1 µ .
We know from [START_REF] Tsitsiklis | An analysis of temporal-difference learning with function approximation[END_REF] that Π µ = 1-the projection matrix Π is defined in Equation (1)-and P µ = 1. Hence, we have ΠM µ = (1-λ)γ 1-λγ < 1 and the matrix (I -ΠM ) is invertible. We can use the identity X(I -Y X) -1 = (I -XY ) -1 X with X = Φ and Y = M -1 µ Φ T D µ M , and obtain

ΦA -1 = (I -ΠM ) -1 ΦM -1 µ . ( 13
)
On the other hand, using the facts that Aθ = b and Âθ = b, we can see that:

A θ -b = A θ -b -( Âθ -b) = b -b -A θ = b -b -A θ + A θ -A θ = b -b -( Â -A)θ + A (θ -θ) = b -Âθ -(b -Aθ) + A A -1 (Aθ -A θ) = b -Âθ + A A -1 (b -A θ).
Then we have

A θ -b = b -Âθ -A A -1 (b -A θ). Consequently A θ -b = (I + A A -1 ) -1 ( b -Âθ) = (I + A A -1 ) -1 ( b -A θ) (14)
where the last equality follows from the identity Aθ = b. Using Equations ( 13) and ( 14), Equation ( 12) can be rewritten as follows:

vLST D(λ) -v LST D(λ) = (I -ΠM ) -1 ΦM -1 µ (I + A A -1 ) -1 ( b -A θ). (15)
Now we will try to bound ΦM -1 µ (I + A A -1 ) -1 ( b -A θ) µ . Notice that for all x,

ΦM -1 µ x µ = x T M -1 µ Φ T D µ ΦM -1 µ x = x T M -1 µ x ≤ 1 √ ν x 2 ( 16
)
where ν is the smallest (real) eigenvalue of the Gram matrix M µ . By taking the norm in Equation ( 15) and using the above relation, we get

vLST D(λ) -v LST D(λ) µ ≤ (I -ΠM ) -1 µ ΦM -1 µ (I + A A -1 ) -1 ( b -A θ) µ ≤ (I -ΠM ) -1 µ 1 √ ν (I + A A -1 ) -1 ( A θ -b ) 2 ≤ (I -ΠM ) -1 µ 1 √ ν (I + A A -1 ) -1 2 A θ -b 2 .
The first part of the lemma is obtained by using the fact that ΠM µ = (1-λ)γ 1-λγ < 1, which imply that

(I -ΠM ) -1 µ = ∞ i=0 (ΠM ) i µ ≤ ∞ i=0 ΠM i µ ≤ 1 1 -(1-λ)γ 1-λγ = 1 -λγ 1 -γ . ( 17
)
We are going now to prove the second part of the Lemma. Since A is invertible, the matrix  is invertible if and only if the matrix ÂA -1 = (A + A )A -1 = I + A A -1 is invertible. Let us denote ρ( A A -1 ) the spectral radius of the matrix A A -1 . A sufficient condition for ÂA -1 to be invertible is that ρ( A A -1 ) < 1. From the inequality ρ(M ) ≤ M 2 for any square matrix M , we can see that for any C and that satisfy

A 2 ≤ < C < 1 A -1 2 , we have ρ( A A -1 ) ≤ A A -1 2 ≤ A 2 A -1 2 ≤ C < 1.
It follows that the matrix  is invertible and

(I + A A -1 ) -1 2 = ∞ i=0 ( A A -1 ) i 2 ≤ ∞ i=0 C i = 1 1 -C .
This concludes the proof of Lemma 4.

To finish the proof of Theorem 1, Lemma 4 suggests that we should control both terms A 2 and A θb 2 with high probability. This is what we do now.

Controlling A 2 . By the triangle inequality, we can see that

A 2 ≤ E[ A ] 2 + A -E[ A ] 2 . ( 18
) Write Ân,k = φ(X k )(φ(X n ) -γφ(X n+1 )) T .
For all n and k, we have Ân,k 2 ≤ 2dL 2 . We can bound the first term of the r.h.s. of Equation ( 18) as follows, by replacing A with its expression in (3):

E[ A ] 2 = A -E 1 n -1 n-1 i=1 i k=1 (λγ) i-k Âi,k 2 = E 1 n -1 n-1 i=1 i k=-∞ (λγ) i-k Âi,k - i k=1 (λγ) i-k Âi,k 2 = E 1 n -1 n-1 i=1 (λγ) i 0 k=-∞ (λγ) -k Âi,k 2 ≤ 1 n -1 n-1 i=1 (λγ) i 2dL 2 1 -λγ ≤ 1 n -1 2dL 2 (1 -λγ) 2 = 0 (n).
Let (δ n ) a parameter in (0, 1) depending on n, that we will fix later, a consequence of Equation ( 18) and the just derived bound is that:

P { A 2 ≥ 1 (n, δ n )} ≤ P{ A -E[ A ] 2 ≥ 1 (n, δ n ) -0 (n)} ≤ δ n if we choose 1 (n, δ n ) such that (cf. Lemma 2) 1 (n, δ n ) -0 (n) = 4dL 2 (1 -λγ) √ n -1       log(n -1) log 1 λγ     + 1   J(n -1, δ n ) + (n) where (n) = 4mdL 2 (n-1)(1-λγ) , that is if 1 (n, δ n ) = 4dL 2 (1 -λγ) √ n -1       log(n -1) log 1 λγ     + 1   J(n -1, δ n ) + (n) + 0 (n). ( 19
)
Controlling A θb 2 . By using the fact that Aθ = b, the definitions of  and b, and the fact that φ(x) T θ = [φθ](x), we have

A θ -b = Âθ - b = 1 n -1 n-1 i=1 z i (φ(X i ) -γφ(X i+1 ) T )θ - 1 n -1 n-1 i=1 z i r(X i ) = 1 n -1 n-1 i=1 z i ([φθ](X i ) -γ[φθ](X i+1 ) T -r(X i )) = 1 n -1 n-1 i=1 z i ∆ i
where, since v LST D(λ) = Φθ, ∆ i is the following number:

∆ i = v LST D(λ) (X i ) -γv LST D(λ) (X i+1 ) -r(X i ).
We can control A θb 2 by following the same proof steps as above. In fact we have

A θ -b 2 ≤ A θ -b -E[ A θ -b ] 2 + E[ A θ -b ] 2 , (20)
and

E[ A θ -b ] 2 ≤ E[ A ] 2 θ 2 + E[ b ] 2 .
From what have been developed before we can see that

E[ A ] 2 ≤ 0 (n) = 1 n-1 2dL 2 (1-λγ) 2 . Similarly we can show that E[ b ] 2 ≤ 1 n-1 √ dLRmax (1-λγ) 2 .
We can hence conclude that

E[ A θ -b ] 2 ≤ 1 n -1 2dL 2 (1 -λγ) 2 θ 2 + 1 n -1 √ dLR max (1 -λγ) 2 = 0 (n).
As a consequence of Equation ( 20) and the just derived bound we have

P( A θ -b 2 ≥ 2 (δ n )) ≤ P( A θ -b -E[ A θ -b ] 2 ≥ 2 (δ n ) -0 (n)) ≤ δ n if we choose 2 (δ n ) such that (cf Lemma 2) 2 (δ n ) = 2 √ dL ∆ i ∞ (1 -λγ) √ n -1       log(n -1) log 1 λγ     + 1   J(n -1, δ n ) + 2 √ dL ∆ i ∞ (n -1)(1 -λγ)     log(n -1) log 1 λγ     + 0 (n). (21)
It remains to compute a bound on ∆ i ∞ . To do so, it suffices to bound v LST D(λ) . For all x ∈ X , we have

|v LST D(λ) (x)| = |φ T (x)θ| ≤ φ T (x) 2 θ 2 ≤ √ dL θ 2 ,
where the first inequality is obtained from the Cauchy-Schwarz inequality. We thus need to bound θ 2 . On the one hand, we have

v LST D(λ) µ = Φθ µ = θ T M µ θ ≥ √ ν θ 2 ,
and on the other hand, we have

v LST D(λ) µ = (I -ΠM ) -1 Π(I -λγP ) -1 r µ ≤ R max 1 -γ = V max .
Therefore

θ 2 ≤ V max √ ν .
We can conclude that

∀x ∈ X , |v LST D(λ) (x)| ≤ √ dLV max √ ν .
Then for all i we have

|∆ i | = |v LST D(λ) (X i ) -γv LST D(λ) (X i+1 ) -r(X i )| ≤ √ dLV max √ ν + γ √ dLV max √ ν + (1 -γ)V max . Since Φ T D µ Φ is a symmetric matrix, we have ν ≤ Φ T D µ Φ 2 . We can see that Φ T D µ Φ 2 ≤ d max j,k |φ t k D µ φ j | = d max j,k |φ t k D 1 2 µ D 1 2 µ φ j | ≤ d max j,k φ t k µ φ j µ ≤ dL 2 , so that ν ≤ dL 2 . It follows that, for all i |∆ i | ≤ √ dLV max √ ν + γ √ dLV max √ ν + √ dL √ ν (1 -γ)V max = 2 √ dL √ ν V max .
Conclusion of the proof. We are ready to conclude the proof. Now that we know how to control both terms A 2 and A θb 2 , we can see that

P {∃n ≥ 1, { A 2 ≥ 1 (n, δ n )} ∪ { A θ -b ) 2 ≥ 2 (n, δ n )}} ≤ ∞ n=1 P { A 2 ≥ 1 (n, δ n )} + P { A θ -b ) 2 ≥ 2 (n, δ n )} ≤2 ∞ n=1 δ n = 1 2 π 2 6 δ < δ if we choose δ n = 1 4n 2 δ.
By the second part of Lemma 4, for all δ, with probability at least 1 -δ, for all n such that 1 (n, δ n ) < C, Â is invertible and

v LST D(λ) -vLST D(λ) µ ≤ 1 -λγ (1 -γ) √ ν 2 (n, δ n ) 1 -1(n,δn ) C = 1 -λγ (1 -γ) √ ν 2 (n, δ n ) + 1 (n, δ n ) 2 (n, δ n ) C -1 (n, δ n ) .
We get the bound of the Theorem by replacing 1 (n, δ n ) and 2 (n, δ n ) with their definitions in Equations ( 19) and (21).

To complete the proof of Theorem 1, we now need to show how to pick C, which will allow to show that the condition 1 (n, δ n ) < C ≤ 1 A -1 2 is equivalent to the one that characterizes the index n 0 (δ) in the Theorem. Indeed we have

∀v ∈ R d , ΦA -1 v µ = (A -1 v) T M µ A -1 v ≥ √ ν A -1 v 2 .
We know that

ΦA -1 v µ = (I -ΠM ) -1 ΦM -1 µ v µ ≤ 1 -λγ 1 -γ ΦM -1 µ v µ ≤ 1 -λγ (1 -γ) √ ν v 2
where the last inequality is obtained from Equation ( 16). Then

A -1 2 ≤ 1 -λγ (1 -γ)ν ,
and consequently we can take C = (1-γ)ν 1-λγ . This concludes the proof of Theorem 1.

Conclusion and Future Work

This paper introduces a high-probability convergence rate for the algorithm LSTD(λ) in terms of the number of samples n and the parameter λ. We have shown that this convergence is at the rate of Õ( 1 √ n ), in the case where the samples are generated from a stationary β-mixing process. To do so, we introduced an original vector concentration inequality (Lemma 2) for estimates that are based on eligibility traces. A simplified version of this concentration inequality (Lemma 3), that applies to general stationary betamixing processes, may be useful in many other contexts where we want to relax the i.i.d. hypothesis on the samples.

The performance bound that we deduced is more accurate than the one from [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF], restricted to the case λ = 0. The analysis that they proposed was based on a Markov design regression model. By using the trace truncation technique we have employed, we believe it is possible to extend the proof of [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] to the general case λ in (0, 1). However we would still pay a 4 √ 2 extra factor in the final bound.

In the future, we plan to instantiate our new bound in a Policy Iteration context like [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] did for LSTD(0). An interesting follow-up work would also be to extend our analysis of LSTD(λ) to the situation where one considers non-stationary policies, as [START_REF] Scherrer | On the use of non-stationary policies for stationary infinite-horizon Markov decision processes[END_REF] showed that it allows to improve the overall performance of the Policy Iteration Scheme. Finally, a challenging question would be to consider LSTD(λ) in the off-policy case, for which the convergence has recently been proved by [START_REF] Yu | Convergence of least-squares temporal difference methods under general conditions[END_REF].

A Proof of Lemma 2

Writing for a given integer m > 1

1 = 1 n -1 m-1 i=1 G i -E[G i ] and 2 = 1 n -1 n-1 i=m (z i -z m i )τ (X i , X i+1 ) T -E[(z i -z m i )τ (X i , X i+1 ) T ],
we have

1 n -1 n-1 i=1 G i -E[G i ] = 1 n -1 n-1 i=m G i -E[G i ] + 1 = 1 n -1 n-1 i=m z i τ (X i , X i+1 ) T -E[z i τ (X i , X i+1 ) T ] + 1 = 1 n -1 n-1 i=m z m i τ (X i , X i+1 ) T -E[z m i τ (X i , X i+1 ) T ] + 1 + 2 = 1 n -1 n-1 i=m (G m i -E[G m i ]) + 1 + 2 . ( 22
)
For all i, we have

z i ∞ ≤ L 1-λγ , G i ∞ ≤ LL 1-λγ , and z i -z m i ∞ ≤ (λγ) m L 1-λγ . As a consequence-using M 2 ≤ M F = √ d × k x ∞ for M ∈ R d×k with
x the vector obtained by concatenating all M columns-, we can see that

1 + 2 2 ≤ 2(m -1) √ d × kLL (n -1)(1 -λγ) + 2(λγ) m √ d × kLL (1 -λγ) (23)
By concatenating all its columns, the d × k matrix G m i may be seen a single vector U m i of size dk. Then, for all > 0,

P 1 n -m n-1 i=m (G m i -E[G m i ]) 2 ≥ ≤ P 1 n -m n-1 i=m (G m i -E[G m i ]) F ≥ = P 1 n -m n-1 i=m (U m i -E[U m i ]) 2 ≥ . ( 24
)
The variables U m i define a stationary β-mixing process (Lemma 1). To deal with the β-mixing assumption, we use the decomposition technique proposed by [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF] that consists in dividing the stationary sequence U m m , . . . , U m n-1 into 2µ n-m blocks of length a n-m (we assume here that n -m = 2a n-m µ n-m ). The blocks are of two kinds: those which contains the even indexes E = ∪ µn-m l=1 E l and those with odd indexes H = ∪ µn-m l=1 H l . Thus, by grouping the variables into blocks we get

P 1 n -m n-1 i=m U m i -E[U m i ] 2 ≥ ≤P i∈H U m i -E[U m i ] 2 + i∈E U m i -E[U m i ] 2 ≥ (n -m) 2 (25) ≤P i∈H U m i -E[U m i ] 2 ≥ (n -m) 4 + P i∈E U m i -E[U m i ] 2 ≥ (n -m) 4 (26) =2P i∈H U m i -E[U m i ] 2 ≥ (n -m) 4 (27)
where Equation ( 25) follows from the triangle inequality, Equation ( 26) from the fact that the event {X + Y ≥ a} implies {X ≥ a 2 } or {Y ≥ a 2 }, and Equation ( 27) from the assumption that the process is stationary. Since H = ∪ µn-m l=1 H l we have

P 1 n -m n-1 i=m U m i -E[U m i ] 2 ≥ ≤ 2P   µn-m l=1 i∈H l U m i -E[U m i ] 2 ≥ (n -m) 4   = 2P µn-m l=1 U (H l ) -E[U (H l )] 2 ≥ (n -m) 4 ( 28
)
where we defined U (H l ) = i∈H l U m i . Now consider the sequence of identically distributed independent blocks (U (H l )) l=1,...,µn-m such that each block U (H l ) has the same distribution as U (H l ). We are going to use the following technical result.

Lemma 5. [START_REF] Yu | Rates of convergence for empirical processes stationnary mixing consequences[END_REF] Let X 1 , . . . , X n be a sequence of samples drawn from a stationary β-mixing process with coefficients {β i }. Let X(H) = (X(H 1 ), . . . , X(H µn-m )) where for all j X(H j ) = (X i ) i∈Hj . Let X (H) = (X (H 1 ), . . . , X (H µn-m )) with X (H j ) independent and such that for all j, X (H j ) has same distribution as X(H j ). Let Q and Q be the distribution of X(H) and X (H) respectively. For any measurable function h : X anµn → R bounded by B, we have

|E Q [h(X(H)] -E Q [h(X (H)]| ≤ Bµ n β an .
By applying Lemma 5, Equation (28) leads to:

P 1 n -m n-1 i=m U m i -E[U m i ] 2 ≥ ≤ 2P µn-m l=1 U (H l ) -E[U (H l )] 2 ≥ (n -m) 4 + 2µ n-m β an-m . (29)
The variables U (H l ) are independent. Furthermore, it can be seen that (

µn-m l=1 U (H l )-E[U (H l )]) µn-m is a σ(U (H 1 ), . . . , U (H µn-m )) martingale: E µn-m l=1 U (H l ) -E[U (H l )] U (H 1 ), . . . , U (H µn-m-1 ) = µn-m-1 l=1 U (H l ) -E[U (H l )] + E[U Hµ n-m -E[U Hµ n-m ]] = µn-m-1 l=1 U (H l ) -E[U (H l )].
We can now use the following concentration result for martingales.

Lemma 6 [START_REF] Hayes | A large-deviation inequality for vector-valued martingales[END_REF]). Let X = (X 0 , . . . , X n ) be a discrete time martingale taking values in an Euclidean space such that X 0 = 0 and for all i, X i -X i-1 2 ≤ B 2 almost surely. Then for all ,

P { X n 2 ≥ } < 2e 2 e - 2 2n(B 2 ) 2 . Indeed, taking X µn-m = µn-m l= U (H l ) -E[U (H l )], and observing that X i -X i-1 = U (H l ) - E[U (H l )] 2 ≤ a n-m C with C = 2 √ dkLL 1-λγ , the lemma leads to P µn-m l=1 U (H l ) -E[U (H l )] 2 ≥ (n -m) 4 ≤ 2e 2 e - (n-m) 2 2 32µ n-m (a n-m C) 2 = 2e 2 e - (n-m) 2 16a n-m C 2 .
where the second line is obtained by using the fact that 2a n-m µ n-m = n -m. With Equations ( 28) and ( 29 The vector U m i is a function of Z i = (X i-m+1 , . . . , X i+1 ), and Lemma 1 tells us that for all j > m, β U j ≤ β Z j ≤ β X j-m ≤ βe -b(j-m) κ .

So the equation above may be re-written as

P 1 n -m n-1 i=m U m i -E[U m i ] 2 ≥ ≤ 4e 2 e - (n-m) 2
16a n-m C 2 + 2(n -m)βe -b(an-m-m) κ = δ .

We now follow a reasoning similar to that of [START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] Let J(n, δ) = 32Λ(n, δ) max Λ(n,δ) b , 1 1 κ . Then Equation ( 30) is reduced to

P 1 n -m n-1 i=m (U m i -E[U m i ]) 2 ≥ C √ n -m (ζJ(n -m, δ)) 1 2 ≤ δ. (33)
Since J(n, δ) is an increasing function on n, and

n-1 √ n-1(n-m) = 1 √ n-m n-1 n-m ≥ 1 √ n-m , we have P 1 n -1 n-1 i=m (G m i -E[G m i ]) 2 ≥ C √ n -1 (ζJ(n -1, δ)) 1 2 ≤ P 1 n -m n-1 i=m (G m i -E[G m i ]) 2 ≥ C √ n -1 n -1 n -m ((m + 1)J(n -1, δ)) 1 2 ≤ P 1 n -m n-1 i=m (G m i -E[G m i ]) 2 ≥ C √
n -m ((m + 1)J(n -m, δ))

1 2

.

By using Equations ( 24) and (33), we deduce that

P 1 n -1 n-1 i=m (G m i -E[G m i ]) 2 ≥ C √ n -1 ((m + 1)J(n -1, δ)) 1 2 ≤ δ. (34)
By combining Equations ( 22), ( 23),(34), plugging the value of C = 2 √ dkLL 1-λγ , and taking m = log (n-1) log 1 λγ , we get the announced result.

Figure 1 :

 1 Figure1: Learning curves for different values of λ. We generated 1000 random Garnet MDPs[START_REF] Archibald | On the generation of Markov decision processes[END_REF] with 100 states, random uniform rewards and γ = 0.99. We also generated 1000 random feature spaces of dimension 20 (by taking random matrices with random uniform entries). For all values of λ ∈ {0.0, 0.3, 0.5, 0.7, 0.9, 1.0}, we display (left) the average of the real error and (right) the standard deviation with respect to the number of samples. Empirically, the best value of λ appears to be a monotonic function of the number of samples n, that tends to 1 asymptotically. This is in accordance with our results in Corollary 1.

Lemma 4 .

 4 Write A = Â -A, b = b -b and ν the smallest eigenvalue of the matrix Φ T D µ Φ. For all λ ∈ (0, 1), the estimate vLST D(λ) satisfies 10 :

  m C 2 + 2(n -m)β U an-m .

  in order to get the same exponent in both of the above exponentials. Takinga n-m -m = C2(n-m) 2 b 1 κ+1 with C 2 = (16C 2 ζ) -1 , and ζ = an-m an-m-m , we have δ ≤ (4e 2 + (n -m)β) exp -min b (n -m) -m, δ) C 2 (n -m) max Λ(n -m, δ) m)C 2 ( (δ)) 2 ≤ exp (-Λ(n -m, δ)) . -m, δ) k k+1 max {Λ(n -m, δ), b} 1 k+1 ≤ exp (-Λ(n -m, δ)) .By combining Equations (31) and (32), we getδ ≤ (4e 2 + (n -m)β) exp (-Λ(n -m, δ)) .If we replace Λ(n -m, δ) with its expression, we obtainexp (-Λ(n -m, δ)) = δ 2 max{4e 2 , (n -m)β} -1 .Since 4e 2 max{4e 2 , (n -m)β} -1 ≤ 1 and (n -m)β max{4e 2 , (n -m)β} -1 ≤ 1, we consequently haveδ ≤ 2 δ 2 ≤ δ. Now, note that since a n-m -m ≥ 1, we have ζ = a n-m a n-m -m = a n-m -m + m a n-m -m ≤ 1 + m.

Throughout the paper, we shall write f (n) = Õ(g(n)) as a shorthand for f (n) = O(g(n) log k g(n)) for some k ≥ 0.

We restrict our focus to finite/countable mainly because it eases the presentation of our analysis. Though this requires some extra work, we believe the analysis we make here can be extended to more general state spaces.

In our countable state space situation, ergodicity holds if and only if the chain is aperiodic and irreducible, that is formally if and only if: ∀(x, y) ∈ X 2 , ∃n 0 , ∀n ≥ n 0 , P n (x, y) > 0.

This assumption is not fundamental: in theory, we can remove any set of features that makes the family linearly dependent; in practice, the algorithm we are going to describe can use the pseudo-inverse instead of the inverse.

We will see in Theorem 1 that  is invertible with high probability for a sufficiently big n.

A stationary ergodic Markov chain is always β-mixing.

See[START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF] for more details.

We denote X i = X × X ... × X i times for i ≥ 1.

This inequality exists in[START_REF] Lazaric | Finite-sample analysis of least-squares policy iteration[END_REF], and is developped here for completeness.