Answers.Body: <p>The SARSA update rule looks like:</p>
  <p><span class="math-container">$$Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma Q(S', A') \right].$$</span></p>
  <p>Very similar, the <span class="math-container">$Q$</span>-learning update rule looks like:</p>
  <p><span class="math-container">$$Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma \max_{A'} Q(S', A') \right].$$</span></p>
  <p>Both of these update rules are formulated for single-agent Markov Decision Processes. Sometimes you can make them work reasonably ok in <em>multi-agent</em> settings, but it is crucial to remember that these update rules should still always be implemented &quot;from the perspective&quot; of a single learning agent, who is oblivious to the presence of other agents and pretends them to be a part of the environment.</p>
  <p>What this means is that the states <span class="math-container">$S$</span> and <span class="math-container">$S'$</span> that you provide in update rules <strong>really must both be states in which the learning agent is allowed to make the next move</strong> (with the exception being that <span class="math-container">$S'$</span> is permitted to be a terminal game state.</p>
  <p>So, suppose that you have three subsequent states <span class="math-container">$S_1$</span>, <span class="math-container">$S_2$</span>, and <span class="math-container">$S_3$</span>, where the learning agent gets to select actions in states <span class="math-container">$S_1$</span> and <span class="math-container">$S_3$</span>, and the opponent gets to select an action in state <span class="math-container">$S_2$</span>. <strong>In the update rule, you should completely ignore</strong> <span class="math-container">$S_2$</span>. This means that you should take <span class="math-container">$S = S_1$</span>, and <span class="math-container">$S' = S_3$</span>.</p>
  <p>Following the reasoning I described above literally may indeed lead to a tricky situation with rewards from transitioning into terminal states, since technically every episode there will be only one agent that directly causes the transition into a terminal state. This issue (plus also some of my explanation above being repeated) is discussed in the <a href="https://ai.stackexchange.com/q/6573/1641">&quot;How to see terminal reward in self-play reinforcement learning?&quot;</a> question on this site.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-31T20:35:19.667Z
Answers.Text: Thanks Dennis. I understand what you're saying, but my question is how does the agent receive the final reward, which could be ultimately determined by another player making a mistake with their action? In a literal sense, how do I perform the update in that scenario?  I keep a list of all of the experience tuples (`S`,`a`,`r`,`S'`), and I only update them once the game is finished, so I could conceivably just add the ultimate reward to the existing reward value for the final `S a S'` transition. Would that work? I must somehow give the final reward to the agent, I'm just not sure how...
Answers.UserDisplayName: BigBadMe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-31T20:46:32.243Z
Answers.Text: @BigBadMe Yes, with the standard Sarsa/$Q$-learning updates you simply give "credit" for the final reward (i.e. the win/loss) to the last transition **caused by your learning agent**. For these algorithms to be applicable, you have to pretend that there is no other agent, they're just a part of "the environment" and any actions they select are just a part of "the environment's transition dynamics". That may not be ideal, but that's how it works when you try to apply a single-agent algorithm to a multi-agent setting. It may still work out in practice (especially with a proper self-play setup).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-31T17:49:33.080Z
Answers.LastActivityDate: 2020-11-01T14:34:21.977Z
Answers.LastEditDate: 2020-11-01T14:34:21.977Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I'm training a SARSA agent to update a Q function, but I'm confused about how you handle the final state. In this case, when the game ends and there is no <span class="math-container">$S'$</span>.</p>
  <p>For example, the agent performed an action based on the state <span class="math-container">$S$</span>, and, because of that, the agent won or lost and there is no <span class="math-container">$S'$</span> to transition to.</p>
  <p><em>So, how do you update the Q function with the very last reward in that scenario, given that the state hasn't actually changed?</em> That case <span class="math-container">$S'$</span> would equal <span class="math-container">$S$</span> even though an action was performed and the agent received a reward (they ultimately won or lost, so quite important update to make!).</p>
  <p>Do I add extra inputs to the state &quot;agent won&quot; and &quot;game finished&quot;, and that's the difference between <span class="math-container">$S$</span> and <span class="math-container">$S'$</span> for the final Q update?</p>
  <p>To make clear, this is in reference to a multi-agent/player system.  So, the final action the agent takes could have a cost/reward associated with it, but the subsequent actions other agents then take could further determine a greater gain or loss for this agent and whether it wins or loses. So, the final state and chosen action, in effect, could generate different rewards without the agent taking further actions.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-01T15:00:53.513Z
Comments.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115729/discussion-on-question-by-bigbadme-how-to-deal-with-the-terminal-state-in-sarsa).
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><implementation><multi-agent-systems><sarsa>
Title: How to deal with the terminal state in SARSA in a multi-agent setting?
UserDisplayName: BigBadMe
ThreadText: # How to deal with the terminal state in SARSA in a multi-agent setting?
  
  (Asked by: username_0 on 2019-01-31)
  
  I'm training a SARSA agent to update a Q function, but I'm confused about how you handle the final state. In this case, when the game ends and there is no $S'$.
  
  For example, the agent performed an action based on the state $S$, and, because of that, the agent won or lost and there is no $S'$ to transition to.
  
  *So, how do you update the Q function with the very last reward in that scenario, given that the state hasn't actually changed?* That case $S'$ would equal $S$ even though an action was performed and the agent received a reward (they ultimately won or lost, so quite important update to make!).
  
  Do I add extra inputs to the state "agent won" and "game finished", and that's the difference between $S$ and $S'$ for the final Q update?
  
  To make clear, this is in reference to a multi-agent/player system. So, the final action the agent takes could have a cost/reward associated with it, but the subsequent actions other agents then take could further determine a greater gain or loss for this agent and whether it wins or loses. So, the final state and chosen action, in effect, could generate different rewards without the agent taking further actions.
  
  **Tags:** reinforcement-learning, implementation, multi-agent-systems, sarsa
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/115729/discussion-on-question-by-bigbadme-how-to-deal-with-the-terminal-state-in-sarsa).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-01-31. Score: 2 | Accepted answer
  
  The SARSA update rule looks like:
  
  $$Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma Q(S', A') \right].$$
  
  Very similar, the $Q$-learning update rule looks like:
  
  $$Q(S, A) \gets Q(S, A) + \alpha \left[ R + \gamma \max\_{A'} Q(S', A') \right].$$
  
  Both of these update rules are formulated for single-agent Markov Decision Processes. Sometimes you can make them work reasonably ok in *multi-agent* settings, but it is crucial to remember that these update rules should still always be implemented "from the perspective" of a single learning agent, who is oblivious to the presence of other agents and pretends them to be a part of the environment.
  
  What this means is that the states $S$ and $S'$ that you provide in update rules **really must both be states in which the learning agent is allowed to make the next move** (with the exception being that $S'$ is permitted to be a terminal game state.
  
  So, suppose that you have three subsequent states $S\_1$, $S\_2$, and $S\_3$, where the learning agent gets to select actions in states $S\_1$ and $S\_3$, and the opponent gets to select an action in state $S\_2$. **In the update rule, you should completely ignore** $S\_2$. This means that you should take $S = S\_1$, and $S' = S\_3$.
  
  Following the reasoning I described above literally may indeed lead to a tricky situation with rewards from transitioning into terminal states, since technically every episode there will be only one agent that directly causes the transition into a terminal state. This issue (plus also some of my explanation above being repeated) is discussed in the ["How to see terminal reward in self-play reinforcement learning?"](https://ai.stackexchange.com/q/6573/1641) question on this site.
  
  > **Comments:**
  > **username_0**: Thanks Dennis. I understand what you're saying, but my question is how does the agent receive the final reward, which could be ultimately determined by another player making a mistake with their action? In a literal sense, how do I perform the update in that scenario?  I keep a list of all of the experience tuples (`S`,`a`,`r`,`S'`), and I only update them once the game is finished, so I could conceivably just add the ultimate reward to the existing reward value for the final `S a S'` transition. Would that work? I must somehow give the final reward to the agent, I'm just not sure how...  
  > **username_2**: @BigBadMe Yes, with the standard Sarsa/$Q$-learning updates you simply give "credit" for the final reward (i.e. the win/loss) to the last transition **caused by your learning agent**. For these algorithms to be applicable, you have to pretend that there is no other agent, they're just a part of "the environment" and any actions they select are just a part of "the environment's transition dynamics". That may not be ideal, but that's how it works when you try to apply a single-agent algorithm to a multi-agent setting. It may still work out in practice (especially with a proper self-play setup).  
  
  ---
  
  