Der Epsilon-Greedy ($\varepsilon$-greedy) Algorithmus ist eine unkomplizierte, aber äußerst effektive Strategie zur Lösung des Multi-Armed-Bandit-Problems. Obwohl er für diese spezielle Aufgabe möglicherweise nicht so robust ist wie einige andere Methoden, machen ihn seine Einfachheit und Vielseitigkeit in der Praxis des Reinforcement Learnings weit verbreitet.

Funktionsweise

Der Algorithmus folgt diesen Schritten:

1. Initialisierung der Aktionswertschätzungen $Q(a)$ für jede Aktion $a$;
2. Auswahl einer Aktion nach folgender Regel:
   • Mit Wahrscheinlichkeit $\varepsilon$: Auswahl einer zufälligen Aktion (Exploration);
   • Mit Wahrscheinlichkeit $1 - \varepsilon$: Auswahl der Aktion mit dem höchsten geschätzten Wert (Exploitation).
3. Ausführung der Aktion und Beobachtung der Belohnung;
4. Aktualisierung der Aktionswertschätzung $Q(a)$ basierend auf der beobachteten Belohnung;
5. Wiederholung der Schritte 2-4 für eine feste Anzahl von Zeitschritten.

Der Hyperparameter $\varepsilon$ (Epsilon) steuert den Kompromiss zwischen Exploration und Exploitation:

• Ein hoher $\varepsilon$ (z. B. 0,5) fördert mehr Exploration;
• Ein niedriger $\varepsilon$ (z. B. 0,01) bevorzugt die Ausnutzung der bisher besten bekannten Aktion.

Beispielcode

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]

Zusätzliche Informationen

Die Effizienz des $\varepsilon$-greedy-Algorithmus hängt stark vom Wert von $\varepsilon$ ab. Zwei Strategien werden üblicherweise zur Auswahl dieses Wertes verwendet:

• Festes $\varepsilon$: Dies ist die allgemeinste Option, bei der der Wert von $\varepsilon$ als Konstante gewählt wird (z. B. 0,1);
• Abnehmendes $\varepsilon$: Der Wert von $\varepsilon$ nimmt im Laufe der Zeit gemäß einem bestimmten Zeitplan ab (z. B. beginnt bei 1 und verringert sich schrittweise auf 0), um in den frühen Phasen die Exploration zu fördern.

Zusammenfassung

Der $\varepsilon$-greedy-Algorithmus ist ein Basisansatz zur Balance zwischen Exploration und Exploitation. Obwohl er einfach ist, dient er als Grundlage für das Verständnis fortgeschrittenerer Strategien wie Upper Confidence Bound (UCB) und Gradienten-Banditen.