Does epsilon-greedy approach always choose the "best action" (100% of the time) when it does not take the random path?

Question

I'm now reading the following blog post but on the epsilon-greedy approach, the author implied that the epsilon-greedy approach takes the action randomly with the probability epsilon, and take the best action 100% of the time with probability 1 - epsilon.

So for example, suppose that the epsilon = 0.6 with 4 actions. In this case, the author seemed to say that each action is taken with the following probability (suppose that the first action has the best value):

• action 1: 55% (.40 + .60 / 4)
• action 2: 15%
• action 3: 15%
• action 4: 15%

However, I feel like I learned that the epsilon-greedy only takes the action randomly with the probability of epsilon, and otherwise it is up to the policy function that decides to take the action. And the policy function returns the probability distribution of actions, not the identifier of the action with the best value. So for example, suppose that the epsilon = 0.6 and each action has 50%, 10%, 25%, and 15%. In this case, the probability of taking each action should be the following:

• action 1: 35% (.40 * .50 + .60 / 4)
• action 2: 19% (.40 * .10 + .60 / 4)
• action 3: 25% (.40 * .25 + .60 / 4)
• action 4: 21% (.40 * .15 + .60 / 4)

Is my understanding not correct here? Does the non-random part of the epsilon (1 - epsilon) always takes the best action, or does it select the action according to the probability distribution?

Answer 1

Epsilon-greedy is most commonly used to ensure that you have some element of exploration in algorithms that otherwise output deterministic policies.

For example, value-based algorithms (Q-Learning, SARSA, etc.) do not directly have a policy as output; they have values for states or state-action pairs as outputs. The standard policy we "extract" from that is a deterministic policy that simply tries to maximize the predicted value (or, technically, a "slightly" nondeterministic policy in that, in proper implementations, it should break ties (where there are multiple equal values at the top) randomly). For such algorithms, there is not sufficient inherent exploration, so we typically use something like epsilon-greedy to introduce an element of exploration. In these cases, both of the possible explanations in your question are identical.

In cases where your algorithm already produces complete probability distributions as outputs that do not so much focus all of the probability mass on a single or a couple of points, like the probability distribution you gave as an example in your question, it's generally not really necessary to use epsilon-greedy on top of it; you already get exploration inherently due to all actions having a decent probability assigned to them.

Now, I've actually personally mostly worked with value-based methods so far and not so much with e.g. policy gradient methods yet, so I'm not sure whether there tends to be a risk that they also "converge" to situations where they place too much probability mass on some actions and too little on others too quickly. If that's the case, I would expect an additional layer of epsilon-greedy exploration might be useful. And, in that case, I would indeed find your explanation the most natural. If I look through, for example, the PPO paper, I didn't find anything about them using epsilon-greedy in a quick glance. So, I suppose the combination of epsilon-greedy with "nondeterministic" policies (ignoring the case of tie-breaking in value-based methods here) simply isn't really a common combination.

Answer 2

Let me give an example of where epsilon-greedy comes unstuck: Imagine you have a environment with a very large branching-factor, like Go; if you were using epsilon-greedy for your exploration then you may find levels higher up the search tree are very well explored because they're hit on more regularly and so you'd want to select more greedily for those areas that are well explored, but further down the tree where actions are not explored you'd want to encourage more level of random exploration. Epsilon-greedy doesn't enable you to do that; it's one probability for all situations. So it's fine to use where the state-space is quite small, but not for large state-spaces.

Actor-critic methods, such as PPO, use the entropy (the measure of randomness) of the policy to form part of the loss function which inherently encourages exploration. To elaborate on this; early in training you'd expect high levels of entropy as all actions may have near-equal probability of being selected, but as the model explores the actions and garners rewards, it will gradually favour taking the actions which lead to higher rewards, and so the entropy will decrease as training progresses and it gradually starts to behave more greedily.

Because the entropy is added to the loss (or reward in case of RL, i.e. negative loss), the agent will get a higher reward if it were to select an action with low probability but ended up getting a high reward. That will have the effect of pushing up its probability of being re-selected again in future, while pushing down the previously more-favoured action probability.

This is good because it ensures there is always some element of curiosity, and it means it will act greedily in areas of the state-space it's already well explored, but continue to explore areas of the state-space which it's unfamiliar, which is why (in my opinion) it's a superior method than using epsilon-greedy.

That said, what I personally do is once training is converged, which I define as the agent isn't garnering higher rewards and there's very low entropy in the policy, then I add some small amount of epsilon-greedy just to force some level of exploration.