I was reading Andrew Ng's lecture notes on reinforcement learning, and I 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 maxima, 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_1$, 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^{(1)} := V^{\pi_1}(s)$

Where V^{(1)} is the value function for the first iteration. Then after the second step we choose some new policy $\pi_2$ to increase the value of $V^{\pi_1}(s)$. Now, with the new policy $\pi_2$, if we do do the second step of the algorithm the following inequality holds true:

$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')$

Because we choose $\pi_2$ in the second step to increase the value function in the previous step (i.e. to improve $V^{(1)}$. So far, its clear that choosing $\pi_2$ can only increase V^{(1)}, because thats how we choose $\pi_2$. However, my confusion comes in the repeat step because once we repeat and go back to step 1, we actually change things completely because we re-calculate $V^{2}$ for the new policy $\pi_2$. Which gives:

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

but its is NOT:

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

Which seems to be a problem because $\pi_2$ was chosen to improve $V^{(1)}$, and not this new $V^{\pi_2}$. Basically the problem is that $pi_2$ guarantees to improve $R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$ by doing $\pi_2$ instead of $pi_1$ when the value function is $V^{\pi_1}$. But in the repeat step we change $V^{\pi_1}$ to $V^{\pi_2}$, but I don't see how that guarantees that the value function improves monotonically at each repeat because $\pi_2$ was calculated to improve the value function when the value functions stay at $V^{\pi_1}$, but step 1 changes $V^{\pi_1}$ to $V^{\pi_2}$ (which is bad because I $\pi_2$ only improved the previous value function we had).