Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lernen Aktionswerte | Multi-Armed-Bandit-Problem
Einführung in Reinforcement Learning

bookAktionswerte

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 zu liefern, wenn eine bestimmte Aktion ausgewählt wird. Er ist vergleichbar mit einem 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)Q(a), die erwartete Belohnung bei Auswahl der Aktion aa dar:

Q(a)=E[RA=a]\def\E{\operatorname{\mathbb{E}}} Q(a) = \E[R | A = a]

wobei:

  • RR die erhaltene Belohnung ist;
  • AA die gewählte Aktion ist.

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

Schätzung von Aktionswerten

Es gibt mehrere Methoden zur Schätzung von Q(a)Q(a) basierend auf beobachteten Belohnungen. Die gebräuchlichste Methode ist die Stichprobenmittelwert-Schätzung, bei der der durchschnittliche Ertrag berechnet wird, der durch die Auswahl der Aktion aa bis zum Zeitpunkt tt erzielt wurde:

Qt(a)=R1+R2+...+RNt(a)Nt(a)=i=1Nt(a)RiNt(a)Q_t(a) = \frac{R_1 + R_2 + ... + R_{N_t(a)}}{N_t(a)} = \frac{\sum_{i=1}^{N_t(a)} R_i}{N_t(a)}

wobei:

  • Qt(a)Q_t(a) der geschätzte Wert der Aktion aa zum Zeitpunkt tt ist;
  • Nt(a)N_t(a) die Anzahl der bisherigen Auswahlen der Aktion aa bis zum Zeitpunkt tt ist;
  • RiR_i die Belohnung ist, die in jedem Fall erhalten wurde, wenn Aktion aa gewählt wurde.

Mit zunehmender Stichprobengröße konvergiert diese Schätzung gegen die wahre erwartete Belohnung Q(a)Q_*(a), vorausgesetzt, die Belohnungsverteilung bleibt stationär.

Note
Definition

Eine stationäre Verteilung ist eine Verteilung, die sich im Zeitverlauf nicht ändert, unabhängig davon, welche Aktionen gewählt werden oder wie sich die Umgebung verändert.

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:

Qk+1=1ki=1kRi=1k(Rk+i=1k1Ri)=1k(Rk+(k1)Qk)=1k(Rk+kQkQk)=Qk+1k(RkQk)\begin{aligned} Q_{k+1} &= \frac1k \sum_{i=1}^k R_i\\ &= \frac1k (R_k + \sum_{i=1}^{k-1} R_i)\\ &= \frac1k (R_k + (k-1) Q_k)\\ &= \frac1k (R_k + k Q_k - Q_k)\\ &= Q_k + \frac1k(R_k - Q_k) \end{aligned}

wobei für eine bestimmte Aktion gilt:

  • QkQ_k ist eine Schätzung der kk-ten Belohnung, die als Durchschnitt der ersten k1k-1 Belohnungen ausgedrückt werden kann;
  • RkR_k ist die tatsächliche kk-te Belohnung.

Intuition

Kennt man die Schätzung der kk-ten Belohnung, QkQ_k, und die tatsächliche kk-te Belohnung, RkR_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:

Qk+1=Qk+α(RkQk)Q_{k+1} = Q_k + \alpha (R_k - Q_k)

wobei α\alpha ein Schrittweitenparameter ist, der die Lernrate steuert. Wie in der vorherigen Formel kann Alpha 1k\frac1k sein, was zu einer Schätzung des Stichprobenmittels 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 erheblich variieren, was zu einer vorzeitigen 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 mindern und eine 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. Q0(a)=1Q_0(a) = 1 statt 0). Dieser Ansatz vermittelt den Eindruck, dass alle Aktionen anfangs vielversprechend sind. Dadurch wird der Agent dazu angeregt, jede Aktion mehrfach zu erkunden, bevor er sich für die beste Option entscheidet. Diese Technik ist am effizientesten, wenn sie mit einer konstanten Schrittweite kombiniert wird.

Note
Hinweis

Die Rate optimaler Aktionen in diesem und zukünftigen Diagrammen bezieht sich auf den Anteil der Umgebungen, in denen die optimale Aktion zu einem bestimmten Zeitschritt gewählt wurde.

Beispielsweise, wenn es 10 Testumgebungen gibt und in 6 davon die optimale Aktion zum Zeitschritt 200 ausgewählt wurde, beträgt die Rate optimaler Aktionen für diesen Zeitschritt 0,6. Diese Kennzahl ist nützlich zur Leistungsbewertung, da sie mit der Maximierung der Belohnung korreliert, ohne von den genauen Belohnungswerten abhängig zu sein.

question mark

Wofür wird der Stichprobenmittelwert bei der Schätzung von Aktionswerten verwendet?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 2

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Awesome!

Completion rate improved to 2.7

bookAktionswerte

Swipe um das Menü anzuzeigen

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 zu liefern, wenn eine bestimmte Aktion ausgewählt wird. Er ist vergleichbar mit einem 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)Q(a), die erwartete Belohnung bei Auswahl der Aktion aa dar:

Q(a)=E[RA=a]\def\E{\operatorname{\mathbb{E}}} Q(a) = \E[R | A = a]

wobei:

  • RR die erhaltene Belohnung ist;
  • AA die gewählte Aktion ist.

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

Schätzung von Aktionswerten

Es gibt mehrere Methoden zur Schätzung von Q(a)Q(a) basierend auf beobachteten Belohnungen. Die gebräuchlichste Methode ist die Stichprobenmittelwert-Schätzung, bei der der durchschnittliche Ertrag berechnet wird, der durch die Auswahl der Aktion aa bis zum Zeitpunkt tt erzielt wurde:

Qt(a)=R1+R2+...+RNt(a)Nt(a)=i=1Nt(a)RiNt(a)Q_t(a) = \frac{R_1 + R_2 + ... + R_{N_t(a)}}{N_t(a)} = \frac{\sum_{i=1}^{N_t(a)} R_i}{N_t(a)}

wobei:

  • Qt(a)Q_t(a) der geschätzte Wert der Aktion aa zum Zeitpunkt tt ist;
  • Nt(a)N_t(a) die Anzahl der bisherigen Auswahlen der Aktion aa bis zum Zeitpunkt tt ist;
  • RiR_i die Belohnung ist, die in jedem Fall erhalten wurde, wenn Aktion aa gewählt wurde.

Mit zunehmender Stichprobengröße konvergiert diese Schätzung gegen die wahre erwartete Belohnung Q(a)Q_*(a), vorausgesetzt, die Belohnungsverteilung bleibt stationär.

Note
Definition

Eine stationäre Verteilung ist eine Verteilung, die sich im Zeitverlauf nicht ändert, unabhängig davon, welche Aktionen gewählt werden oder wie sich die Umgebung verändert.

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:

Qk+1=1ki=1kRi=1k(Rk+i=1k1Ri)=1k(Rk+(k1)Qk)=1k(Rk+kQkQk)=Qk+1k(RkQk)\begin{aligned} Q_{k+1} &= \frac1k \sum_{i=1}^k R_i\\ &= \frac1k (R_k + \sum_{i=1}^{k-1} R_i)\\ &= \frac1k (R_k + (k-1) Q_k)\\ &= \frac1k (R_k + k Q_k - Q_k)\\ &= Q_k + \frac1k(R_k - Q_k) \end{aligned}

wobei für eine bestimmte Aktion gilt:

  • QkQ_k ist eine Schätzung der kk-ten Belohnung, die als Durchschnitt der ersten k1k-1 Belohnungen ausgedrückt werden kann;
  • RkR_k ist die tatsächliche kk-te Belohnung.

Intuition

Kennt man die Schätzung der kk-ten Belohnung, QkQ_k, und die tatsächliche kk-te Belohnung, RkR_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:

Qk+1=Qk+α(RkQk)Q_{k+1} = Q_k + \alpha (R_k - Q_k)

wobei α\alpha ein Schrittweitenparameter ist, der die Lernrate steuert. Wie in der vorherigen Formel kann Alpha 1k\frac1k sein, was zu einer Schätzung des Stichprobenmittels 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 erheblich variieren, was zu einer vorzeitigen 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 mindern und eine 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. Q0(a)=1Q_0(a) = 1 statt 0). Dieser Ansatz vermittelt den Eindruck, dass alle Aktionen anfangs vielversprechend sind. Dadurch wird der Agent dazu angeregt, jede Aktion mehrfach zu erkunden, bevor er sich für die beste Option entscheidet. Diese Technik ist am effizientesten, wenn sie mit einer konstanten Schrittweite kombiniert wird.

Note
Hinweis

Die Rate optimaler Aktionen in diesem und zukünftigen Diagrammen bezieht sich auf den Anteil der Umgebungen, in denen die optimale Aktion zu einem bestimmten Zeitschritt gewählt wurde.

Beispielsweise, wenn es 10 Testumgebungen gibt und in 6 davon die optimale Aktion zum Zeitschritt 200 ausgewählt wurde, beträgt die Rate optimaler Aktionen für diesen Zeitschritt 0,6. Diese Kennzahl ist nützlich zur Leistungsbewertung, da sie mit der Maximierung der Belohnung korreliert, ohne von den genauen Belohnungswerten abhängig zu sein.

question mark

Wofür wird der Stichprobenmittelwert bei der Schätzung von Aktionswerten verwendet?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 2
some-alt