Why does the policy iteration algorithm converge to optimal policy and value function?

Question

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).

Answer 1

I think the part you are missing is that $V^{\pi_2} \ge V^{\pi_1}$ is guaranteed for the same reason we can order $\pi_2 \ge \pi_1$. That is the essentially the definition of one policy being better than another - that its value function is greater or equal in all states. You have guaranteed this by choosing the maximising actions - no state value can possibly be worse than it was before, and if just one action choice has changed to choose a better maximising action, then you already know (but may not have calculated) that the $V^{\pi_2}(s)$ for that state is going to be higher than it was for $V^{\pi_1}(s)$.

When we choose to maximise outcomes to generate $\pi_2$, we don't know what the new $V^{\pi_2}(s)$ is going to be for any state, but we do know that $\forall s: V^{\pi_2}(s) \ge V^{\pi_1}(s)$.

Therefore, going back through the loop and calculating $V^{\pi_2}$ for the new policy is guaranteed to have same or higher values than before, and when it comes to update the policy again, $\pi_3 \ge \pi_2 \ge \pi_1$.

Answer 2

First let's see why Policy Iteration Algorithm works. It has two steps.

Policy Evaluation Step:

$v_n = r_{d_n} + \gamma P_{d_n}v_n$ is the general vectorial form of the system of linear equations.

Here, the terms $r_{d_n}, P_{d_n}$ are immediate rewards and corresponding rows of the transition matrix.

These terms are dependent on the policy $\Pi_n$

Solving the above system of equations we can find the values of $v_n$

Policy Improvement Step:

Assume that we were able to find a new policy $\Pi_{n+1}$ such that

\begin{align} r_{d_n+1} + \gamma P_{d_n+1}v_n & \ge r_{d_n} + \gamma P_{d_n}v_n \\ \implies r_{d_n+1} & \ge [I - \gamma P_{d_n+1}]v_n \quad \text{say this is eqn. 1}\\ \end{align}

Now, based on the new policy $\Pi_{n+1}$, we can find $v_{n+1} = r_{d_{n+1}} + \gamma P_{d_{n+1}}v_{n+1}$, say this is equation 2.

We are going to show that $v_{n+1} \ge v_n$ ;

i.e. essentially for all the states, the newly chosen policy $\Pi_{n+1}$ gives a better value compared to the previous policy $\Pi_{n}$

Proof:

From, equation 2, we have,

$[I - \gamma P_{d_{n+1}}]v_{n+1} = r_{d_n+1}$

From, $1 \&2$, we have

$v_{n+1} \ge v_{n}$

Essentially, the values are monotonically increasing with each iteration.

This is important to understand why Policy Interation will not be stuck at a local maximum.

A Policy is nothing but a state-action space.

At every policy iteration step, we try to find at least one state-action which is different between $\Pi_{n+1}$ and $\Pi_{n}$ and see if $ \quad r_{d_n+1} + \gamma P_{d_n+1}v_n \ge r_{d_n} + \gamma P_{d_n}v_n$. Only if the condition is satisfied we will compute the solution to the new system of linear equations.

Assume $\Pi^*$ and $\Pi^\#$ are the global and local optimum respectively.

Implies, $v_* \ge v_\#$

Assume the algorithm is stuck at the local optimum.

If this is the case, then the policy improvement step will not stop at the local optimum state-action space $\Pi^\#$, as there exists at least one state-action in $\Pi^*$ which is different from $\Pi^\#$ and yields a higher value of $v_{*}$ compared to $v_{\#}$

or, in other words,

$[I-\gamma P_{d_*}]v_* \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge r_{d_\#} + \gamma P_{d_\#}v_\#$

Hence, the Policy iteration does not stop at a local optimum

Answer 3

The optimal value function $v_*(s) := \max_\pi v_\pi(s)$ fulfills the Bellman optimality equation $$ v_\pi(s) = \max_a R(s,a) + \gamma \sum_{s'} P(s'|s,a) v_\pi(s').$$ Also we know by Banach's fixed point theorem that any other value function $v_\pi$ that fulfills this equation is equal to $v_*$, which implies that $\pi$ must be an optimal policy as well.

If we have the statements in the previous paragraph we can argue as follows: the policy iteration algorithm stops once the policy improvement doesn't change $\pi$. That is the exactly the case, when $v_\pi$ fulfills the Bellman optimality equation. Thus $\pi$ must be equal to an optimal policy, once policy iteration stops.