Policy Improvement

Now that you can estimate state value function for any policy, a natural next step is to explore whether there are any policies better than the current one. One way of doing this, is to consider taking a different action $a$ in a state $s$ , and to follow the current policy afterwards. If this sounds familiar, it's because this is similar to how we define the action value function:

q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

If this new value is greater than the original state value $v_\pi(s)$ , it indicates that taking action $a$ in state $s$ and then continuing with policy $\pi$ leads to better outcomes than strictly following policy $\pi$ . Since states are independent, it's optimal to always select action $a$ whenever state $s$ is encountered. Therefore, we can construct an improved policy $\pi'$ , identical to $\pi$ except that it selects action $a$ in state $s$ , which would be superior to the original policy $\pi$ .

Policy Improvement Theorem

The reasoning described above can be generalized as the policy improvement theorem:

\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

The proof of this theorem is relatively simple, and can be achieved by a repeated substitution:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Improvement Strategy

While updating actions for certain states can lead to improvements, it's more effective to update actions for all states simultaneously. Specifically, for each state $s$ , select the action $a$ that maximizes the action value $q_\pi(s, a)$ :

\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

The resulting greedy policy, denoted by $\pi'$ , satisfies the conditions of the policy improvement theorem by construction, guaranteeing that $\pi'$ is at least as good as the original policy $\pi$ , and typically better.

If $\pi'$ is as good as, but not better than $\pi$ , then both $\pi'$ and $\pi$ are optimal policies, as their value functions are equal, and satisfy Bellman optimality equation:

v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 3. Capítulo 5