0
$\begingroup$

In Sutton's textbook (Chapter 5) it says "To ensure that well-defined returns are available, here we define Monte Carlo methods only for episodic tasks". Can someone explain what exactly breaks down for non-episodic tasks for Monte Carlo methods in Reinforcement Learning?

$\endgroup$
2
  • $\begingroup$ Thank you for posting your first question here. Any chance you can edit your post and provide context for this problem, what you know so far, and where explicitly you are stuck? $\endgroup$
    – shepan6
    Jul 16, 2020 at 13:00
  • $\begingroup$ Not sure I understand your request. First sentence in my post provides context (MC, Sutton's textbook). Second sentence states the problem: the necessity of the assumption made in the book. $\endgroup$
    – user100842
    Jul 16, 2020 at 13:10

1 Answer 1

1
$\begingroup$

Can someone explain what exactly breaks down for non-episodic tasks for Monte Carlo methods in Reinforcement Learning?

It is this first part of the sentence that you quote:

"To ensure that well-defined returns are available..."

In more detail, the return distribution in an episodic MDP can be defined as

$$G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$$

where $R_x$ is reward distribution at time step $x$, $\gamma$ is discount factor, and $T$ is the last time step of the episode.

From this you can see that you will need to collect all of $r_{t+1}$ to $r_T$ for an episode in order to calculate a single concrete return value $g_t$. You can only collect $r_T$ at the end of an episode.

In non-episodic tasks, there is no terminal time step $T$, and the return definition becomes:

$$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

This cannot be resolved directly by collecting data for infinite time steps. Or in other words you can never sample an actual return value as it is defined. To get around this you could do one or more of the following:

  • You could use an artifical time horizon $h$, and define $T = t + h$. This will result in a biased sample. However, you can make the bias arbitrarily small relative to total return by making $h$ large. If you are using a discount factor, that may allow for smaller value of $h$.

  • You could use temporal difference (TD) learning to bootstrap return estimates without needing a full sample of return. This will result in a biased sample, but the bias due to bootstrapping should reduce as more samples are collected.

  • You could use TD with eligibilty traces and a high trace decay parameter $\lambda = 1$, which is a way of getting very similar learning behaviour to Monte Carlo, but still allowing learning to occur on each step in a continuing problem.

These options technically stop the approach being true Monte Carlo. The last two are described in the book under TD methods.

$\endgroup$
2
  • $\begingroup$ Thank you! But I find the wording "To ensure that well-defined returns are available" misleading suggesting possibility of infinite returns, diverging series, etc. From what you described it looks more like "For MC to make sense" because one cannot really have an infinitely long sample. Would you agree? $\endgroup$
    – user100842
    Jul 16, 2020 at 12:52
  • $\begingroup$ @user100842: The phrase is explaining why they are reducing scope of MDPs covered in following text. It is semi-formal, and includes a hint of the formal reason, whilst your suggested phrasing is more informal. Otherwise the two phrasings are pretty much equivalent in my opinion. $\endgroup$ Jul 16, 2020 at 14:12

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.