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 funktionell ekvation som definierar en värdefunktion i rekursiv form.

För att förtydliga definitionen:

  • En funktionell ekvation ä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π[GtSt=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

För att erhålla Bellmans ekvation för denna värdefunktion, utvecklas höger sida av ekvationen och en rekursiv relation etableras:

vπ(s)=Eπ[GtSt=s]=Eπ[Rt+1+γRt+2+γ2Rt+3+...St=s]=Eπ[Rt+1+γk=0γkRt+k+2St=s]=Eπ[Rt+1+γGt+1St=s]=aπ(as)s,rp(s,rs,a)(r+γEπ[Gt+1St+1=s])=aπ(as)s,rp(s,rs,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 Bellmans 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 som kan utföras från detta tillstånd, där varje handling vägs efter sannolikheten att den väljs enligt den aktuella policyn π(as)\pi(a | s);
  2. För varje handling aa, beaktas alla möjliga nästa tillstånd ss' och belöningar rr, viktade efter deras sannolikhet p(s,rs,a)p(s', r | s, a);
  3. För varje utfall summeras den omedelbara belöningen rr med det diskonterade värdet av nästa tillstånd γvπ(s)\gamma v_\pi(s').

Genom att summera alla dessa möjligheter erhålls det totala förväntade värdet av tillståndet ss under den aktuella policyn.

Aktionsvärdesfunktion

Här är en aktionsvärdesfunktion i kompakt form:

qπ(s,a)=Eπ[GtSt=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 liknar den föregående:

qπ(s,a)=Eπ[GtSt=s,At=a]=Eπ[Rt+1+γRt+2+γ2Rt+3+...St=s,At=a]=Eπ[Rt+1+γk=0γkRt+k+2St=s,At=a]=Eπ[Rt+1+γGt+1St=s,At=a]=s,rp(s,rs,a)(r+γEπ[Gt+1St+1=s])=s,rp(s,rs,a)(r+γaπ(as)(Eπ[Gt+1St+1=s,At+1=a]))=s,rp(s,rs,a)(r+γaπ(as)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ånds- och åtgärdspar (s,a)(s, a):

  1. Beakta alla möjliga nästa tillstånd ss' och belöningar rr, viktade efter deras sannolikhet p(s,rs,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 ss', multiplicera för alla möjliga åtgärder aa' från tillståndet ss' åtgärdsvärdet q(s,a)q(s', a') med sannolikheten att välja aa' i tillstånd ss' under nuvarande policy π(as)\pi(a' | s'). Summera sedan allt för att få slutvärdet.

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

question mark

Vilket av följande beskriver bäst funktionen hos Bellman-ekvationen?

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

Suggested prompts:

Can you explain the difference between the state value function and the action value function?

How does the Bellman equation help in reinforcement learning?

Can you provide a simple example illustrating the Bellman equation?

Awesome!

Completion rate improved to 2.7

bookBellmans Ekvationer

Svep för att visa menyn

Note
Definition

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

För att förtydliga definitionen:

  • En funktionell ekvation ä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π[GtSt=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

För att erhålla Bellmans ekvation för denna värdefunktion, utvecklas höger sida av ekvationen och en rekursiv relation etableras:

vπ(s)=Eπ[GtSt=s]=Eπ[Rt+1+γRt+2+γ2Rt+3+...St=s]=Eπ[Rt+1+γk=0γkRt+k+2St=s]=Eπ[Rt+1+γGt+1St=s]=aπ(as)s,rp(s,rs,a)(r+γEπ[Gt+1St+1=s])=aπ(as)s,rp(s,rs,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 Bellmans 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 som kan utföras från detta tillstånd, där varje handling vägs efter sannolikheten att den väljs enligt den aktuella policyn π(as)\pi(a | s);
  2. För varje handling aa, beaktas alla möjliga nästa tillstånd ss' och belöningar rr, viktade efter deras sannolikhet p(s,rs,a)p(s', r | s, a);
  3. För varje utfall summeras den omedelbara belöningen rr med det diskonterade värdet av nästa tillstånd γvπ(s)\gamma v_\pi(s').

Genom att summera alla dessa möjligheter erhålls det totala förväntade värdet av tillståndet ss under den aktuella policyn.

Aktionsvärdesfunktion

Här är en aktionsvärdesfunktion i kompakt form:

qπ(s,a)=Eπ[GtSt=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 liknar den föregående:

qπ(s,a)=Eπ[GtSt=s,At=a]=Eπ[Rt+1+γRt+2+γ2Rt+3+...St=s,At=a]=Eπ[Rt+1+γk=0γkRt+k+2St=s,At=a]=Eπ[Rt+1+γGt+1St=s,At=a]=s,rp(s,rs,a)(r+γEπ[Gt+1St+1=s])=s,rp(s,rs,a)(r+γaπ(as)(Eπ[Gt+1St+1=s,At+1=a]))=s,rp(s,rs,a)(r+γaπ(as)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ånds- och åtgärdspar (s,a)(s, a):

  1. Beakta alla möjliga nästa tillstånd ss' och belöningar rr, viktade efter deras sannolikhet p(s,rs,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 ss', multiplicera för alla möjliga åtgärder aa' från tillståndet ss' åtgärdsvärdet q(s,a)q(s', a') med sannolikheten att välja aa' i tillstånd ss' under nuvarande policy π(as)\pi(a' | s'). Summera sedan allt för att få slutvärdet.

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

question mark

Vilket av följande beskriver bäst funktionen hos Bellman-ekvationen?

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