Alessandro Lazaric

Mohammad Ghavamzadeh
email: mohammad.ghavamzadeh@inria.fr

Rémi Munos
email: remi.munos@

Ronald Parr

Finite-Sample Analysis of Least-Squares Policy Iteration

In this paper, we report a performance bound for the widely used least-squares policy iteration (LSPI) algorithm. We first consider the problem of policy evaluation in reinforcement learning, that is, learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning method, and report finite-sample analysis for this algorithm. To do so, we first derive a bound on the performance of the LSTD solution evaluated at the states generated by the Markov chain and used by the algorithm to learn an estimate of the value function. This result is general in the sense that no assumption is made on the existence of a stationary distribution for the Markov chain. We then derive generalization bounds in the case when the Markov chain possesses a stationary distribution and is β-mixing. Finally, we analyze how the error at each policy evaluation step is propagated through the iterations of a policy iteration method, and derive a performance bound for the LSPI algorithm.

Introduction

Least-squares temporal-difference (LSTD) learning [START_REF] Bradtke | Linear least-squares algorithms for temporal difference learning[END_REF][START_REF] Boyan | Least-squares temporal difference learning[END_REF] is a widely used algorithm for prediction in general, and in the context of reinforcement learning (RL), for learning the value function V π of a given policy π. LSTD has been successfully applied to a number of problems especially after the development of the least-squares policy iteration (LSPI) algorithm [START_REF] Lagoudakis | Least-squares policy iteration[END_REF], which extends LSTD to control by using it in the policy evaluation step of policy iteration. More precisely, LSTD computes the fixed point of the operator ΠT , where T is the Bellman operator and Π is the projection operator in a linear function space F . Although LSTD and LSPI have been widely used in the RL community, a finite-sample analysis of LSTD, that is, performance bounds in terms of the number of samples, the space F , and the characteristic parameters of the MDP at hand, is still missing.

Most of the theoretical work analyzing LSTD have been focused on the model-based case, where explicit models of the reward function and the dynamics are available. In particular, [START_REF] Tsitsiklis | An analysis of temporal difference learning with function approximation[END_REF] showed that the distance between the LSTD solution and the value function V π is bounded by the distance between V π and its closest approximation in the linear space, multiplied by a constant which increases as the discount factor approaches 1. In this bound, it is assumed that the Markov chain possesses a stationary distribution ρ π and the distances are measured according c 2012 Alessandro Lazaric, Mohammad Ghavamzadeh and Rémi Munos. solution and its performance. In Theorem 1 we show that with a slight modification of the empirical Bellman operator T (leading to the definition of pathwise LSTD), the operator Π T (where Π is an empirical projection operator) always has a fixed point v, even when the sample-based Gram matrix is not invertible and the Markov chain does not admit a stationary distribution. In this very general setting, it is still possible to derive a bound for the performance of the LSTD solution, v, evaluated at the states of the trajectory used by the algorithm. Moreover, an analysis of the bound reveals a critical dependency on the smallest strictly positive eigenvalue ν n of the sample-based Gram matrix. Then, in the case in which the Markov chain has a stationary distribution ρ π , it is possible to relate the value of ν n to the smallest eigenvalue of the Gram matrix defined according to ρ π . Furthermore, it is possible to generalize the previous performance bound over the entire state space under the measure ρ π , when the samples are drawn from a stationary β-mixing process (Theorem 5). It is important to note that the asymptotic bound obtained by taking the number of samples, n, to infinity is equal (up to constants) to the bound in [START_REF] Tsitsiklis | An analysis of temporal difference learning with function approximation[END_REF] for model-based LSTD. Furthermore, a comparison with the bounds in [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] shows that we successfully leverage on the specific setting of LSTD: 1) the space of functions is linear, and 2) the distribution used to evaluate the performance is the stationary distribution of the Markov chain induced by the policy, and obtain a better bound both in terms of 1) estimation error, a rate of order O(1/n) instead of O(1/ √ n) for the squared error, and 2) approximation error, the minimal distance between the value function V π and the space F instead of the inherent Bellman errors of F . The extension in Theorem 6 to the case in which the samples belong to a trajectory generated by a fast mixing Markov chain shows that it is possible to achieve the same performance as in the case of stationary β-mixing processes. Finally, the analysis of LSPI reveals the need for several critical assumptions on the stationary distributions of the policies that are greedy w.r.t. to the functions in the linear space F . These assumptions seem unavoidable when an on-policy method is used at each iteration, and whether they can be removed or relaxed in other settings is still an open question. This paper extends and improves over the conference paper by [START_REF] Lazaric | Finite-sample analysis of lstd[END_REF] in the following respects: 1) we report the full proofs and technical tools for all the theoretical results, thus making the paper self-contained, 2) we extend the LSTD results to LSPI showing how the approximation errors are propagated through iterations.

The rest of the paper is organized as follows. In Section 2, we set the notation used throughout the paper. In Section 3, we introduce pathwise LSTD by a minor modification to the standard LSTD formulation in order to guarantee the existence of at least one solution. In Section 4, we introduce the Markov design setting for regression and report an empirical bound for LSTD. In Section 5, we show how the Markov design bound of Section 4 may be extended when the Markov chain admits a stationary distribution. In Section 6, we analyze how the LSTD error is propagated through the iterations of LSPI and derive a performance bound for the LSPI algorithm. Finally in Section 7, we draw conclusions and discuss some possible directions for future work.

Preliminaries

For a measurable space with domain X , we let S(X ) and B(X ; L) denote the set of probability measures over X , and the space of bounded measurable functions with domain X and bound 0 < L < ∞, respectively. For a measure ρ ∈ S(X ) and a measurable function f : X → R, we define the ℓ 2 (ρ)-norm of f , || f || ρ , and for a set of n points X 1 , . . . , X n ∈ X , we define the empirical norm

|| f || n as || f || 2 ρ = f (x) 2 ρ(dx) and || f || 2 n = 1 n n ∑ t=1 f (X t ) 2 . The supremum norm of f , || f || ∞ , is defined as || f || ∞ = sup x∈X | f (x)|.
We consider the standard RL framework [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF][START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] in which a learning agent interacts with a stochastic environment and this interaction is modeled as a discrete-time discounted Markov decision process (MDP). A discounted MDP is a tuple M = X , A, r, P, γ where the state space X is a bounded closed subset of the s-dimensional Euclidean space, A is a finite (|A| < ∞) action space, the reward function r : X × A → R is uniformly bounded by R max , the transition kernel P is such that for all x ∈ X and a ∈ A, P(•|x, a) is a distribution over X , and γ ∈ (0, 1) is a discount factor. A deterministic policy π : X → A is a mapping from states to actions. For a given policy π, the MDP M is reduced to a Markov chain M π = X , R π , P π , γ with the reward function R π (x) = r x, π(x) , transition kernel P π (•|x) = P • |x, π(x) , and stationary distribution ρ π (if it admits one). The value function of a policy π, V π , is the unique fixed-point of the Bellman operator T π : B(X

;V max = R max 1-γ ) → B(X ;V max ) defined by (T π V )(x) = R π (x) + γ X P π (dy|x)V (y).
We also define the optimal value function V * as the unique fixed-point of the optimal Bellman operator T * : B(X ;V max ) → B(X ;V max ) defined by

(T * V )(x) = max a∈A r(x, a) + γ X P(dy|x, a)V (y) .
In the following sections, to simplify the notation, we remove the dependency to the policy π and use R, P, V , ρ, and T instead of R π , P π , V π , ρ π , and T π whenever the policy π is fixed and clear from the context.

To approximate the value function V , we use a linear approximation architecture with parameters α ∈ R d and basis functions ϕ i ∈ B(X ; L), i = 1, . . . , d. We denote by φ :

X → R d , φ(•) = ϕ 1 (•), . . . , ϕ d (•)
⊤ the feature vector, and by F the linear function space spanned by the basis functions ϕ i . Thus

F = f α | α ∈ R d and f α (•) = φ(•) ⊤ α .
Let (X 1 , . . . , X n ) be a sample path (trajectory) of size n generated by the Markov chain M π .

Let v ∈ R n and r ∈ R n be such that v t = V (X t ) and r t = R(X t ) be the value vector and the reward vector, respectively. Also, let Φ = [φ(X 1 ) ⊤ ; . . . ; φ(X n ) ⊤ ] be the feature matrix defined at the states,

and

F n = {Φα, α ∈ R d } ⊂
R n be the corresponding vector space. We denote by Π : R n → F n the orthogonal projection onto F n , defined as Πy = arg min z∈F n ||y -z|| n , where ||y|| 2 n = 1 n ∑ n t=1 y 2 t . Note that the orthogonal projection Πy for any y ∈ R n exists and is unique. Moreover, Π is a non-expansive mapping w.r.t. the ℓ 2 -norm: since the projection is orthogonal and using the Cauchy-Schwarz inequality || Πy -Πz|| 2 n = yz, Πy -Πz n ≤ ||y -z|| n || Πy -Πz|| n , and thus, we obtain || Πy -Πz|| n ≤ ||y -z|| n .

Pathwise LSTD

Pathwise LSTD (Algorithm 1) is a version of LSTD that takes as input a linear function space F and a single trajectory X 1 , . . . , X n generated by following the policy, and returns the fixed-point Algorithm 1 A pseudo-code for the batch pathwise LSTD algorithm.

Input: Linear space F = span{ϕ i , 1 ≤ i ≤ d}, sample trajectory {(x t , r t )} n t=1 of the Markov chain Build the feature matrix Φ = [φ(x 1 ) ⊤ ; . . . ; φ(x n ) ⊤ ] Build the empirical transition matrix P : Pi j = I { j = i + 1, j = n} Build matrix A = Φ ⊤ (I -γ P)Φ Build vector b = Φ ⊤ r Return the pathwise LSTD solution α = A + b
of the empirical operator Π T , where T : R n → R n is the pathwise Bellman operator defined as

( T y) t = r t + γy t+1 1 ≤ t < n, r t t = n.
Note that by defining the operator P : R n → R n as ( Py) t = y t+1 for 1 ≤ t < n and ( Py) n = 0, we have T y = r + γ Py. The motivation for using the pathwise Bellman operator is that it is γ-contraction in ℓ 2 -norm, that is, for any y, z ∈ R n , we have

