1
$\begingroup$

I'm currently studying the textbook Reinforcement Learning by Sutton and Barto. I can't seem to understand the derivation in Equation 5.2:

How did (a) become (b)?

How did (a) become (b)? In particular, why is the probability component in (b) computed as $\frac{\pi(a|s) - \frac{\epsilon}{|A(s)|}}{1-\epsilon}?$

Thanks in advance. :)

$\endgroup$
3
  • $\begingroup$ Please add the self-study tag & read its wiki. Then tell us what you understand thus far, what you've tried & where you're stuck. We'll provide hints to help you get unstuck. Please make these changes as just posting your homework & hoping someone will do it for you is grounds for closing. $\endgroup$ Mar 5, 2023 at 14:30
  • 1
    $\begingroup$ The text immediately beneath (5.2) is a full, accurate answer. $\endgroup$
    – whuber
    Mar 5, 2023 at 15:09
  • 2
    $\begingroup$ @kjetilbhalvorsen Thanks for the advice! :) However, I am not sure if this counts as self-study since this is not a routine exercise (nor is it my homework). Nevertheless, I made the changes to point out where my understanding falls short. $\endgroup$
    – prperalta
    Mar 5, 2023 at 23:47

1 Answer 1

1
$\begingroup$

As hinted in @whuber's comment, the summation in your blue box is a weighted average with nonnegative weights summing to 1, and as such it must be less than or equal to the largest number averaged where the largest number is nothing but $\max\limits_a q_\pi(s,a)$. To further clarify, each weight has the form $\frac{\pi(a|s)-\frac{\epsilon}{|\mathcal{A}(s)|}}{1-\epsilon}$ which is nonnegative since the $\epsilon$-soft policy $\pi$ to be improved upon is $\epsilon$-greedy (at least after first iteration in the book's algo), and also clearly $$\sum\limits_a \frac{\pi(a|s)-\frac{\epsilon}{|\mathcal{A}(s)|}}{1-\epsilon}=1$$ since the number of summation terms are just $|\mathcal{A}(s)|$. And since each such weight is nonnegative, it's obvious and easily provable that $$\max\limits_a q_\pi(s,a)=\sum\limits_a \frac{\pi(a|s)-\frac{\epsilon}{|\mathcal{A}(s)|}}{1-\epsilon}\max\limits_a q_\pi(s,a).$$ Now I believe you can make sense of the blue box line. Why it has this form? It’s so contrived that one can compare with the previous value function to show improvement for a generic state $s$ in the state space.

$\endgroup$
2
  • $\begingroup$ thanks for answering! quick question. isn't the annotation referring to the entire equation 5.2 instead of just the summation in (b)? $\endgroup$
    – prperalta
    Mar 6, 2023 at 16:35
  • 1
    $\begingroup$ Just the summation in (b) as I indicated above for your blue box. The rest I supposed from OP you're ok with. All the other steps seem straightforward except perhaps the first step containing you red box, which is based on the definition the the improved $\epsilon$-greedy policy $\pi'$ during which the policy evaluation step is going on. This Monte Carlo model-free learning without exploring starts via on-policy $\epsilon$-greedy policy is a variant of GPI. Let me know if you still have any questions. $\endgroup$
    – cinch
    Mar 6, 2023 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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