Markovův rozhodovací proces

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Markovské rozhodovací procesy jsou pojmenovány po ruském matematikovi Andreji Markovovi. Poskytují matematický rámec pro modelování rozhodování v situacích, kdy jsou výsledky zčásti náhodné a zčásti pod kontrolou uživatele. Markovské rozhodovací procesy se využívají pro studium mnoha typů optimalizačních problémů řešených prostřednictvím dynamického programování a zpětnovazebního učení. Markovské rozhodovací procesy jsou známy od 50. let 20. století (viz Bellman 1957). Mnoho výzkumu v této oblasti bylo učiněno na základě knihy Ronalda A. Howarda Dynamické programování a Markovské procesy z roku 1960. Dnes jsou využívány v různých oblastech včetně robotiky, automatizovaného řízení, ekonomie a průmyslové výroby.

Přesněji řečeno je Markovský rozhodovací proces diskrétní, stochastický a kontrolovaný proces. V každém časovém okamžiku je proces v určitém stavu s a uživatel může vybrat jakoukoli akci a, která je dostupná ve stavu s. Proces na tuto akci v následujícím časovém okamžiku reaguje náhodným přesunutím do nového stavu s' a dává uživateli odpovídající užitek R_a(s,s').

Pravděpodobnost, že proces vybere s' jako nový stav, je ovlivněna vybranou akcí. Pravděpodobnost je určena funkcí přechodu stavu P_a(s,s'). Takže následující stav s' závisí na současném stavu s a na uživatelově akci a. Dané s a a jsou však podmíněně závislé na všech předchozích stavech a akcích. Jinými slovy má přechod stavu Markovského rozhodovacího procesu Markovskou vlastnost.

Markovské rozhodovací procesy jsou rozšířením Markovských řetězců; rozdíl je v přidání akcí (umožňují výběr) a užitků (motivace). Pokud by existovala pouze jedna akce, nebo pokud by byla daná uskutečnitelná akce stejná pro všechny stavy, Markovský rozhodovací proces by se zredukoval na Markovský řetězec.

Definice[editovat | editovat zdroj]

Příklad jednoduchého Markovova rozhodovacího procesu se třemi stavy a dvěma akcemi.

