0
$\begingroup$

Could please some expert on reinforcement learning explain the red-box part in the following off-policy MC control? I mean I did not understand what (and why) is done in the step shown as a red-box. I understood all points, except the red box part: why do we need the line "$A_t \neq \pi(S_t)$ then exit inner loop"? More specifically, why don't we not exit the inner loop when $A_t= \pi(S_t)$?

enter image description here

$\endgroup$
7
  • $\begingroup$ @ Neil Slater, thank you. The question was updated. $\endgroup$ Feb 2 at 17:35
  • $\begingroup$ @ Neil Slater, that code was wrong (I took from some lecture notes) and that was why I needed to put the correct one and asked you do update your answer. $\endgroup$ Feb 2 at 18:01
  • $\begingroup$ @ Neil Slater, tomorrow is fine. I wanted to put correct pseudocode so that other people can make use of your answer. Thank you. $\endgroup$ Feb 2 at 18:06
  • 1
    $\begingroup$ I suppose to more explicitly get at what is probably the primary point of confusion you could add something like: "Why can we not continue using the remainder of experience generated within this episode for lower time steps $t$?" (assuming that that is indeed what you're thinking) $\endgroup$
    – Dennis Soemers
    Feb 2 at 20:19
  • 1
    $\begingroup$ @user3489173 That sort of comment is uncalled for so I'm deleting it. If you have an issue with moderator actions you can post about it on ai.meta.stackexchange.com. Such personal attacks should definitely be left out of it though. $\endgroup$
    – Dennis Soemers
    Feb 2 at 20:35

1 Answer 1

1
$\begingroup$

why do we need the line "𝐴𝑡!=𝜋(𝑆𝑡) then exit inner loop"?

To understand this, you need to go back to the importance sampling ratio:

$$\rho_{t:t+n} = \prod_{k=1}^n \frac{\pi(A_{t+k}|S_{t+k})}{b(A_{t+k}|S_{t+k})}$$

NB Here I am using the more general stochastic form for the target policy $\pi(a|s): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} = \mathbf{Pr}\{A_t = a | S_t = s \}$. Whilst the pseudocode uses $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$. You have to convert between them to see how the weighting factor is really working.

The weighting factor $W$ in the pseudocode is in fact $\rho_{t:T-1}$, calculated step by step working backwards through the trajectory so that it can be used to weight the return from timestep $t$ for each $(s_t, a_t)$ pair.

An important detail is that if any of the $\pi(A_{t+k}|S_{t+k}) = 0$ within an episode, then $\rho_{t:T-1} = 0$ also, and this must then be true for all other timesteps before $t$.

The line:

$W \leftarrow W \frac{1}{b(A_t|S_t)}$

assumes that $\pi(A_{t}|S_{t}) = 1$. This is true for the greedy policy if, and only if $A_t$ is the current greedy choice. As the code uses notation for deterministic policy, then that is the same as saying $\pi(S_{t}) = A_t$ from the pseudocode.

So, when $A_t \neq \pi(S_t)$, $W$ should be set to $0$, and this will logically make $W = 0$ throughout the rest of the loop, and there will be no updates to any Q values.

Exiting the loop when $A_t \neq \pi(S_t)$ saves you from adjusting $W = 0$ in the next line conditionally, then following through with calculating all the useless $0$ updates for earlier time steps.

Or another way to put it: With the $W$ update of $W \leftarrow W \frac{1}{b(A_t|S_t)}$, the loop may continue backwards to estimate expected returns from earlier timesteps only if the agent chose a non-exploring action compared to the current target policy. If an exploring action was taken, then the $W$ update from the pseudocode would be wrong. Not only would it be wrong, but determining the correct value - $W = 0$ - would result in no changes to any estimates for the rest of the loop. Easier just to terminate the loop at that point.

This is why off-policy Monte Carlo control is said to "only learn from the tails of episodes". If the agent explored a new action, that is learned from, but only from the point after it took the last exploring action to the end of the episode. Earlier exploring actions are also learned from indirectly, as they can put the agent in a different state that may not be reachable by the current target policy, and may turn out to be interesting.

$\endgroup$
3
  • $\begingroup$ @ Neil Slater, the point I was asking was this: why do we need to check $A_t \neq \pi(S_t)$? $\endgroup$ Feb 2 at 17:53
  • $\begingroup$ @ Neil Slater, I changed the question photo with pseudocode from SB's book. Could you please update your answer based on this new photo? I think the updated answer will be okay for me. $\endgroup$ Feb 2 at 17:59
  • $\begingroup$ @ Neil Slatter. Thank you so much. You are TOTALLY an expert on RL! $\endgroup$ Feb 3 at 18:18

You must log in to answer this question.

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