Optimalitas }orz}o altalanostas kockazat. erzekeny dontesi problemakban. Szakdolgozat. Gabor Zoltan. Temavezet}o: Dr

Optimalitas }orz}o altalanostas kockazat erzekeny dontesi problemakban Szakdolgozat Gabor Zoltan Temavezet}o: Dr. L}orincz Andras Bels}o konzulens: Dr. Dombi Jozsef

Tartalomjegyzek 1

Bevezetes

5

2

Autonom adaptv rendszerek

8

3

Kockazat erzekeny MDP-k

4

2.1 Kontroll strategia, kornyezet, dinamika : : : : : : : : : : : : : : : 8 2.2 Metadinamika es bels}o reprezentacio : : : : : : : : : : : : : : : : 10 2.3 Celorientalt autonom rendszerek : : : : : : : : : : : : : : : : : : : 12 3.1 3.2 3.3 3.4 3.5

Markov dontesi folyamatok : : : : : : Optimalis politikak : : : : : : : : : : Stacioner politikak iteratv ertekelese Moho es optimalis politikak : : : : : A Bellman egyenlet : : : : : : : : : :

Meger}osteses tanulas

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

: : : : :

4.1 Aszinkron Dinamikus Programozas : : : : : : : : : : : : : : : : : 4.1.1 Egy altalanos aszinkron konvergencia tetel : : : : : : : : : : : 4.1.2 Az Aszinkron Dinamikus Programozas algoritmus konvergencia ja : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2 Valos-idej}u Dinamikus Programozas : : : : : : : : : : : : : : : : : 4.3 Adaptv Aszinkron Dinamikus Programozas : : : : : : : : : : : : 4.4 A DC modell : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

14 14 15 16 19 20

21 22 22

23 26 29 30

5

 anostas Altal

33

6

Szamtogepes szimulaciok

41

5.1 Fogalmak : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 5.2 Meger}osteses tanulas kompakt allapot reprezentacio eseten : : : : 36 6.1 6.2 6.3

A kserleti rendszer es kornyezete : : : : : : : : : : : : : : : : : : 41 A llapot reprezentacio es egyestesi operator : : : : : : : : : : : : : 42 A kserletek modszertana : : : : : : : : : : : : : : : : : : : : : : : 43 1

6.4 Tanulasi eredmenyek : : : : : : : : : : : : : : : : : : : : : : : : : 45 6.5 Kserlet \ritka" vilagokban : : : : : : : : : : : : : : : : : : : : : : 46

7

O sszefoglalas

50

2

A brajegyzek 2.1 Autonom rendszer es kornyezete interakcioja : : : : : : : : : : : : : : 9 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9

Robot es kornyezete : : : : : : : : : : : : : A kserletek menete : : : : : : : : : : : : : : \Tesztvilag" : : : : : : : : : : : : : : : : : : Tipikus s}ur}u vilag : : : : : : : : : : : : : : : Futtatasi eredmenyek : : : : : : : : : : : : : A csomopontok szamanak id}obeli alakulasa : A gondolkodasi id}ok id}obeni alakulasa : : : Memoria-informacio hanyad arany : : : : : : A teljestmeny romlasa ritka vilagok eseten :

3

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

43 44 45 45 46 47 48 48 49

Tablazatok 4.1 Koltsegfuggveny alapu Reinforcement tanulo algoritmus : : : : : : : : 21 4.2 Adaptv aszinkron dinamikus programozasi algoritmus : : : : : : : : 29 4.3 Az adaptv aszinkron tanulasi algoritmus DC modellre kidolgozott implementacioja. : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31 5.1 Adaptv aszinkron algoritmus altalanostassal ellatott verzioja : : : : 38

4

1. Fejezet Bevezetes Az autonom rendszerek eptesenek vagya es problematika ja vegigkseri az emberiseget tortenelme folyaman (Golem, Frankenstein, Kempelen sakkautomata ja, Asimov robotikai torvenyei, stb.). Tudomasunk szerint konkret megvalostassal csak az utobbi id}okben probalkoztak, de szamos irodalmi m}uben (ld. fent) talalkozhatunk olyan robotokkal, amiket az ember kiszolgalasara kesztettek es az emberi tevekenysegek legszelesebb skala jat kepesek vegezni minden beavatkozas nelkul. Ezek a robotok sajat magukrol is gondoskodnak; hibasodas eseten megjavtjak magukat, alkatreszt cserelnek, olajoznak stb. A ma robotjai egyenl}ore meg csak meghatarozott \ved}o", vagyis baratsagos kornyezetben kepesek mozogni. Ennek oka, hogy a jelen programozastechnikai eszkozokkel tul bonyolult feladat egy robot felkesztese a \valos" kornyezet osszes lehetseges helyzetere. Meg ved}o kornyezetben is megeshet, hogy egy robot varatlan esemenyekkel talalkozik. Ilyenkor { ha az uzemeltet}onek szerencseje van { a robot leall. Elkepzelhet}o azonban olyan helyzet is, amelyben egy el}ore nem felterkepezett esemeny katasztrofat okoz. A kornyezet sokszn}usege altal tamasztott akadaly legy}ozesenek egyik lehetseges modszere, ha alkalmazkodo { tanulo robotot eptunk. Vegs}o soron az emberiseg { es egyaltalan az el}ovilag is { a tanulasi (alkalmazkodasi) kepessegenek koszonheti sikeret. Persze joggal vet}odik fel a robotok kontrollalhatosaganak kerdese is. Szamos olyan m}u fordul el}o a szep- es sci- irodalomban, amelyben a tul nagy onallosagra szert tett rendszerek egyszerre keszt}oik ellen fordulnak. Az ilyen esetek elkeru5

lese ketfelekepp kepzelhet}o el: Asimov m}uveiben olyan robotokat kepzel el, melyek velejeben beeptett fekek, serthetetlen torvenyek vannak. Tobb regenyeben erzekletesen mutatta be ennek a megkozeltesnek a torvenyek pontatlansagabol fakado hatranyait. U jabban { talan epp Asimov hatasara { az autonomiat kevesbe korlatozo modszereket vetettek fel, mint pl. a robotok tevekenysegenek meghatarozasa celok es motivaciok beeptesevel. Az Ember vedelme is megfogalmazhatonak t}unik ily modon. Ez a modszer kevesbe korlatozza a robotokat dontesi autonomia jukban es ezzel elkerulheti a merev torvenyek beepteseb}ol szarmazo problemakat. El kell azonban azt is mondani, hogy ennel a modszernel a garancia a robotok \szeld" voltara sokkal arnyaltabb { mely matematikai alltasokban rejlik. A dolgozatban ezen matematikai alltasokat vizsgaljuk { kulonos tekintettel a robotok dontesi algoritmusanak hatasossa tetelere. Specialisan a robotok fogalomalkoto kepessegevel valo felruhazasaval foglalkozunk. A dolgozatban { matematikai oldalrol { optimalis dontesi strategiakat vizsgalok az un. kockazat erzekeny Markov dontesi folyamatok kereten belul. A dolgozat kozponti kerdese, hogy hogyan lehet optimalis dontesi strategiakat kialaktani ha a dontesi modellt csak reszlegesen ismerjuk. A dolgozatban az un. koltsegfuggveny alapu algoritmusokkal foglalkozom. Az ilyen algoritmusok (dontesi fuggvenyek) gyakorlati alkalmazhatosagat korlatozza, hogy a koltsegfuggveny pontos reprezentacio jat kovetelik meg - a tarigeny az allapotok szamaval linearisan n}o. A dolgozatban bevezetek egy olyan csokkentett tarigeny}u reprezentaciot, melyb}ol az optimalis politika meg rekonstrualhato. Megadok egy algoritmust es egy szukseges feltetelt, mely mellett az algoritmus optimalitas }orz}o kompakt reprezentaciot keszt (5.2.8 Tetel). Ennek bizonytasa harom lepesben zajlik { a dolgozat is e szerint tagolodik. A 2. fejezetben az autonom adaptv rendszerek elveinek altalanos ismertetese talalhato, ezutan terek at a bizonytas mar emltett harom lepesere. A 3. fejezetben kidolgozom a kockazat erzekeny Markov dontesi folyamatok stacioner politikakra vonatkozo elmeletet. Az elmelet leglenyegesebb kovetkeztetese, hogy az un. optimalis koltsegfuggveny egyertelm}uen megadja a dontesi problema optimalis megoldasait es az optimalis koltsegfuggveny megkaphato a dontesi modellhez tartozo moho operator iteracio javal (3.5.1 Kovetkezmeny). A 4. fejezetben vizsgalom meg, hogy az elmelet 6

mikent terjeszthet}o ki arra az esetre, ha a dontesi modell nem ismert. El}okeszteskent bebizonytom, hogy az optimalis koltsegfuggvenyhez valo konvergenciat nem befolyasolja, ha az iteracio a kulonboz}o komponensekre nem feltetlenul egyidej}u { azaz az iteracio aszinkron (4.1.3 Tetel). Ezutan bebizonytom, hogy ha csak azokat az allapotokat frisstjuk, amelyeket a rendszer vegtelen sokszor megtapasztal es a rendszer mindig a pillanatnyi tudasa szerinti legjobb akciot valasztja, akkor az gy nyert algoritmus asszimptotikusan optimalis lesz (4.2.4 Tetel). Ezutan megmutatom, hogy ez az eredmeny kiterjeszthet}o arra az esetre, ha a dontesi modell nem ismert, hanem a tapasztalatok alapjan eptjuk (4.3.1 Tetel). Ehhez felteteleznunk kell, hogy a nyert tapasztalatok elegend}oek egy pontos modell feleptesere. Ezutan ismertetem a DC modellt, mely egy hely- es id}otakarekos implementacio ja a dontesi algoritmusnak. Az 5. fejezetben megadom az algoritmust, mely a koltsegfuggeny egy kompakt reprezentacio jat keszti el es bebizonytom, hogy ha a tanulashoz felhasznalt tapasztalatok jol reprezentaljak a dontesi problemat es az un. hamis altalanostasok optimista jelleg}uek, akkor az algoritmus altal kesztett koltsegfuggveny asszimptotikusan az optimalis koltsegfuggvennyel fog megegyezni (5.2.8 Tetel). Szinten kiterek az algoritmus gyors implementacio janak lehet}osegere { mely a DC modell kib}ovteset jelenti. Az utolso fejezet (6 fejezet) a kserletek bemutatasara szolgal. A kserletekhez letrehoztam egy altalanos celu szimulacios szoftvert, mely ket reszb}ol all: a kornyezet (dontesi modell) szimulacio jabol, valamint a donteshozo es tanulo algoritmus implementacio jabol. A kserletekkel bemutatom, hogy a valasztott dontesi problema es altalanostas operator eseten a kompakt reprezentaciot keszt}o algoritmus mind a teljestmeny, mind a tarigeny, mind a valos idej}useg teren jobbnak bizonyul, mint az egyszer}u koltsegfuggveny tablat keszt}o algoritmus. A c kserletekhez szukseges szoftvert egy IBM PC{486{os gepen fejlesztettem Linux c C++ 6.3 fordtoval. A operacios rendszerben, ANSI C++ 3.0 nyelven es GNU c fejleszt}oi csomagot hasznalszukseges adatstrukturak megvalostasara a LEDA tam.

7

2. Fejezet Autonom adaptv rendszerek Ebben a fejezetben betekinthetunk az autonom rendszerek altalanos elmeletebe. A bemutatando modell egyfajta keretet ad az indulashoz. Az elmelet kidolgozasakor f}oleg a mesterseges rendszerek vizsgalatara hagyatkozunk, de gyelembe vesszuk a biologia, pszihologia, es etologia idevago eredmenyeit is.

