I'm training an agent using RL and the SARSA function to update a Q function, but I'm confused 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 because the state hasn't actually changed. In 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 an extra inputs to the State agent_won and game_finished and that's the difference between S and S' for the final Q update?

EDIT: 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.

  • 3
    $\begingroup$ See ai.stackexchange.com/q/3758/1641. That question is about Sarsa rather than $Q$-learning, but exactly the same concept applies. $\endgroup$ – Dennis Soemers Jan 31 '19 at 13:36
  • 2
    $\begingroup$ I would say that there still is in fact an $S'$: that's your terminal state. However, there's no subsequent action $A'$ anymore, so that's why you can't compute $Q(S', A')$ anymore and simply set that term to $0$. Anyway... self.y, is that the discount factor $\gamma$? If so, that shouldn't be added, since that gets multiplied by the "fake" $Q(S', A') = 0$. You'd just want target = reward. $\endgroup$ – Dennis Soemers Jan 31 '19 at 14:15
  • 1
    $\begingroup$ You're a star, Dennis. Thanks so much for your help. $\endgroup$ – BigBadMe Jan 31 '19 at 14:19
  • 1
    $\begingroup$ My comments were assuming a traditional, single-agent Markov Decision Process. If you have two or more agents, and/or other complicating factors, the implementation may have to change a bit. You can edit such details into your question, and I'll probably be able to have a look at that later today (or maybe someone else already does in the meantime) $\endgroup$ – Dennis Soemers Jan 31 '19 at 14:42
  • 1
    $\begingroup$ I realise now I didn't make clear that it was multi-agent, sorry about that. I'll update my question, and if you have any thoughts how I could implement it then I'd certainly welcome the input. $\endgroup$ – BigBadMe Jan 31 '19 at 14:59

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.

| improve this answer | |
  • 1
    $\begingroup$ 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... $\endgroup$ – BigBadMe Jan 31 '19 at 20:35
  • 2
    $\begingroup$ @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). $\endgroup$ – Dennis Soemers Jan 31 '19 at 20:46
  • 2
    $\begingroup$ Perfect, I think I have the pieces put together now. Thanks again for all your input on this, much appreciated. If find this whole field absolutely fascinating, I really enjoy learning about it! $\endgroup$ – BigBadMe Jan 31 '19 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.