0
$\begingroup$

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

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

$\endgroup$
4
  • $\begingroup$ Hello. Welcome to AI SE! Take a look at our on-topic page 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. $\endgroup$ – nbro Dec 15 '20 at 17:24
  • 2
    $\begingroup$ 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. $\endgroup$ – Дмитрий Винник Dec 15 '20 at 19:18
  • 1
    $\begingroup$ 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.) $\endgroup$ – DukeZhou Dec 15 '20 at 21:43
  • $\begingroup$ 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: ai.meta.stackexchange.com/a/1680/2444. $\endgroup$ – nbro Dec 16 '20 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.