2.1 Kontroll strategia, kornyezet, dinamika Tekintsunk egy, a kornyezetevel allando interakcioban allo rendszert. Az interakcio soran a rendszer a kornyezete allapotat erzekel}oin keresztul kerdezheti le es a kornyezetet aktuatorai segtsegevel befolyasolhatja. Legyen X a rendszer osszes lehetseges szenzoros allapotainak halmaza, es A a rendszer aktuatorai lehetseges allapotainak halmaza. Tegyuk fel egyenl}ore, hogy a rendszer egy rogztet stacioner strategiat kovet. stacioner strategia alatt egy olyan  : X ! A lekepezest ertunk, mely azt adja meg, hogy a rendszer hogyan valtozik: x 2 X allapot bekovetkezese a rendszerben az a = (x) akciot valtja ki. Az aktuatorok bealltasa hatassal van a rendszer kornyezetere es a kornyezeten keresztul befolyasolja a rendszer jov}obeni allapotait. Tehat a  kontroll strategia lezarhato egy ^ : X ! P (X ) lekepezesse. Ahhoz, hogy ezt a lezarast de nialni tudjuk jeloljuk a kornyezet osszes lehetseges allapotanak halmazat E{vel, a kornyezet megvaltozasat egy adott a aktuator hatasara lero fuggvenyt 1

1

P (X ) az X halmaz hatvanyhalmaza, vagyis X reszhalmazainak halmaza.

8

pedig  : E  A ! E {vel. Jeloljuk tovabba a kornyezet erzekeleset lero fuggvenyt  : E ! X {vel. A  kontroll strategia lezartja alatt az (E;  ) kornyezetben a

^(x) = (x; (x)) lekepezest ertjuk, ahol  : X  A ! P (X ) lekepezes adott a akcio es x rendszerallapotra megadja az akcio lehetseges kimeneteleit:

(x; a) = f( (e; a))je 2 E; x = (e)g lathato, hogy a ^(x) halmaz merete az

S (x) = fe 2 E : x = (e)g halmaz meretenel csak kisebb lehet, mivel  lekepezes. A rendszer es kornyezete interakciojat a 2.1 abra abrazolja. Ha az S (x) halmaznak minden x-re egy eleme van, azaz az erzekeles pontos, akkor tetsz}oleges  strategia ^(x) lezartja fuggveny: vagyis minden akcio hatasa kiszamthato. Minel nagyobb az S (x) halmaz merete, annal bizonytalanabb egy{egy akcio kimenetele. Az fS (x)gx2X halmazrendszer a rendszernek azt a kepesseget jellemzi, hogy milyen pontossaggal tudja megallaptani szenzorai segtsegevel kornyezete allapotat.

2.1. abra: Autonom rendszer es kornyezete interakcioja Az el}oz}oek ertelmeben a , stacioner kontroll strategiat alkalmazo rendszer dinamikajat a kovetkez}o dierencialis tartalmazassalrhatjuk le.

x 2 ^(x); +

9

ahol x a rendszer \kovetkez}o" pillanatbeli allapotat jeloli. A rendszer kornyezetevel valo interakciojat szinten dierencialis tartalmazassal rhatjuk le: +

x 2 (x; a); +

ahol a az x allapotu rendszer valamelyik akcio ja. Egy, a kornyezetevel allando interakcioban allo rendszer tehat m}ukodesre zartnak tekinthet}o, hisz a rendszer barmely cselekedetenek eredmenye lerhato maganak a rendszer allapotanak a megvaltozasaval. Ez a zartsag nem a zikai ertelemben vett zartsagot jelenti: zikai ertelemben a rendszer igenis nyitott, hiszen allandoan befolyasolja kornyezetet es az is befolyassal br az }o allapotara.

2.2 Metadinamika es bels}o reprezentacio Az autonom rendszerek de nialo tulajdonsaga az, hogy m}ukodesuk a rendszer allapotanak egy bizonyos tartomanyon belul valo tartasara iranyul. Ezt a tulelesre valo torekvesnek szokas nevezni es a kovetkez}okepp fogalmazhato meg: Legyen K a rendszer X allapotainak egy reszhalmaza: a rendszer tulelesi tartomanya. A cel az, hogy a rendszert ezen tulelesi tartomanyon belul tartsuk, vagyis ahhoz, hogy a rendszer fennmaradjon olyan  kontroll strategiat kell alkalmaznia amelyre igaz, hogy ^(x)  K , minden egyes x allapotra. Hogyan talal ilyen kontroll strategiat a rendszer? A rendszer \elete" soran tapasztalatokat szerez a kornyezeter}ol. A m}ukodese annal bizonytalanabb, minel nagyobb a bizonytalansag kornyezete allapotanak megteleseben, azaz minel nagyobb az S (x). Ezt a bizonytalansagot kikuszobolend}o, a rendszernek olyan hasznos hipoteziseket kell gyartania a kornyezeter}ol, amelyek segtsegevel kepes megmagyarazni a \tortenesek" okait. A jo hipotezisek felalltasanak kepesseget nevezzuk abdukcios kepessegnek. Az abdukcio bizonyos ertelemben az indukcio vagy modus ponens (MP) fordtottja, amikor egy q alltas es egy p ! q szabaly fennallasa eseten, a p alltast, mint a q alltas okat szamtasba vesszuk. Az autonom rendszerek a kornyezetuk allapottarol es szabalyairol hipoteziseket gyartanak, hogy elettartalmukat kitoljak. A jo hipotezisek segtsegevel a kontroll strategia javthato. A kontroll strategia modostasat vegz}o szabalyossagok osszesseget meta10

dinamikanak nevezzuk. A rendszer metadinamika ja egy:

M : X  AX ! AX fuggvennyelrhato le. Ha a rendszer allapota x 2 X es pillanatnyi kontroll strategia ja , akkor az M metadinamika segtsegevel a rendszer a kovetkez}o id}opillanatban mar a  = M (x; ) +

kontroll strategiat fogja hasznalni. Az autonom rendszer matadinamika jat altalaban adataik es adatstrukturaik megvaltozasaval rjuk le. A rendszer a kornyezetere vonatkozo tapasztalatait tudasbazisba gy}ujti, melyet a kornyezet vagy \kulvilag" bels}o reprezentaciojanak nevezzunk. A \bels}o" szo utal arra, hogy itt csak a rendszer bels}o allapotairol beszelhetunk, mivel a rendszer a kornyezeteb}ol csak ezt \latja". Jeloljuk B {vel a rendszer bels}o reprezentacio janak lehetseges allapotait. Ekkor a rendszer kontroll strategia ja mint egy  : X  B ! A lekepezesrhato le:

 = (b; x); ahol b 2 B egy bels}o reprezentacio. A rendszer M metadinamikaja a rendszer pillanatnyi b bels}o reprezentaciojat valtoztatja meg:

b = M (x; b); +

ahol M : X  B ! B lekepezes. A rendszer m}ukodeset tehat a kovetkez}okepp lehetne lerni: (a; b ) 2 F (x; b); +

ahol F =   M , azaz F (x; b) = ((x; b); M (x; b)). A bels}o reprezentacioval rendelkez}o rendszereknel harom reszegyseget kulonboztethetunk meg: erzekel}o resz, vegrehajto resz es bels}o reprezentacio.

 Az erzekel}o resz a kornyezet (kulvilag) es a rendszer (belvilag) allapotat erzekeli, es tovabbtja inputkent a rendszernek. Azzal, hogy megengedjuk, hogy a rendszer a sajat allapotat is erzekelje, jelent}osen novelhetjuk tanulasi lehet}osegeit. Az egyes erzekel}o egysegeket, fuggetlenul attol, hogy bels}o, vagy kuls}o 11

informaciokat kozvettenek, szenzoroknak nevezzuk. A szenzoros informacio lehet el}ofeldolgozott informacio is, de fontos, hogy a rendszer tobbi reszet}ol fuggetlenul m}ukodjon.

 A vegrehajto resz a rendszer cselekveseinek megvalosto egysege. A ltalaban

oszetett, tobb manipulatorbol allhat. A vegrehajto resz vezerlese az operatorok segtsegevel tortenik. Az operatorok bealltasaval lehet a manipulatorokat, es azok segtsegevel pedig a kornyezetet allapotat valtoztatni.

 A bels}o reprezentacioban tarolja el a rendszer a tapasztalatait. Ez az a resz,

amelyben az egyes rendszerek legtobbszor kulonboznek. A bels}o reprezentacio tarolhatja a rendszer hosszutavu terveit, otleteit, celjait, stb.

2.3 Celorientalt autonom rendszerek A ltalanos celu autonom rendszer modelljenek tervezesenel nem szorthatjuk meg a modellt egy rogztett metadinamika megadasara. Ehelyett a metadinamika altalanos alapelveit kell rogzteni. Ha a rendszert celokkal latjuk el, akkor gy lehet}osegunk nylik a metadinamika altalanos alapelvei kidolgozasara. Egy ilyen metadinamika eseten egy konkret rendszer elkesztesehez csak annak celjait kell formaba ontenunk. A metadinamika fog gondoskodni a celok elereset biztosto algoritmusok kialakulasarol. Sokszor egy rendszernek tobb celja is lehet, melyek kozott ellentetelesek is el}ofordulhatnak. A cel-kon iktusok feloldasat proritasok bevezetesevel, vagy fuzzy ertekeleselmeleti modszerekkel oldhatjuk meg. A celok megadasanak egy igen egyszer}u modszere a kovetkez}o: jeloljuk a rendszer lehetseges celjainak halmazat C {vel, s vegyunk egyetlen c 2 C celt. Minden celt ugy hatarozunk meg, hogy \megmondjuk", hogy melyek azok az allapotok, melyekben a cel teljesul. A c szimbolum tehat azokat az allapotokat jeloli, amelyekben cel teljesul: azaz c  X . Egy adott cel \beprogramozasa" egyszer}ubb, mint a cel elesere iranyulo cselekvesek beprogramozasa lenne. Peldaul egyetlen szenzor gyelese is eleg lehet: ha van \ehsegerzet" szenzor a rendszerben (mely akkor jelez, ha az ehsegerzet fennall), akkor elegend}o az ehsegerzet szenzor gyelesenek oroktese az \ehseg megszuntetese" cel lerasahoz, 12

a tobbi szenzor jelzeseit egyszer}uen gyelmen kvul kell hagyni.

13

3. Fejezet Kockazat erzekeny MDP-k A tovabbiakban specialis, un. Markov dinamikaju kornyezeteket tekintunk csak es a metadinamikat is fokozatosan megszortjuk.

3.1 Markov dontesi folyamatok A diszkret Markov-folyamatok [2] a sztochasztikus folyamatok egy reszet kepezik [10] es bizonyos megszortasokkal ugyan, de jol modellezik az el}oz}oekben bevezetett adaptv rendszereket. Legyenek X ; X ; X ; . . . diszkret valoszn}usegi valtozok, ahol mindegyik Xt-edik valtozo egy X megszamlalhato halmazbol veszi fel az erteket. Az X halmazt az allapotok halmazanak nevezzuk. Az Xt valojaban a rendszer t id}obeli allapotat jeloli. Ezentul jeloljuk X elemeit x; y; z; x ; x ; . . . { vel. 0

1

2

0

1

3.1.1 Defincio Az X ; X ; X ; . . . diszkret valoszn}usegi valtozok Markov-lancot 0

1

2

(diszkret Markov-folyamatot) alkotnak, ha a kovetkez}o teljesul tetsz}oleges x ; x ; . . . xn X -beli allapotokra, es tetsz}oleges t < . . . < tn id}opillanatokra: 0

1

0

P (Xtn = xnjXtn 1 = xn ; . . . ; Xt1 = x ; Xt0 = x ) = P (Xtn = xn jXtn 1 = xn ): 1

1

0

1

Ez azt jelenti, hogy a rendszer korabbi allapotai a kes}obbi allapotokra csak a jelen allapoton keresztul gyakorolnak befolyast. Legyenek adottak az X allapotok halmaza, A akciok veges halmaza, es Pxy (a) atmenetvaloszn}usegek, ahol x; y 2 X es a 2 A. Az atmenetvaloszn}usegeket ugy kell ertelmezni, hogy ha az x allapotban vagyunk es vegrehajtjuk az a akciot, akkor Pxy (a) valoszn}useggel jutunk az y 14

allapotba. Rendeljunk most minden (x; a; y) allapot-akcio-allapot harmashoz egy koltseget, amelyet c(x; a; y)-val jelolunk. A c(x; a; y) koltsegr}ol feltesszuk, hogy yban egyenletesen korlatos, vagyis letezik olyan M , hogy c(x; a; y) < M , all minden x-re es a-ra. Ha a rendszer az x allapotban van es az a akciot valasztja, a kovetkez}o dolgok tortennek:

 az y allapot a Pxy (a) atmenetvaloszn}usegeknek megfelel}oen valasztodik,  fellep egy c(x; a; y) koltseg. A fent lert folyamatot Markov dontesi folyamatnak nevezzuk. Az akciok kivalasztasaban a rendszer vagy donteshozo valamilyen politikat kovet. Ez valo jaban egy fuggveny, amelynek ertekkeszlete az akciok halmaza. A politika altal valasztott akcio fugghet peldaul a folyamat el}oz}o allapotaitol, vagy lehet sztochasztikus abban az ertelemben, hogy a soron kovetkez}o akcio csak valamilyen eloszlas ertelmeig meghatarozott. Az osszes politikak osztalyanak egy fontos reszhalmazat kepezik a determinisztikus stacioner politikak. Ezekre az jellemz}o, hogy csak a rendszer aktualis allapotatol fuggnek:

3.1.2 Defincio  stacioner politika, ha  2 fu : X ! Ag Ha  egy stacioner politika, akkor konnyen lathato, hogy a rendszer allapotai, azaz az fXt; t = 0; 1; 2; . . .g valoszn}usegi valtozok sorozata Markov-lancot alkot, espedig

P (Xt = yjXt = x) = Pxy ((x)) +1

minden t-re. Markov dontesi problemat egy Markov dontesi folyamaton de nialhatunk: a problema egy adott koltsegfuggveny es optimalizalasi kriterium szerinti optimalis politika kereseset jelenti.

3.2 Optimalis politikak Jelolje ct a t-edik id}opillanatban fellep}o koltseget. Tegyuk fel, hogy a donteshozo rogztett  politikat hajt vegre es legyen S  (x ) = P1t tct, ahol 0 < < 1. S  (x ) egy korlatos valoszn}usegi valtozo, mely a politikahoz tartozo lecsengetett 0

0

15

=0

osszkoltseget adja meg. A , az un. lecsengetesi allando biztostja a korlatossagot, es azt, hogy a jov}obeni koltsegek kevesbe szamtsanak az osszkoltsegben. Mivel S  (x ) valoszn}usegi valtozo, gy nem hasonlthatok ossze altala a kulonboz}o politikak. Az S  veletlen jelleget eltuntethetjuk, ha vesszuk a varhato erteket: 0

v (x ) = E [S (x )]: 0

0

Itt E a  stacioner politika altal generalt, az allapot-akcio trajektoriakon ertelmezett eloszlas szerint varhato erteket jeloli [10]. A jelen dolgozatban azonban az  oltseg (Maximal Total Discounted Cost) fuggvenyt un. Maximalis Lecsengetett Osszk hasznaljuk [5]: v (x ) = esssup S (x);  0

ahol esssup a  altal az allapot-akcio trajektoriakon generalt mertek tarto jan vett szupremumot jeloli. Az ilyen koltsegfuggvennyel ellatott Markov dontesi folyamatokat hvjuk kockazat erzekeny Markov dontesi folyamatoknak [5], a v (x) fuggvenyt pedig a  politika ertekelesenek nevezzuk. Ezek utan mar de nialhatjuk, hogy mit ertunk optimalis politika alatt.

3.2.1 Defincio Azt mondjuk, hogy a  politika optimalis, ha: v (x) = v(x); ahol

v(x) = inf  v (x);

x 2 X; x2X

jeloli az un. optimalis koltsegfuggvenyt.

3.3 Stacioner politikak iteratv ertekelese A kovetkez}o reszekben megmutatjuk, hogy a kockazat erzekeny szekvencialis dontesi problemakban korlatos koltsegek mellett mindig letezik optimalis politika. Legyen adott (X; A; T; c) negyes, ahol X az allapotok veges halmaza, A az akciok veges halmaza, T : X  A ! P (X ) atmenet fuggveny, ahol P (X ) az X halmaz 16

hatvanyhalmaza , es c(x; a; y) 2 R atmenetkoltsegek (x; y 2 X , a 2 A). Ebben a fejezetben csak stacioner politikakkal foglalkozunk. Legyen B (X ) az X -en ertelmezett valos, korlatos fuggvenyek halmaza. Legyen  egy stacioner politika es vezessuk be a kovetkez}o, B (X )-en ertelmezett operatort: 1

(T v)(x) = y2Tmax (c(x; (x); y) + v(y)) : x; x (

( ))

(3:1)

Jeloljuk tetsz}oleges u 2 B (X ) szupremum normajat jjujj-val:

kuk = sup ju(x)j: x2X

(3:2)

3.3.1 Lemma A T operator kontrakcio, index-szel, vagyis barmely ket u; v 2 B (X ) fuggvenyre all, hogy kT u T vk  ku vk. Bizonytas. Legyen u; v 2 B (X ) rogztett. Ahhoz, hogy jjTu T v jj-t becsuljuk, becsuljuk meg el}oszor adott x 2 X -re a (T u)(x) (T v)(x) kulonbseget:

((T u)(x) (T v)(x)) =

max (c(x; (x); y) + u(y)) max (c(x; (x); y) + v(y)) y2T x; x = c(x; (x); y) + u(y) max (c(x; (x); y) + v(y)); y2T x; x y2T (x;(x)) (

( ))

(

( ))

ahol y olyan, hogy:

c(x; (x); y) + u(y) = y2Tmax (c(x; (x); y) + u(y)): x; x (

( ))

Egyszer}uen adodik, hogy: ((T u)(x) (T v)(x))  (u(y) v(y))  sup (u(y) v(y)) y2X

 ku vk Mivel a fenti egyenl}otlenseg minden x 2 X {re all, ezert sup ((T u)(x) (T v)(x))  ku vk: x2X 1

T (x; a) tulajdonkeppen az el}oz}o fejezetbeli Px0 (a) atmenet eloszlas tartojat jeloli: T (x; a) =

fy 2 X jPxy (a) > 0g.

17

Megcserelve u es v szerepet lathatjuk, hogy sup ((T v)(x) (T u)(x))  ku vk

x2X

is all. A fenti ket egyenl}otlenseg felhasznalasaval kapjuk, hogy sup j(T u)(x) (T v)(x)j  ku vk;

x2X

vagyis

kT u T vk  ku vk; 2

ami bizonytando volt.

3.3.2 A lltas Ha  stacioner politika, akkor v (x) = limn!1 (Tnv)(x) . 2

Bizonytas. Mivel T kontrakcio, gy a kontrakcios tetel miatt tudjuk, hogy Tnv a T operator egyetlen xpontjahoz konvergal. Ezert eleg megmutatni, hogy tetsz}oleges stacioner politika ertekel}o fuggvenye kielegti a

v (x) = y2Tmax (c(x; (x); y) + v (y)) x; x (

( ))

xpont egyenletet. Jeloljuk c (x; y)-val c(x; (x); y)-t es a P1t tc (xt; xt ) osszeget c (x ; x ; x ; . . .)-val. Ekkor v (x ) de ncio szerint epp +1

=0

0

1

2

0

sup

x1 2T (x0 );x2 2T (x1 );...

c (x ; x ; x ; . . .); 0

1

2

ahol T (x) = T (x; (x)). Rogztsunk egy  > 0 szamot. Ehhez van olyan x; x; . . . ; xt ; . . . lehetseges -trajektoria (x 2 T (x ) es xt 2 T (xt )), hogy 1

0

1

2

+1

v (x )  < c(x ; x; x; . . . ; xt ; . . .): 0

0

1

2

Nyilvan

c(x ; x; x; . . . ; xt ; . . .)  0

1

2

 = = 2

c(x ; x; x ; . . . ; xt; . . .) sup c(x ; x ; x ; . . . ; xt; . . .))

sup

x2 2T (x1 );x3 2T (x2 );...

max (

0

1

x1 2T (x0 ) x2 2T (x1 );x32T (x2 );...

2

0

1

2

1 X t c (x ; x ))

0 1  t+1 t+2 ( ) 1 0 x2 2T (x1 );x32T (x2 );... t=0 1 X max ( c ( x sup

tc (xt+1; xt+2)):  0 ; x1 ) + x1 2T (x0 ) x2 2T (x1 );x3 2T (x2 );... t=0

max ( x 2T x

sup

T nv = TT . . . Tv, ahol T n-szer szerepel.

18

c (x ; x ) +

Vegyuk eszre, hogy 1 X

tc (xt+1; xt+2) x2 2T (x1 );x3 2T (x2 );... t=0

sup

eppen v (x ), gy ezt visszahelyettestve kapjuk, hogy 1

v (x )  < x12max (c (x ; x ) + v (x )) = (T v )(x ): T x0  0

(

0

)

1

1

0

Mivel  tetsz}oleges volt gy kapjuk, hogy v  T v . Masreszt sup

x1 2T (x0 );x2 2T (x1 );...

c (x ; x ; x ; . . .)  x12max ( sup T x0 0

1

2

(

)

x2 2T (x1 );...

c (x ; x ; x ; . . .)) = (T v )(x ); 0

1

2

es gy valoban T v = v .

0

2

3.4 Moho es optimalis politikak Ebben a fejezetben megmutatjuk, hogy a fenti dontesi folyamatban mindig leteznek optimalis politikak.

3.4.1 Defincio Azt mondjuk, hogy a  politika moho a v koltsegfuggvenyre nezve,

ha

(x) 2 Argmin y2max (c(x; a; y) + v(y)) : T x;a a2A

3

(

)

 tas Ha  moho v -ra, akkor  optimalis is. 3.4.2 All

Bizonytas. Emlekeztet}oul a v  optimalis koltsegfuggveny de ncioja

v(x) = inf  v (x);

x 2 X:

Az egyszer}useg kedveert jeloljuk G-vel azt a B (X ) ! B (X ) operatort, amely a v 2 B (X ) fuggvenyt a (Gv)(x) = min max (c(x; a; y) + v(y)) a2A y2T x;a (

)

(3:3)

fuggvenybe kepezi. Legyen  moho v-ra nezve. Nyilvanvalo, hogy T v = Gv (T , G es a mohosag de nciojabol). Belatjuk, hogy Gv  v, es ebb}ol mar kovetkezik 3

Argmina2A v(a) de ncio szerint azon a 2 A elemek halmaza, melyen v felveszi a minimumat.

19

is, hogy  optimalis. Ugyanis ebben az esetben T v  v, melyb}ol mindket oldalra alkalmazva T -t kapjuk, hogy T v  T v es ez kisebb vagy egyenl}o mint v. Ezt az iteracios eljarast folytatva kapjuk, hogy minden n termeszetes szamra Tnv  v. Ha n tart a vegtelenbe, akkor a bal oldal v -hez konvergal, tehat v  v, tehat v optimalis. Meg kell meg mutatni, hogy Gv  v. Legyen  egy tetsz}oleges politika. Ekkor Gv  T v (ez nem csak a v pontban all) es T v  T v =  v (ez utobbi egyenl}oseget bizonytottuk be a (3.3.2) alltasban). Osszeolvasva az egyenl}otlensegeket kapjuk, hogy Gv  v minden  -re. Veve  -re az in mumot, kapjuk, hogy Gv  v. 2 2

3.5 A Bellman egyenlet 3.5.1 Kovetkezmeny Letezik optimalis politika, es az optimalis koltsegfuggveny

teljesti a kovetkez}o Bellman tpusu egyenletet [2]:

v(x) = min max (c(x; a; y) + v(y)) : a2A y2T x;a (

)

Tovabba az optimalis koltsegfuggveny el}oall, mint limn!1 Gn v, ahol v egy tetsz}oleges korlatos fuggveny. Bizonytas. Mivel A veges, gy mindig van olyan politika, amely moho az optimalis koltsegfuggvenyre nezve. A fenti alltas szerint egy ilyen politika optimalis is lesz. Legyen most  moho v-ra. A fenti bizonytasbol latszik, hogy ekkor T v = v, masreszt mivel  moho v-ra gy T v = Gv de ncio szerint, tehat Gv = v. Konny}u latni, hogy G is kontrakcio, gy az iteralasa az egyetlen xpontjahoz vezet, ami mint mar tudjuk epp v. 2

