Markov decision process/cs

Úvod

Nejistota je velice častým rysem obrovského množství modelů v různých oborech, od počítačové vědy, inženýrství a operačního výzkumu až po ekonomie. Často je nutné řešit problémy nebo přijímat rozhodnutí bez komplexních znalosti všech relevantních faktorů a bez znalosti jejich možného budoucího chování. Ve spoustě situacích výsledek částečně závisí na náhodnosti a částečně na rozhodování agenta. Proto je velice užitečné vytvořit rámec pro modelování toho, jak rozhodovat ve stochastickém prostředí. Příkladem takových modelů jsou Markovské procesy. Tyto procesy mají důležitou charakteristiku, která se spočívá v tom, že způsob, jakým se budou v budoucnu vyvíjet, závisí pouze na jejich současném stavu. To znamená, že každý proces je nezávislý na událostech z minulosti. Pomocí Markovských procesů lze modelovat celou řadu důležitých náhodných systémů, včetně biologických systémů a epidemiologie, finančních a fyzických systémů.

Markovův rozhodovací proces (v angličtině Markov decision process nebo MDP) je matematický model pro rozhodování za nejistoty. Model se používá v situacích, kdy jsou výsledky částečně náhodné a zároveň částečně záleží na rozhodnutích . MDP je obecnějším modelem (rozšířením) Markovských řetězců. Hlavní rozdíl je v přidání do modelu užitků a akcí. V MDP agent provádí posloupnost akcí, které transformují stav systému do jednoho z několika možných následných stavů. Každý možný následný stav má určitou míru pravděpodobnosti přechodu. Postup obsahuje zkoumání současného stavu a vykonaní akce. K řešení se obvykle používají algoritmy dynamického programování. Avšak nevýhodou metod dynamického programování je ten fakt, že prohledávají celý prostor stavů. Takový přistup může být velice náročným vzhledem k času a zdrojům. Dalším problémem je “Short-term vs. long-term problem” – to, co je vhodné z krátkodobého hlediska, může být nevhodné z dlouhodobého hlediska. Jedna z prvních publikací je “A Markovian Decision Process” z roku 1957, autorem je Richard Bellman. V současnosti MDP našlo uplatnění v různých disciplínách – robotika, automatické řízení, ekonomika, výroba atd.