Answers.Body: <p>I read section 2.2 of Sutton and Barto, and I understand your confusion: the <span class="math-container">$\epsilon$</span>-greedy algorithm is not defined precisely on page 27-28. Selecting an action randomly &quot;every once in awhile&quot; with probability <span class="math-container">$\epsilon$</span> means selecting an action randomly with probability <span class="math-container">$\epsilon$</span> at each timestep and selecting an action greedily with probability <span class="math-container">$1-\epsilon$</span> at each timestep. This definition is standard and will be clear as you progress through the book and other relevant literature. For reference, the <span class="math-container">$\epsilon$</span>-greedy algorithm is used in the pseudocode on page 32 of Sutton and Barto.</p>
  <p>The key distinction in this problem is that it's asking for <strong>the probability that the greedy action is selected, NOT the probability that an action is selected greedily</strong>. Specifically, the greedy action can be selected when the agent selects an action randomly because the greedy action is in the action space and the <em>entire</em> action space is sampled uniformly when selecting an action randomly.</p>
  <p>Since <span class="math-container">$\epsilon=0.5$</span>, the agent will select an action greedily 50% of the time, which will 100% of the time be the greedy action. The agent will select an action randomly the other 50% of the time. Since there are two actions in the action space, the greedy action will be selected 50% of the time when the agent selects an action randomly. Therefore, the probability that the greedy action is selected at any single timestep is as follows:</p>
  <p><span class="math-container">\begin{align}
   &amp;p(\mbox{greedy action}) \\
  =\ &amp;p(\mbox{greedy action AND greedy selection}) + p(\mbox{greedy action AND random selection})\\
  =\ &amp;p(\mbox{greedy selection}) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) \\ 
  &amp;\hspace{1em}+ p(\mbox{random selection})\cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &amp;(1-\epsilon) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + \epsilon \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &amp;0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + 0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &amp;0.5 \cdot 1 + 0.5 \cdot 0.5 \\ 
  =\ &amp;0.5+ 0.25 \\ 
  =\ &amp;0.75.
  \end{align}</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-24T00:08:32.780Z
Answers.Text: Thank you for your explanation, it's very clear and helpful. So the key difference that I've missed is between the action selection and the greedy selection. Thanks again !
Answers.UserDisplayName: Daviiid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-07-28T09:31:30.833Z
Answers.Text: could it be equal to $1$ if both actions yield the same reward, i.e. both actions are greedy?
Answers.UserDisplayName: user
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-23T22:12:27.053Z
Answers.LastActivityDate: 2021-05-23T22:12:27.053Z
Answers.UserDisplayName: DeepQZero
Body: <p>I'm new to reinforcement learning and I'm going through <a href="http://incompleteideas.net/book/the-book.html" rel="noreferrer">Sutton and Barto</a>. Exercise 2.1 states the following:</p>
  <blockquote>
  <p>In <span class="math-container">$\varepsilon$</span>-greedy action selection, for the case of two actions and <span class="math-container">$\varepsilon=0.5$</span>, what is the probability that the greedy action is selected?</p>
  </blockquote>
  <p>They describe the <span class="math-container">$\varepsilon$</span>-greedy method on pages 27-28 as follows:</p>
  <blockquote>
  <p>...behave greedily most of the time, but every once in a while,  say with small probability <span class="math-container">$\varepsilon$</span>, instead select randomly from among all the actions with equal probability...</p>
  </blockquote>
  <p>The above method makes the agent select an action randomly &quot;every once in a while&quot; from the action space uniformly with probability <span class="math-container">$\varepsilon$</span>. I find the question imprecise since we don't know the &quot;once in a while&quot; in this exercise (i.e. is it once every <span class="math-container">$50$</span> timesteps? every time step?). If it's for every timestep, isn't it like a Bernouli problem where the parameter is <span class="math-container">$0.5$</span>? I'd say that the agent has a <span class="math-container">$0.5$</span> chance to select a greedy action but I'm not sure at all.</p>
  
Tags: <reinforcement-learning><multi-armed-bandits><epsilon-greedy-policy>
Title: What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?
UserDisplayName: Daviiid
ThreadText: # What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?
  
  (Asked by: username_0 on 2021-05-23)
  
  I'm new to reinforcement learning and I'm going through [Sutton and Barto](http://incompleteideas.net/book/the-book.html). Exercise 2.1 states the following:
  
  > In $\varepsilon$-greedy action selection, for the case of two actions and $\varepsilon=0.5$, what is the probability that the greedy action is selected?
  
  They describe the $\varepsilon$-greedy method on pages 27-28 as follows:
  
  > ...behave greedily most of the time, but every once in a while, say with small probability $\varepsilon$, instead select randomly from among all the actions with equal probability...
  
  The above method makes the agent select an action randomly "every once in a while" from the action space uniformly with probability $\varepsilon$. I find the question imprecise since we don't know the "once in a while" in this exercise (i.e. is it once every $50$ timesteps? every time step?). If it's for every timestep, isn't it like a Bernouli problem where the parameter is $0.5$? I'd say that the agent has a $0.5$ chance to select a greedy action but I'm not sure at all.
  
  **Tags:** reinforcement-learning, multi-armed-bandits, epsilon-greedy-policy
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-05-23. Score: 6 | Accepted answer
  
  I read section 2.2 of Sutton and Barto, and I understand your confusion: the $\epsilon$-greedy algorithm is not defined precisely on page 27-28. Selecting an action randomly "every once in awhile" with probability $\epsilon$ means selecting an action randomly with probability $\epsilon$ at each timestep and selecting an action greedily with probability $1-\epsilon$ at each timestep. This definition is standard and will be clear as you progress through the book and other relevant literature. For reference, the $\epsilon$-greedy algorithm is used in the pseudocode on page 32 of Sutton and Barto.
  
  The key distinction in this problem is that it's asking for **the probability that the greedy action is selected, NOT the probability that an action is selected greedily**. Specifically, the greedy action can be selected when the agent selects an action randomly because the greedy action is in the action space and the *entire* action space is sampled uniformly when selecting an action randomly.
  
  Since $\epsilon=0.5$, the agent will select an action greedily 50% of the time, which will 100% of the time be the greedy action. The agent will select an action randomly the other 50% of the time. Since there are two actions in the action space, the greedy action will be selected 50% of the time when the agent selects an action randomly. Therefore, the probability that the greedy action is selected at any single timestep is as follows:
  
  \begin{align}
  &p(\mbox{greedy action}) \\
  =\ &p(\mbox{greedy action AND greedy selection}) + p(\mbox{greedy action AND random selection})\\
  =\ &p(\mbox{greedy selection}) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) \\
  &\hspace{1em}+ p(\mbox{random selection})\cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &(1-\epsilon) \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + \epsilon \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{greedy selection}) + 0.5 \cdot p(\mbox{greedy action}\ |\ \mbox{random selection})\\
  =\ &0.5 \cdot 1 + 0.5 \cdot 0.5 \\
  =\ &0.5+ 0.25 \\
  =\ &0.75.
  \end{align}
  
  > **Comments:**
  > **username_0**: Thank you for your explanation, it's very clear and helpful. So the key difference that I've missed is between the action selection and the greedy selection. Thanks again !  
  > **username_2**: could it be equal to $1$ if both actions yield the same reward, i.e. both actions are greedy?  
  
  ---
  
  