|| T y -T z|| 2 n = ||γ P(y -z)|| 2 n ≤ γ 2 ||y -z|| 2 n .
Since the orthogonal projection Π is non-expansive w.r.t. ℓ 2 -norm, from Banach fixed point theorem, there exists a unique fixed-point v of the mapping Π T , that is, v = Π T v. Since v is the unique fixed point of Π T , the vector v -T v is perpendicular to the space F n , and thus, Φ ⊤ ( v -T v) = 0. By replacing v with Φα, we obtain Φ ⊤ Φα = Φ ⊤ (r +γ PΦα) and then Φ ⊤ (I -γ P)Φα = Φ ⊤ r. Therefore, by setting A = Φ ⊤ (I -γ P)Φ and b = Φ ⊤ r, we recover a d × d system of equations Aα = b similar to the one in the original LSTD algorithm. Note that since the fixed point v exists, this system always has at least one solution. We call the solution with minimal norm, α = A + b, where A + is the Moore-Penrose pseudo-inverse of A, the pathwise LSTD solution. 1Finally, notice that the algorithm reported in Figure 1 may be easily extended to the incremental version of LSTD by incrementally building the inverse of the matrix A as the samples are collected.

Markov Design Bound

In Section 3, we defined the pathwise Bellman operator with a slight modification in the definition of the empirical Bellman operator T , and showed that the operator Π T always has a unique fixed point v. In this section, we derive a bound for the performance of v evaluated at the states of the trajectory used by the pathwise LSTD algorithm. We first state the main theorem and we discuss it in a number of remarks. The proofs are postponed at the end of the section.

Theorem 1 Let X 1 , . . . , X n be a trajectory generated by the Markov chain, and v, v ∈ R n be the vectors whose components are the value function and the pathwise LSTD solution at {X t } n t=1 , respectively. Then with probability at least 1 -δ (the probability is w.r.t. the random trajectory), we have

||v -v|| n ≤ 1 1 -γ 2 ||v -Πv|| n + 1 1 -γ γV max L d ν n 8 log(2d/δ) n + 1 n , ( 1
)
where the random variable ν n is the smallest strictly-positive eigenvalue of the sample-based Gram matrix 1 n Φ ⊤ Φ. d,n) on the prediction error and it provides insights about how to tune some parameters. We first notice that the bound suggests that the number of samples n should be significantly bigger than the number of features d in order to achieve a small estimation error. Furthermore, the bound can be used to estimate the number of samples needed to guarantee a desired prediction error ε. In fact, apart from the approximation error, which is unavoidable, we have that n = O(d/((1 -γ) 2 ε 2 )) samples are enough to achieve an ε-accurate approximation of the true value function v. We also remark that one might be tempted to reduce the dimensionality d, so as to reduce the sample cost of the algorithm. Nonetheless, this is likely to reduce the approximation capability of F and thus increase the approximation error.

Remark 2 When the eigenvalues of the sample-based Gram matrix 1 n Φ ⊤ Φ are all non-zero, Φ ⊤ Φ is invertible, and thus, Π = Φ(Φ ⊤ Φ) -1 Φ ⊤ . In this case, the uniqueness of v implies the uniqueness of α since

v = Φα =⇒ Φ ⊤ v = Φ ⊤ Φα =⇒ α = (Φ ⊤ Φ) -1 Φ ⊤ v.
On the other hand, when the sample-based Gram matrix 1 n Φ ⊤ Φ is not invertible, the system Ax = b may have many solutions. Among all the possible solutions, one may choose the one with minimal norm: α = A + b.

Remark 3 Note that in case there exists a constant ν > 0, such that with probability 1 -δ ′ all the eigenvalues of the sample-based Gram matrix are lower-bounded by ν, Equation 1 (with ν n replaced by ν) holds with probability at least 1 -(δ + δ ′ ) (see Section 5.1 for a case in which such constant ν can be computed and it is related to the smallest eigenvalue of the model based Gram matrix).

Remark 4 Theorem 1 provides a bound without any reference to the stationary distribution of the Markov chain. In fact, the bound of Equation 1 holds even when the chain does not admit a stationary distribution. For example, consider a Markov chain on the real line where the transitions always move the states to the right, that is, p(X t+1 ∈ dy|X t = x) = 0 for y ≤ x. For simplicity assume that the value function V is bounded and belongs to F . This Markov chain is not recurrent, and thus, does not have a stationary distribution. We also assume that the feature vectors φ(X 1 ), . . . , φ(X n ) are sufficiently independent, so that all the eigenvalues of 1 n Φ ⊤ Φ are greater than ν > 0. Then according to Theorem 1, pathwise LSTD is able to estimate the value function at the samples at a rate O(1/ √ n). This may seem surprising because at each state X t the algorithm is only provided with a noisy estimation of the expected value of the next state. However, the estimates are unbiased conditioned on the current state, and we will see in the proof that using a concentration inequality for martingale, pathwise LSTD is able to learn a good estimate of the value function at a state X t using noisy pieces of information at other states that may be far away from X t . In other words, learning the value function at a given state does not require making an average over many samples close to that state. This implies that LSTD does not require the Markov chain to possess a stationary distribution.

Remark 5

