Oppiskele Bellman-yhtälöt | Dynaaminen Ohjelmointi

Määritelmä

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

Määritelmän selvennykseksi:

Funktioyhtälö on yhtälö, jonka ratkaisu on funktio. Bellman-yhtälön tapauksessa tämä ratkaisu on arvofunktio, jota varten yhtälö on muodostettu;
Rekursiivinen muoto tarkoittaa, että nykyisen tilan 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 suhteen tunnistamista nykyisten ja tulevien tilojen välillä.

Tilaarvofunktio

Muistutuksena tässä on tilan arvon funktio tiiviissä muodossa:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Saadaksesi tämän arvon funktion Bellmanin yhtälön, laajennetaan yhtälön oikeaa puolta ja muodostetaan rekursiivinen yhteys:

\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 arvon funktiolle.

Intuitio

Tilan $s$ arvoa määritettäessä:

Otetaan huomioon kaikki mahdolliset toiminnot $a$ , joita voit tehdä tästä tilasta, painotettuna sillä todennäköisyydellä, jolla valitset kyseisen toiminnon nykyisen politiikkasi $\pi(a | s)$ mukaan;
Jokaiselle toiminnolle $a$ tarkastellaan kaikkia mahdollisia seuraavia tiloja $s'$ ja palkkioita $r$ , painotettuna niiden todennäköisyydellä $p(s', r | s, a)$ ;
Kullekin näistä lopputuloksista otetaan välitön palkkio $r$ sekä diskontattu seuraavan tilan arvo $\gamma v_\pi(s')$ .

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

Toimintoarvofunktio

Tässä on toimintoarvofunktio tiiviissä muodossa:

\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 varsin samanlainen kuin edellisessä tapauksessa:

\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)$ arvon löytämiseksi:

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

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

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 3. Luku 2

Kysy tekoälyä

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

Awesome!

Completion rate improved to 2.7

Pyyhkäise näyttääksesi valikon

Määritelmä

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

Määritelmän selvennykseksi:

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

Tilaarvofunktio

Muistutuksena tässä on tilan arvon funktio tiiviissä muodossa:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Saadaksesi tämän arvon funktion Bellmanin yhtälön, laajennetaan yhtälön oikeaa puolta ja muodostetaan rekursiivinen yhteys:

\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 arvon funktiolle.

Intuitio

Tilan $s$ arvoa määritettäessä:

Otetaan huomioon kaikki mahdolliset toiminnot $a$ , joita voit tehdä tästä tilasta, painotettuna sillä todennäköisyydellä, jolla valitset kyseisen toiminnon nykyisen politiikkasi $\pi(a | s)$ mukaan;
Jokaiselle toiminnolle $a$ tarkastellaan kaikkia mahdollisia seuraavia tiloja $s'$ ja palkkioita $r$ , painotettuna niiden todennäköisyydellä $p(s', r | s, a)$ ;
Kullekin näistä lopputuloksista otetaan välitön palkkio $r$ sekä diskontattu seuraavan tilan arvo $\gamma v_\pi(s')$ .

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

Toimintoarvofunktio

Tässä on toimintoarvofunktio tiiviissä muodossa:

\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 varsin samanlainen kuin edellisessä tapauksessa:

\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)$ arvon löytämiseksi:

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

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

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 3. Luku 2