Markovův rozhodovací proces - Markov decision process

V matematice je Markovův rozhodovací proces ( MDP ) diskrétní stochastický řídicí 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 rozhodovacího orgánu. MDP jsou užitečné pro studium optimalizačních problémů řešených pomocí dynamického programování . MDP byly známy přinejmenším již v 50. letech; jádro výzkumu Markovových rozhodovacích procesů vyplynulo z knihy Ronalda Howarda z roku 1960, Dynamic Programming and Markov Processes . Používají se v mnoha oborech, včetně robotiky , automatického řízení , ekonomiky a výroby . Název MDP pochází od ruského matematika Andrey Markova , protože jsou rozšířením Markovových řetězců .

V každém časovém kroku je proces v nějakém stavu a rozhodovací orgán může zvolit jakoukoli akci, která je ve stavu k dispozici . Proces reaguje v dalším časovém kroku tím, že se náhodně přesune do nového stavu a dá rozhodovateli odpovídající odměnu .

Pravděpodobnost , že proces se pohybuje do svého nového stavu je ovlivněna použitou akce. Konkrétně je to dáno funkcí přechodu stavu . Další stav tedy závisí na aktuálním stavu a činnosti rozhodovatele . Ale vzhledem k tomu a je podmínečně nezávislá na všech předchozích stavů a akcí; jinými slovy, stavové přechody MDP uspokojují Markovovu vlastnost .

Markovské rozhodovací procesy jsou rozšířením Markovových řetězců ; rozdíl je v přidání akcí (umožnění volby) a odměn (poskytnutí motivace). A naopak, pokud pro každý stát existuje pouze jedna akce (např. „Čekání“) a všechny odměny jsou stejné (např. „Nula“), Markovský rozhodovací proces se redukuje na Markovův řetězec.

Definice

Příklad jednoduchého MDP se třemi stavy (zelené kruhy) a dvěma akcemi (oranžové kruhy), se dvěma odměnami (oranžové šipky).

Markovův rozhodovací proces je 4 -tice , kde:

  • je sada stavů nazývaných stavový prostor ,
  • je sada akcí nazývaná akční prostor (alternativně je to sada akcí dostupných ze stavu ),
  • 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) obdržená po přechodu ze stavu do stavu v důsledku akce

Stavové a akční mezery mohou být konečné nebo nekonečné, například množina reálných čísel . Některé procesy s počitatelně nekonečnými stavovými a akčními mezerami lze redukovat na procesy s konečnými stavovými a akčními mezerami.

Funkce zásad je (potenciálně pravděpodobnostní) mapování ze stavového prostoru ( ) do akčního prostoru ( ).

Cíl optimalizace

Cílem v Markovově rozhodovacím procesu je najít pro „tvůrce rozhodnutí“ dobrou „politiku“: funkci, která specifikuje akci, kterou si subjekt s rozhodováním zvolí, když je ve stavu . Jakmile je Markovův rozhodovací proces takto zkombinován s politikou, opraví to akci pro každý stát a výsledná kombinace se chová jako Markovův řetězec (protože akce zvolená ve stavu je zcela určena a redukována na Markovovu přechodovou matici) .

Cílem je zvolit zásadu, která bude maximalizovat nějakou kumulativní funkci náhodných odměn, obvykle očekávanou diskontovanou částku v potenciálně nekonečném horizontu:

(kde si vybereme , tj. akce dané zásadami). A očekávání je převzato

kde je uspokojivý diskontní faktor , který se obvykle blíží 1 (například u nějaké diskontní sazby r). Nižší diskontní faktor motivuje tvůrce rozhodnutí upřednostňovat včasné akce, než je odkládat na neurčito.

Zásada, která maximalizuje výše uvedenou funkci, se nazývá optimální zásada a obvykle se označuje . Konkrétní MDP může mít několik různých optimálních zásad. Vzhledem k vlastnosti Markov lze 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é explicitně znázornit rozdělení pravděpodobnosti přechodu . V takových případech lze k modelování MDP implicitně použít simulátor poskytnutím vzorků z přechodových distribucí. Jednou z běžných forem implicitního modelu MDP je epizodický simulátor prostředí, který lze spustit z počátečního stavu a přináší následný stav a odměnu pokaždé, když obdrží vstup do akce. Tímto způsobem lze vytvářet trajektorie stavů, akcí a odměn, často nazývaných epizody .

