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?
 A: 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) 
A: 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
