Answers.Body: <p>Whether or not MCTS is even a Reinforcement Learning algorithm at all <a href="https://ai.stackexchange.com/q/7589/1641">may be up for debate</a>, but let's assume that we view it as an RL algorithm here.</p>
  
  <p><strong>For practical purposes, MCTS really should be considered to be a Model-Based method.</strong> Below, I'm going to describe how you could view it as a <strong>Model-Free RL approach</strong> in some way... and then wrap back to why that viewpoint isn't really often useful in practice.</p>
  
  <hr>
  
  <p>More specifically, following <a href="https://jair.org/index.php/jair/article/view/11099/26289" rel="noreferrer">this paper</a>, we'll think of an MCTS search process as a value-based RL algorithm (it learns estimates of a value function, very much like Sarsa, <span class="math-container">$Q$</span>-learning, etc.), which limits itself to learning values for the states that it chooses to represent by nodes in the search tree (this set of states that it chooses to represent gradually grows over time during the search process). </p>
  
  <p>Unlike traditional RL approaches, such an MCTS process doesn't really result in a policy or an exhaustive / generalizable value function estimator that can be extracted after the "training" process and re-used in many different states afterwards. We normally play a move after running MCTS, and then discard everything and start over again for the next move (maybe we'll keep a relevant part of the search tree and reuse that, but that's a minor detail... we certainly won't be able to re-use our search results in another match/game/episode).</p>
  
  <p>The <strong>MCTS search process</strong> itself can be viewed as a <strong>Model-Free RL approach</strong>; every iteration of the search can be viewed as an actual episode of an "agent" that is collecting experience in a model-free manner in a "real" environment (but not as real as the game for which we're running the complete search process), where this "internal agent" first follows the Selection Policy for a while (e.g. UCB1), and then a Play-out policy for the remainder of the episode (e.g. uniform random). </p>
  
  <p>This "internal" agent "inside" the MCTS iterations could be viewed as learning from a model-free RL process. The <strong>main problem with this view in practice</strong> is that, because MCTS "decides" to have a laser-like focus on a relatively small subset of states (around the root node), this process really only leads to something useful being learned for that state in the root node (and possibly some of the closest children/grandchildren/etc.). We don't really learn something that can easily be re-used in the future in MCTS. <strong>What this means in practice is that we have to be able to re-run the complete "Reinforcement Learning process" (or search) whenever we need to make a decision</strong> (i.e. every turn in a turn-based game). </p>
  
  <p>That is feasible if you have a simulator, or <strong>model</strong> of the environment, in which you can do the learning... but then we really get back to actually have a <strong>model-based</strong> approach.</p>
  
  <hr>
  
  <p>Fun fact: if you like to take the viewpoint of MCTS as a Model-Free RL approach, you could also turn that into a Model-Based approach again by incorporating additional forms of planning/search "inside" the MCTS iterations. For example, you can <a href="https://ai.stackexchange.com/q/9504/1641">run little instances of MiniMax inside every MCTS iteration</a>, and I suppose that would turn the approach into a Model-Based approach again even in this viewpoint.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-31T19:59:47.977Z
Answers.Text: Thanks for the answer Dennis. Sorry for the delay I had problems accessing my account. The question started out with my confusion on MCTS and the MC approach for Q learning, but now im getting new insights and better understanding on RL. Thanks !
Answers.UserDisplayName: user21872
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-30T17:59:25.407Z
Answers.LastActivityDate: 2019-01-30T17:59:25.407Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <blockquote>
    <p>From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).</p>
  </blockquote>
  
  <p>Monte Carlo Tree Search is a <em>planning</em> algorithm. It can be considered part of RL, in a similar way to e.g. Dyna-Q.</p>
  
  <p>As a planning algorithm MCTS does need access to a model of the environment. Specifically it requires a <em>sampling</em> model, i.e. a model that can accept a state and action, then return a single next state and reward with the same probabilities as the target system. The alternative model, used by other RL techniques such as Value Iteration, is a <em>distribution</em> model which provides the full distribution of probabilities for rewards and next states. </p>
  
  <blockquote>
    <p>if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ?</p>
  </blockquote>
  
  <p>It is not the case. The agent knows what it will observe during the simulation because the simulation <em>is</em> a sampling model.</p>
  
  <blockquote>
    <p>In this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model based reinforcement learning and not model free reinforcement learning ?</p>
  </blockquote>
  
  <p>Yes. This is how most planning algorithms work. </p>
  
  <p>The simulation <em>can</em> be driven purely by sampling from previous experience, which is how Dyna-Q works*. I would still consider that a model-based approach, and its success depends a lot on how well such a model can be learned. In many cases, variance due to errors in the learned model adversely affects learning. So MCTS works best in environments that can be accurately sampled, because they are strongly rules-driven. For example, board games.</p>
  
  <hr>
  
  <p>* Functionally DynaQ is almost identical to experience replay. So much so, that whether you consider it a planning algorithm or experience replay added to basic Q learning is more a matter of how you present the design of the learning agent - e.g. perhaps a designer wants to focus on the model-learning side more, so has code that explicitly represents the learned model.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-30T18:01:33.137Z
