Maximum Q value for new state in Q-Learning never exists

Question

I'm working on implementing a Q-Learning algorithm for a 2 player board game.

I encountered what I think may be a problem. When it comes time to update the Q value with the Bellman equation (above), the last part states that for the maximum expected reward, one must find the highest q value in the new state reached, s', after making action a.

However, it seems like the I never have q values for state s'. I suspect s' can only be reached from P2 making a move. It may be impossible for this state to be reached as a result of an action from P1. Therefore, the board state s' is never evaluated by P2, thus its Q values are never being computed.

I will try to paint a picture of what I mean. Assume P1 is a random player, and P2 is the learning agent.

1. P1 makes a random move, resulting in state s.
2. P2 evaluates board s, finds the best action and takes it, resulting in state s'. In the process of updating the Q value for the pair (s,a), it finds maxQ'(s', a) = 0, since the state hasn't been encountered yet.
3. From s', P1 again makes a random move.

As you can see, state s' is never encountered by P2, since it is a board state that appears only as a result of P2 making a move. Thus the last part of the equation will always result in 0 - current Q value.

Am I seeing this correctly? Does this affect the learning process? Any input would be appreciated.

Thanks.

Answer 1

Your problem is with how you have defined $s'$.

The next state for an agent is not the state that the agent's action immediately puts the environment into. It is the state when it next takes an action. For some, more passive, environments, these are the same things. But for many environments they are not. For instance, a robot that is navigating a maze may take an action to move forward. The next state does not happen immediately at the point that it starts to take the action (when it would still be in the same position), but at a later time, after the action has been processed by the environment for a while (and the robot is in a new position), and the robot is ready to take another action.

So in your 2-player game example using regular Q learning, the next state $s'$ for P2 is not the state immediately after P2's move, but the state after P1 has also played its move in reaction. From P2's perspective, P1 is part of the environment and the situation is no different to having a stochastic environment.

Once you take this perspective on what $s'$ is, then Q learning will work as normal.

However, you should note that optimal behaviour against a specific opponent - such as a random opponent - is not the same as optimal play in a game. There are other ways to apply Reinforcement Learning ideas to 2-player games. Some of them can use the same approach as above - e.g. train two agents, one for P1 and one for P2, with each treating the other as if it were part of the environment. Others use different ways of reversing the view of the agent so that it can play versus itself more directly - in those cases you can treat each player's immediate output as $s'$, but you need to modify the learning agent. A simple modification to Q learning is to alternate between taking $\text{max}_{a'}$ and $\text{min}_{a'}$ depending on whose turn you are evaluating (and assuming P1's goal is to maximise their score while P2's goal is to minimise P1's score - and by extension maximise their own score in any zero-sum game)