Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Leer Bellman-Vergelijkingen | Dynamisch Programmeren
Introductie tot Reinforcement Learning

bookBellman-Vergelijkingen

Note
Definitie

Een Bellman-vergelijking is een functionele vergelijking die een waardefunctie definieert in recursieve vorm.

Ter verduidelijking van de definitie:

  • Een functionele vergelijking is een vergelijking waarvan de oplossing een functie is. Voor de Bellman-vergelijking is deze oplossing de waardefunctie waarvoor de vergelijking is opgesteld;
  • Een recursieve vorm betekent dat de waarde in de huidige toestand wordt uitgedrukt in termen van waarden in toekomstige toestanden.

Kortom, het oplossen van de Bellman-vergelijking levert de gewenste waardefunctie op, en het afleiden van deze vergelijking vereist het identificeren van een recursieve relatie tussen huidige en toekomstige toestanden.

Toestandswaardefunctie

Ter herinnering, hier is een toestandswaardefunctie in compacte vorm:

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

Om de Bellman-vergelijking voor deze waardefunctie te verkrijgen, breiden we de rechterkant van de vergelijking uit en stellen we een recursieve relatie op:

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}

De laatste vergelijking in deze reeks is een Bellman-vergelijking voor de toestandswaardefunctie.

Intuïtie

Om de waarde van een toestand ss te bepalen:

  1. Overweeg alle mogelijke acties aa die je vanuit deze toestand kunt nemen, elk gewogen naar de kans dat je die actie kiest onder je huidige beleid π(a∣s)\pi(a | s);
  2. Voor elke actie aa overweeg je alle mogelijke volgende toestanden s′s' en beloningen rr, gewogen naar hun waarschijnlijkheid p(s′,r∣s,a)p(s', r | s, a);
  3. Voor elk van deze uitkomsten neem je de directe beloning rr die je ontvangt plus de gedisconteerde waarde van de volgende toestand γvπ(s′)\gamma v_\pi(s').

Door al deze mogelijkheden bij elkaar op te tellen, verkrijg je de totale verwachte waarde van de toestand ss onder je huidige beleid.

Actiewaarde-functie

Hier is een actiewaarde-functie in compacte vorm:

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]

De afleiding van de Bellman-vergelijking voor deze functie is vergelijkbaar met de vorige:

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}

De laatste vergelijking in deze reeks is een Bellman-vergelijking voor de actiewaarde-functie.

Intuïtie

Om de waarde van een toestand-actie-paar (s,a)(s, a) te bepalen:

  1. Overweeg alle mogelijke volgende toestanden s′s' en beloningen rr, gewogen naar hun waarschijnlijkheid p(s′,r∣s,a)p(s', r | s, a);
  2. Voor elk van deze uitkomsten neem je de directe beloning rr die je ontvangt plus de gedisconteerde waarde van de volgende toestand;
  3. Om de waarde van de volgende toestand s′s' te berekenen, vermenigvuldig je voor alle acties a′a' mogelijk vanuit toestand s′s' de actie-waarde q(s′,a′)q(s', a') met de kans om a′a' te kiezen in toestand s′s' onder het huidige beleid π(a′∣s′\pi(a' | s'. Tel vervolgens alles op om de uiteindelijke waarde te verkrijgen.

Door al deze mogelijkheden bij elkaar op te tellen, krijg je de totale verwachte waarde van het toestand-actie-paar (s,a)(s, a) onder je huidige beleid.

question mark

Welke van de volgende beschrijvingen geeft het beste de functie van de Bellman-vergelijking weer?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 2

Vraag AI

expand

Vraag AI

ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Awesome!

Completion rate improved to 2.7

bookBellman-Vergelijkingen

Veeg om het menu te tonen

Note
Definitie

Een Bellman-vergelijking is een functionele vergelijking die een waardefunctie definieert in recursieve vorm.

Ter verduidelijking van de definitie:

  • Een functionele vergelijking is een vergelijking waarvan de oplossing een functie is. Voor de Bellman-vergelijking is deze oplossing de waardefunctie waarvoor de vergelijking is opgesteld;
  • Een recursieve vorm betekent dat de waarde in de huidige toestand wordt uitgedrukt in termen van waarden in toekomstige toestanden.

Kortom, het oplossen van de Bellman-vergelijking levert de gewenste waardefunctie op, en het afleiden van deze vergelijking vereist het identificeren van een recursieve relatie tussen huidige en toekomstige toestanden.

Toestandswaardefunctie

Ter herinnering, hier is een toestandswaardefunctie in compacte vorm:

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

Om de Bellman-vergelijking voor deze waardefunctie te verkrijgen, breiden we de rechterkant van de vergelijking uit en stellen we een recursieve relatie op:

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}

De laatste vergelijking in deze reeks is een Bellman-vergelijking voor de toestandswaardefunctie.

Intuïtie

Om de waarde van een toestand ss te bepalen:

  1. Overweeg alle mogelijke acties aa die je vanuit deze toestand kunt nemen, elk gewogen naar de kans dat je die actie kiest onder je huidige beleid π(a∣s)\pi(a | s);
  2. Voor elke actie aa overweeg je alle mogelijke volgende toestanden s′s' en beloningen rr, gewogen naar hun waarschijnlijkheid p(s′,r∣s,a)p(s', r | s, a);
  3. Voor elk van deze uitkomsten neem je de directe beloning rr die je ontvangt plus de gedisconteerde waarde van de volgende toestand γvπ(s′)\gamma v_\pi(s').

Door al deze mogelijkheden bij elkaar op te tellen, verkrijg je de totale verwachte waarde van de toestand ss onder je huidige beleid.

Actiewaarde-functie

Hier is een actiewaarde-functie in compacte vorm:

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]

De afleiding van de Bellman-vergelijking voor deze functie is vergelijkbaar met de vorige:

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}

De laatste vergelijking in deze reeks is een Bellman-vergelijking voor de actiewaarde-functie.

Intuïtie

Om de waarde van een toestand-actie-paar (s,a)(s, a) te bepalen:

  1. Overweeg alle mogelijke volgende toestanden s′s' en beloningen rr, gewogen naar hun waarschijnlijkheid p(s′,r∣s,a)p(s', r | s, a);
  2. Voor elk van deze uitkomsten neem je de directe beloning rr die je ontvangt plus de gedisconteerde waarde van de volgende toestand;
  3. Om de waarde van de volgende toestand s′s' te berekenen, vermenigvuldig je voor alle acties a′a' mogelijk vanuit toestand s′s' de actie-waarde q(s′,a′)q(s', a') met de kans om a′a' te kiezen in toestand s′s' onder het huidige beleid π(a′∣s′\pi(a' | s'. Tel vervolgens alles op om de uiteindelijke waarde te verkrijgen.

Door al deze mogelijkheden bij elkaar op te tellen, krijg je de totale verwachte waarde van het toestand-actie-paar (s,a)(s, a) onder je huidige beleid.

question mark

Welke van de volgende beschrijvingen geeft het beste de functie van de Bellman-vergelijking weer?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 2
some-alt