How to deal with the terminal state in SARSA in a multi-agent setting?

Question

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.

Answer 1

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?" question on this site.