Matthieu Geist

An Algorithmic Survey of Parametric Value Function Approximation

Keywords: Reinforcement learning, survey, value function approximation

Reinforcement learning is a machine learning answer to the optimal control problem. It consists in learning an optimal control policy through interactions with the system to be controlled, the quality of this policy being quantified by the so-called value function. A recurrent subtopic of reinforcement learning is to compute an approximation of this value function when the system is too large for an exact representation. This survey reviews state-of-the-art methods for (parametric) value function approximation by grouping them into three main categories: bootstrapping, residual and projected fixed-point approaches. Related algorithms are derived by considering one of the associated cost functions and a specific minimization method, generally a stochastic gradient descent or a recursive least-squares approach.

I. Introduction

Reinforcement Learning (RL) [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF][2][3][4] [START_REF] Wiering | Reinforcement Learning: State Of the Art[END_REF][6] [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF] addresses the problem of the optimal control of a stochastic dynamic system. In this paradigm, an artificial agent learns an optimal control policy through interactions with the dynamic system (also considered as its environment). After each interaction, the agent receives an immediate scalar reward information and the optimal policy it searches for is the one that maximizes the expected cumulative reward over the long term. The system to be controlled is usually modeled as a Markovian Decision Process (MDP). An MDP is made up of a set of states (the different configurations of the system), a set of actions (which cause a change of the system's state), a set of Markovian transition probabilities (the probability to transit from one state to another under a given action; the Markovian property states that the probability depends on the current state-action pair and not on the path followed to reach it), a reward function associating a scalar to each transition and a discounting factor which decreases long-term rewards' influence. How the agent acts with the system is modeled by a policy which associates to each state a probability distribution over actions. The quality of such a policy is quantified by a value function which associates to each state the expected cumulative discounted reward from starting in the considered state and then following the given policy (expectation being done over all possible trajectories). An optimal policy is one of those which maximize the associated value function for each state.

Thanks to the Markovian property, value functions can be (more or less easily) computed using Bellman equations. The value function of a given policy satisfies the (linear) Bellman evaluation equation and the optimal value function (which is linked to one of the optimal policies) satisfies the (nonlinear) Bellman optimality equation. These Bellman equations are very important for reinforcement learning, as they allow computing the value function.

If the model (that is transition probabilities and the reward function) is known and if state and action spaces are small enough, the optimal policy can be computed using dynamic programming. A first scheme, called policy iteration, consists in evaluating an initial policy (that is computing the associated value function using the linear Bellman evaluation equation) and then improving this policy, the new one being greedy with respect to the computed value function (it associates to each state the action which maximizes the expected cumulative reward obtained from starting in this state, applying this action and then following the initial policy). Evaluation and improvement steps are iterated until convergence (which occurs in a finite number of iterations). A second scheme, called value iteration, consists in computing directly the optimal value function (using the nonlinear Bellman optimality equation and an iterative scheme based on the fact that the value function is the unique fixed-point of the associated Bellman operator). The optimal policy is greedy with respect to the optimal value function.

Reinforcement learning aims at estimating the optimal policy without knowing the model and from interactions with the system. Value functions can no longer be exactly computed, they have to be estimated, which is the main scope of this paper. Reinforcement learning heavily relies on dynamic programming, in the sense that most approaches are some sorts of generalization of value or policy iteration. A first problem is that computing a greedy policy (required for both schemes) from a value function requires the model to be known. The action-value (or Q-) function alleviates this problem by encoding the value of state-action couples (instead of states only). It is defined, for a given policy and for a state-action couple, as the expected discounted cumulative reward starting in the given state, applying the given action and then following the fixed policy. A greedy policy can thus be obtained by maximizing the Q-function over actions.

There are two main approaches to estimate an optimal policy through value functions. The first one, based on value iteration, consists in estimating directly the optimal action-value function which is then used to derive an estimate of the optimal policy (with the drawback that errors in the Q-function estimation can lead to a bad derived policy). The second one, based on policy iteration, consists in mixing the estimation of the Q-function of the current policy (policy evaluation) with policy improvement in a generalized policy iteration scheme (generalized in the sense that evaluation and improvement processes interact, independently of the granularity and other details). This scheme presents many variations. Generally, the Qfunction is not perfectly estimated when the improvement step occurs (optimistic policy iteration). Each change in the policy implies a change in the associated Q-function; therefore, the estimation process can be non-stationary.

The control policy can be derived from the estimated action-value function (for example, using a Boltzmann distribution or an -greedy policy). There is generally an underlying dilemma between exploration and exploitation. At each time step, the agent should decide between acting greedily with respect to its uncertain and imperfect knowledge of the world (exploitation) and taking another action which improves this knowledge and possibly leads to a better policy (exploration). The policy can also have its own representation, which leads to actor-critic architectures (which are a form of policy iteration). The actor is the policy, and the critic is an estimated value or Qfunction which is used to correct the policy representation. All these approaches share a common subproblem: estimating the (action-) value function, of a given policy (evaluation operator) or the optimal one (optimality operator) directly. This issue is even more involved when state or action spaces are too large for a tabular representation, which implies to use some approximate representation. Generally speaking, estimating a function from samples is addressed by the supervised learning paradigm. However, in reinforcement learning, the (action-) values are not directly observed, which renders the underlying estimation problem more difficult. Despite this, a number of (action-) value function estimation algorithms have been proposed in the past decades. The aim of this paper is to review a panel as large as possible of these algorithms by adopting a unifying view which classifies them into three main categories: bootstrapping approaches (Sec. III), residual approaches (Sec. IV) and projected fixed-point approaches (Sec. V). Each of them is related to a specific cost function, and algorithms are derived considering one of these costs and a specific way to minimize it (almost always a stochastic gradient descent or a recursive least-squares approach). Sections III to V are the core of this survey on parametric value function approximation, but additional important topics are briefly covered at the end of the article. Sec. VI shows how these approaches can be embedded in the more general control problem, Sec. VII discusses when choosing what algorithm (among surveyed methods and depending on the practical context) and Sec. VIII provides a brief overview of other ways to estimate a value function, not covered here (such as nonparametric approaches or extensions to eligibility traces). Before this, the underlying formalism is presented in Sec. II.

II. Preliminaries

A Markovian decision process (MDP) is a tuple {S, A, P, R, γ} where S is the (finite) state space, A the (finite) action space, P : s, a ∈ S × A → p(.|s, a) ∈ P(S) the family of Markovian transition probabilities, R : s, a, s ∈ S × A × S → r = R(s, a, s ) ∈ R the bounded deterministic reward function and γ the discount factor weighting long term rewards. According to these definitions, the system stochastically steps from state to state conditionally to the actions the agent performed. Let i be the discrete time step. To each transition (s i , a i , s i+1 ) is associated an immediate reward r i . The action selection process is driven by a policy π : s ∈ S → π(.|s) ∈ P(A).

A. Bellman Equations

The quality of a policy is quantified by the value function V π ∈ R S , defined as the expected discounted cumulative reward starting in a state s and then following the policy π:

V π (s) = E[ ∞ i=0 γ i r i |s 0 = s, π].
Thanks to the Markovian property, the value function of a policy π satisfies the linear Bellman evaluation equation 1 :

V π (s) = E s ,a|s,π [R(s, a, s ) + γV π (s )]. (1)
Let us define the Bellman evaluation operator

T π : V ∈ R S → T π V ∈ R S : [T π V ](s) = E s ,a|s,π [R(s, a, s ) + γV (s )].
The operator T π is a contraction and V π is its unique fixed-point:

V π = T π V π .
An optimal policy π * maximizes the associated value function for each state: π * ∈ argmax π∈P(A) S V π . The associated optimal value function, written V * , satisfies the nonlinear Bellman optimality equation:

V * (s) = max a∈A E s |s,a [R(s, a, s ) + γV * (s )].
The optimal value function is unique, but this is not necessarily the case for the optimal policy. Let us define the Bellman optimality operator

T * : V ∈ R S → T * V ∈ R S : [T * V ](s) = max a∈A E s |s,a [R(s, a, s ) + γV (s )]. (2)
The operator T * is a contraction and V * is its unique fixed-point:

V * = T * V * .
The action-value (or Q-) function encodes the values of state-action couples. This is useful in a model-free context. It is defined as the expected cumulative reward starting in s, applying a and then following π:

Q π (s, a) = E[ ∞ i=0 γ i r i |s 0 = s, a 0 = a, π].
The action-value function Q π also satisfies the linear Bellman evaluation equation:

Q π (s, a) = E s ,a |s,a,π [R(s, a, s ) + γQ π (s , a )].
It is clear that value and action-value functions are directly linked:

V π (s) = E a|s,π [Q π (s, a)].
A Bellman evaluation operator related to the Q-function can also be defined. By a slight abuse of notation, it is also written T π , the distinction being clear from the context

(T π : Q ∈ R S×A → T π Q ∈ R S×A ): [T π Q](s, a) = E s ,a |s,a,π [R(s, a, s ) + γQ(s , a )].
This operator is also a contraction and Q π is its unique fixed-point:

Q π = T π Q π .
The optimal action-value function Q * satisfies the nonlinear Bellman optimality equation too:

Q * (s, a) = E s |s,a [R(s, a, s ) + γ max a ∈A Q * (s , a )].
The associated Bellman optimality operator is defined as (with the same slight abuse of notation)

T * : Q ∈ R S×A → T * Q ∈ R S×A : [T * Q](s, a) = E s |s,a [R(s, a, s ) + γ max a ∈A Q(s , a )].
This is still a contraction and Q * is its unique fixed-point:

Q * = T * Q * .

B. Relaxed Assumptions

As mentioned in Sec. I, an important subtopic of reinforcement learning is to estimate the (action-) value function of a given policy or directly the Q-function of the optimal policy (in all cases the fixed-point of a Bellman operator) from samples, that is observed trajectories of actual interactions. More precisely, learning is done from a trajectory sampled according to a policy π, which can be seen as a set of transitions:

{(s j , a j , r j , s j+1 , a j+1 ) 1≤j≤i }. (3)
A first problem is that the model (that is transition probabilities and reward function) is assumed to be unknown. Therefore, no Bellman operator (from which we search a fixed-point for) can be computed. However, they can be estimated from transitions. The sampled Bellman value function evaluation operator T π j , to be linked to Eq. ( 1), is defined for a transition (s j , r j , s j+1 ) as:

T π j : V ∈ R S → T π j V ∈ R : T π j V = r j + γV (s j+1 ). ( 4
)
Notice that a sampled Bellman optimality operator cannot be defined for the value function (to be linked to Eq. ( 2)), as the maximum depends on the expectation. Similarly, a sampled Bellman evaluation operator can be defined for the Q-function. For a transition (s j , a j , r j , s j+1 , a j+1 ), it is defined as:

T π j : Q ∈ R S×A → T π j Q ∈ R : T π j Q = r j + γQ(s j+1 , a j+1 ).
Last but not least, a sampled Bellman optimality operator can be defined for the Q-function (thanks to the fact that the maximum depends on the expectation and not the contrary). For a transition (s j , a j , r j , s j+1 ), we define:

T * j : Q ∈ R S×A → T * j Q ∈ R : T * j Q = r j +γ max a∈A Q(s j+1 , a).
A second problem is that the state space is usually too large to allow an exact representation of the (action-) value function. Therefore, an approximate representation should be adopted. This article focuses on parametric approaches: the estimated value (respectively action-value) function is of the form Vθ (respectively Qθ ), where θ is the parameter vector; this estimate belongs to an hypothesis space,

H = { Vθ (resp. Qθ )|θ ∈ R p },
which specifies the architecture of the approximation. For example, if the state space is sufficiently small an exact tabular representation can be chosen for the value function. The estimate is thus of the form Vθ (s) = e T s θ with e s being an unitary vector which is equal to one in the component corresponding to state s and zero elsewhere. A common choice in RL is to adopt a linearly parameterized value function: in this case, Vθ (s) = φ(s) T θ with φ(s) a vector of basis functions (e.g., a linear radial basis function network) and θ the set of associated weights. More complex hypothesis spaces can be envisioned, such as neural networks. However, notice that some of the approaches reviewed in this paper do not allow handling nonlinear representations.

C. Survey Overview

Estimating a function from samples is a common topic of supervised learning. However, estimating a value function is a harder problem. Indeed, values are never directly observed, so it is not a regression problem. The available information is provided by the gathered rewards, of which the accumulation defines the value function. Therefore, supervised learning techniques cannot be directly applied to learn such a function 2 . This article reviews state-ofthe-art (parametric) value function estimation algorithms by grouping them into three categories. It will be shown that all approaches minimize the following empirical cost 2 Actually, this is not quite true. One can perform Monte Carlo rollouts starting from a given set of states to obtain related estimated returns (that is estimates of the expected discounted cumulative reward for each state of the set) and use this in any supervised learning scheme. However, this would require being able to sample many possibly infinite trajectories for each state of the set, which is therefore not really practical.

function (given for the Q-function, the value function being a special case):

θ i = argmin ω∈R p i j=1 Tj Qξ -Qω (s j , a j ) 2 (5)
where Tj denotes either T π j or T * j . Each of the three main approaches is obtained by instantiating the parameter vector ξ ∈ R p , as explained below and summarized in Tab. I. a) Bootstrapping approaches (ξ = θ j-1 ): bootstrapping approaches (reviewed in Sec. III) consist in treating value function approximation as a supervised learning problem and to derive an online algorithm. As values are not directly observable, they are replaced by an estimate computed using a sampled Bellman operator (bootstrapping refers to replacing an unobserved value by an estimate). As first noticed in [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF], this corresponds to minimizing cost function [START_REF] Wiering | Reinforcement Learning: State Of the Art[END_REF] instantiated with ξ = θ j-1 . If it is minimized using a stochastic gradient descent, this provides TD-Q and Q-learning algorithms [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], given that the sampled Bellman evaluation or optimality operator is considered. Using a (linear) recursive least-squares approach, this gives the fixed-point Kalman filter algorithm [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF].

