Answers.Body: <p>To clarify notation (question 2 in your post), the phrase &quot;unless pair <span class="math-container">$S_t$</span> appears in <span class="math-container">$S_0, S_1, S_2, \ldots, S_{t-1}$</span>&quot; is meant to <strong>assess if the state <span class="math-container">$S_t$</span> is identical to one of the previous states</strong> 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, <strong>the next state <span class="math-container">$S_t$</span> will never be identical to the previous state <span class="math-container">$S_{t-1}$</span> because the number of cards increases after the hit action</strong>. In the case that the hand busts or the 'stay' action is chosen, the episode ends in a terminal state <span class="math-container">$S_T$</span>. This terminal state has value 0 by convention (i.e. <span class="math-container">$V(S_T) = 0$</span>), and its value does not ever need to be calculated or averaged in the pseudocode, which is why the loop starts at <span class="math-container">$T-1$</span> instead of <span class="math-container">$T$</span>. Other environments such as the <a href="https://gymnasium.farama.org/environments/toy_text/frozen_lake/" rel="nofollow noreferrer">Frozen Lake grid world</a> 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.</p>
  <p>Your understanding of the backwards sweep seems correct. The backwards and forwards sweeps are mathematically equivalent, as they both associate the state <span class="math-container">$S_{t}$</span> with the return <span class="math-container">$R_{t+1}+R_{t+2}+R_{t+3}+\ldots+R_{T}$</span>. To see this equivalence, we can view the returns as follows:</p>
  <p><span class="math-container">$$ \begin{align} 
  S_0 &amp;: R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T\\\\ 
  S_1 &amp;: R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\ 
  S_2 &amp;: R_3 + \ldots + R_{T-2} + R_{T-1} + R_T \\\\ 
  &amp;\vdots \\\\ 
  S_{T-3} &amp;: R_{T-2} + R_{T-1} + R_T \\\\ 
  S_{T-2} &amp;: R_{T-1} + R_T \\\\ 
  S_{T-1} &amp;: R_T
  \end{align} $$</span></p>
  <p>The forwards view iterates through this list from top from bottom (i.e. from <span class="math-container">$S_0$</span> to <span class="math-container">$S_{T-1}$</span>), and the backwards view iterates from bottom to top. <strong>The pseudocode most likely uses the backwards view for brevity and possible speed</strong>. The forwards view requires iterating through the list of rewards <span class="math-container">$[R_1, R_2, R_3, \ldots, R_T]$</span> twice: once to initially calculate <span class="math-container">$$R_1 + R_2 + R_3 + \ldots + R_{T-2} + R_{T-1} + R_T$$</span> and once when calculating the remaining returns. Specifically, to calculate the return for <span class="math-container">$S_1$</span>, it suffices to subtract <span class="math-container">$R_1$</span> from the return for <span class="math-container">$S_0$</span>. Similarly, the return for <span class="math-container">$S_2$</span> is the return for <span class="math-container">$S_1$</span> minus <span class="math-container">$R_2$</span>. Calculating these forward returns amounts to a second iteration through the rewards list (aside from <span class="math-container">$R_{T-1}$</span>) because the rewards <span class="math-container">$[R_1, R_2, \ldots, R_{T-2}]$</span> need to be subtracted. In contrast, the backwards view only needs to pass through the rewards list once: the return for <span class="math-container">$S_{T-1}$</span> is <span class="math-container">$R_T$</span>, and the previous returns for <span class="math-container">$S_{T-2}$</span> through <span class="math-container">$S_0$</span> add a single reward at a time. Specifically, <span class="math-container">$R_{T-1}$</span> is added for <span class="math-container">$S_{T-2}$</span>, <span class="math-container">$R_{T-2}$</span> is added for <span class="math-container">$S_{T-3}$</span>, and so on. There is a slight speed savings (and possibly a one line of pseudocode savings) by preventing the need of initially calculating <span class="math-container">$R_1 + R_2 + \ldots + R_T$</span> as done in the forward view.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-06T18:45:12.590Z
