1
$\begingroup$

I'm really confused about understanding the Monte Carlo first visit algorithm as presented in the Sutton & Barto's book in chapter V. Here is the pseudocode:

enter image description here

The reason is that I'm trying to implement the same algorithm for the game "Blackjack" of OpenAI (Gymnasium). It is for learning purposes, so I'm trying to implement the algorithm from scratch in order to understand the concept of MC behind it. Sadly, after looking different videos and spending many days learning from the book, I have to admit, that I thought I understood the basic idea, but in its implementation I realized, I didn't. There are basically two problems:

  1. In the algorithm from the cited book the trajectory is built up from the sequence: $$S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, ..., S_{T-1}, A_{T-1}, R_{T}$$ generated by running one single episode. THEN, it loops for each step of the episode from: $t = T-1, T-2$ to $0$. That means, that if the episode had 4 tuples ($T = 3$), then I would start the inner loop from $t = T-1 = 4-1 = 3$, followed by $t=2$, then $t=1$ and at the end $t=0$. In other words, as far as I understood, I need to sweep the trajectory backward and not from 0 to 4. So I don't understand, why many different tutorials (#1, #2) or videos(#3) don't calculate the discounted rewards backwards but upwards. Am I wrong? Or am I overlooking something important and maybe obvious?
  1. The second thing is the statement: "Unless the pair $S_{t}, A_{t}$ appears in $S_{0}, A_{0}, S_{1}, A_{1}, ..., S_{t-1}, A_{t-1}$". Here it is not clear to me, how to interpret this statement. In many code implementations out there, it is interpreted as "the first time the state $S_{t}, A_{t}$ is encountered". But looking exactly at the notation, you realize, that the pair $S_{t}, A_{t}$ can only appear after and only the previous pair $S_{t-1}, A_{t-1}$, making the statement (at least for me) a nonsense. Even in this case: I'm missing something obvious?
$\endgroup$
1
  • $\begingroup$ Can you please put your specific question in the title? If you have more than one question, please, focus on one and next time limit each post to a single question. Thanks. $\endgroup$
    – nbro
    Jan 7 at 21:08

1 Answer 1

2
$\begingroup$

To clarify notation (question 2 in your post), the phrase "unless pair $S_t$ appears in $S_0, S_1, S_2, \ldots, S_{t-1}$" is meant to assess if the state $S_t$ is identical to one of the previous states in the episode. I understand your confusion when trying to apply this line of pseudocode to the Blackjack environment. The episodes in the Blackjack environment are equivalent to one complete hand of Blackjack. Note that the state signal in this environment contains the current cards on the table, in particular the player's cards. One of the two actions in Blackjack is to 'hit', which gives another card to the player. Therefore, the next state $S_t$ will never be identical to the previous state $S_{t-1}$ because the number of cards increases after the hit action. In the case that the hand busts or the 'stay' action is chosen, the episode ends in a terminal state $S_T$. This terminal state has value 0 by convention (i.e. $V(S_T) = 0$), and its value does not ever need to be calculated or averaged in the pseudocode, which is why the loop starts at $T-1$ instead of $T$. Other environments such as the Frozen Lake grid world may see the agent return to states previously encountered during the episode, necessitating the loop in the pseudocode for the first-visit MC prediction algorithm.

Your understanding of the backwards sweep seems correct. The backwards and forwards sweeps are mathematically equivalent, as they both associate the state $S_{t}$ with the return $R_{t+1}+R_{t+2}+R_{t+3}+\ldots+R_{T}$. To see this equivalence, we can view the returns as follows:

$$ \begin{align} S_0 &: R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T\\\\ S_1 &: R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\ S_2 &: R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\ &\vdots \\\\ S_{T-3} &: R_{T-2} + R_{T-1} + R_T \\\\ S_{T-2} &: R_{T-1} + R_T \\\\ S_{T-1} &: R_T \end{align} $$

The forwards view iterates through this list from top from bottom (i.e. from $S_0$ to $S_{T-1}$), and the backwards view iterates from bottom to top. The pseudocode most likely uses the backwards view for brevity and possible speed. The forwards view requires iterating through the list of rewards $[R_1, R_2, R_3, \ldots, R_T]$ twice: once to initially calculate $$R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T$$ and once when calculating the remaining returns. Specifically, to calculate the return for $S_1$, it suffices to subtract $R_1$ from the return for $S_0$. Similarly, the return for $S_2$ is the return for $S_1$ minus $R_2$. Calculating these forward returns amounts to a second iteration through the rewards list (aside from $R_{T-1}$) because the rewards $[R_1, R_2, \ldots, R_{T-2}]$ need to be subtracted. In contrast, the backwards view only needs to pass through the rewards list once: the return for $S_{T-1}$ is $R_T$, and the previous returns for $S_{T-2}$ through $S_0$ add a single reward at a time. Specifically, $R_{T-1}$ is added for $S_{T-2}$, $R_{T-2}$ is added for $S_{T-3}$, and so on. There is a slight speed savings (and possibly a one line of pseudocode savings) by preventing the need of initially calculating $R_1 + R_2 + \ldots + R_T$ as done in the forward view.

$\endgroup$

You must log in to answer this question.

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