Markovův rozhodovací proces

Markovovy 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. Markovovy 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í. Markovovy 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 Markovovy 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 Markovův rozhodovací proces diskrétní, stochastický a kontrolovaný proces. V každém časovém okamžiku je proces v určitém stavu ${\displaystyle s}$ a uživatel může vybrat jakoukoli akci ${\displaystyle a}$, která je dostupná ve stavu ${\displaystyle 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 ${\displaystyle s'}$ a dává uživateli odpovídající užitek ${\displaystyle R_{a}(s,s')}$.

Pravděpodobnost, že proces vybere ${\displaystyle s'}$ jako nový stav, je ovlivněna vybranou akcí. Pravděpodobnost je určena funkcí přechodu stavu ${\displaystyle P_{a}(s,s')}$. Takže následující stav ${\displaystyle s'}$ závisí na současném stavu ${\displaystyle s}$ a na uživatelově akci ${\displaystyle a}$. Dané ${\displaystyle s}$ a ${\displaystyle 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 Markovova rozhodovacího procesu Markovovu vlastnost.

Markovovy rozhodovací procesy jsou rozšířením Markovový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, Markovův rozhodovací proces by se zredukoval na Markovův řetězec.

Definice

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

Markovův rozhodovací proces je uspořádaná čtveřice ${\displaystyle (S,A,P_{\cdot }(\cdot ,\cdot ),R_{\cdot }(\cdot ,\cdot ))}$, kde

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

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

Problém

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

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

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

kde ${\displaystyle \ \gamma \ }$ je diskontní faktor splňující ${\displaystyle 0<\gamma \ \leq \ 1}$. Typicky se blíží 1.

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

Řešení

Markovovy 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 ${\displaystyle P}$ a užitkovou funkci ${\displaystyle 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 ${\displaystyle V}$, která obsahuje reálné hodnoty, a strategie ${\displaystyle \pi }$, která uchovává akce. Na konci algoritmu bude ${\displaystyle \pi }$ obsahovat řešení a ${\displaystyle V(s)}$ bude obsahovat diskontovanou sumu užitků, které budou (v průměru) získány provedením tohoto řešení ve stavu ${\displaystyle 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.

${\displaystyle \ \pi (s):=\arg \max _{a}\{R_{a}(s,s')+\gamma \sum _{s'}P_{a}(s,s')V(s')\}}$

${\displaystyle \ V(s):=R(s)+\gamma \sum _{s'}P_{\pi (s)}(s,s')V(s')\ }$

R(s) je zde ${\displaystyle 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

Iterace hodnot

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

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

${\displaystyle \ 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 ${\displaystyle s}$ dokud nekonverguje s levou stranou rovnou pravé straně (což je Bellmanova rovnice pro tento problém).

Iterace strategie

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 ${\displaystyle \pi }$ nezmění ve směru působení prvního kroku na všechny stavy.

Upravená iterace strategie

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ů

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 ${\displaystyle V}$ nebo ${\displaystyle \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í

Částečná pozorovatelnost

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

Výše uvedené řešení předpokládá, že pokud je třeba učinit akci, je stav ${\displaystyle s}$ známý; jinak nemůže být ${\displaystyle \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í

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 ${\displaystyle a}$ a následnému optimálnímu pokračování (nebo podle toho, o jakou strategii se aktuálně jedná):

${\displaystyle \ 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 ${\displaystyle (s,a)}$ (spolu s výsledkem ${\displaystyle s'}$). To znamená: „Byl jsem ve stavu ${\displaystyle s}$ a zkoušel jsem učinit ${\displaystyle a}$ a stalo se ${\displaystyle s'}$“). Čili máme pole ${\displaystyle 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 Markovův 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

Terminologie a notace pro Markovovy 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 ${\displaystyle \beta }$ nebo ${\displaystyle \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 ${\displaystyle \alpha }$. Liší se i zápisy pro pravděpodobnost přechodu.

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

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

Reference

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

• Dynamické programování

Externí odkazy

• MDP Toolbox for Matlab An excellent tutorial and Matlab toolbox for working with MDPs.
• Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto
• SPUDD A structured MDP solver for download by Jesse Hoey
• Learning to Solve Markovian Decision Processes by Satinder P. Singh

Autoritní data	PSH: 7713