Další formou simulátoru je generativní model , jednostupňový simulátor, který dokáže generovat vzorky dalšího stavu a odměnu za daný stav a akci. (Všimněte si, že toto je jiný význam než termín generativní model v kontextu statistické klasifikace.) V algoritmech, které jsou vyjádřeny pomocí pseudokódu , 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 jsou nový stav a odměna. Ve srovnání s epizodickým simulátorem má generativní model tu výhodu, že může poskytovat data z jakéhokoli stavu, nejen z těch, s nimiž se setkáváme na trajektorii.

Tyto modelové třídy tvoří hierarchii informačního obsahu: explicitní model triviálně poskytuje 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 přibližné modely pouze pomocí regrese . Typ modelu dostupného 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 další části vyžadují explicitní model a Monte Carlo vyhledávací strom vyžaduje generativní model (nebo epizodický simulátor, který lze kopírovat v jakémkoliv stavu), zatímco většina učení zesílení algoritmy vyžadují pouze epizodické simulátor .

Algoritmy

Řešení pro MDP s konečným stavem a akčními prostory lze nalézt prostřednictvím řady 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 mezerami a explicitně danými pravděpodobnostmi přechodu a funkcemi odměny, ale základní pojmy lze rozšířit tak, aby zvládaly i jiné problémové třídy, například pomocí aproximace funkcí .

Standardní skupina algoritmů pro výpočet optimálních zásad pro konečné stavy a akce MDP vyžaduje úložiště pro dvě pole indexovaná podle stavu: hodnota , která obsahuje skutečné hodnoty, a zásada , 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) následováním tohoto řešení ze stavu .

Algoritmus má dva kroky (1) aktualizaci hodnoty a (2) aktualizaci zásad, které se v určitém pořadí opakují pro všechny stavy, dokud nedojde k žádným 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é provést pro všechny státy najednou nebo stát podle státu a častěji některým státům než jiným. Dokud není z žádného z kroků trvale vyloučen žádný stav, algoritmus nakonec dospěje ke správnému řešení.

Pozoruhodné varianty

Iterace hodnoty

Při iteraci hodnoty ( Bellman 1957 ), které se také říká zpětná indukce , se funkce nepoužívá; místo toho se hodnota vypočítá v rámci, kdykoli je to potřeba. Dosazením výpočtu do výpočtu výpočtu získáte kombinovaný krok:

kde je číslo iterace. Iterace hodnoty začíná na a jako odhad hodnotové funkce . Poté iteruje, opakovaně počítá pro všechny stavy , dokud se nesbírá s levou stranou rovnou pravou stranou (což je pro tento problém „ Bellmanova rovnice “). Dokument Lloyda Shapleye z roku 1953 o stochastických hrách zahrnoval jako zvláštní případ metodu iterace hodnoty pro MDP, ale to bylo uznáno až později.

Opakování zásad

V iteraci zásad ( Howard 1960 ) se první krok provede jednou a pak se druhý krok opakuje, dokud se nesblíží. Poté se krok jedna provede znovu jednou a tak dále.

Namísto opakování kroku dva do konvergence může být formulován a vyřešen jako sada lineárních rovnic. Tyto rovnice se získají pouze vytvořením rovnice v kroku dva. Opakování kroku dva do konvergence lze tedy interpretovat jako řešení lineárních rovnic relaxací (iterační metoda)

Tato varianta má tu výhodu, že existuje jednoznačná podmínka zastavení: když se pole v průběhu aplikace kroku 1 na všechny stavy nezmění, algoritmus je dokončen.

Iterace zásad je u velkého počtu možných stavů obvykle pomalejší než iterace hodnot.

Upravená iterace zásad

V upravené iteraci zásad ( van Nunen 1976 ; Puterman & Shin 1978 ) se první krok provede jednou a druhý krok se několikrát opakuje. Poté se krok jedna provede znovu jednou a tak dále.

Upřednostňováno zametání

V této variantě se kroky přednostně aplikují na stavy, které jsou nějakým způsobem důležité - ať už na základě algoritmu (v těchto stavech nebo v jejich okolí došlo v poslední době k velkým změnám ) nebo na základě použití (tyto stavy jsou blízko počátečního stavu nebo jinak zájmu osoby nebo programu využívajícího algoritmus).

