Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lära Bellmans Ekvationer | Dynamisk Programmering
Introduktion till Förstärkningsinlärning

bookBellmans Ekvationer

Note
Definition

En Bellman-ekvation är en funktionalekvation som definierar en värdefunktion i rekursiv form.

För att förtydliga definitionen:

  • En funktionalekvation är en ekvation vars lösning är en funktion. För Bellman-ekvationen är denna lösning värdefunktionen som ekvationen är formulerad för;
  • En rekursiv form innebär att värdet i det aktuella tillståndet uttrycks i termer av värden i framtida tillstånd.

Sammanfattningsvis ger lösningen av Bellman-ekvationen den önskade värdefunktionen, och att härleda denna ekvation kräver att man identifierar en rekursiv relation mellan nuvarande och framtida tillstånd.

Tillståndsvärdefunktion

Som en påminnelse, här är en tillståndsvärdesfunktion i kompakt form:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

För att erhålla Bellman-ekvationen för denna värdesfunktion, expanderar vi höger sida av ekvationen och etablerar en rekursiv relation:

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 sista ekvationen i denna kedja är en Bellman-ekvation för tillståndsvärdesfunktionen.

Intuition

För att bestämma värdet av ett tillstånd ss:

  1. Beakta alla möjliga handlingar aa du kan utföra från detta tillstånd, var och en viktad efter sannolikheten att du väljer den handlingen enligt din nuvarande policy π(a∣s)\pi(a | s);
  2. För varje handling aa, beakta alla möjliga nästa tillstånd s′s' och belöningar rr, viktade efter deras sannolikhet p(s′,r∣s,a)p(s', r | s, a);
  3. För varje av dessa utfall, ta den omedelbara belöningen rr du får plus det diskonterade värdet av nästa tillstånd γvπ(s′)\gamma v_\pi(s').

Genom att summera alla dessa möjligheter får du det totala förväntade värdet av tillståndet ss under din nuvarande policy.

Aktionsvärdesfunktion

Här är en aktionsvärdesfunktion 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]

Härledning av Bellman-ekvationen för denna funktion är mycket lik den föregående:

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 sista ekvationen i denna kedja är en Bellman-ekvation för aktionsvärdesfunktionen.

Intuition

För att hitta värdet av ett tillstånd-aktionspar (s,a)(s, a):

  1. Beakta alla möjliga nästa tillstånd s′s' och belöningar rr, viktade efter deras sannolikhet p(s′,r∣s,a)p(s', r | s, a);
  2. För varje av dessa utfall tar du den omedelbara belöningen rr du får plus det diskonterade värdet av nästa tillstånd;
  3. För att beräkna värdet av nästa tillstånd s′s', multiplicera för alla möjliga handlingar a′a' från tillståndet s′s', handlingsvärdet q(s′,a′)q(s', a') med sannolikheten att välja a′a' i tillståndet s′s' under nuvarande policy π(a′∣s′)\pi(a' | s'). Summera sedan allt för att få det slutliga värdet.

Genom att summera alla dessa möjligheter får du det totala förväntade värdet av tillstånd-aktionsparet (s,a)(s, a) under din nuvarande policy.

question mark

Vilket av följande beskriver bäst funktionen hos Bellmans ekvation?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2

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

Awesome!

Completion rate improved to 2.7

bookBellmans Ekvationer

Svep för att visa menyn

Note
Definition

En Bellman-ekvation är en funktionalekvation som definierar en värdefunktion i rekursiv form.

För att förtydliga definitionen:

  • En funktionalekvation är en ekvation vars lösning är en funktion. För Bellman-ekvationen är denna lösning värdefunktionen som ekvationen är formulerad för;
  • En rekursiv form innebär att värdet i det aktuella tillståndet uttrycks i termer av värden i framtida tillstånd.

Sammanfattningsvis ger lösningen av Bellman-ekvationen den önskade värdefunktionen, och att härleda denna ekvation kräver att man identifierar en rekursiv relation mellan nuvarande och framtida tillstånd.

Tillståndsvärdefunktion

Som en påminnelse, här är en tillståndsvärdesfunktion i kompakt form:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

För att erhålla Bellman-ekvationen för denna värdesfunktion, expanderar vi höger sida av ekvationen och etablerar en rekursiv relation:

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 sista ekvationen i denna kedja är en Bellman-ekvation för tillståndsvärdesfunktionen.

Intuition

För att bestämma värdet av ett tillstånd ss:

  1. Beakta alla möjliga handlingar aa du kan utföra från detta tillstånd, var och en viktad efter sannolikheten att du väljer den handlingen enligt din nuvarande policy π(a∣s)\pi(a | s);
  2. För varje handling aa, beakta alla möjliga nästa tillstånd s′s' och belöningar rr, viktade efter deras sannolikhet p(s′,r∣s,a)p(s', r | s, a);
  3. För varje av dessa utfall, ta den omedelbara belöningen rr du får plus det diskonterade värdet av nästa tillstånd γvπ(s′)\gamma v_\pi(s').

Genom att summera alla dessa möjligheter får du det totala förväntade värdet av tillståndet ss under din nuvarande policy.

Aktionsvärdesfunktion

Här är en aktionsvärdesfunktion 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]

Härledning av Bellman-ekvationen för denna funktion är mycket lik den föregående:

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 sista ekvationen i denna kedja är en Bellman-ekvation för aktionsvärdesfunktionen.

Intuition

För att hitta värdet av ett tillstånd-aktionspar (s,a)(s, a):

  1. Beakta alla möjliga nästa tillstånd s′s' och belöningar rr, viktade efter deras sannolikhet p(s′,r∣s,a)p(s', r | s, a);
  2. För varje av dessa utfall tar du den omedelbara belöningen rr du får plus det diskonterade värdet av nästa tillstånd;
  3. För att beräkna värdet av nästa tillstånd s′s', multiplicera för alla möjliga handlingar a′a' från tillståndet s′s', handlingsvärdet q(s′,a′)q(s', a') med sannolikheten att välja a′a' i tillståndet s′s' under nuvarande policy π(a′∣s′)\pi(a' | s'). Summera sedan allt för att få det slutliga värdet.

Genom att summera alla dessa möjligheter får du det totala förväntade värdet av tillstånd-aktionsparet (s,a)(s, a) under din nuvarande policy.

question mark

Vilket av följande beskriver bäst funktionen hos Bellmans ekvation?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2
some-alt