Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Bellman-ligninger | Dynamisk Programmering
Introduksjon til Forsterkende Læring

bookBellman-ligninger

Note
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:

vπ(s)=E⁡π[Gt∣St=s]\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:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\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 ss:

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

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

Handlingsverdifunksjon

Her er en handlingsverdifunksjon i kompakt form:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\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:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\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)(s, a), gjør du følgende:

  1. Vurder alle mulige neste tilstander s′s' og belønninger rr, vektet etter sannsynligheten p(s′,r∣s,a)p(s', r | s, a);
  2. For hvert av disse utfallene tar du den umiddelbare belønningen rr du får, pluss den diskonterte verdien av neste tilstand;
  3. For å beregne verdien av neste tilstand s′s', for alle handlinger a′a' som er mulige fra tilstand s′s', multipliserer du handlingsverdien q(s′,a′)q(s', a') med sannsynligheten for å velge a′a' i tilstand s′s' under gjeldende policy π(a′∣s′)\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)(s, a) under din nåværende policy.

question mark

Hvilket av følgende beskriver best funksjonen til Bellman-likningen?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2

Spør AI

expand

Spør AI

ChatGPT

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

Awesome!

Completion rate improved to 2.7

bookBellman-ligninger

Sveip for å vise menyen

Note
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:

vπ(s)=E⁡π[Gt∣St=s]\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:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\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 ss:

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

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

Handlingsverdifunksjon

Her er en handlingsverdifunksjon i kompakt form:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\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:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\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)(s, a), gjør du følgende:

  1. Vurder alle mulige neste tilstander s′s' og belønninger rr, vektet etter sannsynligheten p(s′,r∣s,a)p(s', r | s, a);
  2. For hvert av disse utfallene tar du den umiddelbare belønningen rr du får, pluss den diskonterte verdien av neste tilstand;
  3. For å beregne verdien av neste tilstand s′s', for alle handlinger a′a' som er mulige fra tilstand s′s', multipliserer du handlingsverdien q(s′,a′)q(s', a') med sannsynligheten for å velge a′a' i tilstand s′s' under gjeldende policy π(a′∣s′)\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)(s, a) under din nåværende policy.

question mark

Hvilket av følgende beskriver best funksjonen til Bellman-likningen?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2
some-alt