B Hemery

H Laurent

B Emile

C Rosenberger

Comparative Study Of Local Descriptors For Measuring Object Taxonomy

Many object descriptors have been proposed in the state of the art. For many reasons (occlusion, point of view, acquisition conditions. . . ), local descriptors have a better robustness for image understanding applications. The goal of this paper is to make a comparative study of eight recent local descriptors. The objective is here to quantify their ability to generate automatically an object taxonomy. In order to answer this question, we use the Caltech256 benchmark which provides a large object taxonomy used as reference. This study shows that SIFT, differential invariants and shape context descriptors are the best ones to achieve this goal.

Introduction

Image processing includes many steps from image acquisition (with camera, webcam, satellite. . . ) to image interpretation. This last step consists in automatically extracting information about objects present in an image (detection of objects of interest, quantitative measure. . . ). Whatever the foreseen application may be (biometric systems, medical imaging, video monitoring. . . ), the extracted information conditions the performances of the resulting process. It is required for this localization to be as precise as possible and with a correct recognition.

The evaluation of object classification or recognition is a crucial step for the validation of an algorithm. The classical way to conduct this evaluation is the use of ROC curves [START_REF] Adler | Comparing human and automatic face recognition performance[END_REF][START_REF] Thacker | Performance characterization in computer vision: A guide to best practices[END_REF] or Precision/Recall curves [5,[START_REF] Muller | Performance evaluation in content-based image retrieval: Overview and proposals[END_REF]. Such approaches use the false recognition rate, that is to say the rate where the object is not correctly recognized. By this way, we just count how many times the algorithm did not find the correct object, independently of the coherence of the made classification.

Our objective is to distinguish among recent local descriptors from the state of the art, those that permit to distinguish objects from different categories. To achieve this goal, we have to propose a similarity measure between objects and categories of objects. Such a similarity measure could be used in an evaluation process in order to improve its quality. This similarity is computed from the well known confusion matrix. As an example, the object "Dog" should be more similar to the object "Cat" than the object "Apple". By the way, we compare local descriptors that enable the definition of such a similarity measure by considering their ability to group objects that are similar within a category.

In this paper, we first present the local descriptors tested in the comparative study. We then present an experimental study where local descriptors performances are compared using the taxonomy available in the Caltech256 database [7]. Finally, some conclusions and perspectives are given.

Background

In this work, we use local descriptors that are commonly used to describe pattern and objects. What is often computed to evaluate a local descriptor is its capacity to discriminate an object from others. In this paper, we are interested in their capacity first to have a similar description of objects that belong to a given category (animal, vehicles,. . . ) and second, to distinguish objects that do not belong to the same category.

To compute the similarity measure, we first compute local descriptors for images of each object. The computation of local descriptors first needs a keypoints detector. Among all keypoints detectors that have been proposed in the literature [14,3], the Hessian-Affine detector described in [13] reveals itself as interesting. The advantage of this detector is that it finds much more keypoints than the Harris-Laplace [START_REF] Harris | A combined corner and edge detector[END_REF] or Harris-Affine ones [13], which is necessary for some samples images. Examples of detected keypoints can be found in figure 1. On the neighborhood of each keypoint, we then compute an invariant descriptor. The descriptors we tested in this work are presented below. • Complex filters (cf) [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or" how do i organize my holiday snaps?[END_REF],

Complex filters are derived from the following equation:

K mn (x, y) = (x + iy) m (x -iy) n G(x, y) (1)
where G(x, y) is a Gaussian function, x and y the pixel position in the filter. Fifteen filters are used, such as m + n < 6, to compute the descriptor on a 41*41 pixels patch. Some of the obtained filters are presented in figure 2. The resulting descriptor is a 15-elements vector. • Steerable filters (jla) [START_REF] Freeman | The design and use of steerable filters[END_REF] and differential invariants (koen) [START_REF] Koenderink | Representation of local geometry in the visual system[END_REF],

Descriptors from steerable filters and from differential invariants use derivatives computed by convolution with Gaussian derivatives for a 41*41 pixels patch. Steerable filters are designed as the output of a three basis filter bank. The outputs are then multiplied by a set of gain maps. Each basis filter is assigned to an angle θ varying from 0°to 60°and 120°. The derivatives of steerable filters are computed up to the 4 th order, the final descriptor contains a 14-elements vector. The differential invariants are computed up to the 4 th and the final descriptor is a 12-elements vector.

• SIFT (sift) [11,[START_REF] Belongie | Shape context: A new descriptor for shape matching and object recognition[END_REF], SIFT is a well known descriptor and has been largely used and studied since Lowe created it in 1999. The SIFT descriptor, as described in [START_REF] Belongie | Shape context: A new descriptor for shape matching and object recognition[END_REF], consists of four stages: (i) scale-space peak selection, (ii) interest point localization, (iii) orientation assignment, and (iv) descriptor. The three first stages correspond to the localization of keypoints. By the way, we use only the fourth stage because we use the Hessian-Affine as keypoints detector. The descriptor is computed from a 4*4 location Cartesian grid as shown in figure 3(a). The gradient on each location bin is then quantized into 8 orientation bins, and is computed on the patch around the keypoint. This leads to a 128-elements vector. • Gradient location and orientation histogram (gloh) [14],

The gradient location and orientation histogram is also a descriptor derived from the SIFT descriptor. It has been designed to increase the robustness and distinctiveness of the SIFT descriptor. It works, like the shape context, on a log-polar location grid. The location grid presented in figure 3(c) has 17 bins: 2 from each of 8 directions plus the center. Each location bins is quantized along 16 directions. This leads to a 272-elements vector, but the final descriptor is reduced to a 128-elements vector with a PCA reduction.

• Cross-correlation (cc) [14]. Finally, the cross correlation descriptor corresponds to a smoothed and uniformly sampled image of the patch around the interest point. The patch is sampled at 9*9 pixels so the final descriptor is a 81-elements vector.

All these descriptors have been studied in [14], SIFT and SIFT-based descriptors obtain the best results in the case of object recognition. As we are in a different context, we aim to see if they are also able to measure the similarity of objects category.

Developed method

To compute the similarity measure between two objects or two categories, we are looking for similar parts in two sample images. We assume the fact that the more there are corresponding keypoints between the two images, the more they are similar. An example of matching result between keypoints can be found in figure 4. We can see the matching of two samples from objects "calculator" and "computer keyboard", both in the "electronic" category. Even if these samples are from different objects, we can see some similarities as both objects have buttons. The computation of a similarity measure between objects is made of 2 steps. First, we apply a matching procedure to define similar parts of different samples. Second, we compute a score quantifying if samples belong to the same object or category.

Matching procedure

We are looking for associations between keypoints from each sample image as in [16]. An association is defined as a double matching between two keypoints: for a keypoint x of image k, we are looking for the nearest neighbor keypoint y among the set Y(I l ) of all points of image l. We also check that the second nearest neighbor point y ′ is far enough from the nearest neighbor (thanks to parameter C), otherwise, the keypoint is rejected. That is to say:

d(x, y) = min z∈Y(I l ) d(x, z) (2) and d(x, y) ≤ C * d(x, y ′ ) ( 3
)
where C is an arbitrary threshold set to 0, 7 and the computed distance d(•, •) between keypoints descriptors is the Euclidean one between the normalized vectors. If these conditions are fulfilled, then we say that the keypoint y is matched to keypoint x. We then associate the keypoint x from image k with keypoint y from image l if y is matched to x and x is matched to y. We can see on figure 4 lines between the associated keypoints.

Once we have defined the associated keypoints between images k and l, we define the similarity measure between these images s(k, l) as the number of associations. The more there are associated points, the more objects present in the images are similar.

Similarity measures

The similarity between objects is computed from several sample images from each object. To obtain it, we compute the average similarity measure S o from the similarity measures s between several images of these two objects:

S o (i, j) = k∈i l∈ j s(k, l) Card(i) * Card( j) (4)
where Card(i) denotes the number of images from object i. We can notice that a higher value denotes more similar objects. In a same way, we define a similarity measure for categories S c as the average similarity measure from objects of the two categories:

S c (u, v) = Σ i∈u j∈v S o (i, j) Card(u) * Card(v) (5)
where Card(u) denotes the number of objects from category u.

For the validation process, we then gather Intra and Inter informations for objects and categories. For objects, Intra o corresponds to the set of similarities S o (i, i) and Inter o corresponds to the set of similarities S o (i, j) with i j. For categories, Intra c corresponds to the set of similarities between objects of the same category, that is to say S c (u, u).

Inter c corresponds to the set of S c (u, v), with u v. Finally, we define a Score as:

Score = E[Intra]-E[Inter] σ[Intra]+σ[Inter] 2 (6)
where E[•] stands for the average and σ[•] stands for the standard deviation. This ratio enables us to determine which descriptors better maximize at the same time the Intra set and minimize the Inter one. The higher the ratio is, the best the descriptor separates objects or categories.

We can then define a similarity matrix such as MS i, j = S o (i, j). This matrix looks like a confusion matrix, but there are two principal differences. First, we can notice that the case S o (i, i) is not interesting, as we aim to compute a similarity between different objects. Second, this matrix is symmetric because S o (i, j) = S o ( j, i). Once built, such a matrix could be used to improve the evaluation of a recognition algorithm, by taking into account the importance of the made error.

Experimental results

This section first presents the Caltech256 Database [7]. Second, we present the obtained results.

Image database

For this comparative study, we use the Caltech256 Database 1 [7]. This database presents several advantages. First, it contains a large number of objects: 256 different objects plus one that represents a clutter class. Objects are various and make this database very difficult. Moreover, sample images from each object are also various. The second advantage is that objects are ordered and grouped within a taxonomy. A part of the taxonomy can be seen in the figure 5. This taxonomy creates categories of objects. Each category contains objects with a common subject.

In this paper, we use one part of this database. We choose 5 categories in the taxonomy: "Household and Everyday", "Sports", "Electronics", "Food" and "Animal". For each category, we select 10 objects recapitulated in table 1. We obtain a total of 50 objects among the 256 available. For each object, we used the first 20 images of the database, and compute a maximum of 150 keypoints per image. This leads to 1.000 sample images and 509.000 comparisons for this work.

Results

In order to validate our similarity measure, we check the Intra o and Inter o similarities for all objects. Table 2 We can see that the sift descriptor performs the best, closely followed by the gloh, pca and cc descriptors. The performance of sift can be explained by its capacity to distinguish different objects as it obtains a very low value of the Inter similarities. These results are similar to results obtained in [14], which validates our similarity measure and the Score o indicator. The question we would like to answer is how these descriptors are able to distinguish categories of objects that are different. Results, presented in Table 3, show Score c for each category. First, we can see that most descriptors mistake for the "Household and Everyday" categories, which reflects the difficulty of the Caltech256 database. The category "Animal" is the best recognized, which sounds reasonable given the taxonomy from Caltech: this category is in the group "Animate" whereas the four other category are from the group "Inanimate". Secondly, we can notice that koen descriptors perform well for all categories, "House" category included. We can also notice that sift, pca, gloh and cc descriptors obtain approximately the same kind of results. ] and the Score c for all categories, including the "Household and everyday" category. We can see that only two descriptors bring out: the sift descriptors still have the lower value for Inter similarities whereas the koen descriptors still have the higher value for the Intra similarities. Moreover, the koen descriptor seems to be the best for a difficult database. We can also remark that most of SIFT-based descriptors perform approximately like the sift descriptor. Finally, the average computation time of the distance between images and objects is presented in Table 6. We can see that, except the gloh descriptor which is slower, most descriptors have approximately the same computation time between: cf, jla and koen descriptors are around 6 seconds per object, sc, sift, pca and cc descriptors are around 8-9 seconds per object, and te gloh descriptor is at 19 second per object. Moreover, the koen descriptor is the fastest one.

Conclusions and perspectives

In this work, we compared 8 recent local descriptors from the state of the art in a particular case. Indeed, we aim to compare their ability to discriminate some object categories from each other. We can see that three descriptors bring out: sift descriptors are the best ones to compute Inter similarities as they are able to reject object from other category whereas koen descriptors are the best ones to compute Intra similarities, and the sc descriptor is a good compromise. In the case of various objects within a category, we suggest to use the koen descriptor, whereas in an easier database, we suggest to use the sift descriptor.

Finally, we aim to use a similarity matrix MS using the sift descriptor that would permit to better evaluate recognition algorithms. For example, if the objet "Dog" is recognize instead of the objet "Cat", we could penalize this error by using the similarity MS "Dog","cat" .

Figure 1 .

 1 Figure 1. Examples of detected keypoints

Figure 2 .

 2 Figure 2. Complex filters

Figure 3 .

 3 Figure 3. Location for different descriptors

Figure 4 .

 4 Figure 4. Example of matching between keypoints of two different samples containing different objects within the same Caltech category

Figure 5 .

 5 Figure 5. Extract of the taxonomy from Caltech256 database [7]: leaves of the tree are the different objects and nodes are the different categories

Table 2 .

 2 Results for objects similarities for each descriptor

	Descriptors E[Intra o ] E[Inter o ] Score o
	cf	7.35	0.51	12.1
	jla	7.42	0.57	11.8
	koen	8.23	1.37	9.8
	sc	6.95	0.12	12.7
	sift	6.83	0.03	13.2
	pca	6.87	0.07	13
	gloh	6.84	0.04	13.1
	cc	6.91	0.10	12.9

Table 1 .

 1 Selected objects per category

	Categories Household and Everyday Sports	Electronics	Food	Animal
		American Flag	Baseball bat	Boom box	Beer mug	Bat
		Bathtub	Baseball glove	Breadmaker	Cake	Bear
		Birdbath	Basketball hoop Calculator	Cereal box	Camel
		Chandelier	Billiard	CD	Chopsticks	Chimp
	Objects	Coin	Bowling ball	Computer keyboard Coffee mug	Conch
		Desk globe	Bowling pin	Computer monitor	Drinking straw Cormorant
		Doorknob	Boxing glove	Computer mouse	Ewer	Crab
		Fire extinguisher	Dumb bell	Flashlight	Fried egg	Dog
		Hammock	Football helmet Head phones	Hamburger	Duck
		Hot tub	Golf-ball	Lightbulb	Ice cream cone Elephant

Table 3 .

 3 Similarity results for each category: a negative ratio implies that the descriptor is not able to distinguish the category from others

	Descriptors Household Sports Electronics Food Animal
	cf	0.071	0.64 0.64	0.64 0.74
	jla	0.051	0.66 0.66	0.65 0.73
	koen	0.20	0.62 0.54	0.62 0.83
	sc	-0.058	0.68 0.71	0.64 0.67
	sift	-0.027	0.67 0.68	0.65 0.67
	pca	-0.058	0.67 0.69	0.65 0.67
	gloh	-0.044	0.67 0.69	0.65 0.67
	cc	-0.088	0.68 0.68	0.65 0.67
	Table 4 presents E[Intra

c ], E[Inter c

Table 4 .

 4 Results for categories similarities for each descriptor, including "Household and everyday" category Household and Everyday". In this case, the database is easier to recognize and this is confirmed by the fact that Intra values increase whereas Inter values decrease. We can see that three descriptors bring out: the koen descriptors have the best Intra values, the sift descriptors have the best Inter values and the sc is a good compromise.

	Descriptors E[Intra c ] E[Inter c ] Score c
	cf	1.06	0.53	0.55
	jla	1.13	0.58	0.55
	koen	1.94	1.44	0.56
	sc	0.67	0.11	0.53
	sift	0.58	0.02	0.53
	pca	0.61	0.05	0.53
	gloh	0.58	0.03	0.53
	cc	0.65	0.10	0.52
	Table 5 presents the same result as table 4, but without
	the category "

Table 5 .

 5 Results for categories similarities for each descriptor, excluding "Household and everyday" category Descriptors E[Intra c ] E[Inter c ] Score c

	cf	1.19	0.50	0.67
	jla	1.27	0.57	0.68
	koen	2.05	1.35	0.65
	sc	0.82	0.12	0.68
	sift	0.71	0.03	0.67
	pca	0.75	0.07	0.67
	gloh	0.72	0.04	0.67
	cc	0.79	0.11	0.67

Table 6 .

 6 Average computation time of similarity between two samples and two objects

	Descriptor	Computation time	Computation time
		for two samples (ms) for two objects (s)
	cf	17,0	6,81
	jla	16,4	6,54
	koen	14,9	5,97
	sc	20,7	8,26
	sift	24,0	9,61
	pca	20,9	8,36
	gloh	49,5	19,81
	cc	19,3	7,70

http://www.vision.caltech.edu/Image_Datasets/ Caltech256/

Acknowledgment

The authors would like to thank to the French Research Ministry for the financial support.


Bruno Scherrer

Approximate Policy Iteration Schemes: A Comparison

. For all algorithms, we describe performance bounds with respect the per-iteration error ǫ, and make a comparison by paying a particular attention to the concentrability constants involved, the number of iterations and the memory required. Our analysis highlights the following points: 1) The performance guarantee of CPI can be arbitrarily better than that of API, but this comes at the cost of a relative-exponential in 1 ǫ -increase of the number of iterations. 2) PSDP ∞ enjoys the best of both worlds: its performance guarantee is similar to that of CPI, but within a number of iterations similar to that of API. 3) Contrary to API that requires a constant memory, the memory needed by CPI and PSDP ∞ is proportional to their number of iterations, which may be problematic when the discount factor γ is close to 1 or the approximation error ǫ is close to 0; we show that the NSPI(m) algorithm allows to make an overall trade-off between memory and performance. Simulations with these schemes confirm our analysis.