A vt = Gvt iteraciot nevezzuk Dinamikus Programozas (DP) iteracionak. A fenti tetelek alapjan lathato, hogy egy optimalis politika megkeresesehez elegend}o v-ot kiszamolni, pl. a DP iteracioval, majd venni v-ra a moho politikat. A tovabbiakban ezt az otletet kovetjuk, olyan feltetelek mellett, hogy a dontesi modell nem vagy csak reszben ismert, vagy a \teljes" DP iteracio \tul" draga. +1

20

4. Fejezet Meger}osteses tanulas Az alabbiakban azt a feladatot tanulmanyozzuk, amikor nem ismert a dontesi folyamat modellje. A kovetkez}oekben csak az un. koltsefuggveny alapu meger}osteses tanulasos algoritmusokkal foglalkozunk. Ezek az algoritmusok a pontos vagy becsult moho operator alapjan a dinamikus programozas egy aszinkron forma jat valostjak meg. Az algoritmus egy vegtelen iteraciobol all, melynek minden le-

4.1. tablazat: Koltsegfuggveny alapu Reinforcement tanulo algoritmus repeat foreverf 1. 2. 3.

xt; ct erzekelese.

Modell modostasa: Gt = M (Gt ; ct; xt; at ; xt ; . . .). E rtekelesek ujraszamolasa: +1

1

1

(

vt (x) = v(Gt(txv)t;)(x); xx 22= UUtt;: +1

4. Akcio kivalasztas: at = (xt; vt). 5. Akcio vegrehajtasa. 6. t := t + 1.

g

peseben a kovetkez}ok tortennek: az els}o lepesben a pillanatnyi allapot, valamint az atmenetkoltsegek erzekelese tortenik, ami azt jelenti, hogy a rendszer bealltja bels}o allapotat a szenzorai segtsegevel. A masodik lepesben tortenik a modell modostasa, melynek vegeredmenye a (3.3) egyenletben de nialt G moho operator egy uj kozeltese. A becsult moho operator alapjan tortenik a becsult optimalis koltsegfuggveny \ nomtasa". Valo jaban tudnunk kell, hogy a bels}o reprezentacioval 21

rendelkez}o rendszerekben a modell modostasa a bels}o reprezentacio megvaltoztatasat jelenti. Az ertekelesek ujraszamolasa az immaron megvaltozott modell alapjan tortenik. Itt az Ut halmaz tetsz}oleges nemures halmaz. A ltalaban elvarjuk, hogy adott t-re xt 2 Ut teljesuljon. Megjegyezzuk, hogy egy menetben (a 3-as lepesben) egy allapot ertekeleset, neha erdemes tobbszor is ujraszamolni, masreszt az allapotok frisstesenek sorrendje igen fontos lehet [12,15]. Azzal, hogy nem minden allapot ertekeleset szamoljuk ujra egy-egy lepesben jelent}os futasid}ot takarthatunk meg. Az akciok kivalasztasa a pillanatnyi ertekeles alapjan tortenik a rendszer kontroll strategia ja segtsegevel. A kontroll strategia lehet peldaul olyan, hogy ha egy bizonyos allapotrol nincs eleg informacionk (bizonytalan az ertekelesunk), akkor az algoritmus veletlenszer}uen valaszt, egyebkent pedig az optimalisnak gondolt akciot valasztja. Az akcio vegrehajtasa a manipulatorok bealltasat jelenti. A manipulatorok hatnak a kuls}o kornyezetre, es ezen kornyezet megvaltozasat eszleli a rendszer a kovetkez}o iteracioban. Lathato, hogy az algoritmus alapvet}oen harom jol elkulonthet}o reszb}ol all: a modelleptesb}ol, az ertekeles szamolasabol es az akcio kivalasztas reszekb}ol. Ezeket egymastol fuggetlenul cserelhetjuk. Az algoritmus motorjat a 3-as lepes, az ertekelesek ujraszamolasa jelenti. A kovetkez}o reszt az algoritmus ezen lepesenek szenteltuk, egyenl}ore azon feltetel mellett, hogy a moho operator pontosan ismert. Ezutan egy olyan algoritmust tekintunk, amelyben mar a kontroll strategianak is jut szerep (4. lepes), mg vegul azt az esetet tekintjuk, amikor a dontesi folyamat modellje, azaz G sem ismert (2. lepes).

4.1 Aszinkron Dinamikus Programozas 4.1.1 Egy altalanos aszinkron konvergencia tetel Az elkovetkezend}okben bizonytott tetelek vegeredmenyben mind Bertsekas es Tsitsiklis un. aszinkron konvergencia tetelen alapulnak [3]. Ebben a fejezetben ennek a tetelnek egy egyszer}ustett forma javal ismerkedunk meg { bizonytas nelkul.

22

4.1.1 Defincio Legyen T : RX ! RX tetsz}oleges lekepezes, v 2 RX , Ut  f1; . . . ; ng nemures halmazok sorozata (t  0)-ra. Ekkor a 8 > < v (x); x 2= Ut; vt (x) = > t : (Tvt)(x); x 2 Ut : iteraciot gyengen aszinkron iteracionak nevezzuk. Ha x 2 Ut , akkor azt mondjuk, 0

+1

hogy vt(x)-et \frisstjuk" a t-edik lepesben.

Legyen X veges halmaz es rogztsuk a T : RX ! RX operatort.

4.1.2 Tetel Legyen a fV (k)g olyan nemures halmazsorozat, hogy . . .  V (k + 1)  V (k)  . . .  RX ; es tegyuk fel, hogy az alabbi ket feltetel teljesul: 1. Szinkron konvergencia feltetel:

T (V (k))  V (k + 1) es ha minden k -ra vk 2 V (k), akkor vk konvergens es limk!1 vk = v , ahol Tv = v, vagyis v T xpontja. 2. Teglalap feltetel: minden k termeszetes szamra

V (k) = V (k)  . . .  Vn (k); 1

ahol jX j = n: Azaz a V (k)-beli vektorok komponenseit egymastol fuggetlenul cserelgetve, szinten V (k )-beli vektort kapunk. Ekkor tetsz}oleges v0 2 V (0) elemb}ol kiindulva a gyengen aszinkron iteracio konvergens es tart a T valamely xpontjahoz, felteve, hogy minden x 2 X vegtelen sokszor fordul el}o az fUt gt2N halmazsorozatban.

4.1.2 Az Aszinkron Dinamikus Programozas algoritmus konvergencia ja Ebben a reszben a vt = Gvt DP iteracio aszinkronna tetelenek lehetsegesegessegevel foglalkozunk. Ehhez szuksegunk van az alabbi lemmara: +1

23

4.1.1 Lemma Legyen 0 < < 1, (X; A; T; c) veges Markov dontesi problema adott. Ekkor leteznek olyan min ; max valos szamok, hogy minden   min es   max valos szam eseten ha vmin (x) =  ; vmax(x) =  (x 2 X ), akkor 1

1

2

2

vmin  Gvmin ;

Gvmax  vmax;

ahol a G operator a moho ertekeleshez tartozo operator (lasd a (3.3) egyenletet). Bizonytas. Legyen  2 R, es v (x) = ; (x 2 X ). Ekkor

(Gv)(x) = min max (c(x; a; y) + v(y)) = min max c(x; a; y) + : a2A y2T x;a a2A y2T x;a (

Ha tehat

)

(

)

c^(x) = min max c(x; a; y); a2A y2T x;a (

)

akkor (Gv)(x) =  + c^(x). Legyen ezutan min = 1 1 min c^(x) x2X es max = 1 1 max c^(x): x2X

A lltjuk, hogy ezen min es max ertekek megfelelnek a tetel felteteleinek. Legyen el}oszor   min tesz}oleges es v(x)   . Megmutatjuk, hogy (Gv)(x)  v(x) all minden x 2 X -re. Valoban: 1

1

(Gv)(x) =  + c^(x)   + min c^(x) =  + (1 )min   : x2X 1

1

1

1

Masreszr}ol legyen   max tesz}oleges es v(x) =  ; x 2 X . Ekkor (Gv)(x)  v(x) all minden x 2 X -re, ugyanis 2

2

(Gv)(x) =  + c^(x)   + max c^(x) =  + (1 )max   : x2X 2

2

2

2

2

4.1.3 Tetel Legyen v 2 RX , ahol X az allapotok veges halmaza. Vegyuk a kovet0

kez}o gyengen aszinkron iteraciot:

8 > < v (x); vt+1(x) = :> t (Gvt)(x);

24

x 2= Ut; x 2 Ut;

ahol a G a a moho operator, Ut  X pedig tetsz}oleges nemures halmazok. limt!1 vt = v  , ahol v  az optimalis koltsegfuggveny, felteve, hogy minden x allapot vegtelen sokszor kerul \frisstesre" (minden x vegtelen sokszor fordul el}o az fUt g halmazrendszerben). Bizonytas. A 4.1.2 aszinkron konvergencia tetelt alkalmazzuk. Ehhez kell konstrualnunk a V (k) halmazokat, majd megmutatjuk, hogy teljesulnek a szinkron konvergencia es a teglalap feltetelek. Legyen

V (k) = fv 2 RX jGk vmin  v  Gk vmaxg; ahol





x2X



x 2 X;

vmin(x) = min min ; min(v (x); v(x) ; 0

es



vmax(x) = max max ; max (v (x); v(x) ; 0

ahol min es max az el}oz}o lemmaban de nialt ertekek. El}oszor meg kell mutatnunk, hogy V (k + 1)  V (k) all minden k-ra. Legyen tehat v 2 V (k + 1) tetsz}oleges. Mivel vmin    min , ezert az el}oz}o lemma szerint vmin  Gvmin . Mivel G monoton, mindket oldalra alkalmazva G-t kapjuk, hogy Gvmin  G vmin , ezt folytatva indukcioval kovetkezik, hogy 2

Gk vmin  Gk vmin; +1

Hasonlo modon bizonythato, hogy

Gk vmax  Gk vmax: +1

Ezekb}ol V (k + 1) de nciojat felhasznalva kapjuk, hogy Gk vmin  v  Gk vmax, vagyis v 2 V (k). Meg kell meg mutatni, hogy

G(V (k))  V (k + 1): Legyen v 2 V (k) tetsz}oleges. Ekkor

Gk vmin  v  Gk vmax: Alkalmazva a G-t es kihasznalva G monotonitasat kapjuk, hogy

Gk vmin  Gv  Gk vmax; +1

+1

25

vagyis Gv 2 V (k + 1). Legyen most vk 2 V (k) minden k-ra. Megmutatjuk, hogy vk konvergens es hatarerteke G xpontja. Mivel Gk vmin  vk  Gk vmax all minden kra, es limk!1 Gk vmin = v = limk!1 Gk vmax (mivel G kontrakcio), ezert a rend}orelv alapjan kovetkezik, hogy limk!1 vk = v. A teglalap feltetel teljesulese egyszer}uen belathato. A megfelel}o Vx(k) halmazok:

Vx(k) = fr 2 Rj(Gk vmin)(x)  r  (Gk vmax)(x)g;

x 2 X:

Ezek utan mar alkalmazhatjuk az aszinkron konvergencia tetelt, amib}ol kovetkezik a tetel alltasa. 2

4.2 Valos-idej}u Dinamikus Programozas Ebben a reszben megmutatjuk, hogy a moho kontroll strategia kovetese asszimptotikusan optimalis viselkedeshez vezet. El}oszor azonban be kell vezetnunk a nemstacioner politikak fogalmat.

4.2.1 Defincio  nem-stacioner politika, ha  = ( ;  ; . . .), ahol 0

1

 : X ! A;  : X  (X  A) ! A; 0

1

... t : X  (X  A)t ! A; ...

A tanulo algoritmusok altalaban nem stacioner politikat kovetnek, hiszen az aktualis akcio valasztasa attol (es csak attol) fugg, hogy el}oz}oleg a rendszer milyen utat jart be { eltekintve a kezdeti feltetelekt}ol.

4.2.2 Defincio Egy  politika asszimptotikusan optimalis, ha minden (x ; a ; x ; a ; . . . ; xt; at; . . .) 0

