Answers.Body: <blockquote>
  <p>I did not understand how the probability 1−ϵ+ϵ/|A|</p>
  </blockquote>
  <p>It's about mutually exclusive probabilities. If A and B are mutually exclusive events, and C can happen in both:</p>
  <p><a href="https://i.sstatic.net/q59sE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/q59sE.png" alt="Mutually exclusive probabilities" /></a></p>
  <p>Then, P(C) = P(C<span class="math-container">$\cap$</span>A) + P(C<span class="math-container">$\cap$</span>B) = (1−ϵ) +ϵ/|A|.</p>
  <p>In English: the prob of C happening = (the prob of both C and A happening) + (the prob of C and B happening).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-07T10:57:14.830Z
Answers.LastActivityDate: 2022-07-07T10:57:14.830Z
Answers.UserDisplayName: asdfasdfsdf
Answers.Body: <blockquote>
  <p>I did not understand how the probability  <span class="math-container">$1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$</span></p>
  </blockquote>
  <p>It is the sum of two mutally-exclusive possibilities:</p>
  <ul>
  <li><p>The agent chooses to exploit, selecting the greedy action with probability <span class="math-container">$1 - \epsilon$</span></p>
  </li>
  <li><p>The agent chooses to explore (probability <span class="math-container">$\epsilon$</span>), <strong>and</strong> so happens to randomly choose the original greedy action (probablility <span class="math-container">$\frac{1}{|\mathcal{A}|}$</span>). Combined probability <span class="math-container">$\frac{\epsilon}{|\mathcal{A}|}$</span>.</p>
  </li>
  </ul>
  <p>Although you <em>might</em> expect that exploring actions would exclude the greedy action, in <span class="math-container">$\epsilon$</span>-greedy approach they do not. It keeps implementation simple, although it does result in this extra term cropping up in the expression for probability of choosing the greedy action.</p>
  <p>Moving the excess probability to other actions, or adjusting the original exploration probability would also both result in an extra small term cropping up in other parts of the theory. There isn't a &quot;clean&quot; way to build an <span class="math-container">$\epsilon$</span>-soft action probability distribution without this slight added complexity.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-03T12:27:17.773Z
Answers.Text: I understand that there's a probability $1-\epsilon$ of selecting the greedy action and there's also a probability $\frac{\epsilon}{|\mathcal{A}|}$ of selecting the greedy action **when you select at random**, and that these 2 events never occur at the same time, so their probability of occurring at the same time is zero, hence you can "just" sum the probabilities. But why do you need to sum, if you select the greedy action with probability $1- \epsilon$?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-03T12:27:20.323Z
Answers.Text: Anyway, $\pi$ is a probability distribution, so the sum of all probabilities should be 1. What do you sum to give 1? I think this is unclear from your answer. Surely, $(1 - \epsilon) + \epsilon = 1$. But this is the sum of probabilities of selecting the greedy action and not selecting the greedy action.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-03T15:09:48.873Z
Answers.Text: @nbro: I am not sure what you are asking. You summarised it well in your first sentence. Your very last sentence is not quiite correct. If you change it to "But this is the sum of probabilities of exploiting and exploring" that would be accurate, and avoid the problem of assuming that exploring is mutually exclusive to taking the greedy action. In $\epsilon$-greedy, sometimes you "explore" and end up taking the greedy action anyway.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-03T16:09:40.180Z
Answers.Text: Actually, I asked 2 questions in order to clarify this answer. 1) Why do we sum the probability of taking the greedy action when we select it at random to the probability of selecting the greedy action when we do not take it at random? Yes, that is the "total" probability of selecting the greedy action, but then what is $1- \epsilon$? This you answered in the last comment, i.e. the probability of exploiting, which is not the same thing as the probability of taking the greedy action?! 2) How do you show that $\pi$ sums up to $1$ using these probabilities?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-03T16:09:42.270Z
Answers.Text: Maybe these weren't the original doubts that the OP had, but, in my view, this answer isn't clear enough without an answer to these 2 questions. One could ask these as separate questions on the site.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-30T12:47:50.477Z
Answers.LastActivityDate: 2022-01-30T12:53:13.497Z
Answers.LastEditDate: 2022-01-30T12:53:13.497Z
Answers.UserDisplayName: Neil Slater
Body: <p>In Sutton &amp; Barto's book on reinforcement learning (<a href="http://incompleteideas.net/book/RLbook2020.pdf#page=122" rel="nofollow noreferrer">section 5.4, p. 100</a>) we have the following:</p>
  <blockquote>
  <p>The on-policy method we present in this section uses <span class="math-container">$\epsilon$</span> greedy policies, meaning that most of the time they choose an action that has maximal estimated action value, but with probability <span class="math-container">$\epsilon$</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{\epsilon}{|\mathcal{A}|}$</span>, and the remaining bulk of
  the probability, <span class="math-container">$1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$</span>, is given to the greedy action.</p>
  </blockquote>
  <p>I understood the probability of a random action selection: since the total probability of random action selections is <span class="math-container">$\epsilon$</span> and since all actions can be selected as random we calculate the probability of an action to be selected randomly as <span class="math-container">$\frac{\epsilon}{|\mathcal{A}|}$</span>.</p>
  <p>However, I did not understand how the probability  <span class="math-container">$1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$</span> for greedy action selection was derived. How is it calculated?</p>
  
