Answers.Body: <p>The specific approaches you mentioned (A3C, DDPG), and usually also other Actor-Critic methods in general, are approaches for the standard <strong>single-agent</strong> 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:</p>
  
  <blockquote>
    <ol>
    <li>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.</li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <blockquote>
    <ol start="2">
    <li>Play against list of specific AIs. Results were excellent against those AIs, but very bad with never seen opponents</li>
    </ol>
  </blockquote>
  
  <p>Here you pretty much exactly give a description of what I mean when I say "overfitting" against the opponent you're training against.</p>
  
  <blockquote>
    <ol start="3">
    <li>Play against itself. Seemed the best to me, but I could not get any convergence due to non-stationary environment. </li>
    </ol>
  </blockquote>
  
  <p>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.</p>
  
  <hr>
  
  <p>The standard approach for self-play training in games is the one popularised by <a href="https://www.nature.com/articles/nature24270" rel="nofollow noreferrer">AlphaGo Zero</a> and <a href="https://science.sciencemag.org/content/362/6419/1140" rel="nofollow noreferrer">AlphaZero</a>, and also around the same time <a href="https://papers.nips.cc/paper/7120-thinking-fast-and-slow-with-deep-learning-and-tree-search" rel="nofollow noreferrer">independently published with results on the game of Hex</a>. 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:</p>
  
  <ol>
  <li>A policy that we're training (parameterised by some function approximator like a Deep Neural Net)</li>
  <li>A tree search algorithm, like Monte Carlo tree search (MCTS).</li>
  </ol>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <hr>
  
  <p>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!</p>
  
  <p>In <a href="https://arxiv.org/abs/1905.05809" rel="nofollow noreferrer">Learning Policies from Self-Play with Policy Gradients and MCTS Value Estimates</a>, 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). </p>
  
  <p>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".</p>
  
  <hr>
  
  <p>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):</p>
  
  <ul>
  <li><a href="https://arxiv.org/abs/1709.04326" rel="nofollow noreferrer">Learning with Opponent-Learning Awareness</a></li>
  <li><a href="https://arxiv.org/abs/1904.03646" rel="nofollow noreferrer">Policy Gradient Search: Online Planning and Expert Iteration without Search Trees</a></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-08T22:15:48.833Z
Answers.Text: *Great* breakdown of common overfitting pitfalls and expert iteration!  Thanks for this.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-16T18:41:42.183Z
Answers.LastActivityDate: 2019-05-16T18:41:42.183Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>I am wondering how am I supposed to train a model using actor/critic algorithms in <strong>environments with opponents</strong>. I tried the followings (using A3C and DDPG):</p>
  
  <ol>
  <li>Play against <strong>random player</strong>. I had rather good results, but not as good as expected since most interesting states cannot be reached with a random opponent.</li>
  <li>Play against <strong>list of specific AIs</strong>. Results were excellent against those AIs, but very bad with never seen opponents</li>
  <li>Play against <strong>itself</strong>. Seemed the best to me, but I could not get any convergence due to non-stationary environment. </li>
  </ol>
  
  <p>Any thought or advice about this would be very welcome.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-11T19:55:39.617Z
Comments.Text: I've recently had a paper accepted at a conference (COG 2019) which would be very relevant to any answer I'd write to this question. Since it only went through peer review relatively recently, it's not publicly available yet. But I do plan to put it up on arXiv very soon (during the coming week somewhere). In case I forget to come back to this question afterwards... feel free to poke me here in a few days to remind me.
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-11T20:07:27.357Z
Comments.Text: I look forward to reading this, thank you ! I am surprised of the difficulties I had to find any relevant paper on this question.
Comments.UserDisplayName: Loheek
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-08T22:12:40.343Z
Comments.Text: @DennisSoemers poking you on the paper!
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-09T09:30:43.367Z
Comments.Text: @DukeZhou It's in my answer down below, though that link is still the arXiv version. The PDF link from the conference itself is here: http://www.ieee-cog.org/2019/papers/paper_91.pdf . We barely missed out on Best Paper Award for this paper, got second place!
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-10T01:11:46.917Z
Comments.Text: Lol the Nash-Equilbrium theorem guarantees convergence. You just need to improve stability (e.g. with a greater diversity of starting agents & more compute).
Comments.UserDisplayName: profPlum
Tags: <neural-networks><deep-learning><reinforcement-learning><ddpg>
Title: Training actor-critic algorithms in games with opponents
UserDisplayName: Loheek
ThreadText: # Training actor-critic algorithms in games with opponents
  
  (Asked by: username_0 on 2019-05-11)
  
  I am wondering how am I supposed to train a model using actor/critic algorithms in **environments with opponents**. I tried the followings (using A3C and DDPG):
  
  1. 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.
  2. Play against **list of specific AIs**. Results were excellent against those AIs, but very bad with never seen opponents
  3. Play against **itself**. Seemed the best to me, but I could not get any convergence due to non-stationary environment.
  
  Any thought or advice about this would be very welcome.
  
  **Tags:** neural-networks, deep-learning, reinforcement-learning, ddpg
  
  > **Comments:**
  > **username_1**: I've recently had a paper accepted at a conference (COG 2019) which would be very relevant to any answer I'd write to this question. Since it only went through peer review relatively recently, it's not publicly available yet. But I do plan to put it up on arXiv very soon (during the coming week somewhere). In case I forget to come back to this question afterwards... feel free to poke me here in a few days to remind me.  
  > **username_0**: I look forward to reading this, thank you ! I am surprised of the difficulties I had to find any relevant paper on this question.  
  > **username_2**: @username_1 poking you on the paper!  
  > **username_1**: @username_2 It's in my answer down below, though that link is still the arXiv version. The PDF link from the conference itself is here: http://www.ieee-cog.org/2019/papers/paper_91.pdf . We barely missed out on Best Paper Award for this paper, got second place!  
  > **username_3**: Lol the Nash-Equilbrium theorem guarantees convergence. You just need to improve stability (e.g. with a greater diversity of starting agents & more compute).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-16. Score: 2
  
  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:
  
  > 1. 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.
  
  > 2. 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.
  
  > 3. 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](https://www.nature.com/articles/nature24270) and [AlphaZero](https://science.sciencemag.org/content/362/6419/1140), and also around the same time [independently published with results on the game of Hex](https://papers.nips.cc/paper/7120-thinking-fast-and-slow-with-deep-learning-and-tree-search). 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:
  
  1. A policy that we're training (parameterised by some function approximator like a Deep Neural Net)
  2. 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](https://arxiv.org/abs/1905.05809), 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):
  
  * [Learning with Opponent-Learning Awareness](https://arxiv.org/abs/1709.04326)
  * [Policy Gradient Search: Online Planning and Expert Iteration without Search Trees](https://arxiv.org/abs/1904.03646)
  
  > **Comments:**
  > **username_2**: *Great* breakdown of common overfitting pitfalls and expert iteration!  Thanks for this.  
  
  ---
  
  