Der Upper Confidence Bound (UCB) Algorithmus ist ein beliebter und effektiver Ansatz zur Lösung des Multi-Armed Bandit Problems. Er bietet starke mathematische Garantien für eine schnelle Konvergenz und optimiert den Erkundungsprozess.

Trotz seiner Effektivität bei der Lösung des MAB-Problems weist der UCB-Algorithmus einige bemerkenswerte Einschränkungen auf, die seine Anwendung im breiteren Bereich des Reinforcement Learnings begrenzen:

• Annahme stationärer Belohnungen: Der UCB-Algorithmus geht davon aus, dass sich die Belohnungsverteilungen im Zeitverlauf nicht ändern;
• Einschränkungen bezüglich Zustands- und Aktionsräumen: Um überhaupt Aktionen nach einer bestimmten Logik auswählen zu können, erfordert der UCB-Algorithmus, dass jede Aktion in jedem Zustand mindestens einmal ausprobiert wird.

Während sich die erste Einschränkung durch eine geringfügige Modifikation des Algorithmus beheben lässt, bleibt die zweite Einschränkung in vielen praktischen Anwendungen eine wesentliche Herausforderung.

Funktionsweise

Der UCB-Algorithmus balanciert Exploration und Exploitation, indem er jedem geschätzten Wert einer Aktion ein Konfidenzintervall zuweist und die Aktion mit der höchsten oberen Schranke auswählt. Dieser Ansatz stellt sicher, dass Aktionen mit unsicheren Belohnungen erkundet werden, während gleichzeitig solche bevorzugt werden, die als optimal erscheinen.

Die Schritte des UCB-Algorithmus sind identisch mit denen des Epsilon-Greedy-Algorithmus, mit Ausnahme des Schrittes der Aktionsauswahl. Der UCB-Algorithmus wählt eine Aktion $A_t$ zum Zeitpunkt $t$ anhand der folgenden Formel aus:

wobei:

• $Q_t(a)$ die geschätzte Belohnung der Aktion $a$ zum Zeitpunkt $t$ ist;
• $N_t(a)$ die Anzahl der bisherigen Auswahlen der Aktion $a$ bis zum Zeitpunkt $t$ ist;
• $c > 0$ ein einstellbarer Parameter ist, der das Gleichgewicht zwischen Exploration und Exploitation steuert, ähnlich wie $\varepsilon$ im $\varepsilon$-greedy Algorithmus;
• $\ln$ die natürliche Logarithmusfunktion ist;
• $\argmax$ der Wert eines Arguments ($a$ in diesem Fall) ist, der den Ausdruck maximiert.

Intuition

$\argmax$ wählt die Aktion, die die Summe aus zwei Teilen maximiert: dem geschätzten Aktionswert und einem Konfidenzintervall. Das Konfidenzintervall wird mit einem Faktor $c$ skaliert, wobei größere Werte das Intervall verbreitern. Das bedeutet, dass der Agent weniger Vertrauen in den Wert der Aktion hat, was die Exploration fördert.

Die Größe dieses Konfidenzintervalls hängt von zwei Faktoren ab:

1. Zeit: Mit zunehmender Zeit wird der Agent weniger sicher bezüglich des Aktionswerts;
2. Aktionshäufigkeit: Je häufiger eine Aktion gewählt wird, desto sicherer wird der Agent bezüglich ihres Werts.

Beispielcode

class UpperConfidenceBoundAgent:
  def __init__(self, n_actions, confidence):
    """Initialize an agent"""
    self.n_actions = n_actions # Number of available actions
    self.confidence = confidence # c
    self.Q = np.zeros(self.n_actions) # Estimated action values
    self.N = np.zeros(self.n_actions) # Action selection counters
    self.t = 0 # Time step counter

  def select_action(self):
    """Select an action according to the upper confidence bound strategy"""
    # Increase the time step counter
    self.t += 1

    # Each action should be taken at least once
    for action in range(self.n_actions):
      if self.N[action] == 0:
        return action

    # Return the action with highest upper confidence bound
    return np.argmax(self.Q + self.confidence * np.sqrt(np.log(self.t) / self.N))

  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

Der UCB-Algorithmus beinhaltet einen Mechanismus zur Exploration, der eine sorgfältige Abstimmung des $c$-Hyperparameters erfordert, um effektiv zu funktionieren. Der optimale Wert für $c$ variiert je nach spezifischem Problem. Hier sind einige allgemeine Richtlinien:

• Hohe Varianz der Belohnungen: Ein größerer $c$-Wert gewährleistet ausreichende Exploration;
• Stabile Belohnungen: Ein kleinerer $c$-Wert ermöglicht es dem Algorithmus, sich schnell auf die optimale Aktion zu konzentrieren;
• Häufig verwendeter Standardwert: Ein typischer Ausgangspunkt ist $c = 1$, jedoch ist oft eine experimentelle Anpassung für optimale Ergebnisse erforderlich.

Zusammenfassung

Der UCB-Algorithmus ist eine leistungsstarke und fundierte Methode, um das Gleichgewicht zwischen Exploration und Exploitation in Multi-Armed-Bandit-Problemen herzustellen. Durch die Auswahl von Aktionen basierend auf geschätzten Belohnungen und Unsicherheiten ermöglicht er effizientes Lernen bei gleichzeitiger Minimierung des Bedauerns.