Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lernen Was Sind Monte-Carlo-Methoden? | 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
Was Sind Monte-Carlo-Methoden?

Note
Definition

Monte-Carlo-Methoden (MC) sind eine Klasse von rechnergestützten Algorithmen, die auf zufälliger Stichprobenziehung basieren, um numerische Ergebnisse zu schätzen.

Monte-Carlo-Methoden werden eingesetzt, wenn deterministische Lösungen schwierig oder unmöglich zu erhalten sind. Sie ersetzen exakte Berechnungen durch Approximationen, die sich mit der Anzahl der Zufallsstichproben verbessern.

Funktionsweise

Monte-Carlo-Methoden können je nach Aufgabe variieren, folgen jedoch alle einem einheitlichen Muster:

  1. Definition eines Bereichs möglicher Eingaben;
  2. Generierung zufälliger Eingaben aus einer Wahrscheinlichkeitsverteilung;
  3. Auswertung einer Funktion auf diesen Eingaben;
  4. Aggregation der Ergebnisse zur Erstellung einer Schätzung.

Beispiele

Auch wenn das oben beschriebene Muster komplex erscheinen mag, sollten diese Beispiele die dahinterstehende Idee verdeutlichen.

Integralberechnung

Die Berechnung von Integralen ist eine anspruchsvolle Aufgabe, die in der Regel den Einsatz verschiedener Techniken erfordert, um das korrekte Ergebnis zu erzielen.

Versuch der Anwendung der Monte-Carlo-Methode zur Lösung dieses Integrals:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Eingabebereich: Dieses Doppelintegral besitzt zwei Variablen, x[0,1]x \in [0, 1] und y[0,1]y \in [0, 1];
  2. Generierung: Beide Variablen sind unabhängig voneinander und gleichverteilt;
  3. Auswertung: Zur Bestimmung eines Punktwertes kann die Funktion unter dem Integral verwendet werden;
  4. Aggregation: Der Wert dieses Integrals kann als Volumen unter der Kurve definiert werden. Das Volumen ergibt sich als Produkt aus Grundfläche und mittlerer Höhe. Die Grundfläche beträgt 1 (Einheitsquadrat) und die mittlere Höhe ist der Durchschnitt der in Schritt 3 erhaltenen Ergebnisse.
12345678910111213141516
import numpy as np result = 0 # Many samples are required for estimates to be precise for i in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Computation of point value value = 1 / (1 + (x + y) ** 2) # Mean aggregation result += (value - result) / (i + 1) # Closed-form solution of this integral true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2) print(f"Approximated result: {result}") print(f"True result: {true_result}")
copy

Approximation von π\Large\pi

Die Approximation von π\pi ist eine der bekanntesten Anwendungen der Monte-Carlo-Methode. Sie zeigt, wie zufällige Stichproben ein geometrisches Problem lösen können, ohne komplexe Analysis zu verwenden.

Betrachte ein Einheitsquadrat mit einem eingeschriebenen Viertelkreis:

  • Das Quadrat erstreckt sich über [0,1]×[0,1][0, 1] \times [0, 1];
  • Der Viertelkreis hat den Radius 1 und ist im Ursprung zentriert.

Die Fläche des Viertelkreises beträgt πr24\displaystyle\frac{\pi r^2}{4} bzw. π4\displaystyle\frac{\pi}{4}, und die Fläche des Quadrats ist 1. Nun werden zufällige Punkte innerhalb des Quadrats gezogen. Bei ausreichend großer Stichprobe gilt:

Punkte im ViertelkreisGesamtanzahl der Punkteπ4\frac{\text{Punkte im Viertelkreis}}{\text{Gesamtanzahl der Punkte}} \approx \frac\pi4

Daraus ergibt sich für den Wert von π\pi:

π4Punkte im ViertelkreisGesamtanzahl der Punkte\pi \approx 4 \cdot \frac{\text{Punkte im Viertelkreis}}{\text{Gesamtanzahl der Punkte}}
1234567891011121314151617181920212223242526272829
import numpy as np import matplotlib.pyplot as plt # Lists for coordinates inside = [] outside = [] # Many samples are required for estimates to be precise for _ in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Splitting points inside and outside of the circle if x**2 + y**2 <= 1: inside.append((x, y)) else: outside.append((x, y)) # Plotting points plt.figure(figsize=(6,6)) plt.scatter(*zip(*inside), color="blue", s=1, label="Inside") plt.scatter(*zip(*outside), color="red", s=1, label="Outside") plt.legend() plt.xlabel("x") plt.ylabel("y") plt.show() estimate = 4 * len(inside) / (len(inside) + len(outside)) print(f"Estimated value of pi: {estimate}") print(f"True value of pi: {np.pi}")
copy

