8
$\begingroup$

I was reading through section 5.7 of the second edition of Sutton and Barto's "Reinforcement Learning: An Introduction" when I came across this passage:

A Pretty Perplexing Passage

where the "method" that the author is referring to is the incremental, every-visit implementation for Off-Policy MC Control with weighted importance sampling covered earlier in the section and provided here for reference:

Off-Policy MC Control

My question is this: why does the method above only learn from the tails of the episode, as the author suggests in the excerpt?

After searching around a bit, the only relevant link I could find online was here:

http://incompleteideas.net/sutton/book/first/5/node7.html

which is an online version of the first edition of the text. An excerpt from this link clarifies that what the author means by "the tails of episodes" is in fact "after the last nongreedy action." However, I still fail to see why all of the remaining actions after some point in an episode are guaranteed to be greedy, or how these greedy actions belong to the only time steps from which the above method can learn.

$\endgroup$

3 Answers 3

8
$\begingroup$

I still fail to see why all of the remaining actions after some point in an episode are guaranteed to be greedy,

It is not the case, there is no guarantee of any number of steps being greedy. The very last step can be non-greedy. In that case, then the only return that will get assessed in off-policy Monte Carlo control is for $S_{T-1}, A_{T-1}$. That step does get processed (and in general the last exploratory step in any trajectory), because you don't apply importance sampling to the action in the $Q(s,a)$ that is being updated.

In general, there will be a number of steps prior to the end of the episode where the behaviour policy took an action that was valid in the target policy. The number will be anything from 0 to the length of the entire episode. Distribution of this number depends on the overlap between behaviour policy and target policy. An $\epsilon$-greedy behaviour policy learning a greedy target policy may have relatively long series where the actions are greedy, depending on value of $\epsilon$.

or how these greedy actions belong to the only time steps from which the above method can learn

This is due to weighted importance sampling. The importance sampling ratio, applied on each time step with target policy $\pi$ and behaviour policy $b$ is:

$$\frac{\pi(a|s)}{b(a|s)}$$

If the target policy is the greedy policy over current $Q(s,a)$ (which it is in the given Monte Carlo Control algorithm), then any exploration will insert a multiplication by 0 into the importance sampling ratio (because $\pi(a|s)=0$ for exploring actions), making the adjusted return estimate zero regardless of any other values. In addition, the weighting when taking the mean also uses this factor, so there will be no change to any $(s,a)$ pair with a later exploratory action.

If you used non-weighted importance sampling, then in theory you do need to add these zeros into the mean Q estimates, because the denominator for the average return is the number of visits to each $(s,a)$. This adding of zeroes counters the over-estimates made when the trajectory from that point on is greedy (and multiplied by a factor of $\frac{1}{(1-\epsilon + \frac{\epsilon}{|\mathcal{A}|})^{T-t-1}}$ for example if you are using $\epsilon$-greedy).

In a sense then it is Monte Carlo Control with weighted importance sampling which has this limitation (of only learning from tails of episodes). However, un-weighted importance sampling is not learning much, it is just learning a correction to its over-estimates elsewhere. And in general weighted importance sampling is preferred due to lower variance.

