Answers.Body: <p>In this game you can view end of an episode two ways:</p>
  <ul>
  <li><p>There is an implied, terminal, fourth state <span class="math-container">$s_4$</span> representing the end of the game.</p>
  </li>
  <li><p>You could view the process as a continuous repeating one, where no matter what the choice is made in <span class="math-container">$s_2$</span> or <span class="math-container">$s_3$</span>, the following state is <span class="math-container">$s_1$</span>.</p>
  </li>
  </ul>
  <p>The first, terminating, view is a simpler and entirely natural view since nothing that the agent does in one episode can influence the next. It will result in a Q table that predicts future rewards within a single episode for the current agent (as opposed to discounted view over multiple episodes).</p>
  <p>You are over-complicating things for yourself by ignoring that a zero reward is still a reward (of <span class="math-container">$0$</span>). There is no need to remove <span class="math-container">$R$</span> from your initial update rule. In many environments there are rewards collected before the end of an episode.</p>
  <p>In addition, to complete the standard episodic view, you can note that <span class="math-container">$Q(s_4, \cdot) = 0$</span> always by definition, hence so does <span class="math-container">$\text{max}_{a'}[Q(s_4, a'] = 0$</span>. It is common here though to have a branch based on detecting a terminal state, and use a different update rule:</p>
  <p><span class="math-container">$$Q_{t+1}(S_3,a_{23}) = Q_t(S_3,a_{23}) + \alpha\left(R - Q_t(s_3,a_{23}) \right)$$</span></p>
  <p>In brief, most implementations of TD algorithms do this:</p>
  <ul>
  <li><p>Always assume a reward on each time step, which can be set to <span class="math-container">$0$</span></p>
  </li>
  <li><p>Special case for end of episode with a simplified update rule, to avoid needing to store, look up or calculate the <span class="math-container">$0$</span> value associated with terminal states</p>
  </li>
  </ul>
  <p>When implementing the environment, it is common to have a <code>step</code> function that always returns reward, next state and whether or not it is terminal e.g.</p>
  <pre><code>reward, next_state, done = env.step(action)
  </code></pre>
  <p>Details may vary around this. If you are working with an environment that does not have such a function (many will not have an inherent reward), then it is common to implement a similar function as a convenient wrapper to the environment so that the agent code does not have to include calculations of what the reward should be or whether the state is terminal.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-28T19:18:42.573Z
Answers.Text: Thank you - this makes things clear. However, I have one more question. The task is just people are playing this two stage MDP for a total of say $T = 200$ trials or episodes. In this view, humans are obviously learning things from episode to episode, albeit to a small extent; therefore, would it better to implement it in the second way you propose, as one continuing Markov Task with one episode and $T$ time steps?
Answers.UserDisplayName: dezdichado
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-28T19:22:08.123Z
Answers.Text: @dezdichado: The learning problem is still solved by the strict episodic view, assuming you keep the Q table between episodes. I assumed this - were you thinking to reset it?. Repeating the episodes allows the learner to explore different approaches and figure out which is best - which is why it is being repeated, because the point is to study learning through trial and error. There are cases where you might want to think about aggregating reward over multiple episodes, but even then it is simpler and easier to analyse if you stick with the strictly episodic view for Q values and update rules.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-19T20:02:56.753Z
Answers.Text: Sorry to bother you again but I am now transitioning from matlab to python and in doing so, I am rewriting all my codes in a more scalable, object-oriented fashion. I was wondering if could point me to a code that writes the environment in customizable manner. I did do google searches and all the implementations I could find use the openai gym interface, which as a whole is a rather advanced for a beginner programmer like me.
Answers.UserDisplayName: dezdichado
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-19T21:02:51.167Z
Answers.Text: @dezdichado The basic gym interface for environments is a reasonable design for a standardised framework in my opinion. I have not worked with any other similar libraries in any depth. Sorry I cannot help further.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-28T18:56:36.023Z
Answers.LastActivityDate: 2020-06-28T19:01:51.453Z
Answers.LastEditDate: 2020-06-28T19:01:51.453Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am a bit confused as to how exactly I should be implementing SARSA (or Q-learning too) on what is a simple 2-stage Markov Decision Task. The structure of the task is as follows:</p>
  <p><a href="https://i.sstatic.net/8RgU4.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8RgU4.jpg" alt="enter image description here" /></a></p>
  <p>Basically, there are three states <span class="math-container">$\{S_1,S_2,S_3\}$</span> with <span class="math-container">$S_1$</span> is in the first stage for which the two possible actions are the two yellow airplanes. <span class="math-container">$S_2$</span> and <span class="math-container">$S_3$</span> are the possible states for the second stage and the feasible actions are the blue and red background pictures, respectively. There is only a reward at the end of the second stage choice. If I call the two first stage actions <span class="math-container">$\{a_{11},a_{12}\}$</span> and the four possible second stage actions <span class="math-container">$\{a_{21},a_{22},a_{23},a_{24}\}$</span>, from left to right, then a sample trial/episode will look like:
  <span class="math-container">$$S_1, a_{11}, S_2, a_{22},R \quad \text{ or }\quad S_1, a_{11}, S_3, a_{24}, R.$$</span></p>
  <p>In the paper I am reading, where the figure is from, they used a complicated version of TD<span class="math-container">$(\lambda)$</span> in which they maintained two action-value functions <span class="math-container">$Q_1$</span> and <span class="math-container">$Q_2$</span> for each stages. On the other hand, I am trying to implement a simple SARSA update for each episode <span class="math-container">$t$</span>:
  <span class="math-container">$$Q_{t+1}(s,a)= Q_t(s,a) + \alpha\left(r + \gamma\cdot Q_t(s',a') - Q_t(s,a)\right).$$</span></p>
  <p>In the first-stage, there is no reward so an actual realization will look like:
  <span class="math-container">$$Q_{t+1}(S_1, a_{11}) = Q_t(S_1,a_{11})+\alpha\left( \gamma\cdot Q_t(S_3,a_{23}) - Q_t(S_1,a_{11})\right).$$</span></p>
  <p>I guess my confusion is then how should it look like for the second stage of an episode? That is, if we continue the above realization of the task above, <span class="math-container">$S_1, a_{11}, S_3, a_{23}, R$</span>, would should fill in the <span class="math-container">$?$</span>:
  <span class="math-container">$$Q_{t+1}(S_3,a_{23}) = Q_t(S_3,a_{23}) + \alpha\left(R +\gamma\cdot Q_t(\cdot,\cdot)-Q_t(s_3,a_{23}) \right)$$</span></p>
  <p>One on hand, it seems to me that since this is the end of an episode, we assign <span class="math-container">$0$</span> to the <span class="math-container">$Q_t(\cdot,\cdot).$</span> On the other hand, the nature of this task is that it repeats the same episode over time for a total of <span class="math-container">$T$</span>, a large number, times we need <span class="math-container">$Q_t(\cdot,\cdot) = Q_t(S_1,\cdot),$</span> with the additional action-selection in the first stage there.</p>
  <p>I will greatly appreciate if someone can tell me what is the right way to go here.</p>
  <p><a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3077926/" rel="nofollow noreferrer">The link to paper</a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-28T08:45:44.810Z