0

1

1

 szerinti lehetseges trajektoriara van olyan T , hogy minden t > T -ra, at 2 A(xt), 0

ahol

A(x) = Argmin y2max (c(x; a; y) + v(y)): T x;a a2A

(

)

26

0

4.2.3 Megjegyzes Azert nem rhatjuk, hogy at = argmin y2max (c(x; a; y) + v(y)); T x;a a2A

(

)

mert a minimalis ertekeles tobb akciora is el}ofordulhat. Ilyenkor valasztanunk kell. Egyik lehetseges megoldas, hogy rendezzuk az akciokat es ez alapjan valasztunk. Az alabbi tetel bizonytasa el}ott jegyezzuk meg, hogy az eddigi eredmenyeinket nem befolyasolja, ha a Markov dontesi problema de ncio jat ugy modostjuk, hogy minden x 2 X allapotra megszortjuk az x-ben alkalmazhato akciok halmazat valamely A(x)  A halmazra.

4.2.4 Tetel (Valos-ideju} Dinamikus Programozas) Legyen  az a nem-stacioner

politika, amelyre

t(x; at ; xt ; at ; xt ; . . . ; a ; x ) 2 Argmin y2max (c(x; a; y) + vt(y)); T x;a 1

1

2

ahol

2

0

0

a2A

(

)

8 > < v (x); vt+1(x) = >: t (Gvt)(x);

x 2= Ut; x 2 Ut es v 2 B (X ) olyan, hogy v  v  es xt 2 Ut. Ez a  = ( ; . . . ; t ; . . .) politika 0

0

0

asszimptotikusan optimalis.

Bizonytas. El}oszor azt az esetet bizonytjuk, amikor Ut = fxtg. Vegyunk egy lehetseges  szerinti trajektoriat, legyen ez p = ((x0; a0); (x1; a1); . . . ; (xt; at); . . .). Legyen U 1  X  A azon (x; a) parok halmaza, amelyre (x; a) par vegtelen sokszor fordul el}o p-ben. U 1 6= ;, mivel mind X , mind A vegesek. Legyen X 1 = fx 2 X j(x; a) 2 U 1 g. Konnyen lathato, hogy ha (x; a) 2 U 1 es y 2 T (x; a), akkor y 2 X 1. Legyen A1(x) = fa 2 Aj(x; a) 2 U 1 g:

Ekkor vt iteracioja a kovetkez}okeppen rhato:

!

vt (x) = min a2min ( max (c(x; a; y) + vt(y))); a2Amin ( max (c(x; a; y) + vt(y))) ; A1 x y2T x;a nA1 x y2T x;a (4:1) +1

( )

(

)

( )

27

(

)

ahol a mina2A-t egyszer}uen csak szetbontottuk ket minimumra. Tudjuk, hogy letezik olyan T , hogy ha t > T , akkor (xt; at) 2 U 1 . Ekkora t-re tehat at 2 A1(xt). Vegyunk egy ilyen t-t; at de ncioja szerint: 0

0

max (c(xt; at; y) + vt(y)) = min max (c(xt; a; y) + vt(y)); a2A y2T x;a

y2T (xt;at )

(

)

tehat min max (c(xt; a; y) + vt(y)) = a2min max (c(x; a; y) + vt(y)): a2A y2T x ;a A1 x y2T x ;a (

t

)

(

t)

(

t

)

Tehat a (4.1)-ben a masodik minimum elhagyhato, azaz:

vt (x) = a2min max (c(x; a; y) + vt(y)): A1 x y2T x;a +1

( )

(

)

Ezutan vegyuk az F 1 = (X 1 ; A1; T; c) Markov dontesi problemat . Lathato, hogy az F 1 feladat resze az eredeti feladatnak, megszortva arra a reszre, amit a donteshozo, aki -t hajtja vegre, vegtelen sokszor bejar. Legyen v^ = vT0 jX 1 , vagyis vT0 megszortottja az X 1 halmazra. Most a v^ kezd}oertekre es F 1-re alkalmazhatjuk az aszinkron dinamikus programozas tetelet (4.1.3 Tetel), ugyanis most mar barmely x 2 X 1 vegtelen sokszor fordul el}o az Ut halmazokban. Kovetkezeskeppen limt!1 vtjX 1 = u, ahol u az F 1 feladathoz tartozo optimalis koltsegfuggveny. Vilagos, hogy vjX 1  u, mivel az F 1 feladat az eredeti feladat megszortasa. Masreszt mivel v  v, gy indukcioval konnyen jon, hogy minden t-re vt  v is all, ugyanis vt (x) = (Gvt)(x)  (Gv)(x) = v(x): 0

0

0

+1

Tehat limt!1 vtjX 1 = u  vjX 1 is all, es gy

vjX 1 = u: Most mar csak azt kell megmutatni, hogy egy id}o utan a rendszer csupa optimalis akciot valaszt. Tudjuk, hogy megfelel}oen nagy t-re

at 2 Argmin max (c(xt; a; y) + vt(y)): 1 y2T xt;a a2A (xt)

(

)

Eleg belatni, hogy van olyan T id}opont, hogy ha t > T , akkor 1

1

at 2 Argmin max (c(xt; a; y) + u(y)) = AF 1 (xt): 1 y2T xt ;a a2A (xt)

(

)

28

Ezt az alltast Szepesvari megmutatta (szobeli kozles). A bizonytas egyszer}uen kiterjeszthehet}o arra az esetre, ha Ut szigoruan b}ovebb mint fxtg. 2 Hasonlo eredmenyeket Korf [7], valamint Barto es tarsai bizonytottak a varhato lecsengetett osszkoltseg esetere [1]. Ennek megfelel}oen az }o eredmenyeik kisse mas bizonytasi modszereket igenyeltek. Megjegyezzuk, hogy az itt lert modszerek mas, egyeb kriteriumokhoz tartozo dontesi problemakra is alkalmazhatoak (ld. [14]).

4.3 Adaptv Aszinkron Dinamikus Programozas Tekintsuk most a 4.2 tablan lathato algoritmust. Az algoritmusban t egy veletlen

4.2. tablazat: Adaptv aszinkron dinamikus programozasi algoritmus T (x; a) := ;; v  v. repeat foreverf 1. xt erzekelese. 2. Modell modostasa: T (xt ; at ) := T (xt ; at ) [ fxtg. 0

1

3. E rtekelesek ujraszamolasa:

1

1

1

(

x 2= Ut; t(x); vt (x) = v(Gv t )(x); x 2 Ut : +1

4. Akcio kivalasztas: at 2 A(xt; t). 5. Akcio vegrehajtasa. 6. t := t + 1.

g

menyiseg, mely azt hivatott elerni, hogy minden allapotban minden akciot vegtelen sokszor valasszunk. Feltetelezzuk, hogy ezeknek a veletlen mennyisegeknek a hatasa asszimptotikusan elt}unik es vegul az algoritmus mindig a moho akciot valasztja. Vilagos, hogy a vegtelen sokszor bejart terresz (X 1 ) modelljet a fenti algoritmus veges id}on belul (1 valoszn}useggel) felepti. Ha ekkor vt  v, akkor a 4.2.4 Tetel alapjan a fenti algoritmus sztochasztikusan asszimptotikusan optimalis lesz; azaz Prob(at 2 A(xt)) ! 1; t ! 1. Ha a dontesekben a veletlen elem nem szerepelne, akkor az eptett modell a vegtelenszer bejart terreszben sem tartana az valodi modellhez { ugyan vt  v teljesulne, am el}ofordulhatna, hogy limt!1 vtjX 1 < vjX 1 .

4.3.1 Tetel A fenti algoritmus sztochasztikusan asszimptotikusan optimalis. 29

Bizonytas. Mivel a rendszer veges id}on belul 1 valoszn}useggel pontos modellt ept, gy ezekutan az algoritmus atalakul aszinkron dinamikus programozassa (a 3-as lepes) es ebb}ol a 4.2.4 Tetel alapjan mar kovetkezik is az alltas. 2

4.4 A DC modell Ebben a reszben bemutatunk egy lehetseges implementaciot egy adaptv aszinkron algoritmust hasznalo rendszerre. A rendszer az un. DC (dynamic concept) modellt hasznalja a dontesi modell kozeltesere [15]. A rendszer es kornyezete interakcio jat a rendszer szemszogeb}ol az x ; a ; x ; a ; . . . allapot{akcio sorozat teljesen lerja. Ezt a sorozatot harmasokra tagolva jutunk el az elemi triplethez: t = (xt; at; xt ). A DC modell tarolasi modszereben az elemi tripletek alapelemeket jelentenek, amelyekb}ol a rendszer eptkezik. A bels}o reprezentaciot egy G = (V; E ), veges, iranytott graf segtsegevel implementaljuk, ahol a V a graf csucsainak halmazat, E a graf eleinek halmazat jeloli es V az elemi tripletek halmazabol veszi elemeit. A graf egy adott id}opillanatban az addig osszegy}ujtott tapasztalatokat tarolja. Els}o megkozeltesben csucsainak halmazat, mint az adott id}opillanatig megtapasztalt elemi esemenyek egy reszhalmazat de nialjuk: 0

0

1

1

+1

V  f ;  ; . . . ; tg: 1

2

A graf elei azt reprezentaljak, hogy az osszekotott elemi tripletek hogyan kovetkezhetnek egymas utan. A kovetkez}o axiomak teljesuleset koveteljuk meg:

 Egy (x; a; y) triplet csak akkor lehet a grafban, ha y 2 T (x; a).  Minden elemi triplet csak egyszer fordulhat el}o a grafban.  Egy ((x; a; y); (z; b; q)) el pontosan akkor lehet a grafban, ha teljesul a ket csucspont-tripletre az un. kompatibilitasi relacio, vagyis ha y = z.

Az X -en de nialt koltsegfuggvenyt most egy V -n de nialt fuggvennyel helyettestjuk. Hogyan lehet egy V -n alkalmasan de nialt fuggvenyb}ol v-ot visszakapni? 30

Legyen T = f(x; a; y)jx 2 X; a 2 A; y 2 T (x; a)g a lehetseges tripletek halmaza es legyen R egy R : T ! R lekepezes. Rendeljuk hozza ehhez az R lekepezeshez azt a QR : X  A ! R fuggvenyt, melyre

QR(x; a) = max fR(x; a; y)j(x; a; y) 2 T g: y2X

(4:2)

Most mar ha adott egy Q : X  A ! R fuggveny, akkor legyen

vQ(x) = min Q(x; a) a2A

Vegeredmenyben ezzel az R fuggvenyhez is hozzarendeltunk egy vR : X ! R fuggvenyt: vR = vQR : A DC modell tanulo-algoritmusa a 4.3 tablan lathato. A graf modostasa alatt

4.3. tablazat: Az adaptv aszinkron tanulasi algoritmus DC modellre kidolgozott

implementacioja.

repeat foreverf 1. xt erzekelese.

2. A graf modostasa (xt ; at ; xt) elemi triplettel. 3. E rtekelesek ujraszamolasa: 1

1

(

Rt ( ) = cR(tx;(a;); y) + v (y);  2== U(x;t; a; y) 2 U : Rt t +1

4. Akcio kivalasztas: at = (xt; vRt+1 ). 5. Akcio vegrehajtasa. 6. t := t + 1.

g

a csucshalmaz kib}ovteset ertjuk az (xt ; at ; xt) triplettel, valamint az elhalmaz kib}ovteset mindazon elekkel, amelyek a kompatibilitasi feltetellel osszefernek. Mivel a grafot folyamatosan eptjuk, el}ofordulhat, hogy valamely x-re nincs (x; a; y) 2 V triplet. Ekkor vRt (x) = cmin de ncio szerint, ahol cmin a kozvetlen koltsegek egy also becslese. QRt (x; a) de ncioja hasonloan ertelmezhet}o. Konnyen latszik, hogy a fenti algoritmusra alkalmazhatjuk az adaptv aszinkron dinamikus programozas tetelet (4.3.1 Tetel) mialtal kapjuk, hogy vRt jX 1 konvergal vjX 1 -hez. Az Ut halmazt a kovetkez}okepp de nialtjuk: 1