Introduction

We consider an infinite-horizon discounted Markov Decision Process (MDP) [START_REF] Puterman | Markov Decision Processes[END_REF][START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF]) (S, A, P, r, γ), where S is a possibly infinite state space, A is a finite action space, P (ds ′ |s, a), for all (s, a), is a probability kernel on S, r : S → [-R max , R max ] is a reward function bounded by R max , and γ ∈ (0, 1) is a discount factor. A stationary deterministic policy π : S → A maps states to actions. We write P π (ds ′ |s) = P (ds ′ |s, π(s)) for the stochastic kernel associated to policy π. The value v π of a policy π is a function mapping states to the expected discounted sum of rewards received when following π from these states: for all s ∈ S,

v π (s) = E ∞ t=0 γ t r(s t ) s 0 = s, s t+1 ∼ P π (•|s t ) .
The value v π is clearly bounded by V max = R max /(1γ). It is well-known that v π can be characterized as the unique fixed point of the linear Bellman operator associated to a policy π: T π : v → r + γP π v. Similarly, the Bellman optimality operator T : v → max π T π v has as unique fixed point the optimal value v * = max π v π . A policy π is greedy w.r.t. a value function v if T π v = T v, the set of such greedy policies is written Gv. Finally, a policy π * is optimal, with value v π * = v * , iff π * ∈ Gv * , or equivalently

