Body: <p>Reinforcement Learning: An Introduction second edition, Richard S. Sutton and Andrew G. Barto:</p>
  <blockquote>
  <ol>
  <li>We made two unlikely assumptions above in order to easily obtain this guarantee of
  convergence for the Monte Carlo method. ... For now we focus on the assumption that policy evaluation operates on an infinite
  number of episodes. This assumption is relatively easy to remove. In fact, the same issue
  arises even in classical DP methods such as iterative policy evaluation, which also converge
  only asymptotically to the true value function.</li>
  </ol>
  </blockquote>
  <blockquote>
  <ol start="2">
  <li>There is a second approach to avoiding the infinite number of episodes nominally
  required for policy evaluation, in which we give up trying to complete policy evaluation
  before returning to policy improvement. On each evaluation step we move the value
  function toward q⇡k, but we do not expect to actually get close except over many steps.
  We used this idea when we first introduced the idea of GPI in Section 4.6. One extreme
  form of the idea is value iteration, in which only one iteration of iterative policy evaluation
  is performed between each step of policy improvement. The in-place version of value
  iteration is even more extreme; there we alternate between improvement and evaluation
  steps for single states.</li>
  </ol>
  </blockquote>
  <p>The original pseudocode:</p>
  <blockquote>
  <p><strong>Monte Carlo ES (Exploring Starts), for estimating</strong> <span class="math-container">$\pi \approx \pi_{*}$</span></p>
  <p>Initialize:</p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$\pi(s) \in \mathcal{A}(s)$</span> (arbitrarily), for all <span class="math-container">$s \in \mathcal{S}$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$Q(s, a) \in \mathbb{R}$</span> (arbitrarily), for all <span class="math-container">$s \in \mathcal{S}, a \in \mathcal{A}(s)$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$Returns(s, a) \leftarrow$</span> empty list, for all <span class="math-container">$s \in \mathcal{S}, a \in \mathcal{A}(s)$</span></p>
  <p>Loop forever (for each episode):</p>
  <p><span class="math-container">$\quad$</span> Choose <span class="math-container">$S_{0} \in \mathcal{S}, A_{0} \in \mathcal{A}\left(S_{0}\right)$</span> randomly such that all pairs have probability <span class="math-container">$\geq 0$</span></p>
  <p><span class="math-container">$\quad$</span> Generate an episode from <span class="math-container">$S_{0}, A_{0},$</span> following <span class="math-container">$\pi: S_{0}, A_{0}, R_{1}, \ldots, S_{T-1}, A_{T-1}, R_{T}$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$G \leftarrow 0$</span></p>
  <p><span class="math-container">$\quad$</span> Loop for each step of episode, <span class="math-container">$t=T-1, T-2, \ldots, 0$</span></p>
  <p><span class="math-container">$\quad\quad$</span> <span class="math-container">$G \leftarrow \gamma G+R_{t+1}$</span></p>
  <p><span class="math-container">$\quad\quad$</span> 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} \ldots, S_{t-1}, A_{t-1}:$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> Append <span class="math-container">$G$</span> to <span class="math-container">$Returns\left(S_{t}, A_{t}\right)$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> <span class="math-container">$Q\left(S_{t}, A_{t}\right) \leftarrow \text{average}\left(Returns\left(S_{t}, A_{t}\right)\right)$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> <span class="math-container">$\pi\left(S_{t}\right) \leftarrow \arg \max _{a} Q\left(S_{t}, a\right)$</span></p>
  </blockquote>
  <p>I want to make the same algorithm but with a model. The book states:</p>
  <blockquote>
  <ol start="3">
  <li>With a model, state values alone are sufficient to determine a policy; one simply looks ahead one step and chooses whichever action leads to the best combination of reward and next state, as we did in the chapter on DP.</li>
  </ol>
  </blockquote>
  <p>So based on the 1st quote I must use &quot;stars exploration&quot; and &quot;one evaluation — one improvement&quot; ideas (as well as in model-free version) to make the algorithm converge.</p>
  <p>My version of the pseudocode:</p>
  <blockquote>
  <p><strong>Monte Carlo ES (Exploring Starts), for estimating <span class="math-container">$\pi \approx \pi_{*}$</span> (with model)</strong></p>
  <p>Initialize:</p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$\pi(s) \in \mathcal{A}(s)$</span> (arbitrarily), for all <span class="math-container">$s \in \mathcal{S}$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$V(s) \in \mathbb{R}$</span> (arbitrarily), for all <span class="math-container">$s \in \mathcal{S}$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$Returns(s) \leftarrow$</span> empty list, for all <span class="math-container">$s \in \mathcal{S}$</span></p>
  <p>Loop forever (for each episode):</p>
  <p><span class="math-container">$\quad$</span> Choose <span class="math-container">$S_{0} \in \mathcal{S}, A_{0} \in \mathcal{A}\left(S_{0}\right)$</span> randomly such that all pairs have probability <span class="math-container">$\geq 0$</span></p>
  <p><span class="math-container">$\quad$</span> Generate an episode from <span class="math-container">$S_{0}, A_{0},$</span> following <span class="math-container">$\pi: S_{0}, A_{0}, R_{1}, \ldots, S_{T-1}, A_{T-1}, R_{T}$</span></p>
  <p><span class="math-container">$\quad$</span> <span class="math-container">$G \leftarrow 0$</span></p>
  <p><span class="math-container">$\quad$</span> Loop for each step of episode, <span class="math-container">$t=T-1, T-2, \ldots, 1$</span>:</p>
  <p><span class="math-container">$\quad\quad$</span> <span class="math-container">$G \leftarrow \gamma G+R_{t+1}$</span></p>
  <p><span class="math-container">$\quad\quad$</span> Unless <span class="math-container">$S_{t}$</span> appears in <span class="math-container">$S_{0}, S_{1}, \ldots, S_{t-1}:$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> Append <span class="math-container">$G$</span> to <span class="math-container">$Returns \left(S_{t}\right)$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> <span class="math-container">$V\left(S_{t}\right)\leftarrow\text{average}\left(Returns\left(S_{t}\right)\right)$</span></p>
  <p><span class="math-container">$\quad\quad\quad$</span> <span class="math-container">$\pi\left(S_{t-1}\right) \leftarrow \operatorname{argmax}_{a} \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid S_{t-1}, a\right)\left[\gamma V\left(s^{\prime}\right)+r\right]$</span></p>
  </blockquote>
  <p>— Here I update the policy in <span class="math-container">$S_{t-1}$</span> because the step before we update <span class="math-container">$V(S_{t})$</span> and changes to <span class="math-container">$V(S_{t})$</span> don't affect <span class="math-container">$\pi (S_{t})$</span>, but affect <span class="math-container">$ \pi (S_{t-1})$</span>, as <span class="math-container">$S_{t}$</span> is in <span class="math-container">$S'$</span> for <span class="math-container">$S_{t-1}$</span>.</p>
  <p>Pseudocode as images:</p>
  <blockquote class="spoiler">
  <p> <a href="https://i.sstatic.net/jo686.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/jo686.png" alt="" /></a>
   <a href="https://i.sstatic.net/qlcLW.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qlcLW.png" alt="" /></a></p>
  </blockquote>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T17:24:07.843Z
