Answers.Body: <p>The value iteration algorithm defines the following update rule (reference is slide 11 in <a href="https://web.mit.edu/1.041/www/lectures/L15-value-iteration-2021fa-pre.pdf" rel="nofollow noreferrer">this MIT course</a>):
  <span class="math-container">$$V_{i+1}(s) = \max_{a}\{R(s,a) + \gamma E_{s'\sim T(.|s,a)} V_i(s')\}$$</span>
  for all states <span class="math-container">$s$</span>, with <span class="math-container">$E_{s'\sim T(.|s,a)} V_i(s') = \sum_{s'} T(s'|s,a)V_i(s')$</span>. I adapted the transition probability name from <span class="math-container">$P$</span> to <span class="math-container">$T$</span> to conform with your notation.</p>
  <p>Note the index <span class="math-container">$i$</span> for the value function on the right hand side of the equations. That's what enables you to do the computations: the value of the state at iteration <span class="math-container">$i+1$</span> is calculated recursively from the values at iteration <span class="math-container">$i$</span>.</p>
  <p>We also have <span class="math-container">$\max_a R(a,s) =$</span> reward for reaching the state, given that the reward assigned to each state doesn't depend on the action which was taken in your example. Therefore the value iteration update rule simplifies to:
  <span class="math-container">$$V_{i+1}(s) = R(s) + \gamma \max_a \{\sum_{s'} T(s'|s,a)V_i(s')\}$$</span></p>
  <p>If you initialize <span class="math-container">$V_0(s)$</span> to the value of the reward function for that state, we have: <span class="math-container">$V_0(S_0) = 1$</span>, <span class="math-container">$V_0(S_1) = -1$</span>, <span class="math-container">$V_0(S_2) = -2$</span>.</p>
  <p>Then for <span class="math-container">$S_0$</span>:
  <span class="math-container">$$\begin{align} V_1(S_0) = R(S_0)  + \gamma \max \{ &amp; T(S_0| a_1, S_0) V_0(S_0) + T(S_2 | a_1, S_0)V_0(S_2); \\ &amp; T(S_0 | a_2, S_0) V_0(S_0) + T(S_1| a_2, S_0) V_0(S_1)\}\end{align}$$</span>
  where the first term in the <span class="math-container">$\max$</span> is the expected value if you take action <span class="math-container">$a_1$</span> from state <span class="math-container">$S_0$</span> and the second term is the expected value if you take action <span class="math-container">$a_2$</span> from state <span class="math-container">$S_0$</span>.</p>
  <p>This gives, with <span class="math-container">$\gamma = 0.2$</span>
  <span class="math-container">$$\begin{align}V_1(S_0) &amp; = 1 + 0.2 * \max \{0.5*1 + 0.5 *-2; 0.2*1 + 0.8*-1\} \\ &amp; = 1 + 0.2 * \max \{-0.5; -0.6\} \\ &amp; = 1 - 0.2*0.5 = 0.9\end{align}$$</span>.</p>
  <p>Similarly for <span class="math-container">$S_1$</span>:
  <span class="math-container">$$\begin{align} V_1(S_1) = R(S_1)  + \gamma \max \{ &amp; T(S_1| a_3, S_1) V_0(S_1) + T(S_0 | a_3, S_1)V_0(S_0); \\ &amp; T(S_1 | a_5, S_1) V_0(S_1)\}\end{align}$$</span>
  which gives:
  <span class="math-container">$$\begin{align}V_1(S_1) &amp; = -1 + 0.2 * \max \{0.3*-1 + 0.7*1; 1*-1\} \\ &amp; = -1 + 0.2 * \max \{0.4; -1\} \\ &amp; = -1 + 0.2*0.4 = -0.92\end{align}$$</span></p>
  <p>And finally for <span class="math-container">$S_2$</span>:
  <span class="math-container">$$\begin{align} V_1(S_2) = R(S_2)  + \gamma \max \{ &amp; T(S_2| a_3, S_2) V_0(S_2) + T(S_0 | a_3, S_2)V_0(S_0); \\ &amp; T(S_1 | a_4, S_2) V_0(S_1)\}\end{align}$$</span>
  which gives:
  <span class="math-container">$$\begin{align}V_1(S_2) &amp; = -2 + 0.2 * \max \{0.2*-2 + 0.8*1; 1*-1\} \\ &amp; = -2 + 0.2 * \max \{0.4; -1\} \\ &amp; = -2 + 0.2*0.4 = -1.92\end{align}$$</span></p>
  <p>To get the values at the next iteration, you can reuse the equations above incrementing the indices by one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-01T21:06:27.393Z
Answers.LastActivityDate: 2022-08-01T21:06:27.393Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Body: <p>I have the following decision tree:</p>
  <p><a href="https://i.sstatic.net/aLCaH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aLCaH.png" alt="enter image description here" /></a></p>
  <p>I calculated the value of the plan using the following paramenters (given):
  {0 → 1 , 1 → 3 , 2 → 4 },
  Discount factor ()= 0.2</p>
  <p>I used this formula to calculate the linear equations to find the value of the plan:
   =  +  ∑ ( ,  ,  )</p>
  <p>Linear equations:</p>
  <p>V0 = 1 + 0.2 (0.5 V0 + 0.5 V2 )</p>
  <p>V1 = -1 + 0.2 (0.7 V0 + 0.3 V1)</p>
  <p>V2 = -2 + 0.2 (1 V1 )</p>
  <p><strong>Now I need to calculate the first three iterations of the value-iteration algorithm, if a discount factor of 0.2 is used and starting initially (iteration 0) with state values all equal to 0. And write it in below format</strong>:</p>
  <p>S0 = {Value at iteration1, value at iteration2, value at iteration3}</p>
  <p>S1 = {Value at iteration1, value at iteration2, value at iteration3}</p>
  <p>S2 = {Value at iteration1, value at iteration2, value at iteration3}</p>
  <p><strong>How can I find the value at different iterations?</strong>
  I know that we can use the Bellman Equation:
  <a href="https://i.sstatic.net/1pYNy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1pYNy.png" alt="enter image description here" /></a></p>
  <p>But how do I use this equation?</p>
  <p>Thanks!</p>
  
Tags: <reinforcement-learning><machine-learning><markov-decision-process><statistics>
Title: Markov's Decision Process - calculate value in each iteration
UserDisplayName: stuckincode
ThreadText: # Markov's Decision Process - calculate value in each iteration
  
  (Asked by: username_0 on 2022-07-31)
  
  I have the following decision tree:
  
  [![enter image description here](https://i.sstatic.net/aLCaH.png)](https://i.sstatic.net/aLCaH.png)
  
  I calculated the value of the plan using the following paramenters (given):
  {0 → 1 , 1 → 3 , 2 → 4 },
  Discount factor ()= 0.2
  
  I used this formula to calculate the linear equations to find the value of the plan:
  = + ∑ ( , , )
  
  Linear equations:
  
  V0 = 1 + 0.2 (0.5 V0 + 0.5 V2 )
  
  V1 = -1 + 0.2 (0.7 V0 + 0.3 V1)
  
  V2 = -2 + 0.2 (1 V1 )
  
  **Now I need to calculate the first three iterations of the value-iteration algorithm, if a discount factor of 0.2 is used and starting initially (iteration 0) with state values all equal to 0. And write it in below format**:
  
  S0 = {Value at iteration1, value at iteration2, value at iteration3}
  
  S1 = {Value at iteration1, value at iteration2, value at iteration3}
  
  S2 = {Value at iteration1, value at iteration2, value at iteration3}
  
  **How can I find the value at different iterations?**
  I know that we can use the Bellman Equation:
  [![enter image description here](https://i.sstatic.net/1pYNy.png)](https://i.sstatic.net/1pYNy.png)
  
  But how do I use this equation?
  
  Thanks!
  
  **Tags:** reinforcement-learning, machine-learning, markov-decision-process, statistics
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-08-01. Score: 1 | Accepted answer
  
  The value iteration algorithm defines the following update rule (reference is slide 11 in [this MIT course](https://web.mit.edu/1.041/www/lectures/L15-value-iteration-2021fa-pre.pdf)):
  $$V\_{i+1}(s) = \max\_{a}\{R(s,a) + \gamma E\_{s'\sim T(.|s,a)} V\_i(s')\}$$
  for all states $s$, with $E\_{s'\sim T(.|s,a)} V\_i(s') = \sum\_{s'} T(s'|s,a)V\_i(s')$. I adapted the transition probability name from $P$ to $T$ to conform with your notation.
  
  Note the index $i$ for the value function on the right hand side of the equations. That's what enables you to do the computations: the value of the state at iteration $i+1$ is calculated recursively from the values at iteration $i$.
  
  We also have $\max\_a R(a,s) =$ reward for reaching the state, given that the reward assigned to each state doesn't depend on the action which was taken in your example. Therefore the value iteration update rule simplifies to:
  $$V\_{i+1}(s) = R(s) + \gamma \max\_a \{\sum\_{s'} T(s'|s,a)V\_i(s')\}$$
  
  If you initialize $V\_0(s)$ to the value of the reward function for that state, we have: $V\_0(S\_0) = 1$, $V\_0(S\_1) = -1$, $V\_0(S\_2) = -2$.
  
  Then for $S\_0$:
  $$\begin{align} V\_1(S\_0) = R(S\_0) + \gamma \max \{ & T(S\_0| a\_1, S\_0) V\_0(S\_0) + T(S\_2 | a\_1, S\_0)V\_0(S\_2); \\ & T(S\_0 | a\_2, S\_0) V\_0(S\_0) + T(S\_1| a\_2, S\_0) V\_0(S\_1)\}\end{align}$$
  where the first term in the $\max$ is the expected value if you take action $a\_1$ from state $S\_0$ and the second term is the expected value if you take action $a\_2$ from state $S\_0$.
  
  This gives, with $\gamma = 0.2$
  $$\begin{align}V\_1(S\_0) & = 1 + 0.2 \* \max \{0.5\*1 + 0.5 \*-2; 0.2\*1 + 0.8\*-1\} \\ & = 1 + 0.2 \* \max \{-0.5; -0.6\} \\ & = 1 - 0.2\*0.5 = 0.9\end{align}$$.
  
  Similarly for $S\_1$:
  $$\begin{align} V\_1(S\_1) = R(S\_1) + \gamma \max \{ & T(S\_1| a\_3, S\_1) V\_0(S\_1) + T(S\_0 | a\_3, S\_1)V\_0(S\_0); \\ & T(S\_1 | a\_5, S\_1) V\_0(S\_1)\}\end{align}$$
  which gives:
  $$\begin{align}V\_1(S\_1) & = -1 + 0.2 \* \max \{0.3\*-1 + 0.7\*1; 1\*-1\} \\ & = -1 + 0.2 \* \max \{0.4; -1\} \\ & = -1 + 0.2\*0.4 = -0.92\end{align}$$
  
  And finally for $S\_2$:
  $$\begin{align} V\_1(S\_2) = R(S\_2) + \gamma \max \{ & T(S\_2| a\_3, S\_2) V\_0(S\_2) + T(S\_0 | a\_3, S\_2)V\_0(S\_0); \\ & T(S\_1 | a\_4, S\_2) V\_0(S\_1)\}\end{align}$$
  which gives:
  $$\begin{align}V\_1(S\_2) & = -2 + 0.2 \* \max \{0.2\*-2 + 0.8\*1; 1\*-1\} \\ & = -2 + 0.2 \* \max \{0.4; -1\} \\ & = -2 + 0.2\*0.4 = -1.92\end{align}$$
  
  To get the values at the next iteration, you can reuse the equations above incrementing the indices by one.
  
  
  ---
  
  