b) Residual approaches (ξ = ω): residual approaches (reviewed in Sec. IV) consist in minimizing the squared error between the (action-) value function and its image through a Bellman operator. Practically, a sampled operator is used, which leads to biased estimates. This corresponds to minimizing cost function [START_REF] Wiering | Reinforcement Learning: State Of the Art[END_REF] instantiated with ξ = ω. If it is minimized using a stochastic gradient descent, it provides the residual algorithms of [START_REF] Baird | Residual Algorithms: Reinforcement Learning with Function Approximation[END_REF]. With a linear recursive least-squares approach, it is the parametric Gaussian Process Temporal Differences algorithm [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF], which can be extended using a statistical linearization approach to nonlinear parameterizations and to the optimality operator (the Kalman Temporal Differences framework [START_REF] Geist | Kalman Temporal Differences[END_REF]). c) Projected fixed-point approaches(ξ = θ i-1 /θ i ): projected fixed-point approaches (reviewed in Sec. V) minimize the squared error between the (action-) value function and the image of this function under the (sampled) Bellman operator projected onto the hypothesis space. This is illustrated by Fig. 1 on Page 11. It can be seen as searching for the fixed-point of an operator defined as the composition of the projection with one of the Bellman operators. Computing directly this fixedpoint corresponds to minimizing cost function (5) instantiated with ξ = θ i . Solved using a linear least-squares approach, it gives the Least-Squares Temporal Differences algorithm [START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF] (generalized using a statistical linearization approach in [13]). Solved using a stochastic gradient descent approach, it provides a bunch of algorithms: Gradient Temporal Difference 2 and Temporal Difference with gradient Correction [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF], nonlinear extension of these algorithms [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF], as well as GQ(λ), an extension to offpolicy learning and eligibility traces [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF], and Greedy-GQ, an extension to the Bellman optimality operator [START_REF] Maei | Toward Off-Policy Learning Control with Function Approximation[END_REF]. Computing the fixed-point associated to the composed operator in an iterative way corresponds to minimizing cost function (5) instantiated with ξ = θ i-1 . If solved using a linear least-squares approach, it is the Least-Squares Policy Evaluation algorithm [START_REF] Nedić | Least Squares Policy Evaluation Algorithms with Linear Function Approximation[END_REF], extended to the Bellman optimality operator in [START_REF] Yu | Q-Learning Algorithms for Optimal Stopping Based on Least Squares[END_REF]. In a batch setting and using any supervised learning algorithm instead of the projection, it is the fitted-Q approach [START_REF] Gordon | Stable Function Approximation in Dynamic Programming[END_REF] [START_REF] Ernst | Tree-Based Batch Mode Reinforcement Learning[END_REF].

Sec. III to V focus on how one can learn the action-value function from samples. How these samples are generated depends on the way the value function approximator is embedded in a more general control scheme (the ultimate goal of RL being to estimate an optimal policy), which is discussed in Sec. VI.

III. Bootstrapping Approaches

Bootstrapping approaches deal with (action-) value function approximation as a supervised learning problem. The (action-) value function of interest is assumed to be observed (either the value or action-value function of a given policy π, or directly the optimal Q-function), and it is projected onto the hypothesis space (minimizing Q -Qθ

2 ) using a stochastic gradient descent or a recursive least-squares approach.

However, resulting algorithms make use of a value which is actually not observed. Bootstrapping consists in replacing this missing observation by a pseudo-observation computed by applying a sampled Bellman operator to the current estimate of the (action-) value function. This is an easy way to understand how to derive algorithms. However, bootstrapping is not supervised learning, the actual minimized cost function is provided in Sec. III-C.

A. Bootstrapped Stochastic Gradient Descent

Algorithms presented in this section aim at estimating respectively the value function of a given policy (TD), the Q-function of a given policy (TD-Q) or directly the optimal action-value function (Q-learning) by combining the bootstrapping principle with a stochastic gradient descent over the associated empirical cost function [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

1) TD with Function Approximation: TD with function approximation (TD-VFA) aims at estimating the value function V π of a fixed policy π. Let the notation v π j depict a (possibly noisy) observation of V π (s j ). The empirical cost is:

ĴV π (θ) = j v π j -Vθ (s j ) 2 . (6)
More precisely, TD with function approximation minimizes this empirical cost function using a stochastic gradient descent: parameters are adjusted by an amount proportional to an approximation of the gradient of (6), only evaluated on a single training example. Let α i be a learning rate satisfying the classical stochastic approximation criterion: updated according to the following Widrow-Hoff equation, given the i th observed state s i :

∞ i=1 α i = ∞ and ∞ i=1 α 2 i < ∞.
θ i = θ i-1 - α i 2 ∇ θi-1 v π i -Vθ (s i ) 2 = θ i-1 + α i ∇ θi-1 Vθ (s i ) v π i -Vθi-1 (s i ) .
However, as mentioned above, the value of the state s i is not observed. It is where the bootstrapping principle applies. The unobserved value v π i is replaced by an estimate computed by applying the sampled Bellman evaluation operator (4) to the current estimate Vθi-1 (s i ). Assume that not only the current state is observed, but the whole transition (s i , s i+1 ) (sampled according to the policy π) as well as associated reward r i . The corresponding update rule is therefore:

θ i = θ i-1 + α i ∇ θi-1 Vθ (s i ) T π i Vθi-1 -Vθi-1 (s i ) with T π i Vθi-1 = r i + γ Vθi-1 (s i+1
). The idea behind using this sampled operator (and more generally behind bootstrapping) is twofold: if parameters are perfectly estimated and if the value function belongs to the hypothesis space, this provides an unbiased estimate of the actual value (the value function being the fixed-point of the unsampled operator) and this estimate provides more information as it is computed using the observed reward. Under some assumptions, notably a linear parameterization hypothesis, TD with function approximation can be shown to be convergent [START_REF] Tsitsiklis | An analysis of temporaldifference learning with function approximation[END_REF] (and it converges to the same solution as LSTD, described in Sec. V-A). This is no longer the case when it is combined with a nonlinear function approximator 3 (a counterexample is exhibited in [START_REF] Tsitsiklis | An analysis of temporaldifference learning with function approximation[END_REF]).

2) TD-Q with Function Approximation: TD-Q with function approximation (TDQ-VFA) aims at estimating the Q-function of a fixed policy π. Combined with a control component such as an -greedy or a Gibbs policy, it provides the well known SARSA algorithm (we use the name TD-Q to separate clearly policy evaluation from control, see Sec. VI). Notice that an MDP with a fixed policy defines a valued Markov chain over the state-action space, therefore value and Q-function evaluation are two similar problems. Let q π j be a (possibly noisy) observation of Q π (s j ). The considered algorithm aims at minimizing

ĴQ π (θ) = j q π j -Qθ (s j , a j ) 2 .
3 Despite this, one of the important empirical successes of RL is based on TD with neural-network-based function approximation [START_REF] Tesauro | Temporal Difference Learning and TD-Gammon[END_REF].

TD-Q with function approximation also minimizes the related empirical cost function using a stochastic gradient descent. Parameters are thus updated as follows, given the i th state-action pair (s i , a i ):

θ i = θ i-1 - α i 2 ∇ θi-1 q π i -Qθ (s i , a i ) 2 = θ i-1 + α i ∇ θi-1 Qθ (s i , a i ) q π i -Qθi-1 (s i , a i ) .
As before, q π i is not observed and it is replaced by an estimate computed by applying the sampled Bellman evaluation operator to the current estimate Qθi-1 (s i , a i ). Assume that the whole transition (s i , a i , s i+1 , a i+1 ), a i+1 being sampled according to policy π, as well as associated reward r i are observed. Parameters are therefore updated according to:

θ i = θ i-1 + α i ∇ θi-1 Qθ (s i , a i ) T π i Qθi-1 -Qθi-1 (s i , a i ) with T π i Qθi-1 = r i + γ Qθi-1 (s i+1 , a i+1
). From a practical point of view, using the Q-function instead of the value function is of interest because it does not require the model to be known in order to derive a greedy policy. Convergence results holding for TD with function approximation apply rather directly to TD-Q with function approximation.

Introduced as above, TD-Q estimates the action-value function of the policy π followed to sample the trajectory (3) used to feed the algorithm (on-policy learning). However, one may want to estimate the Q-function of some different target policy π t (off-policy learning). This can be simply done by using the same transitions and replacing T π i by T πt i . This means that the transition (s i , a i , s i+1 , a i+1 ) should be replaced by the transition (s i , a i , s i+1 , a t i+1 ), with a t i+1 being sampled according to π t (.|s t+1 ). Also, one can consider an alternative bootstrap for q πt i (with π = π t in the on-policy case). Instead of using T πt i Qθi-1 = r i + γ Qθi-1 (s i+1 , a t i+1 ), one can replace q πt i by

r i + γE a|πt,si+1 [ Qθi-1 (s i+1 , a)].

This is also an unbiased estimate of [T πt

Qθi-1 ](s i , a i ) which can be used whenever π t is known and which may lead to better estimates [START_REF] Van Seijen | A Theoretical and Empirical Analysis of Expected Sarsa[END_REF]. These ideas (off-policy and alternative bootstrap) are quite general an can be applied to any policy evaluation algorithm presented in this survey (to any algorithm estimating a Q-function and derived from the Bellman evaluation operator). However, notice that if there is a too large mismatch between the stationary distributions induced by the policies π and π t , the Q-function will be badly estimated by the offpolicy approach. For convergence properties of off-policy learning, see [START_REF] Yu | Least Squares Temporal Difference Methods: An Analysis Under General Conditions[END_REF] and references therein.

3) Q-learning with Function Approximation: Q-learning with function approximation (QL-VFA) aims at estimating directly the optimal action-value function Q * . Let q * j be a (possibly noisy) observation of Q * (s j ). This algorithm aims at minimizing the empirical cost function:

ĴQ * (θ) = j q * j -Qθ (s j , a j ) 2 .
The same approach is used, and parameters are recursively estimated using a stochastic gradient descent. Given the i th state-action pair (s i , a i ), parameters should be updated according to:

θ i = θ i-1 - α i 2 ∇ θi-1 q * i -Qθ (s i , a i ) 2 = θ i-1 + α i ∇ θi-1 Qθ (s i , a i ) q * i -Qθi-1 (s i , a i ) .
As for preceding algorithms, the bootstrapping principle is applied to estimate the unobserved q * i value, using the sampled Bellman optimality operator now, which assumes that the transition (s i , a i , s i+1 ) as well as associated reward r i are observed. Notice that Q-learning with function approximation is an off-policy algorithm, as it also evaluates a policy (the optimal one in this case) from samples generated according to a different policy. Practically, transitions can be sampled according to any sufficiently explorative policy. Parameters are updated as:

θ i = θ i-1 + α i ∇ θi-1 Qθ (s i , a i ) T * i Qθi-1 -Qθi-1 (s i , a i ) with T * i Qθi-1 = r i + γ max a∈A Qθi-1 (s i+1 , a).
Under some assumptions, notably a linear parameterization and the fact that the sampling policy π is explorative enough (it should visit all state-action pairs), QL-VFA can be shown to be convergent [START_REF] Melo | An analysis of reinforcement learning with function approximation[END_REF]. 4) A Summary View: These algorithms can be formalized using the same unified notation. First, value and action-value function evaluation (TD and TD-Q with function approximation) are somehow redundant. As V π (s) = E a|π,s [Q π (s, a)], any algorithm aiming at estimating a Qfunction can easily be specialized to the related value function, as long as the policy is known (thus, this does not apply to Q-learning with function approximation). Practically, it consists in replacing the Q-function by the value function and state-action pairs by states. Consequently, value function estimation is not considered anymore in this article. Let Tj denote either the sampled evaluation or optimality operator, depending on the context. Let also q j be either q π j or q * j , also depending on the context. TD-Q and Q-learning with function approximation aim at minimizing the following empirical cost function, which is instantiated by specifying if evaluation or direct optimization is considered:

Ĵ(θ) = j q j -Qθ (s j , a j ) 2 .
As before, parameters are estimated using a stochastic gradient descent and by applying the bootstrapping principle, which leads to the following update:

θ i = θ i-1 +α i ∇ θi-1 Qθ (s i , a i ) Ti Qθi-1 -Qθi-1 (s i , a i ) .
A practical algorithm is instantiated by specifying which of the sampled Bellman operator is used for T , that is T π or T * . Algorithms have been detailed so far, for the sake of clarity. However, in the rest of this article this summarizing point of view is adopted. Notice also that this update is actually a Widrow-Hoff equation of the following form:

θ i = θ i-1 + K i δ i . (7)
In this expression, δ i = Ti Qθi-1 -Qθi-1 (s i , a i ) is the so-called temporal difference (TD) error, which is the reward prediction error given the current estimate of the action-value function (it depends on which Bellman operator is considered) and

K i = α i ∇ θi-1 Qθ (s i , a i
) is a gain indicating in which direction the parameter vector should be corrected in order to improve the estimate. Most of (online) algorithms presented in this paper satisfy a Widrow-Hoff update.

B. Bootstrapped Recursive Least-Squares

The fixed-point Kalman Filter (FPKF) [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF] also seeks at minimizing the empirical cost function linking (actually unobserved) action-values to the estimated Q-function (still with a bootstrapping approach):

Ĵi (θ) = i j=1 q j -Qθ (s j , a j ) 2 .
However, the parameterization is assumed to be linear and a (recursive) least-squares approach is adopted instead of the stochastic gradient descent used for preceding algorithms. The considered hypothesis space is of the form

H = { Qθ : (s, a) ∈ S × A → φ(s, a) T θ ∈ R|θ ∈ R p },
where φ(s, a) is a feature vector (to be chosen beforehand). For a given state-action couple (s j , a j ), φ(s j , a j ) is shortened as φ j . The corresponding empirical objective function can thus be rewritten as:

Ĵi (θ) = i j=1 q j -φ T j θ 2 .
Thanks to linearity in parameters, this cost function is convex and has a unique minimum:

θ i = argmin θ∈R p Ĵi (θ).
This optimization problem can be solved analytically by zeroing the gradient of Ĵi (θ); this is the principle of the least-squares method. Parameters are thus estimated as:

θ i =   i j=1 φ j φ T j   -1 i j=1 φ j q j .
Let us write P -1 i = i j=1 φ j φ T j . The Sherman-Morrison formula allows updating directly the inverse of a rank-one perturbed matrix:

P i = P i-1 - P i-1 φ i φ T i P i-1 1 + φ T i P i-1 φ i .
This allows estimating parameters recursively:

θ i = θ i-1 + P i-1 φ i 1 + φ T i P i-1 φ i q i -Qθi-1 (s i , a i ) .
As for algorithms presented in Sec. III-A, the bootstrapping principle is applied and the unobserved q i actionvalue is replaced by the estimate Ti Qθi-1 :

θ i = θ i-1 + P i-1 φ i 1 + φ T i P i-1 φ i Ti Qθi-1 -Qθi-1 (s i , a i ) .
This equation is actually a Widrow-Hoff update [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF].

The temporal difference error is still δ i = Ti Qθi-1 -Qθi-1 (s i , a i ); this prediction error term is actually common to all algorithms aiming at estimating the action-value function.The gain depends on the fact that a least-squares minimization has been considered:

K i = P i-1 φ i 1 + φ T i P i-1 φ i .
This gain can be compared to the one obtained using a stochastic gradient descent approach, presented in Sec. III-A. With a linear parametrization, the corresponding gain is K i = α i φ i . Therefore, FPKF can be seen as a variation of TD-Q or Q-learning for which there is some automatic coordinate-based step-size adaptation.

If the sampled Bellman evaluation operator is considered, the FPKF update rule specializes as:

θ i = θ i-1 + K i r i + γφ T i+1 θ i-1 -φ T i θ i-1 .
If the sampled Bellman optimality operator is considered, this update rule specializes as:

θ i = θ i-1 + K i r i + γ max a∈A φ(s i+1 , a) T θ i-1 -φ T i θ i-1 .
This algorithm can be shown to be convergent under some assumptions, for both sampled operators (evaluation and optimality in the case of optimal stopping problems). See [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF] for details.

C. Summary

The principle of bootstrapping algorithms is to derive an online algorithm which minimizes a supervised-learningbased cost function:

θ i = argmin ω∈R p i j=1 (q j -Qω (s j , a j )) 2 .
As values are not observed, the bootstrapping principle is applied: the unobserved q j value is replaced by some estimate. Given that we are looking for a fixed-point of one of the Bellman operators, this estimate is provided by Tj Qθj-1 . Therefore, bootstrapping approaches solve the following optimization problem (as first noticed in [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF]):

θ i = argmin ω∈R p i j=1 Tj Qθj-1 -Qω (s j , a j ) 2 .
This corresponds to Eq. ( 5) instantiated with ξ = θ j-1 . Practical algorithms are then derived given that this cost function is minimized using a stochastic gradient descent or a recursive least-squares approach, and given what Bellman operator is considered. This is summarized in the first column of Tab. I on Page 5.

IV. Residual Approaches

Residual approaches aim at finding an approximation of the fixed-point of one of the Bellman operators by minimizing the distance between the (action-) value function and its image through one of the Bellman operators. The associated cost function is:

J(θ) = Qθ -T Qθ 2 .
Practically, learning is done using samples and the Bellman operator is replaced by a sampled Bellman operator, the model (particularly transition probabilities) being unknown. The associated empirical cost function is therefore:

Ĵ(θ) = j Qθ (s j , a j ) -Tj Qθ 2 . (8)
A common drawback of all approaches aiming at minimizing this cost function is that they produce biased estimates of the (action-) value function. Basically, this is due to the fact that the expectation of a square is not the square of the expectation:

E sj+1|sj ,aj ,π [(Q(s j , a j ) -Tj Q) 2 ] = (Q(s j , a j ) -(T Q)(s j , a j )) 2 + Var sj+1|sj ,aj ,π ( Tj Q).
There is an unwanted variance term acting as a penalty factor which favorises smooth functions. If such penalties are commonly used for regularization, this one is harmful here as it cannot be controlled [START_REF] Antos | Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path[END_REF]. All methods presented below can be modified so as to handle this problem, this will be shortly discussed. However, it is important to notice that any algorithm aiming at minimizing this cost presents this bias problem.

A. Residual Stochastic Gradient Descent

So-called residual algorithms (R-SGD for residual stochastic gradient descent) have been introduced in [START_REF] Baird | Residual Algorithms: Reinforcement Learning with Function Approximation[END_REF].

Their principle is to minimize the empirical cost function (8) using a stochastic gradient descent. The corresponding update rule is therefore:

θ i = θ i-1 - α i 2 ∇ θi-1 ( Qθ (s i , a i ) -Ti Qθ ) 2 with ∇ θi-1 ( Qθ (s i , a i ) -Ti Qθ ) 2 = ∇ θi-1 Qθ (s i , a i ) -Ti Qθ Ti Qθi-1 -Qθi-1 (s i , a i ) .
Here again, this update is actually a Widrow-Hoff equation (see Eq. ( 7)) with δ i = Ti Qθi-1 -Qθi-1 (s i , a i ) and

K i = α i ∇ θi-1 ( Qθ (s i , a i ) -Ti Qθ ).
If the sampled Bellman evaluation operator is considered, gain and temporal difference error are given by:

K i = α i ∇ θi-1 Qθ (s i , a i ) -γ Qθ (s i+1 , a i+1 ) , δ i = r i + γ Qθi-1 (s i+1 , a i+1 ) -Qθi-1 (s i , a i ).
A first problem arises when the sampled Bellman optimality operator is considered. In this case, we have:

K i = α i ∇ θi-1 Qθ (s i , a i ) -γ max a∈A Qθ (s i+1 , a) , δ i = r i + γ max a∈A Qθi-1 (s i+1 , a) -Qθi-1 (s i , a i ).
Here, the gradient of the max operator must be computed: ∇ θi-1 (max a∈A Qθ (s i+1 , a)). This is not straightforward; if this gain is introduced in [START_REF] Baird | Residual Algorithms: Reinforcement Learning with Function Approximation[END_REF], no solution is provided to compute it 4 . Another problem is that these algorithms compute biased estimates of the (action-) value function, as explained above. This is inherent to all approaches minimizing a residual cost function using a sampled Bellman operator. In order to handle this problem, it is proposed in [START_REF] Baird | Residual Algorithms: Reinforcement Learning with Function Approximation[END_REF] to use a double sampling scheme. Let us consider the Bellman evaluation operator. Two transitions are independently generated from the state-action couple (s i , a i ): (s i , a i , r i , s i+1 , a i+1 ) and (s i , a i , r i , s i+1 , a i+1 ). One of these transitions is used to compute the gain, and the other one to compute the TD error:

K i = α i ∇ θi-1 Qθ (s i , a i ) -γ Qθ (s i+1 , a i+1 ) , δ i = r i + γ Qθi-1 (s i+1 , a i+1 ) -Qθi-1 (s i , a i ).
These two transitions being sampled independently, taking the expectation of K i δ i leads to the use of the true (that is unsampled) Bellman operator, without variance term contrary to the use of the same transition in both gain and TD error. However, this suggests that transitions can be sampled on demand (for example using a simulator), which might be a strong assumption.

B. Residual Least-Squares

In this section, methods based on a least-squares minimization of cost function [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF] are reviewed. The parametric Gaussian Process Temporal Differences [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF] algorithm minimizes it by assuming a linear parameterization as well as the Bellman evaluation operator, and the Kalman Temporal Differences framework [START_REF] Geist | Kalman Temporal Differences[END_REF] generalizes it to nonlinear parameterizations as well as to the Bellman optimality operator thanks to a statistical linearization approach [START_REF] Anderson | An Introduction to Multivariate Statistical Analysis[END_REF].

1) Gaussian Process Temporal Differences: Assuming a linear parametrization and the Bellman evaluation operator, cost function ( 8) is linear and can be rewritten as:

J i (θ) = i j=1 (r j + γφ T j+1 θ -φ T j θ) 2 . ( 9
)
Thanks to the linearity in parameters, it can be solved using a recursive least-squares approach: zeroing the gradient (∇ θ J i (θ) = 0) provides a batch estimate which can be made recursive by using the Sherman-Morrison formula. To any least-squares problem can be linked a so called observation model, linking outputs to inputs through the hypothesized parametric model plus some white observation noise n j . In this case, it is simply the sampled Bellman evaluation equation:

r j = φ T j θ -γφ T j+1 θ + n j .
With a unitary noise (that is n j is of unitary variance, P nj = 1), the corresponding least-squares problem is provided by Eq. ( 9).

The (parametric) Gaussian Process Temporal Differences (GPTD) algorithm [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF] considers the same observation model, with a not necessarily unitary noise n j . The effect of the noise variance is to weight square terms in the minimized cost function, this is the slight difference with cost (9):

J i (θ) = i j=1 1 P nj r j + γφ T j+1 θ -φ T j θ 2 .
If one has some prior knowledge about the noise n i , this can be used to obtain this simple weighted least-squares problem. If not, it is sufficient to consider a constant variance (therefore weighting no longer affects the solution of this optimization problem).

Let us write ∆φ j = φ j -γφ j+1 . The unique parameter vector minimizing the above convex cost-function can be computed analytically by zeroing the gradient with respect to the parameter vector:

θ i = argmin θ∈R p J i (θ) =   i j=1 1 P nj ∆φ j ∆φ T j   -1 i j=1 1 P nj ∆φ j r j .
Let us write

P i = ( i j=1 1 Pn j ∆φ j ∆φ T j ) -1
. Thanks to the Sherman-Morrison formula, P i can be computed iteratively and parameters can be estimated recursively. Let θ 0 and P 0 be some priors, the (parametric) GPTD algorithm is given by these two equations:

θ i = θ i-1 + P i-1 ∆φ i P ni + ∆φ T i P i-1 ∆φ i r i -∆φ T i θ i-1 , P i = P i-1 - P i-1 ∆φ i ∆φ T i P i-1 P ni + ∆φ T i P i-1 ∆φ i .
One can recognize the temporal difference error δ i = r i -∆φ T i θ i-1 and a gain K i = Pi-1∆φi Pn i +∆φ T i Pi-1∆φi , to be linked again with the generic Widrow-Hoff update [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF]. Notice that P i is actually a variance matrix quantifying the uncertainty over current parameters estimation (it is the variance of the parameter vector conditioned on past i observed rewards). This is not clear from the proposed leastsquares-based derivation, however it is direct by adopting a Bayesian perspective [START_REF] Engel | Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning[END_REF]. Notice that this interpretation of P i as being a variance matrix can be useful for handling the dilemma between exploration and exploitation [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF].

As all other residual methods, GPTD produces biased estimates of the value function when transitions are stochastic. To alleviate this problem, a colored observation noise n j can be used instead of the classical white noise assumption (a noise being white if ∀i = j, n i and n j are independent, and a colored noise is any non-white noise) [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF]. This noise allows removing the bias (because it leads to minimizing another cost function, linking state estimates to Monte Carlo samples of the discounted return [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF] [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF]Ch. 4.4.3]), but it also induces a memory effect which prevents from learning in an off-policy manner, much like eligibility traces do (e.g., see [START_REF] Precup | Eligibility Traces for Off-Policy Policy Evaluation[END_REF]). These developments are not pursued here (they rely mainly on Bayesian inference and eligibility traces, just the later topic being briefly addressed in Sec. VIII).

The GPTD framework has been originally introduced in a different, non-parametric, manner [START_REF] Engel | Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning[END_REF]: the value function is modeled as a Gaussian process and a kernelbased online sparsification scheme is used to obtain a practical algorithm. As we focus on parametric value function approximation, the algorithm we review is the parametric GPTD [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF]Sec. 4.3]. There also exists an LSTD-based variation of GPTD (see Sec. V-A for LSTD), derived from a maximum likelihood interpretation of the LSTD algorithm [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF]Sec. 4.5]. In the parametric case, it is actually an 2 -regularized form of LSTD, so it is not further developed here.

2) Kalman Temporal Differences: As the GPTD framework, the Kalman Temporal Differences framework [START_REF] Geist | Kalman Temporal Differences[END_REF] also seeks at minimizing cost function [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF], not necessarily considering a unitary noise variance too. Let us write

Ti Q = r i + γ Pi Q with: Pi Q = Q(s i+1 , a i+1 ) (if sampled evaluation op.) max a∈A Q(s i+1 , a) (if sampled optimality op.
) .

Estimated parameters should minimize:

Ĵi (θ) = i j=1 1 P nj r j -Qθ (s j , a j ) -γ Pj Qθ 2 . (10)
Contrary to GPTD, KTD does not assume a linear parameterization nor the sampled evaluation operator. Instead, it makes use of a derivative-free linearization scheme (the derivative-free aspect allows considering the sampled optimality operator), the so-called statistical linearization [START_REF] Anderson | An Introduction to Multivariate Statistical Analysis[END_REF].

The basic idea is to linearize this cost function (taking the distribution of parameters into account), which can subsequently be solved using a classical recursive leastsquares approach. Linearization of (10) goes through the linearization of the associated observation model (to be considered as a function of θ, the state-action couple being fixed):

r j = Qθ (s j , a j ) -γ Pj Qθ + n j . (11)
Assume that it is evaluated in n sampled parameter vectors θ (k) of associated weights w k (how to sample them practically and efficiently being addressed later):

θ (k) , r (k) j = Qθ (k) (s j , a j ) -γ Pj Qθ (k)
1≤k≤n

.

The following statistics of interest are defined:

θ = n k=1 w k θ (k) , rj = n k=1 w k r (k) j , (12)
P θ = n k=1 w k θ (k) -θ θ (k) -θ T , P θrj = n k=1 w k θ (k) -θ r (k) j -rj T = P T rj θ , P rj = n k=1 w k r (k) j -rj 2 . (13)
Statistical linearization consists in linearizing the nonlinear observation model [START_REF] Geist | Kalman Temporal Differences[END_REF] around θ (with P θ being actually the spread of sampling) by adopting a statistical point of view. It finds a linear model r j = A j θ + b j + u j , u j being a noise, by minimizing the sum of square errors between values of nonlinear and linearized functions in the regression points:

(A j , b j ) = argmin A,b n k=1 e (k) j 2 with e (k) j = r (k) j -Aθ (k) + b
The solution of this optimization problem is given by:

A j = P rj θ P -1 θ and b j = rj -A j θ.
Moreover, it is easy to check that the covariance matrix of the error is given by:

P ej = n k=1 e (k) j 2 = P rj -A j P θ A T j .
The nonlinear observation model [START_REF] Geist | Kalman Temporal Differences[END_REF] can thus be replaced by the following equivalent linear observation model:

r j = A j θ + b j + u j with u j = e j + n j .
Notice that the linearization error is taken into account through the noise e j . Noises e j and n j being independent, the variance of P uj is given by P uj = P ej + P nj . Given this statistically linearized observation model, the least-squares problem can be rewritten in a linear form:

θ i = argmin θ∈R p   i j=1 1 P uj (r j -A j θ -b j ) 2   =   i j=1 1 P uj A T j A j   -1 i j=1 A j (r j -b j ) .
With this cost function, the higher is the statistical linearization error of a given transition (quantified by P uj through P ej ), the less the corresponding square term contributes to the cost. Using the Sherman-Morrison formula, a recursive update of this estimate can be obtained (expressing the gain K i directly as a function of the statistics of interest defining A i and b i and assuming some priors θ 0 and P θ0 ):

K i = P θiri P ui + P ri , θ i = θ i-1 + K i (r i -ri ) , (14)
P θi = P θi-1 -K i (P vi + P ri ) K T i .
Here again, the gain's magnitude is directly linked to the linearization error, and large errors will result in small updates (this can be seen as an automatic learning rate). Eq. ( 14) corresponds also to a Widrow-Hoff update, with r i -ri being a statistically linearized temporal difference error (r i is a prediction of the reward given the currently estimated Q-function and the experienced transitions; the algorithm does not optimize a myopic TD error). How to actually sample parameter vectors in order to perform statistical linearization is addressed now. With this recursive estimation, θ i-1 (the previous estimate) and P i-1 (the associated uncertainty matrix, as explained in Sec. IV-B1) are known, and the issue is to compute A i and b i . A first thing is to choose the point around which to linearize and with which magnitude. It is legitimate to sample around the previous estimate θ i-1 and with a spread related to the uncertainty of these estimates. In other words, n parameter vectors are sampled such that θi = θ i-1 and P θi = P i-1 . Notice that θi , the point around which linearization is performed in order to update parameters, is different from θ i , the updated parameter vector. There remains the choice of how parameter vectors are sampled. A natural idea would be to assume a Gaussian distribution of mean θ i-1 and variance P i-1 and to compute statistics of interest (Eqs. [START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF] to ( 13)) using a Monte Carlo approach. However, this would be particularly inefficient. Actually, the problem of sampling these points can be stated as follows: how to sample a random variable (here the parameter vector) of known mean and variance (here θ i-1 and P i-1 ) in order to compute accurate estimates of first and second order moments of a nonlinear mapping of this random variable (here Qθ (s i , a i )-γ Pi Qθ ). The unscented transform [START_REF] Julier | A new extension of the Kalman filter to nonlinear systems[END_REF] provides a solution to this problem and is used by the KTD framework 5 . Full details are provided in [START_REF] Geist | Kalman Temporal Differences[END_REF].

KTD generalizes GPTD in the sense that it allows handling nonlinearities: nonlinear parameterization thanks to the linearization, and the (sampled) Bellman optimality operator thanks to the fact that this linearization scheme does not rely on a gradient computation. Notice that KTD reduces to parametric GPTD if a linear parameterization as well as the sampled Bellman evaluation operator are considered. As other residual approaches, KTD suffers from the bias problem when system transitions are stochastic. In order to handle this issue, a colored noise model (based on the idea of eligibility traces) can be used [START_REF] Geist | Eligibility Traces through Colored Noises[END_REF] (which is actually a generalization of the noise proposed in [START_REF] Engel | Reinforcement Learning with Gaussian Processes[END_REF] for GPTD). However, as mentioned in Sec. IV-B1, this induces some memory effects which prevent from learning in an off-policy manner. Consequently, the sampled Bellman optimality operator can no longer be considered in this setting, because of its off-policy aspect. Using a colored noise also leads to minimizing a different cost function. As for GPTD, these developments are not pursued here, see the corresponding papers [START_REF] Geist | Eligibility Traces through Colored Noises[END_REF][34] [START_REF] Precup | Eligibility Traces for Off-Policy Policy Evaluation[END_REF].

Notice that the available uncertainty information (matrix P i ) can be useful for the dilemma between exploration and exploitation [START_REF]Managing Uncertainty within the KTD framework[END_REF] [START_REF] Daubigney | Uncertainty management for online optimisation of a POMDP-based large-scale spoken dialogue system[END_REF].

C. Summary

Residual approaches aim at finding an approximation of the fixed-point of one of the Bellman operators by minimizing the distance between the (action-) value function and its image through one of the Bellman operators. The associated theoretical cost function is J(θ) = Qθ -T Qθ 2 . Practically, learning is done using samples and the Bellman operator is replaced by its sampled counterpart, the model being unknown. The associated empirical cost function is therefore:

θ i = argmin ω∈R p i j=1 Tj Qω -Qω (s j , a j ) 2 .
This is exactly Eq. ( 5) instantiated with ξ = ω. Minimizing this cost function by considering one of the Bellman operator and using either a stochastic gradient descent or a recursive least-squares approach (possibly generalized using a statistical linearization) provides one of the presented algorithms (see the second column of Tab. I).

A common drawback of all approaches aiming at minimizing this cost function is that they produce biased estimates of the (action-) value function: minimizing the empirical cost function [START_REF] Choi | A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning[END_REF] does not lead to minimize the theoretical cost function Qθ -T Qθ 2 asymptotically. All methods presented in Sec. IV can be modified so as to handle the problem: a double sampling scheme is suggested in Sec. IV-A, and original methods based on coloring the observation noise in Sections IV-B1 and IV-B2. Nevertheless, it is important to notice that any algorithm aiming at minimizing this cost presents this bias problem.

V. Projected Fixed-point Approaches

Projected fixed-point approaches seek at minimizing the distance between the estimated action-value function and the projection (the projection operator being written Π) of the image of this function under a Bellman operator onto the hypothesis space H:

J(θ) = Qθ -ΠT Qθ 2 with Πf = argmin f ∈H f -f 2 . ( 15
)
This is illustrated in Fig. 1. The action-value function estimate Qθ lies in the hypothesis space H. Its image under a Bellman operator T Qθ does not necessarily lye on this hypothesis space. Residual approaches of Sec. IV try to minimize the distance between these two functions, that is line 1 in Fig. 1, with the drawback that using a sampled Bellman operator leads to biased estimates, as discussed before. The function T Qθ can be projected onto the hypothesis space, this projection minimizing the distance between T Qθ and the hypothesis space (line 2 in Fig. 1). Projected fixed-point methods aim at minimizing the distance between this projection and Qθ , represented by line 3 in Fig. 1. Contrary to bootstrapping and residual approaches, least-squares-based algorithms have been introduced before stochastic-gradient-based ones for solving the projected fixed-point problem. Thus, they are reviewed first.

A. Least-Squares-based Approaches

This section reviews algorithms which use a leastsquares approach to minimize the empirical cost linked to [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF]:

θ i = argmin θ∈R p i j=1
Qθ (s j , a j ) -Qω θ (s j , a j ) 2 [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF] with ω θ = argmin

ω∈R p i j=1 Qω (s j , a j ) -Tj Qθ 2 . ( 17
)
Obviously, cost related to ( 16) is minimized for θ = ω θ (assuming that this equation has a solution, which can at least be ensured for the evaluation operator and a linear parametrization). Therefore, nested optimization problems ( 16) and ( 17) can be summarized as θ i = ω θi :

θ i = argmin ω∈R p i j=1 Qω (s j , a j ) -Tj Qθi 2 . ( 18
)
Notice that as θ i appears in both sides of this equation, this is not a pure quadratic cost function, but a fixed-point problem. The least-squares temporal differences (LSTD) algorithm [START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF] assumes a linear parameterization and the (sampled) Bellman evaluation operator in order to solve the above optimization problem. The statistically linearized LSTD (slLSTD) algorithm [13] generalizes it to nonlinear parameterizations and to the (sampled) Bellman optimality operator thanks to a statistical linearization process (the generalization from LSTD to slLSTD being quite close to the generalization from GPTD to KTD). 1) Least-Squares Temporal Differences: LSTD6 assumes a linear parameterization as well as the sampled Bellman evaluation operator. Using the same notations as before, optimization problem ( 18) can be rewritten as:

θ i = argmin ω∈R p i j=1 r j + γφ T j+1 θ i -φ T j ω 2 .
Thanks to linearity in ω (linear parameterization assumption), this can be analytically solved:

θ i =   i j=1 φ j φ T j   -1 i j=1 φ j r j + γφ T j+1 θ i .
Thanks to linearity in θ i (linear parameterization and evaluation operator assumptions), the parameter vector can be isolated:

θ i =   i j=1 φ j (φ j -γφ j+1 ) T   -1 i j=1 φ j r j . (19)
Eq. ( 19) defines the (batch) LSTD estimate. Let us write M -1 i = i j=1 φ j ∆φ T j . Thanks to the Sherman-Morrison formula, a recursive form of this estimation process can be obtained (assuming some priors θ 0 and M 0 ):

K i = M i-1 φ i 1 + (φ i -γφ i+1 ) T M i-1 φ i , θ i = θ i-1 + K i r i + γφ T i+1 θ i-1 -φ T i θ i-1 , M i = M i-1 -K i M T i-1 (φ i -γφ i+1 ) T .
Once again, K i is a gain and r i + γφ T i+1 θ i-1 -φ T i θ i-1 a temporal difference error, to be linked to the Widrow-Hoff update [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF].

LSTD can be slightly modified to have an improved computational cost [START_REF] Geramifard | Incremental Least-Squares Temporal Difference Learning[END_REF] (assuming that the features are sparse, which is not necessarily the case), and it can be "mixed" with a residual approach [START_REF] Johns | Hybrid least-squares algorithms for approximate policy evaluation[END_REF].

2) Statistically Linearized LSTD:

The slLSTD algorithm [13] generalizes LSTD: it does not assume a linear parameterization nor the Bellman evaluation operator. The corresponding optimization problem is therefore (this equation being valid thanks to the subsequent linearization):

θ i = argmin ω∈R p i j=1 r j + γ Pj Qθi -Qω (s j , a j ) 2 . ( 20
)
How slLSTD generalizes LSTD is very close to how KTD generalizes GPTD: a statistical linearization is performed, which allows solving this optimization problem analytically and recursively. Eq. ( 20) can be linked to the following observation model (n j being here a unitary white and centered observation noise):

r j + γ Pj Qθi = Qω (s j , a j ) + n j . ( 21
)
The noise is chosen unitary to strengthen parallel to LSTD, but extension to non-unitary noise is straightforward. As for KTD, a statistical linearization is performed. However, here two different quantities have to be linearized: Qω (s j , a j ) and Pj Qθi . Assume that n parameter vectors ω (k) of associated weights w k are sampled (using the unscented transform), and that their images are computed:

ω (k) , q (k) j = Qω (k) (s j , a j ) 1≤k≤n .
Using the statistical linearization process explained in Sec. IV-B2 and defining the statistics of interest accordingly to Eqs. ( 12) to (13), the following linear observation model is obtained:

Qω (s j , a j ) = A j ω + b j + e j (22)
with A j = P qj ω P -1 ω , b j = qj -A j ω

and P ej = P qj -A j P ω A T j .

Recall that the noise e j is centered and can be sampled as e

(k) j = q (k) j -(A j ω (k) + b j ).
The term P Qθi (s j , a j ) also needs to be linearized. Assume that n parameter vectors θ (k) i of associated weights w k are sampled (again using the unscented transform), and that their images are computed:

θ (k) i , p (k) qj = P Qθ (k) i (s j , a j ) 1≤k≤n .
Using the statistical linearization process explained in Sec. IV-B2 and defining the statistics of interest accordingly to Eqs. ( 12) to (13), the following linear observation model is obtained:

P Qθi (s j , a j ) = C j θ i + d j + j (23)
with C j = P pq j θi P -1 θi , d j = pqj -C j θi and P j = P pq j -C j P θi C T j .

Recall that the noise j is centered and can be sampled as

(k) j = p (k) qj -(C j θ (k) i + d j ).
Notice also that θi is not equal to θ i a priori.

Linearized models ( 22) and ( 23) can be injected into observation model ( 21):

r j + γ (C j θ i + d j + j ) = A j ω + b j + e j + n j ⇔ r j + γ (C j θ i + d j ) = A j ω + e j -γ j + n j .
The linearization error is taken into account in the centered noise u j of variance P uj :

u j = n j + e j -γ j and P uj = E[u 2 j ].
This equivalent observation model leads to the following optimization problem, which can be solved analytically:

θ i = argmin ω∈R p i j=1 1 P uj (r j + γ (C j θ i + d j ) -(A j ω + b j )) 2 (24)
= ( i j=1 1 P uj A T j (A j -γC j )) -1 i j=1 1 P uj A j (r j + γd j -b j ) . (25)
This is the statistically linearized variation of optimization problem [START_REF] Gordon | Stable Function Approximation in Dynamic Programming[END_REF] (which explains the similarity between the LSTD batch estimate [START_REF] Yu | Q-Learning Algorithms for Optimal Stopping Based on Least Squares[END_REF] and Eq. ( 25)). Also, similarly to what happens with KTD, the statistical linearization error is taken into account through the noise variance P uj (the bigger the statistical linearization error, the lesser the impact of the related sample on the learning process). The Sherman-Morrison formula allows again deriving a recursive estimation of θ i . Assume that some priors θ 0 and M 0 are chosen, the slLSTD algorithm is defined as:

K i = M i-1 A T i P ui + (A i -γC i ) M i-1 A T i , θ i = θ i-1 + K i (r i + γd i -b i -(A i -γC i ) θ i-1 ) , M i = M i-1 -K i M T i-1 (A i -γC i ) T T
.

Notice that once again, this satisfies the Widrow-Hoff update, with a gain K i and a temporal difference error

r i + γd i -b i -(A i -γC i )θ i-1
(which can be shown to simplify as r i + γ pqi -qi , the TD error being more visible under this form). Given this recursive formulation, there still remains to choose how to sample parameter vectors (related to ω and θ i ) in order to compute A i , b i , C i , d i and P ui . As for KTD, the unscented transform is used to sample these parameter vectors. The parameter vector ω to be considered is the solution of Eq. [START_REF] Watkins | Q-learning[END_REF], that is the solution of the fixed-point problem θ i = ω θi . In this recursive estimation context, it is legitimate to linearize around the last estimate θ i-1 . The mean being chosen, the only remaining choice is the associated variance P i-1 . In [13], it is proposed to use the same variance matrix as would have been provided by a statistically linearized recursive leastsquares [START_REF] Geist | Statistically Linearized Recursive Least Squares[END_REF] used to perform supervised learning of the approximate action-value function given true observations of the Q-values. The fact that the unobserved actionvalues are not used to update the variance matrix tends to legitimate this choice. The associated matrix update is:

P i = P i-1 - P i-1 A T i A i P i-1 1 + A i P i-1 A T i
The same approach is used to compute C i and d i , coming from the statistical linearization of Pi Qθi . As before, the linearization is performed around the last estimate θ i-1 and considering the matrix variance Σ i-1 provided by a statistical linearized recursive least-squares that would perform a supervised regression of Pi Qθi :

Σ i = Σ i-1 - Σ i-1 C T i C i Σ i-1 1 + C i Σ i-1 C T i
These choices being made, A i , b i , C i and d i can be computed, see [13] for details. A last thing is to compute the variance P ui of the noise u i = n i + e i -γ i . The noise n i is independent of others, and the variance of e i -γ i can be computed using the unscented transform, which provides an analytical expression for this variance.

Mixing all these elements, the slLSTD can be built. Notice that it can be easily shown that with a linear parameterization and the (sampled) Bellman evaluation operator, slLSTD indeed reduces to LSTD [13] (this relies on the fact that the unscented transform is no longer an approximation for a linear mapping). Notice also that slLSTD being a projected fixed-point approach, it does not suffers from the bias problem, even if the observation noise is assumed to be white (contrary to GPTD/KTD).

B. Stochastic Gradient Descent-based Approaches

Algorithms presented in this section aim at minimizing the same cost function, that is :

J i (θ) = argmin θ∈R p i j=1
Qθ (s j , a j ) -Qω θ (s j , a j ) 2 [START_REF] Tsitsiklis | An analysis of temporaldifference learning with function approximation[END_REF] with Qω θ = Π T Qθ .

However, here a stochastic gradient descent approach is considered instead of the least-squares approach of the above section. Algorithms presented in Sec. V-B1, namely Gradient Temporal Difference 2 (GTD2) and Temporal Difference with Gradient Correction (TDC) [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF], assume a linear parameterization and the (sampled) Bellman evaluation operator. Algorithms presented in Sec. V-B2, namely nonlinear GTD2 (nlGTD2) and nonlinear TD (nlTDC) [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF], extend them to the case of a nonlinear parameterization. The (linear) TDC algorithm has also been extended to eligibility traces [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF] and to the Bellman optimality operator [START_REF] Maei | Toward Off-Policy Learning Control with Function Approximation[END_REF], these extensions being briefly presented in Sec. V-B3.

1) Gradient Temporal Difference 2, Temporal Difference with Gradient Correction: GTD2 and TDC algorithms [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF] aim at minimizing cost function [START_REF] Tsitsiklis | An analysis of temporaldifference learning with function approximation[END_REF] while considering the Bellman evaluation operator, and they differ on the route taken to express the gradient followed to perform the stochastic gradient descent. Both methods rely on a linear parameterization, and are based on a reworked expression of the cost function. Let Q be:

Q = Q(s 1 , a 1 ) . . . Q(s i , a i ) T .
Cost function ( 26) can be rewritten as:

J i (θ) = Qθ -Qω θ 2 = ( Qθ -Qω θ ) T ( Qθ -Qω θ ). ( 27
)
Let also Φ i (respectively Φ i ) be the p × i matrix which columns are the features φ(s j , a j ) (respectively φ(s j+1 , a j+1 )):

Φ i = φ(s 1 , a 1 ) . . . φ(s i , a i ) and Φ i = φ(s 2 , a 2 ) . . . φ(s i+1 , a i+1 ) .
Let R i be the set of observed rewards:

R i = r 1 . . . r i T .
As the parameterization is linear and as the Bellman evaluation is considered, the Q-values and their images through the sampled operator are given as:

Qθ = Φ T i θ, T Qθ = R i + γ (Φ i ) T θ.
Qω θ is the projection of T Qθ onto the hypothesis space.

Let us write Π i the empirical projection:

Qω θ = Φ T i ω θ = Π i T Qθ with Π i = Φ T i Φ i Φ T i -1 Φ i .
Cost function [START_REF] Tesauro | Temporal Difference Learning and TD-Gammon[END_REF] can thus be rewritten as:

J i (θ) = Φ T i θ -Π i R i + γ (Φ i ) T θ 2 .
Two basic properties of projection operator are useful here. First, Π i Φ T i θ = Φ T i θ (the hypothesis space is invariant under the projection operator). Second, Π i Π T i = Π i . Using these relationships, the cost can be rewritten as:

J i (θ) = (Φ T i θ -R i -γ(Φ i ) T θ) T Π i (Φ T i θ -R i -γ(Φ i ) T θ).
Let δ j (θ) = r j + γφ T j+1 θ -φ T j θ be the temporal difference error, J i (θ) is finally given as:

J i (θ) = ( i j=1 φ j δ j (θ)) T ( i j=1 φ j φ T j ) -1 ( i j=1 φ j δ j (θ)). ( 28
)
Notice that a Gradient Temporal Difference (GTD) algorithm has been first introduced by considering a slightly different cost function [START_REF] Sutton | A Convergent O(n) Algorithm for Off-policy Temporal-difference Learning with Linear Function Approximation[END_REF]:

J i (θ) =   i j=1 φ j δ j (θ)   T   i j=1 φ j δ j (θ)   .
This explains why the algorithm of [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF] is called GTD2. The negative gradient of cost function ( 28) is given by:

- 1 2 ∇ θ J i (θ) = (29)
  i j=1 (φ j -γφ j+1 ) φ T j     i j=1 φ j φ T j   -1   i j=1 δ j (θ)φ j   .
In order to avoid a bias problem, a second modifiable parameter vector ω ∈ R p is used to form a quasi-stationary estimate of the term ( i j=1 φ j φ T j ) -1 ( i j=1 δ j (θ)φ j ), this being called the weight-doubling trick. Parameter vector θ is updated according to a stochastic gradient descent:

θ i = θ i-1 + α i (φ i -γφ i+1 ) φ T i ω i-1 .
Their remains to find an update rule for ω i . In order to obtain a O(p) algorithm, it is also estimated using a stochastic gradient descent [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF]. One can remark that ω i is actually the solution of a linear least-squares optimization problem:

ω i =   i j=1 φ j φ T j   -1 i j=1 δ j (θ)φ j = argmin ω∈R p i j=1 φ T j ω -δ j (θ) 2 . ( 30
)
This suggests the following update rule for ω i (minimization of Eq. ( 30) using a stochastic gradient descent):

ω i = ω i-1 + β i φ i δ i (θ i-1 ) -φ T i ω i-1 .
Learning rates satisfy the classical stochastic approximation criterion. Moreover, they are chosen such that β i = ηα i with η > 0. The GTD2 algorithm is thus:

θ i = θ i-1 + α i (φ i -γφ i+1 ) φ T i ω i-1 , ω i = ω i-1 + β i φ i δ i (θ i-1 ) -φ T i ω i-1 , with δ i (θ) = r i + γφ T i+1 θ -φ T i θ.
Under some assumptions, this algorithm can be shown to be convergent to the fixed point of ΠT [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF]. Notice that if this algorithm is derived from the gradient of an objective function, it is not a true stochastic gradient method, because the expected weight update direction may differ from the direction of the negative gradient of the objective function (it is a pseudo-gradient method) [START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF].

By expressing the gradient in a slightly different way, another algorithm called TDC can be derived. Rewrites Eq. ( 29):

- 1 2 ∇ θ J i (θ) =   i j=1 δ j (θ)φ j   -γ   i j=1 φ j+1 φ T j     i j=1 φ j φ T j   -1   i j=1 δ j (θ)φ j   .
This gives rise to the following update for θ, ω being updated as before:

θ i = θ i-1 + α i φ i δ i (θ i-1 ) -α i γφ i+1 φ T i ω i-1 .
This algorithm is called TD with gradient correction because the first term, α i φ i δ i (θ i-1 ), is the same as for TD with function approximation (see Sec. III-A) under a linear function approximation architecture, and the second term, -α i γφ i+1 φ T i ω i-1 , acts as a correction. For TDC, learning rates α i and β i are chosen such as satisfying the classic stochastic approximation criterion, and such that lim i→∞ αi βi = 0. This means that θ i is updated on a slower time-scale. The idea behind this is that ω i should look stationary from the θ i point of view. The TDC algorithm can be summarized as follows:

θ i = θ i-1 + α i φ i δ i (θ i-1 ) -α i γφ i+1 φ T i ω i-1 , ω i = ω i-1 + β i φ i δ i (θ i-1 ) -φ T i ω i-1 , with δ i (θ) = r i + γφ T i+1 θ -φ T i θ.
This algorithm can also be shown to be convergent (also to ΠT ) under some assumptions [START_REF] Sutton | Fast gradient-descent methods for temporal-difference learning with linear function approximation[END_REF].

2) Nonlinear extensions: in [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF], GTD2 and TDC are extended to the case of a general nonlinear parameterization Qθ , as long as it is differentiable with respect to θ. The corresponding hypothesis space H = { Qθ |θ ∈ R p } is a differentiable submanifold onto which projecting is generally not computationally feasible. One may assume that the parameter vector θ is slightly updated in one step (given that learning rate are usually small), which causes the surface of the submanifold to be close to linear. Therefore, projection is done onto the tangent plane defined as T H = {(s, a) ∈ S ×A → ω T ∇ θ Qθ (s, a)|ω ∈ R p } (in other words, linearization of Qθ (s, a) by a first order Taylor expansion). The corresponding projection operator Π θ i can be obtained as in Sec. V-B1, the tangent space being an hyperplane:

Π θ i = Φ θ i T Φ θ i Φ θ i T -1 Φ θ i , with Φ θ i = ∇ θ Qθ (s 1 , a 1 ) . . . ∇ θ Qθ (s i , a i ).
The corresponding cost function can therefore be derived as in Sec. V-B1, with basically feature vectors φ(s, a) being replaced by linearized features φ θ j = ∇ θ Qθ (s j , a j ), and by writing δ j (θ) the temporal difference error r j + γ Qθ (s j+1 , a j+1 ) -Qθ (s j , a j ):

J i (θ) = ( i j=1 φ θ j δ j (θ)) T ( i j=1 φ θ j (φ θ j ) T ) -1 ( i j=1 φ θ j δ j (θ)).
The gradient of this cost function is [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF]:

- 1 2 ∇ θ J i (θ) =   i j=1 φ θ j -γφ θ j+1 φ θ j T   ω i + h(θ, ω i ) (31)
= i j=1 δ j (θ)φ θ j -γ   i j=1 φ θ j+1 φ θ j T   ω i + h(θ, ω i ) (32)
with

ω i =   i j=1 φ θ j φ θ j T   -1   i j=1 δ j (θ)φ θ j   and h(θ, ω) = - i j=1 δ j (θ) -φ θ j T ω ∇ 2 Qθ (s j , a j ) ω.
GTD2 and TDC are generalized to nlGTD2 and nlTDC using a stochastic gradient descent on the above cost function. Parameter vector ω i is updated as in Sec. V-B1:

ω i = ω i-1 + β i φ θi-1 i δ i (θ i-1 ) -φ θi-1 i T ω i-1 .
The nonlinear GTD2 algorithm performs a stochastic gradient descent according to Eq. ( 31):

θ i = θ i-1 + α i φ θi-1 i -γφ θi-1 i+1 φ θi-1 i T ω i-1 -h i with h i = δ i (θ i-1 ) -φ θi-1 i T ω i-1 ∇ 2 θi-1 Qθ (s i , a i ) ω i-1 .
Learning rates are chosen as for the TDC algorithm, that is satisfying the classic stochastic approximation criterion and such that lim i→∞ αi βi = 0, which means that θ is updated on a slower timescale than ω. The nonlinear TDC algorithm performs a stochastic gradient descent according to Eq. ( 32):

θ i = θ i-1 +α i φ θi-1 i δ i (θ i-1 ) -γφ θi-1 i+1 φ θi-1 i T ω i-1 -h i with h i = δ i (θ i-1 ) -φ θi-1 i T ω i-1 ∇ 2 θi-1 Qθ (s i , a i ) ω i-1 .
Learning rates are chosen as above. Both nlGTD2 and nlTDC can be shown to be convergent to an undefined local minimum under some assumptions [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF].

3) Extensions of TDC: the TDC algorithm (see Sec. V-B1) has been extended to eligibility traces in [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF]. Moreover, this algorithm, called GQ(λ), allows off-policy learning, that is learning the value of one target policy while following another behaviorial policy. This new algorithm (for which some convergence guarantees are provided) still minimizes the empirical cost function linked to [START_REF] Maei | Convergent temporal-difference learning with arbitrary smooth function approximation[END_REF]. However, instead of the T π Bellman operator considered so far, an eligibility-based T π λ operator is used (λ being the eligibility factor), this operator being defined as the expected λ-return. See [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF] for more details. Using eligibility traces induce a memory effect which prevents from learning in an off-policy manner without caution, see [START_REF] Precup | Eligibility Traces for Off-Policy Policy Evaluation[END_REF] for example. To cope with this problem, importance sampling [START_REF] Ripley | Stochastic Simulation[END_REF] is used in [START_REF] Maei | GQ(λ): a general gradient algorithm for temporal-differences prediction learning with eligibility traces[END_REF] (the idea of using importance sampling for value function approximation having been first introduced in [START_REF] Precup | Eligibility Traces for Off-Policy Policy Evaluation[END_REF]). They present GQ(λ) as an extension of Q-learning, which can be misleading. Actually, they consider off-policy learning (with a known and fixed target policy), but not the Bellman optimality operator.

Nevertheless, the TDC algorithm has also been extended to this operator [START_REF] Maei | Toward Off-Policy Learning Control with Function Approximation[END_REF] (this new algorithm being called Greedy-GQ). To do so, they consider the Bellman evaluation operator T π θ for a policy π θ which depends on the currently estimated action-value function (through parameters θ). Therefore, the considered policy is nonstationary (it evolves with parameters' estimation). If π θ is greedy with respect to the learnt value function, then it is equivalent to considering the Bellman optimality operator. However, in this case, there are some non-differentiability problems (due to the max operator), and Fréchet subdifferentials are used to provide the algorithm [START_REF] Maei | Toward Off-Policy Learning Control with Function Approximation[END_REF]. A convergence analysis for these algorithms is also provided [START_REF] Maei | Toward Off-Policy Learning Control with Function Approximation[END_REF].

C. Iterative projected fixed point

Methods presented so far in Sec. V aim at minimizing the distance between the action-value function and the projection of the image of this function under a Bellman operator onto the hypothesis space:

J(θ) = Qθ -ΠT Qθ 2 .
This can be interpreted as trying to find a fixed-point of the operator ΠT , which is the composition of the projection operator Π and of one of the Bellman operator T .

Assuming that this operator is a contraction (which is not always the case, it depends on the projection operator), there exists a unique fixed-point which can be found by iterating the application of the ΠT operator:

Qθi = ΠT Qθi-1 .
Methods presented in this section adopt this point of view to provide algorithms. 1) Fitted-Q: Fitted-Q is a batch algorithm. It assumes that a set of N transitions is available beforehand: {(s j , a j , r j , s j+1 , a j+1 )} 1≤j≤N .

An initial Q-function Qθ0 is considered, and estimates are refined by iterating the (sampled) ΠT operator:

Qθi = Π T Qθi-1 , ∀i > 0.
Some important comments have to be made here. A sampled Bellman operator is used, because as usual transition probabilities are unknown. Most of time, fitted-Q suggests the sampled Bellman optimality operator, but this approach is of course still valid for the sampled Bellman evaluation operator. The Π operator indeed represents any supervised learning algorithm (which can be more or less directly seen as a projection). Notice that the representation of the estimated action-value function is not necessarily parametric (e.g., using a tree-based supervised learning algorithm [START_REF] Ernst | Tree-Based Batch Mode Reinforcement Learning[END_REF]).

A practical example is given now. Assume that at iteration i the estimate Qθi-1 is available. A first thing is to compute the image of this estimate through the sampled Bellman (here optimality) operator. This consists in computing the following training base, composed of state-action couples and estimated optimal Qvalues: {(s j , a j , r j + γ max a∈A Qθi-1 (s j+1 , a))} 1≤j≤N . A supervised learning algorithm is then used on this set, associating inputs (s j , a j ) to estimated outputs r j + γ max a∈A Qθi-1 (s j+1 , a). This iteration is repeated until a stopping criterion is met (e.g., a maximum number of steps or little changes in the representation).

The fitted-Q idea probably dates back to [START_REF] Samuel | Some studies in machine learning using the game of checkers[END_REF]. Its convergence properties have been analyzed in [START_REF] Gordon | Stable Function Approximation in Dynamic Programming[END_REF], who reasons on the contraction property of the ΠT operator. In [START_REF] Munos | Performance Bounds in Lp norm for Approximate Value Iteration[END_REF], its performance bounds in p norm is analyzed. This is particularly judicious: if performance bounds of supervised learning algorithms are very often analyzed in p norm, this is not the case for (approximate) dynamic programming which is most of the time analyzed in ∞ norm. Fitted-Q has been considered with many different function approximators. For example, see [START_REF] Ormoneit | Kernel-Based Reinforcement Learning[END_REF] for fitted-Q with a kernel-based regression, [START_REF] Riedmiller | Neural Fitted Q Iteration -First Experiences with a Data Efficient Neural Reinforcement Learning Method[END_REF] for fitted-Q with neural networks trained by backpropagation or [START_REF] Ernst | Tree-Based Batch Mode Reinforcement Learning[END_REF] for fitted-Q with tree-based methods.

2) Least-Squares Policy Evaluation: The least-squares policy evaluation (LSPE) algorithm has been proposed7 in [START_REF] Nedić | Least Squares Policy Evaluation Algorithms with Linear Function Approximation[END_REF]. It is directly introduced using the concept of eligibility traces, but this aspect is left apart in this article. The LSPE algorithm can be roughly seen as a fitted-Q algorithm using a linear parameterization, the (sampled) Bellman evaluation operator and for which a new training sample is added to the training set at each iteration. Thanks to linearity (linear parameterization and evaluation operator), an efficient online algorithm can be obtained.

The LSPE algorithm solves recursively Qθi = Π i T Qθi-1 , the Π i projection operator being defined in Sec. V-B1. Given linearity, this can be rewritten as:

θ i = argmin θ∈R p i j=1 φ T j θ -r j -γφ T j+1 θ i-1 2 =   i j=1 φ j φ T j   -1 i j=1 φ j r j + γφ T j+1 θ i-1 = θ i-1 + ( i j=1 φ j φ T j ) -1 i j=1 φ j (r j -(φ j -γφ j+1 ) T θ i-1 ).
All terms involved can be computed recursively and efficiently, using notably the Sherman-Morrison formula:

B -1 i =   i j=1 φ j φ T j   -1 = B -1 i-1 - B -1 i-1 φ i φ T i B -1 i-1 1 + φ T i B -1 i-1 φ i , A i = i j=1 φ j (φ j -γφ j+1 ) T = A i-1 + φ i (φ i -γφ i+1 ) T , b i = i j=1 φ j r j = b i-1 + φ i r i .
The LSPE update can therefore be expressed in a form close to a Widrow-Hoff update:

θ i = θ i-1 + B -1 i (b i -A i θ i-1 ) .
Actually, the way LSPE is presented here differs from [START_REF] Nedić | Least Squares Policy Evaluation Algorithms with Linear Function Approximation[END_REF] in the sense that the B -1 i matrix is originally scaled with a learning rate. The algorithm presented here is the case where the learning rate is chosen constant and equal to one. This algorithm (with a constant learning rate equal to one) is shown to be convergent in [START_REF] Bertsekas | Learning and Approximate Dynamic Programming[END_REF]. Notice that ideas behind LSPE have other applications [START_REF] Bertsekas | Projected Equation Methods for Approximate Solution of Large Linear Systems[END_REF] and can also be linked to variational inequalities [START_REF] Bertsekas | Projected Equations, Variational Inequalities, and Temporal Difference Methods[END_REF].

