# If a policy is epsilon-greedy, is it technically stochastic?

Even though if exploration doesn't happen, it's deterministic.

• I found this is the book "Intro to RL": " In general, policies may be stochastic, specifying probabilities for each action." So, according to the book, it is not, but I was supposed to use a stochastic policy in n-step Sarsa, instead, I used epsilon-greedy, and the algorithm still learns. Jul 6, 2022 at 15:34
• I am not sure I understand the purpose of this question. Are you asking "how much stochasticity there must be in a policy in order to be considered a stochastic policy?" How do you want to measure that? Or are you asking whether a policy that sometimes is not stochastic should be considered stochastic or not? It's a matter of convention, but I would say that it makes more sense to consider this policy stochastic (because it's sometimes stochastic) than deterministic (because it's not always deterministic). Maybe you can classify policies into classes of stochasticity.
– nbro
Jul 6, 2022 at 20:26
• My point is - If you define determinism as a "view where all events are determined completely by previously existing causes", then $\epsilon$-greedy is not deterministic, so it must be the opposite? It may also be worth pointing out that we could consider $\epsilon$-greedy actually an infinite set of policies, where at one extreme you may have something that is completely random, at at the other extreme you have something that is completely deterministic.
– nbro
Jul 6, 2022 at 20:29

I would argue it is just stochastic because it chooses the current best action with probability $$1-\epsilon+\epsilon/|A|$$ and then selects randomly among the rest of the actions with the remaining probability $$\epsilon/|A|$$, where $$A$$ is the action space. The current best action is updated over time with running averages and may be the same one in the long run if it is truly a stationary bandit environment, but it will still explore.
• Technically it selects the current best action with probability $1 - \epsilon + \epsilon / \vert A \vert$. In the case where we select actions uniformly at random (with probability $\epsilon$), one of the options is generally again that we randomly select the best action :) Jul 6, 2022 at 19:16
• @Melanol With probability $\epsilon$, we sample one action uniformly at random from a set of $\vert A \vert$ actions. Sampling "uniformly at random" means we assign equal probabilities to all those actions, which means that each of those actions (including the "best" one) gets a probability of $1 / \vert A \vert$. That gets multiplied by $\epsilon$ because the whole sampling-uniformly-at-random thing only happens with probability $\epsilon$ Jul 7, 2022 at 9:45
Yes - you can think of an epsilon-greedy policy as a mixture of a policy that chooses an action at random (the stochastic part) and a possibly deterministic policy used otherwise. The value of epsilon gives the weight of the random component, and $$1-\epsilon$$ that of the other component.