Q learning (DQN) strategy for a multiplayer zero-sum game

Question

I have been looking for ways to train a Q-learning agent for a multiplayer zero-sum game (a variation of Tic-Tac-Toe in my case). I came up with a learning strategy I haven't found anywhere else, and I want to know if it would work. Here it is:

The agent learns through self-play. It receives a +1 reward for winning (no matter what player won, you'll see later why) and 0 for every other state. The agent learns through a modified Bellman equation, where the expected future reward is SUBTRACTED and not added.

Q(s_t, a) = r - γ * max Q(s_t+1, a)

If you expand this equation, you should get this:

Q(s_t, a) = r_t - γ * r_t+1 + γ² * r_t+2 - γ³ * r_t+3 + ...

Notice how the plus and minus signs alternate. Thus, your expected reward is a sum of the rewards from your turns minus the sum of your opponent's rewards. That is also why the reward for winning is always +1.

This strategy is similar to the minimax tree search, where we want the best rewards for us and the worst for our opponent.

I hope I got my point across. Please note that I'm not very good at maths and AI theory, so forgive me if I mixed some things up or have a wrong notation. Also, if this is not a good approach, which would you recommend?

Answer 1

This works, and is used as a standard approach for two player zero-sum games in reinforcement learning. As you stated, it is a combination of reinforcement learning with Minimax optimisation.

A very similar approach is to have reward +1 for player A winning, and reward -1 for player B winning, with A's objective to maximise reward and B's objective to minimise reward, allowing them to share the same value function directly (with your formulation, the safest thing to do is maintain two value functions, although in some cases it may work with one). This approach leaves the definition of $Q(s,a)$ unchanged from standard RL, but changes the Bellman equation (and matching standard update rule) of $Q(s,a) = r + \gamma \text{min}_{a'}Q(s',a')$.

You may see another variation, where the action variable $a$ is dropped, and the agent selects the next state from all possibilities that the game engine allows. This is called the afterstate representation, and it works effectively for simple board games because it reduces the space needed for the value function compared to an action value approach.