How to fight with unstability in self play?

Question

I'm working on a neural network that plays some board games like reversi or tic-tac-toe (zero-sum games, two players). I'm trying to have one network topology for all the games - I specifically don't want to set any limit for the number of available actions, thus I'm using only a state value network.

I use a convolutional network - some residual blocks inspired by the Alpha Zero, then global pooling and a linear layer. The network outputs one value between 0 and 1 for a given game state - it's value.

The agent, for each possible action, chooses the one that results in a state with the highest value, it uses the epsilon greedy policy.

After each game I record the states and the results and create a replay memory. Then, in order to train the network, I sample from the replay memory and update the network (if the player that made a move that resulted in the current state won the game, the state's target value is 1, otherwise it's 0).

The problem is that after some training, the model plays quite well as one of the players, but loses as the other one (it plays worse than the random agent). At first, I thought it was a bug in the training code, but after further investigation it seems very unlikely. It successfully trains to play vs a random agent as both players, the problem arises when I'm using only self play.

I think I've found some solution to that - initially I train the model against a random player (half of the games as the first player, half as the second one), then when the model has some idea what moves are better or worse, it starts training against itself. I achieved pretty good results with that approach - in tic-tac-toe, after 10k games, I have 98.5% win rate against the random player as the starting player (around 1% draws), 95% as the second one (again around 3% draws) - it finds a nearly optimal strategy. It seems to work also in reversi and breakthrough (80%+ wins against random player after the 10k games as both players). It's not perfect, but it's also not that bad, especially with only 10k games played.

I believe that, when training with self play from the beginning, one of the players gains a significant advantage and repeats the strategy in every game, while the other one struggles with finding a counter. In the end, the states corresponding to the losing player are usually set to 0, thus the model learns that whenever there is the losing player's turn it should return a 0. I'm not sure how to deal with that issue, are there any specific approaches? I also tried to set the epsilon (in eps-greedy) initially to some large value like 0.5 (50% chance for a random move) and gradually decrease it during the training, but it doesn't really help.

Answer 1

The AlphaZero paper mentions an "evaluation" step that seems to deal with the the problem similar to yours:

... we evaluate each new neural network checkpoint against the current best network $f_{\theta_*}$ before using it for data generation ... Each evaluation consists of 400 games ... If the new player wins by a margin of > 55% (to avoid selecting on noise alone) then it becomes the best player $\alpha_{\theta_*}$ , and is subsequently used for self-play generation, and also becomes the baseline for subsequent comparisons

In the AlphaStar they've use a whole league of agents that was constantly played against each other.

Answer 2

When in an environment with competing agents, from the perspective of each agent, the environment becomes non-markovian. That occurs because each agent is constantly adapting its own strategy to other's actions, so a transition that occurred to a pair (s,a) before, resulting in a positive reward, might result in zero or negative reward in future iterations of the game.

I didn't see mentioned, but I imagine that you are using some DQN variation to train the network, since you use a replay buffer. To use this framework, you assume that the environment, from the perspective of the agent, follows a MDP. But, as I argued above, some tuples from the replay buffer might not represent valid data for training, so the corresponding network that is trained with it becomes unstable.

A solution might be use the idea of centralized training with decentralized execution, in conjunction with some policy gradient (PG) algorithm, like REINFORCE or Actor-Critic. Since PG are on-policy algorithms, the data used to train the network is generated by the current policy, so you don't have the replay buffer issue. On the other hand, since is on-policy, it's sample inefficient. The centralized training might help to increase the sample efficiency (it's in fact a good solution to partial observable environments, but from what I understand is not the case with the your game). An additional solution to the sample inefficiency is to use off-policy PG, using, for example, past policies, with respective experience, in a importance sampling framework.

Some related references:

Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments: https://arxiv.org/abs/1706.02275

Off-Policy Policy Gradient: https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html#off-policy-policy-gradient