Answers.Body: <p>Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to predict the next state given your current state and action (this is the model). They take advantage of this with MCTS to speed up training. I suppose Deep Q Learning would also work, but it would be at a huge disadvantage.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-07T15:06:29.760Z
Answers.LastActivityDate: 2020-07-07T15:06:29.760Z
Answers.UserDisplayName: harwiltz
Answers.Body: <p><span class="math-container">$Q$</span>-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for <strong>single-agent environments</strong>. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where that agent can take actions that have some level of influence over the states that they lead to, and rewards may be observed.</p>
  <p>If you have a problem that is, in reality, a multi-agent environment, there is a way to translate this environment to a single-agent setting; you simply have to assume that all other agents (i.e. your opponent in Go) are an inherent part of &quot;the world&quot; or &quot;the environment&quot;, and that all the states in which these other agents make moves are not really states (not visible to your agent), but just intermediate steps where these part-of-the-environment-agents cause the environment to change and, as a result, create state transitions.</p>
  <p>The primary issue with this approach is; we still need to model the decision-making of these agents in order to implement this new view of &quot;the world&quot;, where our opponents are really a part of the world. Whatever implementation we give them, that is what our single-agent RL algorithm will learn to play against. We can just implement our opponents to be random agents, and run a single-agent RL algorithm like DQN, and then we will likely learn to play well against random agents. We'll probably still be very bad against strong opponents though. <strong>If we want to use a single-agent RL algorithm to learn to play well against strong opponents, we need to have an implementation for those strong opponents first.</strong> But if we already have that... why even bother with learning at all? We've already got the strong Go player, so we're already done and don't need to learn!</p>
  <p><strong>MCTS</strong> is a tree search algorithm, one that actively takes into account the fact that there is an opponent with opposing goals, and tries to model the choices that this opponent can make, and can do so better the more computation time we give it. <strong>This algorithm, and learning approaches built around it, are inherently designed to tackle the multi-agent setting</strong> (with agents having opposing goals).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-16T09:39:16.487Z
Answers.Text: It is a nice reply, but it is better to emphasize that deep Q-learning can be used for multi-agent games. TDGammon, for example play gammon and uses temporal difference learning with a neural network, a similar algorithm to deep Q-learning. Even though gammon is a two-agent game, the things you say do not apply for the algorithm of TDGammon because it uses Bellman's equation to update the parameters.
Answers.UserDisplayName: Fırat Kıyak
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-16T10:34:42.623Z
Answers.Text: @FıratKıyak Actually, even TD-Gammon's algorithm probably "shouldn't" have worked in theory, at least in the sense that such an algorithm was not guaranteed to converge to a correct solution for a 2-player game, even given infinite computation time and an infinitely large neural network. The fact that it happened to work well in practice there was likely due to the high degree of stochasticity in the game, automatically creating variety in experience. See also: http://papers.neurips.cc/paper/1292-why-did-td-gammon-work.pdf
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-07T20:03:42.870Z
Answers.LastActivityDate: 2020-07-07T20:03:42.870Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In <a href="https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf" rel="nofollow noreferrer">the previous research</a>, in 2015, Deep Q-Learning shows its great performance on single player Atari Games. But why do AlphaGo's researchers use CNN + MCTS instead of Deep Q-Learning? is that because Deep Q-Learning somehow is not suitable for Go?</p>
  
Tags: <reinforcement-learning><deep-rl><monte-carlo-tree-search>
Title: Why AlphaGo didn't use Deep Q-Learning?
UserDisplayName: malioboro
ThreadText: # Why AlphaGo didn't use Deep Q-Learning?
  
  (Asked by: username_0 on 2020-04-24)
  
  In [the previous research](https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf), in 2015, Deep Q-Learning shows its great performance on single player Atari Games. But why do AlphaGo's researchers use CNN + MCTS instead of Deep Q-Learning? is that because Deep Q-Learning somehow is not suitable for Go?
  
  **Tags:** reinforcement-learning, deep-rl, monte-carlo-tree-search
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-07-07. Score: 9 | Accepted answer
  
  $Q$-learning (and also its deep variant, and most of the other well-known reinforcement learning algorithms) are inherently learning approaches for **single-agent environments**. The entire problem setting that these algorithms are developed for (Markov decision processes, or MDPs) is always framed in terms of a single agent situated in some environment, where that agent can take actions that have some level of influence over the states that they lead to, and rewards may be observed.
  
  If you have a problem that is, in reality, a multi-agent environment, there is a way to translate this environment to a single-agent setting; you simply have to assume that all other agents (i.e. your opponent in Go) are an inherent part of "the world" or "the environment", and that all the states in which these other agents make moves are not really states (not visible to your agent), but just intermediate steps where these part-of-the-environment-agents cause the environment to change and, as a result, create state transitions.
  
  The primary issue with this approach is; we still need to model the decision-making of these agents in order to implement this new view of "the world", where our opponents are really a part of the world. Whatever implementation we give them, that is what our single-agent RL algorithm will learn to play against. We can just implement our opponents to be random agents, and run a single-agent RL algorithm like DQN, and then we will likely learn to play well against random agents. We'll probably still be very bad against strong opponents though. **If we want to use a single-agent RL algorithm to learn to play well against strong opponents, we need to have an implementation for those strong opponents first.** But if we already have that... why even bother with learning at all? We've already got the strong Go player, so we're already done and don't need to learn!
  
  **MCTS** is a tree search algorithm, one that actively takes into account the fact that there is an opponent with opposing goals, and tries to model the choices that this opponent can make, and can do so better the more computation time we give it. **This algorithm, and learning approaches built around it, are inherently designed to tackle the multi-agent setting** (with agents having opposing goals).
  
  > **Comments:**
  > **username_3**: It is a nice reply, but it is better to emphasize that deep Q-learning can be used for multi-agent games. TDGammon, for example play gammon and uses temporal difference learning with a neural network, a similar algorithm to deep Q-learning. Even though gammon is a two-agent game, the things you say do not apply for the algorithm of TDGammon because it uses Bellman's equation to update the parameters.  
  > **username_2**: @username_3 Actually, even TD-Gammon's algorithm probably "shouldn't" have worked in theory, at least in the sense that such an algorithm was not guaranteed to converge to a correct solution for a 2-player game, even given infinite computation time and an infinitely large neural network. The fact that it happened to work well in practice there was likely due to the high degree of stochasticity in the game, automatically creating variety in experience. See also: http://papers.neurips.cc/paper/1292-why-did-td-gammon-work.pdf  
  
  ---
  
  ### Answer by username_1 on 2020-07-07. Score: 6
  
  Deep Q Learning is a model-free algorithm. In the case of Go (and chess for that matter) the model of the game is very simple and deterministic. It's a perfect information game, so it's trivial to predict the next state given your current state and action (this is the model). They take advantage of this with MCTS to speed up training. I suppose Deep Q Learning would also work, but it would be at a huge disadvantage.
  
  
  ---
  
  