Epsilon-greedy

Epsilon-greedy is an exploration rule that, at each step, takes the action with the highest estimated value with probability $1-ϵ$ and a uniformly random action with probability $ϵ$. It is the simplest way to stop a learning agent from committing too early to an action that only looks best.

Definition

With $K$ actions and value estimates $Q(a)$, the policy is

The random branch can also pick the greedy action, which is why the greedy action's probability is $1-ϵ+ϵ/K$. In an MDP the same rule is applied per state using a Q-function.

Worked example

We simulated the classic 10-armed Gaussian testbed: 2,000 seeded problems, arm means drawn from $\mathcal{N}(0,1)$, rewards with unit noise, sample-average estimates, 1,000 steps. Over the last 100 steps, the share of steps choosing the truly best arm was:

• $ϵ=0$ (greedy): 36%, average reward 1.02
• $ϵ=0.01$: 59%, average reward 1.30
• $ϵ=0.1$: 80%, average reward 1.36

Greedy gets stuck early. A small $ϵ$ finds the best arm slowly but would eventually exploit it more; with $ϵ=0.1$ the agent can never pick the best arm more than $0.9+0.01=91\%$ of the time.

Limitations

• Linear regret with a fixed $ϵ$: a constant fraction of steps is wasted forever. Decaying schedules such as ${ϵ}_t\propto 1/t$ fix this in theory but need tuning.
• Undirected: it explores a clearly terrible action as often as a promising one. UCB and Thompson sampling direct exploration toward uncertain options.
• Shallow in long horizons: independent random actions rarely produce the long, coordinated sequences needed to find a distant sparse reward.

Why it matters

Epsilon-greedy is the default exploration in Q-learning and deep Q-networks, usually annealed from 1.0 to around 0.01 or 0.1 early in training. It is easy to reason about, which makes it a good baseline. Its blind randomness is also why it is a poor fit wherever a random action could be costly or unsafe.

Related terms

• Exploration-exploitation trade-off
• Upper confidence bound (UCB)
• Thompson sampling
• Q-learning
• Regret
• Multi-armed bandit

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net