Markovův rozhodovací process

From Simulace.info
Jump to: navigation, search


Úvod

je pojmenován po ruském matematikovi Andrej Markov[1], který je znám pro své teorie stochastických procesů. Jeho teorie byly později nazvány Markovovými řetězci. Umožňují poskytnout pomocí matematického rámce rozhodnout v situacích, kdy výsledky jsou částečně náhodné, nebo do určité míry kontrolovány uživatelem. Tyto procesy se využívají ve studiu optimalizačních problémů řešených díky dynamického programování a zpětnovazebního učení (Reinforcement learning)[2]. Dodnes jsou tyto metody využívány v rozmanitých procesech např. robotice, automatizaci řízení, ekonomii nebo průmyslové výroby.

Zpětnovazební učení (Reinforcement learning)

Je typ strojového učení. Umožňuje strojům a softwarovým agentům automaticky určit ideální chování v konkrétním kontextu, aby maximalizovali jeho výkon. Jednoduchá zpětná vazba odměny se vyžaduje, aby se agent mohl naučit své chování; toto je známé jako zpětnovazebný signál. Existuje mnoho různých algoritmů, které tento problém řeší. Ve skutečnosti je Reinforcement Learning definováno specifickým typem problému a všechna jeho řešení jsou klasifikována jako algoritmy Reinforcement Learning. V problému má agent rozhodnout o nejlepší akci, kterou vybere na základě svého aktuálního stavu. Když se tento krok opakuje, problém je známý jako Markovův rozhodovací proces.

Agenti založení na užitku (Utility-based agents)

Agent založený na užitku[3] se rozhoduje s cílem maximalizovat svůj očekávaný užitek, a může tak být vyčíslen skutečným číslem.

Mějme tedy funkci užitku, která mapuje možné stavy světa na reálné číslo:

u: O

kde O je soubor možností, které reprezentují konečné stavy světa, na které agent může dosáhnout.

Agent si vybere stav, ve kterém očekává nejvyšší výsledek. Tato situace je poměrně jednoduchá, jestliže senzory agentů poskytují perfektní a nezkreslené informace a akce agentů vždy povede přesně ke stavu, který agent očekává (jinými slovy v případě, že prostředí agentů je přístupné a deterministické). Obvykle tomu tak není. Možnosti jsou to, co agent vnímá, a proto nemusí být reálnými možnostmi. Vnímání by mohlo být zkreslené (senzory agentů nemusí být dokonalé) a realita se může změnit během uvažování agentů. Předpokládejme, že agent zná pravděpodobnost reaktivního stavu:

St plus1.png

když je ve stavu s podniká kroky a. Tato pravděpodobnost je vrácena funkcí

T st a st plus1.png

a nazýváme ji přechodovou(tranzitní) funkcí (transition function). Je zřejmé, že:

3vzorec.png

Očekávaný užitek akce ve stavu je následující:

4vzorec.png

kde je dostažení stavu .

Znamená to očekávaný užitek, kdy se jedná o akci a, když je agent ve stavu s. Agent si vybere akci a, která maximalizuje očekávaný užitek v příslušném stavu. Odpovídající vzorec je tedy:

5vzorec.png

Vhodným modelem pro popis chování agentů je rozhodovací Markovův proces (MDP), matematický rámec pojmenovaný po Markovovi pro modelování rozhodování v případech, kdy výsledky jsou částečně náhodné a částečně pod kontrolou rozhodovatele. Optimální politika je akce ze sady všech možných akcí, které agent může provést v určité situaci, která vede k nejvíce očekávanému užitku:

6vzorec.png

nebo

7vzorec.png

Očekávaná odměna je očekávaný užitek, který agent získá v dalším kroku své současné dané situaci, pokud udělá nejlepší možnou akci:

1vzorec.png

Pokud si můžeme vybrat, zda dostaneme stejnou odměnu v čase nebo v čase , je rozumné si zvolit čas , jelikož naše budoucnost je vždy nejistá a nikdy nevíme, co se stane do času do času a jestli budeme vůbec ještě existovat. Proto i přes stejnou nominální částku, pro správnou mezičasovou komparaci, by budoucí odměna měla být diskontována určitým diskontním faktorem γ, který vyjadřuje neurčitost.

Faktor γ je definován (0;1).

2vzorec.png

Teoreticky je koncept agentů založených na užitku jednoduchém a přímočarém. Jeho praktická aplikace bohužel přináší řadu překážek.

  • Za prvé, ve skutečnosti je oceňování užitku, pro možné stavy světa, složitým problémem. Totéž platí pro výčet pravděpodobností dosažení jednotlivých stavů,

diskontních faktorů a vlastně všech ostatních proměnných v modelu.

  • Za druhé, řešení rovnic by mohlo být, vzhledem k jejich nelineárnímu charakteru, relativně pomalé. A konečně, přístup neřeší více cílů, zejména pokud se střetnou krátkodobé a dlouhodobé cíle.

"Neexistuje žádná taková věc, jako je oběd zdarma" (Milton Friedman)[4]. Pro jakýkoli zisk z užitku, agent potřebuje vynaložit nějaké náklady, a pouze v případě, že užitek získal s více než vynaloženými náklady, tím bude agent lepší. Proto bychom měli zavést nákladovou funkci pro jakýkoli možný stav jako kompenzaci funkce užitku. Pro zjednodušení, pokud však není uvedeno jinak, budeme počítat s čistým užitkem (tj. nástroj po odečtení nákladů potřebných k jeho dosažení). To by mohlo být skutečně buď pozitivní, nebo negativní, v závislosti na tom, zda je agent lepší nebo horší.

Příklad

Tímto se dostáváme k demonstraci jednoduchého příkladu:

předpokládejme, že agent je ve městě A a potřebuje se dostat do města B na důležité obchodní jednání. Může si vybrat ze tří možností přepravy: autem, vlakem nebo autobusem.

Jízda autem je relativně pohodlná a poměrně rychlá, ale zároveň drahá, pokud agent jede sám. Bohužel agent není dobrý navigátor a může se ztratit, což by znamenalo zmeškanou schůzku, protože se na ní dostane příliš pozdě. Také jízda delší dobu, na větší vzdálenost má za důsledek větší spotřebu paliva. Cestování vlakem je velmi pohodlné, ale pomalé, protože mezi body A a B není přímá doprava a vlak může dorazit pozdě. Náklady jsou mezi nákladem na řízení automobilu a jízdou autobusem. Autobus je nejlevnější alternativou - doprava autobusem bude téměř jistě časově spolehlivá, ale velkou nepříjemností je, že pouze jeden autobus jezdí mezi body A a B denně, který odjíždi v ne příliš vyhovující době. Znamenalo by to, že by agent musel vyrazit na cestu mnohem dřív a strávit téměř dvakrát více času na cestě než autem nebo vlakem.

Řekněme, že náklady na cestu autem jsou 15, cena vlaku je 10 a náklady na autobus jsou 5.

Užitek z pohodlí příslušných dopravních prostředků je 10 pro vlak, 7 pro auto a 3 pro autobus. Čistý užitek cestování autem, vlakem a autobusem je tedy -8,0 respektive -2.

Užitky z možných výsledků agenta jsou 10, pokud zůstane doma (a například telefonuje místo schůzky), 50, když se dostane na místo určení včas, 40, když se dostane na místo cíle příliš brzy, 30, když se dostane do cíle příliš pozdě, a - 20, když ztratí cestu (poté ani schůzka ani volání není možné - v hlubokých lesích není pokrytí mobilního operátora a obchod je ztracen). Ve skutečnosti je agent na jiné úrovni, když dorazí včas na autobus (48), na vlak (50), nebo autem (42) a každá z těchto situací je samostatným stavem. Pokud necháme zůstat agenta nečinně doma jeho míra užitku bude 0.

Pro zjednodušení jsou zde znázorněny pouze výsledky užitků znázorněných na obrázku 2.1, ale musíme spočítat všechny možnosti (tj. 9 stavů). Celkový užitek příslušného stavu je označen u.


Schéma MDP cestujícího

Obrázek 2.1 - Schéma Markovova rozhodovacího procesu (MDP) cestujícího

MDP diagram.png

Výsledky příkladu - tabulky

Výsledky hodnot tranzitní funkce jsou uvedeny v tabulce 2.1 a tabulce 2.2

Jsou v nich také uvedeny očekáváné užitky jednotlivých akcí agenta (můžeme považovat γ = 1, protože uvažujeme pouze jedno kolo)


Tabulka 2.1 - Očekávané využití výsledků jednotlivých agentů. Užitek a jeho následné upravení pro jednotlivé významy využití konkrétních dopravních prostředků, nejsou zapracovány.

Doma Autobus Včas 5%
Doma Vlak Včas 50%
Doma Auto Včas 70%
Doma Autobus Pozdě 5%
Doma Vlak Pozdě 50%
Doma Auto Pozdě 20%
Doma Auto Ztracen 10%
Doma Autobus Příliš brzy 90%
Doma Zůstat Doma 100%


Tabulka 2.2 - Výpočet očekávaných užitků možných akcí agenta

Doma Autobus Včas 5 50 -2 48 2,4
Doma Autobus Pozdě 5 30 -2 28 1,4 38
Doma Autobus Příliš brzy 90 40 -2 38 34,2
Doma Auto Včas 70 50 -8 42 29,4
Doma Auto Pozdě 20 30 -8 22 4,4 31
Doma Auto Ztracen 10 -20 -8 -28 -2,8
Doma Vlak Včas 50 50 0 50 25,0
Doma Vlak Pozdě 50 30 0 30 15,0 40
Doma Zůstat Doma 100 10 0 10 10 10

Závěr

Je zřejmé, že na základě výše uvedeného výpočtu je optimální politikou agenta jet vlakem. Výpočet pro optimální politiku není obtížný a i kdyby bylo více rozhodovacích kol, složitost úkolu by byla stále přijatelná. Hlavním problémem pro vývoj takového agenta je to, jak by odhadoval užitky a pravděpodobnosti jednotlivých situací, pokud by nebyly přednastaveny.

Zdroje

• Šalamon, T. (2011). Design of Agent-Based Models : Developing Computer Simulations for a Better Understanding of Social Processes. Řepín, Czech Republic: Bruckner Publishing

• Heyman, D.P. & Sobel, M.J. (1990). Stochastic Models, Volume 2.

• Meuleau, Hauskrecht, Kee-Eung, PeshkinLeslie Kaelbling, Thomas Dean Computer Science Department, Box 1910 Brown University, Providence, RI 02912-1210. Solving Very Large Weakly Coupled Markov Decision Processes, https://www.aaai.org/Papers/AAAI/1998/AAAI98-023.pdf

Reference

  1. https://cs.wikipedia.org/wiki/Andrej_Markov.
  2. https://www.youtube.com/watch?v=my207WNoeyA.
  3. Russel, Stuart and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Englewood Cliffs, New Jersey: Prentice Hall.
  4. https://cs.wikipedia.org/wiki/Milton_Friedman.

Výuková videa a materiály

https://www.youtube.com/watch?v=i0o-ui1N35U

https://www.cc.gatech.edu/~bboots3/CS4641-Fall2018/Lecture18/18_MDPs1.pdf

https://www.youtube.com/watch?v=Jk2V9yA82YU

https://www.sciencedirect.com/science/article/abs/pii/S0927050705801768