4
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$ $\endgroup$ Commented Mar 10 at 13:35
  • $\begingroup$ 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. $\endgroup$ Commented Mar 10 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – cinch
    Commented Mar 11 at 7:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .