What is the probability of selecting the greedy action in a 0.5-greedy selection method for the 2-armed bandit problem?

Question

I'm new to reinforcement learning and I'm going through Sutton and Barto. 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.

Answer 1

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}