Answers.Body: <p>You are right that the strict equality <span class="math-container">$q_\pi(s,\pi(s)) = v_\pi(s)$</span> is generally true for a deterministic policy <span class="math-container">$\pi$</span>.</p>
  <p>The <span class="math-container">$\geq$</span> inequality is also correct, of course, and it <em>could be</em> that the authors' intention was to show that <span class="math-container">$\pi_{k+1}$</span> and <span class="math-container">$\pi_k$</span> satisfy the condition for the policy improvement theorem:</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\mathcal{S}$</span>,
  <span class="math-container">$$q_\pi(s,\pi'(s))\geq v_\pi(s)\tag{4.7}$$</span></p>
  </blockquote>
  <p>So they kinda relaxed the equality to show that the condition is satisfied &quot;word-for-word&quot; for <span class="math-container">$\pi'=\pi_{k+1}$</span> and <span class="math-container">$\pi=\pi_k$</span>.</p>
  <p>Although, I must say that they don't seem to be consistent in this - for example, they keep the strict equality at the derivation at the bottom of the page 78. So it might as well be that you've discovered a typo in Sutton and Barto.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-16T18:05:07.793Z
Answers.LastActivityDate: 2021-05-16T18:05:07.793Z
Answers.UserDisplayName: Kostya
Body: <p>When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=120" rel="nofollow noreferrer">page 98 of Sutton and Barto's book (2nd edition)</a> that:</p>
  <p><span class="math-container">$$
  \begin{aligned} 
  q_{\pi_{k}}\left(s, \pi_{k+1}(s)\right) 
  &amp;=
  q_{\pi_{k}}\left(s, \underset{a}{\arg \max } q_{\pi_{k}}(s, a)\right) 
  \\ 
  &amp;=
  \max _{a} q_{\pi_{k}}(s, a) 
  \\ 
  &amp; 
  \geq 
  q_{\pi_{k}}\left(s, \pi_{k}(s)\right) 
  \\ 
  &amp; 
  \geq v_{\pi_{k}}(s) \end{aligned}
  $$</span></p>
  <p>I don't understand why the last inequality is not an equality.</p>
  <p>The policy improvement theorem was derived <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=100" rel="nofollow noreferrer">on page 78</a> for deterministic policies.</p>
  <p>So, the <span class="math-container">$\pi_{k}(s)$</span> we see in <span class="math-container">$q_{\pi_k}(s, \pi_{k}(s))$</span> is a fixed action, call it <span class="math-container">$a'$</span>. Then, in this case, since <span class="math-container">$v_{\pi_k}(s)= \sum_a \pi_k(a|s) q_{\pi_k}(s, a) =   1 * q_{\pi_k}(s, a') = q_{\pi_k}(s, a')$</span> (where the second equality is because the probability of all other actions is 0), shouldn't the last inequality be an equality? When is it possible that we have a greater than relation?</p>
  
Tags: <reinforcement-learning><proofs><monte-carlo-methods><policy-improvement-theorem>
Title: When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?
UserDisplayName: Snowball
ThreadText: # When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?
  
  (Asked by: username_0 on 2021-05-15)
  
  When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on [page 98 of Sutton and Barto's book (2nd edition)](http://incompleteideas.net/book/RLbook2020.pdf#page=120) that:
  
  $$
  \begin{aligned}
  q\_{\pi\_{k}}\left(s, \pi\_{k+1}(s)\right)
  &=
  q\_{\pi\_{k}}\left(s, \underset{a}{\arg \max } q\_{\pi\_{k}}(s, a)\right)
  \\
  &=
  \max \_{a} q\_{\pi\_{k}}(s, a)
  \\
  &
  \geq
  q\_{\pi\_{k}}\left(s, \pi\_{k}(s)\right)
  \\
  &
  \geq v\_{\pi\_{k}}(s) \end{aligned}
  $$
  
  I don't understand why the last inequality is not an equality.
  
  The policy improvement theorem was derived [on page 78](http://incompleteideas.net/book/RLbook2020.pdf#page=100) for deterministic policies.
  
  So, the $\pi\_{k}(s)$ we see in $q\_{\pi\_k}(s, \pi\_{k}(s))$ is a fixed action, call it $a'$. Then, in this case, since $v\_{\pi\_k}(s)= \sum\_a \pi\_k(a|s) q\_{\pi\_k}(s, a) = 1 \* q\_{\pi\_k}(s, a') = q\_{\pi\_k}(s, a')$ (where the second equality is because the probability of all other actions is 0), shouldn't the last inequality be an equality? When is it possible that we have a greater than relation?
  
  **Tags:** reinforcement-learning, proofs, monte-carlo-methods, policy-improvement-theorem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-05-16. Score: 2 | Accepted answer
  
  You are right that the strict equality $q\_\pi(s,\pi(s)) = v\_\pi(s)$ is generally true for a deterministic policy $\pi$.
  
  The $\geq$ inequality is also correct, of course, and it *could be* that the authors' intention was to show that $\pi\_{k+1}$ and $\pi\_k$ satisfy the condition for the policy improvement theorem:
  
  > Let $\pi$ and $\pi'$ be any pair of deterministic policies such that, for all $s\in\mathcal{S}$,
  > $$q\_\pi(s,\pi'(s))\geq v\_\pi(s)\tag{4.7}$$
  
  So they kinda relaxed the equality to show that the condition is satisfied "word-for-word" for $\pi'=\pi\_{k+1}$ and $\pi=\pi\_k$.
  
  Although, I must say that they don't seem to be consistent in this - for example, they keep the strict equality at the derivation at the bottom of the page 78. So it might as well be that you've discovered a typo in Sutton and Barto.
  
  
  ---
  
  