1

Ut = f(x; a; y) 2 V jx = xt; vagy letezik iranytott ut (x; a; y)-bol (xt ; at ; xt)-beg: 1

31

1

Jol lathato, hogy az Ut ilyen valasztasa biztostja, hogy csak azon tripletek ertekeleset valtoztatjuk, amelyeknek az ertekelese megvaltozhat az uj csomopont bevetelevel. A graf eleinek tarolasat altalaban a 3. lepesben tesszuk meg a frissteseknel, amikoris a grafban az iranytassal ellentetesen haladva felfrisstjuk a tripletertekeleseket.

32

5. Fejezet A ltalanostas 5.1 Fogalmak Egy explicit koltsegfuggvenyt hasznalo algoritmus, mint pl. egy, a DC modellt hasznalo rendszer, egyszer}u kornyezetekben kielegt}o eredmenyeket erhet el, azonban nagyobb allapotterekben mar nem kepes hatekonyan m}ukodni. E korlatot atlephetjuk \fogalmak" bevezetesevel, azaz az allapotok alkalmas csoportostasaval. A fogalomalkotas nagyban novelheti rendszer tudasat, hiszen a fogalmakat egyedi peldakbol vezetjuk ugyan le, de alkalmazasuk nem szortkozik ezen peldakra: alkalmazhatok uj objektumok es esemenyek osztalyozasara is. Igy a rendszer a megfelel}o fogalmak kialaktasa utan olyan kornyezetben is jol m}ukodhet, amelyben azel}ott nem volt. Fogalmak nelkul a rendszer szenzori{motoros es gondolkodasi folyamatai csak egyszer}u, veges stimulus halmazra \beugro" re exszer}u akciokra korlatozodnak. Lathattuk, hogy az aktuatorok hatasa altalaban nem egyertelm}u hatasokat okoz a rendszer allapotanak megvaltozasaban. Minnel inkabb egyertelm}u ez hatas, annal konnyebb a megfelel}o kontrollstrategia kidolgozasa. A rendszer szabalyok kialaktasara torekszik. A fogalomalkotas a szabalyok felalltasaban is segt. A kulvilag bels}o reprezentacio ja es a rendszer kornyezeter}ol kialaktott fogalmai szorosan osszefonodnak. A fogalmak sokszor implicite vannak jelen a bels}o reprezentacioban. A fogalmakat a rendszer abduktv kepessege segtsegevel sz}uri ki a cselekvesekhez kapcsolodo tapasztalatai kozul. Az elmult evekben szamos modell alakult ki a fogalomalkotas teren. Tipikus a mesterseges intelligencia (MI) fogalom de ncio ja, 33

amely azt mondja, hogy a fogalmak a vilag objektumaira es esemenyeire vonatkozo szavak es kifejezesek reprezentacios ekvivalensei. A fogalmakat jellegzetessegek de nialjak. Ezen jellegzetessegek az objektumok es esemenyek kulonboz}o tulajdonsagaihoz tartoznak. Peldaul az asztal fogalma magaban foglalja azt a jellegzetesseget, ami azt jeloli, hogy vannak labai. Mivel a jellegzetessegek az objektumok es esemenyek invarians tulajdonsagait reprezentaljak, olyba veszik, hogy szemantikus ertekuk ezzel de nialt. A klasszikus modell azt feltetelezi, hogy a fogalmak es a fogalmak kozti hierarchiakat reprezentalo kapcsolatok kozott vilagos hatarok vannak. A jellegzetessegek termeszete es funkcio ja hatarozza meg a fogalmak hataranak vilagos elkulonuleset. Az elmult evtizedben mas modelleket is kidolgoztak. A valoszn}usegeken alapulo modell, sulyokat rendel a fogalmakat de nialo jellegzetessegekhez, csakugy, mint a fogalmakat de nialo halmazok koze. Ezt a reprezentaciot egy kuszob{alapu dontesi eljarassal otvozik. A pelda{alapu modellekben a fogalmak csak peldakon keresztul de nialtak. Ez a modell szinten alkalmas a fogalomhoz tartozas arnyalatainak es tipikussaganak kifejezesere. Az elkovetkez}okben targyalando fogalomalkotasi koncepcio szakt a hagyomanyos modszerekkel. A fentebb vazolt modellek egyike sem adja a fogalom formalas adekvalt megkozelteset. A feltetelezes, hogy a fogalmak jellegzetessegek altal de nialtak, mell}ozi azokat a tenyez}oket, amelyek a fogalmak kialakulasat es hasznalatat meghatarozzak. A kontextusbeli tenyez}ok szerepe megvaltoztatja a jellegzetessegek relatv fontossagat. Ezek a modellek mind feltetelezik, hogy a vilag a rendszert}ol fuggetlen, objektv igazsagokat tartalmaz es a rendszer feladata, hogy ra jo jjon ezekre az igazsagokra: Az uj fogalomalkotasi koncepcio a kovetkez}o pontokba szedhet}o :

 Elvetjuk, hogy a vilag olyan a priori informacot (logikai, szokseges azonos-

sagokat) hordoz, melyet a rendszernek igyekeznie kell megtanulnia (es bels}o reprezentacio forma jaban) kodolnia. Ehelyett adatok vannak benne, amelyb}ol a rendszernek kell az informaciot kisz}urnie. Az informacioszerzes ertelme, hogy a rendszer cel{orientalt viselkedeseit hatekonyabban tudja megvalostani.

 A fogalom kilaktas folyamata nem elkulonult, absztrakt szintaktikus resz a

rendszerben, hanem szorosan kapcsolodik a rendszer szenzoros es motoros 34

rendszereihez.

 Van korrelacio a vilag invarians tulajdonsagai es a bels}o reprezentacio kozott,

de nem motivalunk szemantikat ezen az alapon. A rendszer{kornyezet egyutthatas a folytonos vilagot meglehet}osen stabil reprezentacioba transzformalja at. Ezt a transzformaciot keresve a rendszer allandoan a vilag invarians mintazatai vagy tulajdonsagai utan kutat.

 A kodolas reprezentacios tartalma cel{orientaltan jelenik meg. A megfeleles a vilag invarians jelensegei es a bels}o reprezentaciojuk kozott nem elegend}o ahhoz, hogy a bels}o reprezentaciohoz szemantikus ertekeket rendeljunk. A szemantika hozzarendelese celra iranyulo kell legyen.

Egy szimulacioban egy tanult DC modell viselkedeset gyelve az vehetnenk eszre, hogy hasonlo szituaciokban hasonlokepp viselkedik. Ez a szituaciot lero fogalom, es a fogalomhoz kapcsolodo cselekves jelenletere utal, tehat a DC modell mar keszt fogalmakat. Ezek a fogalmak implicite megtalalhatok a bels}o reprezentacioban un. szetszort reprezentacioban. A fogalomalkotas pelda alapu. Ezen fogalmak jelentese a bels}o reprezentacio hasznalataval de nialt. A szetszort fogalom reprezentacioi meglehet}osen nagy memoria igeny}u. El}onye azonban az, hogy meglehet}osen robosztus: bels}o reprezentacio janak serulese eseten se tunnek el a fogalmak, legfeljebb elmosodnak. Mindazonaltal kvanatos lenne egy olyan fogalom reprezentacio, amelyben explicite is jelen vannak a fogalmak. Ez lehet}ove tenne szelesebb kor}u hasznalatukat a kontroll strategiaban, es olyan analog szituaciokban is \kiprobalhato" lenne, amelyekkel a rendszer meg nem talalkozott. A fogalmak formalasat peldakbol fogjuk levezetni. Az egy fogalomhoz tartozo peldak halmazaban az kozos, hogy ugyanannak a celnak a teljesuleset josoljak. A kozos tulajdonsagok kiemeleset altalanostasnak nevezzuk. Tehat a modellunk a fogalmakat altalanostassal fogja keszteni. A modell az un. gyors altalanostast hasznalja majd, ami azt jelenti, hogy fogalomalkotasra kerul sor ha mar ket olyan peldat talal a rendszer, ami ugyanazt az \otletet tamogatja".

35

5.2 Meger}osteses tanulas kompakt allapot reprezentacio eseten A meger}osteses tanulas kutatoi koran felismertek, hogy az allapot es akcioter mar kozepesen bonyolult dontesi problema eseteben is hatalmas lehet. Igaz, hogy a fent emltett algoritmusok polinom id}oben futnak ha a modell ismert es rogztett [8], am meg ekkor is hatalmas futasi id}oket igenyelnek. Ezt ketfelekepp lehet redukalni multirezolucios id}o-skalaval [11,13], vagy az allapot-ter kompresszio javal [16,4,9]. Ez utobbi megoldassal tobben is probalkoztak, azonban mindez ideig egyetlen modszerr}ol sem lehetett bebizonytani, hogy meg}orzi az optimalis koltsegfuggvenyt, vagy legalabb az optimalis politikakat. Alabb megadunk egy algoritmust es bebizonytjuk, hogy meg}orzi az optimalis koltsegfuggvenyt. Az algoritmusunk kategoriak, vagyis fogalmak segtsegevel dolgozik.

5.2.1 Defincio Azt mondjuk, hogy egy S kategoria jelen van egy x allapotban, ha S (x) = 1, ahol S fuggveny az S kategoria karakterisztikus fuggvenye.

Az S kategoriat akar tekinthetjuk az allapotter egy reszhalmazanak is S  X . A karakterisztikus fuggvenyenek [0; 1] intervallumra kiterjesztesevel a \fuzzy"{va is tehetjuk a kategoriat. Jeloljuk a rendszer altal hasznalhato kategoriak halmazat K = P (X ){el, K elemeit S {el. A most kovetkez}okben de nialunk egy adatstrukturat, amely segtsegevel az altalanos meger}osteses algoritmusunkat felruhazzuk az explicit fogalomkezeles kepessegevel. Adjunk meg egy (X; A; T; c) dontesi problemat, ahol most, hogy c(x; a; y) = c(y), vagyis c csak y-nak fuggvenye. Legyen adott a kovetkez}o adatstruktura:

V = f(S; a; y)jS  X; a 2 A; y 2 X g; ahol S tulajdonkeppen kategoria, es vegyunk V -n egy ertekelest :

R:V !R

5.2.2 Megjegyzes A fenti V halmaz elemeit altalanostott tripleteknek vagy triple-

teknek nevezzuk. Konnyen lathato, hogy az elemi tripletek olyan specialis tripletek, amelyeknek az els}o alkoto ja egyelem}u halmaz.

36

Az el}oz}o fejezetben bevezetett fuggvenyek kiterjeszthet}ok a V adatstrukturara is. Legyen tehat QR(x; a) = max fR(S; a; y)j(S; a; y) 2 V; x 2 S g: (5:1) Ezzel adott R fuggvenyhez hozzarendeltunk egy Q = QR : X  A ! R fuggvenyt. Most adott Q : X  A ! R fuggvenyhez a szokasos modon { a

vQ(x) = min Q(x; a) a2A de ncio segtsegevel rendeljuk hozza a v = vQ : X ! R fuggvenyt. Egy (S; a; y) 2 V elemnel az S kategoriaban szeretnenk tarolni mindazokat az allapotokat, amelyekb}ol az a akcio az y allapotba visz. Igy a Q(x; a) de ncioja esszer}unek t}unik, hiszen a legrosszabb ertekelest vesszuk gyelembe. Tegyuk fel, hogy V = f(fxg; a; y)jx 2 X; a 2 A; y 2 T (x; a)g: Legyen adott v 2 RX -re Rv (fxg; a; y) = c(y)+ v(y). Ekkor R = Rv -ra, vQR = v. Most ismertetjuk azt az algoritmust, ami egy adaptv aszinkron algoritmus altalanostassal ellatott valtozata. Adott V = f(S; a; y)jS  X; a 2 A; y 2 X g. Tegyuk fel, hogy \V teljes (a; y)-ra nezve", azaz minden a 2 A akciora es y 2 X allapotra pontosan egy olyan S  X kategoria van, hogy (S; a; y) 2 V . Ezt a kategoriat S (a; y)-val fogjuk jelolni. A kezdeti csucshalmaz lehet pl. f(;; a; y)j(a; y) 2 A  X g. Adott tovabba az Rt : V ! R ertekeles. Az algoritmus a 5.1 tablazatban lathato. Az akcio kivalasztas ugyanugy tortenik, mint az Adaptv Aszinkron DP algoritmusnal.

5.2.3 Megjegyzes A ltalaban (S (at ; xt); at ; xt) 2 Ut: 1

1

5.2.4 Megjegyzes A fenti algoritmus alapjan a DC modell konnyen felruhazhato

az altalanostas kepessegevel. Ehhez csak a fenti algoritmust kell kiterjeszteni grafostott algoritmusra. Most ket csucs, pl. (S ; a; y) triplet es az (S ; b; z) triplet, akkor es csak akkor kothet}o ossze, ha y 2 S . 1

2

2

A \t" operacio egyfajta \egyestesi operator", amelyre altalaban igaz, hogy S [ S 0  S t S 0  X . Pontosabban a kovetkez}o tulajdonsagot koveteljuk meg: 37

5.1. tablazat: Adaptv aszinkron algoritmus altalanostassal ellatott verzioja repeat foreverf 1. 2. 3.

xt erzekelese.

Kategoria b}ovtes: S (at ; xt) := S (at ; xt) t fxt g. E rtekelesek ujraszamolasa: 1

1

1

(

Rt ( ) = Rc(ty() +); v (y);  2== U(S;t; a; y) 2 U : Rt t +1

4. Akcio kivalasztas: at = A(xt; t). 5. Akcio vegrehajtasa. 6. t := t + 1:

g

5.2.5 Defincio Azt mondjuk, hogy t b}ovtes tulajdonsagu, ha adott S  X; x 2 X eseten x 2 S t fxg es S  S t fxg. Az egyestesi operacio kategoria-reprezentacio fugg}o, tehat a megvalostast az hatarozza meg, hogy hogyan reprezentaljuk a kategoriakat. Tetelunkhoz szukseg van az alabbi ket de nciora:

5.2.6 Defincio x hamis megel}oz}oje az (a; y) 2 A  X parnak, ha y 2= T (x; a) 5.2.7 Defincio x potencialis megel}oz}oje az (a; y) parnak a t altalanostas melett, ha van olyan t 2 N termeszetes szam, es x ; . . . ; xt 2 X veges sorozat, hogy y 2 1

T (xi; a) es







x 2 . . . ((fx g t fx g) t fx g) . . . t fxtg : 1

2

3

Ha egyetlen (a; y) parnak sincs hamis potencialis megel}oz}oje, akkor az altalanosto algoritmus lenyegeben egy gyengen aszinkron iteraciora redukalodik. Azonban ez tul er}os felteves. Az alabbi tetel azt mutatja, hogy ennel joval gyengebb felteves mellett is meg}orizhet}o az optimalis koltsegfuggvenyhez valo konvergencia.

5.2.8 Tetel Ha t b}ovtes tulajdonsagu es ha x az (a; y) par hamis potencialis megel}oz}oje, akkor

c(y) + v(y)  Q(x; a);

(5:2)

valamint, minden lehetseges atmenetet vegtelen sokszor tapasztal meg a rendszer, akkor az 5.1 tablazattal adott algoritmus olyan R : V ! R fuggvenyhez konvergal, amelyre vR = v  (azaz R -bol kinyerhet}o az optimalis koltsegfuggveny).

38

5.2.9 Megjegyzes Az (5.2) feltetel bal oldalan c(y) + v(y) az y allapot \egy

lepessel novelt" osszkoltsege all. Tehat az (5.2) feltetel azt mondja, hogy akkor nem baj ha hamis az altalanostas, ha az (a,y)-hoz hamisan bekerul}o x-ben az a vegrehajtasanak koltsege, azaz az (x; a; y) atmenet feltetelezese \rovidtesi" lehet}oseget takar. Mivel mi a legrosszabb esetre optimalizalunk | heurisztikusan legalabb is | latszik, hogy egy ilyen atmenet feltetelezese nem okozhat bajt. Bizonytas. Vegyuk eszre, hogy barmely (a; y) parhoz tartozo S = S (a; y) halmaz az algoritmus soran csak n}ohet. Mivel S  X es X veges es veges sok (a; y) par is van, ezert van olyan t0 id}opont, hogy t > t0 eseten az S (a; y) halmazok mar nem valtoznak, gy egy id}o utan mar az osszes lehetseges (x; a; y) atmenet1 le lesz \fedve", mivel egy (xt = x; at = a; xt+1 = y) atmenet utan mar S (a; y) 3 xt = x lesz. Tehat az algoritmus lenyegeben aszinkron dinamikus programozas alaku lesz a G:VR !VR (GR)(S; a; y) = c(y) + vR(y)

lekepezesre nezve . Csakugy, mint a 4. fejezetben konnyen lathato, hogy az aszinkron konvergencia tetelenek feltetelei teljesulnek, tehat az algoritmus altal szamolt Rt fuggvenyek sorozata tart G xpontjahoz (G kontrakcio, gy egyetlen egy xpontja van). Legyen ez a xpont R^ : 2

R^ (S; a; y) = c(y) + vR(y): ^

Bebizonytjuk, hogy QR = Q (QR de nciojara nezve lasd az (5.1) egyenletet), ahol ^

^

Q(x; a) = y2max (c(y) + v(y)): T x;a (

)

Konny}u latni, hogy QR teljesti a ^

QR(x; a) = max (c(y) + vR(y)j(S; a; y) 2 V; x 2 S ) = = max (c(y) + min QR(y; b)j(S; a; y) 2 V; x 2 S ); b ^

^

^

(5.3)

Az (x; a; y) triplet lehetseges atmenet ha y 2 T (x; a)) Hogy egyszer}ustsuk a jelolest, ha R 2 V R es T = (S; a; y), akkor R(T ) = R((S; a; y)) helyett egyszer}uen csak R(S; a; y)-t runk. 1

2

39

illetve Q az

Q(x; a) = max (c(y) + v(y)jy 2 T (x; a))

(5:4)

egyenletet. Mindket xpontegyenletnek csak egyetlen megoldasa lehet. Ha a Q kielegtene az (5.3) xpontegyenletet, akkor tehat Q = QR lenne. Mivel lattuk, hogy T (x; a)  fy 2 X jx 2 S (a; y)g (az atmenetek le vannak fedve), ezert az (5.3)ban szerepl}o maximum argumentumhalmaza b}ovebb, mint az (5.4)-ben szerepl}oe. Ahhoz, hogy ne n}ojon a maximum, { amikor a Q-t (5.3) jobb oldalaba rjuk be, { szukseges hogy a folos elemek erteke a T (x; a)-n vett maximum, azaz Q(x; a) ala essen. A \folosleges" elemek eppen azon y-ok, amelyre x 2 S (a; y), de y 2= T (x; a), azaz ezek csak hamis potencialis megel}oz}ok lehetnek. Azonban feltettuk, hogy ezekre ^

c(y) + v(y)  Q(x; a) tehat a maximumot (5.3)-ban ezek nem befolyasoljak, kovetkezeskeppen Q valoban teljesti (5.3)-at is. 2

40

6. Fejezet Szamtogepes szimulaciok Az el}oz}o fejezetekben megismert matematikai modellek es algoritmusok konkret ellen}orzesere szamtogepes szimulaciokat kesztettem. Erre a celra egy altalanos szofvert fejlesztettem ki, mellyel tetsz}oleges meger}osteses modell szimulacio ja megepthet}o.

6.1 A kserleti rendszer es kornyezete Az adaptv aszinkron DP algoritmusbol ketfele valtozat keszult el. Az egyik az egyszer}u DC modellt alkalmazza (WOG - Without Generalization), mg a masik a modell fogalomkepzesi lehet}oseggel ellatott valtozata (WG - With Generalization). A kserletek celja, hogy igazolja a WG modell josagat a WOG modellel szemben. A rendszer negy reszb}ol tev}odik ossze:

 A Rendszer!Kornyezet Interface tulajdonkeppen a rendszer vegrehajto egy-

seget kepezi. Minden egyes operatorra manipulatorfuggvenyeket adunk meg, melyek az operatorok kornyezetre gyakorolt hatasatrjak le.

 A Kornyezet ! Rendszer Interface a rendszer szenzori resze, melyben minden egyes elem egy szenzor, es a kornyezet ezen szenzorokat alltja be az allapotanak megfelel}oen.

 A Long Term Memory (LTM) vagy Hosszutavu Memoria az altalanostasi algoritmus altal letrehozott graf.

41

 A Short Term Memory (STM) vagy Rovidtavu Memoria. Az STM-et az ese-

menyek sz}uresere hasznaljuk. Ha ugyanis minden kornyezetb}ol jov}o esemenyt felvennenk az LTM{ben, akkor ez a nagy memoria igeny kovetkezteben problemakat okozna. A rengeteg megjegyzett informacio nagy resze raadasul a celok elerese szempontjabol valoszn}uleg felesleges is. Az egyszer}useg kedveert csak azokat az esemenyeket vesszuk fel az LTM{be, amelyek a celhoz kozel vannak. Pontosabban, ha Tt triplet elerte a celt, akkor felvesszuk a Tt; Tt ; . . . Tt k tripletet, ahol k rogztett szam, amit az STM hosszanak nevezzuk. Az STM tulajdonkeppen egy lyukas verem. Ezzel az eljarassal azt erjuk el, hogy a graf szelessegeben jobban n}o, mint melysegeben. 1

A rendszernek ket m}ukodesi allapota van: a tanulasi allapotban modostja a bels}o reprezentacio jat, mikozben az operatorok kivalasztasara is hasznalja. A m}ukodesi allapotban az LTM-et a rendszer, csak hasznalja, de nem epti. A szimulalt vilag, melyben a robot (rendszer) mozog, diszkret pontokbol { egy veges racs racspontjaibol { all (6.1 abra). A vilagban csak a robot mozog, minden mas statikus. A racs minden pontjaban egyszerre egy elem lehet a kovetkez}o objektumok kozul: taplalek (F{ food), akadaly (B{block), uresseg (E{empty), vagy a robot (R{robot). A robot a kornyezetet egy olyan szemen keresztul erzekeli, amelyik minden iranyban lat, tehat az osszes szomszedos pontot latja, egy bizonyos tavolsagig. A robot a kornyezetere a kovetkez}o operatorok vegrehajtasaval hathat: 90 {os fordulas jobbra es balra, el}orelepes, eves. A robot csak a vilag ures pontjaiban tartozkodhat es az \eves" operatort csak akkor alkalmazhatja, ha az el}otte lev}o ponton taplalek van. A robot negy iranyban nezhet es ezt a szaj helyzete hatarozza meg. Kornyezet lehet \torusz" is, ami azt jelenti, hogy ha a robot az egyik oldalon kimegy, akkor a masik oldalon bejon. Ez vonatkozik a latasara is, tehat ha a latotere tullepne a kornyezet hatarat, akkor a masik oldalon \folytatodik".

6.2 A llapot reprezentacio es egyestesi operator Az egyestesi operator megadasa el}ott mindenkeppen tudnunk kell a robot allapotainak tarolasi modjat. A rendszer szenzor-vektor forma jaban tarolja informacioit 42

6.1. abra: Robot es kornyezete

A jobbra nez}o robot 5  5{os teruletet lat. Ebben az esetben a szenzorain a EBEEEEEEFEEEEEBEEEEBEFEEE0 sorozatot erzekeli.

az allapotarol. Az vektor egyes pozcioin a kulvilag negyfele targyanak megfelel}oen negyfele szimbolum allhat: a B,R,E es az F bet}uk valamelyike (6.1 abra). Ehhez vettuk meg az \ehseg-szenzort", ami arrol ad informaciot, hogy a robot evett-e. Ez nulla ha \ehes" es egyre valt ha sikerul ennie. Ez tulajdonkeppen a reinforcement jelet (c(y)-t) reprezentalja. Miel}ott raternenk az egyestesi operatorra, de nialnunk kell a kategoriakat is. A ketegoriakat is vektorral de nialjuk. Bevezetjuk a \" szimbolumot a vektorokat reprezentalo szimbolumok abecejebe. Igy az \E  F " vektor pl. az fE g  A  fF g  A halmazt reprezentalja, ahol A = fR; B; F; E g. Vegyunk most ket vektort u {t es u {t. Az egyestessel kepz}od}o u vektor adott pozcio jan pontosan akkor all \", ha az u es u megfelel}o pozcio jan kulonboz}o jelek allnak, egyebkent a kozos jel all az adott pozcion. Lathato, hogy az u [ u  u t u tartalmazas all a t operatorra, tehat az operator b}ovtes tpusu. 1

