Answers.Body: <p>From S&amp;L's value iteration section:</p>
  <blockquote>
  <p>For arbitrary <span class="math-container">$v_0$</span>, the sequence <span class="math-container">$\{v_k\}$</span> can be shown to converge to <span class="math-container">$v_*$</span> under the same conditions that guarantee the existence of <span class="math-container">$v_*$</span>... value iteration is by reference to the Bellman optimality equation (4.1). Note that value iteration is obtained simply by turning the Bellman optimality equation into an update rule.</p>
  </blockquote>
  <p>Therefore to derive value iteration from policy iteration as its extremely simplified case in a step-by-step manner as requested in your updated question is to formally express the above quoted &quot;<em>turning the Bellman optimality equation into an update rule</em>&quot;. And indeed, as you commented, value iteration first does policy improvement and then policy evaluation (normally we have first policy evaluation and then policy improvement in GPI framework of RL). The key here is value iteration can only be rigorously derived from Bellman optimality equation (BOE), not from policy improvement theorem. And once you do the derivation you'll understand there's no conflict as complained in your comment.</p>
  <p>So first see BOE (4.1) as follows which is already very close to your own quoted first equation:
  <span class="math-container">$$v_*(s)=\max_{a \in \mathcal{A}}\mathbb{E} \Big(R_{t+1}+\gamma v_*(S_{t+1}) \big|S_t=s, A_t=a\Big)$$</span></p>
  <p>To derive a practical algo to solve for optimal state value <span class="math-container">$v_*$</span> in BOE is simply to turn it into an iterative update rule as hinted above in S&amp;B's book. So formally you just simply need to replace LHS's <span class="math-container">$v_*$</span> with <span class="math-container">$v_{k+1}$</span> and RHS's <span class="math-container">$v_*$</span> with <span class="math-container">$v_k$</span> which is exactly your requested equation! Your second equation is just further calculating the expectation  statistics with model-based RL.</p>
  <p>Finally note the <span class="math-container">$v_k, v_{k+1}$</span> in your value iteration are not state values themselves because there's no policy evaluation based on state value here at all, thus you cannot rely on policy improvement theorem to prove convergence. To prove convergence of value iteration as hinted above you need BOE and its contraction mapping fixed point theorem to step-by-step prove the uniqueness and convergence of its iterative solution which is entirely another question. There's a diagram from Zhao's <em>Mathematical Foundation of Reinforcement Learning</em> to illustrate the non-conflict relation between value iteration and policy iteration as follows:
  <a href="https://i.sstatic.net/ckGaJ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ckGaJ.png" alt="enter image description here" /></a></p>
  <p>And the same reference specifically warned:</p>
  <blockquote>
  <p>One problem of value iteration that may confuse beginners is whether <span class="math-container">$v_k$</span> is a state value. The answer is no although <span class="math-container">$v_k$</span>  converges to the optimal state value <span class="math-container">$v_*$</span> eventually. That is because <span class="math-container">$v_k$</span> is not guaranteed to satisfy any Bellman equation... This might be one of the most confusing problems for beginners studying this algorithm. It is easier if we simply treat them as intermediate variables that emerge when solving the BOE.</p>
  </blockquote>
  <p>That's why strictly speaking one shouldn't say policy improve (PI) in value iteration since there's no policy improvement theorem without state values evaluation (note all <span class="math-container">$v_k$</span>'s in value iteration has no subscript <span class="math-container">$\pi$</span> compared to policy iteration), one should only say policy update (PU) in value iteration though it's also consistent with GPI (generalized policy iteration) as shown in above diagram.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T10:04:05.953Z
Answers.Text: unfortunately your explanations are  not clear for me. I want to see the equivalence through a step by step mathematical derivation.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T13:54:20.597Z
Answers.Text: What do you mean by $v_k$ and $v_{k+1}$ are not state values? Are you using ChatGPT or similar to generate your answers? They are what then? Unicorns?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T14:25:07.907Z
Answers.Text: @Neil Slater,  could you please help answer this question?
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T21:54:55.890Z
Answers.Text: A good explanation is in this video but here it seems that now first policy improvement and then policy evaluation (normally, we have first policy evaluation and then policy improvement):  https://www.youtube.com/watch?v=64RljWXMpko
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-13T05:44:40.853Z
Answers.Text: @DSPinfinity Your last comment makes sense and I edited to simplify my answer and tried to meet your added step-by-step derivation request.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-13T07:25:54.763Z
Answers.Text: @cinch, your answer does not provide a proof: you cannot use what is to be proved in mathematical proofs.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-12T05:14:07.100Z
Answers.LastActivityDate: 2024-03-13T05:48:37.670Z
Answers.LastEditDate: 2024-03-13T05:48:37.670Z
Answers.UserDisplayName: cinch
Body: <p>This is the equation for &quot;value iteration&quot; from Sutton-Barto:</p>
  <p><span class="math-container">\begin{align}
  v_{k+1}(s)=&amp; \max_{a \in \mathcal{A}}\mathbb{E} \Big(R_{t+1}+\gamma v_k(S_{t+1}) \big|S_t=s, A_t=a\Big) \\
  =&amp; \max_{a \in \mathcal{A}}\bigg\{
  \mathcal{R}_s^a+\gamma\sum_{s'\in \mathcal{S}}\mathcal{P}_{ss'}^av_{k}(s')\bigg\}
  \end{align}</span></p>
  <p>It is said that this is a special case of &quot;policy iteration&quot; when policy evaluation is stopped after just one sweep (one update of each state).  I do not understand how this gives rise to the value iteration equation above. Can someone provide a step-by-step mathematical derivation of value iteration from policy iteration with one sweep?</p>
  
Tags: <reinforcement-learning><value-functions><sutton-barto><value-iteration><policy-iteration>
Title: How to derive "value iteration" from "policy iteration"?
UserDisplayName: DSPinfinity
ThreadText: # How to derive "value iteration" from "policy iteration"?
  
  (Asked by: username_0 on 2024-03-12)
  
  This is the equation for "value iteration" from Sutton-Barto:
  
  \begin{align}
  v\_{k+1}(s)=& \max\_{a \in \mathcal{A}}\mathbb{E} \Big(R\_{t+1}+\gamma v\_k(S\_{t+1}) \big|S\_t=s, A\_t=a\Big) \\
  =& \max\_{a \in \mathcal{A}}\bigg\{
  \mathcal{R}\_s^a+\gamma\sum\_{s'\in \mathcal{S}}\mathcal{P}\_{ss'}^av\_{k}(s')\bigg\}
  \end{align}
  
  It is said that this is a special case of "policy iteration" when policy evaluation is stopped after just one sweep (one update of each state). I do not understand how this gives rise to the value iteration equation above. Can someone provide a step-by-step mathematical derivation of value iteration from policy iteration with one sweep?
  
  **Tags:** reinforcement-learning, value-functions, sutton-barto, value-iteration, policy-iteration
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-03-12. Score: -2
  
  From S&L's value iteration section:
  
  > For arbitrary $v\_0$, the sequence $\{v\_k\}$ can be shown to converge to $v\_\*$ under the same conditions that guarantee the existence of $v\_\*$... value iteration is by reference to the Bellman optimality equation (4.1). Note that value iteration is obtained simply by turning the Bellman optimality equation into an update rule.
  
  Therefore to derive value iteration from policy iteration as its extremely simplified case in a step-by-step manner as requested in your updated question is to formally express the above quoted "*turning the Bellman optimality equation into an update rule*". And indeed, as you commented, value iteration first does policy improvement and then policy evaluation (normally we have first policy evaluation and then policy improvement in GPI framework of RL). The key here is value iteration can only be rigorously derived from Bellman optimality equation (BOE), not from policy improvement theorem. And once you do the derivation you'll understand there's no conflict as complained in your comment.
  
  So first see BOE (4.1) as follows which is already very close to your own quoted first equation:
  $$v\_\*(s)=\max\_{a \in \mathcal{A}}\mathbb{E} \Big(R\_{t+1}+\gamma v\_\*(S\_{t+1}) \big|S\_t=s, A\_t=a\Big)$$
  
  To derive a practical algo to solve for optimal state value $v\_\*$ in BOE is simply to turn it into an iterative update rule as hinted above in S&B's book. So formally you just simply need to replace LHS's $v\_\*$ with $v\_{k+1}$ and RHS's $v\_\*$ with $v\_k$ which is exactly your requested equation! Your second equation is just further calculating the expectation statistics with model-based RL.
  
  Finally note the $v\_k, v\_{k+1}$ in your value iteration are not state values themselves because there's no policy evaluation based on state value here at all, thus you cannot rely on policy improvement theorem to prove convergence. To prove convergence of value iteration as hinted above you need BOE and its contraction mapping fixed point theorem to step-by-step prove the uniqueness and convergence of its iterative solution which is entirely another question. There's a diagram from Zhao's *Mathematical Foundation of Reinforcement Learning* to illustrate the non-conflict relation between value iteration and policy iteration as follows:
  [![enter image description here](https://i.sstatic.net/ckGaJ.png)](https://i.sstatic.net/ckGaJ.png)
  
  And the same reference specifically warned:
  
  > One problem of value iteration that may confuse beginners is whether $v\_k$ is a state value. The answer is no although $v\_k$ converges to the optimal state value $v\_\*$ eventually. That is because $v\_k$ is not guaranteed to satisfy any Bellman equation... This might be one of the most confusing problems for beginners studying this algorithm. It is easier if we simply treat them as intermediate variables that emerge when solving the BOE.
  
  That's why strictly speaking one shouldn't say policy improve (PI) in value iteration since there's no policy improvement theorem without state values evaluation (note all $v\_k$'s in value iteration has no subscript $\pi$ compared to policy iteration), one should only say policy update (PU) in value iteration though it's also consistent with GPI (generalized policy iteration) as shown in above diagram.
  
  > **Comments:**
  > **username_0**: unfortunately your explanations are  not clear for me. I want to see the equivalence through a step by step mathematical derivation.  
  > **username_2**: What do you mean by $v_k$ and $v_{k+1}$ are not state values? Are you using ChatGPT or similar to generate your answers? They are what then? Unicorns?  
  > **username_0**: @Neil Slater,  could you please help answer this question?  
  > **username_0**: A good explanation is in this video but here it seems that now first policy improvement and then policy evaluation (normally, we have first policy evaluation and then policy improvement):  https://www.youtube.com/watch?v=64RljWXMpko  
  > **username_1**: @DSPinfinity Your last comment makes sense and I edited to simplify my answer and tried to meet your added step-by-step derivation request.  
  > **username_0**: @cinch, your answer does not provide a proof: you cannot use what is to be proved in mathematical proofs.  
  
  ---
  
  