6
$\begingroup$

The text book being referred to, in this question is "Reinforcement Learning: An introduction" by Richard Sutton and Andrew Barto (second edition, 2018). For your convenience, I have enclosed the following part of a paragraph about $\epsilon$-greedy policies in the book, to convey my question with a better clarity. This paragraph can be found at the end of Pg 100, under section 5.4 .

enter image description here So, the non-greedy actions are given the probability $\frac{\epsilon}{|\mathscr{A}(s)|}$, and the greedy action is given the probability $1-\epsilon+\frac{\epsilon}{|\mathscr{A}(s)|}$. All clear upto this point. However, I have a doubt in the policy improvement theorem that is mentioned in Pg 101, under section 5.4. I have enclosed a copy of this proof for your convenience: $$q_\pi(s, \pi'(s)) = \sum_a \pi'(a|s)q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + (1-\epsilon)\max_a q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + (1-\epsilon)\sum_a\frac{\pi(a|s) - \frac{\epsilon}{|\mathscr{A}(s)|}}{1-\epsilon}q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) - \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + \sum_a \pi(a|s)q_\pi(s,a) \\ = v_\pi(s)$$

My question is, shoundn't the greedy action be chosen with a probability of $1-\epsilon + \frac{\epsilon}{|\mathscr{A}(s)|}$? The weighing factors do not add up to 1, as they are probability values. With this argument, the proof (with a slight modification) would be: $$q_\pi(s, \pi'(s)) = \sum_a \pi'(a|s)q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + (1-\epsilon + \frac{\epsilon}{|\mathscr{A}(s)|})\max_a q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + (1-\epsilon + \frac{\epsilon}{|\mathscr{A}(s)|})\sum_a\frac{\pi(a|s) - \frac{\epsilon}{|\mathscr{A}(s)|}}{1-\epsilon + \frac{\epsilon}{|\mathscr{A}(s)|}}q_\pi(s,a) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) - \frac{\epsilon}{|\mathscr{A}(s)|}\sum_aq_\pi(s,a) + \sum_a \pi(a|s)q_\pi(s,a) \\ = v_\pi(s)$$

Though the end result isn't changed, I just want to know what I am conceptually missing, in order to understand the proof that is originally provided. I am extremely sorry, if this is something very elementary that I am not able to fathom.

Thank you so much for your time.

$\endgroup$
6
$\begingroup$

The weights do sum to one. Note that in the second line where we have $$\frac{\epsilon}{|\mathcal{A}(s)|} \sum_a q_{\pi}(s,a) + (1-\epsilon)\max_aq_{\pi}(s,a) \; ,$$ the sum is over the whole action space, including the greedy action, so the sum of the weights will be $\frac{\epsilon}{|\mathcal{A}(s)|} \times |\mathcal{A}(s)| + (1-\epsilon) = 1$.

| improve this answer | |
$\endgroup$

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.