Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Leer Wat Zijn Monte Carlo-Methoden? | Monte Carlo-Methoden
Introductie tot Reinforcement Learning
course content

Cursusinhoud

Introductie tot Reinforcement Learning

Introductie tot Reinforcement Learning

1. Kernprincipes van RL
2. Multi-Armed Bandit Probleem
3. Dynamisch Programmeren
4. Monte Carlo-Methoden
5. Temporale Verschil Leren

book
Wat Zijn Monte Carlo-Methoden?

Note
Definitie

Monte Carlo (MC)-methoden zijn een klasse van computationele algoritmen die gebruikmaken van willekeurige steekproeven om numerieke resultaten te schatten.

Monte Carlo-methoden worden toegepast wanneer deterministische oplossingen moeilijk of onmogelijk te verkrijgen zijn. Ze vervangen exacte berekeningen door benaderingen die verbeteren naarmate het aantal willekeurige steekproeven toeneemt.

Werking

Monte Carlo-methoden kunnen verschillen per taak, maar ze volgen allemaal een vast patroon:

  1. Definieer een domein van mogelijke invoerwaarden;
  2. Genereer willekeurige invoerwaarden uit een kansverdeling;
  3. Evalueer een functie op deze invoerwaarden;
  4. Aggregatie van de resultaten om een schatting te produceren.

Voorbeelden

Hoewel het hierboven beschreven patroon complex kan lijken, zullen deze voorbeelden het onderliggende idee verduidelijken.

Integratieberekening

Het berekenen van integralen is een niet-triviale taak die doorgaans het toepassen van verschillende technieken vereist om het juiste resultaat te verkrijgen.

Laten we proberen de Monte Carlo-methode toe te passen om deze integraal op te lossen:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Invoerdomein: deze dubbele integraal heeft twee variabelen, x[0,1]x \in [0, 1] en y[0,1]y \in [0, 1];
  2. Generatie: beide variabelen zijn onafhankelijk van elkaar en uniform verdeeld;
  3. Evaluatie: om een puntwaarde te verkrijgen, kan de functie onder het integraalteken worden gebruikt;
  4. Aggregatie: de waarde van deze integraal kan worden gedefinieerd als het volume onder de kromme. Het volume kan worden berekend als het product van het grondvlak en de gemiddelde hoogte. Het grondvlak is 1 (eenheidvierkant) en de gemiddelde hoogte is het gemiddelde van de resultaten uit de vorige stap.
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

Benadering van π\Large\pi

Het benaderen van π\pi is een van de meest iconische toepassingen van de Monte Carlo-methode. Dit illustreert hoe willekeurige steekproeven een meetkundig probleem kunnen oplossen zonder complexe calculus.

Beschouw een eenheidscarré met daarin een kwartcirkel:

  • Het vierkant beslaat [0,1]×[0,1][0, 1] \times [0, 1];
  • De kwartcirkel heeft straal 1 en is gecentreerd in de oorsprong.

De oppervlakte van de kwartcirkel is πr24\displaystyle\frac{\pi r^2}{4} ofwel π4\displaystyle\frac{\pi}{4}, en de oppervlakte van het vierkant is 1. Stel nu dat we willekeurige punten binnen het vierkant nemen. Met een voldoende grote steekproefgrootte geldt:

Punten binnen de kwartcirkelTotaal aantal puntenπ4\frac{\text{Punten binnen de kwartcirkel}}{\text{Totaal aantal punten}} \approx \frac\pi4

Dus de waarde van π\pi kan worden berekend als

π4Punten binnenTotaal aantal punten\pi \approx 4 \cdot \frac{\text{Punten binnen}}{\text{Totaal aantal punten}}
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

In de multi-armed bandit-context is een belangrijk doel het schatten van de actie-waarde voor elke arm — dat wil zeggen, de verwachte beloning bij het kiezen van een bepaalde actie. Een veelgebruikte strategie is het schatten van deze waarden door het gemiddelde te nemen van de waargenomen beloningen die in de loop van de tijd zijn verkregen door aan elke arm te trekken. Deze techniek is in feite een Monte Carlo-methode.

Monte Carlo-methoden voor MDP's

In tegenstelling tot dynamische programmeermethoden, die afhankelijk zijn van een volledig en nauwkeurig model van de dynamiek van de omgeving, leren Monte Carlo-methoden uitsluitend uit ervaring — dat wil zeggen, uit daadwerkelijke of gesimuleerde reeksen van toestanden, acties en beloningen.

Dit maakt Monte Carlo-benaderingen bijzonder krachtig: ze vereisen geen enkele voorkennis over hoe de omgeving werkt. In plaats daarvan halen ze waarde-inschattingen direct uit wat er gebeurt tijdens de interactie. In veel praktijksituaties, waarin het modelleren van de omgeving onpraktisch of onmogelijk is, is dit vermogen om te leren uit ruwe ervaring een groot voordeel.

Wanneer directe interactie met de omgeving kostbaar, riskant of traag is, kunnen Monte Carlo-methoden ook leren uit gesimuleerde ervaring, mits er een betrouwbare simulatie beschikbaar is. Dit maakt verkenning en leren mogelijk in een gecontroleerde, herhaalbare omgeving — hoewel dit wel veronderstelt dat er toegang is tot een model dat geloofwaardige overgangen kan genereren.

question mark

Wat is een belangrijk voordeel van het gebruik van Monte Carlo-methoden ten opzichte van dynamische programmeermethoden bij het oplossen van MDP's?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 1

