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

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.

• Comments are not for extended discussion; this conversation has been moved to chat.
– nbro
Nov 1 '20 at 15:00

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.

• 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... Jan 31 '19 at 20:35
• @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). Jan 31 '19 at 20:46