Answers.Body: <p>In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things.</p>
  
  <p>The more general use of "Monte Carlo" is for simulation methods that use random numbers to sample - often as a replacement for an otherwise difficult analysis or exhaustive search.</p>
  
  <p>In RL, Monte Carlo methods are generally taken to be non-bootstrapping sample-based approaches to estimating returns. This is a labelling convention within RL - probably because someone called an initial model-free learner a "Monte Carlo method", and the name stuck whilst many refinements and new ideas have since been published under different names.</p>
  
  <p>The historical use of the term is important, since if you mention you are using "Monte Carlo Control", it usually means a very specific subset of methods within RL, to most readers.</p>
  
  <blockquote>
    <p>So, couldn't -learning also be considered a MC method? </p>
  </blockquote>
  
  <p>In the <em>general</em> sense perhaps. The argument is perhaps stronger for it if the environment is being simulated on a computer for the agent to learn from.</p>
  
  <p>However, if you start to unilaterally call Q-learning a MC method, you are probably going to just confuse people who have learned the conventions in RL.</p>
  
  <blockquote>
    <p>Can an MC method be model-based?</p>
  </blockquote>
  
  <p>In general, yes, because the model can be sampled for planning, and a policy can also be separately sampled - so it is possible to run an MC method with or without a model - depending on whether you sample from the model taking "virtual actions" (for e.g. planning or refining your agent) or from the environment taking real actions. Many RL techniques blur the line between online learning and planning. For instance, using a simulated environment or historical data can be framed as planning for the real environment.</p>
  
  <p>Monte Carlo Tree Search is an example of a model-based technique using the term "Monte Carlo" within RL frameworks. It is used famously within DeepMind's AlphaZero in order to refine a policy and value estimates during self-play.</p>
  
  <blockquote>
    <p>What is the relation between Monte Carlo and [other] model-free algorithms?</p>
  </blockquote>
  
  <p>In the context of RL, Monte Carlo is presented as one way to estimate expected <em>utility</em> (or <em>return</em>) - by sampling from the environment and policy until the a complete trajectory is available:</p>
  
  <p><span class="math-container">$$v_{\pi}(s) = \mathbb{E}_{\pi}[\sum_{k=0}^{T-t} \gamma^k R_{t+1+k} | S_t = s ]$$</span></p>
  
  <p>MC is contrasted with Temporal Difference (TD) approaches, such as Q-learning, which sample <em>bootstrap</em> estimates using the Bellman Equation:</p>
  
  <p><span class="math-container">$$v_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s ]$$</span></p>
  
  <p>The two approaches can be combined in various ways, including TD(<span class="math-container">$\lambda$</span>) methods. With  TD(<span class="math-container">$\lambda$</span>), if you set <span class="math-container">$\lambda = 0$</span> then the algorithm is identical to single-step TD learning, and if you set <span class="math-container">$\lambda = 1$</span> then it is very similar to a Monte Carlo method. Often setting it to some intermediate value is more efficient than either extreme.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T17:29:35.310Z
Answers.Text: Can you clarify these points "because the model can be sampled for planning, and a policy can also be separately sampled"? Are you saying that using a MC method we can build a model which we use for planning?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T17:43:44.167Z
Answers.Text: @nbro: Well, you could yes, same as Dyna-Q does it for example - just store transition history that you observed and sample from it. Someone is bound to have done that at some point, but typically those learned models are not very robust or useful in RL, so it's not a mainstream approach. More usually model-based means you have some other access to a model via a simulation or the game engine for a board game etc
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T18:35:16.733Z
Answers.Text: You are saying that every MC method that uses e.g. a simulation to gain experiences in the form of returns is a model-based algorithm because the simulation itself is a model? Isn't this a little bit of a stretch? Model-based should refer to an algorithm that uses the transition function (or reward function): e.g. value iteration is model-based because it uses the transition function $p$. The simulation only provides a way of experiencing (sampling) the world.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T18:38:00.363Z
Answers.Text: @nbro: No I am not saying that. I am saying that you can often use an existing simulation as a model for model-based learners. All you usually need added to the API is a way to place it into a specific state, and then you have a sampling model (as opposed to a distribution model). Sampling models are adequate for planning, such as MCTS
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T18:39:43.887Z
Answers.Text: Ok, but what difference does it make if we use a simulation or not, in terms of being model-free, in this context? Why did you mention it then?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T18:41:00.647Z
Answers.Text: @nbro: Because if you have a simulation available, you usually have a sampling model available for little or no additional effort. Look-ahead planning using a sampling model is essentially what MCTS is.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-13T17:19:56.667Z
Answers.LastActivityDate: 2019-05-13T18:10:49.223Z
Answers.LastEditDate: 2019-05-13T18:10:49.223Z
Answers.UserDisplayName: Neil Slater
Body: <p>Monte Carlo (MC) methods are methods that use some form of randomness or sampling. For example, we can use an MC method to approximate the area of a circle inside a square: we generate random 2D points inside the square and count the number of points inside and outside the circle. </p>
  
  <p>In reinforcement learning, an MC method is a method that "samples" experience (in the form of "returns") from the environment, in order to approximate e.g. a value function. </p>
  
  <p>A temporal-difference algorithm, like <span class="math-container">$Q$</span>-learning, also performs some form of sampling: it chooses an action using a stochastic policy (e.g. <span class="math-container">$\epsilon$</span>-greedy) and observes a reward and the next state.  So, couldn't <span class="math-container">$Q$</span>-learning also be considered a MC method? Can an MC method be model-based?</p>
  
