Markov decision process/cs - Revision history

Dmitry Borodin at 21:09, 12 June 2020

2020-06-12T21:09:30Z

Dmitry Borodin at 20:07, 12 June 2020

2020-06-12T20:07:32Z

Dmitry Borodin at 20:05, 12 June 2020

2020-06-12T20:05:41Z

Dmitry Borodin at 12:06, 12 June 2020

2020-06-12T12:06:59Z

Dmitry Borodin at 11:47, 12 June 2020

2020-06-12T11:47:08Z

Dmitry Borodin at 17:48, 11 June 2020

2020-06-11T17:48:27Z

Dmitry Borodin at 17:30, 11 June 2020

2020-06-11T17:30:32Z

Dmitry Borodin at 17:20, 11 June 2020

2020-06-11T17:20:58Z

Dmitry Borodin at 17:09, 11 June 2020

2020-06-11T17:09:04Z

Dmitry Borodin: Created page with "=Ú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...."

2020-06-11T16:54:19Z

Created page with "=Ú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...."

New page

=Ú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ů.<ref name="Zanini">ZANINI, Elena. Markov Decision Processes. [online] [cit. 2020-06-01] Dostupné z: https://www.lancaster.ac.uk/postgrad/zaninie/MDP.pdf/</ref>

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 <ref name="4IT495">ŠALAMON, Tomáš. Podklady k předmětu 4IT495 - Simulace systémů; VŠE - fakulta informatiky a statistiky. 10-Multiagent_systems_I_.pdf</ref>. MDP je obecnějším modelem (rozšířením) Markovských řetězců.<ref name="BP1">TŮMOVÁ, Jana. Paralelní ověřování kvalitativních vlastností pravděpodobnostních modelů. Brno,2006. Masarykova Univerzita, Fakulta informatiky. Vedoucí práce: Mgr. Jiří Barnat, Ph.D.</ref> 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.<ref name="Ibe">IBE, Oliver. Markov Processes for Stochastic Modeling. Saint Louis: Elsevier. 2013. ProQuest Ebook Central</ref> Postup obsahuje zkoumání současného stavu a vykonaní akce. K řešení se obvykle používají algoritmy dynamického programování.<ref name="DP">STÁREK, Ivo. Plánování cesty robota pomocí dynamického programování. Brno,2009. Vysoké učení technické v Brně, Fakulta strojního inženýrství. Vedoucí práce: RNDr. Jiří Dvořák, CSc.</ref> 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.<ref name="4IT495"/> 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.

=Citace=
<references/>

← Older revision		Revision as of 21:09, 12 June 2020
Line 98:		Line 98:

	Znovu správná strategie pro agenta jet rychle a v případě, že bude vyžádán – zastavit se.		Znovu správná strategie pro agenta jet rychle a v případě, že bude vyžádán – zastavit se.
		+
		+	==Příklad 2==
		+	Obchod plánuje svou práci na tři měsíce, ředitel obchodu musí rozhodnout: jaká opatření mohou stimulovat poptávku. Má na výběr následující možnosti: sleva 3 % na příští objednávku, doprava zdarma nebo nedělat nic. Kromě toho společnost oceňuje měsíční tržby: výborně, velmi dobře, dobře.
		+
		+	Jsou známé přechodné pravděpodobnosti a odpovídající měsíční příjmy pro každou možnost:
		+
		+	[[File:Priklad2ZadaniDimBo.PNG\|800px]]
		+
		+	Cílem je najít optimální strategii pro stimulaci poptávky. V našem případě máme 3 měsíce a 3 úrovní poptávky (výborně, velmi dobře, dobře).
		+
		+	<math> \nu_1^1=0.4110+0.5100+0.1*70=101</math>
		+
		+	<math> \nu_2^1=0.1105+0.690+0.3*65=84</math>
		+
		+	<math> \nu_3^1=0100+0.285+0.8*60=65</math>
		+
		+
		+	<math> \nu_1^2=0.3130+0.6110+0.1*90=114</math>
		+
		+	<math> \nu_2^2=0130+0.4100+0.6*85=91</math>
		+
		+	<math> \nu_3^2=0125+0.298+0.8*80=83.6</math>
		+
		+
		+	<math> \nu_1^3=0.3100+0.390+0.4*70=85</math>
		+
		+	<math> \nu_2^3=0.1110+0.795+0.2*65=90.5</math>
		+
		+	<math> \nu_3^3=0.05100+0.285+0.75*60=67</math>
		+
		+	S ohledem na náklady každé strategie (10, 20, 0):
		+
		+	[[File:Priklad2DimBo.PNG\|800px]]
		+
		+	Optimální řešení ukazuje, že v prvním a druhém měsíci by společnost měla stimulovat poptávku pomocí bezplatného doručení (pokud poptávka bude “výborná” nebo “velmi dobrá”). Pokud je poptávka jen “dobrá“, nemělo by se nic dělat. Ve třetím měsíci by měl obchod zajistit dodání zdarma bez ohledu na stav systému.

	=Závěr=		=Závěr=

@@ Line 93: / Line 93: @@
 A(pomalu): <math>7*1 = 7</math>
-<i>A(rychle-zastaví): <math>2*0.2+10*0.8=8,4</math></i>
+A(rychle-zastaví): <math>2*0.2+10*0.8=8,4</math>
 A(rychle-ujede): <math>0.2*(0.15*20+0.85*(-50))+0.8*10=0.1</math>
 =Závěr=

@@ Line 49: / Line 49: @@
 Jiný druh nejistoty vzniká, když pravděpodobnosti nebo odměny nejsou známé. Populární oblastí, která se zabývá takovýmto problémem (zejména v oblasti umělé inteligence) je oblast zpětnovazebního 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.
 =Zdroje=
 ==Reference==

← Older revision		Revision as of 12:06, 12 June 2020
Line 50:		Line 50:


−	=~~Citace~~=	+	=Zdroje=
		+	==Reference==
	<references/>		<references/>
		+	==Doplňující literatura==
		+	Piunovskiy, Alexey B. 2012. Examples In Markov Decision Processes. Singapore: World Scientific Publishing Company. ProQuest Ebook Central.
		+
		+	Feinberg E., Shwartz A. 2012. Handbook of Markov decision processes: methods and applications. Springer-Verlag New York Inc.
		+	==Videa==
		+	[https://www.coursera.org/lecture/fundamentals-of-reinforcement-learning/markov-decision-processes-8T0GQ Coursera - Markov Decision Processes]
		+
		+	[https://www.coursera.org/lecture/fundamentals-of-reinforcement-learning/examples-of-mdps-ACRYv Coursera - Examples of MDPs]
		+
		+	[https://www.youtube.com/watch?v=my207WNoeyA Markov Decision Processes (MDPs) - Structuring a Reinforcement Learning Problem]

@@ Line 3: / Line 3: @@
 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ů.<ref name="Zanini">ZANINI, Elena. <i>Markov Decision Processes.</i> [online] [cit. 2020-06-01] Dostupné z: https://www.lancaster.ac.uk/postgrad/zaninie/MDP.pdf/</ref>
-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 <ref name="4IT495">ŠALAMON, Tomáš. <i>Podklady k předmětu 4IT495 - Simulace systémů; VŠE - fakulta informatiky a statistiky. 10-Multiagent_systems_I_.pdf</i></ref>. MDP je obecnějším modelem (rozšířením) Markovských řetězců.<ref name="BP1">TŮMOVÁ, Jana. <i>Paralelní ověřování kvalitativních vlastností pravděpodobnostních modelů</i>. Brno,2006. Masarykova Univerzita, Fakulta informatiky. Vedoucí práce: Mgr. Jiří Barnat, Ph.D.</ref> 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.<ref name="Ibe">IBE, Oliver. <i>Markov Processes for Stochastic Modeling. Saint Louis: Elsevier</i>. 2013. ProQuest Ebook Central</ref> Postup obsahuje zkoumání současného stavu a vykonaní akce. K řešení se obvykle používají algoritmy dynamického programování.<ref name="DP">STÁREK, Ivo. <i>Plánování cesty robota pomocí dynamického programování</i>. Brno,2009. Vysoké učení technické v Brně, Fakulta strojního inženýrství. Vedoucí práce: RNDr. Jiří Dvořák, CSc.</ref> 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.<ref name="4IT495"/> 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.
+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 <ref name="4IT495">ŠALAMON, Tomáš. <i>Podklady k předmětu 4IT495 - Simulace systémů; VŠE - fakulta informatiky a statistiky. 10-Multiagent_systems_I_.pdf</i></ref>. MDP je obecnějším modelem (rozšířením) [https://cs.wikipedia.org/wiki/Markov%C5%AFv_%C5%99et%C4%9Bzec Markovských řetězců].<ref name="BP1">TŮMOVÁ, Jana. <i>Paralelní ověřování kvalitativních vlastností pravděpodobnostních modelů</i>. Brno,2006. Masarykova Univerzita, Fakulta informatiky. Vedoucí práce: Mgr. Jiří Barnat, Ph.D.</ref> 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.<ref name="Ibe">IBE, Oliver. <i>Markov Processes for Stochastic Modeling. Saint Louis: Elsevier</i>. 2013. ProQuest Ebook Central</ref> Postup obsahuje zkoumání současného stavu a vykonaní akce. K řešení se obvykle používají algoritmy [https://cs.wikipedia.org/wiki/Dynamick%C3%A9_programov%C3%A1n%C3%AD dynamického programování].<ref name="DP">STÁREK, Ivo. <i>Plánování cesty robota pomocí dynamického programování</i>. Brno,2009. Vysoké učení technické v Brně, Fakulta strojního inženýrství. Vedoucí práce: RNDr. Jiří Dvořák, CSc.</ref> 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.<ref name="4IT495"/> 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.
 =Definice=
-V této časti se soustředíme na konkrétnější definici a matematický vzore. Nutné zmínit, že existují různé formulace pro MDP, avšak klíčové aspekty jsou stejné. V MDP existuje “tvůrce rozhodnutí“, který se nazývá agent. Agent interaguje s prostředím, ve kterém je umístěn. K těmto interakcím dochází postupně. V každém kroku agent získává určitou reprezentaci stavu prostředí. Vzhledem k této reprezentaci agent vybere akci, kterou má provést. Prostředí je poté převedeno do nového stavu a agent dostává odměnu v důsledku předchozí akce.
+V této časti se soustředíme na konkrétnější definici a matematický vzore. Nutné zmínit, že existují různé formulace pro MDP, avšak klíčové aspekty jsou stejné. V MDP existuje “tvůrce rozhodnutí“, který se nazývá [[Agents/cs|agent]]. Agent interaguje s [[Agent environments/cs|prostředím]], ve kterém je umístěn. K těmto interakcím dochází postupně. V každém kroku agent získává určitou reprezentaci stavu prostředí. Vzhledem k této reprezentaci agent vybere akci, kterou má provést. Prostředí je poté převedeno do nového stavu a agent dostává odměnu v důsledku předchozí akce.
 Komponenty MDP:
@@ Line 16: / Line 16: @@
 Proces výběru akce z daného stavu, přechodu do nového stavu a získání odměny se děje postupně znovu a znovu. Výsledkem je trajektorie/mapa, která ukazuje posloupnost stavů, akcí a odměn. V průběhu tohoto procesu je cílem agenta maximalizovat celkové množství odměn, které získává za provádění akcí. To znamená, že agent chce maximalizovat nejen okamžitou odměnu, ale kumulativní odměny, které dostává v průběhu času. Posledním nezbytným bodem je tranzitní (přechodová) funkce, která označuje pravděpodobnost přechodu z jednoho stavu do jiného při volbě určité akce.
-Markovův rozhodovací proces pak může být definován jako uspořádaná čtveřice prvků {S, A, T, R}, kde
+Markovův rozhodovací proces pak může být definován jako [https://cs.wikipedia.org/wiki/Uspo%C5%99%C3%A1dan%C3%A1_n-tice uspořádaná čtveřice] prvků {S, A, T, R}, kde
 * S – značí konečnou množinu stavů.
 * A – značí konečnou množinu akcí, pro každý stav je možno určit určitou množinu akcí.

@@ Line 34: / Line 34: @@
 [[File:Dynamicke2.PNG|500px|]]
-==Iterace hodnot==
+===Iterace hodnot===
-Tento přistup navrhl Bellman v roce 1957 [3], přístup iterace hodnot, nazývaný také zpětná indukce. Algoritmus vypočítává očekávanou hodnotu každého stavu pomocí hodnoty sousedních stavů až do konvergence.
+Tento přistup navrhl Bellman v roce 1957 <ref name="Ibe"/>, přístup iterace hodnot, nazývaný také zpětná indukce. Algoritmus vypočítává očekávanou hodnotu každého stavu pomocí hodnoty sousedních stavů až do konvergence.
 =Citace=
 <references/>