Consider an instance of SARSA with generalization (Figure 13.7) that is a linear function of features of the state and the action. While there are more complicated alternatives, such as using a decision tree or neural network, the linear function often works well, but requires feature engineering.

The feature-based learners require more information about the domain than the reinforcement-learning methods considered so far. Whereas the previous reinforcement learners were provided only with the states and the possible actions, the feature-based learners require extra domain knowledge in terms of features. This approach requires careful selection of the features; the designer should find features adequate to represent the Q-function.

The algorithm SARSA with linear function approximation, SARSA_LFA, uses a linear function of features to approximate the $Q$-function. It is based on incremental gradient descent, a variant of stochastic gradient descent that updates the parameters after every example. Suppose $F_1,\mathrm{\dots },F_n$ are numerical features of the state and the action. $F_i(s,a)$ provides the value for the $i$th feature for state $s$ and action $a$. These features will be used to represent the linear $Q$-function

for some tuple of weights that have to be learned. Assume that there is an extra feature $F_0(s,a)$ whose value is always 1, so that $w_0$ is not a special case.

An experience in SARSA of the form (the agent was in state $s$, did action $a$, received reward $r$, and ended up in state $s^{\prime }$, in which it decided to do action $a^{\prime }$) provides the new estimate $r+\gamma \ast Q_{\overline{w}}(s^{\prime },a^{\prime })$ to update $Q_{\overline{w}}(s,a)$. This experience can be used as a data point for linear regression. Let $\delta =Q_{\overline{w}}(s,a)-(r+\gamma \ast Q_{\overline{w}}(s^{\prime },a^{\prime }))$. Using Equation 7.4, weight $w_i$ is updated by

This update can then be incorporated into SARSA, giving the algorithm shown in Figure 13.8.

Although this program is simple to implement, feature engineering – choosing what features to include – is non-trivial. The linear function must not only convey the best action to carry out, it must also convey the information about what future states are useful.

This algorithm tends to overfit to current experiences, and to forget about old experiences, so that when it returns to a part of the state space it has not visited recently, it will have to relearn all over again. This is known as catastrophic forgetting. One modification is to remember old experiences ( tuples) and to carry out some steps of action replay, by doing some weight updates based on random previous experiences. Updating the weights requires the use of the next action $a^{\prime }$, which should be chosen according to the current policy, not the policy that was under effect when the experience occurred. When memory size becomes an issue, some of the old experiences can be discarded.

State-based MDPs and state-based reinforcement learning algorithms such as Q-learning, SARSA, and the model-based reinforcement learner have no local maxima that are not global maxima. This is because each state can be optimized separately; improving a policy for one state cannot negatively impact another state.

However, when there is generalization, improving on one state can make other states worse. This means that the algorithms can converge to local optima with a value that is not the best possible. They can work better when there is some way to escape local optima. A standard way to escape local maxima is to use randomized algorithms, for example using population-based methods, similar to particle filtering, where multiple initial initializations are run in parallel, and the best policy chosen. There has been some notable – arguably creative – solutions that have been found using evolutionary algorithms, where the individual runs are combined using a genetic algorithm.