Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Oppiskele Optimaalisuusehdot | Dynaaminen Ohjelmointi
Vahvistusoppimisen Perusteet

bookOptimaalisuusehdot

Edellisessä luvussa opit Bellmanin yhtälöistä tilan arvo- ja tila-toimintoarvofunktioille. Nämä yhtälöt kuvaavat, kuinka tilan arvot voidaan määritellä rekursiivisesti muiden tilojen arvojen kautta, ja arvot riippuvat annetusta politiikasta. Kaikki politiikat eivät kuitenkaan ole yhtä tehokkaita. Arvofunktiot muodostavat itse asiassa osittaisjärjestyksen politiikoille, mikä voidaan esittää seuraavasti:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Politiikka π\pi on parempi tai yhtä hyvä kuin politiikka π′\pi', jos kaikissa mahdollisissa tiloissa politiikan π\pi odotettu tuotto ei ole pienempi kuin politiikan π′\pi' odotettu tuotto.

Note
Opiskele lisää

Osittaisjärjestys noudattaa tavanomaisia järjestyssääntöjä, mutta ei vaadi kaikkien parien vertailua. Tässä tapauksessa voimme järjestää kaksi politiikkaa vain, jos ne tuottavat samat tulokset tai toinen selvästi ylittää toisen. Kaikissa muissa tapauksissa politiikat jäävät vertaamattomiksi.

Optimaalinen politiikka

Note
Määritelmä

Jokaisessa MDP:ssä on olemassa vähintään yksi politiikka, joka on yhtä hyvä tai parempi kuin kaikki muut politiikat. Tätä politiikkaa kutsutaan optimaaliseksi politiikaksi π∗\pi_*. Vaikka optimaalisia politiikkoja voi olla useita, niitä kaikkia merkitään π∗\pi_*.

Miksi optimaalinen politiikka on aina olemassa?

Saatat miettiä, miksi optimaalinen politiikka aina on olemassa mille tahansa MDP:lle. Tämä on erinomainen kysymys, ja sen taustalla oleva intuitio on yllättävän yksinkertainen. Muista, että tilat MDP:ssä kuvaavat täysin ympäristön tilan. Tämä tarkoittaa, että jokainen tila on riippumaton muista: yhdessä tilassa valittu toiminto ei vaikuta muiden tilojen palkkioihin tai lopputuloksiin. Valitsemalla siis optimaalisen toiminnon jokaisessa tilassa erikseen, päädyt luonnollisesti kokonaisuudessaan parhaaseen toimintojen sarjaan koko prosessin aikana. Ja tämä optimaalisten toimintojen joukko jokaisessa tilassa muodostaa optimaalisen politiikan.

Lisäksi on aina olemassa vähintään yksi politiikka, joka on sekä optimaalinen että deterministinen. Jos jossakin tilassa ss kaksi toimintoa aa ja a′a' tuottavat saman odotetun tuoton, yhden niistä valitseminen ei vaikuta politiikan optimaalisuuteen. Soveltamalla tätä periaatetta jokaiseen tilaan politiikasta tulee deterministinen säilyttäen samalla sen optimaalisuuden.

Optimaaliset arvofunktiot

Optimaaliset politiikat jakavat samat arvofunktiot — tämä käy ilmi, kun tarkastellaan, miten politiikkoja verrataan. Tämä tarkoittaa, että optimaaliset politiikat jakavat sekä tilan arvon funktion että toiminnon arvon funktion.

Lisäksi optimaalisilla arvofunktioilla on omat Bellmanin yhtälönsä, jotka voidaan kirjoittaa viittaamatta mihinkään tiettyyn politiikkaan. Näitä yhtälöitä kutsutaan Bellmanin optimaalisen yhtälöiksi.

Optimaalinen tilan arvon funktio

Note
Määritelmä

Optimaalinen tilan arvon funktio V∗V_* (tai v∗v_*) kuvaa suurimman odotetun tuoton, joka on saavutettavissa tietyssä tilassa noudattamalla optimaalista politiikkaa.

