Inkrementelle 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)+α(G−Q(s,a))hvor α=N(s,a)1 for middelværdiestimat. De eneste værdier, der skal gemmes, er de aktuelle estimater af action-værdierne Q(s,a) og antallet af gange, state-action-parret (s,a) er blevet besøgt 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)+α(G−Q(s,a))men α=N(s,a)1 kan ikke anvendes, fordi:
- Hver returnering vægtes med ρ;
- Den endelige sum divideres ikke med N(s,a), men med ∑ρ(s,a).
Værdien af α, der faktisk kan anvendes i dette tilfælde, er lig med C(s,a)W hvor:
- W er en ρ for den aktuelle sekvens;
- C(s,a) er lig med ∑ρ(s,a).
Og hver gang state-action-parret (s,a) forekommer, lægges ρ for den aktuelle sekvens til C(s,a):
C(s,a)←C(s,a)+WPseudokode
Tak for dine kommentarer!
Spørg AI
Spørg AI
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
Inkrementelle 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)+α(G−Q(s,a))hvor α=N(s,a)1 for middelværdiestimat. De eneste værdier, der skal gemmes, er de aktuelle estimater af action-værdierne Q(s,a) og antallet af gange, state-action-parret (s,a) er blevet besøgt 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)+α(G−Q(s,a))men α=N(s,a)1 kan ikke anvendes, fordi:
- Hver returnering vægtes med ρ;
- Den endelige sum divideres ikke med N(s,a), men med ∑ρ(s,a).
Værdien af α, der faktisk kan anvendes i dette tilfælde, er lig med C(s,a)W hvor:
- W er en ρ for den aktuelle sekvens;
- C(s,a) er lig med ∑ρ(s,a).
Og hver gang state-action-parret (s,a) forekommer, lægges ρ for den aktuelle sekvens til C(s,a):
C(s,a)←C(s,a)+WPseudokode
Tak for dine kommentarer!