2

1

2

1

2

1

2

6.3 A kserletek modszertana A kserleteket 10  14{es vilagokban vegeztuk, mikozben a robot szemenek felbontasa 3  3{as. A vilagok torusz tpusuak voltak. A taplalekot es az akadalyt jelent}o elemeket meghatarozott valoszn}useggel helyeztuk el. Annak a valoszn}useget, hogy egy racspontra taplalek kerul P (F ){el es annak, hogy akadaly kerul P (B ){vel jeloltuk. A kserletet tanulasi ciklusokba szerveztuk. A tanulasi ciklus elejen rogztett 43

valoszn}useggel generalunk egy vilagot, amelyben a tanulasi probakat (trial) korszakokba szervezzuk (epoch), majd egy tesztelest vegzunk. Egy trial addig tart, amg nem teljesul a cel azaz amg a robot nem talal taplalekot, vagy amg le nem telik az el}ore meghatarozott probalkozasi id}o (timeout). A timeout{ra azert van szukseg, mert megtortenhet, hogy a robot vegtelen ciklusba kerul, vagyis nem jut el a taplalekig. Ez a korlat minden esetben 1000 volt. Minden epoch 40 trialt tartalmazott, es ezutan a tesztelunk (6.2 abra). A teszteles 500 trialt jelentett ugy, hogy a robot nem tanult. A tesztelest mindig ugyanabban, a kserletsorozat elejen rogztett tesztvilagban vegeztuk el. A teszt eredmenye a taplalek eleresehez szukseges atlagos lepesszam. Egy kserlet 200 tantasi ciklusbol allt. Minden ciklus vegen

kísérlet tanítás* generálás

epoch

teszt

trial *

trial *

step *

step *

6.2. abra: A kserletek menete

A {al jelzett eljarasok ciklusok. Az egyes ciklusok ismetlesi szama: tantas: 200, epoch{ trial: 40, teszt-trial: 500.

rogztjuk az aktualis teszteredmenyeket. A kovetkez}o tanulasi ciklus az el}oz}o ciklus alatt kialaktott memoriaval, de mar mas vilagban tortenik.

44

6.4 Tanulasi eredmenyek Az els}o kserletsorozatban a robot s}ur}u vilagokban tanulhatott. Itt egy akadaly el}ofordulasanak valoszn}usege \nagy" volt; P (F ) = 0:05; P (B ) = 0:15. A tesztvilag a 6.3 abran lathato. A 6.4 abran egy tipikus s}ur}u vilagot lathatunk. Az eredmenyeket bemutato 6.5 abran jol lathato, hogy a WG robot elerte az optimalis lepesszamot, mg a WOG robot meg a 200-adik tanulasi ciklus utan sem volt kepes erre. A

6.3. abra: \Tesztvilag"

6.4. abra: Tipikus s}ur}u vilag 6.6 abran lathatjuk, a WG es a WOG robot altal eptett grafok nagysagat. A WG robot grafjanak nagysaga csupan fele a WOG robotenak, ennek ellenere jobb teljestmenyt nyujtott. Ez azert lehetseges, mert a WG robotban ugyanazok az informaciok megtalalhatok (es meg tobb is), mint a WOG robotban, csak a reprezentacio kompaktsaga miatt, ez kevesebb helyett foglal el. A graf csokkenese kihat a feldolgozasi 45

Åtlagos lépésszám

35 30 25 20 15

WOG

10 5 WG

0 0

50

100

150

200

Tanulási ciklus

6.5. abra: Futtatasi eredmenyek

Az abran a taplalek megszerzesehez szukseges atlagos lepeszam lathato a WOG es a WG robot eseteben.

sebessegre is. A 6.7 abran a \gondolkodasi"-id}o alakulasat lathatjuk. A gondolkodasi id}ot ugy kapjuk meg, hogy minden tanulasi ciklus utan a teszt masdopercben mert futasi idejet elosztjuk az atlagos lepesszammal, azaz a gondolkodasi id}o 500 elemi dontes (az algoritmusban 500 ciklus-lepes lefutasanak) idejet adja meg. Itt is a WG robot bizonyult jobbnak, hiszen tobb mint ketszer gyorsabban vegezte el a teszteket, mint a WG robot. A masik menyiseg, ami szinten jol mutatja a WG robot folenyet, a memoria-informacio hanyad (MIH), amit 1/(atlagos lepesszamgraf csomopontjainak szama){kent de nialunk. A 6.8 abran lathato, hogy a WG robot MIH-e tobb mint haromszorosa a WOG robotenak.

6.5 Kserlet \ritka" vilagokban Mint a dolgozat elejen azt mar emltettuk, a fogalomalkotas lehet}osege egy robot szamara olyan helyzetekben is el}onyt jelenthet, amelyekben eddig meg nem volt. A kovetkez}o kserlet ennek megmutatasara iranyul. Az els}o kserlettel ellentetben, most a tanulasi folyamatot ritka vilagokban futtatjuk le, mg a tesztvilag az el}oz}o kserletbeli teszvilag marad. Azt varjuk, hogy a megvaltozott { ingerszegenyebb { kornyezet miatt teljestmeny csokkenes lep fel a ket robotnal, s mivel raadasul a 46

Csomópontok száma

1400 1200 WOG

1000 800 WG

600 400 200 0 0

50

100

150

200

Tanulási ciklus

6.6. abra: A csomopontok szamanak id}obeli alakulasa tesztvilag a tanult ritka helyett s}ur}u. A vilagok parameterei a kovetkez}ok voltak: P (F ) = 0:02; P (B ) = 0:03. Az eredmenyt, mint a robotok teljestmenyromlasat az el}oz}o kserlethez kepest, a 6.9 abran lathatjuk. Jol meg gyelhet}o, hogy a WOG robot teljestmeny romlasat mutato gorbe fole megy a WG robot gorbejenek. Vagyis a WOG robot atlagos lepesszama nagyobb mertekben n}ott meg, mint a WG robote.

47

30

Gondolkodási idô

25 20 WOG

15 WG

10 5 0 0

50

100

150

200

Tanulási ciklus

6.7. abra: A gondolkodasi id}ok id}obeni alakulasa

4.5

MIH arány (WG/WOG)

4.0 3.5 3.0 2.5 2.0 1.5 1.0 0

50

100

150

200

Tanulási ciklus

6.8. abra: Memoria-informacio hanyad arany

Ezen az abran a WG/WOG MIH-enek aranyat latjuk, amelyet ugy kapunk, hogy minden tanulasi ciklus utan a WG robot MIH-et elosztjuk a WOG robot MIH-evel. A MIH arany azt jellemzi, hogy a WG robot hanyszor nagyobb hatasfokkal hasznalja a memoriajat.

48

Åtlagos lépésszám különbségek

15 WOG

10

5

0 WG

-5 0

50

100

150

200

Tanulási ciklus

6.9. abra: A teljestmeny romlasa ritka vilagok eseten

A teljestmeny romlasat, azaz a lepesszam novekedesenek merteket adjuk meg a ritka vilagban valo tanulas eseten a s}ur}u vilagban valo tanulashoz viszonytva, mindket robot eseteben.

49

7. Fejezet O sszefoglalas A dolgozatban optimalis dontesi strategiakat vizsgalok az un. kockazat erzekeny Markov dontesi folyamatok kereten belul. A dolgozat kozponti kerdese, hogy hogyan lehet optimalis dontesi strategiakat kialaktani ha a dontesi modellt csak reszlegesen ismerjuk. A dolgozatban az un. koltsegfuggveny alapu algoritmusokkal foglalkozom. Az ilyen algoritmusok (dontesi fuggvenyek) gyakorlati alkalmazhatosagat korlatozza, hogy a koltsegfuggveny pontos reprezentacio jat kovetelik meg { a tarigeny az allapotok szamaval linearisan n}o. A dolgozatban bevezettem egy olyan csokkentett tarigeny}u reprezentaciot, melyb}ol az optimalis politika meg rekonstrualhato. Megadok egy algoritmust es egy szukseges feltetelt, mely mellett az algoritmus optimalitas }orz}o kompakt reprezentaciot keszt. Ennek bizonytasa harom lepesben zajlik. Az eredmenyeket kserletekkel is alatamasztom. A jov}oben erdemes lenne elmeleti szempontbol is megvizsgalni az un. rekurzv altalanostas lehet}oseget, amikor a kialaktott fogalmakat a rendszer ujrafelhasznalhatja mas fogalmak alkotasara is [6]. Ennek a modszernek a buktato ja, hogy a megtanult, akaratlanul es nem felismerten rossz kategoriak tovagy}ur}uzhetnek es vegkepp elronthatjak a rendszer teljestmenyet. Masik fontos kutatasi irany annak feldertese, hogy az algoritmus mikent modostando, ha a vilag determinisztikus, de a rendszer meg gyelesei pontatlanok { es gy szamara a vilag akar nem-Markovinak is t}unhet. Ezek a kutatasi iranyok igen geretesek, mert klasszikus problemakat (mint pl. az emberi konstruktivitas, frame-ek, stb.) vizsgalnak egy uj szemszogb}ol. 50

Irodalom [1] A.G. Barto, S.J. Bradtke, and S.P. Singh. Real-time Learning and Control using Asynchronous Dynamic Programming. Technical Report 91-57, Computer Science Department, University of Massachusetts, 1991. [2] R. Bellman. Dynamic Programming. Princeton University Press, Princeton, New Jersey, 1957. [3] D.P. Bertsekas and J.N. Tsitsiklis. Parallel and Distributed Computation (Numerical Methods). Prentice-Hall, Englewood Clis, NJ, USA, 1989. [4] D. Chapman and L.P. Kaelbling. Learning from Delayed Reinforcement in a Complex Domain. TR-90-11, Teleos Research, 1990. [5] M. Heger. Consideration of risk in reinforcement learning. In Proc. of the 11 International Machine Learning Conference, 1994. (submitted).

th

[6] Zs. Kalmar, Cs. Szepesvari, and A. L}orincz. Generalized dynamic concept model as a route to construct adaptive autonomous agents. Neural Network World, 5:353{360, 1995. [7] R.E. Korf. Real-time heuristic search. Arti cial Intelligence, 42:189{211, 1990. [8] M.L. Littman. Algorithms for Sequential Decision Making. PhD thesis, Brown University, Computer Science Department, 1996. [9] S. Mahadevan and J. Connel. Automatic programming of behavior-based robots using reinforcement learning. AAAI-91, 1990. [10] S.M. Ross. Applied Probability Models with Optimization Applications. Holden Day, San Francisco, California, 1970. [11] S.P. Singh. Scaling reinforcement learning algorithms by learning variable temporal resolution models. In Proc. of the 9th Int. COnf. on Machine Learning, Morgan Kaufmann, 1992. 51

[12] R. Sutton. Temporal Credit Assignment in Reinforcement Learning. PhD thesis, University of Masschusetts, Amherst, MA, 1984. [13] R.S. Sutton. TD models: modeling the world at a mixture of time scales. In Proc. of the 12th Int. COnf. on Machine Learning, Morgan Kaufmann, 1995. [14] Cs. Szepesvari. A general framework for reinforcement learning. In Proc. of ICANN'95, pages 165{170, 1995. [15] Cs. Szepesvari and Andras L}orincz. Behavior of an adaptive self-organizing autonomous agent working with cues and competing concepts. Adaptive Behavior, 2(2):131{160, 1994. [16] R. Yee. Abstraction in Control Learning. COINS Technical Report 92-16, Dep. of Computer and Information Science, Univ. of Massachuttes, Amherst, MA, 10003, 1992.

52