T π * v * = v * .
The goal of this paper is to study and compare several approximate Policy Iteration schemes. In the literature, such schemes can be seen as implementing an approximate greedy operator, G ǫ , that takes as input a distribution ν and a function v : S → R and returns a policy π that is (ǫ, ν)approximately greedy with respect to v in the sense that:

ν(T v -T π v) = ν(max π ′ T π ′ v -T π v) ≤ ǫ. (1)
where for all x, νx denotes E s∼ν [x(s)]. In practice, this approximation of the greedy operator can be achieved through a ℓ p -regression of the so-called Q-function-the stateaction value function-(a direct regression is suggested by [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], a fixed-point LSTD approach is used by Lagoudakis & Parr (2003b)) or through a (cost-sensitive) classification problem (Lagoudakis & Parr, 2003a;[START_REF] Lazaric | Analysis of a Classification-based Policy Iteration Algorithm[END_REF]. With this operator in hand, we shall describe several Policy Iteration schemes in Section 2. Then Section 3 will provide a detailed comparative analysis of their performance guarantees, time complexities, and memory requirements. Section 4 will go on by providing experiments that will illustrate their behavior, and confirm our analysis. Finally, Section 5 will conclude and present future work.

Algorithms

API We begin by describing the standard Approximate Policy Iteration (API) [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF]. At each iteration k, the algorithm switches to the policy that is approximately greedy with respect to the value of the previous policy for some distribution ν:

π k+1 ← G ǫ k+1 (ν, v π k ). ( 2
)
If there is no error (ǫ k = 0) and ν assigns a positive weights to every state, it can easily be seen that this algorithm generates the same sequence of policies as exact Policy Iterations since from Equation (1) the policies are exactly greedy.

CPI/CPI(α)/API(α) We now turn to the description of Conservative Policy Iteration (CPI) proposed by [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF]. At iteration k, CPI (described in Equation (3)) uses the distribution d π k ,ν = (1γ)ν(I -γP π k ) -1 -the discounted cumulative occupancy measure induced by π k when starting from ν-for calling the approximate greedy operator, and uses a stepsize α k to generate a stochastic mixture of all the policies that are returned by the successive calls to the approximate greedy operator, which explains the adjective "conservative":

π k+1 ← (1 -α k+1 )π k + α k+1 G ǫ k+1 (d π k ,ν , v π k ) (3)
The stepsize α k+1 can be chosen in such a way that the above step leads to an improvement of the expected value of the policy given that the process is initialized according to the distribution ν [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF]. The original article also describes a criterion for deciding whether to stop or to continue. Though the adaptive stepsize and the stopping condition allows to derive a nice analysis, they are in practice conservative: the stepsize α k should be implemented with a line-search mechanism, or be fixed to some small value α. We will refer to this latter variation of CPI as CPI(α).

It is natural to also consider the algorithm API(α) (mentioned by Lagoudakis & Parr (2003a)), a variation of API that is conservative like CPI(α) in the sense that it mixes the new policy with the previous ones with weights α and 1-α, but that directly uses the distribution ν in the approximate greedy step:

π k+1 ← (1 -α)π k + αG ǫ k+1 (ν, v π k ) (4) Because it uses ν instead of d π k ,ν , API(α) is simpler to implement than CPI(α) 1 .
PSDP ∞ We are now going to describe an algorithm that has a flavour similar to API-in the sense that at each step it does a full step towards a new deterministic policybut also has a conservative flavour like CPI-in the sense that the policies considered evolve more and more slowly. This algorithm is a natural variation of the Policy Search by Dynamic Programming algorithm (PSDP) of [START_REF] Bagnell | Policy search by dynamic programming[END_REF], originally proposed to tackle finite-horizon problems, to the infinite-horizon case; we thus refer to it as PSDP ∞ . To the best of our knowledge however, this variation has never been used in an infinite-horizon context.

The algorithm is based on finite-horizon non-stationary policies. Given a sequence of stationary deterministic policies (π k ) that the algorithm will generate, we will write σ k = π k π k-1 . . . π 1 the k-horizon policy that makes the first action according to π k , then the second action accord-

ing to π k-1 , etc. Its value is v σ k = T π k T π k-1 . . . T π1 r.
We will write ∅ the "empty" non-stationary policy. Note that v ∅ = r and that any infinite-horizon policy that begins with σ k = π k π k-1 . . . π 1 , which we will (somewhat abusively) denote "σ k . . .

" has a value v σ k ... ≥ v σ k -γ k V max .
Starting from σ 0 = ∅, the algorithm implicitely builds a sequence of non-stationary policies (σ k ) by iteratively concatenating the policies that are returned by the approximate greedy operator:

π k+1 ← G ǫ k+1 (ν, v σ k ) (5)
While the standard PSDP algorithm of [START_REF] Bagnell | Policy search by dynamic programming[END_REF] considers a horizon T and makes T iterations, the algorithm we consider here has an indefinite number of iterations. The algorithm can be stopped at any step k. The theory that we are about to describe suggests that one may return any policy that starts by the non-stationary policy σ k . Since σ k is an approximately good finite-horizon policy, and as we consider an infinite-horizon problem, a natural output that one may want to use in practice is the infinitehorizon policy that loops over σ k , that we shall denote

(σ k ) ∞ .
From a practical point of view, PSDP ∞ and CPI need to store all the (stationary deterministic) policies generated from the start. The memory required by the algorithmic scheme is thus proportional to the number of iterations, which may be prohibitive. The aim of the next paragraph, that presents the last algorithm of this article, is to describe a solution to this potential memory issue.

NSPI(m)

We originally devised the algorithmic scheme of Equation ( 5) (PSDP ∞ ) as a simplified variation of the Non-Stationary PI algorithm with a growing period algorithm (NSPI-growing) [START_REF] Scherrer | On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes[END_REF] 2 . With respect to Equation ( 5), the only difference of NSPIgrowing resides in the fact that the approximate greedy step is done with respect to the value v (σ k ) ∞ of the policy that loops infinitely over σ k (formally the algorithm does

π k+1 ← G ǫ k+1 (ν, v (σ k ) ∞ )) instead of the value v σ k of
σ m k = π k π k-1 . . . π k-m+1
. Also, we shall denote (σ m k ) ∞ the m-periodic infinite-horizon nonstationary policy that loops over σ m k . Starting from σ m 0 = π 0 π 1 . . . π m-1 , the algorithm iterates as follows:

π k+1 ← G ǫ k+1 (ν, v (σ m k ) ∞ ) (6)
Each iteration requires to compute an approximate greedy policy π k+1 with respect to the value v (σ m k ) ∞ of (σ m k ) ∞ , that is the fixed point of the compound operator3 :

∀v, T k,m v = T π k T π k-1 . . . T π k-m+1 v.
When one goes from iterations k to k + 1, the process consists in adding π k+1 at the front of the (m -1)-horizon policy π k π k-1 . . . π k-m+2 , thus forming a new m-horizon policy σ m k+1 . Doing so, we forget about the oldest policy π k-m+1 of σ m k and keep a constant memory of size m. At any step k, the algorithm can be stopped, and the output is the policy π k,m = (σ m k ) ∞ that loops on σ m k . It is easy to see that NSPI(m) reduces to API when m = 1. Furthermore, if we assume that the reward function is positive, add "stop actions" in every state of the model that lead to a terminal absorbing state with a null reward, and initialize with an infinite sequence of policies that only take this "stop action", then NSPI(m) with m = ∞ reduces to PSDP ∞ .

Analysis

For all considered algorithms, we are going to describe bounds on the expected loss E s∼µ [v π * (s)v π (s)] = µ(v π *v π ) of using the (possibly stochastic or nonstationary) policy π ouput by the algorithms instead of the optimal policy π * from some initial distribution µ of interest as a function of an upper bound ǫ on all errors (ǫ k ). In order to derive these theoretical guarantees, we will first need to introduce a few concentrability coefficients that relate the distribution µ with which one wants to have a guarantee, and the distribution ν used by the algorithms4 . Definition 1. Let c(1), c(2), . . . be the smallest coefficients in [1, ∞) ∪ {∞} such that for all i and all sets of deterministic stationary policies π 1 , π 2 , . . . , π i , µP π1 P π2 . . . P πi ≤ c(i)ν. For all m, k, we define the following coefficients in [1, ∞) ∪ {∞}:

C (1,k) = (1 -γ) ∞ i=0 γ i c(i + k), C (2,m,k) = (1 -γ)(1 -γ m ) ∞ i=0 ∞ j=0 γ i+jm c(i + jm + k).
Similarly, let c π * (1), c π * (2), . . . be the smallest coefficients in [1, ∞) ∪ {∞} such that for all i, µ(P π * ) i ≤ c π * (i)ν. We define:

C (1) π * = (1 -γ) ∞ i=0 γ i c π * (i). Finally let C π * be the smallest coefficient in [1, ∞) ∪ {∞} such that d π * ,µ = (1 -γ)µ(I -γP π * ) -1 ≤ C π * ν.
With these notations in hand, our first contribution is to provide a thorough comparison of all the algorithms. This is done in Table 1. For each algorithm, we describe some performance bounds and the required number of iterations and memory. To make things clear, we only display the dependence with respect to the concentrability constants, the Algorithm Performance Bound # Iter. Memory Reference API (Eq. ( 2)) [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] PSDP ∞ (Eq. ( 5))

C (2,1,0) 1 (1-γ) 2 ǫ 1 1-γ log 1 ǫ 1 (Lazaric et al., 2010) (= NSPI(1)) C (1,0) 1 (1-γ) 2 ǫ log 1 ǫ API(α) (Eq. (4) C (1,0) 1 (1-γ) 2 ǫ 1 α(1-γ) log 1 ǫ CPI(α) C (1,0) 1 (1-γ) 3 ǫ 1 α(1-γ) log 1 ǫ CPI (Eq. (3)) C (1,0) 1 (1-γ) 3 ǫ log 1 ǫ 1 1-γ 1 ǫ log 1 ǫ C π * 1 (1-γ) 2 ǫ γ ǫ 2 (Kakade
C π * 1 (1-γ) 2 ǫ log 1 ǫ 1 1-γ log 1 ǫ (≃ NSPI(∞)) C (1) π * 1 1-γ ǫ 1 1-γ log 1 ǫ NSPI(m) (Eq. (6)) C (2,m,0) 1 (1-γ)(1-γ m ) ǫ 1 1-γ log 1 ǫ m C (1,0) m 1 (1-γ) 2 (1-γ m ) ǫ log 1 ǫ 1 1-γ log 1 ǫ C (1) π * + γ m C (2,m,m) 1-γ m 1 1-γ ǫ 1 1-γ log 1 ǫ C π * + γ m C (2,m,0) m(1-γ m ) 1 (1-γ) 2 ǫ log 1 ǫ 1 1-γ log 1 ǫ Table 1.
Upper bounds on the performance guarantees for the algorithms. Except when references are given, the bounds are to our knowledge new. A comparison of API and CPI based on the two known bounds was done by [START_REF] Ghavamzadeh | Conservative and Greedy Approaches to Classification-based Policy Iteration[END_REF]. The first bound of NSPI(m) can be seen as an adaptation of that provided by [START_REF] Scherrer | On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes[END_REF] for the more restrictive ℓ∞-norm setting. discount factor γ, the quality ǫ of the approximate greedy operator, and-if applicable-the main parameters α/m of the algorithms. For API(α), CPI(α), CPI and PSDP ∞ , the required memory matches the number of iterations. All but two bounds are to our knowledge original. The derivation of the new results are given in Appendix A.

C (2,m,m) C (1,m) C (1) π * C (1,0) C π * C (2,1,0) C (2,m,0)
Our second contribution, that is complementary with the comparative list of bounds, is that we can show that there exists a hierarchy among the constants that appear in all the bounds of Table 1. In the directed graph of Figure 1, a constant B is a descendent of A if and only if the implication {B < ∞ ⇒ A < ∞} holds 5 . The "if and only if" is important here: it means that if A is a parent of B, and B is not a parent of A, then there exists an MDP for which A 5 Dotted arrows are used to underline the fact that the comparison of coefficients is restricted to the case where the parameter m is finite. is finite while B is infinite; in other words, an algorithm that has a guarantee with respect to A has a guarantee that can be arbitrarily better than that with constant B. Thus, the overall best concentrability constant is C π * , while the worst are C (2,1,0) and C (2,m,0) . To make the picture complete, we should add that for any MDP and any distribution µ, it is possible to find an input distribution ν for the algorithm (recall that the concentrability coefficients depend on ν and µ) such that C π * is finite, though it is not the case for C

(1) π * (and as a consequence all the other coefficients). The derivation of this order relations is done in Appendix B.

The standard API algorithm has guarantees expressed in terms of C (2,1,0) and C (1,0) only. Since CPI's analysis can be done with respect to C π * , it has a performance guarantee that can be arbitrarily better than that of API, though the opposite is not true. This, however, comes at the cost of an exponential increase of time complexity since CPI may require a number of iterations that scales in O 1 ǫ 2 , while the guarantee of API only requires O log 1 ǫ iterations. When the analysis of CPI is relaxed so that the performance guarantee is expressed in terms of the (worse) coefficient C (1,0) (obtained also for API), we can slightly improve the rateto Õ 1 ǫ -, though it is still exponentially slower than that of API. This second result for CPI was proved with a technique that was also used for CPI(α) and API(α). We conjecture that it can be improved for CPI(α), that should be as good as CPI when α is sufficiently small. PSDP ∞ enjoys two guarantees that have a fast rate like those of API. One bound has a better dependency with respect to 1 1-γ , but is expressed in terms of the worse coefficient C

(1) π * . The second guarantee is almost as good as that of CPI since it only contains an extra log 1 ǫ term, but it has the nice property that it holds quickly with respect to ǫ:

in time O(log 1 ǫ ) instead of O( 1 ǫ 2 )
, that is exponentially faster. PSDP ∞ is thus theoretically better than both CPI (as good but faster) and API (better and as fast). Now, from a practical point of view, PSDP ∞ and CPI need to store all the policies generated from the start. The memory required by these algorithms is thus proportional to the number of iterations. Even if PSDP ∞ may require much fewer iterations than CPI, the corresponding memory requirement may still be prohibitive in situations where ǫ is small or γ is close to 1. We explained that NSPI(m) can be seen as making a bridge between API and PSDP ∞ . Since (i) both have a nice time complexity, (ii) API has the best memory requirement, and (iii) NSPI(m) has the best performance guarantee, NSPI(m) is a good candidate for making a standard performance/memory trade-off. If the first two bounds of NSPI(m) in Table 1 extends those of API, the other two are made of two terms: the left terms are identical to those obtained for PSDP ∞ , while the two possible right terms are new, but are controlled by γ m , which can thus be made arbitrarily small by increasing the memory parameter m. Our analysis thus confirms our intuition that NSPI(m) allows to make a performance/memory trade-off in between API (small memory) and PSDP ∞ (best performance). In other words, as soon as memory becomes a constraint, NSPI(m) is the natural alternative to PSDP ∞ .

Experiments

In this section, we present some experiments in order to illustrate the empirical behavior of the different algorithms discussed in the paper. We considered the standard API as a baseline. CPI, as it is described by [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], is very slow (in one sample experiment on a 100 state problem, it made very slow progress and took several millions of iterations before it stopped) and we did not evaluate it further. Instead, we considered two variations: CPI+ that is identical to CPI except that it chooses the step α k at each iteration by doing a line-search towards the policy output by the greedy operator6 , and CPI(α) with α = 0.1, that makes "relatively but not too small" steps at each iteration. To assess the utility for CPI to use the distribution d ν,π for the approximate greedy step, we also considered API(α) with α = 0.1, the variation of API described in Equation ( 4) that makes small steps, and that only differs from CPI(α) by the fact that the approximate greedy step uses the distribution ν instead of d π k ,ν . In addition to these algorithms, we considered PSDP ∞ and NSPI(m) for the values m ∈ {5, 10, 30}.

In order to assess their quality, we consider finite problems where the exact value function can be computed. More precisely, we consider Garnet problems first introduced by [START_REF] Archibald | On the Generation of Markov Decision Processes[END_REF], which are a class of randomly constructed finite MDPs. They do not correspond to any specific application, but remain representative of the kind of MDP that might be encountered in practice. In brief, we consider Garnet problems with |S| ∈ {50, 100, 200}, |A| ∈ {2, 5, 10} and branching factors in {1, 2, 10}. The greedy step used by all algorithms is approximated by an exact greedy operator applied to a noisy orthogonal projection on a linear space of dimension |S| 10 with respect to the quadratic norm weighted by ν or d ν,π (for CPI+ and CPI(α)) where ν is uniform.

For each of these 3 3 = 27 parameter instances, we generated 30 i.i.d. Garnet MDPs (M i ) 1≤i≤30 . For each such MDP M i , we ran API, API(0.1), CPI+, CPI(0.1), NSPI(m) for m ∈ {5, 10, 30} and PSDP ∞ 30 times. For each run j and algorithm, we compute for all iterations k ∈ (1, 100) the performance, i.e. the loss L j,k = µ(v π *v π k ) with respect to the optimal policy. Figure 2 displays statistics about these random variables. For each algorithm, we display a learning curve with confidence regions that account for the variability across runs and problems. The supplementary material contains statistics that are respectively conditioned on the values of n S , n A and b, which gives some insight on the influence of these parameters.

From these experiments and statistics, we can make a series of observations. The standard API scheme is much more variable than the other algorithms and tends to provide the worst performance on average. CPI+ and CPI(α) display about the same asymptotic performance on average. If CPI(α) has slightly less variability, it is much slower than CPI+, that always converges in very few iterations (most of the time less than 10, and always less than 20). API(α)the naive conservative variation of API that is also simpler than CPI(α)-is empirically close to CPI(α), while being on average slightly worse. CPI+, CPI(α) and PSDP ∞ have a similar average performance, but the variability of PSDP ∞ is significantly smaller. PSDP ∞ is the algorithm that overall gives the best results. NSPI(m) does indeed provide a bridge between API and PSDP ∞ . By increasing m, the behavior gets closer to that of PSDP ∞ . With m = 30, NSPI(m) is overall better than API(α), CPI+, and CPI(α), and close to PSDP ∞ . The above relative observations are stable with respect to the number of states n S and actions n A . Interestingly, the differences between the algorithms tend to vanish when the dynamics of the problem gets more and more stochastic (when the branching factor increases). This complies with our analysis based on concentrability coefficients: there are all finite when the dynamics mixes a lot, and their relative difference are the biggest in deterministic instances.

(Std[Std[L 1,k |M1]]) k .
For ease of comparison, all curves are displayed with the same x and y range.

Discussion, Summary and Future Work

We have considered several variations of the Policy Iteration schemes for infinite-horizon problems: API, CPI, NSPI(m), API(α) and PSDP ∞ 7 . We have in particular explained the fact-to our knowledge so far unknownthat the recently introduced NSPI(m) algorithm generalizes API (that is obtained when m=1) and PSDP ∞ (that is very similar when m = ∞). Figure 1 synthesized the theoretical guarantees about these algorithms. Most of the bounds are to our knowledge new.

One of the first important message of our work is that what is usually hidden in the constants of the performance bounds does matter. The constants involved in the bounds for API, CPI, PSDP ∞ and for the main (left) terms of NSPI(m) can be sorted from the worst to the best as follows:

C (2,1,0) , C (1,0) , C (1)
π * , C π * . A detailed hierarchy of all constants was depicted in Figure 1. This is to our knowledge the first time that such an in-depth comparison of the bounds is done, and our hierarchy of constants has interesting implications that go beyond the Policy Iteration schemes we have been focusing on in this paper. As a matter of fact, several other dynamic programming algorithms, namely AVI [START_REF] Munos | Performance Bounds in Lp norm for Approximate Value Iteration[END_REF], λPI [START_REF] Scherrer | Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris[END_REF], AMPI (Scherrer et al., 2012), come with guarantees involv- 7 We recall that to our knowledge, the use of PSDP∞ (PSDP in an infinite-horizon context) is not documented in the literature.

ing the worst constant C (2,1,0) , which suggests that they should not be competitive with the best algorithms we have described here.

At the purely technical level, several of our bounds come in pair; this is due to the fact that we have introduced a new proof technique. This led to a new bound for API, that improves the state of the art in the sense that it involves the constant C (1,0) instead of C (2,1,0) . It also enabled us to derive new bounds for CPI (and its natural algorithmic variant CPI(α)) that is worse in terms of guarantee but has a better time complexity ( Õ( 1 ǫ ) instead of O( 1 ǫ 2 )). We believe this new technique may be helpful in the future for the analysis of other MDP algorithms.

Let us sum up the main insights of our analysis. 1) The guarantee for CPI can be arbitrarily stronger than that of API/API(α), because it is expressed with respect to the best concentrability constant C π * , but this comes at the cost of a relative-exponential in 1 ǫ -increase of the number of iterations. 2) PSDP ∞ enjoys the best of both worlds: its performance guarantee is similar to that of CPI, but within a number of iterations similar to that of API. 3) Contrary to API that requires a constant memory, the memory needed by CPI and PSDP ∞ is proportional to their number of iterations, which may be problematic in particular when the discount factor γ is close to 1 or the approximation error ǫ is close to 0; we showed that the NSPI(m) algorithm allows to make an overall trade-off between memory and perfor-mance.

The main assumption of this work is that all algorithms have at disposal an ǫ-approximate greedy operator. It may be unreasonable to compare all algorithms on this basis, since the underlying optimization problems may have different complexities: for instance, methods like CPI look in a space of stochastic policies while API moves in a space of deterministic policies. Digging and understanding in more depth what is potentially hidden in the term ǫ-as we have done here for the concentrability constants-constitutes a very natural research direction.

Last but not least, we have run numerical experiments that support our worst-case analysis. On simulations on about 800 Garnet MDPs with various characteristics, CPI(α), CPI+ (CPI with a crude line-search mechanism), PSDP ∞ and NSPI(m) were shown to always perform significantly better than the standard API. CPI+, CPI(α) and PSDP ∞ performed similarly on average, but PSDP ∞ showed much less variability and is thus the best algorithm in terms of overall performance. Finally, NSPI(m) allows to make a bridge between API and PSDP ∞ , reaching an overall performance close to that of PSDP ∞ with a controlled memory. Implementing other instances of these algorithmic schemes, running and analyzing experiments on bigger domains constitutes interesting future work.

A. Proofs for Table 1 PSDP ∞ : For all k, we have

v π * -v σ k = T π * v π * -T π * v σ k-1 + T π * v σ k-1 -T π k v σ k-1 ≤ γP π * (v π -v σ k-1 ) + e k where we defined e k = max π ′ T π ′ v σ k-1 -T π k v σ k-1 .
As P π * is non negative, we deduce by induction:

v π * -v σ k ≤ k-1 i=0 (γP π * ) i e k-i + γ k V max .
By multiplying both sides by µ, using the definition of the coefficients c π * (i) and the fact that νe j ≤ ǫ j ≤ ǫ, we get:

µ(v π * -v σ k ) ≤ k-1 i=0 µ(γP π * ) i e k-i + γ k V max (7) ≤ k-1 i=0 γ i c π * (i)ǫ k-i + γ k V max ≤ k-1 i=0 γ i c π * (i) ǫ + γ k V max .

The bound with respect to C

(1) π * is obtained by using the fact that v

σ k ... ≥ v σ k -γ k V max and taking k ≥ log 2Vmax ǫ 1-γ .
Starting back in Equation ( 7) and using the definition of C π * (in particular the fact that for all i, µ(γP π *

) i ≤ 1 1-γ d π * ,µ ≤ Cπ *
1-γ ν) and the fact that νe j ≤ ǫ j , we get:

µ(v π * -v σ k ) ≤ k-1 i=0 µ(γP π * ) i e k-i + γ k V max ≤ C π * 1 -γ k i=1 ǫ i + γ k V max
and the other bound is obtained by using the fact that API/NSPI(m): API is identical to NSPI(1), and its bounds are particular cases of the first two bounds for NSPI(m), so we only consider NSPI(m). By following the proof technique of [START_REF] Scherrer | On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes[END_REF]

