Aktionswerte

Aktionswert ist ein grundlegendes Konzept im MAB-Problem. Er spielt eine entscheidende Rolle in verschiedenen Algorithmen, einschließlich Epsilon-Greedy und Upper Confidence Bound. Der Hauptzweck eines Aktionswerts besteht darin, eine Schätzung der erwarteten Belohnung bereitzustellen, wenn eine bestimmte Aktion gewählt wird. Er ist ähnlich wie ein Zustand-Aktion-Wert, ist jedoch aufgrund der zustandslosen Natur des MAB-Problems unabhängig von einem Zustand.

Definition des Aktionswerts

Formal stellt der Aktionswert, bezeichnet als $Q(a)$, die erwartete Belohnung bei Auswahl der Aktion $a$ dar:

wobei:

• $R$ die erhaltene Belohnung ist;
• $A$ die gewählte Aktion ist.

Da die wahre Belohnungsverteilung in der Regel unbekannt ist, muss $Q(a)$ anhand beobachteter Daten geschätzt werden.

Schätzung von Aktionswerten

Es gibt mehrere Möglichkeiten, $Q(a)$ basierend auf beobachteten Belohnungen zu schätzen. Die gebräuchlichste Methode ist die Stichprobenmittelwert-Schätzung, bei der der durchschnittliche Ertrag berechnet wird, der durch die Auswahl der Aktion $a$ bis zum Zeitpunkt $t$ erzielt wurde:

wobei:

• $Q_t(a)$ der geschätzte Wert der Aktion $a$ zum Zeitpunkt $t$ ist;
• $N_t(a)$ die Anzahl der bisherigen Auswahlvorgänge von Aktion $a$ bis zum Zeitpunkt $t$ ist;
• $R_i$ die Belohnung ist, die in jedem Fall erzielt wurde, wenn Aktion $a$ gewählt wurde.

Mit zunehmender Stichprobengröße nähert sich diese Schätzung dem wahren erwarteten Ertrag $Q_*(a)$ an, vorausgesetzt, die Belohnungsverteilung bleibt stationär.

Inkrementelle Aktualisierungsregel

Obwohl die obige Formel zur Schätzung von Aktionswerten verwendet werden kann, erfordert sie das Speichern aller bisherigen Belohnungen und das erneute Berechnen ihrer Summe bei jedem Zeitschritt. Mit inkrementellen Aktualisierungen wird dies überflüssig. Die Formel für inkrementelle Aktualisierungen kann wie folgt hergeleitet werden:

wobei für eine Aktion gilt:

• $Q_k$ ist eine Schätzung der $k$-ten Belohnung, die als Durchschnitt der ersten $k-1$ Belohnungen ausgedrückt werden kann;
• $R_k$ ist die tatsächliche $k$-te Belohnung.

Intuition

Kennt man die Schätzung der $k$-ten Belohnung, $Q_k$, und die tatsächliche $k$-te Belohnung, $R_k$, kann der Fehler als Differenz zwischen diesen Werten gemessen werden. Anschließend kann die nächste Schätzung berechnet werden, indem die vorherige Schätzung leicht in Richtung der tatsächlichen Belohnung angepasst wird, um den Fehler zu verringern.

Diese Intuition führt zu einer weiteren Formel, die wie folgt aussieht:

wobei $\alpha$ ein Schrittweitenparameter ist, der die Lernrate steuert. Wie in der vorherigen Formel kann Alpha $\frac1k$ sein, was zu einer Stichprobenmittelwertschätzung führt. Alternativ wird häufig ein konstanter Wert für $\alpha$ verwendet, da hierfür kein zusätzlicher Speicherplatz (um zu speichern, wie oft eine Aktion ausgeführt wurde) erforderlich ist und eine Anpassung an nicht-stationäre Umgebungen ermöglicht wird, indem neueren Beobachtungen mehr Gewicht beigemessen wird.

Optimistische Initialisierung

Zu Beginn eines Trainingsprozesses können die Schätzungen der Aktionswerte stark variieren, was zu vorzeitiger Ausnutzung führen kann. Das bedeutet, dass der Agent sein anfängliches Wissen zu früh ausnutzt und auf Grundlage von begrenzter Erfahrung suboptimale Aktionen bevorzugt. Um dieses Problem zu verringern und anfängliche Erkundung zu fördern, ist die optimistische Initialisierung eine einfache und effektive Technik.

Bei der optimistischen Initialisierung werden die Aktionswerte auf relativ hohe Werte gesetzt (z. B. $Q_0(a) = 1$ statt 0). Dadurch entsteht der Eindruck, dass alle Aktionen anfangs vielversprechend sind. Infolgedessen wird der Agent dazu angeregt, jede Aktion mehrfach zu erkunden, bevor er sich für die beste Option entscheidet. Diese Technik ist am effizientesten in Kombination mit einer konstanten Schrittweite.