# in reinforcement learning off policy mc may not work

I noticed off-policy mc prediction(or control) will not work, as being descripted by boxed algorithm in page 110 of the book "reinforcement learning an introduction".

1. The weight W should before C's(and Q(St, At)'s) update, because any Gt (including at the last time T-1) should be reweighted by π(At|St)/b(At|St).

2. Any non-greedy action generated by behavior policy will cause the weight to zero, as descripted too in the book. So actually, the Q(St, At) for the non-greedy action will always be undefined for weighted importance sampling (0/0*Gt) or just zero for ordinary importance sampling (0/N*Gt).

So in general off-policy mc will not work for target policy being greedy !?

Your observation would be valid for any deterministic target policy (where all actions but one have a 0 probability of occurrence), not just the greedy policy.

For such target policies, the only cases where the importance-sampled return will be non-zero is when the behavior policy follows a trajectory that exactly matches one that the target policy would follow. The probability of following such a trajectory is non-zero if all actions possible under target policy have non-zero probability of occurrence in behavior policy. However for longer trajectories the probabilities of choosing the correct action at each step will multiply to result in an extremely small probability of following the target policy trajectory completely. Hence most of the returns observed will be 0.

Say your behavior policy is $$\epsilon$$-greedy. Now when you do follow the "correct" trajectory, the importance sampling weight will be $$1/(1-\epsilon + \epsilon/n)$$ when the greedy action as per your current value estimates is the correct action (same as target policy's choice), or $$n/\epsilon$$ when its not. These weights are quite large, and will be multiplied for each step.

So we have 0 returns when you don't follow the same trajectory as target policy, and very large returns when you do. And these values are such that the average is guaranteed to converge to the true value. This is a good example of a low bias, high variance estimate.

Refer to this lecture snippet on off-policy MC by Hado van Hasselt of DeepMind. This lecture series is a very good resource for RL in general.

Since we're calculating $$q_\pi(S_t | A_t)$$, $$A_t$$ doesn't depend on $$\pi$$'s policy and thus shouldn't depend on $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}$$.

I'd been just as confused when I initially read the algorithm, but finally realized that $$q_\pi(s, a)$$ is the value of taking action a in state s and then following policy $$\pi$$. So, $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}$$ would be needed when estimating $$v_\pi(s_t)$$, but not when estimating $$q_\pi(s_t, a_t)$$.

Any non-greedy action generated by behavior policy will cause the weight to zero, as descripted too in the book

This is correct. The book also explains that this will tend to make learning slower for long trajectories - states and actions near the ends of episodes will tend to be estimated better.

So in general off-policy mc will not work for target policy being greedy !?

It will work, and is still guaranteed to converge to arbitrary accuracy measuring true value functions, provided the behaviour policy covers the target policy - i.e. all actions possible under target policy must have non-zero probability of occurring in behaviour policy.

However, convergence can be very slow for states only seen at the beginning of long trajectories, where there is a high chance of exploratory actions afterwards. Basically you have to rely on the chance of a long enough behaviour policy trajectory starting from whichever state, action pair that you want to improve estimate on - that it takes no actions with zero chance under target policy between those state/action starting points and the end of the episode.

In the limit of infinite samples, this is guaranteed to happen enough times to get an accurate estimate. It is not a theoretical problem, just a practical one of having enough time/CPU resources to run enough trials.

A low exploration parameter can help with longer trajectories, but it is a balancing act between slow updates due to low exploration or due to zeroed returns due to importance sampling when there is exploration.

This is a weakness of basic Monte Carlo off-policy control, and explained as such in the book. However, it is important to note that the method has proven guarantees of convergence. It works in that sense.

• than you for your reply! Can you be more specific? In the book, V(s)=sum(ρ*Gt)/N and ρ=product(π(Ak|Sk)/b(Ak|Sk)) k=t...T-1, then any Gt with non-greedy action will multiplied by ρ = 0 (because of k==t term) which yields 0. Commented Mar 1, 2019 at 9:44
• @mxmxlwlw I'm not sure there is anything more to add. Some $G_t$ will be zero, some will not, depending on what actions were taken. That's all there is to it. The ones for which $G_t$ is zero will not learn from that episode from before whichever $t+n$ took the last exploratory step (not in the target policy). But you run many episodes, so you still get results, even for $G_0$, just less often. Commented Mar 1, 2019 at 9:52