Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Oppiskele Bellman-yhtälöt | Dynaaminen Ohjelmointi
Johdatus Vahvistusoppimiseen

bookBellman-yhtälöt

Note
Määritelmä

Bellman-yhtälö on funktioyhtälö, joka määrittelee arvofunktion rekursiivisessa muodossa.

Selvennyksenä määritelmälle:

  • Funktioyhtälö on yhtälö, jonka ratkaisu on funktio. Bellman-yhtälön tapauksessa tämä ratkaisu on arvofunktio, jolle yhtälö on muodostettu;
  • Rekursiivinen muoto tarkoittaa, että nykytilan arvo ilmaistaan tulevien tilojen arvojen avulla.

Yhteenvetona, Bellman-yhtälön ratkaiseminen antaa halutun arvofunktion, ja tämän yhtälön johtaminen edellyttää rekursiivisen riippuvuuden tunnistamista nykyisten ja tulevien tilojen välillä.

Tilakohtainen arvofunktio

Muistutuksena tässä on tilan arvofunktion tiivis muoto:

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

Saadaksemme tämän arvofunktion Bellmanin yhtälön, laajennetaan yhtälön oikeaa puolta ja muodostetaan rekursiivinen yhteys:

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}

Tämän ketjun viimeinen yhtälö on Bellmanin yhtälö tilan arvofunktiolle.

Intuitio

Tilan ss arvon löytämiseksi:

  1. Otetaan huomioon kaikki mahdolliset toiminnot aa, joita voit tehdä tästä tilasta, jokainen painotettuna sillä todennäköisyydellä, jolla valitset kyseisen toiminnon nykyisen politiikkasi π(a∣s)\pi(a | s) mukaisesti;
  2. Jokaiselle toiminnolle aa otetaan huomioon kaikki mahdolliset seuraavat tilat s′s' ja palkkiot rr, painotettuna niiden todennäköisyydellä p(s′,r∣s,a)p(s', r | s, a);
  3. Kullekin näistä lopputuloksista lasketaan välitön palkkio rr sekä seuraavan tilan diskontattu arvo γvπ(s′)\gamma v_\pi(s').

Yhteenlaskemalla kaikki nämä mahdollisuudet saadaan tilan ss odotettu kokonaisarvo nykyisen politiikan mukaisesti.

Toimintoarvofunktio

Tässä on toimintoarvofunktio tiiviissä muodossa:

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]

Bellmanin yhtälön johtaminen tälle funktiolle on hyvin samankaltainen kuin edellisessä tapauksessa:

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}

Tämän ketjun viimeinen yhtälö on Bellmanin yhtälö toimintoarvofunktiolle.

Intuitio

Tilapari-toimintoparin (s,a)(s, a) arvon löytämiseksi:

  1. Otetaan huomioon kaikki mahdolliset seuraavat tilat s′s' ja palkkiot rr, painotettuna niiden todennäköisyydellä p(s′,r∣s,a)p(s', r | s, a);
  2. Jokaisessa näistä tapauksista lasketaan välitön palkkio rr sekä seuraavan tilan diskontattu arvo;
  3. Seuraavan tilan s′s' arvo lasketaan siten, että kaikille mahdollisille toiminnoille a′a' tilasta s′s' kerrotaan toimintoparin arvo q(s′,a′)q(s', a') todennäköisyydellä valita a′a' tilassa s′s' nykyisen politiikan π(a′∣s′)\pi(a' | s') mukaisesti. Lopuksi summataan kaikki yhteen saadakseen lopullisen arvon.

Yhteenlaskemalla kaikki nämä mahdollisuudet saadaan tilapari-toimintoparin (s,a)(s, a) odotettu kokonaisarvo nykyisen politiikan mukaisesti.

question mark

Mikä seuraavista kuvaa parhaiten Bellmanin yhtälön toimintaa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 2

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Awesome!

Completion rate improved to 2.7

bookBellman-yhtälöt

Pyyhkäise näyttääksesi valikon

Note
Määritelmä

Bellman-yhtälö on funktioyhtälö, joka määrittelee arvofunktion rekursiivisessa muodossa.

Selvennyksenä määritelmälle:

  • Funktioyhtälö on yhtälö, jonka ratkaisu on funktio. Bellman-yhtälön tapauksessa tämä ratkaisu on arvofunktio, jolle yhtälö on muodostettu;
  • Rekursiivinen muoto tarkoittaa, että nykytilan arvo ilmaistaan tulevien tilojen arvojen avulla.

Yhteenvetona, Bellman-yhtälön ratkaiseminen antaa halutun arvofunktion, ja tämän yhtälön johtaminen edellyttää rekursiivisen riippuvuuden tunnistamista nykyisten ja tulevien tilojen välillä.

Tilakohtainen arvofunktio

Muistutuksena tässä on tilan arvofunktion tiivis muoto:

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

Saadaksemme tämän arvofunktion Bellmanin yhtälön, laajennetaan yhtälön oikeaa puolta ja muodostetaan rekursiivinen yhteys:

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}

Tämän ketjun viimeinen yhtälö on Bellmanin yhtälö tilan arvofunktiolle.

Intuitio

Tilan ss arvon löytämiseksi:

  1. Otetaan huomioon kaikki mahdolliset toiminnot aa, joita voit tehdä tästä tilasta, jokainen painotettuna sillä todennäköisyydellä, jolla valitset kyseisen toiminnon nykyisen politiikkasi π(a∣s)\pi(a | s) mukaisesti;
  2. Jokaiselle toiminnolle aa otetaan huomioon kaikki mahdolliset seuraavat tilat s′s' ja palkkiot rr, painotettuna niiden todennäköisyydellä p(s′,r∣s,a)p(s', r | s, a);
  3. Kullekin näistä lopputuloksista lasketaan välitön palkkio rr sekä seuraavan tilan diskontattu arvo γvπ(s′)\gamma v_\pi(s').

Yhteenlaskemalla kaikki nämä mahdollisuudet saadaan tilan ss odotettu kokonaisarvo nykyisen politiikan mukaisesti.

Toimintoarvofunktio

Tässä on toimintoarvofunktio tiiviissä muodossa:

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]

Bellmanin yhtälön johtaminen tälle funktiolle on hyvin samankaltainen kuin edellisessä tapauksessa:

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}

Tämän ketjun viimeinen yhtälö on Bellmanin yhtälö toimintoarvofunktiolle.

Intuitio

Tilapari-toimintoparin (s,a)(s, a) arvon löytämiseksi:

  1. Otetaan huomioon kaikki mahdolliset seuraavat tilat s′s' ja palkkiot rr, painotettuna niiden todennäköisyydellä p(s′,r∣s,a)p(s', r | s, a);
  2. Jokaisessa näistä tapauksista lasketaan välitön palkkio rr sekä seuraavan tilan diskontattu arvo;
  3. Seuraavan tilan s′s' arvo lasketaan siten, että kaikille mahdollisille toiminnoille a′a' tilasta s′s' kerrotaan toimintoparin arvo q(s′,a′)q(s', a') todennäköisyydellä valita a′a' tilassa s′s' nykyisen politiikan π(a′∣s′)\pi(a' | s') mukaisesti. Lopuksi summataan kaikki yhteen saadakseen lopullisen arvon.

Yhteenlaskemalla kaikki nämä mahdollisuudet saadaan tilapari-toimintoparin (s,a)(s, a) odotettu kokonaisarvo nykyisen politiikan mukaisesti.

question mark

Mikä seuraavista kuvaa parhaiten Bellmanin yhtälön toimintaa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 2
some-alt