Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-04T23:03:43.050Z
Answers.Text: @DSPinfinity Thanks for the clarification, I updated the answer
Answers.UserDisplayName: pythonic833
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-05T10:33:19.833Z
Answers.Text: 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!.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-05T10:42:31.980Z
Answers.Text: 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.
Answers.UserDisplayName: pythonic833
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-05T11:02:38.063Z
Answers.Text: 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.
Answers.UserDisplayName: pythonic833
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-06T11:42:12.540Z
Answers.Text: You can use `\leq` or `\geq` instead of `<=` and `>=` ;)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-03T05:34:21.287Z
Answers.Text: I updated the question and the points not clear for me. Could you please update your answer also?
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-02-02T22:00:34.717Z
Answers.LastActivityDate: 2023-02-06T11:43:34.190Z
Answers.LastEditDate: 2023-02-06T11:43:34.190Z
Answers.UserDisplayName: pythonic833
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-04T13:06:31.580Z
Comments.Text: I did. I will be happy if you can provide an answer to this question as a top expert in RL.
Comments.UserDisplayName: DSPinfinity
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-04T17:33:53.227Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-03T11:21:59.000Z
Comments.Text: Can you please put your **specific question** in the title? You can also use mathjax in the title
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><policy-improvement>
Title: 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?
UserDisplayName: DSPinfinity
ThreadText: # 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**: @DSPinfinity 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 `>=` ;)  
  
  ---
  
  