Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Hva er Monte Carlo-metoder? | Monte Carlo-metoder
Introduksjon til Forsterkende Læring
course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Hva er Monte Carlo-metoder?

Note
Definisjon

Monte Carlo (MC)-metoder er en klasse av beregningsalgoritmer som baserer seg på tilfeldig utvalg for å estimere numeriske resultater.

Monte Carlo-metoder brukes når deterministiske løsninger er vanskelige eller umulige å oppnå. De erstatter nøyaktige beregninger med tilnærminger som forbedres med antall tilfeldige utvalg.

Hvordan fungerer de?

Monte Carlo-metoder kan variere fra én oppgave til en annen, men alle følger et felles mønster:

  1. Definer et domene av mulige inputverdier;
  2. Generer tilfeldige inputverdier fra en sannsynlighetsfordeling;
  3. Evaluer en funksjon på disse inputverdiene;
  4. Aggreger resultatene for å produsere et estimat.

Eksempler

Selv om mønsteret beskrevet ovenfor kan virke komplekst, vil disse eksemplene bidra til å tydeliggjøre ideen bak det.

Integralkomputasjon

Å beregne integraler er en ikke-triviell oppgave som vanligvis krever bruk av flere teknikker for å oppnå korrekt resultat.

La oss forsøke å bruke Monte Carlo-metoden for å løse dette integralet:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Inndataområde: Dette dobbeltintegralet har to variabler, x[0,1]x \in [0, 1] og y[0,1]y \in [0, 1];
  2. Generering: Begge disse variablene er uavhengige av hverandre og jevnt fordelt;
  3. Evaluering: For å få en punktverdi kan funksjonen under integralene brukes;
  4. Aggregasjon: Verdien av dette integralet kan defineres som volumet under kurven. Volumet kan beregnes som produktet av grunnflatearealet og gjennomsnittshøyden. Grunnflatearealet er 1 (enhet kvadrat) og gjennomsnittshøyden er gjennomsnittet av resultatene fra forrige steg.
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

Tilnærming av π\Large\pi

Å tilnærme π\pi er en av de mest ikoniske bruksområdene for Monte Carlo-metoden. Dette illustrerer hvordan tilfeldig utvalg kan løse et geometrisk problem uten avansert kalkulus.

Tenk deg et enhetskvadrat med en kvart sirkel innsirklet i det:

  • Kvadratet strekker seg over [0,1]×[0,1][0, 1] \times [0, 1];
  • Kvartsirkelen har radius 1 og er sentrert i origo.

Arealet til kvartsirkelen er πr24\displaystyle\frac{\pi r^2}{4} eller π4\displaystyle\frac{\pi}{4}, og arealet til kvadratet er 1. Nå kan vi trekke tilfeldige punkter inne i kvadratet. Med et stort nok utvalg:

Points inside the quarter circleTotal pointsπ4\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Dermed kan verdien av π\pi beregnes som

π4Points insideTotal points\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}
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 banditter

I multi-armed bandit-problemet er et sentralt mål å estimere aksjonsverdien for hver arm — det vil si den forventede belønningen ved å velge en bestemt handling. En vanlig strategi er å estimere disse verdiene ved å ta gjennomsnittet av de observerte belønningene som oppnås ved å trekke i hver arm over tid. Denne teknikken er faktisk en Monte Carlo-metode.

Monte Carlo-metoder for MDP-er

I motsetning til dynamisk programmering-metoder, som er avhengige av en fullstendig og nøyaktig modell av miljøets dynamikk, lærer Monte Carlo-metoder utelukkende fra erfaring — det vil si fra faktiske eller simulerte sekvenser av tilstander, handlinger og belønninger.

Dette gjør Monte Carlo-tilnærminger spesielt kraftfulle: de krever ingen forhåndskunnskap om hvordan miljøet fungerer. I stedet utleder de verdiberegninger direkte fra det som skjer under interaksjon. I mange virkelige scenarier, der modellering av miljøet er upraktisk eller umulig, er denne evnen til å lære fra rå erfaring en stor fordel.

Når direkte interaksjon med miljøet er kostbart, risikabelt eller tregt, kan Monte Carlo-metoder også lære fra simulert erfaring, forutsatt at det finnes en pålitelig simulering. Dette muliggjør utforskning og læring i et kontrollert, repeterbart miljø — selv om det forutsetter tilgang til en modell som kan generere plausible overganger.

question mark

