# 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 and :

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

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

Claim :

In other words, is an improvement over .

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

Proof :

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

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 for that particular time step, and then follows from then on. In the limit of this process, the policy transforms from to . As long as the expression for the return inside the expectation is finite, the governing policy should be ; only in the limit of this process does the governing policy transform to .

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.