Answers.Body: <p>The expectation is over the policy <span class="math-container">$\pi'$</span> because the action at the state <span class="math-container">$S_t = s$</span> is taken according to <span class="math-container">$\pi'$</span>, <strong>and</strong>, for the proof, the book text (2nd edition, paragraph below Equation 4.8) defines <span class="math-container">$\pi'$</span> to be a policy that is identical to <span class="math-container">$\pi$</span> except that <span class="math-container">$\pi'(s) = a \neq \pi(s)$</span>, where <span class="math-container">$s$</span> is one particular state. </p>
  
  <p>So, essential, the book text tries to prove that, for such a changed policy <span class="math-container">$\pi'$</span>, if <span class="math-container">$q_\pi(s, a) = q_\pi(s, \pi'(s)) &gt; v_\pi(s)$</span>, then the changed policy is better than <span class="math-container">$\pi$</span>. Note that <span class="math-container">$\pi'(s) = a$</span> in this case.</p>
  
  <p>That is why <span class="math-container">$q_\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-07-25T15:43:59.440Z
Answers.LastActivityDate: 2018-11-11T20:39:33.820Z
Answers.LastEditDate: 2018-11-11T20:39:33.820Z
Answers.UserDisplayName: PraveenPalanisamy
Body: <p>In reinforcement learning, policy improvement is a part of an algorithm called policy iteration, which attempts to find approximate solutions to the Bellman optimality equations.</p>
  <p>Pages 84 and 85 in Sutton and Barto's <a href="https://webdocs.cs.ualberta.ca/%7Esutton/book/bookdraft2016sep.pdf" rel="nofollow noreferrer">book</a> on RL mentions the following theorem:</p>
  <blockquote>
  <p><strong>Policy Improvement Theorem</strong></p>
  <p>Given two deterministic policies <span class="math-container">$\pi$</span> and <span class="math-container">$\pi'$</span>, then <span class="math-container">$$v_\pi(s) \leq q_\pi(s, \pi'(s)), \forall s \in S.$$</span></p>
  <p>where <span class="math-container">$S$</span> is the set of all states.</p>
  </blockquote>
  <p>In the the right-hand side of the inequality, the agent acts according to policy <span class="math-container">$\pi'$</span> (given that <span class="math-container">$\pi'(s)$</span> is used in the inequality), in the current state <span class="math-container">$s$</span>, and for all subsequent states acts according to policy <span class="math-container">$\pi$</span>.</p>
  <p>In the left-hand side of the inequality, the agent acts according to policy <span class="math-container">$\pi$</span> (hence the subscript <span class="math-container">$_\pi$</span> of <span class="math-container">$v_\pi(s)$</span>), starting from the current state <span class="math-container">$s$</span>.</p>
  <p>The claim is the following</p>
  <blockquote>
  <p><span class="math-container">$$v_\pi(s) \leq v_{\pi'}(s), \forall s \in S$$</span></p>
  </blockquote>
  <p>In other words, <span class="math-container">$\pi'$</span> is is an improvement over <span class="math-container">$\pi$</span>.</p>
  <p>However, I have a difficulty in understanding the proof. This is discussed below.</p>
  <blockquote>
  <p><strong>Proof</strong></p>
  <p><span class="math-container">$$v_\pi(s) \leq q_\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]$$</span></p>
  </blockquote>
  <p>I am stuck here. The q-function is evaluated over the policy <span class="math-container">$\pi$</span> (note the subscript <span class="math-container">$_\pi$</span> in <span class="math-container">$q_\pi(s, \pi'(s))$</span>). That being the case, <em>how is the expectation over the policy <span class="math-container">$\pi'$</span></em>?</p>
  <p>My guess is the following. In the proof given in Sutton and Barto, the expectation is unrolled in time. At each time step, the agent follows the policy <span class="math-container">$\pi'$</span>  for that particular time step, and then follows <span class="math-container">$\pi$</span> from then on. In the limit of this process, the policy transforms from <span class="math-container">$\pi$</span> to <span class="math-container">$\pi'$</span>. As long as the expression for the return inside the expectation is finite, the governing policy should be <span class="math-container">$\pi$</span>; only in the limit of this process does the governing policy transform to <span class="math-container">$\pi'$</span>.</p>
  
Tags: <reinforcement-learning><proofs>
Title: Understanding why the expectation is over the new policy $\pi'$ in the proof of the Policy Improvement Theorem
UserDisplayName: Karthik Thiagarajan
ThreadText: # Understanding why the expectation is over the new policy $\pi'$ in the proof of the Policy Improvement Theorem
  
  (Asked by: username_0 on 2017-01-28)
  
  In reinforcement learning, policy improvement is a part of an algorithm called policy iteration, which attempts to find approximate solutions to the Bellman optimality equations.
  
  Pages 84 and 85 in Sutton and Barto's [book](https://webdocs.cs.ualberta.ca/%7Esutton/book/bookdraft2016sep.pdf) on RL mentions the following theorem:
  
  > **Policy Improvement Theorem**
  >
  > Given two deterministic policies $\pi$ and $\pi'$, then $$v\_\pi(s) \leq q\_\pi(s, \pi'(s)), \forall s \in S.$$
  >
  > where $S$ is the set of all states.
  
  In the the right-hand side of the inequality, the agent acts according to policy $\pi'$ (given that $\pi'(s)$ is used in the inequality), in the current state $s$, and for all subsequent states acts according to policy $\pi$.
  
  In the left-hand side of the inequality, the agent acts according to policy $\pi$ (hence the subscript $\_\pi$ of $v\_\pi(s)$), starting from the current state $s$.
  
  The claim is the following
  
  > $$v\_\pi(s) \leq v\_{\pi'}(s), \forall s \in S$$
  
  In other words, $\pi'$ is is an improvement over $\pi$.
  
  However, I have a difficulty in understanding the proof. This is discussed below.
  
  > **Proof**
  >
  > $$v\_\pi(s) \leq q\_\pi(s, \pi'(s)) = \mathbb{E}\_{\pi'}[R\_{t+1} + \gamma v\_\pi(S\_{t+1}) \mid S\_t = s]$$
  
  I am stuck here. The q-function is evaluated over the policy $\pi$ (note the subscript $\_\pi$ in $q\_\pi(s, \pi'(s))$). That being the case, *how is the expectation over the policy $\pi'$*?
  
  My guess is the following. In the proof given in Sutton and Barto, the expectation is unrolled in time. At each time step, the agent follows the policy $\pi'$ for that particular time step, and then follows $\pi$ from then on. In the limit of this process, the policy transforms from $\pi$ to $\pi'$. As long as the expression for the return inside the expectation is finite, the governing policy should be $\pi$; only in the limit of this process does the governing policy transform to $\pi'$.
  
  **Tags:** reinforcement-learning, proofs
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-07-25. Score: 3
  
  The expectation is over the policy $\pi'$ because the action at the state $S\_t = s$ is taken according to $\pi'$, **and**, for the proof, the book text (2nd edition, paragraph below Equation 4.8) defines $\pi'$ to be a policy that is identical to $\pi$ except that $\pi'(s) = a \neq \pi(s)$, where $s$ is one particular state.
  
  So, essential, the book text tries to prove that, for such a changed policy $\pi'$, if $q\_\pi(s, a) = q\_\pi(s, \pi'(s)) > v\_\pi(s)$, then the changed policy is better than $\pi$. Note that $\pi'(s) = a$ in this case.
  
  That is why $q\_\pi(s, \pi'(s)) = \mathbb{E}\_{\pi'}[R\_{t+1} + \gamma v\_\pi(S\_{t+1}) \mid S\_t = s]$.
  
  
  ---
  
  