<p>Policy iteration means to improve the policy step by step, so that <span class="math-container">$v_{\pi}(x_{k}) \leq v_{\pi'}(x_{k})$</span> for all <span class="math-container">$x \in X$</span>. If we have <span class="math-container">$v_{\pi}(x_{k}) = v_{\pi'}(x_{k})$</span> for all <span class="math-container">$x \in X$</span>, this means that we do not need to iterate the policy any further since the resulting actions of <span class="math-container">$\pi$</span> and <span class="math-container">$\pi'$</span> are of the same quality and so we have already found the optimal policy. As you mentioned
<span class="math-container">\begin{equation}
\pi'(x_{k}) = \underset{u_{k}\in U}{\mathrm{argmax}}~q_{\pi}(x_{k}, u_{k})
\end{equation}</span>
and also, since we are using a greedy policy (s. Sutton-Barto eq. 3.18 for the last equality sign and <a href="https://ai.stackexchange.com/a/38864/67543">this answer</a> for a step-to-step derivation)
<span class="math-container">\begin{equation}
v_{\pi'}(x_{k}) = v_{\pi}(x_{k}) = \max_{u_{k}\in U} q_{\pi}(x_{k}, u_{k}).
\end{equation}</span>
From here it follows
<span class="math-container">\begin{align}
v_{\pi'}(x_{k}) = \max_{u_{k}\in U} q_{\pi}(x_{k}, u_{k}) =\max_{u_{k}} \mathbb{E} [R_{k+1} + \gamma v_{\pi}(X_{k+1})|X_{k} =x_{k}, U_{k}=u_{k}]
\end{align}</span>
and since the equality <span class="math-container">$v_{\pi}(x_{k}) = v_{\pi'}(x_{k})$</span> for all <span class="math-container">$x_{k} \in X$</span> we can do the final step:
<span class="math-container">\begin{align}
v_{\pi'}(x_{k}) = \max_{u_{k}\in U} q_{\pi}(x_{k}, u_{k}) =\max_{u_{k}} \mathbb{E} [R_{k+1} + \gamma v_{\pi'}(X_{k+1})|X_{k} =x_{k}, U_{k}=u_{k}]
\end{align}</span></p>
<p><strong>Edit: This is the answer I posted to an older version of the question, where it was not clear that OP wanted to know how to derive the first line, but I rather assumed that the simplification between line one and two was asked to explain.<br></strong>
The second line in your equation is actually just the matrix notation (s. slide 9 in your document) of the first one and shows how to build the expectation value.
<span class="math-container">\begin{align}
v_{\pi'}(x_{k}) &amp;= \max\limits_{u_{k} \in U} \mathbb{E} [R_{k+1} + \gamma v_{\pi'}(X_{k+1})|X_{k}=x_{k}, U_{k}=u_{k}] \\
&amp;= \max\limits_{u_{k}} R^{u}_{x} + \gamma \mathbb{E} [v_{\pi'}(X_{k+1})|X_{k}=x_{k}, U_{k}=u_{k}] \\
&amp;= \max\limits_{u_{k}} R^{u}_{x} + \gamma \sum_{x_{k+1} \in X}p(x_{k+1} | x_{k}, u_{k}) v_{\pi'}(x_{k+1}) \\
&amp;=\max\limits_{u_{k}} R^{u}_{x} + \gamma \sum_{x_{k+1} \in X}p^{u}_{xx'} v_{\pi'}(x_{k+1})
\end{align}</span></p>
<p>In the first step, we just build build the expectation value over the reward and moved <span class="math-container">$\gamma$</span> out of the expectation value. Then Just build the expecatation value, so calculate the value function of a given state <span class="math-container">$x_{k+1}$</span> with the probability of ending up there. Then finally, just change the notation to fit with the standard notation provided by OP.</p>

CC BY-SA 4.0
2023-02-04T23:03:43.050Z
@DSPinfinity Thanks for the clarification, I updated the answer
pythonic833
CC BY-SA 4.0
2023-02-05T10:33:19.833Z
Thank you for your efforts but I think still the answer is not correct. In your answer you say "since we have found the optimal policy ", but that is what you want to show!.
DSPinfinity
CC BY-SA 4.0
2023-02-05T10:42:31.980Z
So first, if you are using a procedure that leads to the optimal policy and your policy converges, so $v_{\pi}(x) = v_{\pi'}(x)$ for all $x$, then you found the optimal policy. Second, this equation holds even for a non-optimal but greedy, deterministic policy.
pythonic833
CC BY-SA 4.0
2023-02-05T11:02:38.063Z
I've updated my answer to just refer to a greedy policy and linked an answer where a step-to-step derivation is shown. Note that this step-to-step derivation mentions the optimal policy but doesn't assume any properties that are only valid for the optimal and not for non-optimal case.
pythonic833
CC BY-SA 4.0
2023-02-06T11:42:12.540Z
You can use `\leq` or `\geq` instead of `<=` and `>=` ;)
nbro
CC BY-SA 4.0
2023-02-03T05:34:21.287Z
I updated the question and the points not clear for me. Could you please update your answer also?
DSPinfinity
CC BY-SA 4.0
2023-02-02T22:00:34.717Z
2023-02-06T11:43:34.190Z
2023-02-06T11:43:34.190Z
pythonic833
<p>I did not understand how the equation below is obtained. Ie,
how is the first line obtained and where is the information <span class="math-container">$v_{\pi}(x_k)=v_{\pi'}(x_k)$</span> used in the derivation regarding greedy policy?</p>
<hr />
<p><a href="https://i.sstatic.net/ElI8I.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ElI8I.png" alt="enter image description here" /></a></p>
<p>where <span class="math-container">$\pi^{\prime}(x_k)=argmax_{u_k \in \mathcal{U}}q_{\pi}(x_k, u_k)$</span>.</p>
<hr />
<p>Note: the source of the above equation is slide 22, at the follwing link:
<a href="https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf" rel="nofollow noreferrer">https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf</a></p>

CC BY-SA 4.0
2023-02-04T13:06:31.580Z
I did. I will be happy if you can provide an answer to this question as a top expert in RL.
DSPinfinity
CC BY-SA 4.0
2023-02-04T17:33:53.227Z
I don't know why they didn't use the more common notation $s$ and $a$ to denote states and actions, respectively. Anyway, I'll check your question later (if I don't forget).
nbro
CC BY-SA 4.0
2023-02-03T11:21:59.000Z
Can you please put your **specific question** in the title? You can also use mathjax in the title
nbro
<reinforcement-learning><policy-improvement>
How is the first line obtained and where is the information $v_{\pi}(x_k)=v_{\pi'}(x_k)$ used in the following derivation regarding greedy policy?
DSPinfinity
# How is the first line obtained and where is the information $v_{\pi}(x_k)=v_{\pi'}(x_k)$ used in the following derivation regarding greedy policy?

(Asked by: username_0 on 2023-02-02)

I did not understand how the equation below is obtained. Ie,
how is the first line obtained and where is the information $v\_{\pi}(x\_k)=v\_{\pi'}(x\_k)$ used in the derivation regarding greedy policy?

---

[![enter image description here](https://i.sstatic.net/ElI8I.png)](https://i.sstatic.net/ElI8I.png)

where $\pi^{\prime}(x\_k)=argmax\_{u\_k \in \mathcal{U}}q\_{\pi}(x\_k, u\_k)$.

---

Note: the source of the above equation is slide 22, at the follwing link:
<https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf>

**Tags:** reinforcement-learning, policy-improvement

> **Comments:**
> **username_1**: Can you please put your **specific question** in the title? You can also use mathjax in the title  
> **username_0**: I did. I will be happy if you can provide an answer to this question as a top expert in RL.  
> **username_1**: I don't know why they didn't use the more common notation $s$ and $a$ to denote states and actions, respectively. Anyway, I'll check your question later (if I don't forget).  

---

## 1 answers

### Answer by username_2 on 2023-02-02. Score: 2 | Accepted answer

Policy iteration means to improve the policy step by step, so that $v\_{\pi}(x\_{k}) \leq v\_{\pi'}(x\_{k})$ for all $x \in X$. If we have $v\_{\pi}(x\_{k}) = v\_{\pi'}(x\_{k})$ for all $x \in X$, this means that we do not need to iterate the policy any further since the resulting actions of $\pi$ and $\pi'$ are of the same quality and so we have already found the optimal policy. As you mentioned
\begin{equation}
\pi'(x\_{k}) = \underset{u\_{k}\in U}{\mathrm{argmax}}~q\_{\pi}(x\_{k}, u\_{k})
\end{equation}
and also, since we are using a greedy policy (s. Sutton-Barto eq. 3.18 for the last equality sign and [this answer](https://ai.stackexchange.com/a/38864/67543) for a step-to-step derivation)
\begin{equation}
v\_{\pi'}(x\_{k}) = v\_{\pi}(x\_{k}) = \max\_{u\_{k}\in U} q\_{\pi}(x\_{k}, u\_{k}).
\end{equation}
From here it follows
\begin{align}
v\_{\pi'}(x\_{k}) = \max\_{u\_{k}\in U} q\_{\pi}(x\_{k}, u\_{k}) =\max\_{u\_{k}} \mathbb{E} [R\_{k+1} + \gamma v\_{\pi}(X\_{k+1})|X\_{k} =x\_{k}, U\_{k}=u\_{k}]
\end{align}
and since the equality $v\_{\pi}(x\_{k}) = v\_{\pi'}(x\_{k})$ for all $x\_{k} \in X$ we can do the final step:
\begin{align}
v\_{\pi'}(x\_{k}) = \max\_{u\_{k}\in U} q\_{\pi}(x\_{k}, u\_{k}) =\max\_{u\_{k}} \mathbb{E} [R\_{k+1} + \gamma v\_{\pi'}(X\_{k+1})|X\_{k} =x\_{k}, U\_{k}=u\_{k}]
\end{align}

**Edit: This is the answer I posted to an older version of the question, where it was not clear that OP wanted to know how to derive the first line, but I rather assumed that the simplification between line one and two was asked to explain.**
The second line in your equation is actually just the matrix notation (s. slide 9 in your document) of the first one and shows how to build the expectation value.
\begin{align}
v\_{\pi'}(x\_{k}) &= \max\limits\_{u\_{k} \in U} \mathbb{E} [R\_{k+1} + \gamma v\_{\pi'}(X\_{k+1})|X\_{k}=x\_{k}, U\_{k}=u\_{k}] \\
&= \max\limits\_{u\_{k}} R^{u}\_{x} + \gamma \mathbb{E} [v\_{\pi'}(X\_{k+1})|X\_{k}=x\_{k}, U\_{k}=u\_{k}] \\
&= \max\limits\_{u\_{k}} R^{u}\_{x} + \gamma \sum\_{x\_{k+1} \in X}p(x\_{k+1} | x\_{k}, u\_{k}) v\_{\pi'}(x\_{k+1}) \\
&=\max\limits\_{u\_{k}} R^{u}\_{x} + \gamma \sum\_{x\_{k+1} \in X}p^{u}\_{xx'} v\_{\pi'}(x\_{k+1})
\end{align}

In the first step, we just build build the expectation value over the reward and moved $\gamma$ out of the expectation value. Then Just build the expecatation value, so calculate the value function of a given state $x\_{k+1}$ with the probability of ending up there. Then finally, just change the notation to fit with the standard notation provided by OP.

> **Comments:**
> **username_0**: I updated the question and the points not clear for me. Could you please update your answer also?  
> **username_2**: @username_0 Thanks for the clarification, I updated the answer  
> **username_0**: Thank you for your efforts but I think still the answer is not correct. In your answer you say "since we have found the optimal policy ", but that is what you want to show!.  
> **username_2**: So first, if you are using a procedure that leads to the optimal policy and your policy converges, so $v_{\pi}(x) = v_{\pi'}(x)$ for all $x$, then you found the optimal policy. Second, this equation holds even for a non-optimal but greedy, deterministic policy.  
> **username_2**: I've updated my answer to just refer to a greedy policy and linked an answer where a step-to-step derivation is shown. Note that this step-to-step derivation mentions the optimal policy but doesn't assume any properties that are only valid for the optimal and not for non-optimal case.  
> **username_1**: You can use `\leq` or `\geq` instead of `<=` and `>=` ;)  

---

