# Is this proof of $\epsilon$-greedy policy improvement correct?

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 .

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.

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$$.