Answers.Body: <p>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.</p>
  
  <p>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 <span class="math-container">$R_{t+1} + \text{max}_{a'} Q(S_{t+1},a')$</span>. </p>
  
  <p>You could do this using a regular SARSA sampling the action choice:</p>
  
  <p><span class="math-container">$$R_{t+1} + Q(S_{t+1}, a' \sim \pi(\cdot|S_{t+1}) )$$</span></p>
  
  <p>Or you could use Expected SARSA and take a weighted mean of all possible actions:</p>
  
  <p><span class="math-container">$$R_{t+1} + \sum_{a' \in \mathcal{A}(S_{t+1})} \pi(a'|S_{t+1})Q(S_{t+1}, a')$$</span></p>
  
  <p>Technically these would both be on-policy with respect to evaluating the TD Target, but off-policy with respect to the distribution of <span class="math-container">$S_t, A_t$</span> 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.</p>
  
  <p>If you want to process multi-step updates, then you do have to reference <span class="math-container">$A_{t+1}$</span> and adjust for when the historical data makes a different action choice than your current estimate of the best policy. This would commonly use <em>importance sampling</em>. 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-09T11:55:23.317Z
Answers.Text: 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))$
Answers.UserDisplayName: Amin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-09T13:28:48.380Z
Answers.Text: @KatatoniaSh: Yes, that's it.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-09T09:26:15.533Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-09T09:33:33.003Z
Answers.Text: @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?
Answers.UserDisplayName: Dwait Bhatt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-07T17:10:13.300Z
Answers.LastActivityDate: 2019-02-07T17:16:01.583Z
Answers.LastEditDate: 2019-02-07T17:16:01.583Z
Answers.UserDisplayName: Neil Slater
Body: <p>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, <span class="math-container">$Model(S_{t},A_{t}) \leftarrow S_{t+1}, R_{t+1}$</span>. </p>
  
  <p>If we want to use "SARSA prioritized sweeping", should we save "next state, immediate reward, and next action", that is, <span class="math-container">$Model(S_{t},A_{t}) \leftarrow  S_{t+1}, R_{t+1}, A_{t+1}$</span>?</p>
  
Tags: <reinforcement-learning>
Title: What should be saved in SARSA prioritized sweeping?
UserDisplayName: Amin
ThreadText: # What should be saved in SARSA prioritized sweeping?
  
  (Asked by: username_0 on 2019-02-07)
  
  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}$?
  
  **Tags:** reinforcement-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-07. Score: 3
  
  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.
  
  > **Comments:**
  > **username_0**: Dear @username_1 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))$  
  > **username_1**: @KatatoniaSh: Yes, that's it.  
  > **username_1**: @username_2: 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.  
  > **username_2**: @username_1 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?  
  
  ---
  
  