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

CC BY-SA 4.0
2021-05-24T00:08:32.780Z
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 !
Daviiid
CC BY-SA 4.0
2021-07-28T09:31:30.833Z
could it be equal to $1$ if both actions yield the same reward, i.e. both actions are greedy?
user
CC BY-SA 4.0
2021-05-23T22:12:27.053Z
2021-05-23T22:12:27.053Z
DeepQZero
<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>

<reinforcement-learning><multi-armed-bandits><epsilon-greedy-policy>
What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?
Daviiid
# 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?  

---

