The specific approaches you mentioned (A3C, DDPG), and usually also other Actor-Critic methods in general, are approaches for the standard single-agent Reinforcement Learning (RL) setting. When trying to apply such algorithms to settings that are actually multi-agent settings, it is indeed common to encounter the problems you describe. They can all be viewed as your agent "overfitting" to the opponent they're training against:
- Play against random player. I had rather good results, but not as good as expected since most interesting states cannot be reached with a random opponent.
In this case, your agent will "overfit" against random opponents. It will likely become capable of beating them relatively easily, and to some extent this may also still translate to relatively weak non-random agents (like simple heuristic approaches), but it is unlikely to generalise to strong opponents.
- Play against list of specific AIs. Results were excellent against those AIs, but very bad with never seen opponents
Here you pretty much exactly give a description of what I mean when I say "overfitting" against the opponent you're training against.
- Play against itself. Seemed the best to me, but I could not get any convergence due to non-stationary environment.
When training using self-play like this, there is still a danger of overfitting against "itself". This may turn out to work well in some games, but in other games, there are indeed risk of instability / lack of convergence. This can, for example, be due to the agent "rotating" through a circle of strategies that beat each other. Intuitively, you could think of Rock-Paper-Scissors. A randomly-initialised agent may, for example, have a slight tendency to play Rock more often than the others. Self-play will then lead to a strategy that primarily plays Paper, to beat the current "Rock" strategy. Continued self-play training can then figure out that a tendency to play more Scissors will be strong against itself. Etc., these strategies can keep rotating forever.
The standard approach for self-play training in games is the one popularised by AlphaGo Zero and AlphaZero, and also around the same time independently published with results on the game of Hex. That last paper coined the term "Expert Iteration" for the approach, which I like to use. The basic idea of Expert Iteration is to have:
- A policy that we're training (parameterised by some function approximator like a Deep Neural Net)
- A tree search algorithm, like Monte Carlo tree search (MCTS).
These two components can then iteratively improve each other. The trained policy can be used to guide the search behaviour of MCTS. MCTS can be used to generate a new distribution over actions which, thanks to additional search effort, is typically expected to be a little bit better than then trained policy. That slightly better distribution is then used as a training target for the policy, using a Cross-Entropy loss. This means that the policy is trained to mimic the MCTS search behaviour, and also used to improve that same MCTS search behaviour.
This training procedure has been found to lead to strong results. One of the prevailing hypotheses is that the additional search performed by MCTS can help to stabilise training, and avoid overfitting to the "self" opponent; the search algorithm can actually "reason" about what a strong opponent (not necessarily the "self" agent) could do.
The Expert Iteration training procedure I described above often works well, but it doesn't really answer your question about training Actor-Critic approaches in games with opponents... because it's not really an Actor-Critic algorithm!
In Learning Policies from Self-Play with Policy Gradients and MCTS Value Estimates, we (I'm first author on this paper) propose an approach where the policy in self-play is trained using a training target based on the value estimates of MCTS, rather than the visit counts of MCTS (which is what we use in the standard Expert Iteration framework).
I don't know if it necessarily should exactly be called an Actor-Critic algorithm, but you could intuitively view it as an "Actor-Critic" approach where MCTS is the critic. As mentioned right before Section IV, the resulting gradient estimator also turns out to be very similar to that of the "Mean Actor Critic".
If Expert-Iteration-style solutions are not an option (for example because tree search is infeasible), I would suggest taking a look at some of the following Policy-Gradient-based approaches (and possibly later research that cites these papers):
