25
$\begingroup$

I've been doing a lot of research about Reinforcement Learning lately. I followed Sutton & Barto's Reinforcement Learning: An Introduction for most of this.

I know what Markov Decision Processes are and how Dynamic Programming (DP), Monte Carlo and Temporal Difference (DP) learning can be used to solve them. The problem I'm having is that I don't see when Monte Carlo would be the better option over TD-learning.

The main difference between them is that TD-learning uses bootstrapping to approximate the action-value function and Monte Carlo uses an average to accomplish this. I just can't really think of a scenario when this is the better way to go.

My guess is that it might have something to do with performance but I can't find any sources that can proof this.

Am I missing something or is TD-learning generally the better option?

$\endgroup$

2 Answers 2

31
$\begingroup$

The main problem with TD learning and DP is that their step updates are biased on the initial conditions of the learning parameters. The bootstrapping process typically updates a function or lookup Q(s,a) on a successor value Q(s',a') using whatever the current estimates are in the latter. Clearly at the very start of learning these estimates contain no information from any real rewards or state transitions.

If learning works as intended, then the bias will reduce asymptotically over multiple iterations. However, the bias can cause significant problems, especially for off-policy methods (e.g. Q Learning) and when using function approximators. That combination is so likely to fail to converge that it is called the deadly triad in Sutton & Barto.

Monte Carlo control methods do not suffer from this bias, as each update is made using a true sample of what Q(s,a) should be. However, Monte Carlo methods can suffer from high variance, which means more samples are required to achieve the same degree of learning compared to TD.

In practice, TD learning appears to learn more efficiently if the problems with the deadly triad can be overcome. Recent results using experience replay and staged "frozen" copies of estimators provide work-arounds that address problems - e.g. that is how DQN learner for Atari games was built.

There is also a middle ground between TD and Monte Carlo. It is possible to construct a generalised method that combines trajectories of different lengths - from single-step TD to complete episode runs in Monte Carlo - and combine them. The most common variant of this is TD($\lambda$) learning, where $\lambda$ is a parameter from $0$ (effectively single-step TD learning) to $1$ (effectively Monte Carlo learning, but with a nice feature that it can be used in continuous problems). Typically, a value between $0$ and $1$ makes the most efficient learning agent - although like many hyperparameters, the best value to use depends on the problem.

If you are using a value-based method (as opposed to a policy-based one), then TD learning is generally used more in practice, or a TD/MC combination method such as TD(λ) can be even better.

In terms of "practical advantage" for MC? Monte Carlo learning is conceptually simple, robust and easy to implement, albeit often slower than TD. I would generally not use it for a learning controller engine (unless in a hurry to implement something for a simple environment), but I would seriously consider it for policy evaluation in order to compare multiple agents for instance - that is due to it being an unbiased measure, which is important for testing.

$\endgroup$
3
  • $\begingroup$ First off, thanks for the answer. I see how in theorie an unbiased algorithm could be preferred over a biased one. But considering the high variance Monte Carlo can give at the start of training, I don't see how this really matters. Both Monte Carlo and TD will start with inaccurate approximations and from what I've read, TD will converge much faster. I just can't really come up with a practical advantage of using Monte Carlo. (Amusing the deadly triad can be avoided) $\endgroup$
    – Anne-dirk
    Commented Mar 27, 2018 at 8:10
  • 1
    $\begingroup$ @Anne-dirk If you are using a value-based method (as opposed to a policy-based one), then TD learning is generally used more in practice, or a TD/MC combination method such as TD(λ) can be even better. I am not sure what you mean by "practical advantage"? Monte Carlo learning is conceptually simple, robust and easy to implement. I would generally not use it for a learning controller engine (unless in a hurry to implement something for a simple environment), but I would seriously consider it for policy evaluation in order to compare multiple agents for instance. $\endgroup$ Commented Mar 27, 2018 at 8:53
  • $\begingroup$ @Neul Slater Aaaah I see... That's the kind of answer I was looking for :) Thanks for your help! $\endgroup$
    – Anne-dirk
    Commented Mar 27, 2018 at 9:16
2
$\begingroup$

Essentially it depends on your environment.

TD exploits the Markov property, i.e. the future states of a process rely only upon the current state, and therefore it's usually more efficient to use TD in Markov environments.

MC does not exploit the Markov property as it bases rewards on the entire learning process, which lends itself to non-Markov environments.

$\endgroup$
8
  • $\begingroup$ To be clear, I was referring to efficiency. If you can exploit the Markov property then TD is advantageous because you can start in any given state, take and action and the result will always be the same, so you can compute the TD error with high levels of certainty. With non-MDP if you get a state that is partially observed then TD may not be very efficient. That's not to say you can't use TD in non-MDPs, you can, but it might be inefficient and may get better success with TD lambda rather than TD(1). $\endgroup$
    – BigBadMe
    Commented Feb 23, 2019 at 0:04
  • $\begingroup$ It literally has everything to do with it being Markov; if you're in a Markov environment then once you establish taking action a in state a it will lead will state a' with reward x - that will always be the case in a markov environment, so you don't need to evaluate it over and over - you can take bigger steps and TD enables you to exploit that. But it won't be the case in a POMDP because you can have exactly the same state, take same action, but end up in completely different states and rewards. $\endgroup$
    – BigBadMe
    Commented Feb 23, 2019 at 14:55
  • $\begingroup$ Yes! MDPs are deterministic by definition. POMDPs are stochastic, that's exactly what I've been saying. A MDP is not stochastic - it literally cannot be deterministic and stochastic. But look, if you want to take it up with David Silver, feel free to do so: youtu.be/PnHCvfgC_ZA?t=3811 Burn! $\endgroup$
    – BigBadMe
    Commented Feb 23, 2019 at 15:18
  • $\begingroup$ Oh look, the baby has marked down my answer because he was shown to be wrong. Pathetic. I didn't say MC methods don't work in Markov environments! I was saying efficiency gains can be found by using the correct approach depending on the environment. See, you're now even needing to make things up, and you're coming across as quite pedantic now. $\endgroup$
    – BigBadMe
    Commented Feb 23, 2019 at 15:53
  • $\begingroup$ And no, an MDP is not "just a way of representing the environment and its dynamics", it literally means that if you are state S then all events that occurred before are defined by that state, and if you take action a, then you will always get the same State S' and reward r. That is literally the definition of an MPD, and why it is deterministic. That's why a MDP can be guaranteed to converge to an optimal policy. I get the impression you don't know what you're talking about. $\endgroup$
    – BigBadMe
    Commented Feb 23, 2019 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.