Markovský rozhodovací proces je uspořádaná čtveřice (S,A,P_\cdot(\cdot,\cdot),R_\cdot(\cdot,\cdot)), kde

  • S je konečná množina stavů,
  • A je konečná množina akcí (alternativa: A_s je konečná množina akcí dostupných ve stavu s),
  • P_a(s,s') = \Pr(s_{t+1}=s' \mid s_t = s,\, a_t=a) je pravděpodobnost, že akce a ve stavu s v čase t povede v čase t+1 do stavu s',
  • R_a(s,s') je okamžitý užitek (ne očekávaný okamžitý užitek) dosažený po přechodu stavu na s' ze stavu s s pravděpodobností přechodu P_a(s,s').

(Teorie Markovských rozhodovacích procesů ve skutečnosti nevyžaduje, aby S nebo A byly konečné množiny, ale základní algoritmus níže předpokládá, že jsou konečné).

Problém[editovat | editovat zdroj]

Hlavním úkolem Markovských rozhodovacích procesů je najít strategii pro uživatele: funkci \pi, která specifikuje akci \pi(s), kterou zvolí uživatel ve stavu s. Je třeba poznamenat, že je-li jednou Markovský rozhodovací proces takto zkombinován se strategií, je pro každý stav určena akce a výsledná kombinace se chová jako Markovský řetězec.

Cílem je vybrat strategii \pi, která bude maximalizovat kumulativní funkci náhodných užitků, typicky očekávanou diskontovanou sumu za potenciálně nekonečnou dobu:

 \sum^{\infty}_{t=0}\gamma^t R_{a_t}(s_t, s_{t+1})    (kde zvolíme a_t = \pi(s_t))

kde \ \gamma \ je diskontní faktor splňující 0 < \gamma\ \le\ 1. Typicky se blíží 1.

Díky Markovské vlastnosti může být optimální strategie pro tento speciální problém skutečně zapsána jako funkce pouze s, jak bylo předpokládáno výše.

Řešení[editovat | editovat zdroj]

Markovské rozhodovací procesy lze řešit metodami lineárního programování nebo dynamického programování. Následující text ukazuje použití dynamického programování.

Předpokládejme, že známe funkci přechodu stavu P a užitkovou funkci R. Chceme zjistit strategii, která maximalizuje očekávanou diskontovanou hodnotu.

Standardní skupina algoritmů používaná pro zjištění této optimální strategie vyžaduje uložení dvou polí indexovaných stavem: hodnota V, která obsahuje reálné hodnoty, a strategie \pi, která uchovává akce. Na konci algoritmu bude \pi obsahovat řešení a V(s) bude obsahovat diskontovanou sumu užitků, které budou (v průměru) získány provedením tohoto řešení ve stavu s.

Algoritmus má následující dva druhy kroků, které jsou opakovány v určitém pořadí pro všechny stavy, dokud nedojde k nějakým[kdo?] změnám.

\ \pi(s) := \arg \max_a \{R_a(s,s') + \gamma \sum_{s'} P_a(s,s') V(s')\}
\ V(s) := R(s) + \gamma \sum_{s'} P_{\pi(s)}(s,s') V(s')\

R(s) je zde R_{\pi(s)}(s). Pořadí kroků závisí na variantě algoritmu. Kroky se buď mohou provádět pro všechny stavy najednou, nebo pro každý stav popořadě, a pro některé stavy častěji než pro jiné. Dokud není žádný stav permanentně vyloučen ze žádného z kroků, algoritmus má šanci dospět ke správnému řešení.

Významné varianty[editovat | editovat zdroj]

Iterace hodnot[editovat | editovat zdroj]

Při iteraci hodnot (Bellman 1957), která se rovněž nazývá zpětná indukce, není pole \pi použito; místo toho je hodnota \pi(s) vypočtena kdykoli je potřeba.

Dosazením výpočtu \pi(s) do výpočtu V(s) dostaneme kombinovaný krok:

\ V(s) := R(s) + \gamma \max_a \sum_{s'} P_a(s,s') V(s').\

Toto zaktualizované pravidlo je opakováno pro všechny stavy s dokud nekonverguje s levou stranou rovnou pravé straně (což je Bellmanova rovnice pro tento problém).

Iterace strategie[editovat | editovat zdroj]

Při iteraci strategie je první krok proveden jednou a druhý krok je opakován dokud nekonverguje. Poté je znovu jednou proveden první krok a tak stále dokola.

Místo toho, aby byl druhý krok opakován dokud nekonverguje, měl by být problém formulován a řešen jako množina lineárních rovnic.

Tato varianta má výhodou, že zde existuje konečná podmínka ukončení: algoritmus je dokončen, pokud se pole \pi nezmění ve směru působení prvního kroku na všechny stavy.

Upravená iterace strategie[editovat | editovat zdroj]

V upravené iteraci strategie (van Nunen, 1976; Puterman a Shin 1978) je první krok vykonán jednou a druhý krok je několikrát opakován. Poté je opět proveden první krok atd.

Prioritizace kroků[editovat | editovat zdroj]

V této variantě jsou kroky přednostně aplikovány na stavy, které jsou nějakým způsobem důležité – buď jsou založené na algoritmu (v těchto stavech došlo k velkým změnám V nebo \pi během posledních iterací) nebo jsou založeny na použití (tyto stavy jsou blízko počátečnímu stavu, nebo jsou jinak zajímavé osobě nebo programu, který používá algoritmus).

Rozšíření[editovat | editovat zdroj]

Částečná pozorovatelnost[editovat | editovat zdroj]

Podrobnější informace naleznete v článku Částečně pozorovatelný Markovský rozhodovací proces.

Výše uvedené řešení předpokládá, že pokud je třeba učinit akci, je stav s známý; jinak nemůže být \pi(s) vypočteno. Pokud tento předpoklad není pravdivý, nazývá se problém částečně pozorovatelný Markovský rozhodovací proces.

Zpětnovazební učení[editovat | editovat zdroj]

Pokud jsou pravděpodobnosti či užitky neznámé, jedná se o problém zpětnovazebního učení (Sutton a Barto, 1998).

Pro tento účel je užitečné definovat další funkci, která odpovídá učinění akce a a následnému optimálnímu pokračování (nebo podle toho, o jakou strategii se aktuálně jedná):

\ Q(s,a) = R(s) + \gamma \sum_{s'} P_a(s,s') V(s').\

Zatímco tato funkce je taktéž neznámá, zkušenost během učení je založena na dvojicích (s, a) (spolu s výsledkem s'). To znamená: „Byl jsem ve stavu s a zkoušel jsem učinit a a stalo se s'“). Čili máme pole Q a využíváme zkušenosti k jeho přímé aktualizaci. Uvedené nazýváme Q-učení.

Síla zpětnovazebního učení leží v jeho schopnosti řešit Markovský rozhodovací proces bez výpočtu pravděpodobností přechodu. Uvědomme si, že pravděpodobnosti jsou potřebné pro iteraci hodnoty i strategie. Zpětnovazební učení může být taktéž kombinováno s aproximací funkcí a tím lze řešit problémy s velkým množstvím stavů. Zpětnovazební učení může být rovněž snadno vykonáváno v rámci simulací systémů pomocí metody Monte Carlo.

Alternativní zápisy[editovat | editovat zdroj]

Terminologie a notace pro Markovské rozhodovací procesy není jednoznačná. Existují dva hlavní proudy; první, zaměřený na maximalizační problémy z oblastí jako je ekonomie, používá termíny jako je akce, užitek, hodnota a označuje diskontní faktor \beta nebo \gamma; druhý je zaměřený na minimalizační problémy z oblastí techniky a navigace a používá termíny jako je kontrola, cena, cena změny, a diskontní faktor označuje \alpha. Liší se i zápisy pro pravděpodobnost přechodu.

v tomto článku alternativa komentář
akce a kontrola u
užitek R cena g g je negativní R
hodnota V cena změny J J je negativní V
strategie \pi strategie \mu
diskontní faktor \ \gamma \ diskontní faktor \alpha
pravděpodobnost přechodu P_a(s,s') pravděpodobnost přechodu p_{ss'}(a)

Někdy se pravděpodobnost přechodu zapisuje jakoPr(s,a,s'), Pr(s'|s,a) nebo méně často p_{s's}(a).

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Markov decision process na anglické Wikipedii.

  • R. Bellman. A Markovian Decision Process. Journal of Mathematics and Mechanics 6, 1957.
  • R. E. Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, 1957. Dover paperback edition (2003), ISBN 0-486-42809-5.
  • Ronald A. Howard Dynamic Programming and Markov Processes, The M.I.T. Press, 1960.
  • D. Bertsekas. Dynamic Programming and Optimal Control. Volume 2, Athena, MA, 1995.
  • M. L. Puterman. Markov Decision Processes. Wiley, 1994.
  • H.C. Tijms. A First Course in Stochastic Models. Wiley, 2003.
  • Sutton, R. S. and Barto A. G. Reinforcement Learning: An Introduction. The MIT Press, Cambridge, MA, 1998.
  • J.A. E. E van Nunen. A set of successive approximation methods for discounted Markovian decision problems. Z. Operations Research, 20:203-208, 1976.
  • S. P. Meyn, 2007. Control Techniques for Complex Networks, Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie.
  • S. M. Ross. 1983. Introduction to stochastic dynamic programming. Academic press

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]