$\endgroup$
7
  • $\begingroup$ If the number of steps prior to the end of the episode where the behavior policy is greedy can be 0, then why does the algorithm in my question always update the estimate $Q(S_{T - 1}, A_{T - 1})$, regardless of whether or not $A_{T - 1}$ was greedy? Note that this is indeed the case because the "If $A_t \neq \pi(S_t)$ then exit For loop" line only occurs after the first update to an action value estimate for that episode. $\endgroup$
    – Jack
    Jul 20, 2018 at 16:12
  • 1
    $\begingroup$ @Jack: I already explained that in the answer (first paragraph).You always update for a single step because the importance sampling does not apply to the $a$ in the $Q(s,a)$ being updated. The value of $Q(s,a)$ is already conditional on $a$ being chosen, so you are not concerned about the probability of it happening. $\endgroup$ Jul 20, 2018 at 18:00
  • $\begingroup$ Neil thank you for the detailed answer. I implemented this algorithm to solve an exercise in the same book (ex 5.12, a 'vector race') but learning is very slow. I am monitoring the changes in preferred action from random to 'optimal' after 10⁶ episodes and only about 10-15 of the later actions change. It only learns from the tails and very slowly indeed. Is this common? $\endgroup$ Feb 26, 2020 at 21:30
  • $\begingroup$ @FranciscoGrings: Results will vary considerably according to the problem. I cannot say if it is common to need a million episodes using off-policy monte carlo control on the corner race problem. You could compare your solution to others e.g. github.com/hansweytjens/… $\endgroup$ Feb 27, 2020 at 6:09
  • $\begingroup$ Neil! Thank you for the feedback! The code is also slow but by examining the example you posted I found a fundamental different with my approach: I did not included the velocities as part of the state, but as constraints in the possible actions (in my approach I did not allow actions that lead me to imposible velocity states). I believe that both approaches are not equivalent. $\endgroup$ Feb 27, 2020 at 21:20
0
$\begingroup$

short

Lets say you recorded the following episode:

$$s_1, a_1^o, r_1,\quad s_2, a_2^o, r_2,\quad s_3, a_3^o, r_3,\quad s_4, a_4^p, r_4,\quad s_5, a_5^p, r_5,\quad s_6, a_6^p, r_6 $$

$a^o$ is an off-policy or non-greedy action and $a^p$ is the best action according to the current policy (greedy action).

  • If you learn from $a^p_4$, you improve your model for $Q(s, a^p)$ concerning actions according to the current policy.
  • If you learn from $a^o_3$ you improve you model for $Q(s, a^o)$. This is the understanding of what happens if you choose an off-policy action. Most likely the rest score $r_3 + r_4 + r_5 + r_6$ will be lower. But in a few cases not - this is when you learn a new tactics.
  • If you learn from $a^o_1$, you will most likely have a very low rest-score, as $r_1$, $r_2$ and $r_3$ are on average lower then if acting according to the current policy. For this reason, your learning will just confirm the current policy. Even if $a_1^o$ was a brilliant action, probably $a_2^o$ and $a_3^o$ were not and $\sum\limits_{t \geq 1} r_t$ is smaller compared to a purely greedy episode. Hence, the algorithm can not see the brilliance of what he tried at $t=1$.

detailed explanation

Your algorithm relies on two ingredients to find the optimal $Q(s,a)$, i.e. $Q^*(s,a)$:

  1. A good estimate of the final score based on the current policy $\pi$
  2. A good estimate of what would happen in a state $s$, when the next action would be off-policy and all / most further steps would be on-policy.

Ingredient 2 ensures, that new actions are tried, which eventually improves the current policy. This is the reason you use non-greedy actions. Otherwise, $Q(s, a)$ would only give you great predictions if $a$ is an action according to the current policy ($a=\pi(s)$) and horrible predictions for all other possible actions ($a\in A \backslash \{\pi(s)\}$). This corresponds to learning from the tail of an episode.

But this is not to be confused with learning from sequences of random actions!

Your algorithm learns backwards, i.e. starting with the last rewards and propagating this information step-wise forward to earlier times. If you try to learn from a state $s_{t=7}$ and a lot of off-policy actions follow later at $t \gt 7$, then the corresponding Q-value will be very low, as (most likely) you did a lot of unfavorable actions. Hence, the learning of your algorithms will be: I stick to my (non-optimal) policy for all early stages of the game. For the reason you do not (or just slowly) learn from early portions of the game if non-greedy actions are common.

$\endgroup$
0
$\begingroup$

Actually, the answer to your first question (why does this method learn only from the tails of episodes?) is due to the second to last line.

The if statement basically says that the method will learn from a state-action pairs in an episode only if the action is near-greedy, otherwise $A_t$ likely would not equal $\pi(S_t)$.

$\endgroup$

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.