Lära Bellmans Ekvationer | Dynamisk Programmering

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 formulerats 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 härledning av 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:

\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ärdesfunktion, expanderas höger sida av ekvationen och en rekursiv relation etableras:

\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 hitta värdet av ett tillstånd $s$ :

Beakta alla möjliga handlingar $a$ som kan utföras från detta tillstånd, var och en viktad efter sannolikheten att välja den handlingen enligt den aktuella policyn $\pi(a | s)$ ;
För varje handling $a$ , beakta alla möjliga nästa tillstånd $s'$ och belöningar $r$ , viktade efter deras sannolikhet $p(s', r | s, a)$ ;
För varje av dessa utfall, ta den omedelbara belöningen $r$ samt det diskonterade värdet av nästa tillstånd $\gamma v_\pi(s')$ .

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

Aktionsvärdesfunktion

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

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

Härledning av Bellmans ekvation för denna funktion är ganska lik den föregående:

\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 Bellmans ekvation för aktionsvärdesfunktionen.

Intuition

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

Beakta alla möjliga nästa tillstånd $s'$ och belöningar $r$ , viktade efter deras sannolikhet $p(s', r | s, a)$ ;
För varje av dessa utfall tar du den omedelbara belöningen $r$ du får plus det diskonterade värdet av nästa tillstånd;
För att beräkna värdet av nästa tillstånd $s'$ , multiplicera för alla möjliga handlingar $a'$ från tillståndet $s'$ , handlingsvärdet $q(s', a')$ med sannolikheten att välja $a'$ i tillståndet $s'$ enligt nuvarande policy $\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ånds-aktionsparet $(s, a)$ under din nuvarande policy.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2

Fråga AI

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

Svep för att visa menyn

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 formulerats 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.

Tillståndsvärdefunktion

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

\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ärdesfunktion, expanderas höger sida av ekvationen och en rekursiv relation etableras:

\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 hitta värdet av ett tillstånd $s$ :

Beakta alla möjliga handlingar $a$ som kan utföras från detta tillstånd, var och en viktad efter sannolikheten att välja den handlingen enligt den aktuella policyn $\pi(a | s)$ ;
För varje handling $a$ , beakta alla möjliga nästa tillstånd $s'$ och belöningar $r$ , viktade efter deras sannolikhet $p(s', r | s, a)$ ;
För varje av dessa utfall, ta den omedelbara belöningen $r$ samt det diskonterade värdet av nästa tillstånd $\gamma v_\pi(s')$ .

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

Aktionsvärdesfunktion

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

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

Härledning av Bellmans ekvation för denna funktion är ganska lik den föregående:

\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 Bellmans ekvation för aktionsvärdesfunktionen.

Intuition

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

Beakta alla möjliga nästa tillstånd $s'$ och belöningar $r$ , viktade efter deras sannolikhet $p(s', r | s, a)$ ;
För varje av dessa utfall tar du den omedelbara belöningen $r$ du får plus det diskonterade värdet av nästa tillstånd;
För att beräkna värdet av nästa tillstånd $s'$ , multiplicera för alla möjliga handlingar $a'$ från tillståndet $s'$ , handlingsvärdet $q(s', a')$ med sannolikheten att välja $a'$ i tillståndet $s'$ enligt nuvarande policy $\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ånds-aktionsparet $(s, a)$ under din nuvarande policy.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 2