I was reading Andrew Ng's lecture notes on Reinforcement learning and was trying to understand why policy iteration converged to the optimal value function $V^*$ and optimum policy $\pi^*$.

Recall policy iteration is:

$ \text{Initialize $\pi$ randomly} \\ \text{Repeat},\{\\ \quad Let \ V := V^{\pi} \text{ \\for the current policy, solve bellman's eqn's and set that to the current V}\\ \quad Let \ \pi(s) := argmax_{a \in A} \sum_{s'}P_{sa}(s') V(s')\\ \} $

Why is it that a greedy-algorithm leads to a the optimal policy and the optimal value function? (I know greedy algorithms don't always guarantee that, or might get stuck in local optima's, so I just wanted to see a proof for its optimality of the algorithm). Also, it seems to me that policy iteration is something analogous to clustering or gradient descent. To clustering, because with the current setting of the parameters, we optimize. Similar to gradient descent because it just chooses some value that seems to increase some function. These two methods don't always converge to optimal maximums and I was trying to understand how this algorithm was different from the previous ones I mentioned.

These are my thoughts so far:

Say that we start with some policy $\pi_i$, then after the first step, for that fixed policy we have that:

$ V^{\pi_1}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$

$V := V^{\pi_1}(s)$

Is the value of V. Then after the second step we choose some new policy $\pi_2$ as to increase the value of $V^{\pi_1}(s)$. Now, with the new policy $\pi_2$, the following inequality holds:

$R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s') \leq R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_1}(s')$

Since that is how we choose $\pi_2$ in the second step. So far, its clear that choosing $\pi_2$ can only increase V. However, my confusion comes in because on the next step, we actually change things completely because we re-calculate $V^{\pi_2}$ for the new policy. The thing is that, $\pi_2$ is only guaranteed to increase $V$ because of $V_{\pi}$ didn't change.