Least squares policy evaluation algorithms with linear function approximation (Q1870310)

This paper deals with policy evaluation algorithms within the framework of infinite-horizon dynamic programming problems with discounted cost. The authors consider the discrete-time stationary Markov chain with state space \(\{1,2,\dots, n\}\) and the cost vector \(J\), given by \[ J(i)= E\Biggl[\sum^\infty_{t=0} \alpha^t g(i_t, i_{t+ 1})/i_0= i\Biggr], \] \(i= 1,2,\dots,n\), where \(i_t\) denotes the state of the system at time \(t\). The authors discuss two methods to calculate \(J\) approximately, using simulation, temporal difference and linear cost function approximation. The first method is a new algorithm, including the use of least square subproblems that are solved recursively and with a diminishing stepsize. The second method is the \(\text{LSTD}(\lambda)\) algorithm, proposed by Boyan (to appear in Machine Learning). They state convergence results for these two algorithms.