Rozšíření a zobecnění

Markovský rozhodovací proces je stochastická hra pouze s jedním hráčem.

Částečná pozorovatelnost

Výše uvedené řešení předpokládá, že stav je znám, když je třeba provést akci; jinak 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 přinesli Burnetas a Katehakis v „Optimálních adaptivních politikách pro Markovovy rozhodovací procesy“. V této práci byla vytvořena třída adaptivních politik, které mají vlastnosti rovnoměrně maximální míry konvergence pro celkovou očekávanou odměnu konečného horizontu za předpokladů konečných stavových prostorů a neredukovatelnosti přechodné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 inflací na pravé straně rovnic odhadované optimality průměrné odměny.

Posílení učení

Výukové učení využívá MDP tam, kde nejsou známy pravděpodobnosti nebo odměny.

Za tímto účelem je užitečné definovat další funkci, která odpovídá provedení akce a následnému optimálnímu pokračování (nebo podle jakékoli politiky, kterou aktuálně má):

I když je tato funkce také neznámá, zkušenost během učení je založena na párech (společně s výsledkem ; to znamená „Byl jsem ve stavu a zkusil jsem to udělat a stalo se“). Člověk má tedy pole a používá zkušenosti k jeho přímé aktualizaci. Toto je známé jako Q-learning .

Učení o posílení 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 iteraci hodnot a zásad. V učení posilování je místo explicitní specifikace pravděpodobností přechodu k pravděpodobnostem přechodu přistupováno prostřednictvím simulátoru, který je obvykle restartován mnohokrát z rovnoměrně náhodného počátečního stavu. Výukové učení lze také kombinovat s aproximací funkcí za účelem řešení problémů s velmi velkým počtem států.

Učební automaty

Další aplikace procesu MDP v teorii strojového učení se nazývá učební automaty. Pokud je prostředí stochastické, je to také jeden druh posilovacího učení. První papír automatů podrobného učení zkoumají Narendra a Thathachar (1974), které byly původně výslovně popsány jako automaty konečného stavu . Algoritmus učební automaty má podobně jako u posilovacího učení také tu výhodu, že vyřeší problém, když není známa pravděpodobnost nebo odměny. Rozdíl mezi automaty učení a Q-learningem je v tom, že dřívější technika vynechává paměť hodnot Q, ale aktualizuje pravděpodobnost akce přímo, aby našla výsledek učení. Učební automaty jsou učební schéma s přísným důkazem konvergence.

V učení teorie automatů se stochastický automat skládá 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 rs ,
  • vektor pravděpodobnosti počátečního stavu p (0) = ≪ p 1 (0), ..., p s (0) ≫,
  • vypočitatelná funkce které po každém časovém kroku t generuje p ( t + 1) z 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 " Markovova procesu diskrétních parametrů diskrétních parametrů ". V každém časovém kroku t = 0,1,2,3, ... automat čte vstup ze svého prostředí, aktualizuje P ( t ) na P ( t + 1) pomocí A , náhodně zvolí stav nástupce podle pravděpodobnosti P ( t + 1) a vydá odpovídající akci. Prostředí automatu zase přečte akci a odešle automatu další vstup.

Kategorie teoretická interpretace

Kromě odměn lze Markovův rozhodovací proces chápat z hlediska teorie kategorií . Konkrétně, ať označují volné monoid s nastavenou generující A . Let Dist označují kategorii Kleisli na Giry monádě . Pak se funktorové kóduje obě sady S stavů a pravděpodobnostní funkce P .

Tímto způsobem by Markovovy rozhodovací procesy mohly být generalizovány z monoidů (kategorie s jedním objektem) na libovolné kategorie. Jeden může volat Výsledkem je kontextově závislý Markov rozhodovací proces , protože přechod z jednoho objektu do druhého změn soubor dostupných akcí a sadu možných stavů.

Nepřetržitý Markovův rozhodovací proces

V diskrétních Markovských rozhodovacích procesech jsou rozhodnutí přijímána v diskrétních časových intervalech. V případě Markovových rozhodovacích procesů s nepřetržitým časem lze rozhodnutí učinit kdykoli si to rozhodovací orgán zvolí. Ve srovnání s Markovovými rozhodovacími procesy v diskrétním čase mohou Markovovy rozhodovací procesy s nepřetržitým časem lépe modelovat rozhodovací proces pro systém, který má spojitou dynamiku , tj. Dynamika systému je definována parciálními diferenciálními rovnicemi (PDE).

