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 -

Barto and Sutton - Reinforcement Learning: An Introduction

I am confused on the very first line of the proof. In an MDP -

enter image description here

This equation is the Bellman expectation equation for Q(s,a), while V(s) and Q(s,a) follow the relation -

enter image description here

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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.