Answers.Body: <p>Assuming a continuous/uncountable state space, we can only estimate our value function using function approximation, so our estimates will never be true for all states simultaneously (because, loosely speaking, we have far more states than weights). If we can look at the (approximated) value of states we take in, say, 5 actions time, it is better to make a decision based on these estimations, taking into account the true rewards observed after the 5 actions.</p>
  <p>Further, MCTS also allows more implicit exploration as when choosing the actions to expand the tree we are potentially choosing lots of non-greedy actions that lead to better future returns.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T11:06:11.133Z
Answers.Text: I would note that technically, "because we have far more states than weights" is not the full story as to why our estimates may not be 100% correct. We could probably come up with some weird MDP where there are many different states, each represented by a single variable, and even linear function approximator with just a single weight is sufficient to perfectly represent the optimal value function. In general, in "real-world" / "interesting" problems, it's roughly true-ish though :)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T11:19:45.153Z
Answers.Text: @DennisSoemers I’ve added a disclaimer for you. :)
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T18:08:49.017Z
Answers.Text: @DavidIreland I think your point is that using value based methods only is like having perfect confidence in what would happen in the future, while MCTS simulates the future, so it should have better approximation of the value, am I right?
Answers.UserDisplayName: Hossam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T18:15:40.033Z
Answers.Text: Yes, that sounds correct @Hossam. MCTS essentially allows the agent to search(/plan) and make decisions using real transitions that are simulated in the environment to better help with the decision making.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-05T10:22:36.880Z
Answers.LastActivityDate: 2021-04-05T11:19:15.320Z
Answers.LastEditDate: 2021-04-05T11:19:15.320Z
Answers.UserDisplayName: David
Body: <p>I have been trying to understand why MCTS is very important to the performance of RL agents, and the best description I found was from the paper <a href="https://papers.nips.cc/paper/2009/file/389bc7bb1e1c2a5e7e147703232a88f6-Paper.pdf" rel="nofollow noreferrer">Bootstrapping from Game Tree Search</a> stating:</p>
  <blockquote>
  <p>Deterministic, two-player games such as chess provide an ideal
  test-bed for search bootstrapping. The intricate tactics require a
  significant level of search to provide an accurate position
  evaluation; learning without search has produced little success in
  these domains.</p>
  </blockquote>
  <p>I however don't understand why this is the case, and why value based methods are unable to achieve similar performance.</p>
  <p>So my question would be:</p>
  <ul>
  <li>What are the main advantages of incorporating search based algorithms with value based methods?</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-04T22:29:18.380Z
Comments.Text: In short and simplified terms, MCTS is like being able to look into the future based on experience and choosing the best action :-)
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-04T22:34:14.993Z
Comments.Text: @DavidIreland yes, but value based methods approximate the expected return of the future as well, so why would looking at the future while executing be more accurate than our value estimate?
Comments.UserDisplayName: Hossam
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T00:34:47.643Z
Comments.Text: we can only estimate our values using function approximation, so our estimates will never be _true_ (because we have far more states than weights). If we can look at the (approximated) value of states we take in, say, 5 actions time, it is better to make a decision based on these estimations, taking into account the true rewards observed after the 5 actions. Further, MCTS also allows more implicit exploration as when choosing the actions to expand the tree we are potentially choosing lots of non-greedy actions that lead to better future returns.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-05T08:01:56.163Z
Comments.Text: @DavidIreland That comment looks like the basis of a good answer already
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><monte-carlo-tree-search><value-based-methods>
Title: What is the advantage of using MCTS with value based methods over value based methods only?
UserDisplayName: Hossam
ThreadText: # What is the advantage of using MCTS with value based methods over value based methods only?
  
  (Asked by: username_0 on 2021-04-04)
  
  I have been trying to understand why MCTS is very important to the performance of RL agents, and the best description I found was from the paper [Bootstrapping from Game Tree Search](https://papers.nips.cc/paper/2009/file/389bc7bb1e1c2a5e7e147703232a88f6-Paper.pdf) stating:
  
  > Deterministic, two-player games such as chess provide an ideal
  > test-bed for search bootstrapping. The intricate tactics require a
  > significant level of search to provide an accurate position
  > evaluation; learning without search has produced little success in
  > these domains.
  
  I however don't understand why this is the case, and why value based methods are unable to achieve similar performance.
  
  So my question would be:
  
  * What are the main advantages of incorporating search based algorithms with value based methods?
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, value-based-methods
  > **Comments:**
  > **username_1**: In short and simplified terms, MCTS is like being able to look into the future based on experience and choosing the best action :-)  
  > **username_0**: @DavidIreland yes, but value based methods approximate the expected return of the future as well, so why would looking at the future while executing be more accurate than our value estimate?  
  > **username_1**: we can only estimate our values using function approximation, so our estimates will never be _true_ (because we have far more states than weights). If we can look at the (approximated) value of states we take in, say, 5 actions time, it is better to make a decision based on these estimations, taking into account the true rewards observed after the 5 actions. Further, MCTS also allows more implicit exploration as when choosing the actions to expand the tree we are potentially choosing lots of non-greedy actions that lead to better future returns.  
  > **username_2**: @DavidIreland That comment looks like the basis of a good answer already  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-04-05. Score: 3 | Accepted answer
  
  Assuming a continuous/uncountable state space, we can only estimate our value function using function approximation, so our estimates will never be true for all states simultaneously (because, loosely speaking, we have far more states than weights). If we can look at the (approximated) value of states we take in, say, 5 actions time, it is better to make a decision based on these estimations, taking into account the true rewards observed after the 5 actions.
  
  Further, MCTS also allows more implicit exploration as when choosing the actions to expand the tree we are potentially choosing lots of non-greedy actions that lead to better future returns.
  
  > **Comments:**
  > **username_3**: I would note that technically, "because we have far more states than weights" is not the full story as to why our estimates may not be 100% correct. We could probably come up with some weird MDP where there are many different states, each represented by a single variable, and even linear function approximator with just a single weight is sufficient to perfectly represent the optimal value function. In general, in "real-world" / "interesting" problems, it's roughly true-ish though :)  
  > **username_1**: @DennisSoemers I’ve added a disclaimer for you. :)  
  > **username_0**: @DavidIreland I think your point is that using value based methods only is like having perfect confidence in what would happen in the future, while MCTS simulates the future, so it should have better approximation of the value, am I right?  
  > **username_1**: Yes, that sounds correct @Hossam. MCTS essentially allows the agent to search(/plan) and make decisions using real transitions that are simulated in the environment to better help with the decision making.  
  
  ---
  
  