Answers.Body: <p>The weights <em>do</em> sum to one. Note that in the second line where we have 
  <span class="math-container">$$\frac{\epsilon}{|\mathcal{A}(s)|} \sum_a q_{\pi}(s,a) + (1-\epsilon)\max_aq_{\pi}(s,a) \; ,$$</span>
  the sum is over the whole action space, including the greedy action, so the sum of the weights will be <span class="math-container">$\frac{\epsilon}{|\mathcal{A}(s)|} \times |\mathcal{A}(s)| + (1-\epsilon) = 1$</span>. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-27T13:29:25.450Z
Answers.LastActivityDate: 2020-05-28T13:39:00.260Z
Answers.LastEditDate: 2020-05-28T13:39:00.260Z
Answers.UserDisplayName: David
Body: <p>The following paragraph about <span class="math-container">$\epsilon$</span>-greedy policies can be found at the end of <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=122" rel="nofollow noreferrer">page 100, under section 5.4</a>, of the book &quot;Reinforcement Learning: An Introduction&quot; by Richard Sutton and Andrew Barto (second edition, 2018).</p>
  <blockquote>
  <p>but with probability <span class="math-container">$\varepsilon$</span> they instead select an action at random. That is, all nongreedy actions are given the minimal probability of selection, <span class="math-container">$\frac{\varepsilon}{|\mathcal{A}(s)|}$</span>, and the remaining bulk of the probability, <span class="math-container">$1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$</span>, is given to the greedy action. The <span class="math-container">$\varepsilon$</span>-greedy policies are</p>
  </blockquote>
  <p>So, the non-greedy actions are given the probability  <span class="math-container">$\frac{\varepsilon}{|\mathcal{A}(s)|}$</span>, and the greedy action is given the probability <span class="math-container">$1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$</span>. All clear up to this point.</p>
  <p>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:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  q_{\pi}(s, \pi^{\prime}(s)) &amp;=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\
  &amp;=\frac{\varepsilon}{|\mathcal{A}(s)|} \sum_{a} q_{\pi}(s, a)+(1-\varepsilon) \max _{a} q_{\pi}(s, a) \\
  &amp; \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)\\
  &amp;=\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) \\
  &amp;=v_{\pi}(s) .
  \end{aligned}
  $$</span></p>
  <p>My question is <strong>shouldn't the greedy action be chosen with a probability of <span class="math-container">$1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}$</span></strong>?</p>
  <p>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:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  q_{\pi}(s, \pi^{\prime}(s)) 
  &amp;=\sum_{a} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\
  &amp;=\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) \\
  &amp; \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)\\
  &amp;=\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) \\
  &amp;=v_{\pi}(s) .
  \end{aligned}
  $$</span></p>
  <p>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.</p>
  
Tags: <reinforcement-learning><proofs><epsilon-greedy-policy><policy-improvement-theorem>
Title: Is this proof of $\epsilon$-greedy policy improvement correct?
UserDisplayName: Jarvis1997
ThreadText: # Is this proof of $\epsilon$-greedy policy improvement correct?
  
  (Asked by: username_0 on 2020-05-27)
  
  The following paragraph about $\epsilon$-greedy policies can be found at the end of [page 100, under section 5.4](http://incompleteideas.net/book/RLbook2020.pdf#page=122), 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.
  
  **Tags:** reinforcement-learning, proofs, epsilon-greedy-policy, policy-improvement-theorem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-05-27. Score: 6 | Accepted answer
  
  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$.
  
  
  ---
  
  