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?


1 Answer 1


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

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.

  • $\begingroup$ unfortunately your explanations are not clear for me. I want to see the equivalence through a step by step mathematical derivation. $\endgroup$ Mar 12 at 10:04
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Mar 12 at 13:54
  • $\begingroup$ @Neil Slater, could you please help answer this question? $\endgroup$ Mar 12 at 14:25
  • 1
    $\begingroup$ 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): youtube.com/watch?v=64RljWXMpko $\endgroup$ Mar 12 at 21:54
  • $\begingroup$ @DSPinfinity Your last comment makes sense and I edited to simplify my answer and tried to meet your added step-by-step derivation request. $\endgroup$
    – cinch
    Mar 13 at 5:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .