## 3 Reinforcement Learning Method
### SGD SARSA with Linear Function Approximation  
The SARSA algorithm has been chosen for this application due to its simplicity and stability [37]. The SARSA algorithm is an on-policy TD-learning method, with Q-learning being its off-policy counterpart. The terminology \"on-policy\" or \"off-policy\" refers to whether the updates occur with respect to the current policy. Q-learning is one of the most popular learning algorithms found in literature. However, it is difficult to integrate off-policy learning methods with linear function approximations as they are susceptible to diverge [37]. Hence, SARSA has been chosen for this work due to the seamless integration of the function approximation and learning methods. The basics of the SARSA algorithm are to estimate the expected value of selecting an action \(A\) from the current state \(S\) following the policy \(\pi\). This estimate is called the Q-value and is denoted \(Q(S,A)\). In the tabular approach, a table (called the \"Q-table\") is constructed, composed of a Q-value for each state-action pair in the defined state-action space. The basic goal of the RL agent is to know the exact Q-value for each element in the Q-table to devise the best policy \(\pi\). Therefore, learning is facilitated through updating. In general, updates occur in steps in the direction of the update target. The size of these steps is determined by the step-size parameter or \"learning rate\" \(\alpha\). The update target under the SARSA methodology is the difference between the new estimate of the state-action pair following policy \(\pi\) and the old estimate of the state-action pair. The new estimate considers the achieved reward \(R\) and the value of the future state-action pair following the current policy \(Q(S^{\prime},A^{\prime})\). The consideration of the future Q-value is termed \"bootstrapping\", and the amount that this value impacts the update target is controlled through the discount factor \(\gamma\). The basic SARSA update equation is shown in (15) below  
\[Q(S,A)\gets Q(S,A)+\alpha\big{[}R+\gamma\cdot Q(S^{\prime},A^{\prime})-Q( S,A)\big{]} \tag{15}\]  
The tabular approach works well for small state and action spaces. However, as the problem becomes more complex, the memory required for the Q-table increases significantly. An alternative to the tabular approach is to use function approximation to represent the Q-table such that the Q-values for each state-action pair can be approximated by some function. The function approximation approach also solves another common issue in RL: balancing exploiting known \"good\" actions and exploring other \"better\" ones. In tabular methods, for the agent to be certain it is selecting the most valuable action, all actions should  
Figure 5: A block diagram representing the agent–environment interaction defined by the RL framework, derived from Sutton and Barto [37]. be explored for each state. With function approximation, the values of one state-action pair can be generalized to its neighbors, reducing the burden for an extensive exploration stage and decreasing training time. There are a number of function approximation methods, such as linear approaches and neural networks (a non-linear approach), both of which have their respective advantages and disadvantages [37]. Linear methods are selected in this work to reduce the memory necessary to approximate the Q-values accurately. In linear function approximation methods, the Q-values are represented as the product of a weight vector \(\mathbf{W}\) and a feature vector \(\mathbf{X}(S,A)\), as shown in (16). \[Q(S,A)=\mathbf{W}^{\top}\mathbf{X}(S,A) \tag{16}\]  
The different classes of linear approximation methods stem from how the feature vector is defined. The fundamental types of features are polynomial functions, Fourier basis functions, coarse coding, tile coding, and radial basis functions. Of these, tile coding (a form of coarse coding) is the most computationally efficient [37].