Se voidaan määritellä matemaattisesti seuraavasti:

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

Bellmanin optimaalinen yhtälö tälle arvotoiminnolle voidaan johtaa seuraavasti:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuitio

Kuten jo tiedät, on aina olemassa vähintään yksi politiikka, joka on sekä optimaalinen että deterministinen. Tällainen politiikka valitsee jokaisessa tilassa johdonmukaisesti yhden tietyn toimenpiteen, joka maksimoi odotetun tuoton. Tämän vuoksi tämän optimaalisen toimenpiteen valitsemisen todennäköisyys on aina 1, ja minkä tahansa muun toimenpiteen valitsemisen todennäköisyys on 0. Tämän perusteella alkuperäinen Bellmanin yhtälö ei enää tarvitse summasymbolia. Koska tiedämme valitsevamme aina parhaan mahdollisen toimenpiteen, voimme yksinkertaisesti korvata summan ottamalla maksimin kaikista mahdollisista toimenpiteistä.

Optimaalinen toimintojen arvofunktio

Note
Määritelmä

Optimaalinen toimintojen arvofunktio Q∗Q_* (tai q∗q_*) kuvaa suurimman odotetun tuoton, joka voidaan saavuttaa suorittamalla tietty toiminto tietyssä tilassa ja noudattamalla optimaalista politiikkaa sen jälkeen.

Se voidaan määritellä matemaattisesti seuraavasti:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmanin optimaalisuusyhtälö tälle arvofunktiolle voidaan johtaa seuraavasti:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuitio

Samoin kuin tilan arvofunktiossa, summa voidaan korvata ottamalla maksimi kaikista mahdollisista toiminnoista.

question mark

Miksi optimaalinen politiikka on aina olemassa missä tahansa Markovin päätösprosessissa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 3

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

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

Suggested prompts:

Can you explain the difference between deterministic and stochastic policies?

How do Bellman optimality equations help in finding the optimal policy?

Can you provide an example of how to compute the optimal value function for a simple MDP?

Awesome!

Completion rate improved to 2.7

bookOptimaalisuusehdot

Pyyhkäise näyttääksesi valikon

Edellisessä luvussa opit Bellmanin yhtälöistä tilan arvo- ja tila-toimintoarvofunktioille. Nämä yhtälöt kuvaavat, kuinka tilan arvot voidaan määritellä rekursiivisesti muiden tilojen arvojen kautta, ja arvot riippuvat annetusta politiikasta. Kaikki politiikat eivät kuitenkaan ole yhtä tehokkaita. Arvofunktiot muodostavat itse asiassa osittaisjärjestyksen politiikoille, mikä voidaan esittää seuraavasti:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Politiikka π\pi on parempi tai yhtä hyvä kuin politiikka π′\pi', jos kaikissa mahdollisissa tiloissa politiikan π\pi odotettu tuotto ei ole pienempi kuin politiikan π′\pi' odotettu tuotto.

Note
Opiskele lisää

Osittaisjärjestys noudattaa tavanomaisia järjestyssääntöjä, mutta ei vaadi kaikkien parien vertailua. Tässä tapauksessa voimme järjestää kaksi politiikkaa vain, jos ne tuottavat samat tulokset tai toinen selvästi ylittää toisen. Kaikissa muissa tapauksissa politiikat jäävät vertaamattomiksi.

Optimaalinen politiikka

Note
Määritelmä

Jokaisessa MDP:ssä on olemassa vähintään yksi politiikka, joka on yhtä hyvä tai parempi kuin kaikki muut politiikat. Tätä politiikkaa kutsutaan optimaaliseksi politiikaksi π∗\pi_*. Vaikka optimaalisia politiikkoja voi olla useita, niitä kaikkia merkitään π∗\pi_*.

Miksi optimaalinen politiikka on aina olemassa?