Answers.LastActivityDate: 2024-01-06T20:07:20.650Z
Answers.LastEditDate: 2024-01-06T20:07:20.650Z
Answers.UserDisplayName: DeepQZero
Body: <p>I'm really confused about understanding the Monte Carlo first visit algorithm as presented in the Sutton &amp; Barto's book in chapter V. Here is the pseudocode:</p>
  <p><a href="https://i.sstatic.net/rESs2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rESs2.png" alt="enter image description here" /></a></p>
  <p>The reason is that I'm trying to implement the same algorithm for the game &quot;Blackjack&quot; 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 <em>thought</em> I understood the basic idea, but in its implementation I realized, I didn't. There are basically two problems:</p>
  <ol>
  <li>In the algorithm from the cited book the trajectory is built up from the sequence:
  <span class="math-container">$$S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, ..., S_{T-1}, A_{T-1}, R_{T}$$</span>
  generated by running one single episode. THEN, it loops for each step of the episode <strong>from</strong>: <span class="math-container">$t = T-1, T-2$</span> to <span class="math-container">$0$</span>. That means, that if the episode had 4 tuples (<span class="math-container">$T = 3$</span>), then I would start the inner loop from <span class="math-container">$t = T-1 = 4-1 = 3$</span>, followed by <span class="math-container">$t=2$</span>, then <span class="math-container">$t=1$</span> and at the end <span class="math-container">$t=0$</span>. In other words, as far as I understood, <em>I need to sweep the trajectory <strong>backward</strong> and not from 0 to 4.</em> So I don't understand, why many different tutorials (<a href="https://medium.com/data-science-in-your-pocket/monte-carlo-for-reinforcement-learning-with-example-1754439dd628" rel="nofollow noreferrer">#1</a>, <a href="https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/" rel="nofollow noreferrer">#2</a>) or videos(<a href="https://youtu.be/wn8hlPNwL74?si=3D2O-Xq8N-cuWrTB" rel="nofollow noreferrer">#3</a>) don't calculate the discounted rewards <strong>backwards</strong> but upwards. Am I wrong? Or am I overlooking something important and maybe obvious?</li>
  </ol>
  <ol start="2">
  <li>The second thing is the statement:
  &quot;Unless the pair <span class="math-container">$S_{t}, A_{t}$</span> appears in <span class="math-container">$S_{0}, A_{0}, S_{1}, A_{1}, ..., S_{t-1}, A_{t-1}$</span>&quot;. Here it is not clear to me, how to interpret this statement. In many code implementations out there, it is interpreted as &quot;the first time the state <span class="math-container">$S_{t}, A_{t}$</span> is encountered&quot;. But looking exactly at the notation, you realize, that the pair <span class="math-container">$S_{t}, A_{t}$</span> <em>can only appear after and only</em> the previous pair <span class="math-container">$S_{t-1}, A_{t-1}$</span>, making the statement (at least for me) a nonsense. Even in this case: I'm missing something obvious?</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-07T21:08:24.150Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><monte-carlo-methods>
Title: Confused about Monte Carlo first visit algorithm
UserDisplayName: Dave
ThreadText: # Confused about Monte Carlo first visit algorithm
  
  (Asked by: username_0 on 2024-01-05)
  
  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](https://i.sstatic.net/rESs2.png)](https://i.sstatic.net/rESs2.png)
  
  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](https://medium.com/data-science-in-your-pocket/monte-carlo-for-reinforcement-learning-with-example-1754439dd628), [#2](https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/)) or videos([#3](https://youtu.be/wn8hlPNwL74?si=3D2O-Xq8N-cuWrTB)) don't calculate the discounted rewards **backwards** but upwards. Am I wrong? Or am I overlooking something important and maybe obvious?
  
  2. 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?
  
  **Tags:** reinforcement-learning, monte-carlo-methods
  
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-01-06. Score: 2 | Accepted answer
  
  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](https://gymnasium.farama.org/environments/toy_text/frozen_lake/) 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.
  
  
  ---
  
  