2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Commented May 13, 2019 at 17:29
  • $\begingroup$ @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 $\endgroup$
    – Neil Slater
    Commented May 13, 2019 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented May 13, 2019 at 18:35
  • $\begingroup$ @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 $\endgroup$
    – Neil Slater
    Commented May 13, 2019 at 18:38
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Commented May 13, 2019 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .