Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Oppiskele Off-Policy Monte Carlo -ohjaus | Monte Carlo -Menetelmät
Johdatus Vahvistusoppimiseen
course content

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Off-Policy Monte Carlo -ohjaus

Siinä missä on-policy-menetelmät oppivat seuraamalla ja parantamalla samaa politiikkaa, off-policy-menetelmät tuovat mukanaan uuden näkökulman: ne oppivat yhdestä politiikasta (kohdepolitiikka) samalla kun ne seuraavat toista (käyttäytymispolitiikka). Tämä erottelu on tehokas — se mahdollistaa kohdepolitiikan arvioinnin tai parantamisen ilman, että sitä tarvitsee varsinaisesti noudattaa tiedonkeruun aikana.

Vertauskuva

Palataanpa jäätelökauppaan edellisestä luvusta. Sinä ja ystäväsi astutte sisään, ja jälleen tarjolla on kolme tuttua makua: suklaa, vanilja ja mansikka. Suklaa on oma suosikkisi, ja ensimmäinen ajatuksesi on tilata sitä. Mutta tämä kauppa on sinulle uusi, etkä ole aivan varma, onko suklaan valinta oikea. Onneksi ystäväsi on tunnettu jäätelön ystävä, joka on vieraillut lähes kaikissa kaupungin jäätelöbaareissa. Kysyt hänen mielipidettään. "Suklaa täällä on ihan ok," hän sanoo, "mutta usko pois — mansikka on poikkeuksellisen hyvää." Niinpä päätät hänen kokemuksensa perusteella jättää tavanomaisen valintasi väliin ja valita mansikan.

Tämä päätös — luottaa jonkun toisen kokemukseen oman valinnan ohjaamiseksi — on off-policy-menetelmien ydin. Pyrit parantamaan päätöksentekoasi käyttämällä dataa, joka on kerätty jonkun toisen käyttäytymisen perusteella. Kyseessä on yhä tutkiminen — mutta sitä ohjaa ulkoinen kokemus oman sijaan.

Tärkeyspainotus

Koska agentti seuraa käyttäytymispolitiikkaa jaksojen luomisen aikana, meidän täytyy huomioida ero, joka syntyy siitä, mitä käyttäytymispolitiikka tuottaa ja mitä kohdepolitiikka tuottaisi. Tässä kohtaa tärkeyspainotus astuu kuvaan.

Tärkeyspainotus (importance sampling) tarjoaa keinon säätää käyttäytymispolitiikan (behavior policy) tuottamia tuottoja niin, että ne ovat kelvollisia arvioita kohdepolitiikalle (target policy).

Tarkastellaan polkua, joka alkaa tietyssä tilassa StS_t ja seuraa tiettyä politiikkaa π\pi, kunnes episodi päättyy ajanhetkellä TT. Erityisesti havainnoimme:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Mikä on tämän polun todennäköisyys politiikan π\pi alla? Se riippuu sekä politiikan toimintatodennäköisyyksistä että ympäristön siirtymädynamiikasta:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Oletetaan nyt, että polku onkin itse asiassa tuotettu eri politiikalla — käyttäytymispolitiikalla bb. Jotta voimme käyttää tätä polkua odotusarvojen arvioimiseen kohdepolitiikalle π\pi, meidän täytyy huomioida, kuinka paljon todennäköisempi tai epätodennäköisempi tämä toimintojen sarja olisi ollut π\pi:n alla verrattuna bb:hen.

Tässä kohtaa tärkeyspainotussuhde tulee mukaan. Se määritellään polun suhteellisena todennäköisyytenä kahden politiikan alla:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

Lopulta siirtymätodennäköisyydet kumoutuivat, koska molemmat politiikat toimivat samassa ympäristössä, ja ρ\rho:n arvo riippuu ainoastaan politiikoista, ei ympäristöstä.

Miksi tämä on tärkeää

Suhde ρ\rho kertoo, miten käyttäytymispolitiikalla havaittu tuotto GtG_t painotetaan, jotta siitä tulee harhaton arvio siitä, millainen tuotto olisi ollut kohdepolitiikalla:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Toisin sanoen, vaikka data kerättiin politiikalla bb, voimme silti arvioida odotetut tuotot politiikalla π\pi — edellyttäen, että bb antaa nollasta poikkeavan todennäköisyyden jokaiselle toiminnolle, jonka π\pi voi valita (peittävyysoletus, assumption of coverage).

Käytännön näkökohdat

Tärkeyspainotuksen varianssi

Tärkeyspainotuksen (importance sampling) sisällyttäminen on käsitteellisesti suoraviivaista. Arvioitua toimintojen arvofunktiota q(s,a)q(s, a) säädetään painottamalla jokaista havaittua tuottoa vastaavalla tärkeyspainotuksen kertoimella. Yksinkertaisin muotoilu näyttää tältä:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

missä:

  • ρi(s,a)\rho_i(s, a) on tärkeyspainotuksen kerroin ii:nnessä trajektoriassa alkaen tilasta (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) on kyseisen trajektorian tuotto;
  • N(s,a)N(s, a) on tilan (s,a)(s, a) vierailukertojen määrä.

Tätä kutsutaan tavalliseksi tärkeyspainotukseksi (ordinary importance sampling). Se antaa harhattoman arvion q(s,a)q(s, a):sta, mutta voi kärsiä hyvin suuresta varianssista, erityisesti silloin kun käyttäytymis- ja kohdepolitiikat eroavat merkittävästi toisistaan.

Varianssiongelman lieventämiseksi voidaan käyttää vakaampaa vaihtoehtoa: painotettu tärkeyspainotus (weighted importance sampling). Tässä menetelmässä tärkeyspainot normalisoidaan, mikä vähentää suurten kertoimien vaikutusta ja johtaa vakaampaan oppimiseen:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(s, a)}

Tässä versiossa osoittaja on sama painotettu tuottojen summa, mutta nimittäjä on nyt tärkeyspainotusten summa yksinkertaisen laskennan sijaan.

Tämä tekee arviosta harhaisen, mutta harha pienenee näytteiden määrän kasvaessa. Käytännössä painotettu tärkeyspainotus on suositeltavaa sen huomattavasti pienemmän varianssin ja paremman numeerisen vakauden vuoksi.

Politiikat

Kuten on-policy-tapauksessa, käytetään ε\varepsilon-ahneita politiikkoja sekä kohdepolitiikalle π(as)\pi(a | s) että käyttäytymispolitiikalle b(as)b(a | s).

Ensisilmäyksellä vaikuttaa luonnolliselta tehdä kohdepolitiikasta täysin ahne — onhan lopullinen tavoitteemme ahne politiikka. Käytännössä tämä aiheuttaa kuitenkin merkittävän ongelman: jos jossain vaiheessa π(as)=0\pi(a | s) = 0 toiminnolle, jonka käyttäytymispolitiikka todella valitsi, tärkeyden painotussuhde ρ\rho muuttuu nollaksi ja jakson loppuosa jätetään käytännössä huomiotta.

Käyttämällä pientä ε\varepsilon-arvoa (esim. ε=0,01\varepsilon = 0{,}01) kohdepolitiikassa varmistetaan, että π(as)>0\pi(a | s) > 0 kaikille toiminnoille, joten ρ\rho ei koskaan romahda nollaan kesken jakson. Kun koulutus on valmis, opittu ε\varepsilon-ahne politiikka voidaan helposti muuntaa täysin ahneeksi. Kuten on-policy-oppimisessa, käyttäytymispolitiikassa tulisi käyttää laskevaa ε\varepsilon-arvoa, mutta tällä kertaa pääasiassa numeerisen vakauden vuoksi, sillä ρ\rho voi silti pudota nollaan kesken jakson, koska tietokoneet esittävät lukuja tietyllä tavalla.

Pseudokoodi

question mark

Mikä on tärkeyspainotuksen tarkoitus?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 4. Luku 6

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

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

course content

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Off-Policy Monte Carlo -ohjaus

Siinä missä on-policy-menetelmät oppivat seuraamalla ja parantamalla samaa politiikkaa, off-policy-menetelmät tuovat mukanaan uuden näkökulman: ne oppivat yhdestä politiikasta (kohdepolitiikka) samalla kun ne seuraavat toista (käyttäytymispolitiikka). Tämä erottelu on tehokas — se mahdollistaa kohdepolitiikan arvioinnin tai parantamisen ilman, että sitä tarvitsee varsinaisesti noudattaa tiedonkeruun aikana.

Vertauskuva

Palataanpa jäätelökauppaan edellisestä luvusta. Sinä ja ystäväsi astutte sisään, ja jälleen tarjolla on kolme tuttua makua: suklaa, vanilja ja mansikka. Suklaa on oma suosikkisi, ja ensimmäinen ajatuksesi on tilata sitä. Mutta tämä kauppa on sinulle uusi, etkä ole aivan varma, onko suklaan valinta oikea. Onneksi ystäväsi on tunnettu jäätelön ystävä, joka on vieraillut lähes kaikissa kaupungin jäätelöbaareissa. Kysyt hänen mielipidettään. "Suklaa täällä on ihan ok," hän sanoo, "mutta usko pois — mansikka on poikkeuksellisen hyvää." Niinpä päätät hänen kokemuksensa perusteella jättää tavanomaisen valintasi väliin ja valita mansikan.

Tämä päätös — luottaa jonkun toisen kokemukseen oman valinnan ohjaamiseksi — on off-policy-menetelmien ydin. Pyrit parantamaan päätöksentekoasi käyttämällä dataa, joka on kerätty jonkun toisen käyttäytymisen perusteella. Kyseessä on yhä tutkiminen — mutta sitä ohjaa ulkoinen kokemus oman sijaan.

Tärkeyspainotus

Koska agentti seuraa käyttäytymispolitiikkaa jaksojen luomisen aikana, meidän täytyy huomioida ero, joka syntyy siitä, mitä käyttäytymispolitiikka tuottaa ja mitä kohdepolitiikka tuottaisi. Tässä kohtaa tärkeyspainotus astuu kuvaan.

Tärkeyspainotus (importance sampling) tarjoaa keinon säätää käyttäytymispolitiikan (behavior policy) tuottamia tuottoja niin, että ne ovat kelvollisia arvioita kohdepolitiikalle (target policy).

Tarkastellaan polkua, joka alkaa tietyssä tilassa StS_t ja seuraa tiettyä politiikkaa π\pi, kunnes episodi päättyy ajanhetkellä TT. Erityisesti havainnoimme:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Mikä on tämän polun todennäköisyys politiikan π\pi alla? Se riippuu sekä politiikan toimintatodennäköisyyksistä että ympäristön siirtymädynamiikasta:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Oletetaan nyt, että polku onkin itse asiassa tuotettu eri politiikalla — käyttäytymispolitiikalla bb. Jotta voimme käyttää tätä polkua odotusarvojen arvioimiseen kohdepolitiikalle π\pi, meidän täytyy huomioida, kuinka paljon todennäköisempi tai epätodennäköisempi tämä toimintojen sarja olisi ollut π\pi:n alla verrattuna bb:hen.

Tässä kohtaa tärkeyspainotussuhde tulee mukaan. Se määritellään polun suhteellisena todennäköisyytenä kahden politiikan alla:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

Lopulta siirtymätodennäköisyydet kumoutuivat, koska molemmat politiikat toimivat samassa ympäristössä, ja ρ\rho:n arvo riippuu ainoastaan politiikoista, ei ympäristöstä.

Miksi tämä on tärkeää

Suhde ρ\rho kertoo, miten käyttäytymispolitiikalla havaittu tuotto GtG_t painotetaan, jotta siitä tulee harhaton arvio siitä, millainen tuotto olisi ollut kohdepolitiikalla:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Toisin sanoen, vaikka data kerättiin politiikalla bb, voimme silti arvioida odotetut tuotot politiikalla π\pi — edellyttäen, että bb antaa nollasta poikkeavan todennäköisyyden jokaiselle toiminnolle, jonka π\pi voi valita (peittävyysoletus, assumption of coverage).

Käytännön näkökohdat

Tärkeyspainotuksen varianssi

Tärkeyspainotuksen (importance sampling) sisällyttäminen on käsitteellisesti suoraviivaista. Arvioitua toimintojen arvofunktiota q(s,a)q(s, a) säädetään painottamalla jokaista havaittua tuottoa vastaavalla tärkeyspainotuksen kertoimella. Yksinkertaisin muotoilu näyttää tältä:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

missä:

  • ρi(s,a)\rho_i(s, a) on tärkeyspainotuksen kerroin ii:nnessä trajektoriassa alkaen tilasta (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) on kyseisen trajektorian tuotto;
  • N(s,a)N(s, a) on tilan (s,a)(s, a) vierailukertojen määrä.

Tätä kutsutaan tavalliseksi tärkeyspainotukseksi (ordinary importance sampling). Se antaa harhattoman arvion q(s,a)q(s, a):sta, mutta voi kärsiä hyvin suuresta varianssista, erityisesti silloin kun käyttäytymis- ja kohdepolitiikat eroavat merkittävästi toisistaan.

Varianssiongelman lieventämiseksi voidaan käyttää vakaampaa vaihtoehtoa: painotettu tärkeyspainotus (weighted importance sampling). Tässä menetelmässä tärkeyspainot normalisoidaan, mikä vähentää suurten kertoimien vaikutusta ja johtaa vakaampaan oppimiseen:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(s, a)}

Tässä versiossa osoittaja on sama painotettu tuottojen summa, mutta nimittäjä on nyt tärkeyspainotusten summa yksinkertaisen laskennan sijaan.

Tämä tekee arviosta harhaisen, mutta harha pienenee näytteiden määrän kasvaessa. Käytännössä painotettu tärkeyspainotus on suositeltavaa sen huomattavasti pienemmän varianssin ja paremman numeerisen vakauden vuoksi.

Politiikat

Kuten on-policy-tapauksessa, käytetään ε\varepsilon-ahneita politiikkoja sekä kohdepolitiikalle π(as)\pi(a | s) että käyttäytymispolitiikalle b(as)b(a | s).

Ensisilmäyksellä vaikuttaa luonnolliselta tehdä kohdepolitiikasta täysin ahne — onhan lopullinen tavoitteemme ahne politiikka. Käytännössä tämä aiheuttaa kuitenkin merkittävän ongelman: jos jossain vaiheessa π(as)=0\pi(a | s) = 0 toiminnolle, jonka käyttäytymispolitiikka todella valitsi, tärkeyden painotussuhde ρ\rho muuttuu nollaksi ja jakson loppuosa jätetään käytännössä huomiotta.

Käyttämällä pientä ε\varepsilon-arvoa (esim. ε=0,01\varepsilon = 0{,}01) kohdepolitiikassa varmistetaan, että π(as)>0\pi(a | s) > 0 kaikille toiminnoille, joten ρ\rho ei koskaan romahda nollaan kesken jakson. Kun koulutus on valmis, opittu ε\varepsilon-ahne politiikka voidaan helposti muuntaa täysin ahneeksi. Kuten on-policy-oppimisessa, käyttäytymispolitiikassa tulisi käyttää laskevaa ε\varepsilon-arvoa, mutta tällä kertaa pääasiassa numeerisen vakauden vuoksi, sillä ρ\rho voi silti pudota nollaan kesken jakson, koska tietokoneet esittävät lukuja tietyllä tavalla.

Pseudokoodi

question mark

Mikä on tärkeyspainotuksen tarkoitus?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 4. Luku 6
some-alt