Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära Inkrementella Implementationer | Monte Carlo-metoder
Introduktion till Förstärkningsinlärning
course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
2. Multi-Armed Bandit-Problemet
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporär Differensinlärning

book
Inkrementella Implementationer

Att lagra varje avkastning för varje tillstånd-aktionspar kan snabbt förbruka minne och avsevärt öka beräkningstiden — särskilt i stora miljöer. Denna begränsning påverkar både on-policy och off-policy Monte Carlo-kontrollalgoritmer. För att hantera detta använder vi inkrementella beräkningsstrategier, liknande de som används i multi-armed bandit-algoritmer. Dessa metoder möjliggör att värdeuppskattningar uppdateras direkt, utan att hela avkastningshistoriken behöver sparas.

On-policy Monte Carlo-kontroll

För on-policy-metoden liknar uppdateringsstrategin den som används i MAB-algoritmer:

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

där α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} för medelvärdesuppskattning. De enda värden som behöver sparas är de aktuella uppskattningarna av aktionsvärden Q(s,a)Q(s, a) och antalet gånger tillstånd-aktionsparet (s,a)(s, a) har besökts N(s,a)N(s, a).

Pseudokod

Off-policy Monte Carlo-kontroll

För off-policy-metoden med ordinär importance sampling är allt detsamma som för on-policy-metoden.

En mer intressant situation uppstår med viktad importance sampling. Ekvationen ser likadan ut:

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 inte användas eftersom:

  1. Varje return är viktad med ρ\rho;
  2. Den slutliga summan delas inte med N(s,a)N(s, a), utan med ρ(s,a)\sum \rho(s, a).

Värdet på α\alpha som faktiskt kan användas i detta fall är lika med WC(s,a)\displaystyle \frac{W}{C(s,a)} där:

  • WW är ρ\rho för den aktuella trajektorien;
  • C(s,a)C(s, a) är lika med ρ(s,a)\sum \rho(s, a).

Och varje gång tillstånd-aktionsparet (s,a)(s, a) uppstår, adderas ρ\rho för den aktuella trajektorien till C(s,a)C(s, a):

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

Pseudokod

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 7

Fråga AI

expand

Fråga AI

ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
2. Multi-Armed Bandit-Problemet
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporär Differensinlärning

book
Inkrementella Implementationer

Att lagra varje avkastning för varje tillstånd-aktionspar kan snabbt förbruka minne och avsevärt öka beräkningstiden — särskilt i stora miljöer. Denna begränsning påverkar både on-policy och off-policy Monte Carlo-kontrollalgoritmer. För att hantera detta använder vi inkrementella beräkningsstrategier, liknande de som används i multi-armed bandit-algoritmer. Dessa metoder möjliggör att värdeuppskattningar uppdateras direkt, utan att hela avkastningshistoriken behöver sparas.

On-policy Monte Carlo-kontroll

För on-policy-metoden liknar uppdateringsstrategin den som används i MAB-algoritmer:

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

där α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} för medelvärdesuppskattning. De enda värden som behöver sparas är de aktuella uppskattningarna av aktionsvärden Q(s,a)Q(s, a) och antalet gånger tillstånd-aktionsparet (s,a)(s, a) har besökts N(s,a)N(s, a).

Pseudokod

Off-policy Monte Carlo-kontroll

För off-policy-metoden med ordinär importance sampling är allt detsamma som för on-policy-metoden.

En mer intressant situation uppstår med viktad importance sampling. Ekvationen ser likadan ut:

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 inte användas eftersom:

  1. Varje return är viktad med ρ\rho;
  2. Den slutliga summan delas inte med N(s,a)N(s, a), utan med ρ(s,a)\sum \rho(s, a).

Värdet på α\alpha som faktiskt kan användas i detta fall är lika med WC(s,a)\displaystyle \frac{W}{C(s,a)} där:

  • WW är ρ\rho för den aktuella trajektorien;
  • C(s,a)C(s, a) är lika med ρ(s,a)\sum \rho(s, a).

Och varje gång tillstånd-aktionsparet (s,a)(s, a) uppstår, adderas ρ\rho för den aktuella trajektorien till C(s,a)C(s, a):

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

Pseudokod

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 7
some-alt