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

The following paragraph about $$\epsilon$$-greedy policies can be found at the end of page 100, under section 5.4, of the book "Reinforcement Learning: An Introduction" by Richard Sutton and Andrew Barto (second edition, 2018).

but with probability $$\varepsilon$$ they instead select an action at random. That is, all nongreedy actions are given the minimal probability of selection, $$\frac{\varepsilon}{|\mathcal{A}(s)|}$$, and the remaining bulk of the probability, $$1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$$, is given to the greedy action. The $$\varepsilon$$-greedy policies are

So, the non-greedy actions are given the probability $$\frac{\varepsilon}{|\mathcal{A}(s)|}$$, and the greedy action is given the probability $$1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$$. All clear up to this point.

However, I have a doubt in the policy improvement theorem that is mentioned in page 101, under section 5.4. I have enclosed a copy of this proof for your convenience:

\begin{aligned} q_{\pi}(s, \pi^{\prime}(s)) &=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\ &=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+(1-\varepsilon) \max _{a} q_{\pi}(s, a) \\ & \geq \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+(1-\varepsilon) \sum_{a} \frac{\pi(a \mid s)-\frac{\varepsilon}{|\mathcal{A}(s)|}}{1-\varepsilon} q_{\pi}(s, a)\\ &=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)-\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\sum_{a} \pi(a \mid s) q_{\pi}(s, a) \\ &=v_{\pi}(s) . \end{aligned}

My question is shouldn't the greedy action be chosen with a probability of $$1-\varepsilon+\frac{\varepsilon}{|\mathcal{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:

\begin{aligned} q_{\pi}(s, \pi^{\prime}(s)) &=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\ &=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+ \left( 1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|} \right) \max _{a} q_{\pi}(s, a) \\ & \geq \frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\left(1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|} \right) \sum_{a} \frac{\pi(a \mid s)-\frac{\varepsilon}{|\mathcal{A}(s)|}}{1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|} } q_{\pi}(s, a)\\ &=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)-\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+\sum_{a} \pi(a \mid s) q_{\pi}(s, a) \\ &=v_{\pi}(s) . \end{aligned}

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.

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