I am studying RL and have a hard time proving the existence of an optimal policy. I found some resources online, and I am trying to prove the following theorem:

If there exists a policy $\pi$, state $s' \in \mathcal{S}$ and action $a' \in \mathcal{A}(s')$ such that $q_\pi(s', a') \geq v_\pi(s')$ then the policy $\pi'(a|s) = \pi(a|s)(1- \delta_{s, s'}) + \delta_{a, a'}\delta_{s, s'}$ satisfy $$ v_{\pi'}(s) \geq v_\pi(s) \; \forall s \in \mathcal{S} $$

Now there is a proof in this article on medium(theorem 1), but I dont fully understand it and would like to write it out more explicitly, using the definition of expectaton with respect to the different policies and so on, but I always end up being really confused and struggling to see where the inequalities in line 4 and 5 comes from in the article.

I would really appreciate if someone could take a look at it and give me a more explicit derivation of this fact. Thanks:)


1 Answer 1


This theorem is basically the policy improvement theorem in S&L's RL book page 78, though expressed differently. The reasons for your confused line 4 & 5 are essentially same as your reference's proof comment stated:

and then repeatedly used the fact that the value of the pair of state and action $(s^*, a^*)$ is greater than or equal to the value of state $s^*$.

Since this theorem's condition is that there exists $s^*,a^*$ such that $q_\pi(s^*,a^*) \geq v_\pi(s^*)$, following your reference's notation and line 1 which you already understood, line 4 can be formally derived as: $$\mathbb{E}_{\pi'}(R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s) = \mathbb{E}_{\pi'}(R_{t+1}+\gamma \mathbb{E}_{\pi}(q_\pi(S_{t+1},A_{t+1}))|S_t=s)$$, where $S_{t+1}$ is the (random) entering state after $s$ determined solely by the MDP environment.

Then follow the same proof step for line 2, the above $$\text{RHS} \leq \mathbb{E}_{\pi'}(R_{t+1}+\gamma \mathbb{E}_{\pi'}(q_\pi(S_{t+1},A_{t+1}))|S_t=s) = \mathbb{E}_{\pi'}(R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|S_t=s) = \mathbb{E}_{\pi'}(R_{t+1}+\gamma (R_{t+2}+\gamma v_\pi(S_{t+2}))|S_t=s) = \mathbb{E}_{\pi'}(R_{t+1}+\gamma R_{t+2}+\gamma^2 v_\pi(S_{t+2})|S_t=s)$$

Finally line 5 is similar to above derivation of line 4.

  • $\begingroup$ Thanks for the reply! I just have some minor questions. When I try to obtain $\mathbb{E}_{\pi'}(R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s)$ I arrive at $\mathbb{E}_{\pi'}(R_{t+1}+\gamma\mathbb{E}_\pi( v_\pi(S_{t+1}))|S_t=s)$. Is it true that $\mathbb{E}_\pi( v_\pi(S_{t+1})) = v_\pi(S_{t+1})$? It probably answers my second question as well; why can you remove the expectation around $q_\pi$ when you go from $\mathbb{E}_{\pi'}(R_{t+1}+\gamma \mathbb{E}_{\pi'}(q_\pi(S_{t+1},A_{t+1}))|S_t=s) $ to $ \mathbb{E}_{\pi'}(R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|S_t=s)$? $\endgroup$
    – mNugget
    Commented Apr 1 at 6:22
  • 1
    $\begingroup$ Yes since by definition both state and action value functions of a specific state $s$ are expectation statistics conditioned on $S=s$ following your notation, and note here all expectations are conditioned on $S_t=s$. So to transform from action value to state value there's no need for extra expectation operator. $\endgroup$
    – cinch
    Commented Apr 1 at 15:07

You must log in to answer this question.

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