Answers.Body: <p>This theorem is basically the policy improvement theorem in S&amp;L's RL book page 78, though expressed differently. The reasons for your confused line 4 &amp; 5 are essentially same as your reference's proof comment stated:</p>
  <blockquote>
  <p>and then repeatedly used the fact that the value of the pair of state and action <span class="math-container">$(s^*, a^*)$</span> is greater than or equal to the value of state <span class="math-container">$s^*$</span>.</p>
  </blockquote>
  <p>Since this theorem's condition is that there exists <span class="math-container">$s^*,a^*$</span> such that <span class="math-container">$q_\pi(s^*,a^*) \geq v_\pi(s^*)$</span>, following your reference's notation and line 1 which you already understood, line 4 can be formally derived as:
  <span class="math-container">$$\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)$$</span>, where <span class="math-container">$S_{t+1}$</span> is the (random) entering state after <span class="math-container">$s$</span> determined solely by the MDP environment.</p>
  <p>Then follow the same proof step for line 2, the above <span class="math-container">$$\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)$$</span></p>
  <p>Finally line 5 is similar to above derivation of line 4.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-01T06:22:05.290Z
Answers.Text: 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)$?
Answers.UserDisplayName: mNugget
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-01T15:07:12.137Z
Answers.Text: 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.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-01T05:57:05.903Z
Answers.LastActivityDate: 2024-04-01T05:57:05.903Z
Answers.UserDisplayName: cinch
Body: <p>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:</p>
  <p>If there exists a policy <span class="math-container">$\pi$</span>, state <span class="math-container">$s' \in \mathcal{S}$</span> and action <span class="math-container">$a' \in \mathcal{A}(s')$</span> such that <span class="math-container">$q_\pi(s', a') \geq v_\pi(s')$</span> then the policy <span class="math-container">$\pi'(a|s) = \pi(a|s)(1- \delta_{s, s'}) + \delta_{a, a'}\delta_{s, s'}$</span> satisfy
  <span class="math-container">$$
  v_{\pi'}(s) \geq v_\pi(s) \; \forall s \in \mathcal{S}
  $$</span></p>
  <p>Now there is a proof in this <a href="https://towardsdatascience.com/why-does-the-optimal-policy-exist-29f30fd51f8c" rel="nofollow noreferrer">article on medium</a>(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.</p>
  <p>I would really appreciate if someone could take a look at it and give me a more explicit derivation of this fact.
  Thanks:)</p>
  
Tags: <reinforcement-learning><bellman-equations>
Title: Proof of bellman optimality equations
UserDisplayName: mNugget
ThreadText: # Proof of bellman optimality equations
  
  (Asked by: username_0 on 2024-04-01)
  
  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](https://towardsdatascience.com/why-does-the-optimal-policy-exist-29f30fd51f8c)(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:)
  
  **Tags:** reinforcement-learning, bellman-equations
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-04-01. Score: 2 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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)$?  
  > **username_1**: 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.  
  
  ---
  
  