Answers.Text: This is the common-sense answer, I guess my answer is the tinfoil-hat answer :D
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-31T20:05:16.370Z
Answers.Text: Thanks Neil for the answer. Both you and Dennis helps me understand better on model free and model based RL. Of course my confusion is mistaking MCTS as RL solution algorithm instead of search algorithm. Merging them is wht makes things interesting like in Alphago. Thanks !
Answers.UserDisplayName: user21872
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-30T17:27:28.887Z
Answers.LastActivityDate: 2019-01-30T17:27:28.887Z
Answers.UserDisplayName: Neil Slater
Body: <p>From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).</p>
  
  <p>Model free RL means agent doesnt know the transition and reward model. Thus for it to know which next state it will observe and next reward it will get is for the agent to actually perform an action.</p>
  
  <p>my question is:
  if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ? (it never really <strong>interact</strong> with the environment: e.g it never really move the piece in a Go game during rollout or look ahead, thus cannot observed anything). </p>
  
  <p>It can only assume observing anything when not actually interacting with environment (during simulation) if it knows the transition model as I understand it. The same arguments goes for the rewards during rollout/ simulation.</p>
  
  <p>in this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model <strong>based</strong> reinforcement learning and not model <strong>free</strong> reinforcement learning ?</p>
  
  <p>** it makes sense in Alphago, since the agent is trained to estimate what it would observed. but MCTS (without policy and value netwrok) method assumes that agent knows what it would observed even though no additional training is included.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-30T09:04:40.010Z
