Rozhodov´an´ı, markovsk´e rozhodovac´ı procesy ˇ sen´e u Reˇ ´lohy Shrom´aˇzdil: Jiˇr´ı Kl´ema,
[email protected] LS 2013/2014
C´ıle materi´ alu: Text poskytuje ˇreˇsen´e u ´lohy jako podp˚ urn´ y v´ yukov´ y materi´al ke cviˇcen´ım v pˇredmˇetu A4B33ZUI.
1
Jednotliv´ a rozhodnut´ı, bayesovsk´ e rozhodov´ an´ı
Pˇ r´ıklad 1. (AIMA, 16.10): Jdete si koupit ojet´e auto do bazaru. V u ´vahu pˇripad´ a, ˇze si auto pˇred n´ akupem provˇeˇr´ıte testem (kopnete do pneumatik, zavezete ho ke kamar´ adovi mechanikovi) a teprve pak se rozhodnete. Kaˇzd´e auto m˚ uˇze b´yt budˇ v dobr´em nebo ˇspatn´em stavu (s+ a s− ). Nechˇt se rozhodujete o konkr´etn´ım autˇe a1 , jeho bazarov´ a cena je 30000 Kˇc, trˇzn´ı cena a1 v dobr´em stavu je 40000 Kˇc. Pˇr´ıpadn´ a oprava auta (pˇrechod ze ˇspatn´eho do dobr´eho stavu) stoj´ı 14000 Kˇc. Odhadujete, ˇze auto je v dobr´em stavu a1+ s pst´ı 70%. Pˇred n´ akupem m˚ uˇzete prov´est jeden konkr´etn´ı test t1 za cenu 1000 Kˇc. Test urˇc´ı, v jak´em stavu auto je, ale s neurˇcitost´ı: P r(t1+ (a1 )|a1+ ) = 0.8 a P r(t1+ (a1 )|a1− ) = 0.35. Vypoˇctˇete stˇredn´ı ˇcist´ y zisk pokud koup´ıte a1 bez t1 . P EU (kup+|{}) = s∈{+,−} U (s)P r(s|kup+) = 40000−(0.7×30000+0.3×44000) = 40000 − 34200 = 5800 Kˇc Analogie dle klasick´ eho rozhodov´an´ı: P P d∗ (t) = argmin s∈{+,−} l(d, s)P r(s|t) = argmin s∈{+,−} l(d, s)P r(s) = kup+,kup−
kup+,kup−
= argmax (10000 × 0.7 − 4000 × 0.3, 0) = argmax(5800, 0) = kup+ kup+,kup−
Z´ avˇ er 1: N´akup auta bez testu se vyplat´ı.
1
Pouˇzijte Bayes˚ uv teor´em k urˇcen´ı psti, ˇze auto je v dobr´em stavu pro oba v´ ysledky testu. P r(a1+ |t1+ (a1)) = P r(a1+ |t1− (a1)) =
P r(t1+ (a1)|a1+)×P r(a1+ ) 0.8×0.7 0.56 = 0.8×0.7+0.35×0.3 = 0.665 = P r(t1+ (a1)) P r(t1− (a1)|a1+ )×P r(a1+ ) 0.2×0.7 0.14 = 0.2×0.7+0.65×0.3 = 0.335 = 0.418 P r(t1− (a1))
0.842
Najdˇete optim´ aln´ı rozhodnut´ı o n´akupu pro oba v´ ysledky testu. EU (αt1 |t1+ (a1)) = 40000 − (0.842 × 30000 + 0.158 × 44000) = 40000 − 32240 = 7788 Kˇc EU (αt1 |t1− (a1)) = 40000 − (0.418 × 30000 + 0.582 × 44000) = 40000 − 38120 = 1852 Kˇc Analogie dle klasick´eho rozhodov´ an´ı: P d∗ (t1+ (a1)) = argmin l(d, s)P r(s|t) = argmin (10000×0.842−4000×0.158, 0) = kup+,kup−
kup+,kup−
argmin (7788, 0) = kup+ kup+,kup− P d∗ (t1− (a1)) = argmin l(d, s)P r(s|t) = argmin (10000×0.418−4000×0.582, 0) = kup+,kup−
kup+,kup−
argmin (1852, 0) = kup+ kup+,kup−
Z´ avˇ er 2: N´akup auta se vyplat´ı pˇri pozitivn´ım i negativn´ım v´ysledku testu. Uˇz z toho plyne nulov´a VPI testu – test nem´a potenci´al zmˇenit rozhodnut´ı pˇri jak´emkoli v´ysledku.
Urˇcete VPI testu t1 . Navrhnˇete optim´aln´ı strategii pro potenci´aln´ıho kupce auta a1 . EU (α|{}) = max(5800, 0) = 5800 Kˇc EU (αt1 |t1+ (a1)) = max(7788, 0) = 7788 Kˇc EU (αt1 |t1− (a1)) = max(1852, 0) = 1852 Kˇc V P I(t1 (a1 )) = (P r(t1+ (a1)) × 7788 + P r(t1− (a1)) × 1852) − 5800 = (0.665 × 7788 + 0.335 × 1852) − 5800 = 5800 − 5800 = 0 Kˇc Jde o ”tvrdou” nulu, lze zjistit rozeps´an´ım: P r(t1+ (a1)) × (10000 × P r(a1+ |t1+ (a1)) − 4000 × P r(a1− |t1+ (a1))) + P r(t1− (a1)) × (10000 × P r(a1+ |t1− (a1)) − 4000 × P r(a1− |t1− (a1))) = 10000 × (P r(a1+ , t1+ (a1)) + P r(a1+ , t1− (a1)))−4000×(P r(a1− , t1+ (a1))+P r(a1− , t1− (a1))) = 10000×P r(a1+ )− 4000 × P r(a1− ) = 5800 Kˇc V P I(t1(a1)) − Cost(t1(a1)) = −1000 < 0 Z´ avˇ er 3: Logick´y v´ysledek. Test v ˇz´adn´em z pˇr´ıpad˚ u nevede ke zmˇenˇe rozhodnut´ı, m´a nulovou hodnotu, pˇri zapoˇcten´ı ceny dokonce z´apornou. Ide´aln´ı strategie je koupit auto
2
bez testu. Test by musel b´yt v´yraznˇe citlivˇejˇs´ı, aby se vyplatil. Pˇresnost testu (pˇriˇcemˇz trivi´aln´ı klasifik´ator ”dobr´y stav” m´a pˇresnost 0.7): P r(t1+ (a1), a1+ ) + P r(t1− (a1), a1− ) = 0.8 × 0.7 + 0.65 × 0.3 = 0.755
Pˇ r´ıklad 2. Chyst´ ate se na cestu ze San Francisca do Oaklandu. M´ ate dvˇe moˇznosti, do Oaklandu se chcete dostat co nejdˇr´ıve. M˚ uˇzete jet autem pˇres Bay Bridge nebo po ˇzeleznici vedouc´ı tunelem pod z´ atokou. Na Bay Bridge b´yvaj´ı ˇcasto z´ acpy (v danou ˇc´ ast dne zhruba ve 40% pˇr´ıpad˚ u). Pˇri norm´ aln´ım provozu trv´ a cesta pˇres Bay Bridge 30 minut, pokud je z´ acpa, trv´ a cesta 1 hodinu. Vlakem cesta trv´ a 40 minut. Pokud nem´ ame ˇz´ adnou informaci o provozu na mostˇe, vyplat´ı se jet autem nebo vlakem? EU (vlak|{}) = 40 P min EU (auto|{}) = z∈{+,−} U (z)P r(z|auto) = 0.4 × 60 + 0.6 × 30 = 42 min Z´ avˇ er 1: Cesta vlakem je rychlejˇs´ı.
Pˇredpokl´ adejme, ˇze z webu dopravn´ıch informac´ı lze za 5 minut upˇresnit dopravn´ı situaci na Bay Bridge. V´ıme, ˇze pokud je most skuteˇcnˇe ucpan´ y, str´ anka ˇr´ık´ a tot´eˇz s 90% pravdˇepodobnost´ı. Pokud most nen´ı ucpan´ y, str´ anka indikuje dopravn´ı z´acpu ve 20% pˇr´ıpad˚ u. Jak se zmˇen´ı pravdˇepodobnost z´acpy na mostˇe s dopravn´ı informac´ı? Z Bayesova vztahu: P (zpred |zreal )P (zreal ) 0.36 = P0.9×0.4 P (zpred ) (zpred ) = P (zpred ) P (zpred |¬zreal )P (¬zreal ) 0.12 = P0.2×0.6 P (¬zreal |zpred ) = P (zpred ) (zpred ) = P (zpred ) 0.36 P (zreal |zpred ) = 0.36+0.12 = 0.75 0.12 P (¬zreal |zpred ) = 0.36+0.12 = 0.25
P (zreal |zpred ) =
Pozn: P (zpred ) = 0.48, and P (¬zpred ) = 0.52. P (¬zpred |zreal )P (zreal ) = 0.1×0.4 P (¬zpred ) 0.52 = 0.07 P (¬zpred |¬zreal )P (¬zreal ) = = 0.8×0.6 P (¬zpred ) 0.52 = 0.93
P (zreal |¬zpred ) = P (¬zreal |¬zpred )
Co budeme dˇelat, jestliˇze dopravn´ı info pˇredpov´ıd´a z´acpu? Co budeme dˇelat v opaˇcn´em pˇr´ıpadˇe?
3
EU (auto|zpred ) = P (zreal |zpred )×60+P (¬zreal |zpred )×30 = 0.75×60+0.25×30 = 52.5 min EU (auto|¬zpred ) = P (zreal |¬zpred )×60+P (¬zreal |¬zpred )×30 = 0.07×60+0.93× 30 = 32 min Z´ avˇ er 2: Pˇri pˇredpovˇedi z´acpy na mostˇe pojedeme vlakem, v opaˇcn´em pˇr´ıpadˇe autem.
Je u ´ˇceln´e str´ avit 5 minut zjiˇstov´an´ım dopravn´ıch informac´ı nebo je v´ yhodnˇejˇs´ı okamˇzitˇe vyrazit? Pokud dopravn´ı info pˇredpov´ıd´a z´acpu, pojedeme vlakem a naopak. J´ızda vlakem bude trvat 40 min, doba j´ızdy autem v pˇr´ıpadˇe pˇredpovˇedi voln´eho mostu je 32 minut. Tyto ˇcasy mus´ıme v´aˇzit pravdˇepodobnost´ı obou stav˚ u dopravn´ıho infa a k obˇema pˇriˇc´ıst 5 min potˇrebn´ych ke zjiˇstˇen´ı pˇredpovˇedi. Do Oaklandu tedy doraz´ıme v pr˚ umˇeru za: U (zpred ) = 5 + P (zpred ) × 40 + P (¬zpred ) × 32 = 5 + 0.48 × 40 + 0.52 × 32 = 40.8 Tento ˇcas porovn´ame s ide´aln´ı volbou bez znalosti dopravn´ıch informac´ı. Tou je cesta vlakem za 40 minut. Z´ avˇ er 3: Dopravn´ı informace n´am pom´ahaj´ı zv´yˇsit kvalitu rozhodnut´ı. Doba 5 minut na jejich zjiˇstˇen´ı je ale pˇr´ıliˇs vysok´a. Nejv´yhodnˇejˇs´ı je tedy rovnou se vydat na cestu vlakem.
2
Markovsk´ e rozhodovac´ı procesy
Pˇ r´ıklad 3. Uvaˇzujte epizod´ aln´ı dˇej se tˇremi stavy (1, 2, 3). Odmˇeny v jednotliv´ych stavech jsou -2,-1 a 0, dˇej konˇc´ı dosaˇzen´ım stavu 3. Ve stavech 1 a 2 lze aplikovat akce a a b. Akce a vede s pravdˇepodobnost´ı 20% k setrv´ an´ı ve stavu, s pravdˇepodobnost´ı 80% vede k pˇrechodu z 1 do 2 resp. z 2 do 1. Akce b vede s pravdˇepodobnost´ı 90% k setrv´ an´ı ve stavu, s pravdˇepodobnost´ı 10% vede k pˇrechodu do stavu 3. Kvalitativnˇe se pokuste odhadnout optim´aln´ı taktiku ve stavech 1 a 2. Snaˇz´ıme se maximalizovat odmˇenu. Pokraˇcov´an´ım dˇeje pouze roste z´aporn´a odmˇena, je proto vhodn´e usilovat co nejrychleji o dosaˇzen´ı stavu 3 a ukonˇcen´ı dˇeje. Souˇcasnˇe plat´ı, ˇze pˇrechod do 3 pomoc´ı akce b je relativnˇe nepravdˇepodobn´y, i po ˇsesti pokusech je st´ale vˇetˇs´ı neˇz 50% pravdˇepodobnost, ˇze dˇej jeˇstˇe nebyl ukonˇcen. Stˇredn´ı poˇcet pokus˚ u vedouc´ıch k ukonˇcen´ı dˇeje je 10 (pro p = 0.1: E = p + 2p(1 − p) + 3p(1 − p)2 + · · · = 1/p = 10). Nen´ı proto vhodn´e usilovat o pˇrechod do stavu 3 pˇr´ımo ze stavu 2. Rozd´ıl v ohodnocen´ı akce b mezi stavy 1 a 2 bude ve stˇredn´ı hodnotˇe 10, proto se vyplat´ı
4
nejprve pˇrej´ıt ze stavu 2 do stavu 1 a vyuˇz´ıt pˇritom relativnˇe vysok´e u ´spˇeˇsnosti akce a. Teprve pot´e se budeme pokouˇset o pˇrechod do stavu 3. Z´ avˇ er 1: Jako optim´aln´ı taktika se jev´ı π ∗ = (b, a, N U LL).
Fromalizujte jako MDP. Aplikujte iteraci taktiky. Vyjdˇete z taktiky π0 = (b, b, N U LL) a podrobnˇe ilustrujte konvergenci k optim´aln´ı taktice. Inicializace: π0 = (b, b, N U LL), U0 = (0, 0, 0). Iterace 1: Vyhodnocen´ı taktiky: U1 (1) = −1+0.9×U1 (1), U1 (2) = −2+0.9×U1 (2), U1 (3) = 0, U1 (1) = −10, U1 (2) = −20, (lze ˇreˇsit pomoc´ı DP, ale snadno i analyticky). Vylepˇsen´ı taktiky: Q1 (a, 1) = −1 + 0.2 × U1 (1) + 0.8 × U1 (2) = −19, Q1 (b, 1) = −1 + 0.9 × U1 (1) + 0.1 × U1 (3) = −10, Q1 (a, 1) < Q1 (b, 1) → ve stavu 1 vol´ıme b, Q1 (a, 2) = −2 + 0.8 × U1 (1) + 0.2 × U1 (2) = −14, Q1 (b, 2) = −2 + 0.9 × U1 (2) + 0.1 × U1 (3) = −20, Q1 (a, 2) > Q1 (b, 2) → ve stavu 2 vol´ıme a, π1 = (b, a, N U LL). Iterace 2: Vyhodnocen´ı taktiky: U2 (1) = −1+0.9×U2 (1), U2 (2) = −2+0.8×U2 (2)+0.2×U2 (1), U2 (1) = −10, U2 (2) = −12.5, (opˇet analytick´e ˇreˇsen´ı). Vylepˇsen´ı taktiky: Q2 (a, 1) = −1 + 0.2 × U2 (1) + 0.8 × U2 (2) = −13, Q2 (b, 1) = −1 + 0.9 × U2 (1) + 0.1 × U2 (3) = −10, Q2 (a, 1) < Q2 (b, 1) → ve stavu 1 vol´ıme b, Q2 (a, 2) = −2 + 0.8 × U2 (1) + 0.2 × U2 (2) = −12.5 Q2 (b, 2) = −2 + 0.9 × U2 (2) + 0.1 × U2 (3) = −13.25 Q2 (a, 2) > Q2 (b, 2) → ve stavu 2 vol´ıme a, π2 = (b, a, N U LL), nedoˇslo ke zmˇenˇe taktiky, STOP. Z´ avˇ er 2: Potvrdili jsme pˇredchoz´ı z´avˇer, optim´aln´ı taktikou je π ∗ = (b, a, N U LL).
Znovu aplikujte iteraci taktiky. Tentokr´at vyjdˇete z taktiky π0 = (a, a, N U LL). Co se stane? Jak´e je moˇzn´e ˇreˇsen´ı? Inicializace: π0 = (a, a, N U LL), U0 = (0, 0, 0). Iterace 1: Vyhodnocen´ı taktiky: U1 (1) = −1 + 0.2 × U1 (1) + 0.8 × U1 (2), U1 (2) = −2 + 0.8 × U1 (1) + 0.2 × U1 (2), (soustava rovnic nem´a ˇreˇsen´ı)
5
(DP ˇreˇsen´ı nekonverguje, ohodnocen´ı stav˚ u roste k ∞). ˇ sen´ım je zaveden´ı sr´aˇzkov´eho ˇcinitele γ. Soustava rovnic pˇrestane b´yt Z´ avˇ er 3: Reˇ singul´arn´ı. Je tˇreba si ale uvˇedomit, ˇze ˇreˇs´ıme jinak formulovanou u ´lohu a pro n´ızk´e hodnoty γ by mohlo doj´ıt k tomu, ˇze optim´aln´ı taktika se zmˇen´ı. Upˇrednostn´ıme okamˇzit´y zisk a m˚ uˇzeme i ve stavu 2 jako optim´aln´ı volit akci b.
Pˇ r´ıklad 4. Uvaˇzujme hru dvou hr´ aˇc˚ u na hern´ım pl´ anu o ˇctyˇrech pol´ıch. Kaˇzd´y z hr´ aˇc˚ u m´ a jeden k´ amen a jeho c´ılem je dostat sv˚ uj k´ amen na opaˇcnou stranu hern´ıho pl´ anu (hr´ aˇc A se z pole 1 mus´ı dostat na pole 4, hr´ aˇc B z pole 4 na pole 1). V´ıtˇez´ı ten hr´ aˇc, kter´emu se to podaˇr´ı prvn´ımu. Hr´ aˇc A t´ ahne jako prvn´ı. Pˇr´ıpustn´e akce jsou pohyby vlevo a vpravo na sousedn´ı pole, nelze z˚ ustat st´ at a vzd´ at se tahu, nelze t´ ahnout mimo hern´ı pl´ an. Pokud je na vedlejˇs´ım poli soupeˇr˚ uv k´ amen, je v´ysledkem pohybu pˇreskoˇcen´ı kamene (pˇr´ıklad: je-li A na pozici 3 a B na pozici 2 je v´ysledkem pohybu A vlevo posun A na pozici 1).
Kter´ y z hr´ aˇc˚ u vyhraje? Naznaˇcte klasick´e ˇreˇsen´ı probl´emu pomoc´ı prohled´av´an´ı stavov´eho prostoru. Stav hry je d´an pozic´ı obou hr´aˇc˚ u, lze jej tedy zapsat jako uspoˇr´adanou dvojici (sA , sB ). Existuje celkem 11 r˚ uzn´ych dosaˇziteln´ych stav˚ u (pro kaˇzdou pozici kamene A existuj´ı tˇri pozice kamene B, stav (4, 1) je nedosaˇziteln´y). Standardn´ı ˇreˇsen´ı je realizov´ano procedurou MiniMax. Hern´ı strom je na obr´azku n´ıˇze (hodnocen´ı je z pohledu hr´aˇce A, kter´y je tedy maximalizaˇcn´ım hr´aˇcem). Jedin´y probl´em je v tom, ˇze u ´loha obsahuje cykly a standardn´ı MiniMax s prohled´av´an´ım do hloubky by skonˇcil v nekoneˇcn´em cyklu. Proto je tˇreba prov´est drobn´e u ´pravy. Expandovan´e stavy ukl´ad´ame na z´asobn´ık a pokud je detekov´an cyklus, oznaˇc´ı se hodnota stavu jako “?” a vˇetev se ukonˇc´ı. Pˇri propagaci ohodnocen´ı se potom racion´alnˇe pˇredpokl´ad´a, ˇze max(1,?)=1 a min(-1,?)=-1. To pro danou hru, kde nejsou v´ıtˇezstv´ı a prohry r˚ uzn´e kvality, jako ˇreˇsen´ı zcela postaˇcuje.
6
Z´ avˇ er 1: Pro hry dvou hr´aˇc˚ u je klasick´ym ˇreˇsen´ım MiniMax. Pˇri optim´aln´ı strategii obou hr´aˇc˚ u zv´ıtˇez´ı A.
Lze tuto u ´lohu formulovat a ˇreˇsit jako MDP? Je to v´ yhodn´e? Jak by se u ´loha musela zmˇenit, aby to v´ yhodn´e bylo? Z´ avˇ er 2: Kaˇzd´y prohled´avac´ı probl´em lze formulovat jako MDP. Pˇrevod je rutinn´ı: stavy a akce jsou identick´e, c´ılov´e stavy se mapuj´ı na stavy termin´aln´ı u MDP, pˇrechodov´a matice je deterministick´a, odmˇena je invertovanou cenovou funkc´ı. V pˇr´ıpadˇe deterministick´ych akc´ı pouˇzit´ı MDP v´yhodn´e nen´ı. Formalismus je zbyteˇcnˇe sloˇzit´y a v´ypoˇcetnˇe n´aroˇcn´y. Vhodn´ym ˇreˇsen´ım by se stalo pro stochastick´e varianty probl´emu.
Probl´em formulujte jako MDP. Nechˇt je VA (s) je hodnota stavu pokud je na tahu hr´ aˇc A, VB (s) je hodnota stavu pokud je na tahu hr´aˇc B. Odmˇena ve stavu s nechˇt je R(s), pro termin´aln´ı stavy v´ıtˇezn´e pro A je 1, pro termin´aln´ı stavy v´ıtˇezn´e pro B je -1. Nakreslete graf stavov´eho prostoru. Zapiˇste Bellmanovy rovnice pro oba hr´aˇce a aplikujte tyto rovnice v r´amci hodnotov´e iterace. Formulujte ukonˇcovac´ı podm´ınku iterace. Graf stavov´eho prostoru je na obr´azku n´ıˇze. Tahy A jsou znaˇcen´e plnou ˇcervenou ˇcarou, tahy B pˇreruˇsovanou modrou ˇcarou.
7
Bellmanovy rovnice tak´e vych´az´ı z principu MiniMaxu: a 0 VA (s) = R(s) + maxa Pss 0 VB (s ) a 0 VB (s) = R(s) + mina Pss0 VA (s ) R(s) bude pouˇzito pouze v termin´aln´ıch stavech, ohodnocen´ı zbyl´ych stav˚ u je nulov´e a ˇr´ıd´ı se pouze n´asledn´ıky. Hr´aˇc A maximalizuje ohodnocen´ı, hr´aˇc B jej naopak minimalizuje. Protoˇze akce jsou deterministick´e, kaˇzd´a akce m´a jednotkovou pst pro jednoho n´asledn´ıka a nulovou pro vˇsechny zbyl´e stavy. Hr´aˇci se v taz´ıch stˇr´ıdaj´ı, proto stˇr´ıd´ame i aplikace pˇr´ısluˇsn´ych Bellmanov´ych rovnic. Na poˇc´atku je ohodnocen´ı 11 dostupn´ych stav˚ u d´ano pouze pro R(s) termin´al˚ u, pro zbytek stav˚ u je nulov´e. Ohodnocen´ı se ˇs´ıˇr´ı postupnˇe, vyuˇz´ıv´ame graf stavov´eho prostoru, viz tabulka: s VA VB VA VB VA VB
(1,4) 0 0 0 -1 +1 -1
(2,4) 0 0 0 +1 +1 +1
(3,4) 0 0 0 +1 +1 +1
(1,3) 0 0 -1 -1 -1 -1
(2,3) 0 -1 +1 -1 +1 -1
(4,3) +1 +1 +1 +1 +1 +1
(1,2) 0 0 -1 -1 -1 -1
(3,2) 0 -1 +1 -1 +1 -1
(4,2) +1 +1 +1 +1 +1 +1
(2,1) -1 -1 -1 -1 -1 -1
(3,1) -1 -1 -1 -1 -1 -1
Ukonˇcovac´ı podm´ınkou je nulov´a zmˇena ve vektoru hodnot pro jednoho z hr´aˇc˚ u (tedy shoda VA (s) s vektorem VA (s) o dva tahy dˇr´ıve nebo stejn´e srovn´an´ı pro VB (s)). V tabulce v´yˇse je shoda pro posledn´ı dva v´ypoˇcty VB (s). Je jasn´e, ˇze ke zmˇenˇe nem˚ uˇze doj´ıt uˇz ani u VA (s), bude se odvozovat z identick´eho VB (s). Je tˇreba si uvˇedomit, ˇze vektory ohodnocen´ı stav˚ u obou hr´aˇc˚ u se v ekvilibriu neshoduj´ı. VA (s) pˇredpokl´ad´a, ˇze na tahu je hr´aˇc A a naopak. Proto nelze pˇri ukonˇcen´ı srovn´avat VA (s) a VB (s), mj. stav (3,2) sv´e ohodnocen´ı z principu pˇrep´ın´a (vyhraje ten, kdo je pr´avˇe na tahu).
8
Z´ avˇ er 3: MDP souˇcasnˇe ˇreˇs´ı probl´em pro zah´ajen´ı obˇema hr´aˇci. Ohodnocen´ı termin´aln´ıch stav˚ u je dan´e apriori. Ve stavech (2,4) a (3,4) v´ıtˇez´ı hr´aˇc A bez ohledu na to kdo je na tahu. Ve stavech (1,3) a (1,2) v´ıtˇez´ı hr´aˇc B bez ohledu na to kdo je na tahu (jsou zrcadlov´ym obrazem stav˚ u (2,4) a (3,4)). Ve stavech (1,4), (2,3) a (3,2) v´ıtˇez´ı ten, kdo je pr´avˇe na tahu. MiniMax strom uveden´y dˇr´ıve pouˇz´ıv´a na r˚ uzn´ych u ´rovn´ıch stromu r˚ uzn´a ohodnocen´ı, de facto tedy kombinuje VA (s) a VB (s) dle u ´rovnˇe stromu.
Pˇ r´ıklad 5. Za dveˇ rmi je tygr (ˇ reˇ sen´ı jako POMDP). Stoj´ıte v m´ıstnosti, z n´ıˇz vedou dvoje dveˇre. V´ıte, ˇze za jednˇemi dveˇrmi je hladov´y tygr, druh´e ˇ je slyˇset, dveˇre garantuj´ı bezpeˇcn´y odchod z m´ıstnosti. Tygr obˇcas zaˇrve. Rev ale z jednoho poslechu nen´ı u ´plnˇe zˇrejm´e, odkud ˇrev vych´ az´ı. Chcete se z m´ıstnosti bezpeˇcnˇe a rychle dostat, v kaˇzd´em okamˇziku se m˚ uˇzete rozhodnout mezi tˇremi volbami: otevˇr´ıt dveˇre vlevo, otevˇr´ıt dveˇre vpravo nebo poˇckat aˇz tygr znovu zaˇrve. Pracujte s n´ asleduj´ıc´ımi ohodnocen´ımi: otevˇren´ı nespr´ avn´ych dveˇr´ı odpov´ıd´ a ztr´ atˇe 100, otevˇren´ı spr´ avn´ych dveˇr´ı zisku 10, ˇcek´ an´ı je spojeno se zt´ atou 1, pˇri kaˇzd´em zaˇrv´ an´ı se zm´yl´ıte v odhadu smˇeru v 15% pˇr´ıpad˚ u (uk´ aˇzete na jedny ze dveˇr´ı, ale spr´ avnˇe to bude jen v 85% situac´ı), pokud bereme v u ´vahu celou sekvenci n´ aslech˚ u, omyly jsou vz´ ajemnˇe nez´ avisl´e, tygr mezi ˇrvan´ım svoji pozici nemˇen´ı. Probl´em formalizujte jako ˇc´asteˇcnˇe pozorovateln´ y markovsk´ y rozhodovac´ı proces. POMDP = {S, A, P, R, O, Ω}, skryt´e stavy: S={T L, T R, ST OP }, TL ∼ tygr vlevo, TR ∼ tygr vpravo, STOP ∼ konec hry (byly otevˇreny dveˇre) akce: A={Li, L, R}, Li ∼ poslouchej=ˇcekej na dalˇs´ı zaˇrv´an´ı, L ∼ otevˇri lev´e dveˇre, R ∼ otevˇri prav´e dveˇre, pozorov´an´ı: O={LL, LR}, LL ∼ tygr slyˇsen vlevo, LR ∼ tygr slyˇsen vpravo, pˇrechodov´e psti (P): P r(T L|T L, Li) = 1, P r(T R|T L, Li) = 0, P r(T L|T L, L) = 0, P r(T R|T L, L) = 0,P r(ST OP |T L, L) = 1 (uv´adˇeno pouze pro TL, TR je symetrick´y), senzorick´y model (Ω): P r(LL|T L, Li) = 0.85, P r(LR|T L, Li) = 0.15, funkce odmˇeny: R(Li, T L) = −1, R(R, T L) = 10, R(L, T L) = −100.
Naleznˇete optim´ aln´ı pl´ an d´elky 1 jako funkci belief. Tj. navrhnˇete optim´aln´ı akci v z´ avislosti na tom jakou pravdˇepodobnost pˇriˇrazujete skryt´ ym stav˚ um. V jak´ ych bodech belief prostoru se bude rozhodnut´ı mˇenit? Vzhledem k tomu, ˇze m´ame pouze dva stavy, staˇc´ı belief reprezentovat jako jedin´e re´aln´e ˇc´ıslo od 0 do 1. Zapisujme jej jako b(T L), b(T R) je doplˇ nkem do jedn´e. Uˇzitek
9
akc´ı bude funkc´ı jedin´e promˇenn´e. Protoˇze v´ıme, ˇze bude line´arn´ı funkc´ı b, staˇc´ı jej pro vˇsechny akce spoˇc´ıtat pouze v krajn´ıch bodech belief prostoru, tedy pro situace, kdy jsme si naprosto jisti, ˇze tygr je vlevo nebo naopak vpravo. Viz obr´azek n´ıˇze.
Z´ avˇ er 1: Z obr´azku je tak´e zˇrejm´e, ˇze pro b(T R) > 0.9 se vyplat´ı volit akci L, pro b(T R) < 0.1 se vyplat´ı volit akci R. Pro stˇredn´ı oblast b je nejv´yhodnˇejˇs´ı akce Li. Hodnoty 0.1 a 0.9 vych´az´ı z rovnice: −100b(T R) + 10(1 − b(T R)) = −1, resp. −100(1 − b(T R)) + 10 × b(T R) = −1.
Kolik je podm´ınˇen´ ych pl´ an˚ u d´elky 2? Urˇcete uˇzitek alespoˇ n jednoho z nich (opˇet p˚ ujde o funkci belief). Bude nˇekter´ y z pl´an˚ u ˇcistˇe dominov´an pl´any jin´ ymi? Podm´ınˇen´y pl´an d´elky 2 je takov´y pl´an, kter´y urˇcuje akci pro dan´y okamˇzik a n´aslednˇe akci pro okamˇzik po pˇr´ıˇst´ım zaˇrv´an´ı. Protoˇze zaˇrv´an´ı m˚ uˇzeme slyˇset ze dvou stran a pro kaˇzd´y smˇer m˚ uˇzeme volit jinou akci, bude m´ıt pl´an tˇri akce [A1 if LR then A2 else A3 ], k´ odovat budeme jako [A1 A2 A3 ]. Teoreticky m´ame 27 pl´an˚ u (sekvence d´elky 3 nad abecedou tˇr´ı akc´ı, tj. 33 moˇznost´ı). Vˇsechny pl´any, kter´e nezaˇc´ınaj´ı akc´ı Li, ale vedou na restart hry, tj. existuje pouze 9 podm´ınˇen´ych pl´an˚ u d´elky 2. Trivi´aln´ı ohodnocen´ı je pro pl´an [Li, Li, Li]: α[LiLiLi] (b(T R) = 0) = α[LiLiLi] (b(T R) = 1) = −2, Sloˇzitˇejˇs´ı pro pl´an [LiLLi]: α[LiLLi] (b(T R) = 0) = R(Li, T L) + P r(T R|T R, Li)(P r(LL|T R, Li) × α[L] (0) + P r(LR|T R, Li)α[Li] (0))+P r(T L|T R, Li)(P r(LL|T L, Li)×α[L] (0)+P r(LR|T L, Li)α[Li] (0)) = −1 + 1(0.15 × −100 + 0.85(−1)) + 0(. . . ) = −16.85, α[LiLLi] (b(T R) = 1) = R(Li, T R) + P r(T L|T L, Li)(P r(LL|T L, Li) × α[L] (1) +
10
P r(LR|T L, Li)α[Li] (1))+P r(T R|T L, Li)(P r(LL|T R, Li)α[L] (1)+P r(LR|T R, Li)α[Li] (1)) = −1 + 1 × (0.85 × 10 + 0.15 × −1) + 0 × (. . . ) = 7.35, Z 9 pl´an˚ u poˇc´ınaj´ıc´ıch Li je jen 5 dominuj´ıc´ıch: [LiRR] pro beliefs<0.019, [LiLiR] pro beliefs 0.019-0.39, [LiLiLi] pro beliefs 0.39-0.61, [LiLLi] pro beliefs 0.61-0.981, [LiLL] pro beliefs>0.981. V prvn´ım pˇr´ıpadˇe je natolik jasn´e, ˇze stav je TR, ˇze jak´ykoli smˇer ponech´av´a akci R, ve druh´em je tˇreba TR potvrdit LR, jinak poslouch´ame d´ale, uprostˇred je nejistota tak velk´a, ˇze jak´ykoli smˇer nem˚ uˇze v´est na otevˇren´ı dveˇr´ı, d´ale symetricky . . . . Je evidentn´ı, ˇze pl´an [LiRLi] ned´av´a smysl (pokud slyˇs´ım tygra ˇrv´at vpravo, teˇzko pak otevˇru dveˇre vpravo a pokud ho uslyˇs´ım vlevo, tak budu d´ale vyˇck´avat), [LiLiL] je jeho doplˇ nkem, [LiRL] je tak´e nesmysl (otevˇru prav´e dveˇre pokud slyˇs´ım tygra vpravo a naopak). Potenci´alnˇe zaj´ımav´y je [LiLR], ale neprosad´ı se d´ıky aktu´aln´ı parametrizaci, penalta za otevˇren´ı nespr´avn´ych dveˇr´ı je pˇr´ıliˇs velk´a.
Pˇri celkov´em ˇreˇsen´ı hry je tˇreba tyto pl´any srovnat s pl´any d´elky 1, kter´e hru tak´e konˇc´ı, tedy L a R, ty evidentnˇe pˇredˇc´ı [LiLL], resp. [LiRR] pro krajn´ı beliefs. Pro doplˇ nen´ı bod pˇrepnut´ı mezi [LiRR] a [LiLiR]: 7.35 − (16.85 + 7.35)x = −2, x = 9.35/(16.85+7.35) = 0.39 Jeˇstˇe bod pˇrepnut´ı mezi [LiLiR] a [LiLiLi]: 7.35−(16.85+ 7.35)x = 9 − (101 + 9)x, x = (9 − 7.35)/(110 − 24.2) = 0.019 Z´ avˇ er 2: Je celkem 9 podm´ınˇen´ych pl´an˚ u d´elky 2. Nedominovan´ych je ale pouze 5, pokud bereme v u ´vahu i pl´any d´elky 1, tak dokonce jenom 3.
Kolikr´ at je tˇreba na zaˇc´ atku hry slyˇset ˇrev ze stejn´e strany pˇredt´ım neˇz se vyplat´ı otevˇr´ıt jedny ze dveˇr´ı? Zd˚ uvodnˇete.
11
Z bodu b) v´ıme, ˇze b(TR) mus´ı b´yt menˇs´ı neˇz 0.1 nebo vˇetˇs´ı neˇz 0.9, toho dos´ahneme ˇ [LL, LL] nebo [LR, LR]. Testujme pro [LR, LR] po dvou souhlasn´ych pozorov´an´ıch bud (pozor, b2 (T R) nelze obecnˇe poˇc´ıtat jako (1 − 0.152 ) = 0.9775): b0 (T R) = 0.5 (zaˇc´atek hry), b1 (T L) = αP r(LR|T L, Li)(P r(T L|T L, Li) × b0 (T L) + P r(T L|T R, Li) × b0 (T R)) = α × 0.15 × (1 × 0.5 + 0 × 0.5) = α × 0.15 × 0.5, b1 (T R) = αP r(LR|T R, Li)(P r(T R|T R, Li)×b0 (T R)+P r(T R|T L, Li)×b0 (T L)) = α × 0.85 × (1 × 0.5 + 0 × 0.5) = α × 0.85 × 0.5, b1 (T L) + b1 (T R) = 1 . . . α = 2 . . . b1 (T L) = 0.15, b1 (T R) = 0.85, jedno zaˇrv´an´ı nestaˇc´ı b2 (T L) = αP r(LR|T L, Li)(P r(T L|T L, Li) × b1 (T L) + P r(T L|T R, Li) × b1 (T R)) = α × 0.15 × (1 × 0.15 + 0 × 0.5) = α × 0.152 , b2 (T R) = αP r(LR|T R, Li)(P r(T R|T R, Li)×b1 (T R)+P r(T R|T L, Li)×b1 (T L)) = α × 0.85 × (1 × 0.5 + 0 × 0.5) = α × 0.852 , b2 (T L) + b2 (T R) = 1 . . . α = 1.34 . . . b1 (T L) = 0.03, b1 (T R) = 0.97, dvˇe zaˇrv´an´ı staˇc´ı. Z´ avˇ er 3: Tygr mus´ı b´yt na zaˇc´atku hry slyˇset alespoˇ n dvakr´at ze stejn´e strany, aby se vyplatilo pˇrestat ˇcekat a otevˇr´ıt dveˇre (samozˇrejmˇe otavˇreme ty, od kter´ych nebyl ˇrev slyˇset.) V´ypoˇcet je orientaˇcn´ı, protoˇze zisk za ˇcek´an´ı urˇcen´y v bodˇe b) nen´ı koneˇcn´y. M˚ uˇzeme ovˇeˇrit ohodnocen´ım n´asleduj´ıc´ı taktiky π: ˇcekej dokud poˇcet zaˇrv´an´ı z jedn´e strany nebude o 2 vyˇsˇs´ı neˇz z druh´e strany, pot´e otevˇri dveˇre s menˇs´ım poˇctem zaˇrv´an´ı. Uvaˇzujme b0 (T R) = 0 (druh´y krajn´ı stav m´a totoˇzn´e hodnocen´ı, je symetrick´y): απ = 0.852 × (10 − 2) + 0.152 × (−100 − 2) + 2 × 0.85 × 0.15 × (απ − 2) (prvn´ı ˇclen odpov´ıd´a volbˇe spr´avn´e akce R, druh´y volbˇe nespr´avn´e akce L po dvou nepravdˇepodobn´ych pˇresleˇs´ıch, posledn´ı ˇclen odpov´ıd´a n´avratu do p˚ uvodn´ıho stavu po dvou nesouhlasn´ych n´asleˇs´ıch a ztr´atˇe -2 za ˇcek´an´ı) 0.745 × απ = 3.48 − 0.51 → απ = 3.99 Z´ avˇ er 4: Tato taktika dosahuje stˇredn´ıho ohodnocen´ı 4 ve vˇsech bodech belief prostoru. Dominuje jednoduch´emu pl´anu [LiLR] a pro poˇc´ateˇcn´ı neinformovan´y stav b0 (T R) = 0.5 pˇrekon´av´a i vˇsechny ostatn´ı dosud hodnocen´e pl´any. Okamˇzit´e otevˇren´ı jednˇech ze dveˇr´ı se vyplat´ı jeˇstˇe v menˇs´ı m´ıˇre (pro silnˇejˇs´ı beliefs) neˇz se zd´alo z pl´an˚ u d´elky 1.
12
