Kursinnhold

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL

Hva er RL?RL Kontra Andre Læringsparadigmer Markov Beslutningsprosess Episoder og Avkastning Modell, policy og verdier Utforskning vs Utnyttelse Grunnleggende om Gymnasium Utfordring: Oppsett av et Miljø

2. Multi-Armet Bandittproblem

Probleminnledning Aksjonsverdier Epsilon-grådig Algoritme Algoritme for Øvre Konfidensgrense Gradientbandittalgoritme Utfordring: Multi-Armede Banditter

3. Dynamisk Programmering

Hva er dynamisk programmering?Bellman-ligninger Optimalitetsbetingelser Policyvurdering Policyforbedring Generalisert Policyiterasjon Policyiterasjon Verdiiterasjon Utfordring: Dynamisk Programmering

4. Monte Carlo-metoder

Hva er Monte Carlo-metoder?Estimering av Verdifunksjon Monte Carlo-Kontroll Utforskningsmetoder On-Policy Monte Carlo-Kontroll Off-Policy Monte Carlo-Kontroll Inkrementelle Implementasjoner Utfordring: Monte Carlo-metoder

5. Temporal Difference-læring

Hva er temporær differanse-læring?TD(0): Verdifunksjonsestimering SARSA: On-Policy TD-Læring Q-læring: Off-Policy TD-Læring Generalisering av TD-læring Utfordring: Temporær Differanse-Læring

Bellman-ligninger

Definisjon

En Bellman-ligning er en funksjonell ligning som definerer en verdifunksjon i rekursiv form.

For å tydeliggjøre definisjonen:

En funksjonell ligning er en ligning der løsningen er en funksjon. For Bellman-ligningen er denne løsningen verdifunksjonen som ligningen er formulert for;
En rekursiv form betyr at verdien i nåværende tilstand uttrykkes ved hjelp av verdier i fremtidige tilstander.

Kort sagt, å løse Bellman-ligningen gir den ønskede verdifunksjonen, og å utlede denne ligningen krever å identifisere et rekursivt forhold mellom nåværende og fremtidige tilstander.

Tilstandsverdifunksjon

Som en påminnelse, her er en tilstandsverdifunksjon i kompakt form:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

For å utlede Bellman-likningen for denne verdifunksjonen, utvider vi høyresiden av likningen og etablerer et rekursivt forhold:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Den siste likningen i denne kjeden er en Bellman-likning for tilstandsverdifunksjonen.

Intuisjon

For å finne verdien til en tilstand $s$ :

Vurder alle mulige handlinger $a$ du kan ta fra denne tilstanden, hver vektet etter hvor sannsynlig det er at du velger denne handlingen under din nåværende policy $\pi(a | s)$ ;
For hver handling $a$ vurderer du alle mulige neste tilstander $s'$ og belønninger $r$ , vektet etter sannsynligheten $p(s', r | s, a)$ ;
For hvert av disse utfallene tar du den umiddelbare belønningen $r$ du får pluss den diskonterte verdien av neste tilstand $\gamma v_\pi(s')$ .

Ved å summere alle disse mulighetene får du den totale forventede verdien av tilstanden $s$ under din nåværende policy.

Handlingsverdifunksjon

Her er en handlingsverdifunksjon i kompakt form:

\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Utledningen av Bellman-likningen for denne funksjonen ligner mye på den forrige:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Den siste likningen i denne kjeden er en Bellman-likning for handlingsverdifunksjonen.

Intuisjon

For å finne verdien til et tilstands-handlingspar $(s, a)$ , gjør du følgende:

Vurder alle mulige neste tilstander $s'$ og belønninger $r$ , vektet etter sannsynligheten $p(s', r | s, a)$ ;
For hvert av disse utfallene tar du den umiddelbare belønningen $r$ du får, pluss den diskonterte verdien av neste tilstand;
For å beregne verdien av neste tilstand $s'$ , for alle handlinger $a'$ som er mulige fra tilstand $s'$ , multipliserer du handlingsverdien $q(s', a')$ med sannsynligheten for å velge $a'$ i tilstand $s'$ under gjeldende policy $\pi(a' | s')$ . Deretter summerer du alt for å få den endelige verdien.

