2
$\begingroup$

Sutton-Barto page 111, first paragraph (Off-policy Monte Carlo Control):

A potential problem is that this method learns only from the tails of episodes, when all of the remaining actions in the episode are greedy. If nongreedy actions are common, then learning will be slow, particularly for states appearing in the early portions of long episodes.

Could someone please explain clearly the above paragraph?

$\endgroup$

1 Answer 1

2
$\begingroup$

From the same page's pseudocode for off-policy Monte Carlo Control for estimating the optimal target policy, in the nested inner loop you have:

If $A_t \neq \pi(S_t)$ then exit inner Loop (proceed to next episode), otherwise scale importance sampling ratio $W$ by $\frac{1}{b(A_t|S_t)}$.

Therefore here samples collected towards the end of episodes where the importance sampling ratio is large, contribute more to the estimation of the expected returns of the target policy. These high-weight samples dominate the update process especially if the behavior policy is more exploratory where $b(A_t|S_t)$ is very small, leading to learning primarily from the tails of episodes in the sense of return/value updates with greedy actions.

If nongreedy exploratory actions are common in the early portions of long episodes, the said inner loop would always exit before these early non-greedy actions, causing no feedback or learning about their credit assignment. For instance, if an agent went for a suboptimal long route in a large maze caused by early non-greedy actions, there's no learning to correct this due to the above demonstrated tail learning only nature. The optimal route learning would be very slow on average until some episodes happen to enter the optimal route by the behavior policy's early non-greedy actions.

$\endgroup$
0

You must log in to answer this question.

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