Answers.Body: <p>In the gridworld setting, you can replicate the lecture's results, by defining the reward function <span class="math-container">$R_t(s,a) = R(s)$</span>, meaning that the reward function simply aggregates only on the current state and ignores the selected action and the next state, as well. With this modification, the state value of a terminal state always (after the 1st iteration) equals its reward (+1 or -1).</p>
  <p>However, this is not very common in MDP implementations (e.g. in gym envs). I think that when this is the case, it should always be highlighted.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T01:58:08.377Z
Answers.Text: Another way to put this: The states in boxes with +1 and -1 reward for leaving them are *not* the terminal states. The terminal state occurs when taking any action from those states (which also grants the associated reward), and is not shown on the grid. How can you tell they are not terminal states? Because they have a non-zero value. Terminal states have 0 value by definition (because nothing happens after the agent enters them)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-19T13:23:41.210Z
Answers.Text: Exactly. There is a little confusion on the definition of Q and V among books and lecture slides.
Answers.UserDisplayName: ddaedalus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-21T02:05:56.373Z
Answers.Text: @NeilSlater Yes! I found this out while performing the lengthy and tedious computation. I think this is something that should be said especially when you are learning MDP for the first time to avoid this grand confusion.
Answers.UserDisplayName: cgo
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-18T16:52:59.003Z
Answers.LastActivityDate: 2022-02-18T16:52:59.003Z
Answers.UserDisplayName: ddaedalus
Body: <p>I am watching the lecture by Abbeel on MDPs and Reinforcement Learning. The setup of the problem is the classic gridworld with optimal policy (and corresponding values of states) pictured below. <a href="https://i.sstatic.net/PU3VJ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/PU3VJ.png" alt="enter image description here" /></a></p>
  <p>The parameters of the problem here are: there is a 0.8 chance that you go to your chosen action and 0.1 chance you go to a direction perpendicular to it. For example, if you choose &quot;right&quot;, then you have a 0.8 chance of going right and a 0.1 chance of going up, and another 0.1 chance of going down. If the action makes the agent 'bump' into the wall or 'leave' the world, then the agent stays in the same place.</p>
  <p>My question is this: Since the problem above shows the optimal policy (having solved/demonstrated the solution via the Value Iteration algorithm), is it possible that I solve for the values of the states manually (analytically), knowing that the optimal policy is give above? I expected that if I setup the (system of) equations, I should be able to recover the values that are printed in the figure above.</p>
  <p>I represented the states of the gridworld as follows. <span class="math-container">$X$</span> is just a place holder since it is a blocked state.</p>
  <p><span class="math-container">$\begin{array}{cccc} H &amp; D &amp; A &amp; +1 \\ G &amp;X &amp; B &amp; -1 \\ F &amp; E &amp; C &amp; J \end{array}$</span></p>
  <p>Knowing that <span class="math-container">$V^{\pi}(s) = \displaystyle\sum_{a} \pi(a|S) \displaystyle\sum_{s'} P(s'|s,a) [r_{t+1} + \gamma V^{\pi}(s')]$</span>, <span class="math-container">$\gamma = 0.9$</span>, there are no rewards awarded for every step except with entering the terminal states <span class="math-container">$+1$</span> and <span class="math-container">$-1$</span>.</p>
  <p>The actions are already deterministic at this point, so I set <span class="math-container">$\pi(a|s) = 1$</span>.
  For simplicity of notation, I just wrote <span class="math-container">$A$</span> as the value of state <span class="math-container">$A$</span> in the following equations:</p>
  <p>At state <span class="math-container">$A$</span>: <span class="math-container">$A = 0.8[1+0] + 0.1[0.9A] + 0.1[0.9B]$</span>.
  Meaning: 0.8 chance of going right, receiving a reward of 1, and the value of the terminal state is 0. 0.1 change of going up and therefore ending up in the same state <span class="math-container">$A$</span>. Finally, 0.1 chance of going down, ending up in state <span class="math-container">$B$</span>.</p>
  <p>Another example: <span class="math-container">$H = 0.8[0.9D] + 0.1[0.9H] + 0.1[0.9G]$</span>
  Meaning: 0.8 chance to move right to D, 0.1 chance to bump the upper wall and stay in H, another 0.1 chance to move down the lower state G.</p>
  <p>There are a total of 9 equations of this form. When I solved for the unknowns <span class="math-container">$A,B,\cdots,J$</span>, why am I not getting the values placed here in this figure?</p>
  <p>Edit: I found an error that made the values way above 1. The error is now fixed. The values are now below 1, which is good. But why am I not getting the values indicated in this figure?</p>
  <p>Please give some insights.</p>
  
Tags: <reinforcement-learning><value-functions><bellman-equations><value-iteration>
Title: calculating the value of a state in an optimal policy analytically and iteratively
UserDisplayName: cgo
ThreadText: # calculating the value of a state in an optimal policy analytically and iteratively
  
  (Asked by: username_0 on 2022-02-18)
  
  I am watching the lecture by Abbeel on MDPs and Reinforcement Learning. The setup of the problem is the classic gridworld with optimal policy (and corresponding values of states) pictured below. [![enter image description here](https://i.sstatic.net/PU3VJ.png)](https://i.sstatic.net/PU3VJ.png)
  
  The parameters of the problem here are: there is a 0.8 chance that you go to your chosen action and 0.1 chance you go to a direction perpendicular to it. For example, if you choose "right", then you have a 0.8 chance of going right and a 0.1 chance of going up, and another 0.1 chance of going down. If the action makes the agent 'bump' into the wall or 'leave' the world, then the agent stays in the same place.
  
  My question is this: Since the problem above shows the optimal policy (having solved/demonstrated the solution via the Value Iteration algorithm), is it possible that I solve for the values of the states manually (analytically), knowing that the optimal policy is give above? I expected that if I setup the (system of) equations, I should be able to recover the values that are printed in the figure above.
  
  I represented the states of the gridworld as follows. $X$ is just a place holder since it is a blocked state.
  
  $\begin{array}{cccc} H & D & A & +1 \\ G &X & B & -1 \\ F & E & C & J \end{array}$
  
  Knowing that $V^{\pi}(s) = \displaystyle\sum\_{a} \pi(a|S) \displaystyle\sum\_{s'} P(s'|s,a) [r\_{t+1} + \gamma V^{\pi}(s')]$, $\gamma = 0.9$, there are no rewards awarded for every step except with entering the terminal states $+1$ and $-1$.
  
  The actions are already deterministic at this point, so I set $\pi(a|s) = 1$.
  For simplicity of notation, I just wrote $A$ as the value of state $A$ in the following equations:
  
  At state $A$: $A = 0.8[1+0] + 0.1[0.9A] + 0.1[0.9B]$.
  Meaning: 0.8 chance of going right, receiving a reward of 1, and the value of the terminal state is 0. 0.1 change of going up and therefore ending up in the same state $A$. Finally, 0.1 chance of going down, ending up in state $B$.
  
  Another example: $H = 0.8[0.9D] + 0.1[0.9H] + 0.1[0.9G]$
  Meaning: 0.8 chance to move right to D, 0.1 chance to bump the upper wall and stay in H, another 0.1 chance to move down the lower state G.
  
  There are a total of 9 equations of this form. When I solved for the unknowns $A,B,\cdots,J$, why am I not getting the values placed here in this figure?
  
  Edit: I found an error that made the values way above 1. The error is now fixed. The values are now below 1, which is good. But why am I not getting the values indicated in this figure?
  
  Please give some insights.
  
  **Tags:** reinforcement-learning, value-functions, bellman-equations, value-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-02-18. Score: 3 | Accepted answer
  
  In the gridworld setting, you can replicate the lecture's results, by defining the reward function $R\_t(s,a) = R(s)$, meaning that the reward function simply aggregates only on the current state and ignores the selected action and the next state, as well. With this modification, the state value of a terminal state always (after the 1st iteration) equals its reward (+1 or -1).
  
  However, this is not very common in MDP implementations (e.g. in gym envs). I think that when this is the case, it should always be highlighted.
  
  > **Comments:**
  > **username_2**: Another way to put this: The states in boxes with +1 and -1 reward for leaving them are *not* the terminal states. The terminal state occurs when taking any action from those states (which also grants the associated reward), and is not shown on the grid. How can you tell they are not terminal states? Because they have a non-zero value. Terminal states have 0 value by definition (because nothing happens after the agent enters them)  
  > **username_1**: Exactly. There is a little confusion on the definition of Q and V among books and lecture slides.  
  > **username_0**: @username_2 Yes! I found this out while performing the lengthy and tedious computation. I think this is something that should be said especially when you are learning MDP for the first time to avoid this grand confusion.  
  
  ---
  
  