Proces decyzyjny Markowa

W matematyce proces decyzyjny Markowa ( MDP ) jest stochastycznym procesem sterowania w czasie dyskretnym . Zapewnia ramy matematyczne do modelowania podejmowania decyzji w sytuacjach, w których wyniki są częściowo losowe , a częściowo pod kontrolą decydenta. MDP są przydatne do badania problemów optymalizacyjnych rozwiązywanych za pomocą programowania dynamicznego . MDP były znane co najmniej już w latach pięćdziesiątych; główny zbiór badań nad procesami decyzyjnymi Markowa powstał dzięki Ronaldowi Howardowi Książka z 1960 roku, Programowanie dynamiczne i procesy Markowa . Znajdują zastosowanie w wielu dziedzinach, w tym w robotyce , automatyce , ekonomii i produkcji . Nazwa MDP pochodzi od rosyjskiego matematyka Andrieja Markowa, ponieważ są one przedłużeniem łańcuchów Markowa .

Na każdym etapie proces znajduje się w jakimś stanie $,$$a$ może wybrać dowolną akcję , jest dostępna w $.$ Proces reaguje w następnym kroku czasowym, losowo przechodząc do nowego stanu $s')}$$′$ odpowiednią nagrodę. ${\ Displaystyle R_ {a} (s$ .

Na prawdopodobieństwo przejścia procesu do nowego stanu $.$ akcja W szczególności jest to określone przez funkcję przejścia stanu ${\ Displaystyle P_ {a} (s, s')}$ . Tak $}$ następny stan $działania$ od stanu bieżącego $za {\ displaystyle$ decydenta . Ale biorąc pod $i$ , jest warunkowo niezależny od wszystkich poprzednich stanów i $;$ innymi słowy, przejścia stanu MDP spełniają własność Markowa .

Procesy decyzyjne Markowa są przedłużeniem łańcuchów Markowa ; różnica polega na dodaniu działań (pozwalających na wybór) i nagród (dających motywację). I odwrotnie, jeśli dla każdego stanu istnieje tylko jedno działanie (np. „czekaj”) i wszystkie nagrody są takie same (np. „zero”), proces decyzyjny Markowa sprowadza się do łańcucha Markowa.

Definicja

Przykład prostego MDP z trzema stanami (zielone kółka) i dwiema akcjami (pomarańczowe kółka), z dwiema nagrodami (pomarańczowe strzałki).

Proces decyzyjny Markowa to 4- krotka ${\ Displaystyle (S, A, P_ {a}, R_ {a})}$ , gdzie:

• ${\ displaystyle S}$ to zbiór stanów zwanych przestrzenią stanów , S {\ displaystyle S}
• ${\ displaystyle A}$ to zbiór działań zwanych przestrzenią akcji (alternatywnie to zbiór działań dostępnych ze stanu $\ displaystyle A_ {s}$$, ZA$ }
• ${\ Displaystyle P_ {a} (s, s') = \ Pr (s_ {t + 1} = s '\ mid s_ {t} = s, a_ {t} = a)}$ to prawdopodobieństwo, że akcja $displaystyle$ w stanie $s}$ w czasie ${\ displaystyle t}$ doprowadzi do stanu w czasie , ${\ displaystyle s'}$${\ displaystyle t + 1$ }
• ${a} (s, s')}$$s'}$ natychmiastową nagrodą (lub oczekiwaną natychmiastową nagrodą) otrzymaną po przejściu ze stanu do stanu $s}$${\ displaystyle$ , w wyniku działania ${\ displaystyle a}$

Przestrzenie stanów i akcji mogą być skończone lub nieskończone, na przykład zbiór liczb rzeczywistych . Niektóre procesy z policzalnie nieskończonymi przestrzeniami stanów i działań można zredukować do procesów ze skończonymi przestrzeniami stanów i działań.

Funkcja polityki $($$)$ ) odwzorowanie z przestrzeni stanów ( ) $na$ przestrzeń akcji

Cel optymalizacji

Celem procesu decyzyjnego Markowa jest znalezienie dobrej „polityki” dla decydenta: funkcji, $}$ określa działanie, które podejmuje decydent ${\ displaystyle \ pi (s)$ wybierze, kiedy będzie w stanie ${\ displaystyle s}$ . Po połączeniu procesu decyzyjnego Markowa z polityką w ten sposób ustala się działanie dla każdego stanu, a wynikowa kombinacja zachowuje się jak łańcuch Markowa (ponieważ działanie wybrane w stanie ${\ displaystyle s}$ π $\ pi (s)}$${\ Displaystyle \ Pr (s_ {t + 1} =s'\mid s_{t}=s,a_{t}=a)}$ i redukuje się do ${\ Displaystyle \ Pr (s_ {t + 1} = s' \ mid s_ {t} = s)}$ , macierz przejść Markowa).

Celem jest wybranie polityki , która zmaksymalizuje pewną skumulowaną funkcję losowych nagród, zazwyczaj oczekiwaną zdyskontowaną sumę w potencjalnie nieskończonym horyzoncie: ${\ displaystyle \ pi }$

$t$${\ Displaystyle E \ lewo [\ suma _ {t = 0} ^ {\ infty} {\ gamma ^ {t} R_ {$ za ${\ Displaystyle a_ {t} = \ pi (s_ {$ , czyli działania podane przez politykę). A oczekiwanie jest przejmowane ${\ Displaystyle s_ {t + 1} \ sim P_ {a_ {t}} (s_ {t}, s_ {t + 1})}$

gdzie $jest$ współczynnikiem dyskontującym spełniającym $,$$)$ bliski 1 dla pewnej Niższy czynnik dyskontujący motywuje decydenta do wcześniejszego podejmowania działań, zamiast odkładania ich w nieskończoność.

Polityka, która maksymalizuje powyższą funkcję, nazywana jest polityką optymalną i jest zwykle oznaczana . $}$ } Konkretny MDP może mieć wiele odrębnych optymalnych zasad. Ze względu na własność Markowa można wykazać, że optymalna polityka jest funkcją stanu obecnego, jak założono powyżej.

Modele symulacyjne

$przypadkach$ przedstawić przejścia W takich przypadkach można użyć symulatora do niejawnego modelowania MDP, dostarczając próbki z rozkładów przejściowych. Jedną z powszechnych form niejawnego modelu MDP jest epizodyczny symulator środowiska, który można uruchomić ze stanu początkowego i daje kolejny stan i nagrodę za każdym razem, gdy otrzymuje dane wejściowe akcji. W ten sposób trajektorie stanów, akcji i nagród, często nazywane epizodami mogą być produkowane.

Inną formą symulatora jest model generatywny , jednoetapowy symulator, który może generować próbki następnego stanu i nagradzać dany stan i działanie. (Zauważ, że jest to inne $go$ niż termin model generatywny w kontekście klasyfikacji statystycznej). W algorytmach , które są wyrażane za pomocą pseudokodu , często używa się do reprezentowania modelu generatywnego. Na przykład wyrażenie $s', r \ pobiera G (s, a)}$$displaystyle a}$ może oznaczać akcję próbkowania z modelu generatywnego, gdzie $\$ { to obecny stan i akcja, a ${\ displaystyle s'}$ i ${\ displaystyle r}$ to nowy stan i nagroda. W porównaniu z symulatorem epizodycznym model generatywny ma tę zaletę, że może generować dane z dowolnego stanu, nie tylko napotkanego na trajektorii.

Te klasy modeli tworzą hierarchię treści informacji: model jawny w prosty sposób daje model generatywny poprzez próbkowanie z rozkładów, a wielokrotne stosowanie modelu generatywnego daje symulator epizodyczny. W przeciwnym kierunku możliwe jest jedynie poznanie przybliżonych modeli poprzez regresję . Rodzaj modelu dostępnego dla konkretnego MDP odgrywa znaczącą rolę w określaniu, które algorytmy rozwiązania są odpowiednie. Na przykład programowania dynamicznego opisane w następnej sekcji wymagają jawnego modelu i przeszukiwania drzewa metodą Monte Carlo wymaga modelu generatywnego (lub symulatora epizodycznego, który można skopiować w dowolnym stanie), podczas gdy większość algorytmów uczenia się przez wzmacnianie wymaga jedynie symulatora epizodycznego.

Algorytmy

Rozwiązania dla MDP ze skończonymi przestrzeniami stanów i akcji można znaleźć za pomocą różnych metod, takich jak programowanie dynamiczne . Algorytmy w tej sekcji mają zastosowanie do MDP ze skończonymi przestrzeniami stanów i akcji oraz jawnie określonymi prawdopodobieństwami przejścia i funkcjami nagrody, ale podstawowe koncepcje można rozszerzyć, aby obsłużyć inne klasy problemów, na przykład za pomocą aproksymacji funkcji .

Standardowa rodzina algorytmów do obliczania optymalnych zasad dla MDP o skończonych stanach i działaniach wymaga przechowywania dwóch tablic indeksowanych według stanu: wartość , która zawiera wartości rzeczywiste, i polityka , $displaystyle$ zawiera akcje $\ pi}$ . Na końcu algorytmu $displaystyle$ zawierał rozwiązanie i będzie zawierał zdyskontowaną sumę nagród, które można zdobyć (średnio), stosując się do tego rozwiązania π ${$ ze stanu ${\ displaystyle s}$ .

Algorytm składa się z dwóch etapów, (1) aktualizacji wartości i (2) aktualizacji zasad, które są powtarzane w pewnej kolejności dla wszystkich stanów, dopóki nie nastąpią żadne dalsze zmiany. Oba rekurencyjnie aktualizują nowe oszacowanie optymalnej polityki i wartości stanu, używając starszego oszacowania tych wartości.

${\ Displaystyle V (s): = \ suma _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)}$

${\ Displaystyle \ pi (s): = \ operatorname {argmax} _ { a}\left\{\suma _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\ }}$

Ich kolejność zależy od wariantu algorytmu; można je również wykonać dla wszystkich stanów naraz lub dla stanu po stanie, a częściej dla niektórych stanów niż innych. Dopóki żaden stan nie zostanie trwale wykluczony z żadnego z etapów, algorytm ostatecznie dotrze do właściwego rozwiązania.

Godne uwagi warianty

Iteracja wartości

W iteracji wartości ( Bellman 1957 ), która jest również nazywana $indukcją$ wsteczną , nie jest używana; $_$$tego$ wartość obliczana w Zastąpienie obliczenia ${\ Displaystyle \ pi (s)}$ do obliczenia ${\ Displaystyle V (s)}$ daje połączony krok :

${\ Displaystyle V_ {i + 1}(s):=\max _{a}\left\{\suma _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V_{i}(s')\prawo)\prawo\},}$

gdzie $.$ liczbą iteracji Iteracja wartości zaczyna się od ${\ displaystyle$${0}}$ jako odgadnięcie funkcji wartości . $się$ iteruje, wielokrotnie obliczając $dla$ wszystkich stanów $zbiega$ lewą stroną równą prawej boku (co jest równaniem Bellmana „dla tego problemu ). Artykuł Lloyda Shapleya z 1953 r. na temat gier stochastycznych zawierał jako szczególny przypadek metodę iteracji wartości dla MDP, ale uznano to dopiero później.

Iteracja polityki

W iteracji polityki ( Howard 1960 ) krok pierwszy jest wykonywany raz, a następnie krok drugi jest wykonywany raz, a następnie oba są powtarzane, aż polityka będzie zbieżna. Następnie krok pierwszy jest ponownie wykonywany raz i tak dalej. (Iteracja zasad została wymyślona przez Howarda w celu optymalizacji Sears , którą optymalizował za pomocą iteracji wartości).

Zamiast powtarzać krok drugi do zbieżności, można ją sformułować i rozwiązać jako zestaw równań liniowych. Równania $te$ uzyskuje się po prostu przez wykonanie . Zatem powtórzenie kroku drugiego do zbieżności można interpretować jako rozwiązanie równań liniowych przez relaksację .

$wariant$ ma tę zaletę, że istnieje określony warunek zatrzymania: gdy tablica zmienia się w trakcie stosowania kroku 1 do wszystkich stanów, algorytm jest zakończony.

Iteracja zasad jest zwykle wolniejsza niż iteracja wartości dla dużej liczby możliwych stanów.

Zmodyfikowana iteracja zasad

W zmodyfikowanej iteracji polityki ( van Nunen 1976 ; Puterman i Shin 1978 ) krok pierwszy jest wykonywany raz, a następnie krok drugi jest powtarzany kilka razy. Następnie krok pierwszy jest ponownie wykonywany raz i tak dalej.

Zamiatanie priorytetowe

$są$$lub$ w jakiś sposób ważne - czy to na podstawie algorytmu ( ostatnio nastąpiły duże zmiany w tych stanach) oparte w użyciu (te stany są bliskie stanu początkowego lub w inny sposób interesują osobę lub program korzystający z algorytmu).

Rozszerzenia i uogólnienia

Proces decyzyjny Markowa to gra stochastyczna z tylko jednym graczem.

Częściowa obserwowalność

Główny artykuł: Częściowo obserwowalny proces decyzyjny Markowa

Powyższe rozwiązanie zakłada, że ​​znany jest stan $w$ którym należy podjąć działanie; w przeciwnym razie nie można obliczyć ${\ Displaystyle \ pi (s)} .$ Kiedy to założenie nie jest prawdziwe, problem nazywa się częściowo obserwowalnym procesem decyzyjnym Markowa lub POMDP.

Uczenie się ze wzmocnieniem

Główny artykuł: Uczenie się przez wzmacnianie

Uczenie się ze wzmocnieniem wykorzystuje MDP, w których prawdopodobieństwa lub nagrody są nieznane.

W tym celu przydatne jest zdefiniowanie dodatkowej funkcji, która odpowiada podjęciu działania, ${\ displaystyle a}$ następnie optymalnemu kontynuowaniu (lub zgodnie z jakąkolwiek aktualnie obowiązującą polityką): za

${\ Displaystyle \ Q (s, a) = \ suma _ {s'} P_ {a} (s, s') (R_ {a} (s, s') + \ gamma V (s')). \ }$

$;$ funkcja jest również nieznana, doświadczenie podczas uczenia się opiera się na parach (wraz $stanie$ to ${\ displaystyle s}$ i próbowałem zrobić $i$${\ displaystyle a$ stało się") Tak więc mamy tablicę $,$ aby ją bezpośrednio zaktualizować. Jest to znane jako Q-learning .

Uczenie się ze wzmocnieniem może rozwiązywać procesy decyzyjne Markowa bez wyraźnego określenia prawdopodobieństw przejścia; wartości prawdopodobieństw przejścia są potrzebne w iteracji wartości i polityki. W uczeniu się przez wzmacnianie, zamiast jawnej specyfikacji prawdopodobieństw przejścia, dostęp do prawdopodobieństw przejścia uzyskuje się za pośrednictwem symulatora, który jest zwykle wielokrotnie uruchamiany ponownie z jednakowo losowego stanu początkowego. Uczenie się przez wzmacnianie można również połączyć z aproksymacją funkcji, aby rozwiązać problemy z bardzo dużą liczbą stanów.

Uczenie się automatów

Główny artykuł: Automaty uczące się

Innym zastosowaniem procesu MDP w teorii uczenia maszynowego są automaty uczące. Jest to również jeden rodzaj uczenia się przez wzmacnianie, jeśli środowisko jest stochastyczne. Pierwsza dotycząca automatów uczących się szczegółów została przeanalizowana przez Narendra i Thathachar (1974), które pierwotnie zostały wyraźnie opisane jako automaty skończone . Podobnie jak w przypadku uczenia się przez wzmacnianie, algorytm automatów uczących się ma również tę zaletę, że rozwiązuje problem, gdy prawdopodobieństwo lub nagrody są nieznane. Różnica między automatami uczącymi się a uczeniem Q polega na tym, że poprzednia technika pomija pamięć wartości Q, ale bezpośrednio aktualizuje prawdopodobieństwo działania, aby znaleźć wynik uczenia. Automaty uczące to schemat uczenia się z rygorystycznym dowodem zbieżności.

W teorii automatów uczenia się automat stochastyczny składa się z:

• zbiór x możliwych wejść,
• zbiór Φ = { Φ ₁ , ..., Φ _s } możliwych stanów wewnętrznych,
• zbiór α = { α ₁ , ..., α _r } możliwych wyników lub działań, przy czym r ≤ s ,
• wektor prawdopodobieństwa stanu początkowego p (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• obliczalna funkcja A , która po każdym kroku czasowym t generuje p ( t + 1) z p ( t ), bieżącego wejścia i bieżącego stanu, oraz
• funkcja G : Φ → α, która generuje wyjście w każdym kroku czasowym.

Stany takiego automatu odpowiadają stanom „ procesu Markowa o parametrach dyskretnych ”. W każdym kroku czasowym t = 0,1,2,3,... automat odczytuje dane wejściowe ze swojego otoczenia, aktualizuje P( t ) do P( t + 1) przez A , losowo wybiera stan następczy zgodnie z prawdopodobieństwa P( t + 1) i wyprowadza odpowiednie działanie. Z kolei środowisko automatu odczytuje akcję i wysyła kolejne wejście do automatu.

Interpretacja teorii kategorii

$Poza$ nagrodami proces w kategoriach Mianowicie, niech $monoid$ wolny ze zbiorem generującym A . Niech Dist oznacza kategorię Kleisliego monady Giry'ego . Wtedy funktor ${\ Displaystyle {\ mathcal {A}} \ do \ mathbf {Dist}}$ koduje zarówno zbiór S stanów, jak i funkcję prawdopodobieństwa P .

W ten sposób procesy decyzyjne Markowa można uogólnić z monoidów (kategorii z jednym obiektem) na dowolne kategorie. Wynik można nazwać kontekstem ( $\ Displaystyle ({\ mathcal {C}}, F: {\ mathcal {C}} \ do \ mathbf {Dist})$ } zależny proces decyzyjny Markowa , ponieważ przejście z jednego $w$ do drugiego zmienia zestaw dostępnych działań i zbiór możliwych stanów.

Proces decyzyjny Markowa w czasie ciągłym

W dyskretnych procesach decyzyjnych Markowa decyzje są podejmowane w dyskretnych odstępach czasu. Jednak w przypadku procesów decyzyjnych Markowa w czasie ciągłym decyzje mogą być podejmowane w dowolnym momencie wybranym przez decydenta. W porównaniu z procesami decyzyjnymi Markowa w czasie dyskretnym, procesy decyzyjne Markowa w czasie ciągłym mogą lepiej modelować proces decyzyjny dla systemu, który ma dynamikę ciągłą , tj. dynamikę systemu definiują równania różniczkowe zwyczajne (ODE).

Definicja

W celu omówienia ciągłego procesu decyzyjnego Markowa wprowadzamy dwa zestawy notacji:

Jeśli przestrzeń stanów i przestrzeń akcji są skończone,

• ${\ Displaystyle {\ mathcal {S}}}$ : Przestrzeń stanów;
• ${\ Displaystyle {\ mathcal {A}}}$ : Przestrzeń akcji;
• ${\ Displaystyle q (i \ mid j, a)}$ S $\ Displaystyle {\ mathcal {S}} \ razy {\ mathcal {A}} \ rightarrow \ trójkąt {\ mathcal {S}}}$ , funkcja szybkości przejścia;
• ${\ Displaystyle R (i, a)}$ : ${\ Displaystyle {\ mathcal {S}} \ razy {\ mathcal {A}} \ rightarrow \ mathbb {R}}$ , funkcję nagrody.

Jeśli przestrzeń stanów i przestrzeń akcji są ciągłe,

• ${\ Displaystyle {\ mathcal {X}}}$ : przestrzeń stanów;
• ${\ Displaystyle {\ mathcal {U}}}$ : przestrzeń możliwej kontroli;
• ${\ Displaystyle f (x, u)}$ : ${\ Displaystyle {\ mathcal {X}} \ razy {\ mathcal {U}} \ strzałka w prawo \ trójkąt {\ mathcal { X}}}$ , funkcja szybkości przejścia;
• ${\ Displaystyle r (x, u)}$ : ${\ Displaystyle {\ mathcal {X}} \ razy {\ mathcal {U}} \ rightarrow \ mathbb {R}}$ , funkcja stopy nagrody taka, że ${\ Displaystyle r (x (t), u (t)} \, dt = dR (x (t), u (t))} , gdzie R$ ( $Displaystyle R (x, u)}$ jest funkcją nagrody, którą omówiliśmy w poprzednim przypadku.

Problem

Podobnie jak w procesach decyzyjnych Markowa w czasie dyskretnym, w procesach decyzyjnych Markowa w czasie ciągłym chcemy znaleźć optymalną politykę lub kontrolę , która mogłaby dać nam optymalną oczekiwaną zintegrowaną nagrodę:

${\ Displaystyle \ max \ nazwa operatora {E} _ {u} \ lewo [\ lewo. \ int _ {0} ^ {\ infty} \ gamma ^ {t} r (x (t), u (t) )\,dt\;\right|x_{0}\right]}$

gdzie ${\ Displaystyle 0 \ równoważnik \ gamma <1.}$

Formuła programowania liniowego

Jeśli przestrzeń stanu i przestrzeń działania są skończone, moglibyśmy użyć programowania liniowego, aby znaleźć optymalną politykę, co było jednym z najwcześniej zastosowanych podejść. Tutaj rozważamy tylko model ergodyczny, co oznacza, że ​​nasz MDP w czasie ciągłym staje się ergodycznym łańcuchem Markowa w czasie ciągłym przy polityce stacjonarnej . Przy takim założeniu, chociaż decydent może podjąć decyzję w dowolnym momencie w bieżącym stanie, nie mógłby skorzystać więcej, podejmując więcej niż jedno działanie. Lepiej dla nich, aby podejmowali działania tylko w momencie, gdy system przechodzi z obecnego stanu do innego. W pewnych warunkach (szczegółowe sprawdzenie Wniosku 3.14 $decyzyjnych$ Markowa w czasie ciągłym ), jeśli nasza funkcja wartości optymalnej $jest$ niezależna od stanu mieli następująca nierówność:

${\ Displaystyle g \ geq R (i, a) + \ suma _{j\in S}q(j\mid i,a)h(j)\quad \forall i\in S{\text{ i }}a\in A(i)}$

$Jeśli$ istnieje $spełniająca$ , $to$ będzie _ Aby znaleźć , moglibyśmy użyć następującego modelu programowania liniowego: ${\ displaystyle {\ bar {V}} ^ {*}}$

• Pierwotny program liniowy (P-LP)

${\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {Minimalizuj}} \ quad & g \\ {\ tekst {st}} \ quad & g - \ suma _ {j \ w S} q (j \ mid i, a) h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}} Dualny program liniowy (D-LP$

• )

${\ Displaystyle {\ rozpocząć {wyrównane} {\ tekst {Maksymalizuj}} & \ suma _ {i \ w S} \ suma _ {a \ w A (i)} R (i, a) y(i,a)\\{\text{st}}&\sum _{i\in S}\sum _{a\in A(i)}q(j\mid i,a)y(i, a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y( i,a)\geq 0\qquad \forall a\in A(i){\text{ and }}\forall i\in S\end{aligned}}}$

$Displaystyle y (i, a)}$$\$ -LP, jeśli nienatywny i spełnia ograniczenia w Problem z DLP. $że$ wykonalne rozwiązanie D-LP

${\ Displaystyle {\ rozpocząć {wyrównane} \ suma _ {i \ w S} \ suma _ {a \ w A (i)} R (i, a) y ^ {*} (i, a) \ geq \ suma _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{wyrównane}}}$

dla wszystkich możliwych rozwiązań do D-LP. ${\ Displaystyle y (i, a)} Gdy$$już$ znajdziemy optymalne rozwiązanie użyć go

Równanie Hamiltona-Jacobiego-Bellmana

W MDP w czasie ciągłym, jeśli przestrzeń stanów i przestrzeń akcji są ciągłe, optymalne kryterium można znaleźć, rozwiązując równanie różniczkowe cząstkowe Hamiltona – Jacobiego – Bellmana (HJB) . Aby omówić równanie HJB, musimy przeformułować nasz problem

${\ Displaystyle {\ rozpocząć {wyrównane} V (x (0), 0) = {} & \ max _ {u} \ int _ {0} ^ {T} r (x (t), u (t))\,dt+D[x(T)]\\{\text{st}}\quad &{\frac {dx(t)}{dt}}=f[t,x(t), u(t)]\end{wyrównane}}}$

${\ Displaystyle D (\ cdot)}$ to końcowa funkcja nagrody, ${\ Displaystyle x (t)}$ to wektor stanu systemu, jest ${\ Displaystyle u (t)}$ wektor kontrolny systemu, który próbujemy znaleźć. ${\ Displaystyle f (\ cdot)}$ pokazuje, jak wektor stanu zmienia się w czasie. Równanie Hamiltona – Jacobiego – Bellmana jest następujące:

${\ Displaystyle 0 = \ max _ {u} (r (t, x, u ) + {\ Frac {\ częściowe V (t, x)} {\ częściowe x}} f (t, x, u))}$

$,$ aby znaleźć optymalną kontrolę , która mogłaby dać nam funkcję optymalnej V $^ {*}}$

Aplikacja

Ciągłe procesy decyzyjne Markowa mają zastosowanie w systemach kolejkowych , procesach epidemicznych i procesach populacyjnych .

Notacje alternatywne

Terminologia i notacja dla MDP nie są całkowicie ustalone. Istnieją dwa główne nurty — jeden koncentruje się na problemach maksymalizacji z kontekstów takich jak ekonomia, używając terminów akcja, nagroda, wartość i nazywając czynnik dyskontowy β lub γ , podczas gdy drugi koncentruje się na problemach minimalizacji z inżynierii i nawigacji , używając terminów kontrola, koszt, koszt do wykorzystania i nazywając czynnik dyskontowy α . Ponadto notacja prawdopodobieństwa przejścia jest różna.

w tym artykule	alternatywny	komentarz
akcja _	kontrolować cię
nagroda r	koszt gr	g jest minusem R
wartość V	kosztowny j	J jest negatywem V
polityka π	polityka _
czynnik dyskontujący γ	czynnik dyskontujący α
prawdopodobieństwo przejścia ${\ Displaystyle P_ {a} (s, s')}$	${\ Displaystyle p_ {ss'} (a)$ }

Ponadto $_$ _ $_ mid s,a)}$ lub, rzadko, ${\ displaystyle p_ {s} (a).}$

Ograniczone procesy decyzyjne Markowa

Ograniczone procesy decyzyjne Markowa (CMDP) są rozszerzeniami procesu decyzyjnego Markowa (MDP). Istnieją trzy podstawowe różnice między MDP i CMDP.

• Istnieje wiele kosztów poniesionych po zastosowaniu akcji zamiast jednej.
• CMDP są rozwiązywane tylko za pomocą programów liniowych , a programowanie dynamiczne nie działa.
• Ostateczna polityka zależy od stanu początkowego.

Istnieje wiele aplikacji dla CMDP. Ostatnio był używany w scenariuszach planowania ruchu w robotyce.

Zobacz też

• Automaty probabilistyczne
• Algorytm szans
• Kwantowe automaty skończone
• Częściowo obserwowalny proces decyzyjny Markowa
• Programowanie dynamiczne
• Równanie Bellmana do zastosowań w ekonomii.
• Równanie Hamiltona-Jacobiego-Bellmana
• Optymalna kontrola
• Ekonomia rekurencyjna
• Problem owiec Mabinogion
• Gry stochastyczne
• Q-learning

Dalsza lektura

•   Bellman., RE (2003) [1957]. Programowanie dynamiczne (wyd. Dover w miękkiej oprawie). Princeton, NJ: Princeton University Press. ISBN 978-0-486-42809-3 .
• Bertsekas, D. (1995). Dynamiczne programowanie i optymalna kontrola . Tom. 2. MA: Atena.
• Derman, C. (1970). Procesy decyzyjne Markowa o skończonych stanach . Prasa akademicka.
•   Feinberg, EA; Shwartz, A., wyd. (2002). Podręcznik procesów decyzyjnych Markowa . Boston, MA: Kluwer. ISBN 9781461508052 .
•   Guo, X.; Hernández-Lerma, O. (2009). Procesy decyzyjne Markowa w czasie ciągłym . Modelowanie stochastyczne i stosowane prawdopodobieństwo . Skoczek. ISBN 9783642025464 .
•   Meyn, SP (2007). Techniki sterowania dla złożonych sieci . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-88441-9 . Zarchiwizowane od oryginału w dniu 19 czerwca 2010 r. Dodatek zawiera skróconą wersję „Meyn & Tweedie” . Zarchiwizowane od oryginału w dniu 18 grudnia 2012 r.
• Puterman., ML (1994). Procesy decyzyjne Markowa . Wileya.
• Ross, SM (1983). Wprowadzenie do stochastycznego programowania dynamicznego (PDF) . Prasa akademicka.
• Sutton, RS; Barto, AG (2017). Uczenie się ze wzmocnieniem: wprowadzenie . Cambridge, MA: The MIT Press.
•   Tijms., HC (2003). Pierwszy kurs modeli stochastycznych . Wileya. ISBN 9780470864289 .

Linki zewnętrzne

• Nauka rozwiązywania procesów decyzyjnych Markowa autorstwa Satinder P. Singh