3
$\begingroup$

In Sutton & Barto's book on reinforcement learning (section 5.4, p. 100) 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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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$? $\endgroup$
    – nbro
    Commented Apr 3, 2022 at 12:27
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Apr 3, 2022 at 12:27
  • $\begingroup$ @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. $\endgroup$
    – Neil Slater
    Commented Apr 3, 2022 at 15:09
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Commented Apr 3, 2022 at 16:09
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Apr 3, 2022 at 16:09
2
$\begingroup$

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

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .