Answers.Body: <p>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:</p>
  
  <ul>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  <li><p>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 . . .</p></li>
  <li><p>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. </p></li>
  <li><p>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.</p></li>
  </ul>
  
  <p>Regarding your use of two opposing agents, I can see two possible improvements:</p>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>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 <em>minimise</em> the action value on its turn. That means use <code>min</code> and <code>argmin</code> functions for steps that represent player B's turn wherever player A would use <code>min</code> or <code>argmin</code>, 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).</p></li>
  </ol>
  
  <p>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</p>
  
  <p>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".</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-07T13:16:35.617Z
Answers.Text: Thanks Neil, that's a lot of useful ideas!   I will try to get a perfect player and test some of the things you suggested. How did you actually handle illegal moves in your TicTacToe implementation? Currently, I return a reward of -1 and the game is lost, but I saw that people also suggest to take the next best move that is legal. Any preferences ??
Answers.UserDisplayName: user3877351
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-07T13:22:44.793Z
Answers.Text: @Axel: There is not much benefit to teaching the agent legality of moves - it doesn't help with optimal play. So take next best. My version worked with *afterstate* value representation (instead of action-value representations), so the agent was not given the option to select a non-valid move.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-07T13:23:34.097Z
Answers.Text: My version here: https://github.com/neilslater/game_playing_scripts/blob/master/tictactoe_q.py - note it is also just a tabular implementation, so it uses string state summaries and enumerates all possible states
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-17T13:15:49.623Z
Answers.Text: If this were a tabular learning scenario, how will the final Q-values look like?
Answers.UserDisplayName: pg2455
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-17T15:10:37.283Z
Answers.Text: @pg2455: Too complex to answer in a comment in detail, and depends a lot on discount rate. With a discount rate of 1 (i.e. no discounting), then you end up with each state being strictly worth -1, 0 or 1, with the starting state worth 0. You could ask a new question on the site if you want more detail.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-21T18:59:34.273Z
Answers.Text: Thanks! I asked a new question here: https://ai.stackexchange.com/questions/10119/what-will-q-values-look-like-in-self-play-tic-tac-toe
Answers.UserDisplayName: pg2455
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-06T16:21:58.150Z
Answers.LastActivityDate: 2018-06-06T17:14:48.073Z
Answers.LastEditDate: 2018-06-06T17:14:48.073Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T22:51:25.560Z
Answers.LastActivityDate: 2019-07-31T22:51:25.560Z
Answers.UserDisplayName: DanielD
Body: <p>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.</p>
  <p>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.</p>
  <p>Assuming that there is no hidden programming bug, <em>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?</em></p>
  <p><a href="https://i.sstatic.net/y3xOx.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/y3xOx.png" alt="TicTacToeSelfPlayResults" /></a></p>
  <p>Here further details.</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-05T21:41:00.293Z
Comments.Text: have you tried making the network deeper?
Comments.UserDisplayName: k.c. sayz 'k.c sayz'
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-05T21:44:02.973Z
Comments.Text: I haven't done any DQN training before, but note that if your game agent  plateaus during self-play it might be the case that each instance of gameplay is very similar to previous instances, thus reducing the amount of "stuff" learnt
Comments.UserDisplayName: k.c. sayz 'k.c sayz'
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-06T07:47:11.033Z
Comments.Text: Sounds to me like over-fitting, ie it gets very good at beating one particular player (itself), but cannot cope easily with different playing styles.
Comments.UserDisplayName: Oliver Mason
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-06T08:45:30.683Z
Comments.Text: When you let the network play against a random player, do you switch off the exploratory moves? The DQN should in theory learn optimal play (it may not be here, and I have a few ideas about what might be going wrong for you), but the learning agent will have some epsilon probability of making a random move whilst in learning mode, so I'd like to know a bit more about how you are assessing it.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-06T10:05:10.110Z
Comments.Text: Yes, when I play against the random player exploration is off (eps=0). The shown epsilon values only apply during the phases of self-play. Btw., during self-play I train of course two independent networks which play against each other (and not one).
Comments.UserDisplayName: user3877351
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-06T12:51:16.843Z
Comments.Text: @Axel: Thanks, that's useful extra information (maybe edit this into your question). As an aside it is not necessary for zero-sum 2-player games to have two independent networks, and is more efficient to use just one evaluation network with one player trying to maximise return, the other trying to minimise it. However, that probably is not your problem. I will try to answer this question with some suggestions alter today or tomorrow
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-07T09:17:21.730Z
Comments.Text: I had a similar problem that my reward suddenly collapsed after many  training iterations. The issue was that some very big gradients that started to occur destroyed the learned weights after many iterations. I fixed it by clamping the gradients that are fed to the optimizer (Adam in my case). Also which are the opponents you play against, the most recent policy or a random pick from the history?
Comments.UserDisplayName: Marcel_marcel1991
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-08T07:22:37.453Z
Comments.Text: @Marcel: Interesting, didn't know about that problem. But that doesn't happen here. My weights remain between +-1 and clamping the gradients didn't change the result :-(   I'm testing the progress against a true random player that does not come from any history. It is simply a player that randomly picks one of the remaining free squares.
Comments.UserDisplayName: user3877351
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-08T08:21:55.210Z
Comments.Text: @Axel I mean during training what opponents do you use for the self-play. If you play always against the most recent copy of your model it can happen that it finds a perfect policy against this but that does not really generalize well. So you should maybe better play against a random sample of your history of policies. (But this is my experience in policy gradient training maybe that does not apply in q-Learning)
Comments.UserDisplayName: Marcel_marcel1991
Tags: <reinforcement-learning><deep-rl><dqn><self-play><tic-tac-toe>
Title: Why does self-playing tic-tac-toe not become perfect?
UserDisplayName: user3877351
ThreadText: # Why does self-playing tic-tac-toe not become perfect?
  
  (Asked by: username_0 on 2018-06-05)
  
  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?*
  
  [![TicTacToeSelfPlayResults](https://i.sstatic.net/y3xOx.png)](https://i.sstatic.net/y3xOx.png)
  
  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.
  
  **Tags:** reinforcement-learning, deep-rl, dqn, self-play, tic-tac-toe
  
  > **Comments:**
  > **username_1**: have you tried making the network deeper?  
  > **username_1**: I haven't done any DQN training before, but note that if your game agent  plateaus during self-play it might be the case that each instance of gameplay is very similar to previous instances, thus reducing the amount of "stuff" learnt  
  > **username_2**: Sounds to me like over-fitting, ie it gets very good at beating one particular player (itself), but cannot cope easily with different playing styles.  
  > **username_3**: When you let the network play against a random player, do you switch off the exploratory moves? The DQN should in theory learn optimal play (it may not be here, and I have a few ideas about what might be going wrong for you), but the learning agent will have some epsilon probability of making a random move whilst in learning mode, so I'd like to know a bit more about how you are assessing it.  
  > **username_0**: Yes, when I play against the random player exploration is off (eps=0). The shown epsilon values only apply during the phases of self-play. Btw., during self-play I train of course two independent networks which play against each other (and not one).  
  > **username_3**: @Axel: Thanks, that's useful extra information (maybe edit this into your question). As an aside it is not necessary for zero-sum 2-player games to have two independent networks, and is more efficient to use just one evaluation network with one player trying to maximise return, the other trying to minimise it. However, that probably is not your problem. I will try to answer this question with some suggestions alter today or tomorrow  
  > **username_4**: I had a similar problem that my reward suddenly collapsed after many  training iterations. The issue was that some very big gradients that started to occur destroyed the learned weights after many iterations. I fixed it by clamping the gradients that are fed to the optimizer (Adam in my case). Also which are the opponents you play against, the most recent policy or a random pick from the history?  
  > **username_0**: @Marcel: Interesting, didn't know about that problem. But that doesn't happen here. My weights remain between +-1 and clamping the gradients didn't change the result :-(   I'm testing the progress against a true random player that does not come from any history. It is simply a player that randomly picks one of the remaining free squares.  
  > **username_4**: @Axel I mean during training what opponents do you use for the self-play. If you play always against the most recent copy of your model it can happen that it finds a perfect policy against this but that does not really generalize well. So you should maybe better play against a random sample of your history of policies. (But this is my experience in policy gradient training maybe that does not apply in q-Learning)  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2018-06-06. Score: 4
  
  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".
  
  > **Comments:**
  > **username_0**: Thanks username_3, that's a lot of useful ideas!   I will try to get a perfect player and test some of the things you suggested. How did you actually handle illegal moves in your TicTacToe implementation? Currently, I return a reward of -1 and the game is lost, but I saw that people also suggest to take the next best move that is legal. Any preferences ??  
  > **username_3**: @Axel: There is not much benefit to teaching the agent legality of moves - it doesn't help with optimal play. So take next best. My version worked with *afterstate* value representation (instead of action-value representations), so the agent was not given the option to select a non-valid move.  
  > **username_3**: My version here: https://github.com/username_3/game_playing_scripts/blob/master/tictactoe_q.py - note it is also just a tabular implementation, so it uses string state summaries and enumerates all possible states  
  > **username_5**: If this were a tabular learning scenario, how will the final Q-values look like?  
  > **username_3**: @username_5: Too complex to answer in a comment in detail, and depends a lot on discount rate. With a discount rate of 1 (i.e. no discounting), then you end up with each state being strictly worth -1, 0 or 1, with the starting state worth 0. You could ask a new question on the site if you want more detail.  
  > **username_5**: Thanks! I asked a new question here: https://ai.stackexchange.com/questions/10119/what-will-q-values-look-like-in-self-play-tic-tac-toe  
  
  ---
  
  ### Answer by username_6 on 2019-07-31. Score: 0
  
  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.
  
  
  ---
  
  