# Proof that an epsilon greedy policy w.r.t. $q$ values is better than the original policy $\pi$?

I was trying to understand the proof why policy improvement theorem can be applied on epsilon-greedy policy.

The proof starts with the mathematical definition - I am confused on the very first line of the proof. In an MDP - This equation is the Bellman expectation equation for Q(s,a), while V(s) and Q(s,a) follow the relation - So how can we ever derive the first line of the proof ? What does the notation Q(s, π'(s)) even mean, since π is not a deterministic policy but a stochastic one (so it doesn't refer to a fixed action) ? Isn't the Q value only defined for a state action pair ?

## 1 Answer

The first line of the proof that you are quoting:

$$q_{\pi}(s,\pi'(s)) = \sum_a \pi'(a|s)q_{\pi}(s,a)$$

has some loose notation. The function $\pi'(s)$ is not defined for a stochastic policy, and even it it were, is would not map a state to an action in order to be a valid second argument to $q(s, a)$.

A more accurate way of writing it would be:

$$\mathbb{E}[q_{\pi}(S_t,A_t)|S_t=s, A_t \sim \pi'] = \sum_a \pi'(a|s)q_{\pi}(s,a)$$

Essentially, what is the expected value of following $\pi$ but changing action at state $s$ to follow $\pi'$ - the core evaluation needed for the policy improvement theorem.

However, that is a little awkward and loses the gist of the line. So the proof you are reading does a sleight-of-hand, essentially re-using the start of the deterministic version of the proof.

It is not a big deal, the right hand side of the first line is trivially correct from definitions of $q_{\pi}$ and $\pi'$. The proof could start with the text what is the expected value of following $\pi$ but changing action at state $s$ to follow $\pi'$, lead with the right hand side of the first line, and be just as rigorous.