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

bookIncrementele 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.

Awesome!

Completion rate improved to 2.7

bookIncrementele Implementaties

Veeg om het menu te tonen

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