Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Leer Incrementele Implementaties | 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
Incrementele Implementaties

Het opslaan van elke opbrengst voor elk toestand-actie-paar kan snel het geheugen uitputten en de rekentijd aanzienlijk verhogen — vooral in grote omgevingen. Deze beperking beïnvloedt zowel on-policy als off-policy Monte Carlo-controle-algoritmen. Om dit aan te pakken, passen we incrementele berekeningsstrategieën toe, vergelijkbaar met die gebruikt in multi-armed bandit-algoritmen. Deze methoden maken het mogelijk om waarde-inschattingen direct bij te werken, zonder volledige opbrengstgeschiedenissen te bewaren.

On-Policy Monte Carlo-controle

Voor de on-policy methode lijkt de bijwerkstrategie op de strategie die wordt gebruikt in MAB-algoritmen:

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

waarbij α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} voor de gemiddelde schatting. De enige waarden die opgeslagen moeten worden zijn de huidige schattingen van de actiewaarden Q(s,a)Q(s, a) en het aantal keren dat het toestand-actie-paar (s,a)(s, a) is bezocht N(s,a)N(s, a).

Pseudocode

Off-Policy Monte Carlo-controle

Voor de off-policy methode met gewone importance sampling is alles hetzelfde als bij de on-policy methode.

Een interessantere situatie ontstaat bij gewogen importance sampling. De vergelijking ziet er hetzelfde uit:

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

maar α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kan niet worden gebruikt omdat:

  1. Elke opbrengst wordt gewogen met ρ\rho;
  2. De uiteindelijke som wordt niet gedeeld door N(s,a)N(s, a), maar door ρ(s,a)\sum \rho(s, a).

De waarde van α\alpha die in dit geval daadwerkelijk kan worden gebruikt is gelijk aan WC(s,a)\displaystyle \frac{W}{C(s,a)} waarbij:

  • WW een ρ\rho is voor het huidige traject;
  • C(s,a)C(s, a) gelijk is aan ρ(s,a)\sum \rho(s, a).

En elke keer dat het toestand-actie-paar (s,a)(s, a) voorkomt, wordt de ρ\rho van het huidige traject toegevoegd aan C(s,a)C(s, a):

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

Pseudocode

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 7

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
Incrementele Implementaties

Het opslaan van elke opbrengst voor elk toestand-actie-paar kan snel het geheugen uitputten en de rekentijd aanzienlijk verhogen — vooral in grote omgevingen. Deze beperking beïnvloedt zowel on-policy als off-policy Monte Carlo-controle-algoritmen. Om dit aan te pakken, passen we incrementele berekeningsstrategieën toe, vergelijkbaar met die gebruikt in multi-armed bandit-algoritmen. Deze methoden maken het mogelijk om waarde-inschattingen direct bij te werken, zonder volledige opbrengstgeschiedenissen te bewaren.

On-Policy Monte Carlo-controle

Voor de on-policy methode lijkt de bijwerkstrategie op de strategie die wordt gebruikt in MAB-algoritmen:

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

waarbij α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} voor de gemiddelde schatting. De enige waarden die opgeslagen moeten worden zijn de huidige schattingen van de actiewaarden Q(s,a)Q(s, a) en het aantal keren dat het toestand-actie-paar (s,a)(s, a) is bezocht N(s,a)N(s, a).

Pseudocode

Off-Policy Monte Carlo-controle

Voor de off-policy methode met gewone importance sampling is alles hetzelfde als bij de on-policy methode.

Een interessantere situatie ontstaat bij gewogen importance sampling. De vergelijking ziet er hetzelfde uit:

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

maar α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kan niet worden gebruikt omdat:

  1. Elke opbrengst wordt gewogen met ρ\rho;
  2. De uiteindelijke som wordt niet gedeeld door N(s,a)N(s, a), maar door ρ(s,a)\sum \rho(s, a).

De waarde van α\alpha die in dit geval daadwerkelijk kan worden gebruikt is gelijk aan WC(s,a)\displaystyle \frac{W}{C(s,a)} waarbij:

  • WW een ρ\rho is voor het huidige traject;
  • C(s,a)C(s, a) gelijk is aan ρ(s,a)\sum \rho(s, a).

En elke keer dat het toestand-actie-paar (s,a)(s, a) voorkomt, wordt de ρ\rho van het huidige traject toegevoegd aan C(s,a)C(s, a):

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

Pseudocode

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 7
some-alt