# Policy Improvement Theorem

In reinforcement learning, policy improvement is a part of an algorithm called policy iteration, which attempts to find approximate solutions to the Bellman optimality equations. Page-84, 85 in Sutton and Barto's book on RL mentions the following theorem:

Policy Improvement Theorem

Given two deterministic policies $$\pi$$ and $$\pi'$$:

$$\forall s \in S, V_{\pi}(s) \leq Q_{\pi}(s, \pi'(s))$$

LHS of inequality: the agent acts according to policy $$\pi$$ starting from the current state.

RHS of inequality : the agent acts according to policy $$\pi'$$ in the current state, and for all subsequent states acts according to policy $$\pi$$

Claim : $$\forall s \in S, V_\pi(s) \leq V_{\pi'}(s)$$

In other words, $$\pi'$$ is an improvement over $$\pi$$.

I have difficulty in understanding the proof. This is discussed below:

Proof : $$V_\pi(s) \leq Q_\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}[R_{t+1} + \gamma V_\pi(S_{t+1}) | S_t = s]$$

I am stuck here. The q-function is evaluated over the policy $$\pi$$. That being the case, how is the expectation over the policy $$\pi'$$?

My guess is the following: in the proof given in Sutton and Barto, the expectation is unrolled in time. At each time step, the agent follows the policy $$\pi'$$ for that particular time step and then follows $$\pi$$ from then on. In the limit of this process, the policy transforms from $$\pi$$ to $$\pi'$$. As long as the expression for the return inside the expectation is finite, the governing policy should be $$\pi$$; only in the limit of this process does the governing policy transform to $$\pi'$$.

They never quite spell it out, but an expression like: \begin{align} E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t=s] \end{align} means "the expected discounted value when starting in state $s$, choosing actions according to $\pi'$ for the next time step, and according to $\pi$ thereafter", while: \begin{align} E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t=s] \end{align} means "the expected discounted value when starting in state $s$, choosing actions according to $\pi'$ for the next TWO timesteps, and according to $\pi$ thereafter", etc.
So we really have: \begin{align} E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t=s] = E[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t=s, A_t=\pi'(s)] \end{align} and if we look up to the beginning of section 4.2 on Policy Improvement, we can see that this is equal to $q(s, \pi'(s))$. The reason that they have these two different expressions for $q(s, \pi(s))$ is that the first is needed because to complete the proof they need to be able to talk about following $\pi'$ for increasingly longer spans of time, and the second is simply the definition of a Q-function for a deterministic policy.