8
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.