Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lernen Inkrementelle Implementierungen | Monte-Carlo-Methoden
Einführung in Reinforcement Learning

bookInkrementelle Implementierungen

Das Speichern jeder einzelnen Rückgabe für jedes Zustand-Aktions-Paar kann den Speicher schnell erschöpfen und die Rechenzeit erheblich erhöhen – insbesondere in großen Umgebungen. Diese Einschränkung betrifft sowohl On-Policy- als auch Off-Policy-Monte-Carlo-Kontrollalgorithmen. Um dem entgegenzuwirken, werden inkrementelle Berechnungsstrategien verwendet, ähnlich wie bei Multi-Armed-Bandit-Algorithmen. Diese Methoden ermöglichen es, Wertschätzungen dynamisch zu aktualisieren, ohne vollständige Rückgabeverläufe zu speichern.

On-Policy-Monte-Carlo-Kontrolle

Für die On-Policy-Methode ähnelt die Aktualisierungsstrategie der Strategie, die in MAB-Algorithmen verwendet wird:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

wobei α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} für die Mittelwertschätzung gilt. Die einzigen Werte, die gespeichert werden müssen, sind die aktuellen Schätzungen der Aktionswerte Q(s,a)Q(s, a) und die Anzahl der Besuche des Zustand-Aktions-Paares (s,a)(s, a), also N(s,a)N(s, a).

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Für das Off-Policy-Verfahren mit gewöhnlichem Importance Sampling bleibt alles wie beim On-Policy-Verfahren.

Eine interessantere Situation ergibt sich beim gewichteten Importance Sampling. Die Gleichung sieht gleich aus:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

aber α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kann nicht verwendet werden, weil:

  1. Jede Rückgabe mit ρ\rho gewichtet wird;
  2. Die endgültige Summe nicht durch N(s,a)N(s, a), sondern durch ρ(s,a)\sum \rho(s, a) geteilt wird.

Der Wert von α\alpha, der in diesem Fall tatsächlich verwendet werden kann, entspricht WC(s,a)\displaystyle \frac{W}{C(s,a)}, wobei:

  • WW das ρ\rho für die aktuelle Trajektorie ist;
  • C(s,a)C(s, a) gleich ρ(s,a)\sum \rho(s, a) ist.

Und jedes Mal, wenn das Zustand-Aktions-Paar (s,a)(s, a) auftritt, wird das ρ\rho der aktuellen Trajektorie zu C(s,a)C(s, a) addiert:

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocode

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 7

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

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

Suggested prompts:

Can you explain the difference between on-policy and off-policy Monte Carlo control?

How does incremental computation improve efficiency in Monte Carlo methods?

Can you clarify how the weighted importance sampling update works?

Awesome!

Completion rate improved to 2.7

bookInkrementelle Implementierungen

Swipe um das Menü anzuzeigen

Das Speichern jeder einzelnen Rückgabe für jedes Zustand-Aktions-Paar kann den Speicher schnell erschöpfen und die Rechenzeit erheblich erhöhen – insbesondere in großen Umgebungen. Diese Einschränkung betrifft sowohl On-Policy- als auch Off-Policy-Monte-Carlo-Kontrollalgorithmen. Um dem entgegenzuwirken, werden inkrementelle Berechnungsstrategien verwendet, ähnlich wie bei Multi-Armed-Bandit-Algorithmen. Diese Methoden ermöglichen es, Wertschätzungen dynamisch zu aktualisieren, ohne vollständige Rückgabeverläufe zu speichern.

On-Policy-Monte-Carlo-Kontrolle

Für die On-Policy-Methode ähnelt die Aktualisierungsstrategie der Strategie, die in MAB-Algorithmen verwendet wird:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

wobei α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} für die Mittelwertschätzung gilt. Die einzigen Werte, die gespeichert werden müssen, sind die aktuellen Schätzungen der Aktionswerte Q(s,a)Q(s, a) und die Anzahl der Besuche des Zustand-Aktions-Paares (s,a)(s, a), also N(s,a)N(s, a).

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Für das Off-Policy-Verfahren mit gewöhnlichem Importance Sampling bleibt alles wie beim On-Policy-Verfahren.

Eine interessantere Situation ergibt sich beim gewichteten Importance Sampling. Die Gleichung sieht gleich aus:

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

aber α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kann nicht verwendet werden, weil:

  1. Jede Rückgabe mit ρ\rho gewichtet wird;
  2. Die endgültige Summe nicht durch N(s,a)N(s, a), sondern durch ρ(s,a)\sum \rho(s, a) geteilt wird.

Der Wert von α\alpha, der in diesem Fall tatsächlich verwendet werden kann, entspricht WC(s,a)\displaystyle \frac{W}{C(s,a)}, wobei:

  • WW das ρ\rho für die aktuelle Trajektorie ist;
  • C(s,a)C(s, a) gleich ρ(s,a)\sum \rho(s, a) ist.

Und jedes Mal, wenn das Zustand-Aktions-Paar (s,a)(s, a) auftritt, wird das ρ\rho der aktuellen Trajektorie zu C(s,a)C(s, a) addiert:

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocode

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 7
some-alt