Answers.Body: <blockquote>
  <p>I don't understand how did we get rid of the condition <span class="math-container">$A_{t}=\pi'(s)$</span>.</p>
  </blockquote>
  <p>We don't really, it is just moved into the subscript <span class="math-container">$\pi'$</span> in <span class="math-container">$\mathbb{E}_{\pi'}[]$</span> - it means the same thing here, that the next action is chosen according to the modified policy <span class="math-container">$\pi'$</span>. 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 <span class="math-container">$v_{\pi'}(s)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-22T19:22:44.067Z
Answers.Text: Am I right in thinking that this follows because $\pi'$ is a strictly deterministic policy?
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-22T21:37:59.700Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-23T01:41:13.287Z
Answers.Text: 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)$.
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-23T06:16:52.297Z
Answers.Text: @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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-23T11:09:04.670Z
Answers.Text: @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?
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-23T13:22:51.480Z
Answers.Text: @Daviiid There is no need to look deeper. The only difference between terms in the subscript of the expectation, and terms in the conditions is that the latter are usually specific boundary measurements whilst the former are more general rules on the expectation. Note the $v_{\pi}(S_{t+1})$ inside the $\mathbb{E}_{\pi'}$ means that the general case of $\pi'$ is being ignored after the first timestep (for getting $R_{t+1}$ and $S_{t+1}$) because $v_{\pi}$ relies on following $\pi$, *not* $\pi'$.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-23T14:08:11.973Z
Answers.Text: @NeilSlater I see, I think I'm getting a clearer view. So when we write $q_{\pi}(s,a)=\mathbb{E}_{\pi}[G_{t}|S_{t}=s,A_{t}=a]$ it means we're trying to evaluate the action $a$ taken in state $s$ and then following policy $\pi$, this could also be written as $q_{\pi}(s,a)=\mathbb{E}_{\pi '}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s]$ where $\pi '(s)=a$ but $\pi '$ is the same as $\pi$ for any other state. I think I had a hard time conciliating the definition which focused on the condition $A_{t}=a$ and the fact just we can take it off (while modifying the subscript). Thank you again!
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-22T18:36:15.300Z
Answers.LastActivityDate: 2021-06-22T18:36:15.300Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm going through Sutton and Barto's book <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a> and I'm trying to understand the proof of the Policy Improvement Theorem, presented at page 78 of the physical book.</p>
  <p>The theorem goes as follows:</p>
  <blockquote>
  <p>Let <span class="math-container">$\pi$</span> and <span class="math-container">$\pi'$</span> be any pair of deterministic policies such that, for all <span class="math-container">$s\in S$</span>,</p>
  <p><span class="math-container">$q_{\pi}(s,\pi'(s))\geq v_{\pi}(s)$</span>.</p>
  <p>Then the policiy <span class="math-container">$\pi'$</span> must be as good as, or better than, <span class="math-container">$\pi$</span>. That is, it must obtain greater or equal expected return from all states <span class="math-container">$s\in S$</span>:</p>
  <p><span class="math-container">$v_{\pi'}(s)\geq v_{\pi}(s)$</span>.</p>
  </blockquote>
  <p>I take it that for the proof, the policy <span class="math-container">$\pi'$</span> is identical to <span class="math-container">$\pi$</span> except for one particular state <span class="math-container">$s$</span> (at each time step) for which we have <span class="math-container">$\pi'(s)=a\neq \pi(s)$</span>, as suggested by @PraveenPalanisamy in his answer <a href="https://ai.stackexchange.com/questions/2733/understanding-why-the-expectation-is-over-the-new-policy-pi-in-the-proof-of">here</a>.</p>
  <p>The proof start from the statement of the theorem: <span class="math-container">$v_{\pi}(s)\leq q_{\pi}(s,\pi'(s))$</span></p>
  <p>And then <span class="math-container">$q_{\pi}(s,\pi'(s))$</span> is developed as <span class="math-container">$\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]$</span></p>
  <p>I don't understand how did we get rid of the condition <span class="math-container">$A_{t}=\pi'(s)$</span>. I don't think it's related to adding the subscript <span class="math-container">$\pi'$</span> to the expectation because it's something that should be done by definition since for the <strong>following time steps</strong> we choose policy <span class="math-container">$\pi$</span> which is exactly <span class="math-container">$\pi'$</span>.</p>
  
Tags: <reinforcement-learning><dynamic-programming><policy-improvement><policy-improvement-theorem>
Title: How do we get from conditional expectation on both state and action to only state in the proof of the Policy Improvement Theorem?
UserDisplayName: Daviiid
ThreadText: # How do we get from conditional expectation on both state and action to only state in the proof of the Policy Improvement Theorem?
  
  (Asked by: username_0 on 2021-06-22)
  
  I'm going through Sutton and Barto's book [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/the-book.html) 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](https://ai.stackexchange.com/questions/2733/understanding-why-the-expectation-is-over-the-new-policy-pi-in-the-proof-of).
  
  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'$.
  
  **Tags:** reinforcement-learning, dynamic-programming, policy-improvement, policy-improvement-theorem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-06-22. Score: 2 | Accepted answer
  
  > 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)$.
  
  > **Comments:**
  > **username_2**: Am I right in thinking that this follows because $\pi'$ is a strictly deterministic policy?  
  > **username_1**: @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.  
  > **username_0**: Thank you for your answer @username_1 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)$.  
  > **username_1**: @username_0 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.  
  > **username_0**: @username_1 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?  
  > **username_1**: @username_0 There is no need to look deeper. The only difference between terms in the subscript of the expectation, and terms in the conditions is that the latter are usually specific boundary measurements whilst the former are more general rules on the expectation. Note the $v_{\pi}(S_{t+1})$ inside the $\mathbb{E}_{\pi'}$ means that the general case of $\pi'$ is being ignored after the first timestep (for getting $R_{t+1}$ and $S_{t+1}$) because $v_{\pi}$ relies on following $\pi$, *not* $\pi'$.  
  > **username_0**: @username_1 I see, I think I'm getting a clearer view. So when we write $q_{\pi}(s,a)=\mathbb{E}_{\pi}[G_{t}|S_{t}=s,A_{t}=a]$ it means we're trying to evaluate the action $a$ taken in state $s$ and then following policy $\pi$, this could also be written as $q_{\pi}(s,a)=\mathbb{E}_{\pi '}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s]$ where $\pi '(s)=a$ but $\pi '$ is the same as $\pi$ for any other state. I think I had a hard time conciliating the definition which focused on the condition $A_{t}=a$ and the fact just we can take it off (while modifying the subscript). Thank you again!  
  
  ---
  
  