Tags: <reinforcement-learning><monte-carlo-methods><temporal-difference-methods><comparison><model-free-methods>
Title: What is the relation between Monte Carlo and model-free algorithms?
UserDisplayName: nbro
ThreadText: # What is the relation between Monte Carlo and model-free algorithms?
  
  (Asked by: username_0 on 2019-05-13)
  
  Monte Carlo (MC) methods are methods that use some form of randomness or sampling. For example, we can use an MC method to approximate the area of a circle inside a square: we generate random 2D points inside the square and count the number of points inside and outside the circle.
  
  In reinforcement learning, an MC method is a method that "samples" experience (in the form of "returns") from the environment, in order to approximate e.g. a value function.
  
  A temporal-difference algorithm, like $Q$-learning, also performs some form of sampling: it chooses an action using a stochastic policy (e.g. $\epsilon$-greedy) and observes a reward and the next state. So, couldn't $Q$-learning also be considered a MC method? Can an MC method be model-based?
  
  **Tags:** reinforcement-learning, monte-carlo-methods, temporal-difference-methods, comparison, model-free-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-13. Score: 3
  
  In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things.
  
  The more general use of "Monte Carlo" is for simulation methods that use random numbers to sample - often as a replacement for an otherwise difficult analysis or exhaustive search.
  
  In RL, Monte Carlo methods are generally taken to be non-bootstrapping sample-based approaches to estimating returns. This is a labelling convention within RL - probably because someone called an initial model-free learner a "Monte Carlo method", and the name stuck whilst many refinements and new ideas have since been published under different names.
  
  The historical use of the term is important, since if you mention you are using "Monte Carlo Control", it usually means a very specific subset of methods within RL, to most readers.
  
  > So, couldn't -learning also be considered a MC method?
  
  In the *general* sense perhaps. The argument is perhaps stronger for it if the environment is being simulated on a computer for the agent to learn from.
  
  However, if you start to unilaterally call Q-learning a MC method, you are probably going to just confuse people who have learned the conventions in RL.
  
  > Can an MC method be model-based?
  
  In general, yes, because the model can be sampled for planning, and a policy can also be separately sampled - so it is possible to run an MC method with or without a model - depending on whether you sample from the model taking "virtual actions" (for e.g. planning or refining your agent) or from the environment taking real actions. Many RL techniques blur the line between online learning and planning. For instance, using a simulated environment or historical data can be framed as planning for the real environment.
  
  Monte Carlo Tree Search is an example of a model-based technique using the term "Monte Carlo" within RL frameworks. It is used famously within DeepMind's AlphaZero in order to refine a policy and value estimates during self-play.
  
  > What is the relation between Monte Carlo and [other] model-free algorithms?
  
  In the context of RL, Monte Carlo is presented as one way to estimate expected *utility* (or *return*) - by sampling from the environment and policy until the a complete trajectory is available:
  
  $$v\_{\pi}(s) = \mathbb{E}\_{\pi}[\sum\_{k=0}^{T-t} \gamma^k R\_{t+1+k} | S\_t = s ]$$
  
  MC is contrasted with Temporal Difference (TD) approaches, such as Q-learning, which sample *bootstrap* estimates using the Bellman Equation:
  
  $$v\_{\pi}(s) = \mathbb{E}\_{\pi}[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t = s ]$$
  
  The two approaches can be combined in various ways, including TD($\lambda$) methods. With TD($\lambda$), if you set $\lambda = 0$ then the algorithm is identical to single-step TD learning, and if you set $\lambda = 1$ then it is very similar to a Monte Carlo method. Often setting it to some intermediate value is more efficient than either extreme.
  
  > **Comments:**
  > **username_0**: Can you clarify these points "because the model can be sampled for planning, and a policy can also be separately sampled"? Are you saying that using a MC method we can build a model which we use for planning?  
  > **username_1**: @username_0: Well, you could yes, same as Dyna-Q does it for example - just store transition history that you observed and sample from it. Someone is bound to have done that at some point, but typically those learned models are not very robust or useful in RL, so it's not a mainstream approach. More usually model-based means you have some other access to a model via a simulation or the game engine for a board game etc  
  > **username_0**: You are saying that every MC method that uses e.g. a simulation to gain experiences in the form of returns is a model-based algorithm because the simulation itself is a model? Isn't this a little bit of a stretch? Model-based should refer to an algorithm that uses the transition function (or reward function): e.g. value iteration is model-based because it uses the transition function $p$. The simulation only provides a way of experiencing (sampling) the world.  
  > **username_1**: @username_0: No I am not saying that. I am saying that you can often use an existing simulation as a model for model-based learners. All you usually need added to the API is a way to place it into a specific state, and then you have a sampling model (as opposed to a distribution model). Sampling models are adequate for planning, such as MCTS  
  > **username_0**: Ok, but what difference does it make if we use a simulation or not, in terms of being model-free, in this context? Why did you mention it then?  
  > **username_1**: @username_0: Because if you have a simulation available, you usually have a sampling model available for little or no additional effort. Look-ahead planning using a sampling model is essentially what MCTS is.  
  
  ---
  
  