ε-Greedy Algorithm (Exploration vs.
Exploitation Strategy)
• The ε-Greedy Algorithm is one of the most widely used methods to solve the multi-armed
bandit problem in Reinforcement Learning. Its purpose is to balance exploration (trying new
actions) with exploitation (using the best-known action so far).
• The ε-Greedy Algorithm is a simple yet powerful solution to the exploration–exploitation
dilemma.
• It works well in practice, but the choice of ε (and whether to anneal it) significantly affects
performance.
• It is commonly used as a baseline algorithm in multi-armed bandits and many reinforcement
learning problems.
Core Idea
Exploration Rate (ε):
• Epsilon (ε) is a probability value in the range 0 ≤ ε ≤ 1.
• With probability ε, the agent explores by selecting a random action.
• With probability 1 − ε, the agent exploits by selecting the greedy action (the action with the
highest estimated value so far).
• Exploration ensures the algorithm continues to discover new possibilities.
• Exploitation ensures the algorithm mostly sticks with what seems best.
Extreme Cases:
ε = 1 → Full exploration (the agent ignores past knowledge and only explores).
ε = 0 → Pure exploitation (the agent always picks the best-known action; no new exploration).
Steps of the ε-Greedy Algorithm
1)Initialize:
Set ε (e.g., 0.1).
Initialize payoff estimates for each slot machine/action.
2)Action Selection:
Generate a random number between 0 and 1.
If the number < ε → choose a random action (exploration).
Else → choose the action with the best current average payoff (exploitation).
3)Update:
After selecting an action, observe its reward.
Update the estimated payoff for that action.
4)Repeat for all trials.
Illustrative Example
Suppose there are 3 slot machines (A, B, C):
True average rewards: A = 0.4, B = 0.6, C = 0.5.
Using ε = 0.1:
In 10% of cases, the algorithm tries a random machine (maybe discovers B).
In 90% of cases, it chooses the best-known machine so far.
Over time, it learns that Machine B is best and plays it most of the time.
Advantages
• Avoids being stuck forever: Unlike the naïve algorithm, there’s always a chance (ε) of trying
other actions.
• Efficient exploitation: Most of the time, the best-known action is chosen, maximizing
reward.
• Early exploitation: The algorithm doesn’t wait too long—it starts exploiting while still
exploring.
Disadvantages
Choice of ε is tricky:
• If ε is too large → too much random exploration (wastes trials).
• If ε is too small → not enough exploration (might miss the best option).
• Slower convergence: At small ε values, it might take longer to discover the true best
machine.
Dynamic / Decaying Epsilon:
• Initially, a high ε (e.g., ε = 1) encourages exploration when the environment is unfamiliar.
• Over time, ε decreases gradually (ε → 0), shifting the agent’s behavior from exploration toward
exploitation as it becomes more confident in its action-value estimates.
• Example:
ε = 0.9 → 90% exploration, 10% exploitation.
ε = 0.1 → 10% exploration, 90% exploitation.
This ensures the agent remains greedy but never stops exploring completely, avoiding the risk of
missing better actions.
Advantage Decaying Epsilon:
The decaying ε-greedy balances short-term exploration with long-term exploitation, making it practical for
Improvement: Annealing ε
• Annealing means gradually reducing ε over time:
• Start with a large ε (more exploration early on).
• Gradually decrease ε (focus more on exploitation as knowledge improves).
Example:
First 100 trials: ε = 0.5 (lots of exploration).
Later trials: ε = 0.1 (mostly exploitation).
This balances learning early and reward optimization later.