Understanding On-policy First Visit Monte Carlo Control algorithm

Question

I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to estimate the optimal policy in Reinforcement Learning.

I am having troubles understanding the step in blue of the algorithm. Is the pair St, At NEVER supposed to appears in the given set of states ? In this case, the following pseudo-code will never get realized ? What is the specific case where St, At appears in the set of Action-States ?

Please feel free to ask more details if my question isn't clear enough.

The algorithm is taken from the reinforcement learning book written by R.Sutton and A. Barto.

Answer 1

The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S_t, A_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S_t, A_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a trajectory.

This condition:

• Is always trivially satisfied for the pair $(S_0, A_0)$ (it's the beginning of the trajectory, so we can't possible have observed that state-action pair before)
• Is satisfied at time $t = 1$ if and only if $(S_1, A_1) \neq (S_0, A_0)$ (so at least one of the state or the action must be different from the preceding ones)
• Is satisfied at time $t = 2$ if and only if $(S_2, A_2) \neq (S_1, A_1)$ AND $(S_2, A_2) \neq (S_0, A_0)$.
• etc.