Comments.Text: Could you clarify exactly what you are referring to when you say "Monte Carlo Search Algorithm"? Monte-Carlo is a very general concept, not one specific algorithm. **Monte-Carlo Tree Search** is more specific, that's one algorithm (or kind of a family of very closely related algorithms). I suspect you're confusing traditional model-free RL approaches based on Monte Carlo **Returns** (not search) with MCTS... but it would be easier to tell for sure if you mention in which textbook (and where in the textbook) you read that statement
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-30T09:40:33.147Z
Comments.Text: Thanks for the reply Dennis, I meant MCTS, because this is what occurred to me when reading the explanation of of Alphago. Because from what I understand Alphago improve the search by also using policy and value network. I think MCTS without policy and value network in Go game is also a model free RL approaches ? and if that is the case i am still confuse about knowing the reward and transition during rollout   .....*I editted the question to make it clearer
Comments.UserDisplayName: user21872
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-30T09:46:29.477Z
Comments.Text: I see... I'll likely write a more detailed answer somewhere later today (may take a while) if noone else does in the meantime. But my very short answer would be: MCTS often isn't viewed as an RL algorithm at all, though sometimes it may be (see answers to https://ai.stackexchange.com/q/7589/1641). If you take that view of it being an RL algorithm... I would say that it is a model-free RL algorithm, but one that does require a model of the environment because you don't extract a reusable policy from it, but run it over and over again for every state you encounter (e.g. every turn in a game).
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-30T10:01:52.817Z
Comments.Text: I see, thanks for the link. I think most of my confusion stems from MCTS sort of like estimating the value of the nodes which confused me with RL solution approach. So maybe this means that MCTS cant function without a sort of mechanism telling which states to go next upon taking an action or branching (I would assume a sort of transition model). But this is clear if I separate: agent learning & pure tree search algorithm (not exclusively apply for agent to learn value). Now this makes sense. Anyway I look forward to read your detailed answer too. Thanks !
Comments.UserDisplayName: user21872
Tags: <reinforcement-learning><models><monte-carlo-tree-search>
Title: Rollout algorithm like Monte Carlo search suggest model based reinforcement learning?
UserDisplayName: user21872
ThreadText: # Rollout algorithm like Monte Carlo search suggest model based reinforcement learning?
  
  (Asked by: username_0 on 2019-01-30)
  
  From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).
  
  Model free RL means agent doesnt know the transition and reward model. Thus for it to know which next state it will observe and next reward it will get is for the agent to actually perform an action.
  
  my question is:
  if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ? (it never really **interact** with the environment: e.g it never really move the piece in a Go game during rollout or look ahead, thus cannot observed anything).
  
  It can only assume observing anything when not actually interacting with environment (during simulation) if it knows the transition model as I understand it. The same arguments goes for the rewards during rollout/ simulation.
  
  in this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model **based** reinforcement learning and not model **free** reinforcement learning ?
  
  \*\* it makes sense in Alphago, since the agent is trained to estimate what it would observed. but MCTS (without policy and value netwrok) method assumes that agent knows what it would observed even though no additional training is included.
  
  **Tags:** reinforcement-learning, models, monte-carlo-tree-search
  > **Comments:**
  > **username_1**: Could you clarify exactly what you are referring to when you say "Monte Carlo Search Algorithm"? Monte-Carlo is a very general concept, not one specific algorithm. **Monte-Carlo Tree Search** is more specific, that's one algorithm (or kind of a family of very closely related algorithms). I suspect you're confusing traditional model-free RL approaches based on Monte Carlo **Returns** (not search) with MCTS... but it would be easier to tell for sure if you mention in which textbook (and where in the textbook) you read that statement  
  > **username_0**: Thanks for the reply Dennis, I meant MCTS, because this is what occurred to me when reading the explanation of of Alphago. Because from what I understand Alphago improve the search by also using policy and value network. I think MCTS without policy and value network in Go game is also a model free RL approaches ? and if that is the case i am still confuse about knowing the reward and transition during rollout   .....*I editted the question to make it clearer  
  > **username_1**: I see... I'll likely write a more detailed answer somewhere later today (may take a while) if noone else does in the meantime. But my very short answer would be: MCTS often isn't viewed as an RL algorithm at all, though sometimes it may be (see answers to https://ai.stackexchange.com/q/7589/1641). If you take that view of it being an RL algorithm... I would say that it is a model-free RL algorithm, but one that does require a model of the environment because you don't extract a reusable policy from it, but run it over and over again for every state you encounter (e.g. every turn in a game).  
  > **username_0**: I see, thanks for the link. I think most of my confusion stems from MCTS sort of like estimating the value of the nodes which confused me with RL solution approach. So maybe this means that MCTS cant function without a sort of mechanism telling which states to go next upon taking an action or branching (I would assume a sort of transition model). But this is clear if I separate: agent learning & pure tree search algorithm (not exclusively apply for agent to learn value). Now this makes sense. Anyway I look forward to read your detailed answer too. Thanks !  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-01-30. Score: 5
  
  Whether or not MCTS is even a Reinforcement Learning algorithm at all [may be up for debate](https://ai.stackexchange.com/q/7589/1641), but let's assume that we view it as an RL algorithm here.
  
  **For practical purposes, MCTS really should be considered to be a Model-Based method.** Below, I'm going to describe how you could view it as a **Model-Free RL approach** in some way... and then wrap back to why that viewpoint isn't really often useful in practice.
  
  ---
  
  More specifically, following [this paper](https://jair.org/index.php/jair/article/view/11099/26289), we'll think of an MCTS search process as a value-based RL algorithm (it learns estimates of a value function, very much like Sarsa, $Q$-learning, etc.), which limits itself to learning values for the states that it chooses to represent by nodes in the search tree (this set of states that it chooses to represent gradually grows over time during the search process).
  
  Unlike traditional RL approaches, such an MCTS process doesn't really result in a policy or an exhaustive / generalizable value function estimator that can be extracted after the "training" process and re-used in many different states afterwards. We normally play a move after running MCTS, and then discard everything and start over again for the next move (maybe we'll keep a relevant part of the search tree and reuse that, but that's a minor detail... we certainly won't be able to re-use our search results in another match/game/episode).
  
  The **MCTS search process** itself can be viewed as a **Model-Free RL approach**; every iteration of the search can be viewed as an actual episode of an "agent" that is collecting experience in a model-free manner in a "real" environment (but not as real as the game for which we're running the complete search process), where this "internal agent" first follows the Selection Policy for a while (e.g. UCB1), and then a Play-out policy for the remainder of the episode (e.g. uniform random).
  
  This "internal" agent "inside" the MCTS iterations could be viewed as learning from a model-free RL process. The **main problem with this view in practice** is that, because MCTS "decides" to have a laser-like focus on a relatively small subset of states (around the root node), this process really only leads to something useful being learned for that state in the root node (and possibly some of the closest children/grandchildren/etc.). We don't really learn something that can easily be re-used in the future in MCTS. **What this means in practice is that we have to be able to re-run the complete "Reinforcement Learning process" (or search) whenever we need to make a decision** (i.e. every turn in a turn-based game).
  
  That is feasible if you have a simulator, or **model** of the environment, in which you can do the learning... but then we really get back to actually have a **model-based** approach.
  
  ---
  
  Fun fact: if you like to take the viewpoint of MCTS as a Model-Free RL approach, you could also turn that into a Model-Based approach again by incorporating additional forms of planning/search "inside" the MCTS iterations. For example, you can [run little instances of MiniMax inside every MCTS iteration](https://ai.stackexchange.com/q/9504/1641), and I suppose that would turn the approach into a Model-Based approach again even in this viewpoint.
  
  > **Comments:**
  > **username_0**: Thanks for the answer Dennis. Sorry for the delay I had problems accessing my account. The question started out with my confusion on MCTS and the MC approach for Q learning, but now im getting new insights and better understanding on RL. Thanks !  
  
  ---
  
  ### Answer by username_2 on 2019-01-30. Score: 4
  
  > From what I understand, Monte Carlo Tree Search Algorithm is a solution algorithm for model free reinforcement learning (RL).
  
  Monte Carlo Tree Search is a *planning* algorithm. It can be considered part of RL, in a similar way to e.g. Dyna-Q.
  
  As a planning algorithm MCTS does need access to a model of the environment. Specifically it requires a *sampling* model, i.e. a model that can accept a state and action, then return a single next state and reward with the same probabilities as the target system. The alternative model, used by other RL techniques such as Value Iteration, is a *distribution* model which provides the full distribution of probabilities for rewards and next states.
  
  > if that is the case, then how come the agent knows which state it will observe during the rollout, since rollout is just a simulation, and the agent never actually perform that action ?
  
  It is not the case. The agent knows what it will observe during the simulation because the simulation *is* a sampling model.
  
  > In this case, doesnt rollout in Monte Carlo Tree Search algorithm suggests that the agent knows the transition model and reward model and thus a solution algorithm for model based reinforcement learning and not model free reinforcement learning ?
  
  Yes. This is how most planning algorithms work.
  
  The simulation *can* be driven purely by sampling from previous experience, which is how Dyna-Q works\*. I would still consider that a model-based approach, and its success depends a lot on how well such a model can be learned. In many cases, variance due to errors in the learned model adversely affects learning. So MCTS works best in environments that can be accurately sampled, because they are strongly rules-driven. For example, board games.
  
  ---
  
  \* Functionally DynaQ is almost identical to experience replay. So much so, that whether you consider it a planning algorithm or experience replay added to basic Q learning is more a matter of how you present the design of the learning agent - e.g. perhaps a designer wants to focus on the model-learning side more, so has code that explicitly represents the learned model.
  
  > **Comments:**
  > **username_1**: This is the common-sense answer, I guess my answer is the tinfoil-hat answer :D  
  > **username_0**: Thanks Neil for the answer. Both you and Dennis helps me understand better on model free and model based RL. Of course my confusion is mistaking MCTS as RL solution algorithm instead of search algorithm. Merging them is wht makes things interesting like in Alphago. Thanks !  
  
  ---
  
  