3) Q-learning for optimal stopping problems: The Qlearning for optimal stopping problems (Q-OSP) [START_REF] Yu | Q-Learning Algorithms for Optimal Stopping Based on Least Squares[END_REF] extends LSPE to the (sampled) Bellman optimality operator, the parameterization being still linear. This algorithm is originally presented in the case of optimal stopping problems, which are a restrictive class of Markovian decision processes. However, it is presented here in the general case.

The derivation of this algorithm is the same as for the LSPE one, by considering the optimality operator instead of the evaluation one:

θ i = argmin θ∈R p i j=1 φ T j θ -r j -γ max a∈A φ(s j+1 , a) T θ i-1 =   i j=1 φ j φ T j   -1 i j=1 r j + γ max a∈A φ(s j+1 , a) T θ i-1 .
The matrix ( i j=1 φ j φ T j ) -1 can still be computed recursively and efficiently. However, this is not the case for the term i j=1 (r j + γ max a∈A (φ(s j+1 , a) T θ i-1 )) which requires remembering the whole trajectory and needs to be computed at each iteration. In [START_REF] Yu | Q-Learning Algorithms for Optimal Stopping Based on Least Squares[END_REF] this algorithm is shown to be convergent for optimal stopping problems and under some assumptions, and some more computationally efficient variations for the same restrictive class of MDPs are also proposed.

D. Summary

Projected fixed-point approaches seek at estimating a fixed-point of the composed operator ΠT , Π being the projection onto the hypothesis space H and T being one of the Bellman operator. This fixed-point can be computed directly, which corresponds to minimizing Qθ -ΠT Qθ 2 . The associated optimization problem is given by:

θ i = argmin ω∈R p i j=1 Qω (s j , a j ) -Tj Qθi 2 .
This is Eq. ( 5) instantiated with ξ = θ i . If solved with a recursive least-squares approach, it gives the LSTD algorithm (or its statistical-linearization-based generalization). If solved using a stochastic gradient descent, it can provide GTD2 and TDC as well as their generalization to nonlinear parametrization, and their extensions to offpolicy learning and to the Bellman optimality operator (GQ(λ) and greedy GQ).

Other approaches search for this fixed point using an iterative method: Qθi = ΠT Qθi-1 . The corresponding optimization problem is:

θ i = argmin ω∈R p i j=1
Qω (s j , a j ) -Tj Qθi-1 2 . This is Eq. ( 5) instantiated with ξ = θ i-1 . Solved using a least-squares approach, it provides LSPE or Q-OSP, given what Bellman operator is considered. In a batch setting and using any supervised learning algorithm as the projection, it is fitted-Q. See the third column of Tab. I.

VI. Control

The ultimate goal of reinforcement learning is the control problem, that is computing an optimal control policy. We show here how the studied value function approximators integrate in the more general control problem.

A. Batch learning

Assume that a set of trajectories, sampled according to some (explorative enough) behaviorial policy, is available. In a batch setting, the aim is to estimate an optimal policy from the available data. To do so, approximate dynamic programming (ADP) can be used.

Approximate policy iteration (API) is generally speaking a policy iteration scheme where the policy evaluation step is approximated. API is initialized with some policy π 0 . At each time step k, policy π k is evaluated using any approximate policy evaluation algorithm fed with the available data (that is, any action-value function approximator based on the Bellman evaluation operator and used in an off-policy setting, as explained in Sec. III-A2). This gives an estimate Qπ k θ , which is used to improve the policy: π k+1 (s) = argmax a Qπ k θ (s, a), notably for any s in the dataset. The process iterates until some stopping criterion is satisfied. A classic API algorithm is LSPI (Least-Squares Policy Iteration) [START_REF] Lagoudakis | Least-squares policy iteration[END_REF], which uses LSTD as the value function approximator. However, any other policy evaluation algorithm could be used (TD-Q, GPTD, TDC, etc.). Notice that instead of working with an imposed set of data, new trajectories could be generated at each iteration (generally, using the current estimated policy slightly perturbed, in order to ensure variety of samples).

Approximate value iteration (AVI) consists in computing directly an estimate of the optimal value function. Generally speaking, any value function approximator based on the Bellman optimality operator (such as Q-learning, greedy-GQ, KTD or slLSTD for example) can serve as an AVI algorithm, even if fitted-Q is perhaps best known. Given the available dataset and a value function approximator (based on T * ), an estimate Q * θ of the optimal actionvalue function is computed, and it is used to provide an estimated optimal policy: π * (s) = argmax a Q * θ (s, a). Notice that other approximate dynamic programming algorithms exist, such as ADP based on linear programming [START_REF] De Farias | The Linear Programming Approach to Approximate Dynamic Programming[END_REF][59], on modified policy iteration [START_REF] Scherrer | Approximate Modified Policy Iteration[END_REF] or on conservative policy iteration [START_REF] Kakade | Approximately optimal approximate reinforcement learning[END_REF]. However, these do not necessarily rely on a value function approximation algorithm.

B. Online learning

Assume that the goal is now to learn in an online fashion, that is improving the policy while interacting with the system. This can be handled by an asynchronous API approach: at each time step, the greedy action (with respect to the currently estimated Q-function) is applied and the action-value function is updated using any policy evaluation algorithm (this implies using an online value function approximator, generally in an on-policy setting).

However, learning online induces a dilemma between exploration and exploitation and the greedy action should not be applied at each time step. Instead, from time to time an explorative action (suboptimal according to the currently estimated action-value function but with the potential to improve this estimate) should be chosen. A classic asynchronous API approach is SARSA: the Qfunction is updated according to the TD-Q algorithm (onpolicy setting) and the applied action is chosen according to an -greedy policy (greedy action with probability 1 -, random action else). However, any policy evaluation algorithm could be used instead (such as R-SGD, GPTD, LSTD, etc.), and other action selection schemes could be envisioned (such as a Gibbs sampling approach, for example).

Notice that learning control online induces nonstationarity problems: as the evaluated policy depends on the currently estimated Q-function, it actually changes at each time step, and the value function approximator should take this into account. If gradient-based policy evaluation algorithms handle this well, thanks to the use of a learning rate, this is not the case for least-squaresbased algorithms. A simple solution to this problem is to add a forgetting factor to the minimized cost function:

θ i = argmin ω∈R p i j=1 β i-j
Tj Qξ -Qω (s j , a j )

2

, where 0 β < 1 is the forgetting factor. Notice that more general schemes for handling non-stationarity are possible through the original formulation of the KTD framework [START_REF] Geist | Kalman Temporal Differences[END_REF].

Similarly, it is possible to consider asynchronous AVI. This is exactly the same approach, replacing the policy evaluation algorithm by a value function approximator based on the Bellman optimality operator (this approximator must be able to learn in an online fashion, which could exclude fitted-Q). Asynchronous AVI tends to be less cautious than asynchronous API, in the sense that the estimated Q-function do not take into account the explorative steps of the action selection scheme (this cautious aspect also depends heavily on the exploration strategy). This is well illustrated by the cliff-walking task [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]Ch. 6.5].

C. Actor-critic algorithms

The online approaches discussed so far use an explicit representation for the action-value function, but not for the policy (which depends explicitly on the Q-function). Actor-critic methods [START_REF] Barto | Neuronlike adaptive elements that can solve difficult learning control problems[END_REF][63][64] [START_REF] Peters | Natural Actor-Critic[END_REF][66] use an explicit representation for both these objects (Q and π). This approach as several advantages. Notably, it allows considering in a principled way continuous actions (which are a problem due to the greedy and the max operators of other approaches) and it somehow implicitly handles the dilemma between exploration and exploitation.

Assume that the policy π w is parameterized by some vector w. Actor-critic algorithms aim at maximizing the value on a distribution d 0 of starting state: find w such that ρ(w) = E s∼d0 [V πw ] is maximum. This can be done by performing a gradient ascent (or possibly a natural gradient ascent [START_REF] Peters | Natural Actor-Critic[END_REF]): w i+1 = w i + α i ∇ρ(w i ). Let d π denote the so-called discounted stationary distribution, d π (s) = (1 -γ) i≥0 γ i P (s i = s|s 0 , π), the gradient admits an analytical expression [START_REF] Sutton | Policy Gradient Methods for Reinforcement Learning with Function Approximation[END_REF]:

∇ρ(w) = 1 1 -γ E s∼d πw ,a∼πw(.|s) [Q πw (s, a)∇ w π w (a|s)].
Generally speaking, actor-critic approaches maximize ρ using a (natural) gradient ascent, and the gradient ∇ρ is estimated using an approximation of the Q-function Q πw (instead of the unavailable true Q-function). However, one cannot use any approximation Qθ of Q πw [START_REF] Konda | On Actor-Critic Algorithms[END_REF] [START_REF] Sutton | Policy Gradient Methods for Reinforcement Learning with Function Approximation[END_REF]. First, Qθ must be a "good approximation" of Q πw (in a least-squares sense, see [START_REF] Sutton | Policy Gradient Methods for Reinforcement Learning with Function Approximation[END_REF] for details). Second, the parameterizations of Qθ and π w must be "compatible", meaning that they should satisfy [START_REF] Konda | On Actor-Critic Algorithms[END_REF][64]:

∇ θ Qθ (s, a) = ∇ w ln π w (a|s).
Therefore, choosing one parameterization imposes the other.

At this stage, one can remark that if the parameterization is compatible, then E a∼π(.|s) [ Qθ (s, a)] = 0: Qθ is not a Q-function, but an advantage function (generally defined as A(s, a) = Q(s, a) -V (s)). Algorithms studied in this survey do not allow learning directly such a function, and the literature offers variations of existing algorithms to learn Qθ (s, a) (e.g., see the LSTD-Q variation in [START_REF] Peters | Natural Actor-Critic[END_REF]).

There is a simple solution to this problem. As shown in [START_REF] Geist | Revisiting natural actor-critics with value function approximation[END_REF], it is possible to replace Q πw by a "good approximation" Qθ,ξ (s, a) = f θ (s, a) + g ξ (s) with ∇ θ f θ (s, a) = ∇ w ln π w (a|s) (no specific condition on g ξ ). This way, Qθ,ξ is actually an action-value function (not an advantage function) and all important theorems of [START_REF] Sutton | Policy Gradient Methods for Reinforcement Learning with Function Approximation[END_REF][65] can be shown to hold. Therefore, one can plug its favorite parametric policy evaluation algorithm in an actor-critic approach, see [START_REF] Geist | Revisiting natural actor-critics with value function approximation[END_REF] for details. However, notice that if the compatibility condition is satisfied, the "good approximation" condition may not be perfectly satisfied. Nevertheless, it often works well in practice.

VII. Algorithms comparison

This section aims at comparing surveyed algorithms. First, alternative taxonomies are provided. Then, we discuss when choosing what algorithm, depending on the context. Finally, we give some pointers to the literature, regarding experimental results.

A. Alternative taxonomies

Surveyed algorithms have been divided into three categories (bootstrapping, residual and projected fixed-point) and two subcategories (gradient-based or least-squaresbased). Other taxonomies are possible, as summarized in Tab. II.

First, they either estimate the action-value function of a given policy (Q π ) or the optimal Q-function (Q * ) directly. In the first case, they can be used as the policy evaluation component of a more general API scheme, as explained above. In the second case, they provide directly the optimal policy through the estimated Q-function, which is an AVI scheme. This is depicted as pi/vi in Tab. II (equivalently, pi means that the Bellman evaluation operator is considered and vi means that the Bellman optimality operator is considered). Some of the reviewed algorithms are only defined for linear parameterization of the action-value function, whereas others allow considering nonlinear architectures such as multi-layered neural networks (mainly through a gradient descent or thanks to a statistical linearization). This is depicted as l/nl in Tab. II.

A point not discussed so far is the computational (and memory) complexity of the reviewed algorithms. There are basically two cases. For stochastic gradient descentbased algorithms, complexity is in O(p), and for recursive least-squares-based approach, complexity is in O(p 2 ). Notice that for algorithms handling the Bellman optimality operator, these complexities have to be scaled by the number of actions (because of the max computation). Exceptions (to the two aforementioned cases) are fitted-Q (which complexity depends on the considered supervised learning scheme) and Q-OSP (which is moreover linear in the length of the trajectory). Considering the sample efficiency of these algorithms, second order approaches are usually more efficient (a notable exception being FPKF, see [START_REF] Scherrer | Recursive Least-Squares Learning with Eligibility Traces[END_REF]).

