How to overcome overfitting to single player styles in reinforcement learning?

Question

I am implementing an actor-critic reinforcement learning algorithm for winning a two player tic-tac-toe like game. The agent is trained against a min-max player and after a number of episodes is able to learn a set of rules which lead it to winning a good majority of games.

However, as soon as I play against the trained agent by using even a slightly different playing style, it looses miserably. In other words, it is evident the agent overfitted with respect to the deterministic behaviour of the min-max player. It is clear to me what are the roots of the problem, but I would like to get an overview of the different methodologies which can be applied to overcome (or mitigate) this issue.

The two solutions I would like to try are the following:
1. Training the agent with different opponents for fixed amounts of episodes (or time) each. So that for example I train the agent by using a depth 2 min-max player for the first 10000 episodes, then I use a random playing agent for the next 10000 episodes, then I use a depth 4 min-max player for other 10000 episodes and repeat the process.
2. Starting episodes from different initial configurations. In this way the agents will play a much wider set of sampled games and will be more difficult for the agent to overfit.

Are these two reasonable approaches? Are there other tricks/good practices to try out?

Answer 1

Both of the solutions you suggest seem to be built around the intuition that it's good to ensure that there is sufficient variety in the experiences that you provide to your RL algorithm.

That intuition is good, but it should not come at (too much of) a cost in playing strength of the opponent. I'm afraid that your first solution may break down because of this; Tic Tac Toe is such a simple game, any agent that doesn't play optimally can really be viewed as a very poor agent... and I think minimax agents with very low limits on search depth may end up playing suboptimally. Your second solution seems better in this regard, that could help.

For this particular case of Tic Tac Toe, I suspect you should be able to train just fine against only optimal minimax agents, as long as you make sure that those optimal minimax agents break ties randomly. In some situations, there may be multiple different actions that are all "equally optimal". Then, you'll want to make sure that your minimax agents break ties randomly, rather than always deterministically picking the same action. This can be done, for example, by making sure to always shuffle your lists of legal moves in minimax after they are generated.