Multi-Armed Bandits

Im Multi-Armed-Bandit-Problem besteht ein zentrales Ziel darin, den Aktionswert für jeden Arm zu schätzen – also die erwartete Belohnung bei Auswahl einer bestimmten Aktion. Eine gängige Strategie ist es, diese Werte durch das Mittel der beobachteten Belohnungen zu schätzen, die im Laufe der Zeit durch Ziehen jedes Arms erhalten wurden. Diese Technik ist tatsächlich eine Monte-Carlo-Methode.

Monte-Carlo-Methoden für MDPs

Im Gegensatz zu dynamischen Programmiermethoden, die auf ein vollständiges und genaues Modell der Umgebungsdynamik angewiesen sind, lernen Monte-Carlo-Methoden ausschließlich aus Erfahrungen – das heißt, aus tatsächlichen oder simulierten Sequenzen von Zuständen, Aktionen und Belohnungen.

Dies macht Monte-Carlo-Ansätze besonders leistungsfähig: Sie benötigen keinerlei Vorwissen darüber, wie die Umgebung funktioniert. Stattdessen gewinnen sie Wertschätzungen direkt aus den während der Interaktion gesammelten Erfahrungen. In vielen realen Szenarien, in denen die Modellierung der Umgebung unpraktisch oder unmöglich ist, stellt diese Fähigkeit, aus rohen Erfahrungen zu lernen, einen entscheidenden Vorteil dar.

Wenn die direkte Interaktion mit der Umgebung kostspielig, riskant oder langsam ist, können Monte-Carlo-Methoden auch aus simulierten Erfahrungen lernen, sofern eine zuverlässige Simulation existiert. Dies ermöglicht Erkundung und Lernen in einer kontrollierten, wiederholbaren Umgebung – vorausgesetzt, es steht ein Modell zur Verfügung, das plausible Übergänge erzeugen kann.

question mark

Was ist ein wesentlicher Vorteil der Verwendung von Monte-Carlo-Methoden gegenüber dynamischen Programmiermethoden bei der Lösung von MDPs?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 1

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
Was Sind Monte-Carlo-Methoden?

Note
Definition

Monte-Carlo-Methoden (MC) sind eine Klasse von rechnergestützten Algorithmen, die auf zufälliger Stichprobenziehung basieren, um numerische Ergebnisse zu schätzen.

Monte-Carlo-Methoden werden eingesetzt, wenn deterministische Lösungen schwierig oder unmöglich zu erhalten sind. Sie ersetzen exakte Berechnungen durch Approximationen, die sich mit der Anzahl der Zufallsstichproben verbessern.

Funktionsweise

Monte-Carlo-Methoden können je nach Aufgabe variieren, folgen jedoch alle einem einheitlichen Muster:

  1. Definition eines Bereichs möglicher Eingaben;
  2. Generierung zufälliger Eingaben aus einer Wahrscheinlichkeitsverteilung;
  3. Auswertung einer Funktion auf diesen Eingaben;
  4. Aggregation der Ergebnisse zur Erstellung einer Schätzung.

Beispiele

Auch wenn das oben beschriebene Muster komplex erscheinen mag, sollten diese Beispiele die dahinterstehende Idee verdeutlichen.

Integralberechnung

Die Berechnung von Integralen ist eine anspruchsvolle Aufgabe, die in der Regel den Einsatz verschiedener Techniken erfordert, um das korrekte Ergebnis zu erzielen.

Versuch der Anwendung der Monte-Carlo-Methode zur Lösung dieses Integrals:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Eingabebereich: Dieses Doppelintegral besitzt zwei Variablen, x[0,1]x \in [0, 1] und y[0,1]y \in [0, 1];
  2. Generierung: Beide Variablen sind unabhängig voneinander und gleichverteilt;
  3. Auswertung: Zur Bestimmung eines Punktwertes kann die Funktion unter dem Integral verwendet werden;
  4. Aggregation: Der Wert dieses Integrals kann als Volumen unter der Kurve definiert werden. Das Volumen ergibt sich als Produkt aus Grundfläche und mittlerer Höhe. Die Grundfläche beträgt 1 (Einheitsquadrat) und die mittlere Höhe ist der Durchschnitt der in Schritt 3 erhaltenen Ergebnisse.
