Body: <p>According to Reinforcement Learning (2nd Edition) by Sutton and Barto, the policy improvement theorem states that for any pair of deterministic policies <span class="math-container">$\pi'$</span> and <span class="math-container">$\pi$</span>, if <span class="math-container">$q_\pi(s,\pi'(s)) \geq v_\pi(s)$</span> <span class="math-container">$\forall s \in \mathcal{S}$</span>, then <span class="math-container">$v_{\pi'}(s) \geq v_\pi(s)$</span> <span class="math-container">$\forall s \in \mathcal{S}$</span>.</p>
  <p>The proof of this theorem seems to rely on <span class="math-container">$\pi$</span> and <span class="math-container">$\pi'$</span> being identical for all states except <span class="math-container">$s$</span>. To my best understanding, this is what allows us to write the expectation <span class="math-container">$\mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = a, A_t = \pi'(s)]$</span> as <span class="math-container">$\mathbb{E}_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = a]$</span> in line 2, which is central to the proof (re-produced from the book below).</p>
  <p><span class="math-container">\begin{aligned}
  v_{\pi}(s) &amp; \leq q_{\pi}\left(s, \pi^{\prime}(s)\right) \\
  &amp;=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) \mid S_{t}=s, A_{t}=\pi^{\prime}(s)\right] \\
  &amp;=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) \mid S_{t}=s\right] \\
  &amp; \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) \mid S_{t}=s\right] \\
  &amp;=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma \mathbb{E}_{\pi^{\prime}}\left[R_{t+2}+\gamma v_{\pi}\left(S_{t+2}\right) \mid S_{t+1}, A_{t+1}=\pi^{\prime}\left(S_{t+1}\right)\right] \mid S_{t}=s\right] \\
  &amp;=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} v_{\pi}\left(S_{t+2}\right) \mid S_{t}=s\right] \\
  &amp; \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} v_{\pi}\left(S_{t+3}\right) \mid S_{t}=s\right] \\
  &amp; \vdots \\
  &amp; \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\cdots \mid S_{t}=s\right] \\
  &amp;=v_{\pi^{\prime}}(s)
  \end{aligned}</span></p>
  <p>Does this mean that the proof is merely proving the special case of the policy improvement theorem for when the policies are identical except at <span class="math-container">$s$</span>? I am having trouble seeing why the proof holds for the more general case of the two policies being potentially different for all states. In that case, line 2 would not hold and the theorem would not hold for all states as it claims to do.</p>
  
Tags: <reinforcement-learning><proofs><sutton-barto><policy-improvement-theorem>
Title: Policies for which the policy improvement theorem holds
UserDisplayName: bonzo_pippinpaddle
ThreadText: # Policies for which the policy improvement theorem holds
  
  (Asked by: username_0 on 2021-08-23)
  
  According to Reinforcement Learning (2nd Edition) by Sutton and Barto, the policy improvement theorem states that for any pair of deterministic policies $\pi'$ and $\pi$, if $q\_\pi(s,\pi'(s)) \geq v\_\pi(s)$ $\forall s \in \mathcal{S}$, then $v\_{\pi'}(s) \geq v\_\pi(s)$ $\forall s \in \mathcal{S}$.
  
  The proof of this theorem seems to rely on $\pi$ and $\pi'$ being identical for all states except $s$. To my best understanding, this is what allows us to write the expectation $\mathbb{E}[R\_{t+1} + \gamma v\_\pi(S\_{t+1})|S\_t = a, A\_t = \pi'(s)]$ as $\mathbb{E}\_{\pi'}[R\_{t+1} + \gamma v\_\pi(S\_{t+1})|S\_t = a]$ in line 2, which is central to the proof (re-produced from the book below).
  
  \begin{aligned}
  v\_{\pi}(s) & \leq q\_{\pi}\left(s, \pi^{\prime}(s)\right) \\
  &=\mathbb{E}\left[R\_{t+1}+\gamma v\_{\pi}\left(S\_{t+1}\right) \mid S\_{t}=s, A\_{t}=\pi^{\prime}(s)\right] \\
  &=\mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma v\_{\pi}\left(S\_{t+1}\right) \mid S\_{t}=s\right] \\
  & \leq \mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma q\_{\pi}\left(S\_{t+1}, \pi^{\prime}\left(S\_{t+1}\right)\right) \mid S\_{t}=s\right] \\
  &=\mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma \mathbb{E}\_{\pi^{\prime}}\left[R\_{t+2}+\gamma v\_{\pi}\left(S\_{t+2}\right) \mid S\_{t+1}, A\_{t+1}=\pi^{\prime}\left(S\_{t+1}\right)\right] \mid S\_{t}=s\right] \\
  &=\mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma R\_{t+2}+\gamma^{2} v\_{\pi}\left(S\_{t+2}\right) \mid S\_{t}=s\right] \\
  & \leq \mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma R\_{t+2}+\gamma^{2} R\_{t+3}+\gamma^{3} v\_{\pi}\left(S\_{t+3}\right) \mid S\_{t}=s\right] \\
  & \vdots \\
  & \leq \mathbb{E}\_{\pi^{\prime}}\left[R\_{t+1}+\gamma R\_{t+2}+\gamma^{2} R\_{t+3}+\gamma^{3} R\_{t+4}+\cdots \mid S\_{t}=s\right] \\
  &=v\_{\pi^{\prime}}(s)
  \end{aligned}
  
  Does this mean that the proof is merely proving the special case of the policy improvement theorem for when the policies are identical except at $s$? I am having trouble seeing why the proof holds for the more general case of the two policies being potentially different for all states. In that case, line 2 would not hold and the theorem would not hold for all states as it claims to do.
  
  **Tags:** reinforcement-learning, proofs, sutton-barto, policy-improvement-theorem
  
  ---
  
  ## 0 answers
  
  