Oppiskele Bellman-yhtälöt | Dynaaminen Ohjelmointi

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, 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 arvofunktion tiivis muoto:

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

Saadaksesi Bellmanin yhtälön tälle arvofunktiolle, 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 arvofunktiolle.

Intuitio

Tilan $s$ arvon määrittämiseksi:

Otetaan huomioon kaikki mahdolliset toiminnot $a$ , joita voit suorittaa 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)$ ;
Jokaisessa näistä tapauksista otetaan välitön palkkio $r$ sekä seuraavan tilan diskontattu 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 hyvin 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:

Tarkastellaan kaikkia mahdollisia seuraavia tiloja $s'$ ja palkkioita $r$ , painotettuna niiden todennäköisyydellä $p(s', r | s, a)$ ;
Jokaisessa näistä tapauksista otetaan välitön palkkio $r$ sekä diskontattu arvo seuraavasta tilasta;
Seuraavan tilan $s'$ arvo lasketaan siten, että kaikille mahdollisille toiminnoille $a'$ tilasta $s'$ kerrotaan toimintoparin arvo $q(s', a')$ todennäköisyydellä, jolla $a'$ valitaan 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.

Selvennyksenä määritelmälle:

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 arvofunktion tiivis muoto:

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

Saadaksesi Bellmanin yhtälön tälle arvofunktiolle, 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 arvofunktiolle.

Intuitio

Tilan $s$ arvon määrittämiseksi:

Otetaan huomioon kaikki mahdolliset toiminnot $a$ , joita voit suorittaa 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)$ ;
Jokaisessa näistä tapauksista otetaan välitön palkkio $r$ sekä seuraavan tilan diskontattu 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 hyvin 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:

Tarkastellaan kaikkia mahdollisia seuraavia tiloja $s'$ ja palkkioita $r$ , painotettuna niiden todennäköisyydellä $p(s', r | s, a)$ ;
Jokaisessa näistä tapauksista otetaan välitön palkkio $r$ sekä diskontattu arvo seuraavasta tilasta;
Seuraavan tilan $s'$ arvo lasketaan siten, että kaikille mahdollisille toiminnoille $a'$ tilasta $s'$ kerrotaan toimintoparin arvo $q(s', a')$ todennäköisyydellä, jolla $a'$ valitaan 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