# Policy and value iteration algorithm convergence conditions

Policy and value iteration algorithms can be used to solve Markov decision process problems. I have a hard time understanding to necessary conditions for convergence. If the optimal policy does not change during two steps (i.e. during iterations i and i+1), can it be concluded that the algorithms have converged? If not, then when?

To answer your question, let me first write out some important (in)equalities.

Bellman optimality equation:

\begin{align} v_∗(s) &= \max_{a} \mathbb{E}[R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t =s, A_t =a] \\ &= \max_{a} \sum_{s'}p(s'\mid s, a) \biggl[r(s, a, s') + \gamma v_∗(s')\biggl] \end{align}

where $v_*(.)$ is the optimal value function.

Policy improvement theorem (Pit):

Let $\pi$ and $\pi'$ be any pair of deterministic policies such that, for all $s \in S$, $q_\pi(s, \pi'(s)) \geq v_\pi(s)$ Then the policy $\pi'$ must be as good as, or better than, $\pi$. That is, it must obtain greater or equal expected return from all states $s \in S: v_{\pi'} (s) \geq v_\pi(s)$.

(find on page 89 of Sutton & Barto, Reinforcement learning: An Introduction book)

We can improve a policy $\pi$ at every state by the following rule:

\begin{align} \pi'(s) &= \arg \max_{a}q_π(s, a)\\ &= \arg \max_{a} \sum_{s'}p(s' \mid s, a)\biggl[r(s, a, s') + \gamma v_\pi(s')\biggl] \end{align}

Our new policy $\pi'$ satisfies the condition of Pit and so is as good as or better than $\pi$. If $\pi'$ is as good as, but not better than $\pi$, then $v_{\pi'}(s)=v_{\pi}(s)$ for all $s$. From our definition of $\pi'$ we deduce, that:

\begin{align} v_{\pi'}(s)&=\max_{a} \mathbb{E}\biggl[R_{t+1} + \gamma v_{ \pi'}(S_{t+1}) \mid S_t =s, A_t =a \biggl]\\ &= \max_{a}\sum_{s'}p(s' \mid s, a) \biggl[r(s, a, s') + \gamma v_{π'}(s') \biggl] \end{align}

But this equality is the same as the Bellman optimality equation so $v_{\pi'}$ must equal $v_*$.

From the above said, it is hopefully clear, that if we improve a policy and get the same value function, that we had before, the new policy must be one of the optimal policies. For more information, see Sutton & Barto (2012)

You're correct: either the current value function estimate or the current policy estimate can completely describe the state of the algorithm. Each one implies a unique next choice for the other. From the paper linked below,

"Policy iteration continues until $V_{n+1} = V_n, α_{n+1} = α_n$."

https://editorialexpress.com/jrust/research/siam_dp_paper.pdf