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.


1 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.