Answers.Body: <p>As referenced in Sutton's RL book regarding policy improvement theorem (PIT):</p>
  <blockquote>
  <p>The policy improvement theorem applies to the two policies that we considered at the
  beginning of this section: an original deterministic policy, <span class="math-container">$\pi$</span>, and a changed policy, <span class="math-container">$\pi'$</span>, that is identical to <span class="math-container">$\pi$</span> except that <span class="math-container">$\pi'(s)=a \neq \pi(s)$</span>. For states other than <span class="math-container">$s$</span>, (4.7) holds because the two sides are equal.</p>
  </blockquote>
  <p>Note (4.7) is just your listed inequality, therefore with function approximation generally speaking the inequality (4.7) no longer holds for <em>all</em> states between every policy improvement step via their approximated function of feature vector and parameters, regardless you're using a simple linear function or a neural network approximator. This is because after policy improvement step to update the parameters, unlike the exact tabular cases, the updated parameters would possibly affect all other states' (action) values as well.</p>
  <p>--------further clarification after OP's addition----
  Convergence is a much harder topic. In some cases such as with Monte Carlo methods using nonlinear approximation, convergence can still be guaranteed because MC methods update the parameters based on the full return which provides unbiased estimates of the value function even with nonlinearity and above mentioned parameters global impact.</p>
  <p>However, in other cases such as TD(0) using nonlinear approximation, convergence guarantees are not as straightforward. TD(0) updates are based on bootstrapping where the value estimate is updated using the estimate of the next state's value. Nonlinear approximators can introduce biases and instability, leading to divergent behavior.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-10T13:35:23.320Z
Answers.Text: Thank you for your answer. I read the same book, and I accept what you are saying. However, I still miss the key point, I still see only "what book says" and no "here it's proven". From page 254: "It is no longer true that if we change the policy to improve the discounted value of one state then we are guaranteed to have improved the overall policy in any useful sense". So apparently, we are getting in one improvement step $\pi'$ which is equal to $\pi$ except $\pi'(s) \neq \pi(s)$
Answers.UserDisplayName: Samuel Krempasky
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-10T13:59:22.300Z
Answers.Text: For example non-linear approximation of MC guarantee convergence, but non-linear approximation of TD(0) doesn't. Why? Your answer seems to me applicable to both of them, even one of them has to converge, and other hasn't.
Answers.UserDisplayName: Samuel Krempasky
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-11T07:25:02.160Z
Answers.Text: You've significantly expanded your OP to several fronts including convergence difference for various model-free RL methods and a specific discounted case which is not policy gradient method. I've updated for your last comment. Perhaps if I have time will read your discounted case.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-10T07:28:27.387Z
Answers.LastActivityDate: 2024-03-11T07:18:13.197Z
Answers.LastEditDate: 2024-03-11T07:18:13.197Z
Answers.UserDisplayName: cinch
Body: <p>Policy improvement theorem is proven as follows:</p>
  <p><span class="math-container">$$v_\pi(s) = \sum_{a \in A} \pi(a|s)q_\pi(a,s) \leq \max_{a \in A} q_\pi(a,s) = q_\pi(\pi'(s), s)$$</span></p>
  <p>What step of the proof does not hold for function approximation?</p>
  <p>Or maybe the question could be asked differently. As referenced in Sutton's RL book in Chapter 10:</p>
  <blockquote>
  <p>It is no longer true that if we change the policy to improve the
  discounted value of one state then we are guaranteed to have improved
  the overall policy in any useful sense.</p>
  </blockquote>
  <p>Why?</p>
  
Tags: <reinforcement-learning><proofs><function-approximation><policy-improvement-theorem>
Title: Why policy improvement theorem can't be applied in case of function approximation?
UserDisplayName: Samuel Krempasky
ThreadText: # Why policy improvement theorem can't be applied in case of function approximation?
  
  (Asked by: username_0 on 2024-03-09)
  
  Policy improvement theorem is proven as follows:
  
  $$v\_\pi(s) = \sum\_{a \in A} \pi(a|s)q\_\pi(a,s) \leq \max\_{a \in A} q\_\pi(a,s) = q\_\pi(\pi'(s), s)$$
  
  What step of the proof does not hold for function approximation?
  
  Or maybe the question could be asked differently. As referenced in Sutton's RL book in Chapter 10:
  
  > It is no longer true that if we change the policy to improve the
  > discounted value of one state then we are guaranteed to have improved
  > the overall policy in any useful sense.
  
  Why?
  
  **Tags:** reinforcement-learning, proofs, function-approximation, policy-improvement-theorem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-03-10. Score: 6 | Accepted answer
  
  As referenced in Sutton's RL book regarding policy improvement theorem (PIT):
  
  > The policy improvement theorem applies to the two policies that we considered at the
  > beginning of this section: an original deterministic policy, $\pi$, and a changed policy, $\pi'$, that is identical to $\pi$ except that $\pi'(s)=a \neq \pi(s)$. For states other than $s$, (4.7) holds because the two sides are equal.
  
  Note (4.7) is just your listed inequality, therefore with function approximation generally speaking the inequality (4.7) no longer holds for *all* states between every policy improvement step via their approximated function of feature vector and parameters, regardless you're using a simple linear function or a neural network approximator. This is because after policy improvement step to update the parameters, unlike the exact tabular cases, the updated parameters would possibly affect all other states' (action) values as well.
  
  --------further clarification after OP's addition----
  Convergence is a much harder topic. In some cases such as with Monte Carlo methods using nonlinear approximation, convergence can still be guaranteed because MC methods update the parameters based on the full return which provides unbiased estimates of the value function even with nonlinearity and above mentioned parameters global impact.
  
  However, in other cases such as TD(0) using nonlinear approximation, convergence guarantees are not as straightforward. TD(0) updates are based on bootstrapping where the value estimate is updated using the estimate of the next state's value. Nonlinear approximators can introduce biases and instability, leading to divergent behavior.
  
  > **Comments:**
  > **username_0**: Thank you for your answer. I read the same book, and I accept what you are saying. However, I still miss the key point, I still see only "what book says" and no "here it's proven". From page 254: "It is no longer true that if we change the policy to improve the discounted value of one state then we are guaranteed to have improved the overall policy in any useful sense". So apparently, we are getting in one improvement step $\pi'$ which is equal to $\pi$ except $\pi'(s) \neq \pi(s)$  
  > **username_0**: For example non-linear approximation of MC guarantee convergence, but non-linear approximation of TD(0) doesn't. Why? Your answer seems to me applicable to both of them, even one of them has to converge, and other hasn't.  
  > **username_1**: You've significantly expanded your OP to several fronts including convergence difference for various model-free RL methods and a specific discounted case which is not policy gradient method. I've updated for your last comment. Perhaps if I have time will read your discounted case.  
  
  ---
  
  