SARSA

Topics: Reinforcement Learning

Algorithm Overview

SARSA is a tabular, on-policy reinforcement learning algorithm that learns a discrete policy. It is targeted at environments with discrete state and discrete action spaces.

SARSA is based on the single-step temporal difference method. Its goal is to learn a table of Q-values. Therefore, it deals with transitions from state-action pair to state-action pair. After convergence, the optimal policy would be to select the action with the highest Q-value.

The update equation for SARA is (1):

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \, \Bigr[ r_{t+1} + \gamma \, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \Bigr]$$

where:

• $\alpha$ is the learning rate
• $r_{t+1} + \gamma \, Q(s_{t+1}, a_{t+1})$ is the target

This update is done after every transition from a non-terminal state.

Pseudocode

References

1. R. S. Sutton and A. G. Barto, Reinforcement learning: an introduction. in Adaptive computation and machine learning. Cambridge, Mass: MIT Press, 2018.