Lastly, some algorithms produce biased estimates (residual approaches, if not combined with a double sampling scheme or with some colored noise), whereas the other provide unbiased estimates (bootstrapping and projected fixed-point). This is depicted as b/ub in Tab. II. We also recall how ξ is instantiated (see Eq. ( 5)) and if the algorithm is based on a stochastic gradient descent (sgd) or a recursive least-squares (rls) approach.

B. Which algorithm to choose?

One can wonder when choosing what algorithm. Unfortunately, there is no easy answer to this. Nevertheless, we try to give some clues here.

First, one may choose between (asynchronous) API and AVI. We think that the choice between an online and a batch learning algorithm (that is asynchronous or not) is more linked to the studied problem than a real choice (is the data imposed? can we sample easily trajectories?). Choosing between API and AVI is a matter of taste (as far as we know, there is no definitive argument in favor of one or the other).

Second, one can choose between a residual and a bootstrapping or a projected fixed-point approach (bootstrapping and projected fixed-point approaches converge to the same limit, when convergence occurs). Residual approaches are more stable and more predictable [START_REF] Munos | Error Bounds for Approximate Policy Iteration[END_REF], but they suffer from the bias problem (which disappears when the transitions are deterministic). Other arguments in favor of each approach (residual vs projected fixedpoint) are developed in [START_REF] Scherrer | Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The unified oblique projection view[END_REF]. Therefore, if the dynamic is (near-) deterministic (or even Lipschitz from our own experience), then a residual method could be chosen (stability argument), else a projected fixed-point or bootstrap approach must be preferred.

If the residual approach is rejected, there is still the choice between bootstrapping and projected fixed-point approaches. Generally speaking, gradient-based bootstrapping algorithms offer less theoretical guarantees than their projected fixed-point counterparts, but they empirically learn faster and tuning meta-parameters is easier. This is no longer true for the least-squares-based algorithms: FPKF is much slower than LSTD (due to the bootstrapping), and they provide the same solution asymptotically.

Then, one can choose between a gradient-based and a least-squares based approach. Least-squares approaches are more sample efficient (which can be theoretically argued in some cases, see for example the finite sample analysis of LSTD [START_REF] Lazaric | Finite-Sample Analysis of LSTD[END_REF]), but they also have a higher computational cost. So this choice is a trade-off between sample efficiency and computational cost. If samples are costly to generate or imposed, we advocate to use a leastsquares approach. In the other hand, if there are many features (thus many parameters to be learnt) and if the transitions are easy to generate, gradient-based methods may be preferred.

We have provided a unified derivation of surveyed algorithms, but most of them were introduced differently than in their original derivation. Notably, concerning GPTD [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF] and KTD [START_REF] Geist | Kalman Temporal Differences[END_REF], the parameter vector to be learnt is modeled as a random variable of which mean and variance are estimated 8 . Therefore, during learning, uncertainty information about parameters estimates is available. This can be used to compute some variance about the estimated action-value function, for any stateaction couple. This can be useful for solving the dilemma between exploration and exploitation (for example, it may be interesting to choose an action with a low estimated value if this estimate is uncertain or adopt an optimistic action selection). See [START_REF]Managing Uncertainty within the KTD framework[END_REF] for a discussion on this subject. The same idea can be adapted to (sl)LSTD, less directly, see [13] for details.

One can also choose between linear and nonliear parameterization. If good linear features are available, it is certainly better to use them, thus to choose a linear parametric value function approximator. However, sometimes a multi-layered artificial neural network can provide better results (generally speaking, the underlying hypothesis space may be richer). In this case, one has to choose an RL algorithm able to handle such nonlinearities. Notice that the only algorithms to come with theoretical guarantees in the nonlinear case are nlTDC and nlGTD2 (but KTD and slLSTD work well in practice, and learn faster, but at a higher computational cost).

Last but not least, the ease of implementation (or the availability of some library) and the ease of choosing the meta-parameters can also drive the choice of the algorithm. Generally speaking, linear-least-squares-based algorithms are easier to tune (there is no learning rate).

C. Experimental comparisons

Another point not addressed so far in this article is the thorough experimental comparison of the reviewed algorithms. This is beyond the scope of this algorithmic survey, but Tab. III provides links to the literature, showing where a comparison between algorithm X and algorithm Y can be found (often within a control scheme). This table can be read line by line. Please notice that this does not pretend to be exhaustive (for example, there are some application papers, notably for dialogue management in spoken dialog systems, but not all of them are reported).

In the table, gradBoot refers to gradient-based bootstrapping algorithms (TD-V, TD-Q, Q-learning), gradRes refers to gradient-based residual algorithms (R-SGD), gradPFP refers to gradient-based projected-fixed-point approaches (GTD2, TDC and greedy-GQ) and itPFP refers to iterated fixed-point algorithms (LSPE and Q-OSP, fitted-Q being left appart). If an algorithm is compared to itself in the table, it means either that it is actually a group of algorithms (as gradBoot for example) or that the paper contains some illustrative example (as the illustration of the variance information provided by the GPTD algorithm in [START_REF] Engel | Algorithms and Representations for Reinforcement Learning[END_REF]) or some problem-specific experiment/large-scale application.

VIII. Other value function approximators

This article surveys parametric value function approximators, but there exist other ways to estimate a value function. Some of them are briefly mentioned hereafter.

A. Extension to eligibility traces

TD learning with eligibility traces [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], known as TD(λ), provides a nice bridge between temporal difference learning and Monte Carlo learning, and by controlling the bias/variance trade-off [START_REF] Kearns | Bias-Variance Error Bounds for Temporal Difference Updates[END_REF], their use can significantly speed up learning. When the value function is approximated through a linear architecture, the depth λ of the eligibility traces is also known to control the quality of approximation [START_REF] Tsitsiklis | An analysis of temporaldifference learning with function approximation[END_REF].

Using eligibility traces amounts to looking for the fixedpoint of the following variation of the Bellman operator [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF] (here we assume a fixed policy, that is the evaluation problem): T λ V = (1 -λ) ∞ i=0 λ i T i+1 V . As we have introduced a sampled Bellman operator to derive surveyed algorithms, the same can be done for this T λ operator. For a partial trajectory (s k , r k , s k+1 ) j≤k≤i-1 , we define T λ j,i the sampled and truncated operator (e.g., see [START_REF] Scherrer | Recursive Least-Squares Learning with Eligibility Traces[END_REF]):

T λ j,i V = V (s j ) + i k=j (γλ) k-j (r k + γV (s k+1 ) -V (s k )).
This being defined, the work done in this survey can be repeated by replacing Tj by T λ j,i in Eq. ( 5):

θ i = argmin ω∈R p i j=1
T λ j,i Vξ -Vω (s j , a j )

2

.

Notice that this only holds for the evaluation problem (the Bellman optimality operator is not considered) and in the on-policy case. To handle the off-policy case, it is necessary to use also importance sampling. See [68][79], where this approach is used to derive new off-policy least-squaresbased and eligibility-traces-based algorithms.

B. Nonparametric approaches

Given an approximation architecture, this survey has shown that there exists a bunch of approaches to learn the corresponding parameters. However, choosing a judicious hypothesis space is highly problem-dependent and it is generally a difficult issue. Therefore, we think that research fields such as feature construction, feature selection, or more generally non-parametric value function approximation are of primary importance.

The GPTD algorithm [START_REF] Engel | Bayes Meets Bellman: The Gaussian Process Approach to Temporal Difference Learning[END_REF] is kernel-based and nonparametric in its more general form (not presented here). Using the same idea (that is constructing the span of the feature space implicitly defined by a Mercer kernel), the LSTD algorithm has been kernelized [START_REF] Xu | Kernel-Based Least Squares Policy Iteration for Reinforcement Learning[END_REF] as well as the LSPE algorithm [START_REF] Jung | Kernelizing LSPE(λ)[END_REF]. More generally, kernelized approaches to value function approximation are discussed in [START_REF] Taylor | Kernelized Value Function Approximation for Reinforcement Learning[END_REF].

Feature selection via 1 -regularization has also been envisioned for non-parametric value function approximation: adding an 1 -penalty term imposes some parameters to be exactly zero, which allows handling the case p n (much more features than samples). Adding such a penalty term to value function approximation is not straightforward and there are many ways to do it. See [START_REF] Loth | Sparse temporal difference learning using lasso[END_REF] for an approach based on residual minimization and [START_REF] Kolter | Regularization and Feature Selection in Least-Squares Temporal Difference Learning[END_REF][85] [START_REF] Geist | 1 -penalized projected Bellman residual[END_REF][87] [START_REF] Geist | A Dantzig Selector Approach to Temporal Difference Learning[END_REF] for approaches based on projected fixed-point ( [START_REF] Geist | A Dantzig Selector Approach to Temporal Difference Learning[END_REF] provides a synthetic overview of these methods).

Another approach consists in generating features, based on the Bellman error [START_REF] Menache | Basis Function Adaptation in Temporal Difference Reinforcement Learning[END_REF][90] [START_REF] Parr | Analyzing Feature Generation for Value-Function Approximation[END_REF][92] [START_REF] Wu | Automatic Induction of Bellman-Error Features for Probabilistic Planning[END_REF] or upon graph structure built from observed trajectories through the state space [START_REF] Mahadevan | Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes[END_REF]. State aggregation (e.g., [START_REF] Bertsekas | Adaptive aggregation methods for infinite horizon dynamic programming[END_REF] [START_REF] Singh | Reinforcement learning with soft state aggregation[END_REF]) can also be seen as a feature generation scheme. Other methods are based on local averagers or kernel smoothers (usually Nadaraya-Watson-like estimators) [START_REF] Ormoneit | Kernel-Based Reinforcement Learning[END_REF][97] [START_REF] Barreto | Reinforcement learning using kernel-based stochastic factorization[END_REF]. These are examples among others, this general topic would deserve another survey.

C. Other criteria

In this article, the quality of a policy is quantified by the value function defined as the expected discounted cumulative reward, V π (s) = E[ i≥0 γ i r i |s 0 = s, π]. Other criteria can be envisioned, such as the finite horizon criterion (and the value function is then V π (s) = E[ H i=0 r i |s 0 = s, π] for some predefined horizon H) or the average-reward criterion (for which the value function is defined as V π (s) = lim H→∞ 1 H E[ H i=0 r i |s 0 = s, π]). The γ-discounted criterion considered in this article is probably the most frequently used in the literature, but notice that the work done here cannot be directly adapted to the other criteria.

IX. Conclusion

This article has reviewed a large part of the state of the art in parametric (action-) value function approximation. Basically, it has been shown that all these approaches can be derived from the unified cost function [START_REF] Wiering | Reinforcement Learning: State Of the Art[END_REF]. Further, they can be categorized in three main classes, given the considered cost function (related to bootstrapping, residual or projected fixed-point). In each of these groups, they can be categorized given that the cost function is minimized using a stochastic gradient descent or a recursive least-squares approach (except fitted-Q, which can be considered with any supervised learning algorithm). Projected fixed-point approaches can be divided into two approaches, given that the cost function is directly minimized or that the underlying possible fixed-point is searched for using an iterative scheme. All of this is summarized in Tab. I on Page 5. Sec. VI to VIII have given clues on how the surveyed value function approximators can be used for control, how they can be compared and what are other possible (not covered) approaches for estimating a value function.

Fig. 1 .

 1 Fig. 1. Projected fixed-point principle.

max a∈A Qθ (s i+1 , a) is generally non-differentiable resp. to θ; a solution could be to rely on Fréchet subdifferentials[START_REF] Kruger | On Fréchet subdifferentials[END_REF].

Notice that other approximation schemes can be considered instead of the unscented transform, such as the scaled unscented transform[START_REF] Julier | The scaled unscented transformation[END_REF], approximation schemes based on Sterling interpolation[START_REF] Nørgård | New developments in state estimation for nonlinear systems[END_REF] or more generally sigma-point-based transforms[START_REF] Van Der Merwe | Sigma-point kalman filters for probabilistic inference in dynamic state-space models[END_REF].

Notice that LSTD has not been originally introduced as a projected fixed point method (like in[START_REF] Lagoudakis | Least-squares policy iteration[END_REF]), but as a residual least-squares debiased using instrumental variables[START_REF] Söderström | Instrumental variable methods for system identification[END_REF]. See[START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF] for details.

Actually, if the name LSPE has been introduced in[START_REF] Nedić | Least Squares Policy Evaluation Algorithms with Linear Function Approximation[END_REF] (in a multistep value-iteration context), the related algorithm has first been introduced in[START_REF] Bertsekas | Temporal Differences-Based Policy Iteration and Applications in Neuro-Dynamic Programming[END_REF], where it is built upon λ-policy-iteration.

What allows us deriving it differently here is the close link between recursive least-squares, Kalman filtering and Bayesian filtering.

Acknowledgments

The authors would like to thank Jérémy Fix and Bruno Scherrer for proofreading earlier versions of this article, as well as the anonymous reviewers for useful comments and suggestions. This research was partly funded by the EU FP7 FET project ILHAIRE (grant n • 270780) and the Région Lorraine (France).