# Combining Subgoal Graphs with Reinforcement Learning to Build a Rational Pathfinder
## 3 Materials and Methods
### The LSPI-Based Feasible Trajectory Planner  
#### 3.4.1 LSPI Method  
LSPI can deal with continuous state spaces and be more data-efficient and time-efficient than other conventional temporal-different RL methods. Figure 4 shows the overview of the entire LSPI framework [18]. It is a completely off-policy and offline algorithm, and can use sample sets collected arbitrarily from the simulation environment or the real world. At the policy evaluation step, it uses the linear structure to obtain the approximate state-action value function, which is easy to implement and use. At the policy improvement stage, it obtains greedy policies by maximizing state-action values, based on approximate value functions. Furthermore, the transparent inner mechanism is beneficial for users to see how it works and why failures occur. Theoretically, samples from any policy can be collected arbitrarily. Even during policy iteration, samples from the current policy can also be collected and added to train policies. LSPI provides great flexibility for collecting samples, which brings much convenience in practical uses. However, similar to using samples to approximate linear or nonlinear functions, the sample distribution in the state space affects the speed and result of approximating. Therefore, when sample sets are of poor quality, LSPI causes a worse effect via fitting biased distribution based on the data-efficient feature. To solve these problems, in this paper, we not only used random policies to collect samples, but we also tried using random environments to collect samples. Details on how samples are collected are given in Section 4.1. The prominent advantage of LSPI is its ability to deal with continuous or large state spaces, while tabular RL methods (e.g., Q-learning and Sarsa) cannot solve them, since it is impractical and computationally expensive to use the table structure to store state-action values, (i.e., Computer Go: \(10^{170}\) states and Helicopter Control: continuous state spaces). The key of LSPI is that, during the policy evaluation stage, it uses linear architectures to approximate value functions (i.e., uses \(\hat{Q}^{\pi}(s,a;\omega)\) to approximate \(Q^{\pi}(s,a)\) via linear basis functions with free parameters \(\omega\)). \(Q^{\pi}(s,a)\) is the state-action function under policy \(\pi\). The design of basis functions is fundamental work in LSPI. It is popular to use radial basis functions or polynomial basis functions, and we chose polynomial basis functions, since, compared with radial basis functions, polynomial basis functions have clear structures for designers. The definition of \(\hat{Q}^{\pi}(s,a;\omega)\) is  
\[\hat{Q}^{\pi}(s,a;\omega)=\ \sum_{j=1}^{k}\varphi_{j}(s,a)\omega_{j}, \tag{2}\]  
where \(\omega_{j}\) is the weight parameter, \(\varphi_{j}(s,a)\) is the fixed basis function that is linearly independent, \(s\) is the state, \(a\) is the action, and \(k\) is the number of basis functions. Two kinds of value-function approximation projections (i.e., Bellman residual minimizing approximation and least-squares fixed-point approximation) are used to approximate value functions. Because learning the Bellman approximation requires \"doubled\" samples [18] which are impossibly collected from the model-free system, we chose the second approximation that is more practical for the learning task and evaluates the state-action value more accurately. In the policy-evaluation step, LSTDQ was used to find the solution of least-squares fixed-point approximation which is equivalent to learning \(\omega\). Since the model was unknown, samples were used to learn \(\omega\) in an incremental way [18].