10
$\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$
8
$\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 & Bart.

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$
  • $\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 Mar 27 '18 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$ – Neil Slater Mar 27 '18 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 Mar 27 '18 at 9:16
-1
$\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$
  • $\begingroup$ I don't think this is correct or, at least, obvious to see. The Markov property, in the context of RL, is associated with the states. Can you please clarify why MC algorithms would work better when the Markov property would not be satisfied? $\endgroup$ – nbro Feb 22 at 16:30
  • $\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 Feb 23 at 0:04
  • $\begingroup$ "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", it will be the same if the environment is deterministic. What does this have to do with the Markov property? I don't get your claims. Where did you read that TD will be more inefficient than MC in e.g. POMDPs? $\endgroup$ – nbro Feb 23 at 10:46
  • $\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 Feb 23 at 14:55
  • $\begingroup$ "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". No. This is only true if the environment is deterministic. The environment can also be stochastic. "that will always be the case in a markov environment", No, this is an orthogonal issue to the Markov property. $\endgroup$ – nbro Feb 23 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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