The most critical part of the bound in Equation 1 is the inverse dependency on the smallest positive eigenvalue ν n . A similar dependency is shown in the LSTD analysis of [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. The main difference is that here we have a more complete finite-sample analysis with an explicit dependency on the number of samples and the other characteristic parameters of the problem. Furthermore, if the Markov chain admits a stationary distribution ρ, we are able to relate the existence of the LSTD solution to the smallest eigenvalue of the Gram matrix defined according to ρ (see Section 5.1).

In order to prove Theorem 1, we first introduce the regression setting with Markov design and then state and prove a lemma about this model. [START_REF] Delattre | Nonparametric regression with martingale increment errors[END_REF] recently analyzed a similar setting in the general case of martingale incremental errors.

Definition 2

The model of regression with Markov design is a regression problem where the data (X t ,Y t ) 1≤t≤n are generated according to the following model: X 1 , . . . , X n is a sample path generated by a Markov chain, Y t = f (X t ) + ξ t , where f is the target function, and the noise term ξ t is a random variable which is adapted to the filtration generated by X 1 , . . . , X t+1 and is such that

|ξ t | ≤ C and E[ξ t |X 1 , . . . , X t ] = 0.
(2)

The next lemma reports a risk bound for the Markov design setting which is of independent interest.

Lemma 3 (Regression bound for the Markov design setting)

We consider the model of regression with Markov design in Definition 2. Let ŵ ∈ F n be the least-squares estimate of the (noisy) values Y = {Y t } n t=1 , that is, ŵ = ΠY , and w ∈ F n be the least-squares estimate of the (noiseless) values Z = {Z t = f (X t )} n t=1 , that is, w = ΠZ. Then for any δ > 0, with probability at least 1 -δ (the probability is w.r.t. the random sample path X 1 , . . . , X n ), we have

|| ŵ -w|| n ≤ CL 2d log(2d/δ) nν n , ( 3
)
where ν n is the smallest strictly-positive eigenvalue of the sample-based Gram matrix 1 n Φ ⊤ Φ.

Proof [Lemma 3] We define ξ ∈ R n to be the vector with components ξ t = Y t -Z t , and ξ = ŵw = Π(Y -Z) = Πξ. Since the projection is orthogonal we have ξ, ξ n = || ξ|| 2 n (see Figure 1). Since ξ ∈ F n , there exists at least one α ∈ R d such that ξ = Φα, so by Cauchy-Schwarz inequality we have

|| ξ|| 2 n = ξ, ξ n = 1 n d ∑ i=1 α i n ∑ t=1 ξ t ϕ i (X t ) ≤ 1 n ||α|| 2 d ∑ i=1 n ∑ t=1 ξ t ϕ i (X t ) 2 1/2 . ( 4
)
Now among the vectors α such that ξ = Φα, we define α to be the one with minimal ℓ 2 -norm, that is, α = Φ + ξ. Let K denote the null-space of Φ, which is also the null-space of 1 n Φ ⊤ Φ. Then α may be decomposed as α = αK + αK ⊥ , where αK ∈ K and αK ⊥ ∈ K ⊥ , and because the decomposition is orthogonal, we have

|| α|| 2 2 = || αK || 2 2 + || αK ⊥ || 2 2 .
Since α is of minimal norm among all the vectors α such that ξ = Φα, its component in K must be zero, thus α ∈ K ⊥ .

The Gram matrix 1 n Φ ⊤ Φ is positive-semidefinite, thus its eigenvectors corresponding to zero eigenvalues generate K and the other eigenvectors generate its orthogonal complement K ⊥ . Therefore, from the assumption that the smallest strictly-positive eigenvalue of

1 n Φ ⊤ Φ is ν n , we deduce that since α ∈ K ⊥ , || ξ|| 2 n = 1 n α⊤ Φ ⊤ Φ α ≥ ν n α⊤ α = ν n || α|| 2 2 .
(5)

By using the result of Equation 5in Equation 4, we obtain

|| ξ|| n ≤ 1 n √ ν n d ∑ i=1 n ∑ t=1 ξ t ϕ i (X t ) 2 1/2 . ( 6
)
Now, from the conditions on the noise in Equation 2, we have that for any i = 1, . . . , d

E[ξ t ϕ i (X t )|X 1 , . . . , X t ] = ϕ i (X t )E[ξ t |X 1 , . . . , X t ] = 0,
and since ξ t ϕ i (X t ) is adapted to the filtration generated by X 1 , . . . , X t+1 , it is a martingale difference sequence w.r.t. that filtration. Thus one may apply Azuma's inequality to deduce that with probability 1 -δ,

n ∑ t=1 ξ t ϕ i (X t ) ≤ CL 2n log(2/δ) ,
where we used that |ξ t ϕ i (X t )| ≤ CL for any i and t. By a union bound over all features, we have that with probability 1 -δ, for all 1

≤ i ≤ d n ∑ t=1 ξ t ϕ i (X t ) ≤ CL 2n log(2d/δ) . (7)
The result follows by combining Equations 7 and 6.

T v v F n Πv T v Π T v v = Π T v Figure 2:
This figure represents the space R n , the linear vector subspace F n and some vectors used in the proof of Theorem 1.

Remark about Lemma 3

Note that this lemma is an extension of the bound for regression with deterministic design in which the states, {X t } n t=1 , are fixed and the noise terms, ξ t 's, are independent. In deterministic design, usual concentration results provide high probability bounds similar to Equation 3 (see, e.g., [START_REF] Hsu | Random design analysis of ridge regression[END_REF], but without the dependence on ν n . An open question is whether it is possible to remove ν n in the bound for the Markov design regression setting.

In the Markov design model considered in this lemma, states {X t } n t=1 are random variables generated according to the Markov chain and the noise terms ξ t may depend on the next state X t+1 (but should be centered conditioned on the past states X 1 , . . . , X t ). This lemma will be used in order to prove Theorem 1, where we replace the target function f with the value function V , and the noise term ξ t with the temporal difference r(X t ) + γV (X t+1 ) -V (X t ).

Proof [Theorem 1]

Step 1: Using the Pythagorean theorem and the triangle inequality, we have (see Figure 2)

||v -v|| 2 n = ||v -Πv|| 2 n + || v -Πv|| 2 n ≤ ||v -Πv|| 2 n + || v -Π T v|| n + || Π T v -Πv|| n 2 . ( 8
)
From the γ-contraction of the operator Π T and the fact that v is its unique fixed point, we obtain

|| v -Π T v|| n = || Π T v -Π T v|| n ≤ γ|| v -v|| n , (9)
Thus from Equation 8and 9, we have

||v -v|| 2 n ≤ ||v -Πv|| 2 n + γ||v -v|| n + || Π T v -Πv|| n 2 . ( 10
)
Step 2: We now provide a high probability bound on || Π T v -Πv|| n . This is a consequence of Lemma 3 applied to the vectors Y = T v and Z = v. Since v is the value function at the points

{X t } n t=1
, from the definition of the pathwise Bellman operator, we have that for 1 ≤ t ≤ n -1,

ξ t = y t -v t = r(X t ) + γV (X t+1 ) -V (X t ) = γ V (X t+1 ) -P(dy|X t )V (y) ,
and ξ n = y nv n = -γ P(dy|X n )V (y). Thus, Equation 2 holds for 1 ≤ t ≤ n -1. Here we may choose C = 2γV max for a bound on ξ t , 1 ≤ t ≤ n -1, and C = γV max for a bound on ξ n . Azuma's inequality may be applied only to the sequence of n -1 terms (the n-th term adds a contribution to the bound), thus instead of Equation 7, we obtain

n ∑ t=1 ξ t ϕ i (X t ) ≤ γV max L 2 2n log(2d/δ) + 1 ,
with probability 1-δ, for all 1 ≤ i ≤ d. Combining with Equation 6, we deduce that with probability 1 -δ, we have

|| Π T v -Πv|| n ≤ γV max L d ν n 8 log(2d/δ) n + 1 n , ( 11
)
where ν n is the smallest strictly-positive eigenvalue of 1 n Φ ⊤ Φ. The claim follows by solving Equation 10 for ||v -v|| n and replacing || Π T v -Πv|| n from Equation 11.

Generalization Bounds

As we pointed out earlier, Theorem 1 makes no assumption on the existence of the stationary distribution of the Markov chain. This generality comes at the cost that the performance is evaluated only at the states visited by the Markov chain and no generalization on other states is possible.

However in many problems of interest, the Markov chain has a stationary distribution ρ, and thus, the performance may be generalized to the whole state space under the measure ρ. Moreover, if ρ exists, it is possible to derive a condition for the existence of the pathwise LSTD solution depending on the number of samples and the smallest eigenvalue of the Gram matrix defined according to ρ ; G ∈ R d×d , G i j = ϕ i (x)ϕ j (x)ρ(dx). In this section, we assume that the Markov chain M π is exponentially fast β-mixing with parameters β, b, κ, that is, its β-mixing coefficients satisfy β i ≤ β exp(-bi κ ) (see Section A.2 in the appendix for a more detailed definition of β-mixing processes). Before stating the main results of this section, we introduce some notation. If ρ is the stationary distribution of the Markov chain, we define the orthogonal projection operator Π : B(X

;V max ) → F as ΠV = arg min f ∈F ||V -f || ρ .
Furthermore, in the rest of the paper with a little abuse of notation, we replace the empirical norm

||v|| n defined on states X 1 , . . . , X n by ||V || n , where V ∈ B(X ;V max ) is such that V (X t ) = v t .
Finally, we should guarantee that the pathwise LSTD solution V is uniformly bounded on X . For this reason, we move from F to the truncated space F in which for any function f ∈ F , a truncated function f is defined as

f (x) = f (x) if | f (x)| ≤ V max , sgn f (x) V max otherwise. ( 12
)
In the next sections, we present conditions on the existence of the pathwise LSTD solution and derive generalization bounds under different assumptions on the way the samples X 1 , . . . , X n are generated.

Uniqueness of Pathwise LSTD Solution

In this section, we assume that all the eigenvalues of G are strictly positive; that is, we assume the existence of the model-based solution of LSTD, and derive a condition to guarantee that the samplebased Gram matrix 1 n Φ ⊤ Φ is invertible. More specifically, we show that if a large enough number of samples (depending on the smallest eigenvalue of G) is available, then the smallest eigenvalue of 1 n Φ ⊤ Φ is strictly positive with high probability. Lemma 4 Let G be the Gram matrix defined according to the distribution ρ and ω > 0 be its smallest eigenvalue. Let X 1 , . . . , X n be a trajectory of length n of a stationary β-mixing process with parameters β, b, κ and stationary distribution ρ. If the number of samples n satisfies the following condition d+1) , β} , then with probability 1δ, the family of features (ϕ 1 , . . . , ϕ d ) is linearly independent on the states X 1 , . . . , X n (i.e., || f α || n = 0 implies α = 0) and the smallest eigenvalue ν n of the sample-based Gram matrix

n > 288L 2 Λ(n, d, δ) ω max Λ(n, d, δ) b , 1 1/κ , ( 13
)
where 2 Λ(n, d, δ) = 2(d + 1) log n + log e δ + log + max{18(6e) 2(
1 n Φ ⊤ Φ satisfies √ ν n ≥ √ ν = √ ω 2 -6L 2Λ(n, d, δ) n max Λ(n, d, δ) b , 1 1/κ > 0 . ( 14
)
Proof From the definition of the Gram matrix and the fact that ω > 0 is its smallest eigenvalue, for any function f α ∈ F , we have

|| f α || 2 ρ = ||φ ⊤ α|| 2 ρ = α ⊤ Gα ≥ ωα ⊤ α = ω||α|| 2 . ( 15
)
Using the concentration inequality from Corollary 18 in the appendix and the fact that the basis functions ϕ i are bounded by L, thus f α is bounded by L||α||, we have

|| f α || ρ -2|| f α || n ≤ ε with probability 1 -δ, where ε = 12L α 2Λ(n, d, δ) n max Λ(n, d, δ) b , 1 1/κ . Thus we obtain 2|| f α || n + ε ≥ √ ω||α||. (16)
Let α be such that || f α || n = 0, then if the number of samples n satisfies the condition of Equation 13, we may deduce from Equation 16and the definition of ε that α = 0. This indicates that given Equation 13, with probability 1 -δ, the family of features (ϕ 1 , . . . , ϕ d ) is linearly independent on the states X 1 , . . . , X n , and thus, ν n > 0. The inequality in Equation 14 is obtained by choosing α to be the eigenvector of 1 n Φ ⊤ Φ corresponding to the smallest eigenvalue ν n . For this value of α, we have || f α || n = √ ν n ||α||. By using the definition of ε in Equation 16 and reordering we obtain

2 √ ν n ||α|| + 12L||α|| 2Λ(n, d, δ) n max Λ(n, d, δ) b , 1 1/κ ≥ √ ω||α|| ,
and the claim follows.

Remark 1 In order to make the condition on the number of samples and its dependency on the critical parameters of the problem at hand more explicit, let us consider the case of a stationary process with b = β = κ = 1. Then the condition in Equation 13 becomes (up to constant and logarithmic factors)

n ≥ O 288L 2 ω (d + 1) log n δ 2 .
As can be seen, the number of samples needed to have strictly positive eigenvalues in the samplebased Gram matrix has an inverse dependency on the smallest eigenvalue of G. As a consequence, the more G is ill-conditioned the more samples are needed for the sample-based Gram matrix 1 n Φ ⊤ Φ to be invertible.

Generalization Bounds for Stationary β-mixing Processes

In this section, we show how Theorem 1 may be generalized to the entire state space X when the Markov chain M π has a stationary distribution ρ. In particular, we consider the case in which the samples X 1 , . . . , X n are obtained by following a single trajectory in the stationary regime of M π , that is, when we consider that X 1 is drawn from ρ.

Theorem 5 Let X 1 , . . . , X n be a path generated by a stationary β-mixing process with parameters β, b, κ and stationary distribution ρ. Let ω > 0 be the smallest eigenvalue of the Gram matrix defined according to ρ and n satisfy the condition in Equation 13. Let V be the truncation (using Equation 12) of the pathwise LSTD solution, then

|| V -V || ρ ≤ 2 1 -γ 2 2 √ 2||V -ΠV || ρ + ε 2 + 2 1 -γ γV max L d ν 8 log (8d/δ) n + 1 n + ε 1 (17)
with probability 1 -δ, where ν is a lower-bound on the eigenvalues of the sample-based Gram matrix defined by Equation 14, d+1) , β} , and

ε 1 = 24V max 2Λ 1 (n, d, δ/4) n max Λ 1 (n, d, δ/4) b , 1 1/κ , with Λ 1 (n, d, δ/4) = 2(d + 1) log n + log 4e δ + log + max{18(6e) 2(
ε 2 = 12 V max + L||α * || 2Λ 2 (n, δ/4) n max Λ 2 (n, δ/4) b , 1 1/κ , ( 18
) with Λ 2 (n, δ/4) = log 4e δ + log max{6, n β} and α * is such that f α * = ΠV .
Proof This result is a consequence of applying generalization bounds to both sides of Equation 1(Theorem 1). We first bound the left-hand side:

2|| V -V || n ≥ 2|| V -V || n ≥ || V -V || ρ -ε 1
with probability 1 -δ ′ . The first step follows from the definition of the truncation operator, while the second step is a straightforward application of Corollary 17 in the appendix.

We now bound the term ||V -ΠV || n in Equation 1:

||V -ΠV || n ≤ ||V -ΠV || n ≤ 2 √ 2||V -ΠV || ρ + ε 2
with probability 1 -δ ′ . The first step follows from the definition of the operator Π. The second step is an application of the inequality of Corollary 19 in the appendix for the function V -ΠV .

From Theorem 1, the two generalization bounds, and the lower-bound on ν, each one holding with probability 1 -δ ′ , the statement of the Theorem (Equation 17) holds with probability 1 -δ by setting δ = 4δ ′ .

Remark 1 Rewriting the bound in terms of the approximation and estimation error terms (up to constants and logarithmic factors), we obtain

|| V -V || ρ ≤ O 1 1 -γ 2 ||V -ΠV || ρ + 1 1 -γ 1 √ n .
While the first term (approximation error) only depends on the target function V and the function space F , the second term (estimation error) primarily depends on the number of samples. Thus, when n goes to infinity, the estimation error goes to zero and we obtain the same performance bound (up to a 4 √ 2 constant) as for the model-based case reported by [START_REF] Tsitsiklis | An analysis of temporal difference learning with function approximation[END_REF]. The additional multiplicative constant 4 √ 2 in front of the approximation error is the standard cost to have the improved rate bounds for the squared loss and linear spaces (see, e.g., [START_REF] Györfi | A Distribution-free Theory of Nonparametric Regression[END_REF]. In fact, it is possible to derive a bounds with constant 1 but a worse rate n -1/4 instead of n -1/2 . The bound in Theorem 5 is more accurate whenever the approximation error is small and few samples are available.

Remark 2 [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] reported a sample-based analysis for the modified Bellman residual (MBR) minimization algorithm. They consider a general setting in which the function space F is bounded and the performance of the algorithm is evaluated according to an arbitrary measure µ (possibly different than the stationary distribution of the Markov chain ρ). Since [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] showed that the MBR minimization algorithm is equivalent to LSTD when F is a linearly parameterized space, it would be interesting to compare the bound in Theorem 5 to the one in Lemma 11 of [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF]. In Theorem 5, similar to [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF], samples are drawn from a stationary β-mixing process, however, F is a linear space and ρ is the stationary distribution of the Markov chain. It is interesting to note the impact of these two differences in the final bound. The use of linear spaces has a direct effect on the estimation error and leads to a better convergence rate due to the use of improved functional concentration inequalities (Lemma 16 in the appendix). In fact, while in [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] the estimation error for the squared error is of order O(1/ √ n), here we achieve a faster convergence rate of order O(1/n). Moreover, although [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] showed that the solution of MBR minimization coincides with the LSTD solution, its sample-based analysis cannot be directly applied to LSTD. In fact, in [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] the function space F is assumed to be bounded, while general linear spaces cannot be bounded. Whether the analysis of [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] may be extended to the truncated solution of LSTD is an open question that requires further investigation.

Generalization Bounds for Markov Chains

The main assumption in the previous section is that the trajectory X 1 , . . . , X n is generated by a stationary β-mixing process with stationary distribution ρ. This is possible if we consider samples of a Markov chain during its stationary regime, that is, X 1 ∼ ρ. However in practice, ρ is not known, and the first sample X 1 is usually drawn from a given initial distribution and the rest of the sequence is obtained by following the Markov chain from X 1 on. As a result, the sequence X 1 , . . . , X n is no longer a realization of a stationary β-mixing process. Nonetheless, under suitable conditions, after ñ < n steps, the distribution of X ñ approaches the stationary distribution ρ. In fact, according to the convergence theorem for fast-mixing Markov chains (see, e.g., Proposition 20 in the appendix), for any initial distribution λ ∈ S(X ), we have

X λ(dx)P n (•|x) -ρ(•) TV ≤ β exp(-bn κ ).
where || • || TV is the total variation. 3We now derive a bound for a modification of pathwise LSTD in which the first ñ samples (that are used to burn the chain) are discarded and the remaining nñ samples are used as training samples for the algorithm.

Theorem 6 Let X 1 , . . . , X n be a trajectory generated by a β-mixing Markov chain with parameters β, b, κ and stationary distribution ρ. Let ñ (1 ≤ ñ < n) be such that nñ satisfies the condition of Equation 13, and X ñ+1 , . . . , X n be the samples actually used by the algorithm. Let ω > 0 be the smallest eigenvalue of the Gram matrix defined according to ρ and α * ∈ R d be such that f α * = ΠV . Let V be the truncation of the pathwise LSTD solution (using Equation 12), then by setting ñ = 1 b log 2e βn δ 1/κ , with probability 1 -δ, we have

|| V -V || ρ ≤ 2 1 -γ 2 2 √ 2||V -ΠV || ρ + ε 2 + 2 1 -γ γV max L d ν 8 log (8d/δ) n - ñ + 1 ñ + ε 1 , (19
) where ε 1 and ε 2 are defined as in Theorem 5 (with nñ as the number of training samples).

The proof of this result is a simple consequence of Lemma 24 in the appendix applied to Theorem 5. 19indicates that in the case of β-mixing Markov chains, a similar performance to the one for stationary β-mixing processes is obtained by discarding the first ñ = O(log n) samples.

Remark 1 The bound in Equation

Finite-Sample Analysis of LSPI

In the previous sections we studied the performance of pathwise-LSTD for policy evaluation. Now we move to the analysis of the least-squares policy iteration (LSPI) algorithm [START_REF] Lagoudakis | Least-squares policy iteration[END_REF] in which at each iteration k samples are collected by following a single trajectory of the policy under evaluation, π k , and LSTD is used to compute an approximation of V π k . In particular, in the next section we report a performance bound by comparing the value of the policy returned by the algorithm after K iterations, V π K , and the optimal value function, V * , w.r.t. an arbitrary target distribution σ. In order to achieve this bound we introduce assumptions on the MDP and the linear space F . In Section 6.2 we show that in some cases one of these assumptions does not hold and the performance of LSPI can be arbitrarily bad.

Generalization Bound for LSPI

In this section, we provide a performance bound for the LSPI algorithm [START_REF] Lagoudakis | Least-squares policy iteration[END_REF]. We first introduce the greedy policy operator G that maps value functions to their corresponding greedy policies:

G(V ) (x) = arg max a∈A r(x, a) + γ X P(dy|x, a)V (y) .
We use G(F ) to refer to the set of all the greedy policies w.r.t. the functions in F . LSPI is a policy iteration algorithm that uses LSTD for policy evaluation at each iteration. It starts with an arbitrary initial value function V -1 ∈ F and its corresponding greedy policy π 0 . At the first iteration, it approximates V π 0 using LSTD and returns a function V 0 whose truncated version V 0 is used to build the policy π 1 for the second iteration. 4 More precisely, π 1 is the greedy policy w.r.t. V 0 , that is,

π 1 = G( V 0 )
. So, at each iteration k of LSPI, a function V k-1 is computed as an approximation to V π k-1 , and then truncated, V k-1 , and used to build the policy π k = G( V k-1 ). Note that the MDP model is needed in order to generate the greedy policy π k . To avoid the need for the model, we could simply move from LSTD to LSTD-Q. The analysis of LSTD in the previous sections may be easily extended to action-value function, and thus, to LSTD-Q. 5 For simplicity we use value function in the paper and report the LSPI bound in terms of the distance to the optimal value function.

It is important to note that in general the measure used to evaluate the final performance of LSPI, σ ∈ S(X ), might be different than the distribution used to generate the samples at each iteration. Moreover, the LSTD performance bounds of Section 5 require the samples to be collected by following the policy under evaluation. Thus, we make the following assumption.

Assumption 1 (Lower-bounding distribution) There exists a distribution µ ∈ S(X ) such that for any policy π that is greedy w.r.t. a function in the truncated space F , µ ≤ Cρ π , where C < ∞ is a constant and ρ π is the stationary distribution of policy π. 4. Unlike in the original formulation of LSPI, here we need to explicitly truncate the function so as to prevent unbounded functions. 5. We point out that moving to LSTD-Q requires the introduction of some exploration to the current policy. In fact, in the on-policy setting, if the policy under evaluation is deterministic, it does not provide any information about the value of actions a = π(•) and the policy improvement step would always fail. Thus, we need to consider stochastic policies where the current policy is perturbed by an ε > 0 randomization which guarantees that any action has a non-zero probability to be selected in any state.

We define the second-order discounted-average concentrability of future-state distributions as

C σ,µ = (1 -γ) 2 ∑ m≥1 mγ m-1 c σ,µ (m)
and we assume that C σ,µ < ∞.

We also need to guarantee that with high probability a unique LSTD solution exists at each iteration of the LSPI algorithm, thus, we make the following assumption.

Assumption 3 (Linear independent features) Let µ ∈ S(X ) be the lower-bounding distribution from Assumption 1. We assume that the features φ(•) of the function space F are linearly independent w.r.t. µ. In this case, the smallest eigenvalue ω µ of the Gram matrix G µ ∈ R d×d w.r.t. µ is strictly positive.

Lemma 7 Under Assumption 3, at each iteration k of LSPI, the smallest eigenvalue ω k of the Gram matrix G k defined according to the stationary distribution ρ k = ρ π k is strictly positive and ω k ≥

ω µ C .
Proof Similar to Lemma 4, for any function

f α ∈ F , we have ||α|| ≤ || f α || µ √ ω µ . Using Assumption 1, || f α || µ ≤ √ C || f α || ρ k , and thus, ||α|| ≤ C ω µ || f α || ρ k . For the α that is the eigenvector of G k corre- sponding to ρ k , we have ||α|| = || f α || ρ k √ ω k .
For this value of α, we may write

|| f α || ρ k √ ω k ≤ C ω µ || f α || ρ k , and thus, ω k ≥ ω µ
C , which guarantees that ω k is strictly positive, because ω µ is strictly positive according to Assumption 3. Finally, we make the following assumption on the stationary β-mixing processes corresponding to the stationary distributions of the policies encountered at the iterations of the LSPI algorithm.

Assumption 4 (Slower β-mixing process) We assume that there exists a stationary β-mixing process with parameters β, b, κ, such that for any policy π that is greedy w.r.t. a function in the truncated space F , it is slower than the stationary β-mixing process with stationary distribution ρ π (with parameters βπ , b π , κ π ). This means that β is larger and b and κ are smaller than their counterparts βπ , b π , and κ π (see Definition 14). Now we may state the main theorem of this section.

Theorem 8 Let us assume that at each iteration k of the LSPI algorithm, a path of size n is generated from the stationary β-mixing process with stationary distribution ρ k-1 = ρ π k-1 . Let n satisfy the condition in Equation 13for the slower β-mixing process defined in Assumption 4. Let V -1 ∈ F be an arbitrary initial value function, V 0 , . . . ,V K-1 ( V 0 , . . . , V K-1 ) be the sequence of value functions (truncated value functions) generated by LSPI after K iterations, and π K be the greedy policy w.r.t. the truncated value function V K-1 . Then under Assumptions 1-4, with probability 1 -δ (w.r.t. the random samples), we have

||V * -V π K || σ ≤ 4γ (1 -γ) 2 (1 + γ) CC σ,µ 2 1 -γ 2 2 √ 2E 0 (F ) + E 2 + 2 1 -γ γV max L d ν µ 8 log(8dK/δ) n + 1 n + E 1 + γ K-1 2 R max , where 1. E 0 (F ) = sup π∈G ( F ) inf f ∈F || f -V π || ρ π ,
2. E 1 is ε 1 from Theorem 5 written for the slower β-mixing process defined in Assumption 4,

3. E 2 is ε 2 from Theorem 5 written for the slower β-mixing process defined in Assumption 4 and ||α * || replaced by C ω µ R max 1-γ , and 4. ν µ is ν from Equation 14in which ω is replaced by ω µ defined in Assumption 3, and the second term is written for the slower β-mixing process defined in Assumption 4.

Remark 1

The previous theorem states a bound on the prediction error when LSPI is stopped after a fixed number K of iterations. The structure of the bound resembles the one in [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF].

Unlike policy evaluation, the approximation error E 0 (F ) now depends on how well the space F can approximate the target functions V π obtained in the policy improvement step. While the estimation errors are mostly similar to those in policy evaluation, an additional term of order γ K is introduced. Finally, we notice that the concentrability terms may significantly amplify the prediction error (see also next remark). [START_REF] Farahmand | Error propagation for approximate policy and value iteration[END_REF] recently performed a refined analysis of the propagation of the error in approximate policy iteration and have interesting insights on the concentrability terms.

Remark 2

The most critical issue about Theorem 8 is the validity of Assumptions 1-4. The analysis of LSTD explicitly requires that the samples are collected by following the policy under evaluation, π k , and the performance is bounded according to its stationary distribution ρ k . Since the performance of LSPI is assessed w.r.t. a target distribution σ, we need each of the policies encountered through the LSPI process to have a stationary distribution which does not differ too much from σ. Furthermore, since the policies are random (at each iteration k the new policy π k is greedy w.r.t. the approximation V k-1 which is random because of the sampled trajectory), we need to consider the distance of σ and the stationary distribution of any possible policy generated as greedy w.r.t. a function in the truncated space F , that is, ρ π , π ∈ G( F ). Thus in Assumption 1 we first assume the existence of a distribution µ lower-bounding any possible stationary distribution ρ k . The existence of µ and the value of the constant C depend on the MDP at hand. In Section 6.2, we provide an example in which the constant C is infinite. In this case, we show that the LSPI performance, when the samples at each iteration are generated according to the stationary distribution of the policy under evaluation, can be arbitrarily bad. A natural way to relax this assumption would be the use of off-policy LSTD in which the samples are collected by following a behavior policy. Nonetheless, we are not aware of any finite-sample analysis for such an algorithm. Another critical term appearing in the bound of LSPI, inherited from Theorem 5, is the maximum of ||α * k || over the iterations, where

α * k is such that f α * k = Π ρ k V π k . Each term ||α * k
|| can be bounded whenever the features of the space F are linearly independent according to the stationary distribution ρ k . Since α * k is a random variable, the features {ϕ i } d i=1 of the space F should be carefully chosen so as to be linearly independent w.r.t. the lower-bounding distribution µ.

We now prove a lemma that is used in the proof of Theorem 8.

Lemma 9 Let π k be the greedy policy w.r.

t. V k-1 , that is, π k = G( V k-1
) and ρ π k be the stationary distribution of the Markov chain induced by π k . We have

|| V k -T π k V k || ρ π k ≤ (1 + γ)|| V k -V π k || ρ π k . Proof [Lemma 9] We first show that V k -T π k V k = (I -γP π k )( V k -V π k ) (I -γP π k )( V k -V π k ) = V k -V π k -γP π k V k + γP π k V π k = V k -V π k -T π k V k + T π k V π k = V k -V π k -T π k V k +V π k = V k -T π k V k .
For any distribution σ ∈ S(X ), we may write

|| V k -T π k V k || σ = ||(I -γP π k )( V k -V π k )|| σ ≤ ||I -γP π k || σ || V k -V π k || σ ≤ 1 + γ||P π k || σ || V k -V π k || σ If σ is the stationary distribution of π k , that is, σ = ρ π k , then ||P π k || σ =
||V * -V π K || σ ≤ 4γ (1 -γ) 2 C σ,µ max 0≤k<K || V k -T π k V k || µ + γ K-1 2 R max . ( 20
)
From Assumption 1, we know that || • || µ ≤ √ C|| • || ρ k for any 0 ≤ k < K and thus we may rewrite Equation 20as

||V * -V π K || σ ≤ 4γ (1 -γ) 2 CC σ,µ max 0≤k<K || V k -T π k V k || ρ k + γ K-1 2 R max . (21)
Using the result of Lemma 9, Equation 21 may be rewritten as

||V * -V π K || σ ≤ 4γ (1 -γ) 2 (1 + γ) CC σ,µ max 0≤k<K || V k -V π k || ρ k + γ K-1 2 R max . ( 22
)
We can now use the result of Theorem 5 (which holds with probability δ/K) and replace || V k -V π k || ρ k with its upper-bound. The next step would be to apply the maximum over k to this upperbound (the right hand side of Equation 17). There are four terms on the r.h.s. of Equation 17 that depend on k and in following we find a bound for each of them.

1.

||V π k -Π ρ k V π k || ρ k :
This term can be upper-bounded by E 0 (F ). This quantity, E 0 (F ), measures the approximation power of the linear function space F .

2. ε 1 : This term only depends on the parameters βk , b k , κ k of the stationary β-mixing process with stationary distribution ρ k . Using Assumption 4, this term can be upper-bounded by E 1 , which is basically ε 1 written for the slower β-mixing process from Assumption 4.

3. ε 2 : This term depends on the following k-related terms.

6. The slight difference between Equation 20 and the bound in Lemma 12 of [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] is due to a small error in Equation 26of [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF]. It can be shown that the r.h.s. of Equation 26 in [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF] is not an upper-bound for the r.h.s. of its previous equation. This can be easily fixed by redefining the coefficients α k while we make sure that they remain positive and still sum to one. This modification causes two small changes in the final bound: the constant 2 in front of the parenthesis becomes 4 and the power of the γ in front of R max changes from K/p to (K -1)/p.

• The term under the root-square in Equation 18: This term depends on the parameters βk , b k , κ k of the stationary β-mixing process with stationary distribution ρ k . Similar to ε 1 , this term can be upper-bounded by rewriting it for the slower β-mixing process from Assumption 4.

• α * k : The coefficient vector α * k is such that f α * k = Π ρ k V π k .
This term can be upper-bounded as follows: ω k : This is the smallest eigenvalue of the Gram matrix G k defined according to the distribution ρ k . From Lemma 7, this term can be lower-bounded by ω µ .

||α * k || (a) ≤ || f α * || µ √ ω µ (b) ≤ C ω µ || f α * || ρ k = C ω µ ||Π ρ k V π k || ρ k (c) ≤ C ω µ ||V π k || ρ k ≤ C ω µ ||V π k || ∞ = C ω µ V max = C ω µ R max 1 -γ .
• The second term on the r.h.s. of Equation 14: This term depends on the parameters βk , b k , κ k of the stationary β-mixing process with stationary distribution ρ k . Similar to ε 1 and ε 2 , this term can be upper-bounded by rewriting it for the slower β-mixing process from Assumption 4.

By replacing the above lower and upper bounds in Equation 14, we obtain ν µ which is a lower-bound for any ν ρ k .

The claim follows by replacing the bounds for the above four terms in Equation 22.

A Negative Result for LSPI

In the previous section we analyzed the performance of LSPI when at each iteration the samples are obtained from a trajectory generated by following the policy under evaluation. In order to bound the performance of LSPI in Theorem 8, we made a strong assumption on all possible stationary distributions that can be obtained at the iterations of the algorithm. Assumption 1 states the existence of a lower-bounding distribution µ the stationary distribution π of any policy π ∈ G( F ). If such a distribution does not exist (C is infinite), the LSPI performance can no longer be bounded. In other words, this result states that in some MDPs, even if at each iteration the target function

V π k is perfectly approximated by V k under ρ k -norm, that is, ||V π k -V k || ρ k = 0,
the LSPI performance could be arbitrarily bad. In this section we show a very simple MDP in which this is actually the case.

Let consider a finite MDP with X = {x 1 , x 2 , x 3 }, A = {a, b}, and the reward function r and transition model p as illustrated in Figure 3. As it can be noticed only two policies are available in this MDP: π a which takes action a in state x 1 and π b which takes action b in this state. It is easy to verify that the stationary distribution ρ π a assigns probabilities ε 1+ε , 1 1+ε , and 0 to x 1 , x 2 , and x 3 ,

1, 1 x 1 x 2 x 3 a/b b a 0.5, 1 a/b 0, ǫ 0, 1 -ǫ 0, ǫ 0, 1 -ǫ f α * X V π a x 1 x 2 x 3 Figure 3: (left)
The MDP used in the example of Section and (right) the value function for policy π a in this MDP.

while ρ π b has probabilities ε 1+ε , 0, and 1 1+ε . Since ρ π a ρ π b assign a probability 0 to two different states, it is not possible to find a finite constant C such that a distribution µ is lower-bounding both ρ π a and ρ π b , thus, C = ∞ and according to Theorem 8 LSPI may have an arbitrary bad performance.

Let initialize LSPI with the suboptimal policy π a . The value function V π a is shown in Figure 3 (note that the specific values depend on the choice of ε and γ).

Let F = { f α (x) = α 1 x + α 2 , α ∈ R 2 }
be the space of lines in dimension 1. Let α * be the solution to the following minimization problem α * = arg inf α∈R ||V π af α || 2 ρ πa (the projection of π a onto space F ). Since ρ π a assigns a probability 0 to state x 3 , the f α * in Figure 3 has a zero loss, that is, ||V π af α * || ρ πa = 0. Nonetheless, while the greedy policy w.r.t. V π a is the optimal policy π b , the policy improvement step w.r.t. f α * returns the policy π a . As a result, although at each iteration the function space F may accurately approximate the value function of the current policy π w.r.t. its stationary distribution ρ π , LSPI never improves its performance and returns π a instead of the optimal policy π b . By properly setting the rewards we could make the performance of π a arbitrarily worse than π b .

Conclusions

In this paper we presented a finite-sample analysis of the least-squares policy iteration (LSPI) algorithm [START_REF] Lagoudakis | Least-squares policy iteration[END_REF]. This paper substantially extends the analysis in [START_REF] Lazaric | Finite-sample analysis of lstd[END_REF] by reporting all the lemmas used to prove the performance bounds of LSTD in the case of βmixing and Markov chain processes and by analyzing how the performance of LSTD is propagated through iterations in LSPI.

More in detail, we first studied a version of LSTD, called pathwise LSTD, for policy evaluation. We considered a general setting where we do not make any assumption on the Markov chain. We derived an empirical performance bound that indicates how close the LSTD solution is to the value function at the states along a trajectory generated by following the policy and used by the algorithm. The bound is expressed in terms of the best possible approximation of the value function in the selected linear space (approximation error), and an estimation error which depends on the number of samples and the smallest strictly-positive eigenvalue of the sample-based Gram matrix. We then showed that when the Markov chain possesses a stationary distribution, one may deduce generalization performance bounds using the stationary distribution of the chain as the generalization measure. In particular, we considered two cases, where the sample trajectory is generated by stationary and non-stationary β-mixing Markov chains, and derived the corresponding bounds. Finally, we considered the whole policy iteration algorithm (LSPI) and showed that under suitable conditions it is possible to bound the error cumulated through the iterations.

The techniques used for the analysis of LSTD have also been recently employed for the development of the finite-sample analysis of a number of novel algorithms such as LSTD with random projections (Ghavamzadeh et 2010), LassoTD [START_REF] Ghavamzadeh | Finite-sample analysis of lasso-td[END_REF], and Classificationbased Policy Iteration with a Critic [START_REF] Gabillon | Classification-based policy iteration with a critic[END_REF]. Technical issues. From a technical point of view there are two main open issues.

1. Dependency on ν n in the bound of Theorem 1. In Section 4 we introduced the Markov design setting for regression in which the samples are obtained by following a Markov chain and the noise is a zero-mean martingale. By comparing the bound in Lemma 3 with the bounds for least-squares regression in deterministic design (see, e.g., Theorem 11.1 in [START_REF] Györfi | A Distribution-free Theory of Nonparametric Regression[END_REF], the main difference is the inverse dependency on the eigenvalue ν n of the empirical matrix. It is not clear whether this dependency is intrinsic in the process generating the samples or whether it can be removed. [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] recently developed improved Azuma's inequalities for self-normalizing process (see also, e.g., [START_REF] De La Peña | Pseudo-maximization and self-normalized processes[END_REF][START_REF] De La Peña | Exponential inequalities for self-normlized processes with applications[END_REF] which suggest that the bound can be improved by removing the dependency from ν n and, thus, also from the L ∞ -norm L of the features.

2. The log n dependency in the generalization bounds. Chaining techniques [START_REF] Talagrand | The Generic Chaining: Upper and Lower Bounds of Stochastic Processes[END_REF] can be successfully applied to remove the log n dependency in Pollard's inequalities for regression in bounded spaces. An interesting question is whether similar techniques can be applied to the refined analysis for squared losses and linear spaces (see, e.g., Lemma 10) used in our theorems.

Extensions. Some extensions to the current work are possible.

LSTD(λ).

A popular improvement to LSTD is the use of eligibility traces, thus obtaining LSTD(λ). The extension of the results presented in this paper to this setting does not seem to be straightforward since the regression problem solved in LSTD(λ) does not match the Markov design setting introduced in Definition 2. Hence, it is an open question how a finitesample analysis of LSTD(λ) could be derived.

2. Off-policy LSTD. [START_REF] Yu | Error bounds for approximations from projected linear equations[END_REF] derived new bounds for projected linear equations substituting the 1 √ 1-γ 2 term in front of the approximation error with a much sharper term depending on the spectral radius of some matrices defined by the problem. An open question is whether these new bounds can be effectively reused in the finite-sample analysis derived in this paper, thus obtaining much sharper bounds.

3. Joint analysis of BRM and LSTD. Scherrer (2010) recently proposed a unified view of Bellman residual minimization (BRM) [START_REF] Schweitzer | Generalized polynomial approximations in markovian decision processes[END_REF][START_REF] Baird | Residual algorithms: Reinforcement learning with function approximation[END_REF] and temporal difference methods through the notion of oblique projections. This suggests the possibility that the finite-sample analysis of LSTD could be extended to BRM through this unified view over the two methods.

Proposition 11 Let F be a class of linear functions f : X → R of dimension d and F be the class of functions obtained by truncating functions f ∈ F at a threshold B. Then for any sample

X n 1 = {X 1 , . . . , X n } and ε > 0 N 2 ε, F , X n 1 ≤ 3 3e(2B) 2 ε 2 2(d+1)
.

Proof Using Theorem 9.4. in [START_REF] Györfi | A Distribution-free Theory of Nonparametric Regression[END_REF] and the fact that the pseudo-dimension of F is the same as F , we have

N 2 ε, F , X n 1 ≤ 3 2e(2B) 2 ε 2 log 3e(2B) 2 ε 2 d+1 ≤ 3 3e(2B) 2 ε 2 2(d+1)
.

We now use Proposition 11 to invert the bound in Lemma 10 for truncated linear spaces.

Corollary 12 Let F be a class of linear functions f : X → R of dimension d, F be the class of functions obtained by truncating functions f ∈ F at a threshold B, and X n 1 = {X 1 , . . . , X n } be a sequence of i.i.d. samples. By inverting the bound of Lemma 10, for any f ∈ F , we have

f -2 f X n 1 ≤ ε(δ), f X n 1 -2 f ≤ ε(δ), with probability 1 -δ, where ε(δ) = 12B 2Λ(n, d, δ) n , (23)
and Λ(n, d, δ) = 2(d + 1) log n + log e δ + log 9(12e) 2(d+1) . Proof In order to prove the corollary it is sufficient to verify that the following inequality holds for the ε defined in Equation 233E N 2

√ 2 24 ε, F , X 2n 1 exp - nε 2 288B 2 ≤ δ.
Using Proposition 11, we bound the first term as

E N 2 √ 2 24 ε, F , X 2n 1 ≤ 3 C 1 ε 2 2(d+1) , with C 1 = 3456eB 2 . Next we notice that Λ(n, d, δ) ≥ 1 and thus ε ≥ 1/(nC 2 ) with C 2 = (288B 2 ) -1 .
Using these bounds in the original inequality and some algebra we obtain

3E N 2 √ 2 24 ε, F , X 2n 1 exp - nε 2 288B 2 ≤ 9 C 1 ε 2 2(d+1) exp -nC 2 ε 2 ≤ 9 (nC 1 C 2 ) 2(d+1) exp -C 2 n Λ(n, d, δ) nC 2 = 9 (nC 1 C 2 ) 2(d+1) n -2(d+1) δ e 1 9(C 1 C 2 ) 2(d+1) = δ e ≤ δ.
Non-functional versions of Corollary 12 can be simply obtained by removing the covering number from the statement of Lemma 10.

Corollary 13 Let f : X → R be a function bounded in absolute value by B and X n

1 = {X 1 , . . . , X n } be a sequence of i.i.d. samples. Then f -2 f X n 1 ≤ ε(δ), f X n 1 -2 f ≤ ε(δ), with probability 1 -δ, where ε(δ) = 12B 2 n log 3 δ .

A.2 Stationary β-mixing Processes

We first introduce β-mixing stochastic processes and β-mixing coefficients.

Definition 14 Let {X t } t≥1 be a stochastic process. Let X j i = {X i , X i+1 , . . . , X j } and σ(X j i ) denote the sigma-algebra generated by X j i . The i-th β-mixing coefficient of the stochastic process is defined by

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

The process {X t } t≥1 is said to be β-mixing if β i → 0 as i → ∞. In particular, {X t } t≥1 mixes at an exponential rate with parameters β, b, κ if β i ≤ β exp(-bi κ ). Finally, {X t } t≥1 is strictly stationary if X t ∼ ν for any t > 0.

Let X 1 , . . . , X n be a sequence of samples drawn from a stationary β-mixing process with coefficients {β i }. We first introduce the blocking technique of [START_REF] Yu | Rates of convergence for empirical processes of stationary mixing sequences[END_REF]. Let us divide the sequence of samples into blocks of size k n . For simplicity we assume n = 2m n k n with 2m n be the number of blocks. 7 For any 1 ≤ j ≤ m n we define the set of indexes in an odd and even block respectively as

H j = {t : 2( j -1)k n + 1 ≤ t ≤ (2 j -1)k n }, and
E j = {t : (2 j -1)k n + 1 ≤ t ≤ (2 j)k n }.
Let H = ∪ m n j=1 H j and E = ∪ m n j=1 E j be the set of all indexes in the odd and even blocks, respectively. We use X(H j ) = {X t : t ∈ H j } and X(H) = {X t : t ∈ H}. We now introduce a ghost sample X ′ (the size of the ghost sample X ′ is equal to the number of samples in each block k n ) in each of the odd blocks such that the joint distribution of X ′ (H j ) is the same as X(H j ) but independent from any other block. In the following, we also use another ghost sample X ′′ independently generated from the same distribution as X ′ .

Proposition 15 [START_REF] Yu | Rates of convergence for empirical processes of stationary mixing sequences[END_REF] Let X 1 , . . . , X n be a sequence of samples drawn from a stationary βmixing process with coefficients {β i }. Let Q, Q ′ be the distributions of X(H) and X ′ (H), respec-

tively. For any measurable function h

: X m n k n → R bounded by B E Q [h(X(H))] -E Q ′ h(X ′ (H)) ≤ Bm n β k n .
Before moving to the extension of Propsition 10 to β mixing processes, we report this technical lemma.

Lemma 16 Let F be a class of functions f : X → R bounded in absolute value by B and X 1 , . . . , X n be a sequence of samples drawn from a stationary β-mixing process with coefficients {β i }. For any ε > 0

P ∃ f ∈ F : f -2 f X n 1 > ε ≤ 2δ( √ 2ε) + 2m n β k n , (24)
P ∃ f ∈ F : f X n 1 -2 √ 2 f > ε ≤ 2δ( √ 2ε) + 2m n β k n , (25)
where

δ(ε) = 3E N 2 √ 2 24 ε, F , X ′ (H) ∪ X ′′ (H) exp - m n ε 2 288B 2 .
Proof Similar to [START_REF] Meir | Nonparametric time series prediction through adaptive model selection[END_REF], we first introduce F as the class of block functions f :

X k n → R defined as f X(H j ) 2 = 1 k n ∑ t∈H j f (X t ) 2 .
It is interesting to notice that block functions have exactly the same norms as the functions in F . In

fact f 2 X(H) = 1 m n m n ∑ j=1 | f (X(H j ))| 2 = 1 m n m n ∑ j=1 1 k n ∑ t∈H j | f (X t )| 2 = f X(H) , (26)
and

f 2 = E | f (X(H 1 ))| 2 = 1 k n ∑ t∈H 1 E | f (X t )| 2 = E | f (X 1 )| 2 = f , (27)
where in Equation 27, we used the fact that the process is stationary. We now focus on Equation 24

P ∃ f ∈ F : f -2 f X n 1 > ε (a) ≤ P ∃ f ∈ F : f -f X(H) + f X(E) > ε (b) = P ∃ f ∈ F : 1 2 f -2 f X(H) + 1 2 f -2 f X(E) > ε (c) ≤ P ∃ f ∈ F : f -2 f X(H) > 2ε + P ∃ f ∈ F : f -2 f X(E) > 2ε (d) = 2P ∃ f ∈ F : f -2 f X(H) > 2ε (e) ≤ 2 P ∃ f ∈ F : f -2 f X ′ (H) > 2ε + m n β k n (f) ≤ 2δ ′ (2ε) + 2m n β k n .
(a) We used the inequality

√ a + b ≥ 1 √ 2 ( √ a+ √ b) to split the norm f X n 1 ≥ 1 2 f X(H) + f X(E) . (b) Algebra.
(c) Split the probability. (d) (1) Since the process is stationary the distribution over the even blocks is the same as the distribution over the odd blocks. (2) From Equations 26 and 27. (e) Using Proposition 15 with h equals to the indicator function of the event inside the bracket, and the fact that the indicator function is bounded by B = 1 and its expected value is equal to the probability of the event.

(f) Lemma 10 on space F where

δ ′ (ε) = 3E N 2 √ 2 24 ε, F , {X ′ (H j ), X ′′ (H j )} m n j=1 exp - m n ε 2 288B 2 ,
where X ′′ is a ghost sample independently generated from the same distribution as X ′ . Now we relate the ℓ 2 -covering number of F to the covering number of F . Using the definition of f we have

|| f -ḡ|| 2 X(H) = 1 m n m n ∑ j=1 f X(H j ) -ḡ X(H j ) 2 = 1 m n k n m n ∑ j=1 ∑ t∈H j f (X t ) 2 1 2 -∑ t ′ ∈H j g(X t ′ ) 2 1 2 2 .
Taking the square and using the Cauchy-Schwarz inequality, each element of the outer summation may be written as

∑ t∈H j f (X t ) 2 + g(X t ) 2 -2 ∑ t∈H j f (X t ) 2 1 2 ∑ t ′ ∈H j g(X t ′ ) 2 1 2 ≤ ∑ t∈H j f (X t ) 2 + g(X t ) 2 -2 f (X t )g(X t ) = ∑ t∈H j f (X t ) -g(X t ) 2 .
By the sum over all the odd blocks we obtain

|| f -ḡ|| 2 X(H) ≤ || f -g|| 2 X(H) ,
which indicates that 2 ε, F , {X ′ (H j ), X ′′ (H j )} m n j=1 ≤ N 2 ε, F , X ′ (H) ∪ X ′′ (H) . Therefore, we have δ ′ (2ε) ≤ δ(2ε) ≤ δ( √ 2ε), which concludes the proof.

With a similar approach, we can prove Equation 25

P ∃ f ∈ F : f X n 1 -2 √ 2 f > ε (a) ≤ P ∃ f ∈ F : √ 2 2 f X(H) + f X(E) -2 √ 2 f > ε (b) = P ∃ f ∈ F : √ 2 2 f X(H) - √ 2 f + √ 2 2 f X(E) - √ 2 f > ε (c) ≤ P ∃ f ∈ F : f X(H) -2 f > √ 2ε + P ∃ f ∈ F : f X(E) -2 f > √ 2ε (d) = 2P ∃ f ∈ F : f X(H) -2 f > √ 2ε (e) ≤ 2 P ∃ f ∈ F : f X ′ (H) -f > √ 2ε + m n β k n (f) ≤ 2δ ′ ( √ 2ε) + 2m n β k n ≤ 2δ( √ 2ε) + 2m n β k n .
(a) We used the inequality

√ a + b ≤ ( √ a + √ b) to split the norm f X n 1 ≤ √ 2 2
f X(H) + f X(E) . (b)-(f) use the same arguments as before.

Corollary 17 Let F be a class of linear functions f : X → R of dimension d, F be the class of functions obtained by truncating functions f ∈ F at a threshold B, and X n 1 = {X 1 , . . . , X n } be a sequence of samples drawn from a stationary exponentially fast β-mixing process with coefficients {β i }. By inverting the bound of Lemma 16, for any f ∈ F we have

f -2 f X n 1 ≤ ε(δ), f X n 1 -2 √ 2 f ≤ ε(δ),
with probability 1 -δ, where

ε(δ) = 12B 2Λ(n, d, δ) n max Λ(n, d, δ) b , 1 1/κ , ( 28
)
and Λ(n, d, δ) = 2(d + 1) log n + log e δ + log + max{18(6e) 2(d+1) , β} .

Proof In order to prove the statement, we need to verify that ε in Equation 28satisfies

δ ′ = 6E N 2 1 12 ε, F , X ′ (H) ∪ X ′′ (H) exp - m n ε 2 144B 2 + 2m n β k n ≤ δ .
Using Proposition 11 the covering number can be bounded by

E N 2 1 12 ε, F , X ′ (H) ∪ X ′′ (H) ≤ 3 1728eB 2 ε 2 2(d+1)
.

By recalling the definition of the β-coefficients {β i } and k n ≥ 1 we have

2m n β k n ≤ n k n β exp(-bk κ n ) ≤ n β exp(-bk κ n ) .
From the last two inequalities, m n = n/2k n , setting C 1 = 1728eB 2 and D = 2(d + 1) we obtain

δ ′ ≤ 18 C 1 ε 2 D exp - nε 2 144B 2 1 2k n + n β exp(-bk κ n ).
By equalizing the arguments of the two exponential we obtain the definition of k n as

k n = nC 2 ε 2 b 1 κ+1
, where C 2 = (576B 2 ) -1 , which implies

max nC 2 ε 2 b 1 κ+1 , 1 ≤ k n ≤ max 2nC 2 ε 2 b 1 κ+1
, 1 .

Thus we have the bound

1 2k n ≥ 1 4 min b nC 2 ε 2 1 κ+1 , 2 ≥ 1 4 min b nC 2 ε 2 1 κ+1 , 1 .
Using the above inequalities, we may write δ ′ as

δ ′ ≤ 18 C 1 ε 2 D exp -min b nC 2 ε 2 , 1 1 κ+1 nC 2 ε 2 + n β exp -b max nC 2 ε 2 b , 1 κ κ+1
.

The objective now is to make the arguments of the two exponential equal. For the second argument we have b max nC 2 ε 2 b , 1

κ κ+1 = b max nC 2 ε 2 b , 1 min b nC 2 ε 2 , 1 1 κ+1 ≥ nC 2 ε 2 min b nC 2 ε 2 , 1 1 κ+1 . Thus δ ′ ≤ 18 C 1 ε 2 D + n β exp -min b nC 2 ε 2 , 1 1 κ+1 nC 2 ε 2 .
Now we plug in ε from Equation 28. Using the fact that Λ ≥ 1, we know that ε 2 ≥ (nC 2 ) -1 , and thus δ ′ ≤ 18 (nC 1 C 2 ) D + n β exp (-Λ) .

Using the definition of Λ, we obtain Proof Let G = g α = f α L||α|| so that

δ ′ ≤ 18 (nC 1 C 2 ) D + n β n -D max{18(C 1 C 2 ) D , β} -1 δ e ≤ (1 + n 1-D ) δ e ≤ (1 + 1) δ e ≤ δ ,
{β i }. For any f ∈ F we have f -2 f X n 1 ≤ ε(δ), f X n 1 -2 √ 2 f ≤ ε(δ),
||g α || ∞ = 1 L||α|| || f α || ∞ ≤ 1 L||α|| ||α|| sup i ||ϕ i (x)|| ∞ ≤ 1.
We can thus apply Lemma 16 to the bounded space G with B = 1. By using a similar inversion as in Corollary 17, we thus obtain that with probability 1 -δ, for any function

g α ∈ G g α -2 g α X n 1 ≤ ε(δ), g α X n 1 -2 √ 2 g α ≤ ε(δ),
. , X n ) = {∃ f ∈ F : f X n 1 -2 √ 2 f > ε},
respectively.

Finally, we consider a special case in which out of the n total number of samples, ñ (1 ≤ ñ < n) are used to "burn" the chain and nñ are actually used as training samples.

Lemma 24 Let F be a class of linear functions f : X → R of dimension d and F be the class of functions obtained by truncating functions f ∈ F at a threshold B. Let M be an ergodic and aperiodic Markov chain with a stationary distribution ρ. Let M be mixing with an exponential rate with parameters β, b, κ. Let µ be the initial distribution and X 1 , . . . , X n be a sequence of samples such that X 1 ∼ µ and X 1<t≤n obtained by following M from X 1 . If the first ñ (1 ≤ ñ < n) samples are used to burn the chain and nñ are actually used as training samples, by inverting Lemma 23, for any f ∈ F , we obtain

f -2 X n 1 ≤ ε(δ), f X n 1 -2 √ 2 f ≤ ε(δ),
We first substitute the total variation in Lemma 23 with the bound in Equation 29, and then verify that ε in Equation 24 satisfies the following inequality.

δ ′ = λ -ρ TV + 2δ( √ 2ε) + 2m n-ñβ k n-ñ ≤ β exp(-b ñκ ) + 18 C 1 ε 2 D exp - (n -ñ)C 2 ε 2 k n-ñ + (n -ñ) β exp(-bk κ n-ñ) ≤ 1 2n + 1 + (n -ñ) 1-D δ e ≤ ( 1 2 + 1 + 1) δ e ≤ δ,
where C 1 = 1728eB 2 and C 2 = (288B 2 ) -1 . The above inequality can be verified by following the same steps as in Corollary 17 and by optimizing the bound for ñ.

Figure 1 :

 1 Figure 1: This figure shows the components used in Lemma 3 and its proof such as w, ŵ, ξ, and ξ, and the fact that ξ, ξ n = || ξ|| 2 n .

Assumption 2 .

 2 (Discounted-average Concentrability of Future-State Distribution [Antos et al., 2008]) Given the target distribution σ ∈ S(X ) and an arbitrary sequence of policies {π m } m≥1 , let c σ,µ = sup π 1 ,...,π m d(µP π 1 . . . P π m ) dσ .

( a )

 a Similar to Equation 15, this is true for any function f α ∈ F . (b) This is an immediate application of Assumption 1. (c) We use the fact that the orthogonal projection Π ρ k is non-expansive for norm || • || ρ k . 4. ν ρ k : This term depends on the following k-related terms.

  n, d, δ) = 2(d + 1) log n + log e δ + log + max{18(6e)2(d+1) , β} .

.

  Finally, we notice that||g α || = 1 L||α|| || f α || and ||g α || X n 1 = 1 L||α|| || f α || X n1 and the statement follows. and η(X 1 , . .

  n, d, δ) = 2(d + 1) log n + log e δ + log + max{18(6e) 2(d+1) , β} , and ñ = 1 b log 2e βn δ 1/κ . Proof After ñ steps, the first sample used in the training set (X ñ+1 ) is drawn from the distribution λ = µP ñ. Using Proposition 20 and Definition 21 we have ||λ -ρ|| TV ≤ β exp(-b ñκ ).

  Theorem 1 provides a bound on the prediction error of the LSTD solution v w.r.t. the true value function v on the trajectory X 1 , . . . , X n used as a training set for pathwise-LSTD. The bound contains two main terms. The first term ||v -Πv|| n is the approximation error and it

	represents the smallest possible error in approximating v with functions in F . This error cannot
	be avoided. The second term, of order O( d/n), is the estimation error and it accounts for the
	error due to the use of a finite number of noisy samples and it shows what is the influence of the
	different elements of the problem (e.g., γ,

Remark 1

  1 and the claim follows. Note that this theorem holds not only for ℓ 2 -norm, but for any ℓ p -norm, p ≥ 1.

Proof [Theorem 8] Rewriting Lemma 12 in

[START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF]

for V instead of Q, we obtain 6

Note that whenever the matrix A is invertible A+ = A -1 .

We define log + x = max{log x, 0}.

We recall that for any two distributions µ 1 , µ 2 ∈ S(X ), the total variation norm is defined as||µ 1µ 2 || TV = sup X⊆X |µ 1 (X)µ 2 (X)|.

The extension to the general case is straightforward.

= {X 1 , . . . , X n } be a sequence of samples drawn from a stationary exponentially fast β-mixing process with coefficients

Acknowledgments

We would like to thank Odalric Maillard for useful discussions. This work was supported by French National Research Agency (ANR) through the projects EXPLO-RA n • ANR-08-COSI-004 and LAMPADA n • ANR-09-EMER-007, by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the "contrat de projets état region (CPER) 2007-2013", European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 270327, and by PASCAL2 European Network of Excellence through PASCAL2 Pump Priming Programme.

Appendix A.

In this appendix we report a series of lemmata which are used throughout the paper. In particular, we derive concentration of measures inequalities for linear spaces and squared loss when samples are generated from different stochastic processes. We start with the traditional setting of independent and identically distributed samples in Section A.1, then move to samples generated from mixing processes in Section A.2, and finally consider the more general case of samples obtained by simulating a fast mixing Markov chain starting from an arbitrary distribution in Section A.3.

As a general rule, we use proposition to indicate results which are copied from other sources, while lemma refers to completely or partially new results.

A.1 IID Samples

Although in the setting considered in the paper the samples are non-i.i.d., we first report functional concentration inequalities for i.i.d. samples which will be later extended to stationary and nonstationary β-mixing processes. We first recall the definition of expected and empirical ℓ 2 -norms for

Lemma 10 Let F be a class of functions f : X → R bounded in absolute value by B. Let X n 1 = {X 1 , . . . , X n } be a sequence of i.i.d. samples. For any ε > 0

where N 2 (ε, F , X n 1 ) is the (L 2 , ε)-cover number of the function space F on the samples X n 1 (see [START_REF] Györfi | A Distribution-free Theory of Nonparametric Regression[END_REF].

Proof The first statement is proved in [START_REF] Györfi | A Distribution-free Theory of Nonparametric Regression[END_REF] and the second one can be proved similarly.

which concludes the proof.

In order to understand better the shape of the estimation error, we consider a simple β-mixing process with parameters β = b = κ = 1. Equation 28 reduces to d+1) . It is interesting to notice that the shape of the bound in this case resembles the structure of the bound in Corollary 12 for i.i.d. samples. Finally, we report the non-functional version of the previous corollary.

Corollary 18 Let F be a class of linear functions f : X → R of dimension d such that its features ϕ i : X → R are bounded in absolute value by L for any i = 1, . . . , d and X n Corollary 19 Let f : X → R be a linear function, f be its truncation at a threshold B, and X n 1 = {X 1 , . . . , X n } be a sequence of samples drawn from a stationary exponentially fast β-mixing process with coefficients

with probability 1 -δ, where

Proof The proof follows the same steps as in Corollary 17. We have the following sequence of inequalities

where C 2 = (576B 2 ) -1 .

A.3 Markov Chains

We first review the conditions for the convergence of Markov chains (Theorem 13.3.3. in [START_REF] Meyn | Markov Chains and Stochastic Stability[END_REF].

Proposition 20 Let M be an ergodic and aperiodic Markov chain defined on X with stationary distribution ρ. If P(A|x) is the transition kernel of M with A ⊆ X and x ∈ X , then for any initial

where || • || TV is the total variation norm.

Definition 21 Let M be an ergodic and aperiodic Markov chain with stationary distribution ρ. M is mixing with an exponential rate with parameters β, b, κ, if its β-mixing coefficients {β i } satisfy

Lemma 22 Let M be an ergodic and aperiodic Markov chain with a stationary distribution ρ. Let X 1 , . . . , X n be a sequence of samples drawn from the stationary distribution of the Markov chain ρ and X ′ 1 , . . . , X ′ n be a sequence of samples such that X ′ 1 ∼ ρ ′ and X ′ 1<t≤n generated by simulating M from X ′ 1 . Let η be an event defined on X n , then

We prove one side of the inequality. Let Q be the conditional joint distribution of (X 1<t≤n |X 1 = x) and Q ′ be the conditional joint distribution of (X ′ 1<t≤n |X ′ 1 = x). We first notice that Q is exactly the same as Q ′ . In fact, the first sequence (X 1<t≤n ) is generated by drawing X 1 from the stationary distribution ρ and then following the Markov chain. Similarly, the second sequence (X ′ 1<t≤n ) is obtained following the Markov chain from X ′ 1 ∼ ρ ′ . As a result, the conditional distributions of the two sequences is exactly the same and just depend on the Markov chain. As a result, we obtain the following sequence of inequalities

Lemma 23 Let F be a class of functions f : X → R bounded in absolute value by B, M be a an ergodic and aperiodic Markov chain with a stationary distribution ρ. Let M be mixing with an exponential rate with parameters β, b, κ. Let λ be an initial distribution over X and X 1 , . . . , X n be a sequence of samples such that X 1 ∼ λ and X 1<t≤n obtained by following M from X 1 . For any ε > 0,

Proof The proof is an immediate consequence of Lemma 16 and Lemma 22 by defining η(X 1 , . . . , X n ) as η(X 1 , . . . , X n ) = {∃ f ∈ F : f -2 f X n 1 > ε},