12345678910111213141516
import numpy as np result = 0 # Many samples are required for estimates to be precise for i in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Computation of point value value = 1 / (1 + (x + y) ** 2) # Mean aggregation result += (value - result) / (i + 1) # Closed-form solution of this integral true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2) print(f"Approximated result: {result}") print(f"True result: {true_result}")
copy

Approximation von π\Large\pi

Die Approximation von π\pi ist eine der bekanntesten Anwendungen der Monte-Carlo-Methode. Sie zeigt, wie zufällige Stichproben ein geometrisches Problem lösen können, ohne komplexe Analysis zu verwenden.

Betrachte ein Einheitsquadrat mit einem eingeschriebenen Viertelkreis:

  • Das Quadrat erstreckt sich über [0,1]×[0,1][0, 1] \times [0, 1];
  • Der Viertelkreis hat den Radius 1 und ist im Ursprung zentriert.

Die Fläche des Viertelkreises beträgt πr24\displaystyle\frac{\pi r^2}{4} bzw. π4\displaystyle\frac{\pi}{4}, und die Fläche des Quadrats ist 1. Nun werden zufällige Punkte innerhalb des Quadrats gezogen. Bei ausreichend großer Stichprobe gilt:

Punkte im ViertelkreisGesamtanzahl der Punkteπ4\frac{\text{Punkte im Viertelkreis}}{\text{Gesamtanzahl der Punkte}} \approx \frac\pi4

Daraus ergibt sich für den Wert von π\pi:

π4Punkte im ViertelkreisGesamtanzahl der Punkte\pi \approx 4 \cdot \frac{\text{Punkte im Viertelkreis}}{\text{Gesamtanzahl der Punkte}}
1234567891011121314151617181920212223242526272829
import numpy as np import matplotlib.pyplot as plt # Lists for coordinates inside = [] outside = [] # Many samples are required for estimates to be precise for _ in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Splitting points inside and outside of the circle if x**2 + y**2 <= 1: inside.append((x, y)) else: outside.append((x, y)) # Plotting points plt.figure(figsize=(6,6)) plt.scatter(*zip(*inside), color="blue", s=1, label="Inside") plt.scatter(*zip(*outside), color="red", s=1, label="Outside") plt.legend() plt.xlabel("x") plt.ylabel("y") plt.show() estimate = 4 * len(inside) / (len(inside) + len(outside)) print(f"Estimated value of pi: {estimate}") print(f"True value of pi: {np.pi}")
copy

Multi-Armed Bandits

Im Multi-Armed-Bandit-Problem besteht ein zentrales Ziel darin, den Aktionswert für jeden Arm zu schätzen – also die erwartete Belohnung bei Auswahl einer bestimmten Aktion. Eine gängige Strategie ist es, diese Werte durch das Mittel der beobachteten Belohnungen zu schätzen, die im Laufe der Zeit durch Ziehen jedes Arms erhalten wurden. Diese Technik ist tatsächlich eine Monte-Carlo-Methode.

Monte-Carlo-Methoden für MDPs

Im Gegensatz zu dynamischen Programmiermethoden, die auf ein vollständiges und genaues Modell der Umgebungsdynamik angewiesen sind, lernen Monte-Carlo-Methoden ausschließlich aus Erfahrungen – das heißt, aus tatsächlichen oder simulierten Sequenzen von Zuständen, Aktionen und Belohnungen.

Dies macht Monte-Carlo-Ansätze besonders leistungsfähig: Sie benötigen keinerlei Vorwissen darüber, wie die Umgebung funktioniert. Stattdessen gewinnen sie Wertschätzungen direkt aus den während der Interaktion gesammelten Erfahrungen. In vielen realen Szenarien, in denen die Modellierung der Umgebung unpraktisch oder unmöglich ist, stellt diese Fähigkeit, aus rohen Erfahrungen zu lernen, einen entscheidenden Vorteil dar.

Wenn die direkte Interaktion mit der Umgebung kostspielig, riskant oder langsam ist, können Monte-Carlo-Methoden auch aus simulierten Erfahrungen lernen, sofern eine zuverlässige Simulation existiert. Dies ermöglicht Erkundung und Lernen in einer kontrollierten, wiederholbaren Umgebung – vorausgesetzt, es steht ein Modell zur Verfügung, das plausible Übergänge erzeugen kann.

question mark

Was ist ein wesentlicher Vorteil der Verwendung von Monte-Carlo-Methoden gegenüber dynamischen Programmiermethoden bei der Lösung von MDPs?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 4. Kapitel 1
some-alt