Hva er en hovedfordel med å bruke Monte Carlo-metoder fremfor dynamisk programmering i løsning av MDP-er?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 1

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Hva er Monte Carlo-metoder?

Note
Definisjon

Monte Carlo (MC)-metoder er en klasse av beregningsalgoritmer som baserer seg på tilfeldig utvalg for å estimere numeriske resultater.

Monte Carlo-metoder brukes når deterministiske løsninger er vanskelige eller umulige å oppnå. De erstatter nøyaktige beregninger med tilnærminger som forbedres med antall tilfeldige utvalg.

Hvordan fungerer de?

Monte Carlo-metoder kan variere fra én oppgave til en annen, men alle følger et felles mønster:

  1. Definer et domene av mulige inputverdier;
  2. Generer tilfeldige inputverdier fra en sannsynlighetsfordeling;
  3. Evaluer en funksjon på disse inputverdiene;
  4. Aggreger resultatene for å produsere et estimat.

Eksempler

Selv om mønsteret beskrevet ovenfor kan virke komplekst, vil disse eksemplene bidra til å tydeliggjøre ideen bak det.

Integralkomputasjon

Å beregne integraler er en ikke-triviell oppgave som vanligvis krever bruk av flere teknikker for å oppnå korrekt resultat.

La oss forsøke å bruke Monte Carlo-metoden for å løse dette integralet:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Inndataområde: Dette dobbeltintegralet har to variabler, x[0,1]x \in [0, 1] og y[0,1]y \in [0, 1];
  2. Generering: Begge disse variablene er uavhengige av hverandre og jevnt fordelt;
  3. Evaluering: For å få en punktverdi kan funksjonen under integralene brukes;
  4. Aggregasjon: Verdien av dette integralet kan defineres som volumet under kurven. Volumet kan beregnes som produktet av grunnflatearealet og gjennomsnittshøyden. Grunnflatearealet er 1 (enhet kvadrat) og gjennomsnittshøyden er gjennomsnittet av resultatene fra forrige steg.
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

Tilnærming av π\Large\pi

Å tilnærme π\pi er en av de mest ikoniske bruksområdene for Monte Carlo-metoden. Dette illustrerer hvordan tilfeldig utvalg kan løse et geometrisk problem uten avansert kalkulus.

Tenk deg et enhetskvadrat med en kvart sirkel innsirklet i det:

  • Kvadratet strekker seg over [0,1]×[0,1][0, 1] \times [0, 1];
  • Kvartsirkelen har radius 1 og er sentrert i origo.

Arealet til kvartsirkelen er πr24\displaystyle\frac{\pi r^2}{4} eller π4\displaystyle\frac{\pi}{4}, og arealet til kvadratet er 1. Nå kan vi trekke tilfeldige punkter inne i kvadratet. Med et stort nok utvalg:

Points inside the quarter circleTotal pointsπ4\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Dermed kan verdien av π\pi beregnes som

π4Points insideTotal points\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}
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 banditter

I multi-armed bandit-problemet er et sentralt mål å estimere aksjonsverdien for hver arm — det vil si den forventede belønningen ved å velge en bestemt handling. En vanlig strategi er å estimere disse verdiene ved å ta gjennomsnittet av de observerte belønningene som oppnås ved å trekke i hver arm over tid. Denne teknikken er faktisk en Monte Carlo-metode.

Monte Carlo-metoder for MDP-er

I motsetning til dynamisk programmering-metoder, som er avhengige av en fullstendig og nøyaktig modell av miljøets dynamikk, lærer Monte Carlo-metoder utelukkende fra erfaring — det vil si fra faktiske eller simulerte sekvenser av tilstander, handlinger og belønninger.

Dette gjør Monte Carlo-tilnærminger spesielt kraftfulle: de krever ingen forhåndskunnskap om hvordan miljøet fungerer. I stedet utleder de verdiberegninger direkte fra det som skjer under interaksjon. I mange virkelige scenarier, der modellering av miljøet er upraktisk eller umulig, er denne evnen til å lære fra rå erfaring en stor fordel.

Når direkte interaksjon med miljøet er kostbart, risikabelt eller tregt, kan Monte Carlo-metoder også lære fra simulert erfaring, forutsatt at det finnes en pålitelig simulering. Dette muliggjør utforskning og læring i et kontrollert, repeterbart miljø — selv om det forutsetter tilgang til en modell som kan generere plausible overganger.

question mark

Hva er en hovedfordel med å bruke Monte Carlo-metoder fremfor dynamisk programmering i løsning av MDP-er?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 1
some-alt