Answers.Body: <p>Epsilon-greedy is most commonly used to ensure that you have some element of exploration in algorithms that otherwise output deterministic policies. </p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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. <strong>If that's the case</strong>, 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 <a href="https://arxiv.org/abs/1707.06347" rel="nofollow noreferrer">PPO paper</a>, 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-03T09:03:54.560Z
Answers.Text: You are right that policy gradient methods are often inherently stochastic and on-policy. Adding exploration functions is possible but immediately makes them off-policy. Deterministic Policy Gradient is an example of that. Policy Gradient methods cannot use epsilon greedy or even plain greedy over the value function as the learned policy, because it is not differentiable.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-03T09:12:40.757Z
Answers.Text: @NeilSlater I'm not 100% sure on the "adding exploration immediately makes them off-policy". In the case of value-based methods, Sarsa is also on-policy but generally used in combination with epsilon-greedy. In the case of DPG, the impression I got from a very quick glance through the paper is that they really want to learn something deterministic in the first place, and then of course you get off-policyness since you need exploration during training. Differentiability is an important point I forgot about though!
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-03T09:39:15.050Z
Answers.Text: I meant that in the context of policy gradient methods. SARSA does not "add" epsilon greedy, it directly evaluates the current best epsilon greedy policy. If you add a higher epsilon to it, for more exploration, then yes it would become off-policy. You could use Expected SARSA as an off-policy method to do just that - learn optimal policy for epsilon 0.1 when behaving with policy for epsilon 0.3
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-03T08:29:01.277Z
Answers.LastActivityDate: 2018-08-03T08:29:01.277Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-20T10:35:54.320Z
Answers.LastActivityDate: 2019-05-20T10:35:54.320Z
Answers.UserDisplayName: BigBadMe
Body: <p>I'm now reading <a href="https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-7-action-selection-strategies-for-exploration-d3a97b7cceaf" rel="nofollow noreferrer">the following blog post</a> 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.</p>
  
  <p>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):</p>
  
  <ul>
  <li>action 1: 55% (.40 + .60 / 4) </li>
  <li>action 2: 15%</li>
  <li>action 3: 15%</li>
  <li>action 4: 15%</li>
  </ul>
  
  <p>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:</p>
  
  <ul>
  <li>action 1: 35% (.40 * .50 + .60 / 4)</li>
  <li>action 2: 19% (.40 * .10 + .60 / 4)</li>
  <li>action 3: 25% (.40 * .25 + .60 / 4)</li>
  <li>action 4: 21% (.40 * .15 + .60 / 4)</li>
  </ul>
  
  <p>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?</p>
  
Tags: <reinforcement-learning>
Title: Does epsilon-greedy approach always choose the "best action" (100% of the time) when it does not take the random path?
UserDisplayName: Blaszard
ThreadText: # Does epsilon-greedy approach always choose the "best action" (100% of the time) when it does not take the random path?
  
  (Asked by: username_0 on 2018-08-03)
  
  I'm now reading [the following blog post](https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-7-action-selection-strategies-for-exploration-d3a97b7cceaf) 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?
  
  **Tags:** reinforcement-learning
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-08-03. Score: 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](https://arxiv.org/abs/1707.06347), 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.
  
  > **Comments:**
  > **username_2**: You are right that policy gradient methods are often inherently stochastic and on-policy. Adding exploration functions is possible but immediately makes them off-policy. Deterministic Policy Gradient is an example of that. Policy Gradient methods cannot use epsilon greedy or even plain greedy over the value function as the learned policy, because it is not differentiable.  
  > **username_1**: @username_2 I'm not 100% sure on the "adding exploration immediately makes them off-policy". In the case of value-based methods, Sarsa is also on-policy but generally used in combination with epsilon-greedy. In the case of DPG, the impression I got from a very quick glance through the paper is that they really want to learn something deterministic in the first place, and then of course you get off-policyness since you need exploration during training. Differentiability is an important point I forgot about though!  
  > **username_2**: I meant that in the context of policy gradient methods. SARSA does not "add" epsilon greedy, it directly evaluates the current best epsilon greedy policy. If you add a higher epsilon to it, for more exploration, then yes it would become off-policy. You could use Expected SARSA as an off-policy method to do just that - learn optimal policy for epsilon 0.1 when behaving with policy for epsilon 0.3  
  
  ---
  
  ### Answer by username_3 on 2019-05-20. Score: 0
  
  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.
  
  
  ---
  
  