Tags: <reinforcement-learning><epsilon-greedy-policy>
Title: How is the probability of a greedy action in "$\epsilon$-greedy policies" derived?
UserDisplayName: user3489173
ThreadText: # How is the probability of a greedy action in "$\epsilon$-greedy policies" derived?
  
  (Asked by: username_0 on 2022-01-30)
  
  In Sutton & Barto's book on reinforcement learning ([section 5.4, p. 100](http://incompleteideas.net/book/RLbook2020.pdf#page=122)) we have the following:
  
  > The on-policy method we present in this section uses $\epsilon$ greedy policies, meaning that most of the time they choose an action that has maximal estimated action value, but with probability $\epsilon$ they instead select an action at random. That is, all nongreedy actions are given the minimal probability of selection, $\frac{\epsilon}{|\mathcal{A}|}$, and the remaining bulk of
  > the probability, $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$, is given to the greedy action.
  
  I understood the probability of a random action selection: since the total probability of random action selections is $\epsilon$ and since all actions can be selected as random we calculate the probability of an action to be selected randomly as $\frac{\epsilon}{|\mathcal{A}|}$.
  
  However, I did not understand how the probability $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$ for greedy action selection was derived. How is it calculated?
  
  **Tags:** reinforcement-learning, epsilon-greedy-policy
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-01-30. Score: 3 | Accepted answer
  
  > I did not understand how the probability $1-\epsilon+\frac{\epsilon}{|\mathcal{A}|}$
  
  It is the sum of two mutally-exclusive possibilities:
  
  * The agent chooses to exploit, selecting the greedy action with probability $1 - \epsilon$
  * The agent chooses to explore (probability $\epsilon$), **and** so happens to randomly choose the original greedy action (probablility $\frac{1}{|\mathcal{A}|}$). Combined probability $\frac{\epsilon}{|\mathcal{A}|}$.
  
  Although you *might* expect that exploring actions would exclude the greedy action, in $\epsilon$-greedy approach they do not. It keeps implementation simple, although it does result in this extra term cropping up in the expression for probability of choosing the greedy action.
  
  Moving the excess probability to other actions, or adjusting the original exploration probability would also both result in an extra small term cropping up in other parts of the theory. There isn't a "clean" way to build an $\epsilon$-soft action probability distribution without this slight added complexity.
  
  > **Comments:**
  > **username_3**: I understand that there's a probability $1-\epsilon$ of selecting the greedy action and there's also a probability $\frac{\epsilon}{|\mathcal{A}|}$ of selecting the greedy action **when you select at random**, and that these 2 events never occur at the same time, so their probability of occurring at the same time is zero, hence you can "just" sum the probabilities. But why do you need to sum, if you select the greedy action with probability $1- \epsilon$?  
  > **username_3**: Anyway, $\pi$ is a probability distribution, so the sum of all probabilities should be 1. What do you sum to give 1? I think this is unclear from your answer. Surely, $(1 - \epsilon) + \epsilon = 1$. But this is the sum of probabilities of selecting the greedy action and not selecting the greedy action.  
  > **username_2**: @nbro: I am not sure what you are asking. You summarised it well in your first sentence. Your very last sentence is not quiite correct. If you change it to "But this is the sum of probabilities of exploiting and exploring" that would be accurate, and avoid the problem of assuming that exploring is mutually exclusive to taking the greedy action. In $\epsilon$-greedy, sometimes you "explore" and end up taking the greedy action anyway.  
  > **username_3**: Actually, I asked 2 questions in order to clarify this answer. 1) Why do we sum the probability of taking the greedy action when we select it at random to the probability of selecting the greedy action when we do not take it at random? Yes, that is the "total" probability of selecting the greedy action, but then what is $1- \epsilon$? This you answered in the last comment, i.e. the probability of exploiting, which is not the same thing as the probability of taking the greedy action?! 2) How do you show that $\pi$ sums up to $1$ using these probabilities?  
  > **username_3**: Maybe these weren't the original doubts that the OP had, but, in my view, this answer isn't clear enough without an answer to these 2 questions. One could ask these as separate questions on the site.  
  
  ---
  
  ### Answer by username_1 on 2022-07-07. Score: 2
  
  > I did not understand how the probability 1−ϵ+ϵ/|A|
  
  It's about mutually exclusive probabilities. If A and B are mutually exclusive events, and C can happen in both:
  
  [![Mutually exclusive probabilities](https://i.sstatic.net/q59sE.png)](https://i.sstatic.net/q59sE.png)
  
  Then, P(C) = P(C$\cap$A) + P(C$\cap$B) = (1−ϵ) +ϵ/|A|.
  
  In English: the prob of C happening = (the prob of both C and A happening) + (the prob of C and B happening).
  
  
  ---
  
  