Exercise 3.3.4

Policy improvement theorem: proof for stochastic policies

HardWritten

A key concept in policy iteration is that by alternating between evaluating (\(E\)) the current policy, obtaining \(v_{\pi}\) we can improve (\(I\)) the policy be making the new policy greedy with respect \(v_{\pi}\). This results in an alternating sequence of policies and value functions that eventually converge the optimal policy and value function: \[\pi_0 \overset{E}{\rightarrow} v_{\pi_0} \overset{I}{\rightarrow} \pi_1 \overset{E}{\rightarrow} v_{\pi_1} \overset{I}{\rightarrow} \pi_2 \overset{E}{\rightarrow} ... \overset{I}{\rightarrow} \pi_* \overset{E}{\rightarrow} v_*\]

Why making the next policy greedy with respect to the current value function estimate is an improvement is a consequence of the policy improvement theorem. Recall that the policy improvement theorem states that for two deterministic policies \(\pi, \pi'\) such that \(\pi'\) is the same except that \(\pi'(s) = a \not = \pi(s)\) for some \(s\), we have that if \(q_{\pi}(s, \pi'(s)) \geq v_{\pi}(s)\) then \(v_{\pi'}(s) \geq v_{\pi}(s)\). A proof sketch, assuming deterministic policies, can be found in section 4.2 of the book. The policy improvement theorem can be extended for stochastic policies.

Prove the policy improvement theorem for the stochastic case. What would need to be changed to the existing proof sketch for the deterministic case?