Vraag AI

expand

Vraag AI

ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

course content

Cursusinhoud

Introductie tot Reinforcement Learning

Introductie tot Reinforcement Learning

1. Kernprincipes van RL
2. Multi-Armed Bandit Probleem
3. Dynamisch Programmeren
4. Monte Carlo-Methoden
5. Temporale Verschil Leren

book
Wat Zijn Monte Carlo-Methoden?

Note
Definitie

Monte Carlo (MC)-methoden zijn een klasse van computationele algoritmen die gebruikmaken van willekeurige steekproeven om numerieke resultaten te schatten.

Monte Carlo-methoden worden toegepast wanneer deterministische oplossingen moeilijk of onmogelijk te verkrijgen zijn. Ze vervangen exacte berekeningen door benaderingen die verbeteren naarmate het aantal willekeurige steekproeven toeneemt.

Werking

Monte Carlo-methoden kunnen verschillen per taak, maar ze volgen allemaal een vast patroon:

  1. Definieer een domein van mogelijke invoerwaarden;
  2. Genereer willekeurige invoerwaarden uit een kansverdeling;
  3. Evalueer een functie op deze invoerwaarden;
  4. Aggregatie van de resultaten om een schatting te produceren.

Voorbeelden

Hoewel het hierboven beschreven patroon complex kan lijken, zullen deze voorbeelden het onderliggende idee verduidelijken.

Integratieberekening

Het berekenen van integralen is een niet-triviale taak die doorgaans het toepassen van verschillende technieken vereist om het juiste resultaat te verkrijgen.

Laten we proberen de Monte Carlo-methode toe te passen om deze integraal op te lossen:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Invoerdomein: deze dubbele integraal heeft twee variabelen, x[0,1]x \in [0, 1] en y[0,1]y \in [0, 1];
  2. Generatie: beide variabelen zijn onafhankelijk van elkaar en uniform verdeeld;
  3. Evaluatie: om een puntwaarde te verkrijgen, kan de functie onder het integraalteken worden gebruikt;
  4. Aggregatie: de waarde van deze integraal kan worden gedefinieerd als het volume onder de kromme. Het volume kan worden berekend als het product van het grondvlak en de gemiddelde hoogte. Het grondvlak is 1 (eenheidvierkant) en de gemiddelde hoogte is het gemiddelde van de resultaten uit de vorige stap.
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

Benadering van π\Large\pi

Het benaderen van π\pi is een van de meest iconische toepassingen van de Monte Carlo-methode. Dit illustreert hoe willekeurige steekproeven een meetkundig probleem kunnen oplossen zonder complexe calculus.

Beschouw een eenheidscarré met daarin een kwartcirkel:

  • Het vierkant beslaat [0,1]×[0,1][0, 1] \times [0, 1];
  • De kwartcirkel heeft straal 1 en is gecentreerd in de oorsprong.

De oppervlakte van de kwartcirkel is πr24\displaystyle\frac{\pi r^2}{4} ofwel π4\displaystyle\frac{\pi}{4}, en de oppervlakte van het vierkant is 1. Stel nu dat we willekeurige punten binnen het vierkant nemen. Met een voldoende grote steekproefgrootte geldt:

Punten binnen de kwartcirkelTotaal aantal puntenπ4\frac{\text{Punten binnen de kwartcirkel}}{\text{Totaal aantal punten}} \approx \frac\pi4

Dus de waarde van π\pi kan worden berekend als

π4Punten binnenTotaal aantal punten\pi \approx 4 \cdot \frac{\text{Punten binnen}}{\text{Totaal aantal punten}}
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

In de multi-armed bandit-context is een belangrijk doel het schatten van de actie-waarde voor elke arm — dat wil zeggen, de verwachte beloning bij het kiezen van een bepaalde actie. Een veelgebruikte strategie is het schatten van deze waarden door het gemiddelde te nemen van de waargenomen beloningen die in de loop van de tijd zijn verkregen door aan elke arm te trekken. Deze techniek is in feite een Monte Carlo-methode.

Monte Carlo-methoden voor MDP's

In tegenstelling tot dynamische programmeermethoden, die afhankelijk zijn van een volledig en nauwkeurig model van de dynamiek van de omgeving, leren Monte Carlo-methoden uitsluitend uit ervaring — dat wil zeggen, uit daadwerkelijke of gesimuleerde reeksen van toestanden, acties en beloningen.

Dit maakt Monte Carlo-benaderingen bijzonder krachtig: ze vereisen geen enkele voorkennis over hoe de omgeving werkt. In plaats daarvan halen ze waarde-inschattingen direct uit wat er gebeurt tijdens de interactie. In veel praktijksituaties, waarin het modelleren van de omgeving onpraktisch of onmogelijk is, is dit vermogen om te leren uit ruwe ervaring een groot voordeel.

Wanneer directe interactie met de omgeving kostbaar, riskant of traag is, kunnen Monte Carlo-methoden ook leren uit gesimuleerde ervaring, mits er een betrouwbare simulatie beschikbaar is. Dit maakt verkenning en leren mogelijk in een gecontroleerde, herhaalbare omgeving — hoewel dit wel veronderstelt dat er toegang is tot een model dat geloofwaardige overgangen kan genereren.

question mark

Wat is een belangrijk voordeel van het gebruik van Monte Carlo-methoden ten opzichte van dynamische programmeermethoden bij het oplossen van MDP's?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 1
some-alt