v σ k ... ≥ v σ k -γ k V max , k i=1 ǫ i ≤ kǫ,
, writ- ing Γ k,m = (γP π k )(γP π k-1 ) • • • (γP π k-m+1 ) and e k+1 = max π ′ T π ′ v π k,m -T π k+1 v π k,m , one can show that: v π * -v π k,m ≤ k-1 i=0 (γP π * ) i (I -Γ k-i,m ) -1 e k-i + γ k V max .
Multiplying both sides by µ (and observing that e k ≥ 0) and the fact that νe j ≤ ǫ j ≤ ǫ, we obtain:

µ(v π * -v π k ) ≤ k-1 i=0 µ(γP π * ) i (I -Γ k-i,m ) -1 e k-i + γ k V max (8) ≤ k-1 i=0   ∞ j=0 γ i+jm c(i + jm)ǫ k-i   + γ k V max (9) ≤ k-1 i=0 ∞ j=0 γ i+jm c(i + jm)ǫ + γ k V max , (10)
which leads to the first bound by taking k ≥

log 2Vmax ǫ 1-γ
. Starting back on Equation ( 9), assuming for simplicity that ǫ -k = 0 for all k ≥ 0, we get: (11) which leads to the second bound by taking k =

µ(vπ * -vπ k ) -γ k Vmax ≤ ⌈ k-1 m ⌉ l=0 m-1 h=0 ∞ j=0 γ h+(l+j)m c(h + (l + j)m)ǫ k-h-lm ≤ ⌈ k-1 m ⌉ l=0 m-1 h=0 ∞ j=l γ h+jm c(h + jm) max k-(l+1)m+1≤p≤k-lm ǫp ≤ ⌈ k-1 m ⌉ l=0 m-1 h=0 ∞ j=0 γ h+jm c(h + jm) max k-(l+1)m+1≤p≤k-lm ǫp Approximate Policy Iteration Schemes: A Comparison = m-1 h=0 ∞ j=0 γ h+jm c(h + jm) ⌈ k-1 m ⌉ l=0 max l-(l+1)m+1≤p≤k-lm ǫp ≤ ∞ i=0 γ i c(i) k -1 m ǫ,
log 2Vmax ǫ 1-γ
. Last but not least, starting back on Equation (8), and using the fact that

(I -Γ k-i,m ) -1 = I + Γ k-i,m (I -Γ k-i,m
) -1 we see that:

µ(v π * -v π k ) -γ k V max ≤ k-1 i=0 µ(γP π * ) i e k-i + + k-1 i=0 µ(γP π * ) i Γ k-i,m (I -Γ k-i,m ) -1 e k-i .
The first term of the r.h.s. can be bounded exactly as for PSDP ∞ . For the second term, we have:

k-1 i=0 µ(γP π * ) i Γ k-i,m (I -Γ k-i,m ) -1 e k-i ≤ k-1 i=0 ∞ j=1 γ i+jm c(i + jm)ǫ k-i = γ m k-1 i=0 ∞ j=0 γ i+jm c(i + (j + 1)m)ǫ k-i ,
and we follow the same lines as above (from Equation (9) to Equations ( 10) and ( 11)) to conclude.

CPI, CPI(α), API(α): Conservative steps are addressed by a tedious generalization of the proof for API by [START_REF] Munos | Error Bounds for Approximate Policy Iteration[END_REF]. Due to lack of space, the proof is deferred to the Supplementary Material.

B. Proofs for Figure 1

We here provide details on the order relation for the concentrability coefficients.

C π * → C (1) π * : (i) We have C π * ≤ C (1) π * because d π * ,µ = (1 -γ)µ(I -γP π * ) -1 = (1 -γ) ∞ i=0 γ i µ(P π * ) i ≤ (1 -γ) ∞ i=0 γ i c π * (i)ν = C (1) π * ν and C π * is the smallest coefficient C satisfying d π * ,µ ≤ Cν. (ii) We may have C π * < ∞ and C (1)
π * = ∞ by design-ing a MDP on N where π * induces a deterministic transition from state i to state i + 1.

C

(1)

π * → C (1,0) : (i) We have C (1) π * ≤ C (1,0) because for all i, c π * (i) ≤ c(i). (ii) It is easy to obtain C (1) π * < ∞ and C (1,0) = ∞ since C (1)
π * only depends on one policy while C

(1) π * depends on all policies. ,m,m) holds because ,m,m) .

C (1,0) → C (2,m,0) and C (1,m) → C (2,m,m) : (i) C (1,m) ≤ 1 1-γ m C (2
C (1,m) 1 -γ = ∞ i=0 γ i c(i + m) ≤ ∞ i=0 ∞ j=0 γ i+jm c(i + (j + 1)m) = 1 (1 -γ)(1 -γ m ) C (2
(ii) One may have ,m,m) is Θ( 1i ) (the sum diverges). The reasoning is similar for the other relation. ,1,0) . (ii) C (2,m,0) can be rewritten as follows:

C (1,m) < ∞ and C (2,m,m) = ∞ when c(i) = Θ( 1 i 2 γ i ), since the generic term of C (1,m) is Θ( 1 i 2 ) (the sum converges) while that of C (2
C (1,m) → C (1,0) and C (2,m,m) → C (2,m,0) : We here assume that m < ∞. (i) We have C (1,m) ≤ 1 γ m C (1,0) and C (2,m,m) ≤ 1 γ m C (2,m,0) . (ii) It suffices that c(j) = ∞ for some j < m to have C (2,m,0) = ∞ while C (2,m,m) < ∞, or to have C (1,0) = ∞ while C (1,m) < ∞. C (2,1,0) ↔ C (2,m,0) : (i) We clearly have C (2,m,0) ≤ 1-γ m 1-γ C (2
C (2,m,0) = (1 -γ)(1 -γ m ) ∞ i=0 1 + i m γ i c(i).
Then, using the fact that 1 + i m ≥ max 1, i m , we have

1 -γ 1 -γ m C (2,m,0) ≥ ∞ i=0 max 1, i m γ i c(i) ≥ m-1 i=0 γ i c(i) + ∞ i=m i m γ i c(i) ≥ m-1 i=0 γ i c(i) + m m + 1 ∞ i=m i + 1 m γ i c(i) = m-1 i=0 γ i c(i) + m m + 1 C (2,1,0) - m-1 i=0 γ i c(i) = m m + 1 C (2,1,0) + 1 m + 1 m-1 i=0 γ i c(i). Thus, when m is finite, C (2,m,0) < ∞ ⇒ C (2,1,0) < ∞.
We begin by proving the following result: Theorem 1. At each iteration k < k * of CPI (Equation (3)), the expected loss satisfies:

µ(v π * -v π k ) ≤ C (1,0) (1 -γ) 2 k i=1 α i ǫ i + e {(1-γ) k i=1 αi} V max .
Proof. Using the facts that

T π k+1 v π k = (1 -α k+1 )v π k + α k+1 T π k+1 v π k and the notation e k+1 = max π ′ T π ′ v π k - T π ′ k+1 v π k , we have: v π * -v π k+1 = v π * -T π k+1 v π k + T π k+1 v π k -T π k+1 v π k+1 = v π * -(1 -α k+1 )v π k -α k+1 T π ′ k+1 v π k + γP π k+1 (v π k -v π k+1 ) = (1 -α k+1 )(v π * -v π k ) + α k+1 (T π * v π * -T π * v π k ) + α k+1 (T π * v π k -T π ′ k+1 v π k ) + γP π k+1 (v π k -v π k+1 ) ≤ [(1 -α k+1 )I + α k+1 γP π * ] (v π -v π k ) + α k+1 e k+1 + γP π k+1 (v π k -v π k+1 ). (12)
Using the fact that v π k+1 = (I -γP π k+1 ) -1 r, and the fact that (I -γP π k+1 ) -1 is non-negative, we can see that

v π k -v π k+1 = (I -γP π k+1 ) -1 (v π k -γP π k+1 v π k -r) = (I -γP π k+1 ) -1 (T π k v π k -T π k+1 v π k ) ≤ (I -γP π k+1 ) -1 α k+1 e k+1 .
Putting this back in Equation ( 12), we obtain:

v π * -v π k+1 ≤ [(1 -α k+1 )I + α k+1 γP π * ] (v π -v π k ) + α k+1 (I -γP π k+1 ) -1 e k+1 .
Define the matrix

Q k = [(1 -α k )I + α k γP π * ], the set N i,k = {j; k -i + 1 ≤ j ≤ k} (this set contains exactly i elements), the matrix R i,k = j∈N i,k Q j , and the coefficients β k = 1 -α k (1 -γ) and δ k = k i=1 β k .
By repeatedly using the fact that the matrices Q k are non-negative, we get by induction

v π * -v π k ≤ k-1 i=0 R i,k α k-i (I -γP π k-i ) -1 e k-i + δ k V max . (13)
Let P j (N i,k ) be the set of subsets of N i,k of size j. With this notation we have

R i,k = i j=0 I∈Pj (N i,k ) ζ I,i,k (γP π * ) j
where for all subset I of N i,k , we wrote

ζ I,i,k = n∈I α n   n∈N i,k \I (1 -α n )   .
Therefore, by multiplying Equation ( 13) by µ, using the definition of the coefficients c(i), and the facts that ν ≤ (1 -γ)d ν,π k+1 , we obtain:

µ(v π * -v π k ) ≤ 1 1 -γ k-1 i=0 i j=0 ∞ l=0 I∈Pj (N i,k ) ζ I,i,k γ j+l c(j + l)α k-i ǫ k-i + δ k V max . = 1 1 -γ k-1 i=0 i j=0 ∞ l=j I∈Pj (N i,k ) ζ I,i,k γ l c(l)α k-i ǫ k-i + δ k V max ≤ 1 1 -γ k-1 i=0 i j=0 ∞ l=0 I∈Pj (N i,k ) ζ I,i,k γ l c(l)α k-i ǫ k-i + δ k V max = 1 1 -γ ∞ l=0 γ l c(l) k-1 i=0   i j=0 I∈Pj (N i,k ) ζ I,i,k   α k-i ǫ k-i + δ k V max = 1 1 -γ ∞ l=0 γ l c(l) k-1 i=0   j∈N i,k (1 -α j + α j )   α k-i ǫ k-i + δ k V max = 1 1 -γ ∞ l=0 γ l c(l) k-1 i=0 α k-i ǫ k-i + δ k V max .
Now, using the fact that for x ∈ (0, 1), log(1x) ≤ -x, we can observe that

log δ k = log k i=1 β i = k i=1 log β i = k i=1 log(1 -α i (1 -γ)) ≤ -(1 -γ) k i=1 α i .
As a consequence, we get δ k ≤ e -(1-γ) k i=1 αi .

In the analysis of CPI, [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF] show that the learning steps that ensure the nice performance guarantee of CPI satisfy α k ≥ (1-γ)ǫ 12γVmax , the right term e {(1-γ) k i=1 αi} above tends 0 exponentially fast, and we get the following corollary that shows that CPI has a performance bound with the coefficient C (1,0) of API in a number of iterations

O log 1 ǫ ǫ . Corollary 1. The smallest (random) iteration k † such that log Vmax ǫ 1-γ ≤ k † i=1 α i ≤ log Vmax ǫ 1-γ + 1 is such that k † ≤ 12γVmax log Vmax ǫ ǫ(1-γ) 2
and the policy π k † satisfies:

µ(v π * -v π k † ) ≤   C (1,0) k † i=1 α i (1 -γ) 2 + 1   ǫ ≤ C (1,0) log Vmax ǫ + 1 (1 -γ) 3 + 1 ǫ.
Since the proof is based on a generalization of the analysis of API and thus does not use any of the specific properties of CPI, it turns out that the results we have just given can straightforwardly be specialized to CPI(α).

Corollary 2. Assume we run CPI(α) for some α ∈ (0, 1), that is CPI (Equation (3)) with α k = α for all k.

If k = log Vmax ǫ α(1 -γ) , then µ(v π * -v π k ) ≤ α(k + 1)C (1,0) (1 -γ) 2 ǫ ≤ C (1,0) log Vmax ǫ + 1 (1 -γ) 3 + 1 ǫ.
The above bound for CPI(α) involves the factor 1 (1-γ) 3 . A precise examination of the proof shows that this amplification is due to the fact that the approximate greedy operator uses the distribution d π k ,ν ≥ (1γ)ν instead of ν (for API). In fact, using a very similar proof, it is easy to show that API(α) satisfies the following result.

Corollary 3. Assume API(α) is run for some α ∈ (0, 1).

If k = log Vmax ǫ α(1 -γ) , then µ(v π * -v π k ) ≤ α(k + 1)C (1,0) (1 -γ) ǫ ≤ C (1,0) log Vmax ǫ + 1 (1 -γ) 2 + 1 ǫ.
D. More details on the Numerical Simulations Domain and Approximations In our experiments, a Garnet is parameterized by 4 parameters and is written G(n S , n A , b, p): n S is the number of states, n A is the number of actions, b is a branching factor specifying how many possible next states are possible for each state-action pair (b states are chosen uniformly at random and transition probabilities are set by sampling uniform random b -1 cut points between 0 and 1) and p is the number of features (for linear function approximation). The reward is state-dependent: for a given randomly generated Garnet problem, the reward for each state is uniformly sampled between 0 and 1. Features are chosen randomly: Φ is a n S ×p feature matrix of which each component is randomly and uniformly sampled between 0 and 1. The discount factor γ is set to 0.99 in all experiments.

All the algorithms we have discussed in the paper need to repeatedly compute G ǫ (ρ, v) for some distribution ρ = ν or ρ = d π,ν . In other words, they must be able to make calls to an approximate greedy operator applied to the value v of some policy for some distribution ρ. To implement this operator, we compute a noisy estimate of the value v with a uniform white noise u(ι) of amplitude ι, then projects this estimate onto the space spanned by Φ with respect to the ρ-quadratic norm (projection that we write Π Φ,ρ ), and then applies the (exact) greedy operator on this projected estimate. In a nutshell, one call to the approximate greedy operator G ǫ (ρ, v) amounts to compute GΠ Φ,ρ (v + u(ι)).

Simulations We have run series of experiments, in which we callibrated the perturbations (noise, approximations) so that the algorithm are significantly perturbed but no too much (we do not want their behavior to become too erratic). After trial and error, we ended up considering the following setting. We used Garnet problems G(n S , n A , b, p) with the number of states n S ∈ {50, 100, 200}, the number of actions n A ∈ {2, 5, 10}, the branching factor b ∈ {1, 2, 10}} (b = 1 corresponds to deterministic problems), the number of features to approximate the value p = n S 10 , and the noise level ι = 0.1 (10%). In addition to Figure 2 that shows the statistics overall for the all the parameter instances, Figure 3, 4 and 5 display statistics that are respectively conditioned on the values of n S , n A and b, which gives some insight on the influence of these parameters.

Figure 1 .

 1 Figure1. Hierarchy of the concentrability constants. A constant A is better than a constant B-see the text for details-if A is a parent of B on the above graph. The best constant is Cπ * .

Figure 2 .

 2 Figure 2. Statistics for all instances. The MDPs (Mi) 1≤i≤30 are i.i.d. with the same distribution as M1. Conditioned on some MDP Mi and some algorithm, the error measures at all iteration k are i.i.d. with the same distribution as L 1,k . The central line of the learning curves gives the empirical estimate of the overall average error (E[L 1,k ]) k . The three grey regions (from dark to light grey) are estimates of respectively the variability (across MDPs) of the average error (Std[E[L 1,k |M1]]) k , the average (across MDPs) of the standard deviation of the error (E[Std[L 1,k |M1]]) k , and the variability (across MDPs) of the standard deviation of the error(Std[Std[L 1,k |M1]]) k .For ease of comparison, all curves are displayed with the same x and y range.

Figure 3 .

 3 Figure 3. Statistics conditioned on the number of states. Top: nS = 50. Middle: nS = 100. Bottom nS = 200.

Figure 4 .

 4 Figure 4. Statistics conditioned on the number of actions. Top: nA = 2. Middle: nA = 5. Bottom na = 10.

Figure 5 .

 5 Figure 5. Statistics conditioned on the branching factor. Top: b = 1 (deterministic). Middle: b = 2. Bottom b = 10.

In practice, controlling the greedy step with respect to dπ k ,ν requires to generate samples from this very distribution. As explained by[START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF], one such sample can be done by running one trajectory starting from ν and following π k , stopping at each step with probability 1γ. In particular, one sample from dπ k ,ν requires on average 1 1-γ samples from the underlying MDP. With this respect, API(α) is much simpler to implement.

We later realized that it was in fact a very natural variation of PSDP. To "give Caesar his due and God his", we kept as the main reference the older work and gave the name PSDP∞.

Implementing this algorithm in practice can trivially be done through cost-sensitive classification in a way similar to[START_REF] Lazaric | Analysis of a Classification-based Policy Iteration Algorithm[END_REF]. It could also be done with a straight-forward extension of LSTD(λ) to non-stationary policies.

The expected loss corresponds to some weighted ℓ1-norm of the loss vπ *vπ. Relaxing the goal to controlling the weighted ℓp-norm for some p ≥ 2 allows to introduce some finer coefficients[START_REF] Farahmand | Error propagation for approximate policy and value iteration (extended version)[END_REF] Scherrer et al., 2012). Due to lack of space, we do not consider this here.

We implemented a crude line-search mechanism, that looks on the set 2 i α where α is the minimal step estimated by CPI to ensure improvement.

Supplementary Material

C. Proof for CPI, CPI(α), API(α)