Comments.Text: You say "In the paper I am reading" - could you please link that resource, as it may explain why the writers are using what appears to be an over-complicated approach to solve a trivial-looking toy problem.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-28T16:50:34.093Z
Comments.Text: @NeilSlater I added the link to the paper. I should mention that the research is roughly about modeling human decision-making, especially that of those who have some impairment. As such, the focus is hardly about finding an optimal solver. 
  
  But my question is very simple - I want to start very simple by implementing a basic SARSA, which I did; however, the simulations I got look very different and wrong even, so I am guessing that my implementation is wrong.
Comments.UserDisplayName: dezdichado
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-28T17:30:15.067Z
Comments.Text: Thanks for adding the link. I didn't read the paper yet, but would expect the researchers are implementing *inverse* reinforcement learning given the stated goal. That could be dificult to follow if you want to study classic RL used for optimal control.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><q-learning><markov-decision-process><sarsa>
Title: Implementing SARSA for a 2-stage Markov Decision Process
UserDisplayName: dezdichado
ThreadText: # Implementing SARSA for a 2-stage Markov Decision Process
  
  (Asked by: username_0 on 2020-06-28)
  
  I am a bit confused as to how exactly I should be implementing SARSA (or Q-learning too) on what is a simple 2-stage Markov Decision Task. The structure of the task is as follows:
  
  [![enter image description here](https://i.sstatic.net/8RgU4.jpg)](https://i.sstatic.net/8RgU4.jpg)
  
  Basically, there are three states $\{S\_1,S\_2,S\_3\}$ with $S\_1$ is in the first stage for which the two possible actions are the two yellow airplanes. $S\_2$ and $S\_3$ are the possible states for the second stage and the feasible actions are the blue and red background pictures, respectively. There is only a reward at the end of the second stage choice. If I call the two first stage actions $\{a\_{11},a\_{12}\}$ and the four possible second stage actions $\{a\_{21},a\_{22},a\_{23},a\_{24}\}$, from left to right, then a sample trial/episode will look like:
  $$S\_1, a\_{11}, S\_2, a\_{22},R \quad \text{ or }\quad S\_1, a\_{11}, S\_3, a\_{24}, R.$$
  
  In the paper I am reading, where the figure is from, they used a complicated version of TD$(\lambda)$ in which they maintained two action-value functions $Q\_1$ and $Q\_2$ for each stages. On the other hand, I am trying to implement a simple SARSA update for each episode $t$:
  $$Q\_{t+1}(s,a)= Q\_t(s,a) + \alpha\left(r + \gamma\cdot Q\_t(s',a') - Q\_t(s,a)\right).$$
  
  In the first-stage, there is no reward so an actual realization will look like:
  $$Q\_{t+1}(S\_1, a\_{11}) = Q\_t(S\_1,a\_{11})+\alpha\left( \gamma\cdot Q\_t(S\_3,a\_{23}) - Q\_t(S\_1,a\_{11})\right).$$
  
  I guess my confusion is then how should it look like for the second stage of an episode? That is, if we continue the above realization of the task above, $S\_1, a\_{11}, S\_3, a\_{23}, R$, would should fill in the $?$:
  $$Q\_{t+1}(S\_3,a\_{23}) = Q\_t(S\_3,a\_{23}) + \alpha\left(R +\gamma\cdot Q\_t(\cdot,\cdot)-Q\_t(s\_3,a\_{23}) \right)$$
  
  One on hand, it seems to me that since this is the end of an episode, we assign $0$ to the $Q\_t(\cdot,\cdot).$ On the other hand, the nature of this task is that it repeats the same episode over time for a total of $T$, a large number, times we need $Q\_t(\cdot,\cdot) = Q\_t(S\_1,\cdot),$ with the additional action-selection in the first stage there.
  
  I will greatly appreciate if someone can tell me what is the right way to go here.
  
  [The link to paper](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3077926/)
  
  **Tags:** reinforcement-learning, q-learning, markov-decision-process, sarsa
  > **Comments:**
  > **username_1**: You say "In the paper I am reading" - could you please link that resource, as it may explain why the writers are using what appears to be an over-complicated approach to solve a trivial-looking toy problem.  
  > **username_0**: @NeilSlater I added the link to the paper. I should mention that the research is roughly about modeling human decision-making, especially that of those who have some impairment. As such, the focus is hardly about finding an optimal solver.   But my question is very simple - I want to start very simple by implementing a basic SARSA, which I did; however, the simulations I got look very different and wrong even, so I am guessing that my implementation is wrong.  
  > **username_1**: Thanks for adding the link. I didn't read the paper yet, but would expect the researchers are implementing *inverse* reinforcement learning given the stated goal. That could be dificult to follow if you want to study classic RL used for optimal control.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-28. Score: 1 | Accepted answer
  
  In this game you can view end of an episode two ways:
  
  There is an implied, terminal, fourth state $s_4$ representing the end of the game.
  
  You could view the process as a continuous repeating one, where no matter what the choice is made in $s_2$ or $s_3$, the following state is $s_1$.
  
  
  The first, terminating, view is a simpler and entirely natural view since nothing that the agent does in one episode can influence the next. It will result in a Q table that predicts future rewards within a single episode for the current agent (as opposed to discounted view over multiple episodes).
  You are over-complicating things for yourself by ignoring that a zero reward is still a reward (of $0$). There is no need to remove $R$ from your initial update rule. In many environments there are rewards collected before the end of an episode.
  In addition, to complete the standard episodic view, you can note that $Q(s_4, \cdot) = 0$ always by definition, hence so does $\text{max}_{a'}[Q(s_4, a'] = 0$. It is common here though to have a branch based on detecting a terminal state, and use a different update rule:
  $$Q_{t+1}(S_3,a_{23}) = Q_t(S_3,a_{23}) + \alpha\left(R - Q_t(s_3,a_{23}) \right)$$
  In brief, most implementations of TD algorithms do this:
  
  Always assume a reward on each time step, which can be set to $0$
  
  Special case for end of episode with a simplified update rule, to avoid needing to store, look up or calculate the $0$ value associated with terminal states
  
  
  When implementing the environment, it is common to have a step function that always returns reward, next state and whether or not it is terminal e.g.
  reward, next_state, done = env.step(action)
  
  Details may vary around this. If you are working with an environment that does not have such a function (many will not have an inherent reward), then it is common to implement a similar function as a convenient wrapper to the environment so that the agent code does not have to include calculations of what the reward should be or whether the state is terminal.
  
  > **Comments:**
  > **username_0**: Thank you - this makes things clear. However, I have one more question. The task is just people are playing this two stage MDP for a total of say $T = 200$ trials or episodes. In this view, humans are obviously learning things from episode to episode, albeit to a small extent; therefore, would it better to implement it in the second way you propose, as one continuing Markov Task with one episode and $T$ time steps?  
  > **username_1**: @dezdichado: The learning problem is still solved by the strict episodic view, assuming you keep the Q table between episodes. I assumed this - were you thinking to reset it?. Repeating the episodes allows the learner to explore different approaches and figure out which is best - which is why it is being repeated, because the point is to study learning through trial and error. There are cases where you might want to think about aggregating reward over multiple episodes, but even then it is simpler and easier to analyse if you stick with the strictly episodic view for Q values and update rules.  
  > **username_0**: Sorry to bother you again but I am now transitioning from matlab to python and in doing so, I am rewriting all my codes in a more scalable, object-oriented fashion. I was wondering if could point me to a code that writes the environment in customizable manner. I did do google searches and all the implementations I could find use the openai gym interface, which as a whole is a rather advanced for a beginner programmer like me.  
  > **username_1**: @dezdichado The basic gym interface for environments is a reasonable design for a standardised framework in my opinion. I have not worked with any other similar libraries in any depth. Sorry I cannot help further.  
  
  ---
  
  