Why does self-playing tic-tac-toe not become perfect?

Question

I trained a DQN that learns tic-tac-toe by playing against itself with a reward of -1/0/+1 for a loss/draw/win. Every 500 episodes, I test the progress by letting it play some episodes (also 500) against a random player.

As shown in the picture below, the net learns quickly to get an average reward of 0.8-0.9 against the random player. But, after 6000 episodes, the performance seems to deteriorate. If I play manually against the net, after 10000 episodes, it plays okay, but by no means perfect.

Assuming that there is no hidden programming bug, is there anything that might explain such a behavior? Is there anything special about self-play in contrast to training a net against a fixed environment?

Here further details.

The net has two layers with 100 and 50 nodes (and a linear output layer with 9 nodes), uses DQN and a replay buffer with 4000 state transitions. The shown epsilon values are only used during self-play, during evaluation against the random player exploration is switched off. Self-play actually works by training two separate nets of identical architecture. For simplicity, one net is always player1 and the other always player2 (so they learn slightly different things). Evaluation is then done using the player1 net vs. a random player which generates moves for player2.

Answer 1

There are lots of ways that RL agents can fail to learn properly, so you are faced with a little bit of experimentation and maybe bug hunting unfortunately. However, from the description you have given in the question and comments, I can make a few observations and guesses about where to look:

• Your metric of average reward against a random player is sensible. In this case, you could also use a perfect player (that ideally randomised choice of any optimal move), where you would see a maximum averaged return of zero - this would be helpful to know if your agent had learned a fully optimal behaviour, because it would consistently score zero. In general for more complex games a perfect player is not available to test with, but as you are learning here it might help you.

• Your DQNs might be unable to fit the value function. You can test that in this case by getting the value function from an optimal self-play player (all the values will be -1, 0, or 1) and using a supervised learning approach, separately from your agent. You should be able to get a loss very close to zero - if you cannot do that, then something could be wrong with your network architecture.

• Whilst you are training, even though you are using a variation of Q-learning (which learns an optimal policy even whilst exploring other actions), your DQNs are not learning optimal play. That is because you have used two agents. In DQN, the algorithm is not aware that there are other learning agents, and it will treat any other agents as if they were part of the environment. Which means that the agents will spend some effort trying to set the game up for each other to make an exploration mistake. That could lead to non-optimal choices and a little bit of instability. Your decay of epsilon should help with that, although you are caught between a rock and a hard place here. You want to learn off-policy and explore, but are forced to reduce exploration. There are a couple of ways to resolve that, I will explain a bit further down . . .

• 10,000 games may not be enough. In the experiments I have done with TicTacToe agents, it seems between 20,000 and 50,000 games are required for a naive learner. More may be required if you have done something that makes learning inefficient. In addition, I found when adding more sophisticated learning approaches (in my case using eligibility traces) the agents appear to become close to optimal very quickly, but actually have flaws which take a long time to shake out, just as long as running a more naive algorithm. When the flaws got found and fixed, it upset the value function for a while and I saw fluctuations in my metrics similar to yours.

• Q-learning with NNs is inherently unstable. DQN implements some ideas to fix that, but it is not perfect. It is not uncommon to need to adjust the batch size and/or time steps between taking frozen copy of network for the TD target calculation. The initial stability followed by poor performance looks a lot like that instability too.

Regarding your use of two opposing agents, I can see two possible improvements:

1. Alternately train one or other agent in each game, don't train both at once. That will mean each agent is learning to play against the other agent playing its best without exploratory moves.

2. Combine networks into single agent description. As this is a zero-sum game, you can take player A's network for calculating values, and just have player B try to minimise the action value on its turn. That means use min and argmin functions for steps that represent player B's turn wherever player A would use min or argmin, including in the Q-value updates - this is typically easy to add to the inner loop of Q-learning, and should improve learning efficiency (essentially you are hard-coding knowledge that this is a zero-sum game and taking advantage of that symmetry).

Both of these ideas will free you up from caring about the value of epsilon, or decaying it - you can probably just leave it fixed at e.g. 0.1

Finally, as a test of whether your agent can cope with learning optimal play in general, you could have it learn against an already optimal agent. That is obviously not something you can do for more complex games, but might help you debug agent code and hyper-parameters of the network - it divides your problem up into "can it learn this at all" and "can it learn through self-play".

Answer 2

As epsilon is throttled down networks 1 and 2 can freely specialize to producing tic-tac-toe's well-known non-losing behaviour against quasi-perfect adversaries without encoding any non-losing or winning behaviour against random (in other words, bad) adversaries. I suggest while training network 1 (1st mover) and reducing epsilon-1 you keep the 2nd mover's epsilon-2 to values distinctly above 0, indeed why not fixed. Vice-versa for training the 2nd mover.