Ved å summere alle disse mulighetene sammen, får du den totale forventede verdien av tilstands-handlingsparet $(s, a)$ under din nåværende policy.

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Kursinnhold

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL

2. Multi-Armet Bandittproblem

Probleminnledning Aksjonsverdier Epsilon-grådig Algoritme Algoritme for Øvre Konfidensgrense Gradientbandittalgoritme Utfordring: Multi-Armede Banditter

3. Dynamisk Programmering

Hva er dynamisk programmering?Bellman-ligninger Optimalitetsbetingelser Policyvurdering Policyforbedring Generalisert Policyiterasjon Policyiterasjon Verdiiterasjon Utfordring: Dynamisk Programmering

4. Monte Carlo-metoder

5. Temporal Difference-læring

Hva er temporær differanse-læring?TD(0): Verdifunksjonsestimering SARSA: On-Policy TD-Læring Q-læring: Off-Policy TD-Læring Generalisering av TD-læring Utfordring: Temporær Differanse-Læring

Bellman-ligninger

Definisjon

En Bellman-ligning er en funksjonell ligning som definerer en verdifunksjon i rekursiv form.

For å tydeliggjøre definisjonen:

En funksjonell ligning er en ligning der løsningen er en funksjon. For Bellman-ligningen er denne løsningen verdifunksjonen som ligningen er formulert for;
En rekursiv form betyr at verdien i nåværende tilstand uttrykkes ved hjelp av verdier i fremtidige tilstander.

Kort sagt, å løse Bellman-ligningen gir den ønskede verdifunksjonen, og å utlede denne ligningen krever å identifisere et rekursivt forhold mellom nåværende og fremtidige tilstander.

Tilstandsverdifunksjon

Som en påminnelse, her er en tilstandsverdifunksjon i kompakt form:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

For å utlede Bellman-likningen for denne verdifunksjonen, utvider vi høyresiden av likningen og etablerer et rekursivt forhold:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Den siste likningen i denne kjeden er en Bellman-likning for tilstandsverdifunksjonen.

Intuisjon

For å finne verdien til en tilstand $s$ :

Vurder alle mulige handlinger $a$ du kan ta fra denne tilstanden, hver vektet etter hvor sannsynlig det er at du velger denne handlingen under din nåværende policy $\pi(a | s)$ ;
For hver handling $a$ vurderer du alle mulige neste tilstander $s'$ og belønninger $r$ , vektet etter sannsynligheten $p(s', r | s, a)$ ;
For hvert av disse utfallene tar du den umiddelbare belønningen $r$ du får pluss den diskonterte verdien av neste tilstand $\gamma v_\pi(s')$ .

Ved å summere alle disse mulighetene får du den totale forventede verdien av tilstanden $s$ under din nåværende policy.

Handlingsverdifunksjon

Her er en handlingsverdifunksjon i kompakt form:

\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Utledningen av Bellman-likningen for denne funksjonen ligner mye på den forrige:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Den siste likningen i denne kjeden er en Bellman-likning for handlingsverdifunksjonen.

Intuisjon

For å finne verdien til et tilstands-handlingspar $(s, a)$ , gjør du følgende:

Vurder alle mulige neste tilstander $s'$ og belønninger $r$ , vektet etter sannsynligheten $p(s', r | s, a)$ ;
For hvert av disse utfallene tar du den umiddelbare belønningen $r$ du får, pluss den diskonterte verdien av neste tilstand;
For å beregne verdien av neste tilstand $s'$ , for alle handlinger $a'$ som er mulige fra tilstand $s'$ , multipliserer du handlingsverdien $q(s', a')$ med sannsynligheten for å velge $a'$ i tilstand $s'$ under gjeldende policy $\pi(a' | s')$ . Deretter summerer du alt for å få den endelige verdien.

Ved å summere alle disse mulighetene sammen, får du den totale forventede verdien av tilstands-handlingsparet $(s, a)$ under din nåværende policy.

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2