I'm going through Sutton and Barto's book Reinforcement Learning: An Introduction and I'm trying to understand the proof of the Policy Improvement Theorem, presented at page 78 of the physical book.

The theorem goes as follows:

Let $\pi$ and $\pi'$ be any pair of deterministic policies such that, for all $s\in S$,

$q_{\pi}(s,\pi'(s))\geq v_{\pi}(s)$.

Then the policiy $\pi'$ must be as good as, or better than, $\pi$. That is, it must obtain greater or equal expected return from all states $s\in S$:

$v_{\pi'}(s)\geq v_{\pi}(s)$.

I take it that for the proof, the policy $\pi'$ is identical to $\pi$ except for one particular state $s$ (at each time step) for which we have $\pi'(s)=a\neq \pi(s)$, as suggested by @PraveenPalanisamy in his answer here.

The proof start from the statement of the theorem: $v_{\pi}(s)\leq q_{\pi}(s,\pi'(s))$

And then $q_{\pi}(s,\pi'(s))$ is developed as $\mathbb{E}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s,A_{t}=\pi'(s)]=\mathbb{E}_{\pi'}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s]$

I don't understand how did we get rid of the condition $A_{t}=\pi'(s)$. I don't think it's related to adding the subscript $\pi'$ to the expectation because it's something that should be done by definition since for the following time steps we choose policy $\pi$ which is exactly $\pi'$.


1 Answer 1


I don't understand how did we get rid of the condition $A_{t}=\pi'(s)$.

We don't really, it is just moved into the subscript $\pi'$ in $\mathbb{E}_{\pi'}[]$ - it means the same thing here, that the next action is chosen according to the modified policy $\pi'$. Moving the condition around is part of the proof's strategy, which eventually expresses the expectation in a familiar way so that we end up with a something that matches the definition of $v_{\pi'}(s)$.

  • $\begingroup$ Am I right in thinking that this follows because $\pi'$ is a strictly deterministic policy? $\endgroup$
    – David
    Commented Jun 22, 2021 at 19:22
  • 1
    $\begingroup$ @DavidIreland It is not required, and there is a version of the policy improvement theorem for improving epsilon-greedy policies too. There are a couple of intuitive looks at that too - e.g. an epsilon-greedy policy has identical expected returns to the matching greedy policy but with a change to reward and state transitions where the environment bechaves with probabiliy epsilon as if a random action was chosen. But yes in the first view of the policy improvement theorem in the book it is a deterministic policy. $\endgroup$ Commented Jun 22, 2021 at 21:37
  • $\begingroup$ Thank you for your answer @NeilSlater but trying to get the expression in a familiar way to $v_{\pi'}(s)$ isn't so rigorous am I wrong? Especially if we do that in the proof, why don't we do the same in the definition of the action value function instead of explicitely state the condition on the action $q_{\pi}(s,a)=\mathbb{E}[G_{t}|S_{t}=s,A_{t}=a]$. If it's just for clarity, I believe there wouldn't be much of a difference between $q_{\pi}(s,a)$ and $v_{\pi}(s)$. $\endgroup$
    – Daviiid
    Commented Jun 23, 2021 at 1:41
  • $\begingroup$ @Daviiid It is not "just for clarity" and I do not say that in the answer. It is algebraic manipulation, same as e.g. rationaiising a fraction or cancelling terms on two sides of an equation. $\endgroup$ Commented Jun 23, 2021 at 6:16
  • $\begingroup$ @NeilSlater yes I know sorry if it came as if it was in your answer. I just stated the "just for clarity" in relation with the $q_{\pi}(s,a)$ case to say that I don't believe it's for clarity but for another purpose. I really understand your answer from an "intuition" point of view. Since we're sure that we're taking action $\pi '(s)$ and then following $\pi '$ which is a deterministic policy, it's seems like a "factorization", in some sense, of the expression. But is it rigorous? I mean, based on measure theorems and properties we don't have a clear implication or do we? $\endgroup$
    – Daviiid
    Commented Jun 23, 2021 at 11:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .