# Proof of bellman optimality equations

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:)

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)$$
• 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)$? Commented Apr 1 at 6:22
• 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. Commented Apr 1 at 15:07