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 das Reinforcement Learning
course content

Kursinhalt

Einführung in das Reinforcement Learning

Einführung in das Reinforcement Learning

1. Kernprinzipien des RL
2. Multi-Armed-Bandit-Problem
3. Dynamische Programmierung
4. Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen

book
Inkrementelle Implementierungen

Das Speichern jeder 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, Schätzwerte 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), N(s,a)N(s, a).

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Für die Off-Policy-Methode mit gewöhnlichem Importance Sampling bleibt alles wie bei der On-Policy-Methode.

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 wird mit ρ\rho gewichtet;
  2. Die endgültige Summe wird nicht durch N(s,a)N(s, a), sondern durch ρ(s,a)\sum \rho(s, a) geteilt.

Der Wert von α\alpha, der in diesem Fall tatsächlich verwendet werden kann, ist gleich 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

course content

Kursinhalt

Einführung in das Reinforcement Learning

Einführung in das Reinforcement Learning

1. Kernprinzipien des RL
2. Multi-Armed-Bandit-Problem
3. Dynamische Programmierung
4. Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen

book
Inkrementelle Implementierungen

Das Speichern jeder 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, Schätzwerte 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), N(s,a)N(s, a).

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Für die Off-Policy-Methode mit gewöhnlichem Importance Sampling bleibt alles wie bei der On-Policy-Methode.

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 wird mit ρ\rho gewichtet;
  2. Die endgültige Summe wird nicht durch N(s,a)N(s, a), sondern durch ρ(s,a)\sum \rho(s, a) geteilt.

Der Wert von α\alpha, der in diesem Fall tatsächlich verwendet werden kann, ist gleich 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