# What should be saved in SARSA prioritized sweeping?

In the book "Reinforcement Learning: An Introduction", by Sutton and Barto, they provided the "Q-learning prioritized sweeping" algorithm, in which the model saves the next state and the immediate reward, for each state and action, that is, $$Model(S_{t},A_{t}) \leftarrow S_{t+1}, R_{t+1}$$.

If we want to use "SARSA prioritized sweeping", should we save "next state, immediate reward, and next action", that is, $$Model(S_{t},A_{t}) \leftarrow S_{t+1}, R_{t+1}, A_{t+1}$$?

SARSA is an on-policy method. Your historical choices of action will have been made using older Q values, and thus from a different policy. In addition, the action that was taken at the time may not have been typical for the agent (it may have been exploring). So you don't usually want to re-use historical action choices to calculate TD targets in single-step SARSA, because these may introduce bias.

Provided you are performing single-step SARSA, then you can re-generate the action choice sampling from the current best policy. This is similar to generating the max Q value in the TD target value $$R_{t+1} + \text{max}_{a'} Q(S_{t+1},a')$$.

You could do this using a regular SARSA sampling the action choice:

$$R_{t+1} + Q(S_{t+1}, a' \sim \pi(\cdot|S_{t+1}) )$$

Or you could use Expected SARSA and take a weighted mean of all possible actions:

$$R_{t+1} + \sum_{a' \in \mathcal{A}(S_{t+1})} \pi(a'|S_{t+1})Q(S_{t+1}, a')$$

Technically these would both be on-policy with respect to evaluating the TD Target, but off-policy with respect to the distribution of $$S_t, A_t$$ that you are running the update for. That's already the case due to prioritised sweeping focussing more updates on certain transitions, but could be a big difference when using a neural network to approximate Q. Bear in mind that making TD learning methods off-policy can have a negative impact on stability.

If you want to process multi-step updates, then you do have to reference $$A_{t+1}$$ and adjust for when the historical data makes a different action choice than your current estimate of the best policy. This would commonly use importance sampling. This is true for Q-learning as well however, so there would still be no difference in what you store between Q-learning and SARSA.

• Dear @Neil Thank you so much. To make sure that I understood your points, you mean that in a tabular single step SARSA, the model stores $Model(S_{t},A_{t}) \leftarrow S_{t+1}, R_{t+1}$, as the same as "Q-Learning", and then for each step in repeat, we re-generate a new action for $A_{t+1}$, and we do not use importance sampling at all. $s,a \leftarrow first(PQueue)$ $r,s^{\prime} \leftarrow Model(s,a)$ $Take action a^{\prime} , e.g. \epsilon -greedy from Q(s^{\prime},.)$ $Q(s,a) \leftarrow Q(s,a) + \alpha . (r+\gamma Q(s^{\prime},a^{\prime}) - Q(s,a))$ – Katatonia Feb 9 '19 at 11:55
• @KatatoniaSh: Yes, that's it. – Neil Slater Feb 9 '19 at 13:28
• @Dwait: Ideally you would re-sample $A_{t+1}$ as part of any re-calculation of the priority, although that could be inefficient. Possibly though you could still get away with it, since the priorities may still loosely apply due to a particular state being interesting in the given problem. – Neil Slater May 9 '19 at 9:26
• @NeilSlater Thanks! And sorry I meant to edit my comment but deleted it instead. Posting it again so your response isn't out of context for other readers: The order of making these updates is still governed by their priorities in the PQueue which are decided by Rt+1+γQ(St+1,At+1)−Q(St,At), where At+1 is the historical action chosen while moving along the trajectory, right? Here the target is different from the one that will be used for making the actual update. So the central idea of Prioritized Sweeping - making the bigger updates first - is somewhat spoiled with SARSA isn't it? – Dwait Bhatt May 9 '19 at 9:33