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.