Markovin päätösprosessien (MDP) käyttö stokastisen reaktiivisen järjestelmän mallina on melko yleistä. Yksinkertaistaen MDP koostuu tiloista, "aakkostosta" tai tapahtumista ja tilasiirtymistä. Joskus tiloille annetaan vielä erilaisia määreitä, esimerkiksi tiloissa voidaan evaluoida tilapropositioita tai -predikaatteja. Sivuutan nämä nyt tässä yhteydessä.
MDP:n tilasiirtymä on kuvaus tiloista ja aakkosista jakaumaksi tilojen yli. Siis toisinsanoen, kun olemme tietyssä tilassa, ja vuorovaikutamme MDP:n kanssa tuottamalla tietyn tapahtuman, tai havaitsemme tapahtuman (eroa ei tässä yhteydesä tarvise tehdä), MDP reagoi siirymällä satunnaisesti johonkin tilaan ja tällä siirtymisellä on tietty jakauma. Tapahtuma voi tietenkin olla myös täysin deterministinen ja johtaa yhteen uniikkiin tilaan, tämä on erityistapaus jossa jakauman tiheysfunktio saa arvon 1 jossain tilassa ja 0 muissa.
Vuorovaikutusta varten voidaan ajatella vastustaja, joka valitsee tapahtumat jollakin perusteella. En mene tässä nyt siihen teoriaan, mutta ns pelisemantiikat ovat käyttäytymisen analysoimisen malleja, jossa kaksi vastustajaa pyrkii vuorotellen valitsemaan tapahtumia, ja toinen yrittää saada aikaan virheen ja toinen estää sen; järjestelmän oikeellisuus on siis kiinni siitä, voiko "paha" vastustaja voittaa vai ei. Oletan tässä yhteydessä että meillä on vain yksi vastustaja (kutsutaan myös skeduleriksi, engl. scheduler), mutta pidän tästä sanasta enemmän.
Useimpia ominaisuuksia tutkitaan selvittämällä todennäköisyyksiä kaikkien mahdollisten vastustajien yli. Yksi tärkein rakenteellinen entiteetti on niin sanottu loppukomponentti (engl end component). Loppukomponentti on joukko tiloja ja tilasiirtymiä jolla on seuraavanlaiset ominaisuudet: Ensiksikin jokaisessa tilassa voidaan valita jokin tilasiirtymä (ellei sitten tila ole yksinään joukossa), ja toisekseen, kaikki tällaisen tilasiirtymän mahdolliset lopputulemat ovat myös joukossa. Kolmanneksi, jokaisesta tilasta on mahdollista (so. nollaa suuremmalla todennäköisyydellä) päästä jokaiseen muuhun joukon tilaan seuraamalla joukon siirtymiä.
Loppukomponentti C on maksimaalinen, jos MDP:stä ei löydy loppukomponettia, jonka osajoukko C olisi. Maksimaaliset loppukomponentit muodostavat ekvivalenssiluokat MDP:n tiloille. Osa tietenkin on triviaaleja, eli sisältää vain yhden tilan eikä yhtään siirtymää.
Loppukomponentit ovat tärkeitä siksi, että vastustaja joka pelaa "loputtomiin" päätyy poikkeuksetta raja-arvona johonkin loppukomponenttiin, riippumatta siitä miten se pelaa. Yksi rakenteellinen laskennallinen ongelma MDP:n osalta on niinsanottu maksimaalisten loppukomponenttien dekompositio, jossa MDP jaetaan.
Jouduin, hieman yllättäen, rakentamaan ratkaisun kysymykseen: Onko annetussa MDP:ssä ei-triviaalia loppukomponenttia. Kysymys ei ole helppo laskennallisesti. En halunnut laskea dekompositiota, koska dekompositio on neliöllinen pahimmassa tapauksessa. Koska minulla ei ollut aikaa ratkaista ongelmaa "hyvin", päädyin toteuttamaan eräänlaisen "laiskan dekomposition", jossa pyritään mahdollisimman agressiivisesti eliminoimaan transitioita ja triviaaleja loppukomponentteja. Se tuntuu toimivan hyvin, mutta pahimmassa tapauksessa (kun ei-triviaaleja loppukomponentteja ei ole, ja tietyt patologiset ehdot toteutuvat) sekin on neliöllinen.
En löytänyt vastausta kysymykseen: Onko ei-triviaalisuuden ratkaiseminen olennaisesti yhtä kompleksista kuin dekompositio. Tiedän, että dekompositiolle on olemassa ratkaisu, jossa eksponentti ei ole kaksi, vaan noin puolitoista, mutta tämä ei vastaa kysymykseeni, eli siihen onko dekompositio (olennaisesti) välttämätöntä ei-triviaalisuuden päättämiseksi. Epäilen että se on.
Tarvitsin tätä siksi, että olen kirjoittamassa työkalua, joka tarkastaa onko MDP tosiasiallisesti deterministinen. Tämä tarkoittaa siis sitä, että kun MDP:tä tarkastellaan sivuuttamalla tietyt tapahtumat (niiden ajatellaan olevan vastustajan tavoittamattomissa), vastustaja ei kykene saamaan järjestelmää käyttäytymään eri tavoilla toistamalla jotakin strategiaa. Tämä on tietyissä tietoturva- ja luotettavuusominaisuuksissa mielenkiintoisia kysymyksiä.
Ei kommentteja:
Lähetä kommentti