Comments.Text: Hello. Welcome to AI SE! Take a look at our [on-topic page](https://ai.stackexchange.com/help/on-topic) to know more about our site and scope. Meanwhile, you should probably fix the language mistakes (e.g. in the title). I would also like to note that you can use latex/mathjax on this site, so I suggest that you edit your post to use it and fix these mistakes.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T19:18:14.973Z
Comments.Text: I've changed the title a bit, but not sure I have time to rewrite the images of pseudocode in latex. It certainly will not make the question more clear.
Comments.UserDisplayName: Дмитрий Винник
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T21:43:39.837Z
Comments.Text: No worries if pressed for time, but part of the utility of rendering the formulae in latex/mathjax is that it facilitates getting an answer.  (Person answering can cut and paste the original formulas to save time.  Not doing that places the burden on them, which can be a disincentive for answering.)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-16T15:36:50.353Z
Comments.Text: I was not asking you to convert the pseudocode to latex/mathjax, but just the formulas at the end of your post, but someone already proposed an edit that fixes that. You don't need to convert the screenshots of the pseudocode to latex, so you can revert your last edit. If you really want to do that, maybe have a look at this: https://ai.meta.stackexchange.com/a/1680/2444.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><monte-carlo-methods>
Title: Is my pseudocode titled "Monte Carlo Exploring Starts (with model)" correct?
UserDisplayName: Дмитрий Винник
ThreadText: # Is my pseudocode titled "Monte Carlo Exploring Starts (with model)" correct?
  
  (Asked by: username_0 on 2020-12-15)
  
  Reinforcement Learning: An Introduction second edition, Richard S. Sutton and Andrew G. Barto:
  
  > 1. We made two unlikely assumptions above in order to easily obtain this guarantee of
  >    convergence for the Monte Carlo method. ... For now we focus on the assumption that policy evaluation operates on an infinite
  >    number of episodes. This assumption is relatively easy to remove. In fact, the same issue
  >    arises even in classical DP methods such as iterative policy evaluation, which also converge
  >    only asymptotically to the true value function.
  
  > 2. There is a second approach to avoiding the infinite number of episodes nominally
  >    required for policy evaluation, in which we give up trying to complete policy evaluation
  >    before returning to policy improvement. On each evaluation step we move the value
  >    function toward q⇡k, but we do not expect to actually get close except over many steps.
  >    We used this idea when we first introduced the idea of GPI in Section 4.6. One extreme
  >    form of the idea is value iteration, in which only one iteration of iterative policy evaluation
  >    is performed between each step of policy improvement. The in-place version of value
  >    iteration is even more extreme; there we alternate between improvement and evaluation
  >    steps for single states.
  
  The original pseudocode:
  
  > **Monte Carlo ES (Exploring Starts), for estimating** $\pi \approx \pi\_{\*}$
  >
  > Initialize:
  >
  > $\quad$ $\pi(s) \in \mathcal{A}(s)$ (arbitrarily), for all $s \in \mathcal{S}$
  >
  > $\quad$ $Q(s, a) \in \mathbb{R}$ (arbitrarily), for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$
  >
  > $\quad$ $Returns(s, a) \leftarrow$ empty list, for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$
  >
  > Loop forever (for each episode):
  >
  > $\quad$ Choose $S\_{0} \in \mathcal{S}, A\_{0} \in \mathcal{A}\left(S\_{0}\right)$ randomly such that all pairs have probability $\geq 0$
  >
  > $\quad$ Generate an episode from $S\_{0}, A\_{0},$ following $\pi: S\_{0}, A\_{0}, R\_{1}, \ldots, S\_{T-1}, A\_{T-1}, R\_{T}$
  >
  > $\quad$ $G \leftarrow 0$
  >
  > $\quad$ Loop for each step of episode, $t=T-1, T-2, \ldots, 0$
  >
  > $\quad\quad$ $G \leftarrow \gamma G+R\_{t+1}$
  >
  > $\quad\quad$ Unless the pair $S\_{t}, A\_{t}$ appears in $S\_{0}, A\_{0}, S\_{1}, A\_{1} \ldots, S\_{t-1}, A\_{t-1}:$
  >
  > $\quad\quad\quad$ Append $G$ to $Returns\left(S\_{t}, A\_{t}\right)$
  >
  > $\quad\quad\quad$ $Q\left(S\_{t}, A\_{t}\right) \leftarrow \text{average}\left(Returns\left(S\_{t}, A\_{t}\right)\right)$
  >
  > $\quad\quad\quad$ $\pi\left(S\_{t}\right) \leftarrow \arg \max \_{a} Q\left(S\_{t}, a\right)$
  
  I want to make the same algorithm but with a model. The book states:
  
  > 3. With a model, state values alone are sufficient to determine a policy; one simply looks ahead one step and chooses whichever action leads to the best combination of reward and next state, as we did in the chapter on DP.
  
  So based on the 1st quote I must use "stars exploration" and "one evaluation — one improvement" ideas (as well as in model-free version) to make the algorithm converge.
  
  My version of the pseudocode:
  
  > **Monte Carlo ES (Exploring Starts), for estimating $\pi \approx \pi\_{\*}$ (with model)**
  >
  > Initialize:
  >
  > $\quad$ $\pi(s) \in \mathcal{A}(s)$ (arbitrarily), for all $s \in \mathcal{S}$
  >
  > $\quad$ $V(s) \in \mathbb{R}$ (arbitrarily), for all $s \in \mathcal{S}$
  >
  > $\quad$ $Returns(s) \leftarrow$ empty list, for all $s \in \mathcal{S}$
  >
  > Loop forever (for each episode):
  >
  > $\quad$ Choose $S\_{0} \in \mathcal{S}, A\_{0} \in \mathcal{A}\left(S\_{0}\right)$ randomly such that all pairs have probability $\geq 0$
  >
  > $\quad$ Generate an episode from $S\_{0}, A\_{0},$ following $\pi: S\_{0}, A\_{0}, R\_{1}, \ldots, S\_{T-1}, A\_{T-1}, R\_{T}$
  >
  > $\quad$ $G \leftarrow 0$
  >
  > $\quad$ Loop for each step of episode, $t=T-1, T-2, \ldots, 1$:
  >
  > $\quad\quad$ $G \leftarrow \gamma G+R\_{t+1}$
  >
  > $\quad\quad$ Unless $S\_{t}$ appears in $S\_{0}, S\_{1}, \ldots, S\_{t-1}:$
  >
  > $\quad\quad\quad$ Append $G$ to $Returns \left(S\_{t}\right)$
  >
  > $\quad\quad\quad$ $V\left(S\_{t}\right)\leftarrow\text{average}\left(Returns\left(S\_{t}\right)\right)$
  >
  > $\quad\quad\quad$ $\pi\left(S\_{t-1}\right) \leftarrow \operatorname{argmax}\_{a} \sum\_{s^{\prime}, r} p\left(s^{\prime}, r \mid S\_{t-1}, a\right)\left[\gamma V\left(s^{\prime}\right)+r\right]$
  
  — Here I update the policy in $S\_{t-1}$ because the step before we update $V(S\_{t})$ and changes to $V(S\_{t})$ don't affect $\pi (S\_{t})$, but affect $ \pi (S\_{t-1})$, as $S\_{t}$ is in $S'$ for $S\_{t-1}$.
  
  Pseudocode as images:
  
  > [![](https://i.sstatic.net/jo686.png)](https://i.sstatic.net/jo686.png)
  > [![](https://i.sstatic.net/qlcLW.png)](https://i.sstatic.net/qlcLW.png)
  
  **Tags:** reinforcement-learning, monte-carlo-methods
  
  > **Comments:**
  > **username_1**: Hello. Welcome to AI SE! Take a look at our [on-topic page](https://ai.stackexchange.com/help/on-topic) to know more about our site and scope. Meanwhile, you should probably fix the language mistakes (e.g. in the title). I would also like to note that you can use latex/mathjax on this site, so I suggest that you edit your post to use it and fix these mistakes.  
  > **username_0**: I've changed the title a bit, but not sure I have time to rewrite the images of pseudocode in latex. It certainly will not make the question more clear.  
  > **username_2**: No worries if pressed for time, but part of the utility of rendering the formulae in latex/mathjax is that it facilitates getting an answer.  (Person answering can cut and paste the original formulas to save time.  Not doing that places the burden on them, which can be a disincentive for answering.)  
  > **username_1**: I was not asking you to convert the pseudocode to latex/mathjax, but just the formulas at the end of your post, but someone already proposed an edit that fixes that. You don't need to convert the screenshots of the pseudocode to latex, so you can revert your last edit. If you really want to do that, maybe have a look at this: https://ai.meta.stackexchange.com/a/1680/2444.  
  
  ---
  
  ## 0 answers
  
  