Het epsilon-greedy ($\varepsilon$-greedy) algoritme is een eenvoudige maar zeer effectieve strategie voor het aanpakken van het multi-armed bandit probleem. Hoewel het mogelijk niet zo robuust is als sommige andere methoden voor deze specifieke taak, maken de eenvoud en veelzijdigheid het breed toepasbaar binnen het domein van reinforcement learning.

Werking

Het algoritme volgt de volgende stappen:

1. Initialiseren van de schattingen van de actiewaarden $Q(a)$ voor elke actie $a$;
2. Kies een actie volgens de volgende regel:
   • Met kans $\varepsilon$: kies een willekeurige actie (exploratie);
   • Met kans $1 - \varepsilon$: kies de actie met de hoogste geschatte waarde (exploitatie).
3. Voer de actie uit en observeer de beloning;
4. Werk de schatting van de actiewaarde $Q(a)$ bij op basis van de waargenomen beloning;
5. Herhaal stappen 2-4 voor een vast aantal tijdstappen.

De hyperparameter $\varepsilon$ (epsilon) bepaalt de afweging tussen exploratie en exploitatie:

• Een hoge $\varepsilon$ (bijv. 0.5) stimuleert meer exploratie;
• Een lage $\varepsilon$ (bijv. 0.01) geeft de voorkeur aan exploitatie van de best bekende actie.

Voorbeeldcode

class EpsilonGreedyAgent:
  def __init__(self, n_actions, epsilon):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.epsilon = epsilon # epsilon
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters

  def select_action(self):
    """Select an action according to the epsilon-greedy strategy"""
    # With probability epsilon - random action
    if np.random.rand() < self.epsilon:
      return np.random.randint(self.n_actions)
    # Otherwise - action with highest estimated action value
    else:
      return np.argmax(self.Q)

  def update(self, action, reward):
    """Update the values using sample average estimate"""
    # Increasing the action selection counter
    self.N[action] += 1
    # Updating the estimated action value
    self.Q[action] += (reward - self.Q[action]) / self.N[action]

Aanvullende informatie

De efficiëntie van het $\varepsilon$-greedy algoritme is sterk afhankelijk van de waarde van $\varepsilon$. Twee strategieën worden vaak gebruikt om deze waarde te bepalen:

• Vaste $\varepsilon$: dit is de meest algemene optie, waarbij de waarde van $\varepsilon$ als een constante wordt gekozen (bijvoorbeeld 0,1);
• Afnemende $\varepsilon$: de waarde van $\varepsilon$ neemt in de loop van de tijd af volgens een bepaald schema (bijvoorbeeld begint bij 1 en neemt geleidelijk af tot 0) om verkenning in de vroege fasen te stimuleren.

Samenvatting

Het $\varepsilon$-greedy algoritme is een basisbenadering voor het balanceren van exploratie en exploitatie. Hoewel eenvoudig, vormt het de basis voor het begrijpen van meer geavanceerde strategieën zoals upper confidence bound (UCB) en gradient bandits.