Markovův rozhodovací proces - Markov decision process
V matematice, a Markovův rozhodovací proces (MDP) je diskrétní čas stochastický řízení proces. Poskytuje matematický rámec pro modelování rozhodování v situacích, kdy jsou výsledky částečně náhodný a částečně pod kontrolou rozhodovatele. MDP jsou užitečné pro studium optimalizační problémy vyřešeno prostřednictvím dynamické programování a posilování učení. MDP byly známy přinejmenším již v padesátých letech;[1] vyústil jádro výzkumu markovských rozhodovacích procesů Ronald Howard kniha z roku 1960, Dynamické programování a Markovovy procesy.[2] Používají se v mnoha oborech, včetně robotika, automatické ovládání, ekonomika a výrobní. Název MDP pochází od ruského matematika Andrey Markov protože jsou rozšířením Markovovy řetězy.
V každém časovém kroku je proces v nějakém stavu a osoba s rozhodovací pravomocí může zvolit jakoukoli akci který je k dispozici ve stavu . Proces reaguje v dalším kroku náhodným přesunem do nového stavu a poskytnutí odpovídající odměny rozhodovateli .
The pravděpodobnost že se proces přesune do nového stavu je ovlivněna zvolenou akcí. Konkrétně je to dáno funkcí přechodu stavu . Tedy další stav záleží na aktuálním stavu a akce rozhodovacího orgánu . Ale vzhledem k tomu a , je podmíněně nezávislý na všech předchozích stavech a akcích; jinými slovy, přechody stavu MDP splňují Majetek Markov.
Markovské rozhodovací procesy jsou rozšířením Markovovy řetězy; Rozdíl spočívá v přidání akcí (umožnění volby) a odměn (poskytnutí motivace). Naopak, pokud pro každý stát existuje pouze jedna akce (např. „Počkejte“) a všechny odměny jsou stejné (např. „Nula“), Markovův rozhodovací proces se redukuje na Markovův řetězec.
Definice
Markovův rozhodovací proces je 4n-tice , kde
- je soubor států zvaných státní prostor,
- je sada akcí zvaná akční prostor (alternativně, je sada akcí dostupných ze státu ),
- je pravděpodobnost, že akce ve stavu v čase povede ke stavu v čase ,
- je okamžitá odměna (nebo očekávaná okamžitá odměna) získaná po přechodu ze stavu do stavu , kvůli akci
Stavové a akční prostory mohou být konečné nebo nekonečné, například množina reálných čísel. Některé procesy s nekonečnými stavovými a akčními prostory lze redukovat na procesy s konečnými stavovými a akčními prostory.[3]
Cíl optimalizace
Cílem markovského rozhodovacího procesu je najít dobrou „politiku“ pro rozhodovatele: funkci který určuje akci že rozhodovatel si zvolí, kdy bude ve stavu . Jakmile je rozhodovací proces Markov kombinován s politikou tímto způsobem, opraví to akci pro každý stát a výsledná kombinace se chová jako Markovův řetězec (od akce zvolené ve stavu je zcela určeno a snižuje na , Markovova přechodová matice).
Cílem je zvolit politiku který maximalizuje určitou kumulativní funkci náhodných odměn, obvykle očekávanou diskontovanou částku za potenciálně nekonečný horizont:
- (kde se rozhodneme , tj. akce dané politikou). A očekávání je převzato
kde je uspokojivý slevový faktor , což je obvykle téměř 1 (například pro nějakou diskontní sazbu r). Nižší slevový faktor motivuje osobu s rozhodovací pravomocí, aby upřednostňoval včasné akce, spíše je neodkládal na neurčito.
Zásada, která maximalizuje výše uvedenou funkci, se nazývá optimální politika a je obvykle označován . Konkrétní MDP může mít několik odlišných optimálních zásad. Z důvodu vlastnosti Markov je možné ukázat, že optimální politika je funkcí aktuálního stavu, jak se předpokládá výše.
Modely simulátoru
V mnoha případech je obtížné představovat rozdělení pravděpodobnosti přechodu, , výslovně. V takových případech lze simulátor použít k modelování MDP implicitně poskytnutím vzorků z přechodových distribucí. Jednou běžnou formou implicitního modelu MDP je epizodický simulátor prostředí, který lze spustit z počátečního stavu a přináší následující stav a odměnu pokaždé, když obdrží vstup akce. Tímto způsobem se často nazývají trajektorie stavů, akcí a odměn epizody mohou být vyrobeny.
Další formou simulátoru je a generativní model, jednokrokový simulátor, který může generovat vzorky dalšího stavu a odměňovat je za jakýkoli stav a akci.[4] (Všimněte si, že se jedná o jiný význam než tento výraz generativní model v kontextu statistické klasifikace) algoritmy které jsou vyjádřeny pomocí pseudo kód, se často používá k reprezentaci generativního modelu. Například výraz může označovat akci vzorkování z generativního modelu, kde a jsou aktuální stav a akce a a jsou nový stát a odměna. Ve srovnání s epizodickým simulátorem má generativní model tu výhodu, že může přinést data z jakéhokoli stavu, nejen z těch, které se vyskytly v trajektorii.
Tyto modelové třídy tvoří hierarchii informačního obsahu: explicitní model triviálně přináší generativní model prostřednictvím vzorkování z distribucí a opakovaná aplikace generativního modelu poskytuje epizodický simulátor. V opačném směru je možné naučit se pouze přibližné modely regrese. Typ modelu, který je k dispozici pro konkrétní MDP, hraje významnou roli při určování, které algoritmy řešení jsou vhodné. Například dynamické programování algoritmy popsané v následující části vyžadují explicitní model a Hledání stromu v Monte Carlu vyžaduje generativní model (nebo epizodický simulátor, který lze kopírovat v jakémkoli stavu), zatímco většina posilování učení Algoritmy vyžadují pouze epizodický simulátor.
Algoritmy
Řešení pro MDP s konečným stavem a akčními prostory lze najít pomocí různých metod, jako je dynamické programování. Algoritmy v této části se vztahují na MDP s konečnými stavovými a akčními prostory a výslovně danými pravděpodobnostmi přechodu a funkcemi odměny, ale základní pojmy lze rozšířit i na jiné třídy problémů, například aproximace funkce.
Standardní rodina algoritmů pro výpočet optimálních zásad pro konečné a akční MDP vyžaduje úložiště pro dvě pole indexovaná podle stavu: hodnota , který obsahuje skutečné hodnoty, a politika , který obsahuje akce. Na konci algoritmu bude obsahovat řešení a bude obsahovat zlevněnou částku odměn, které mají být získány (v průměru) sledováním tohoto řešení od státu .
Algoritmus má dva kroky, (1) aktualizaci hodnoty a (2) aktualizaci zásad, které se v určitém pořadí opakují pro všechny státy, dokud nedojde k dalším změnám. Oba rekurzivně aktualizují nový odhad optimální zásady a hodnoty stavu pomocí staršího odhadu těchto hodnot.
Jejich pořadí závisí na variantě algoritmu; lze je také udělat pro všechny státy najednou nebo stát po státu a častěji pro některé státy než jiné. Dokud nebude z některého z kroků trvale vyloučen žádný stav, algoritmus nakonec dospěje ke správnému řešení.[5]
Pozoruhodné varianty
Hodnotová iterace
V hodnotové iteraci (Bellman 1957 ), který se také nazývá zpětná indukce, funkce se nepoužívá; místo toho hodnota se počítá uvnitř kdykoli je to potřeba. Nahrazení výpočtu do výpočtu dává kombinovaný krok[je třeba další vysvětlení ]:
kde je číslo iterace. Hodnotová iterace začíná na a jako hádka funkce hodnoty. Poté iteruje a opakovaně počítá pro všechny státy , dokud konverguje s levou stranou rovnou pravé straně (což je „Bellmanova rovnice „pro tento problém[je zapotřebí objasnění ]). Lloyd Shapley papír z roku 1953 stochastické hry jako speciální případ byla zahrnuta metoda iterace hodnot pro MDP,[6] ale toto bylo poznáno až později.[7]
Iterace zásad
V iteraci zásad (Howard 1960 ), první krok se provede jednou a poté se druhý krok opakuje, dokud nedojde ke konvergenci. Pak se první krok provede znovu jednou a tak dále.
Místo opakování druhého kroku ke konvergenci je možné jej formulovat a řešit jako soubor lineárních rovnic. Tyto rovnice jsou získány pouze vytvořením v rovnici druhého kroku.[je zapotřebí objasnění ] Opakování druhého kroku ke konvergenci lze tedy interpretovat jako řešení lineárních rovnic pomocí Relaxace (iterativní metoda)
Tato varianta má tu výhodu, že existuje určitá podmínka zastavení: když pole se během aplikace kroku 1 na všechny stavy nezmění, algoritmus je dokončen.
Iterace zásad je obvykle pomalejší než iterace hodnot pro velký počet možných stavů.
Upravená iterace zásad
V upravené iteraci zásad (van Nunen 1976; Puterman & Shin 1978 ), první krok se provede jednou a poté se druhý krok několikrát opakuje.[8][9] Pak se první krok provede znovu jednou a tak dále.
Prioritní zametání
V této variantě jsou kroky přednostně aplikovány na státy, které jsou nějakým způsobem důležité - ať už na základě algoritmu (došlo k velkým změnám v nebo kolem těchto států v poslední době) nebo na základě použití (tyto státy jsou blízko počátečního stavu nebo jinak zajímavé pro osobu nebo program využívající algoritmus).
Rozšíření a zobecnění
Markovský rozhodovací proces je a stochastická hra pouze s jedním hráčem.
Částečná pozorovatelnost
Výše uvedené řešení předpokládá, že stát je známo, kdy mají být přijata opatření; v opačném případě nelze vypočítat. Pokud tento předpoklad není pravdivý, problém se nazývá částečně pozorovatelný Markovův rozhodovací proces nebo POMDP.
Významný pokrok v této oblasti poskytli Burnetas a Katehakis v „Optimální adaptivní politice pro rozhodovací procesy v Markově“.[10] V této práci byla vytvořena třída adaptivních politik, které mají jednotně vlastnosti maximální rychlosti konvergence pro celkovou očekávanou odměnu konečného horizontu za předpokladů konečných prostorů státní akce a neredukovatelnosti přechodového zákona. Tyto zásady předepisují, že výběr akcí v každém stavu a časovém období by měl být založen na indexech, které jsou inflacemi na pravé straně odhadovaných rovnic průměrné optimality odměn.
Posílení učení
Pokud pravděpodobnosti nebo odměny nejsou známy, problém je v posilování učení.[11]
Pro tento účel je užitečné definovat další funkci, která odpovídá provedení akce a poté optimálně pokračovat (nebo podle jakékoli politiky, kterou jeden aktuálně má):
I když tato funkce není známa, zkušenosti s učením jsou založeny na páry (společně s výsledkem ; to znamená: „Byl jsem ve stavu a zkusil jsem to udělat a stalo se "). Jeden tedy má pole a využívá zkušenosti k přímé aktualizaci. Toto se nazývá Q-učení.
Posílení učení může vyřešit Markovovy rozhodovací procesy bez výslovné specifikace pravděpodobností přechodu; hodnoty pravděpodobností přechodu jsou potřebné v hodnotové a politické iteraci. V posilovacím učení se místo explicitní specifikace pravděpodobností přechodu přistupuje k pravděpodobnostem přechodu prostřednictvím simulátoru, který se obvykle mnohokrát restartuje z rovnoměrně náhodného počátečního stavu. Posílení učení lze také kombinovat s aproximací funkcí k řešení problémů s velmi velkým počtem států.
Učební automaty
Další aplikace procesu MDP v strojové učení teorie se nazývá učení automatů. Toto je také jeden typ učení o posílení, pokud je prostředí stochastické. První detail výukové automaty příspěvek je zjišťován Narendra a Thathachar (1974), které byly původně výslovně popsány jako konečné automaty.[12] Podobně jako učící se posilování má algoritmus učební automaty také tu výhodu, že řeší problém, když není známa pravděpodobnost nebo odměna. Rozdíl mezi automaty učení a Q-learningem spočívá v tom, že dřívější technika vynechává paměť Q-hodnot, ale aktualizuje pravděpodobnost akce přímo, aby našla výsledek učení. Učební automaty jsou výukové programy s přísným důkazem konvergence.[13]
V učení teorie automatů stochastický automat skládá se z:
- sada X možných vstupů,
- množina Φ = {Φ1, ..., Φs } možných vnitřních stavů,
- množina α = {α1, ..., αr } možných výstupů nebo akcí s r ≤ s,
- vektor pravděpodobnosti počátečního stavu p(0) = ≪ p1(0), ..., ps(0) ≫,
- A vypočítatelná funkce A které po každém časovém kroku t generuje p(t +1) od p(t), aktuální vstup a aktuální stav a
- funkce G: Φ → α, který generuje výstup v každém časovém kroku.
Stavy takového automatu odpovídají stavům „diskrétního stavu diskrétního parametru Markov proces ".[14] V každém časovém kroku t = 0,1,2,3, ..., automat načte vstup ze svého prostředí, aktualizuje P (t) horní(t + 1) od A, náhodně vybere následnický stát podle pravděpodobností P (t + 1) a odešle příslušnou akci. Prostředí automatu zase čte akci a odesílá další vstup do automatu.[13]
Teoretický výklad kategorie
Kromě odměn je to Markovův rozhodovací proces lze chápat ve smyslu Teorie kategorií. Jmenovitě označit volný monoid s generátorovou sadou A. Nechat Dist označit Kategorie Kleisli z Giry monad. Pak funktor kóduje obě sady S stavů a pravděpodobnostní funkce P.
Tímto způsobem lze Markovovy rozhodovací procesy zobecnit z monoidů (kategorie s jedním objektem) na libovolné kategorie. Jeden může volat výsledek A kontextově závislý Markovův rozhodovací proces, protože přesun z jednoho objektu do druhého v změní sadu dostupných akcí a sadu možných stavů.
Fuzzy Markov rozhodovací procesy (FMDP)
V MDP je optimální politikou politika, která maximalizuje pravděpodobnostně vážený součet budoucích odměn. Optimální politika proto sestává z několika akcí, které patří do konečné sady akcí. Ve fuzzy Markovových rozhodovacích procesech (FMDP) se nejprve hodnotová funkce počítá jako běžné MDP (tj. S konečnou sadou akcí); poté je politika extrahována fuzzy odvozovacím systémem. Jinými slovy, hodnotová funkce se používá jako vstup pro fuzzy inferenční systém a politika je výstupem fuzzy inferenčního systému.[15]
Markovský proces kontinuálního času
V Markovových rozhodovacích procesech v diskrétním čase se rozhodnutí přijímají v diskrétních časových intervalech. Nicméně pro Markovovy rozhodovací procesy v nepřetržitém čase, rozhodnutí lze učinit kdykoli, kdo si rozhodne. Ve srovnání s Markovovými rozhodovacími procesy v diskrétním čase mohou Markovovy rozhodovací procesy v nepřetržitém čase lépe modelovat rozhodovací proces pro systém, který má kontinuální dynamika, tj. dynamika systému je definována parciální diferenciální rovnice (PDE).
Definice
Abychom mohli diskutovat o Markovově procesu rozhodování v nepřetržitém čase, zavedeme dvě sady notací:
Pokud jsou stavový prostor a akční prostor konečné,
- : Státní prostor;
- : Akční prostor;
- : , funkce rychlosti přechodu;
- : , funkce odměny.
Pokud jsou stavový prostor a akční prostor spojité,
- : státní prostor;
- : prostor možné kontroly;
- : , funkce rychlosti přechodu;
- : , funkce odměny taková , kde je funkce odměny, o které jsme diskutovali v předchozím případě.
Problém
Stejně jako Markovovy rozhodovací procesy v diskrétním čase, i v Markovových rozhodovacích procesech s kontinuálním časem chceme najít optimální politika nebo řízení což by nám mohlo poskytnout optimální očekávanou integrovanou odměnu:
kde
Formulace lineárního programování
Pokud je stavový prostor a akční prostor konečný, mohli bychom pomocí lineárního programování najít optimální politiku, což byl jeden z prvních použitých přístupů. Zde uvažujeme pouze ergodický model, což znamená, že se náš nepřetržitý MDP stává ergodický nepřetržitý markovský řetězec pod stojícím politika. Za tohoto předpokladu, i když rozhodující orgán může za současného stavu učinit rozhodnutí kdykoli, nemohl by mít větší užitek z provedení více než jedné akce. Je pro ně lepší provést akci pouze v době, kdy systém přechází ze současného stavu do jiného stavu. Za určitých podmínek (podrobněji viz Dodatek 3.14 ze dne Markovovy rozhodovací procesy v nepřetržitém čase ), pokud naše funkce optimální hodnoty je nezávislý na státu , budeme mít následující nerovnost:
Pokud existuje funkce , pak bude nejmenší splnění výše uvedené rovnice. Aby bylo možné najít , můžeme použít následující model lineárního programování:
- Primární lineární program (P-LP)
- Duální lineární program (D-LP)
je proveditelné řešení pro D-LP, pokud není nativní a uspokojil omezení v problému D-LP. Dostupné řešení na D-LP se říká, že je optimálním řešením, pokud
pro všechna proveditelná řešení na D-LP. Jakmile jsme našli optimální řešení , můžeme jej použít k vytvoření optimální politiky.
Hamilton – Jacobi – Bellmanova rovnice
V případě MDP s nepřetržitým časem, pokud je stavový prostor a akční prostor spojitý, lze optimální kritérium najít řešením Hamilton – Jacobi – Bellman (HJB) parciální diferenciální rovnice Abychom mohli diskutovat o HJB rovnici, musíme přeformulovat náš problém
je funkce odměny terminálu, je systémový vektor systému, je vektor řízení systému, který se snažíme najít. ukazuje, jak se stavový vektor v čase mění. Rovnice Hamilton – Jacobi – Bellman je následující:
Mohli bychom vyřešit rovnici, abychom našli optimální řízení , což by nám mohlo dát optimální funkce hodnoty
aplikace
Markovské rozhodovací procesy v nepřetržitém čase mají aplikace systémy řazení do fronty, epidemické procesy a populační procesy.
Alternativní notace
Terminologie a notace pro MDP nejsou zcela vyřešeny. Existují dva hlavní proudy - jeden se zaměřuje na problémy s maximalizací z kontextů, jako je ekonomie, používání výrazů akce, odměna, hodnota a volání faktoru slevy nebo zatímco druhá se zaměřuje na minimalizační problémy z inženýrství a navigace[Citace je zapotřebí ]pomocí výrazů ovládání, cena, náklady do vyřízení a volání faktoru slevy . Kromě toho se liší značení pravděpodobnosti přechodu.
v tomto článku | alternativní | komentář |
---|---|---|
akce | řízení | |
odměna | náklady | je zápor |
hodnota | náklady do konce | je zápor |
politika | politika | |
diskontní faktor | diskontní faktor | |
pravděpodobnost přechodu | pravděpodobnost přechodu |
Kromě toho je někdy psána pravděpodobnost přechodu , nebo zřídka
Omezené Markovovy rozhodovací procesy
Omezené Markovovy rozhodovací procesy (CMDP) jsou rozšíření Markovova rozhodovacího procesu (MDP). Mezi MDP a CMDP existují tři zásadní rozdíly.[16]
- Po provedení akce namísto jedné vznikne několik nákladů.
- CMDP jsou řešeny pomocí lineární programy pouze a dynamické programování nefunguje.
- Konečná politika závisí na počátečním stavu.
Existuje řada aplikací pro CMDP. Nedávno byl použit v plánování pohybu scénáře v robotice.[17]
Viz také
Reference
- ^ Bellman, R. (1957). „Markovianský rozhodovací proces“. Journal of Mathematics and Mechanics. 6 (5): 679–684. JSTOR 24900506.
- ^ Howard, Ronald A. (1960). Dynamické programování a Markovovy procesy (PDF). The M.I.T. Lis.
- ^ Wrobel, A. (1984). „Na Markovianových rozhodovacích modelech s konečnou kostrou“. Matematické metody operačního výzkumu (ZOR). 28 (Únor): 17–27. doi:10.1007 / bf01919083. S2CID 2545336.
- ^ Kearns, Michael; Mansour, Yishay; Ng, Andrew (2002). „Řídký algoritmus vzorkování pro téměř optimální plánování ve velkých Markovských rozhodovacích procesech“. Strojové učení. 49 (193–208): 193–208. doi:10.1023 / A: 1017932429737.
- ^ Posílení učení: Teorie a implementace Pythonu. Peking: China Machine Press. 2019. str. 44. ISBN 9787111631774.
- ^ Shapley, Lloyd (1953). „Stochastické hry“. Sborník Národní akademie věd Spojených států amerických. 39 (10): 1095–1100. Bibcode:1953PNAS ... 39.1095S. doi:10.1073 / pnas.39.10.1095. PMC 1063912. PMID 16589380.
- ^ Kallenberg, Lodewijk (2002). "Konečný stav a akce MDP". Ve Feinberg, Eugene A .; Shwartz, Adam (eds.). Příručka Markovových rozhodovacích procesů: metody a aplikace. Springer. ISBN 978-0-7923-7459-6.
- ^ Puterman, M. L .; Shin, M. C. (1978). "Modifikované iterační algoritmy zásad pro problémy se zlevněným rozhodnutím Markov". Věda o řízení. 24 (11): 1127–1137. doi:10,1287 / mnsc.24.11.1127.
- ^ van Nunen, J.A. E.E (1976). "Sada postupných aproximačních metod pro zlevněné problémy Markovianova rozhodování. Z". Operační výzkum. 20 (5): 203–208. doi:10.1007 / bf01920264. S2CID 5167748.
- ^ Burnetas, A.N .; Katehakis, M. N. (1997). "Optimální adaptivní politiky pro Markovovy rozhodovací procesy". Matematika operačního výzkumu. 22 (1): 222. doi:10,1287 / bř. 22.1.222.
- ^ Shoham, Y .; Powers, R .; Grenager, T. (2003). „Multi-agent posílení učení: kritický průzkum“ (PDF). Technická zpráva, Stanford University: 1–13. Citováno 2018-12-12.
- ^ Narendra, K. S.; Thathachar, M. A. L. (1974). "Učící se automaty - průzkum". Transakce IEEE na systémech, člověku a kybernetice. SMC-4 (4): 323–334. CiteSeerX 10.1.1.295.2280. doi:10.1109 / TSMC.1974.5408453. ISSN 0018-9472.
- ^ A b Narendra, Kumpati S.; Thathachar, Mandayam A. L. (1989). Učební automaty: Úvod. Prentice Hall. ISBN 9780134855585.
- ^ Narendra & Thathachar 1974, zbývá str. 325.
- ^ Fakoor, Mahdi; Kosari, Amirreza; Jafarzadeh, Mohsen (2016). „Plánování cesty humanoidních robotů s fuzzy Markovovými rozhodovacími procesy“. Journal of Applied Research and Technology. 14 (5): 300–310. doi:10.1016 / j.jart.2016.06.006.
- ^ Altman, Eitan (1999). Omezené Markovovy rozhodovací procesy. 7. CRC Press.
- ^ Feyzabadi, S .; Carpin, S. (18. – 22. Srpna 2014). „Plánování cesty s ohledem na riziko pomocí hierarchicky omezených Markovových rozhodovacích procesů“. Věda o automatizaci (CASE). Mezinárodní konference IEEE. 297, 303.
Další čtení
- Bellman., R. E. (2003) [1957]. Dynamické programování (Doverská brožovaná ed.). Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3.
- Bertsekas, D. (1995). Dynamické programování a optimální řízení. 2. MA: Athéna.
- Derman, C. (1970). Markovianské rozhodovací procesy konečného stavu. Akademický tisk.
- Feinberg, E.A.; Shwartz, A., eds. (2002). Příručka Markovových rozhodovacích procesů. Boston, MA: Kluwer. ISBN 9781461508052.
- Guo, X .; Hernández-Lerma, O. (2009). Markovovy rozhodovací procesy v nepřetržitém čase. Stochastické modelování a aplikovaná pravděpodobnost. Springer. ISBN 9783642025464.
- Meyn, S. P. (2007). Řídicí techniky pro složité sítě. Cambridge University Press. ISBN 978-0-521-88441-9. Archivovány od originál dne 19. června 2010. Příloha obsahuje zkráceně „Meyn & Tweedie“. Archivovány od originál dne 18. prosince 2012.
- Puterman., M. L. (1994). Markovské rozhodovací procesy. Wiley.
- Ross, S. M. (1983). Úvod do stochastického dynamického programování (PDF). Akademický tisk.
- Sutton, R. S .; Barto, A. G. (2017). Učení o posílení: Úvod. Cambridge, MA: MIT Press.
- Tijms., H.C. (2003). První kurz stochastických modelů. Wiley. ISBN 9780470864289.