Saatat miettiä, miksi optimaalinen politiikka aina on olemassa mille tahansa MDP:lle. Tämä on erinomainen kysymys, ja sen taustalla oleva intuitio on yllättävän yksinkertainen. Muista, että tilat MDP:ssä kuvaavat täysin ympäristön tilan. Tämä tarkoittaa, että jokainen tila on riippumaton muista: yhdessä tilassa valittu toiminto ei vaikuta muiden tilojen palkkioihin tai lopputuloksiin. Valitsemalla siis optimaalisen toiminnon jokaisessa tilassa erikseen, päädyt luonnollisesti kokonaisuudessaan parhaaseen toimintojen sarjaan koko prosessin aikana. Ja tämä optimaalisten toimintojen joukko jokaisessa tilassa muodostaa optimaalisen politiikan.

Lisäksi on aina olemassa vähintään yksi politiikka, joka on sekä optimaalinen että deterministinen. Jos jossakin tilassa ss kaksi toimintoa aa ja a′a' tuottavat saman odotetun tuoton, yhden niistä valitseminen ei vaikuta politiikan optimaalisuuteen. Soveltamalla tätä periaatetta jokaiseen tilaan politiikasta tulee deterministinen säilyttäen samalla sen optimaalisuuden.

Optimaaliset arvofunktiot

Optimaaliset politiikat jakavat samat arvofunktiot — tämä käy ilmi, kun tarkastellaan, miten politiikkoja verrataan. Tämä tarkoittaa, että optimaaliset politiikat jakavat sekä tilan arvon funktion että toiminnon arvon funktion.

Lisäksi optimaalisilla arvofunktioilla on omat Bellmanin yhtälönsä, jotka voidaan kirjoittaa viittaamatta mihinkään tiettyyn politiikkaan. Näitä yhtälöitä kutsutaan Bellmanin optimaalisen yhtälöiksi.

Optimaalinen tilan arvon funktio

Note
Määritelmä

Optimaalinen tilan arvon funktio V∗V_* (tai v∗v_*) kuvaa suurimman odotetun tuoton, joka on saavutettavissa tietyssä tilassa noudattamalla optimaalista politiikkaa.

Se voidaan määritellä matemaattisesti seuraavasti:

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

Bellmanin optimaalinen yhtälö tälle arvotoiminnolle voidaan johtaa seuraavasti:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuitio

Kuten jo tiedät, on aina olemassa vähintään yksi politiikka, joka on sekä optimaalinen että deterministinen. Tällainen politiikka valitsee jokaisessa tilassa johdonmukaisesti yhden tietyn toimenpiteen, joka maksimoi odotetun tuoton. Tämän vuoksi tämän optimaalisen toimenpiteen valitsemisen todennäköisyys on aina 1, ja minkä tahansa muun toimenpiteen valitsemisen todennäköisyys on 0. Tämän perusteella alkuperäinen Bellmanin yhtälö ei enää tarvitse summasymbolia. Koska tiedämme valitsevamme aina parhaan mahdollisen toimenpiteen, voimme yksinkertaisesti korvata summan ottamalla maksimin kaikista mahdollisista toimenpiteistä.

Optimaalinen toimintojen arvofunktio

Note
Määritelmä

Optimaalinen toimintojen arvofunktio Q∗Q_* (tai q∗q_*) kuvaa suurimman odotetun tuoton, joka voidaan saavuttaa suorittamalla tietty toiminto tietyssä tilassa ja noudattamalla optimaalista politiikkaa sen jälkeen.

Se voidaan määritellä matemaattisesti seuraavasti:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmanin optimaalisuusyhtälö tälle arvofunktiolle voidaan johtaa seuraavasti:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuitio

Samoin kuin tilan arvofunktiossa, summa voidaan korvata ottamalla maksimi kaikista mahdollisista toiminnoista.

question mark

Miksi optimaalinen politiikka on aina olemassa missä tahansa Markovin päätösprosessissa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 3
some-alt