## 2 Literature Review
### Fundamental Concepts
#### 2.1.2 Least-Squares Policy Iteration  
Least-Squares Policy Iteration (LSPI) is a model-free, off-line, and off-policy approximation policy iteration RL technique proposed by [PERSON] and [PERSON] (2003) [PERSON] and [PERSON] (2003). LSPI addresses the challenges associated with Q-learning by replacing the direct evaluation of the optimal state-action value function of the Bellman equation by approximating Q-values for each policy using a linear weighted function approximator, That is, a set consisting of \(k\) state-action-dependent basic functions \(\varphi(s,a)\) provides the information of the selected state-action pair features as given in Equation (5). \[\mathcal{F}=\left\{\varphi_{j}(s,a):S\times A\mapsto R,\ j=1,\ldots,k\right\} \tag{5}\]  
The basic functions are fixed and manually designed. The state-action value function is therefore approximated as the weighted linear combination of the \(k\) basic functions as given in Equation (6). \[\hat{Q}^{\pi}(s,a)=\sum_{j=1}^{k}\varphi_{j}(s,a)w_{j}=\varphi(s,a)^{T}w \tag{6}\]  
where \(w_{j}\) is the weight associated with the \(j\)th basic function. From the approximated form of Equation (2), using Equation (6), the matrix form of Equation (2) can be written as in Equation (7). \[\Psi w\approx R+\gamma P^{\pi\pi}\Psi w \tag{7}\]  
where \(\Psi\) is a matrix of basic functions for each state-action pair and is of size \(|S||A|\times k\). Equation (7) can be reformulated as Equation (8) for a linearly dependent column of \(\Psi\). \[\Psi^{T}(\Psi-\gamma P^{\pi T}\Psi)w^{\pi}=\Psi^{T}R \tag{8}\]  
Solving the linear system in Equation (8) leads to the extraction of the weights associated with \(\hat{Q}^{\pi}(s,a)\) in Equation (6). The equation for extracting the weights can be written as in Equation (9). \[w^{\pi}=X^{-1}y \tag{9}\]  
where \(X\) and \(y\) are given in Equations (10) and (11), respectively. \[X=\Psi^{T}(\Psi-\gamma P^{\pi\pi}\Psi) \tag{10}\]  
\[y=\Psi^{T}R \tag{11}\]  
LSPI, as a model-free off-policy learning algorithm, learns \(X\) and \(y\) using sampling from the environment. Subsequently, the learned \(X\) and \(y\) are used to learn the weights to approximate the state-value function \(Q^{\pi}\) of a fixed policy \(\pi\) from the obtained samples using Least-Squares Temporal-Difference Learning (LSTDQ) [PERSON] and [PERSON] (2003). The LSTDQ is an algorithm similar to the least-squares temporal-difference learning algorithm (LSTD) LSTD (LSTD) (LSTD) and learns the approximate state-action-value function of a fixed policy, therefore allowing action selection and policy improvement without a model. Therefore, with a set of samples \(\mathcal{D}=\left\{(s_{i},a_{i},r_{i},\xi_{i})|i=1,2\ldots,M\right\}\) obtained from the environment, the approximated versions of \(\Psi\), \(P^{\hat{\tau}}\Psi\), and \(R\) are constructed using Equations (12)-(14), respectively. \[\Psi=\left( \begin{array}{c}\Psi(s_{1},a_{1})^{T}\\ \vdots\\ \Psi(s_{i},a_{i})^{T}\\ \vdots\\ \Psi(s_{M},a_{M})^{T}\end{array} \right) \tag{12}\]  
\[P^{\hat{\tau}}\Psi=\left( \begin{array}{c}\Psi(\xi_{1},\pi(\xi_{1}))^{T}\\ \vdots\\ \Psi(\xi_{i},\pi(\xi_{i}))^{T}\\ \vdots\\ \Psi(\xi_{M},\pi(\xi_{M}))^{T}\end{array} \right) \tag{13}\]  
\[\hat{R}=\left( \begin{array}{c}r_{1}\\ \vdots\\ r_{i}\\ \vdots\\ r_{M}\end{array} \right) \tag{14}\]  
Therefore, the approximated \(\hat{X}\) and \(\hat{y}\) can be given as in Equations (15) and (16), respectively. \[\hat{X}=\frac{\hat{\Psi}^{T}(\hat{\Psi}-\gamma p^{\hat{\tau}}\Psi)}{M} \tag{15}\]  
\[\hat{y}=\frac{\hat{\Psi}^{T}\hat{R}}{M} \tag{16}\]  
Since in a practical evaluation of \(\hat{X}\) and \(\hat{y}\), \(M\) is finite, the solution to the system will not be affected if the factor \(1/M\) is dropped. If \(\hat{X}\) and \(\hat{y}\) combined can be obtained in a single sample, then constructing an iteration update rule for \(\hat{X}\) and \(\hat{y}\) is feasible.