Why is the value function obtained from a greedy policy different from its original value function (i.e. $ V_k \neq V_{\pi_k } $)? Consider a vector of values $V_k$ and consider the related value $V_{\pi_k}$ obtained by coming the policy $\pi_k$ by acting greedily according to it. i.e.
$$ \pi_k(i) := arg \min_{a \in A} \{ R(i,a) + \alpha \sum_{j \in S} P_{i,j}(a ) V_k \}$$
where $P_{ij}( a ) = Pr[j \mid i, a]$
my question is why is:
$$ V_k \neq V_{\pi_k } $$
my intuition (which is obviously wrong) says that we are acting according to the value function $V_k$ so we should get the same value function out. Why is this reasoning incorrect?
Note that I am sure we could cook up a boring example that shows Im wrong. I don't want that or need that. That won't provide insights to WHY I am wrong, just that I am which I already know.
 A: Your intuition is off because the policy $\pi$ used to form $V_k$ (or what I will denote as $V^{\pi}$) will actually be different than the policy $\pi_k$ if $\pi$ is not optimal. We can show they will be different in the event $\pi$ is not optimal by investigating the following. We can first state the following definitions
\begin{align}
V^{\pi}(s) &= R(s, \pi(s)) + \gamma \mathbb{E}_{s' \sim P(s,\pi(s))} \left[V^{\pi}(s')\right] \\
Q^{\pi}(s,a) &= R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right]
\end{align}
If we make note of the above definitions, it is clear that $V^{\pi}(s) = Q^{\pi}(s, \pi(s))$. We can also use these definitions to restate $\pi_k$ in the following manner
\begin{align}
\pi_k(s) &= \arg \min_{a \in A(s)} \left\lbrace R(s,a) + \gamma \mathbb{E}_{s' \sim P(s,a)} \left[V^{\pi}(s')\right] \right\rbrace \\
&= \arg \min_{a \in A(s)}  Q^{\pi}(s,a)  \\
&= \arg \min_{a \in A(s)} \left\lbrace Q^{\pi}(s,a) - Q^{\pi}(s, \pi(s))\right\rbrace
\end{align}
If we look at the final expression for $\pi_{k}(s)$, it is clear that for a given state $s$, $\pi_k(s)$ will be a better action than $\pi(s)$ unless $\pi(s)$ is already an optimal action for the given state $s$. This implies that $V^{\pi_k}(s) \leq V^{\pi}(s)$ for all $s \in S$. The way one can view it is that the $\arg \min$ step to construct $\pi_k(s)$ is effectively saying "For each state $s$, choose the action $a$ that is most optimal relative to $\pi(s)$ to make as the action choice for $\pi_k(s)$".
