2
$\begingroup$

I came across this formula in Sutton And Barto: RL an Intro (2nd Edition) equation number 4.7 (page number 78).

If $\pi$ and $\pi'$ are deterministic policies and $q_\pi(s, \pi'(s)) \geq v_\pi(s)$ then the policy $\pi'$ is as good or better than $\pi$.

NOTE on Convention: As per the convention of the book goes, I think they are using rewards for state to action to state transition sequence rather than state to action transition.

My questions are:

  • Why are they comparing state value function to action value function?
  • Isn't it obvious the above equation might hold true (provided we select the best action among the possible actions) even for the policy $\pi$ since then the equation will change to $q_\pi(s, \pi(s)) \geq v_\pi(s)$ and we know $v_\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a|s)q_\pi(s, a)$?

What is the inconsistency here?

$\endgroup$
  • $\begingroup$ About the last question which might seem a little illegible, since in state value function we will weigh all the possible actions with their probability there is a chance a low reward action state might creep in, whereas in the action value function the weight-age is already bypassed and we are directly measuring the worth of a function which might be better or worse even though the actions taken from the same policy used to calculate state value. $\endgroup$ – DuttaA May 11 at 6:45
  • $\begingroup$ It's like trying to show that Newton's laws of motion were limited prior to Einstein's successful prediction of Mercury's orbit and the bend of light in the sun's corona. $\endgroup$ – FelicityC May 17 at 20:05
1
$\begingroup$

Why are they comparing state value function to action value function?

It is because $v_{\pi}(s)$ and $q_{\pi}(s,a)$ measure the same quantity at different stages of the trajectory. By comparing the values at the same $s$ and modifying how $a$ is selected, the proof makes assertions about how that choice impacts the value.

It is important to recall that $v_{\pi}(s)$ measures the expected future reward when starting in state $s$ and following policy $\pi$, and that $q_{\pi}(s,a)$ measures the expected future reward when starting in state $s$ and taking action $a$, thereafer following policy $\pi$. When $a$ is chosen using a deterministic $a = \pi(s)$ then $v_{\pi}(s) = q_{\pi}(s,\pi(s))$

Isn't it obvious the above equation might hold true

The inequality (it is not an equation) does strictly hold true, because the equation $v_{\pi}(s) = q_{\pi}(s,\pi(s))$ is true. However, that is not terribly useful, it doesn't prove anything new.

What is interesting is if you change the decision for $a$

(provided we select the best action among the possible actions)

You cannot do that. The policy decides the actions, by definition. Selecting a better action according to the action value function, and showing what that does is precisely what the proof is showing.

since then the equation will change to $q_\pi(s, \pi(s)) \geq v_\pi(s)$

$q_\pi(s, \pi(s)) = v_\pi(s)$ - yes your inequality holds, but is equivalent to not changing anything.

and we know $v_\pi(s) = \pi(a|s)q_\pi(s, \pi(s))$?

Here you have switched to using a non-deterministic policy and a deterministic policy in the same statement (you also have not defined $a$ properly), making your equation badly formed. The correct form would be:

$$v_\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a|s)q_\pi(s, a)$$

This is not a relevant form for the initial policy improvement theorem. However it does become relevant when the theory is adapted to show improving $\epsilon$-greedy policies later.


NOTE on Convention: As per the convention of the book goes, I think they are using rewards for state to action to state transition sequence rather than state to action transition.

That is not a convention in the book. In the book, the reward distribution is generally given as joint distribution with state transition in $p(s', r | s, a)$ - this is a very generic approach that models any discrete MDP, regardless of how the rewards are described as associated with any of $s, a, s'$ or a random factor.

Possibly the convention you are referring to is labelling the immediate reward as $R_{t+1}$, so that a small section of trajectory starting from state $S_t$ might be $S_t, A_t, R_{t+1}, S_{t+1}$ . . . some other texts will use $R_t$ here. However, that is not relevant to the policy improvement theorem, it would hold the same under either convention, just with slight relabelling of the reward indices.

$\endgroup$
  • $\begingroup$ What does deterministic mean? Does it mean for a state that action will be chosen with probability 1? Because only in that case v(s)=q(s,a) for a policy. $\endgroup$ – DuttaA May 11 at 8:44
  • 1
    $\begingroup$ @DuttA "What does deterministic mean?". It means that $\pi(s)$ outputs a single action value. If you use the form of the policy function $\pi(a|s)$ then yes one $a$ will output 1, and the rest 0 - however the proof you refer does not use that form. You cannot say "v(s)=q(s,a)", it is badly formed, as you have not defined $a$ properly (is it $\pi(s)$ ?) It might seem that I am nitpicking on that, but it seems to be loose thinking around this issue that has got you a bit lost in the proof. $\endgroup$ – Neil Slater May 11 at 8:54
  • 1
    $\begingroup$ Yes it is....so if the formula is valid only for deterministic policies, then it is not very generalized. $\endgroup$ – DuttaA May 11 at 8:55
  • 1
    $\begingroup$ @DuttaA: It proves policy improvement, which can be done using deterministic policies. Given that the optimal policy can always be deterministic in strict MDPs, it is as general as it needs to be, and definitely gives strong theoretical backing to Dynamic Programming approach of Policy Iteration $\endgroup$ – Neil Slater May 11 at 8:58
  • 1
    $\begingroup$ Later in the book, the proof is extended to show a similar convergence to "best" policy applies to $\epsilon$-greedy policies. Note that the best $\epsilon$-greedy policy is unlikely to be strictly optimal, but if you can reduce $\epsilon$ then you can get arbitrarily close to an optimal deterministic policy $\endgroup$ – Neil Slater May 11 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.