Answers.Body: <p>I think it can be such difficult to use DQN to play Go.Since Go has about 361! states.This results in most of the obtained Q(s',a') being sparse in all cases, which makes the convergence very, very slow.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-10T18:36:46.797Z
Answers.LastActivityDate: 2024-09-10T18:36:46.797Z
Answers.UserDisplayName: ななこ七七子
Answers.Body: <p>DQN and MCTS (+ NNs) are algorithms of two distinct RL flavors:</p>
  <ul>
  <li>DQN is <em>model-free</em> RL: it's able to learn the value of actions without having access to the underlying MDP (i.e. environment's model), so that you can later retrieve a (<span class="math-container">$\epsilon$</span>-greedy) policy.</li>
  <li>MCTS is a <em>planning</em> technique in <em>model-based</em> RL. You can use it only if you have access to the model of the MDP (or to a learned approximation). Having the true model is quite beneficial, because you can plan in advance meaning that you can reason about which action is the best by seeing what would happen in the future.</li>
  </ul>
  <p>DQN is able to do a 1-step lookahead in the future by looking at the action-value of the next state-action pair, i.e. <span class="math-container">$Q(s',a')$</span> - there are also extensions to <span class="math-container">$n$</span>-step learning, anyway <span class="math-container">$n$</span> is relatively small (because that whould increase variance a lot) - instead MCTS can explore the full tree of interaction (where you have all the possible state-action combinations) until termination of the episode. Indeed, exploring the full tree is always impractical and MCTS does this in a randomized fashion (thus the name Monte Carlo) to approximate the value.</p>
  <p>AlphaGo/Zero uses also a <em>value network</em> to provide a further estimate of the next state value, <span class="math-container">$V(s')$</span>, which is combined with the classical notion of value provided by MCTS itself, then it has also a policy network that is learned to predict the actions found useful by MCTS.</p>
  <blockquote>
  <p>My current theory is that Deep Q Learning approaches require dense reward environments and games like chess don't really place emphasis on mid game rewards.</p>
  </blockquote>
  <p>Partially true, I mean exploration technique and reward shaping can help with sparse rewards, but the point is that having access to the underlying model makes everything easier to learn. Consider that DQN has to implicitly learn the model (actually it learns an association between state-action and value), and after learning it cannot change its beliefs if the state distribution shifts for example. Instead, MCTS can even adapt to changing distributions because you plan your action in advance, so without experiencing the actual environment.</p>
  <blockquote>
  <p>My question is why didn't the Alpha zero team use a deep Q learning approach if it is capable of building complex representations of the state.</p>
  </blockquote>
  <p>Their value network can, in principle, learn complex representations of the state too. It is used as a heuristic to improve the search of MCTS. In principle, I think is possibile to use a Q-network too but one has to change the heuristic that MCTS follows to judge actions which guides the exploration of the game tree.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-02T13:25:59.737Z
Answers.LastActivityDate: 2023-07-02T13:25:59.737Z
Answers.UserDisplayName: Luca Anzalone
Body: <p>Recently I've been studying how Deep Q Networks work, and as I was reading I just assumed that game engines like Alpha Zero use Deep Q Learning to choose actions. But as I was reading the Alpha Zero papers and I saw that they were using Monte Carlo Tree Search with a Neural network in the back to provide policy and value predictions. My question is why didn't the Alpha zero team use a deep Q learning approach if it is capable of building complex representations of the state. What are the advantages to using a Tree search algorithm for this particular circumstance and in general what are the different situations where one would prefer to use Deep Q learning and where one would go for a Monte Carlo Tree approach.</p>
  <p>My current theory is that Deep Q Learning approaches require dense reward environments and games like chess don't really place emphasis on mid game rewards. The only thing that matters is to win the game whether by a lot or a little.</p>
  
Tags: <reinforcement-learning><dqn><monte-carlo-tree-search><alphazero>
Title: Deep Q Networks v Monte Carlo Tree Search in Alpha Zero
UserDisplayName: Kiran Manicka
ThreadText: # Deep Q Networks v Monte Carlo Tree Search in Alpha Zero
  
  (Asked by: username_0 on 2023-07-01)
  
  Recently I've been studying how Deep Q Networks work, and as I was reading I just assumed that game engines like Alpha Zero use Deep Q Learning to choose actions. But as I was reading the Alpha Zero papers and I saw that they were using Monte Carlo Tree Search with a Neural network in the back to provide policy and value predictions. My question is why didn't the Alpha zero team use a deep Q learning approach if it is capable of building complex representations of the state. What are the advantages to using a Tree search algorithm for this particular circumstance and in general what are the different situations where one would prefer to use Deep Q learning and where one would go for a Monte Carlo Tree approach.
  
  My current theory is that Deep Q Learning approaches require dense reward environments and games like chess don't really place emphasis on mid game rewards. The only thing that matters is to win the game whether by a lot or a little.
  
  **Tags:** reinforcement-learning, dqn, monte-carlo-tree-search, alphazero
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-07-02. Score: 5 | Accepted answer
  
  DQN and MCTS (+ NNs) are algorithms of two distinct RL flavors:
  
  * DQN is *model-free* RL: it's able to learn the value of actions without having access to the underlying MDP (i.e. environment's model), so that you can later retrieve a ($\epsilon$-greedy) policy.
  * MCTS is a *planning* technique in *model-based* RL. You can use it only if you have access to the model of the MDP (or to a learned approximation). Having the true model is quite beneficial, because you can plan in advance meaning that you can reason about which action is the best by seeing what would happen in the future.
  
  DQN is able to do a 1-step lookahead in the future by looking at the action-value of the next state-action pair, i.e. $Q(s',a')$ - there are also extensions to $n$-step learning, anyway $n$ is relatively small (because that whould increase variance a lot) - instead MCTS can explore the full tree of interaction (where you have all the possible state-action combinations) until termination of the episode. Indeed, exploring the full tree is always impractical and MCTS does this in a randomized fashion (thus the name Monte Carlo) to approximate the value.
  
  AlphaGo/Zero uses also a *value network* to provide a further estimate of the next state value, $V(s')$, which is combined with the classical notion of value provided by MCTS itself, then it has also a policy network that is learned to predict the actions found useful by MCTS.
  
  > My current theory is that Deep Q Learning approaches require dense reward environments and games like chess don't really place emphasis on mid game rewards.
  
  Partially true, I mean exploration technique and reward shaping can help with sparse rewards, but the point is that having access to the underlying model makes everything easier to learn. Consider that DQN has to implicitly learn the model (actually it learns an association between state-action and value), and after learning it cannot change its beliefs if the state distribution shifts for example. Instead, MCTS can even adapt to changing distributions because you plan your action in advance, so without experiencing the actual environment.
  
  > My question is why didn't the Alpha zero team use a deep Q learning approach if it is capable of building complex representations of the state.
  
  Their value network can, in principle, learn complex representations of the state too. It is used as a heuristic to improve the search of MCTS. In principle, I think is possibile to use a Q-network too but one has to change the heuristic that MCTS follows to judge actions which guides the exploration of the game tree.
  
  
  ---
  
  ### Answer by username_1 on 2024-09-10. Score: 0
  
  I think it can be such difficult to use DQN to play Go.Since Go has about 361! states.This results in most of the obtained Q(s',a') being sparse in all cases, which makes the convergence very, very slow.
  
  
  ---
  
  