Answers.Body: <p>First thing to know is that, in this case, values for the gridworld in new iteration are completely calculated with respect to the old values from the previous iteration. Value of <span class="math-container">$0.78$</span> is got like this:  </p>
  
  <p><span class="math-container">$0.9 \cdot (0.8 \cdot 1 + 0.1 \cdot 0.72 + 0.1 \cdot 0) = 0.7848 \approx 0.78$</span>  </p>
  
  <p>term <span class="math-container">$0.8 \cdot 1$</span> is for going to the right with probability of <span class="math-container">$0.8$</span> and getting reward of <span class="math-container">$1$</span>.  </p>
  
  <p>term <span class="math-container">$0.1 \cdot 0.72$</span> is for going up with probability of <span class="math-container">$0.1$</span>, we hit the wall and stay in the same field which value is <span class="math-container">$0.72$</span> (from previous iteration)  </p>
  
  <p>term <span class="math-container">$0.1 \cdot 0$</span> is for going down with probability of <span class="math-container">$0.1$</span>, even though value of that field in the image is <span class="math-container">$0.43$</span> we take the value from previous iteration which is <span class="math-container">$0$</span>.  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-12T22:05:07.810Z
Answers.LastActivityDate: 2019-03-12T22:05:07.810Z
Answers.UserDisplayName: Brale
Answers.Body: <p>In second iteration,</p>
  <p>using the bellman equation,</p>
  <p>for (3,3), we got <strong>0.8[0+(0.9)(1)]+0.1[0+(0.9)(0.72)]+0.1[0+(0.9)(0)] = 0.78</strong></p>
  <p>for (3,2), we got <strong>0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(-1)] = 0.43</strong></p>
  <p>for (2,3), we got <strong>0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(0)] = 0.52</strong></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-03T07:04:09.573Z
Answers.LastActivityDate: 2024-07-03T07:07:11.973Z
Answers.LastEditDate: 2024-07-03T07:07:11.973Z
Answers.UserDisplayName: Md. Foysal Ahmed
Body: <p>I am trying to understand the value iteration method for Markov Decision Process(MDP) and I was referring to UC Berkeley's slides titled <a href="https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/mdps-exact-methods.pdf" rel="nofollow noreferrer">Markov Decision Processes and Exact Solution Methods</a></p>
  <p>On slide no. 9, we start with the first step :</p>
  <p><a href="https://i.sstatic.net/5Jyh2.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5Jyh2.jpg" alt="enter image description here" /></a></p>
  <p>Ok! So, we have the information about the transition function (described elaborately in slide no. 5 as well), the <strong>resting reward is 0</strong> and <strong>discount of 0.9</strong>.</p>
  <p>Using this, I am able to compute the <em>utility value</em> of the cell left to terminal state with R = +1 (Green cell). The action that is going to be most rewarding at this cell is moving forward, so putting the values in the equation as:</p>
  <p><span class="math-container">$$0.0 + 0.9 (0.8*1 + 0.1*0 + 0.1*0) =0.72$$</span></p>
  <p>which seems to be correct:</p>
  <p><a href="https://i.sstatic.net/LCQzx.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/LCQzx.jpg" alt="enter image description here" /></a></p>
  <p>Now, using the same algorithm I am able to compute the value of the cells adjacent to this newly obtained utility cell value. However, I really do not know how did they update the value from</p>
  <blockquote>
  <p>0.72 -&gt; 0.78</p>
  </blockquote>
  <p>in the next slide:</p>
  <p><a href="https://i.sstatic.net/8lgsJ.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8lgsJ.jpg" alt="enter image description here" /></a></p>
  <p>I have tried searching at various sites and seen some videos but most of them stop at the first iteration assuming the next step is the same, as it is a recursive equation (And it should have been so!), but I am stuck at this!</p>
  
Tags: <reinforcement-learning><markov-decision-process><value-iteration>
Title: Unable to understand the second iteration update in value iteration algorithm for solving MDP
UserDisplayName: Devendra Vyas
ThreadText: # Unable to understand the second iteration update in value iteration algorithm for solving MDP
  
  (Asked by: username_0 on 2019-03-12)
  
  I am trying to understand the value iteration method for Markov Decision Process(MDP) and I was referring to UC Berkeley's slides titled [Markov Decision Processes and Exact Solution Methods](https://people.eecs.berkeley.edu/%7Epabbeel/cs287-fa12/slides/mdps-exact-methods.pdf)
  
  On slide no. 9, we start with the first step :
  
  [![enter image description here](https://i.sstatic.net/5Jyh2.jpg)](https://i.sstatic.net/5Jyh2.jpg)
  
  Ok! So, we have the information about the transition function (described elaborately in slide no. 5 as well), the **resting reward is 0** and **discount of 0.9**.
  
  Using this, I am able to compute the *utility value* of the cell left to terminal state with R = +1 (Green cell). The action that is going to be most rewarding at this cell is moving forward, so putting the values in the equation as:
  
  $$0.0 + 0.9 (0.8\*1 + 0.1\*0 + 0.1\*0) =0.72$$
  
  which seems to be correct:
  
  [![enter image description here](https://i.sstatic.net/LCQzx.jpg)](https://i.sstatic.net/LCQzx.jpg)
  
  Now, using the same algorithm I am able to compute the value of the cells adjacent to this newly obtained utility cell value. However, I really do not know how did they update the value from
  
  > 0.72 -> 0.78
  
  in the next slide:
  
  [![enter image description here](https://i.sstatic.net/8lgsJ.jpg)](https://i.sstatic.net/8lgsJ.jpg)
  
  I have tried searching at various sites and seen some videos but most of them stop at the first iteration assuming the next step is the same, as it is a recursive equation (And it should have been so!), but I am stuck at this!
  
  **Tags:** reinforcement-learning, markov-decision-process, value-iteration
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-03-12. Score: 2 | Accepted answer
  
  First thing to know is that, in this case, values for the gridworld in new iteration are completely calculated with respect to the old values from the previous iteration. Value of $0.78$ is got like this:
  
  $0.9 \cdot (0.8 \cdot 1 + 0.1 \cdot 0.72 + 0.1 \cdot 0) = 0.7848 \approx 0.78$
  
  term $0.8 \cdot 1$ is for going to the right with probability of $0.8$ and getting reward of $1$.
  
  term $0.1 \cdot 0.72$ is for going up with probability of $0.1$, we hit the wall and stay in the same field which value is $0.72$ (from previous iteration)
  
  term $0.1 \cdot 0$ is for going down with probability of $0.1$, even though value of that field in the image is $0.43$ we take the value from previous iteration which is $0$.
  
  
  ---
  
  ### Answer by username_2 on 2024-07-03. Score: 0
  
  In second iteration,
  
  using the bellman equation,
  
  for (3,3), we got **0.8[0+(0.9)(1)]+0.1[0+(0.9)(0.72)]+0.1[0+(0.9)(0)] = 0.78**
  
  for (3,2), we got **0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(-1)] = 0.43**
  
  for (2,3), we got **0.8[0 + 0.9(0.72)] + 0.1[0 + 0.9(0)] + 0.1[0 + 0.9(0)] = 0.52**
  
  
  ---
  
  