Definice

Abychom mohli diskutovat o Markovově rozhodovacím procesu v nepřetržitém čase, zavedeme dvě sady zápisů:

Pokud je 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ého ovládání;
  • : , funkce přechodové rychlosti;
  • : , funkce míry odměny taková, že kde je funkce odměny, kterou jsme probrali v předchozím případě.

Problém

Stejně jako Markovovy rozhodovací procesy v diskrétním čase, v Markovských rozhodovacích procesech s nepřetržitým časem chceme najít optimální politiku nebo kontrolu, která by nám mohla 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 použít lineární programování k nalezení optimální politiky, což byl jeden z prvních aplikovaných přístupů. Zde uvažujeme pouze ergodický model, což znamená, že se naše MDP s nepřetržitým časem stává ergodickým Markovovým řetězcem s kontinuálním časem v rámci stacionární politiky . Za tohoto předpokladu, i když rozhodovací orgán může učinit rozhodnutí kdykoli v aktuálním stavu, nemohli mít větší prospěch tím, že provedli více než jednu akci. Je pro ně lepší provést akci pouze v době, kdy systém přechází z aktuálního stavu do jiného stavu. Za určitých podmínek (pro podrobnější kontrolu Důsledek 3.14 Markovských rozhodovacích procesů s nepřetržitým časem ), pokud je naše optimální hodnotová funkce nezávislá na stavu , budeme mít následující nerovnost:

Pokud existuje funkce , pak bude nejmenší splňující výše uvedenou rovnici. Abychom našli , mohli bychom 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í D-LP, pokud není přirozené a splňuje omezení v problému D-LP. Proveditelné řešení D-LP je považováno za optimální řešení, pokud

pro všechna možná řešení D-LP. Jakmile najdeme optimální řešení , můžeme jej použít k vytvoření optimálních zásad.

Hamilton – Jacobi – Bellmanova rovnice

Pokud je v MDP spojitého času stavový prostor a akční prostor spojitý, mohlo by být optimální kritérium nalezeno řešením parciální diferenciální rovnice Hamilton – Jacobi – Bellman (HJB) . Abychom mohli diskutovat o rovnici HJB, musíme svůj problém přeformulovat

je funkce odměny terminálu, je vektor stavu systému, je vektor řízení systému, který se snažíme najít. ukazuje, jak se stavový vektor v průběhu času mění. Rovnice Hamilton – Jacobi – Bellman je následující:

Rovnici bychom mohli vyřešit tak, abychom našli optimální řízení , což by nám mohlo poskytnout funkci optimální hodnoty

aplikace

Markovovy rozhodovací procesy s nepřetržitým časem mají aplikace v systémech zařazování do front , epidemických procesech a populačních procesech .

Alternativní zápisy

Terminologie a zápis pro MDP nejsou zcela vyřešeny. Existují dva hlavní proudy - jeden se zaměřuje na problémy maximalizace z kontextů, jako je ekonomika, pomocí výrazů akce, odměna, hodnota a volání faktoru slevy nebo , zatímco druhý se zaměřuje na problémy s minimalizací z oblasti strojírenství a navigace, pomocí výrazů kontrola, náklady „cost-to-go“ a volání na faktor slevy . Kromě toho se zápis pravděpodobnosti přechodu liší.

v tomto článku alternativní komentář
akce řízení
odměna náklady je záporem
hodnota náklady na cestu je záporem
politika politika
diskontní faktor diskontní faktor
pravděpodobnost přechodu pravděpodobnost přechodu

Navíc pravděpodobnost přechodu je někdy psáno , nebo, zřídka,

Omezené Markovovy rozhodovací procesy

Omezené Markovovy rozhodovací procesy (CMDP) jsou rozšířením Markovova rozhodovacího procesu (MDP). Mezi MDP a CMDP existují tři zásadní rozdíly.

Existuje řada aplikací pro CMDP. Nedávno byl použit ve scénářích pohybového plánování v robotice.

Viz také

Reference

Další čtení

externí odkazy