Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Inkrementelle Implementeringer | Monte Carlo-metoder
Introduktion til Forstærkningslæring

bookInkrementelle Implementeringer

Opbevaring af hver eneste returnering for hvert state-action-par kan hurtigt udtømme hukommelsen og markant forøge beregningstiden — især i store miljøer. Denne begrænsning påvirker både on-policy og off-policy Monte Carlo kontrolalgoritmer. For at imødekomme dette anvendes inkrementelle beregningsstrategier, svarende til dem, der bruges i multi-armed bandit-algoritmer. Disse metoder muliggør, at værdiestimater kan opdateres løbende, uden at hele returneringshistorikken skal gemmes.

On-policy Monte Carlo-kontrol

For on-policy-metoden ligner opdateringsstrategien den strategi, der anvendes i MAB-algoritmer:

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

hvor α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} for middelværdiestimat. De eneste værdier, der skal gemmes, er de aktuelle estimater af action-værdierne Q(s,a)Q(s, a) og antallet af gange, state-action-parret (s,a)(s, a) er blevet besøgt N(s,a)N(s, a).

Pseudokode

Off-policy Monte Carlo-kontrol

For off-policy-metoden med ordinær importance sampling er alt det samme som for on-policy-metoden.

En mere interessant situation opstår med vægtet importance sampling. Ligningen ser ud på samme måde:

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

men α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kan ikke anvendes, fordi:

  1. Hver returnering vægtes med ρ\rho;
  2. Den endelige sum divideres ikke med N(s,a)N(s, a), men med ρ(s,a)\sum \rho(s, a).

Værdien af α\alpha, der faktisk kan anvendes i dette tilfælde, er lig med WC(s,a)\displaystyle \frac{W}{C(s,a)} hvor:

  • WW er en ρ\rho for den aktuelle sekvens;
  • C(s,a)C(s, a) er lig med ρ(s,a)\sum \rho(s, a).

Og hver gang state-action-parret (s,a)(s, a) forekommer, lægges ρ\rho for den aktuelle sekvens til C(s,a)C(s, a):

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

Pseudokode

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 7

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 2.7

bookInkrementelle Implementeringer

Stryg for at vise menuen

Opbevaring af hver eneste returnering for hvert state-action-par kan hurtigt udtømme hukommelsen og markant forøge beregningstiden — især i store miljøer. Denne begrænsning påvirker både on-policy og off-policy Monte Carlo kontrolalgoritmer. For at imødekomme dette anvendes inkrementelle beregningsstrategier, svarende til dem, der bruges i multi-armed bandit-algoritmer. Disse metoder muliggør, at værdiestimater kan opdateres løbende, uden at hele returneringshistorikken skal gemmes.

On-policy Monte Carlo-kontrol

For on-policy-metoden ligner opdateringsstrategien den strategi, der anvendes i MAB-algoritmer:

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

hvor α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} for middelværdiestimat. De eneste værdier, der skal gemmes, er de aktuelle estimater af action-værdierne Q(s,a)Q(s, a) og antallet af gange, state-action-parret (s,a)(s, a) er blevet besøgt N(s,a)N(s, a).

Pseudokode

Off-policy Monte Carlo-kontrol

For off-policy-metoden med ordinær importance sampling er alt det samme som for on-policy-metoden.

En mere interessant situation opstår med vægtet importance sampling. Ligningen ser ud på samme måde:

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

men α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} kan ikke anvendes, fordi:

  1. Hver returnering vægtes med ρ\rho;
  2. Den endelige sum divideres ikke med N(s,a)N(s, a), men med ρ(s,a)\sum \rho(s, a).

Værdien af α\alpha, der faktisk kan anvendes i dette tilfælde, er lig med WC(s,a)\displaystyle \frac{W}{C(s,a)} hvor:

  • WW er en ρ\rho for den aktuelle sekvens;
  • C(s,a)C(s, a) er lig med ρ(s,a)\sum \rho(s, a).

Og hver gang state-action-parret (s,a)(s, a) forekommer, lægges ρ\rho for den aktuelle sekvens til C(s,a)C(s, a):

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

Pseudokode

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 7
some-alt