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 Reinforcement Learning
course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
Inkrementelle Implementeringer

At gemme hver eneste afkastværdi 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ærdiskøn kan opdateres løbende, uden at hele afkasts-historikken 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 handlingsvæ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 almindelig 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 bruges, 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 bruges 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) optræder, 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

course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
Inkrementelle Implementeringer

At gemme hver eneste afkastværdi 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ærdiskøn kan opdateres løbende, uden at hele afkasts-historikken 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 handlingsvæ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 almindelig 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 bruges, 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 bruges 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) optræder, 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