Proces decyzyjny Markowa - Markov decision process

W matematyce proces decyzyjny Markowa ( MDP ) jest procesem sterowania stochastycznego w czasie dyskretnym . Zapewnia matematyczne ramy 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 . MDPs były znane co najmniej już w latach pięćdziesiątych; rdzeń badań nad procesami decyzyjnymi Markowa wynika z książki Ronalda Howarda z 1960 r., Dynamiczne programowanie i procesy Markowa . Znajdują zastosowanie w wielu dyscyplinach, m.in. robotyce , automatyce , ekonomii i produkcji . Nazwa MDPs pochodzi od rosyjskiego matematyka Andrieja Markowa, ponieważ są one przedłużeniem łańcuchów Markowa .

Na każdym etapie czasowym proces znajduje się w pewnym stanie , a decydent może wybrać dowolne działanie, które jest dostępne w stanie . Proces odpowiada w następnym kroku losowo przechodząc do nowego stanu i dając decydentowi odpowiednią nagrodę . ${\displaystyle s}$${\displaystyle a}$${\displaystyle s}$${\displaystyle s'}$${\ Displaystyle R_ {a} (s, s')}$

Prawdopodobieństwo , że proces przechodzi do nowej stanie zależy od wybranego działania. W szczególności jest to funkcja przejścia stanu . Zatem następny stan zależy od stanu obecnego i działania decydenta . Ale dane i , jest warunkowo niezależne od wszystkich poprzednich stanów i działań; innymi słowy, przejścia stanów MDP spełniają własność Markowa . ${\displaystyle s'}$${\ Displaystyle P_ {a} (s, s')}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s}$${\displaystyle a}$

Procesy decyzyjne Markowa są przedłużeniem łańcuchów Markowa ; różnica polega na dodawaniu 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 redukuje się do łańcucha Markowa.

Definicja

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

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

• ${\displaystyle S}$jest zbiorem stanów zwanym przestrzenią stanów ,
• ${\ Displaystyle A}$jest zbiorem akcji zwanym przestrzenią akcji (alternatywnie jest zbiorem akcji dostępnym ze stanu ),${\displaystyle A_{s}}$${\displaystyle s}$
• ${\ Displaystyle P_ {a} (s, s') = \ Pr (s_ {t + 1} = s '\ mid s_ {t} = s, a_ {t} = a)}$jest prawdopodobieństwem, że działanie w stanie w czasie doprowadzi do stanu w czasie ,${\displaystyle a}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s'}$${\displaystyle t+1}$
• ${\ Displaystyle R_ {a} (s, s')}$to natychmiastowa nagroda (lub oczekiwana natychmiastowa nagroda) otrzymana po przejściu ze stanu do stanu w wyniku działania${\displaystyle s}$${\displaystyle s'}$${\displaystyle a}$

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

Funkcja polityki to (potencjalnie probabilistyczne) mapowanie z przestrzeni stanów ( ) do przestrzeni akcji ( ). ${\displaystyle \pi}$${\displaystyle S}$${\ Displaystyle A}$

Cel optymalizacji

Celem procesu decyzyjnego Markowa jest znalezienie dobrej „polityki” dla decydenta: funkcji, która określa akcję, którą decydent wybierze w stanie . Gdy proces decyzyjny Markowa zostanie połączony w ten sposób z polityką, naprawia to akcję dla każdego stanu, a wynikowa kombinacja zachowuje się jak łańcuch Markowa (ponieważ akcja wybrana w stanie jest całkowicie określona przez macierz przejścia Markowa i redukuje się do niej) . ${\displaystyle \pi}$${\ Displaystyle \ pi (s)}$${\displaystyle s}$${\displaystyle s}$${\ Displaystyle \ pi (s)}$${\ Displaystyle \ Pr (s_ {t + 1} = s '\ mid s_ {t} = s, a_ {t} = a)}$${\ Displaystyle \ Pr (s_ {t + 1} = s '\ mid s_ {t} = s)}$

Celem jest wybór polityki , która zmaksymalizuje pewną skumulowaną funkcję losowych nagród, zazwyczaj oczekiwanej zdyskontowanej sumy w potencjalnie nieskończonym horyzoncie: ${\displaystyle \pi}$

${\ Displaystyle E \ lewo [\ suma _ {t = 0} ^ {\ infty} {\ gamma ^ {t} R_ {a_ {t}} (s_ {t}, s_ {t + 1})} \ prawej ]}$(gdzie wybieramy , czyli działania określone przez politykę). I oczekiwanie zostaje przejęte${\ Displaystyle a_ {t} = \ pi (s_ {t})}$${\ Displaystyle s_ {t + 1} \ sim P_ {a_ {t}} (s_ {t}, s_ {t + 1})}$

gdzie jest spełniony czynnik dyskontowy , który zwykle jest bliski 1 (na przykład dla pewnej stopy dyskontowej r). Niższy czynnik dyskontowy motywuje decydenta do wcześniejszego podejmowania działań, zamiast odkładania ich w nieskończoność. ${\ Displaystyle \ \ Gamma \ }$${\ Displaystyle 0 \ leq \ \ gamma \ \ leq \ 1}$${\ Displaystyle \ gamma = 1/(1 + r)}$

Polityka, która maksymalizuje powyższą funkcję, nazywana jest polityką optymalną i jest zwykle oznaczana jako . Konkretny MDP może mieć wiele odrębnych optymalnych polityk. Dzięki własności Markowa można wykazać, że optymalna polityka jest funkcją stanu obecnego, jak założono powyżej. ${\ Displaystyle \ pi ^ {*}}$

Modele symulatorów

W wielu przypadkach trudno jest jednoznacznie przedstawić rozkłady prawdopodobieństwa przejścia , . W takich przypadkach symulator może być użyty do niejawnego modelowania MDP poprzez dostarczenie próbek z rozkładów przejść. 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 działania. W ten sposób można wytworzyć trajektorie stanów, działań i nagród, często nazywane epizodami . ${\ Displaystyle P_ {a} (s, s')}$

Inną formą symulatora jest model generatywny , jednoetapowy symulator, który może generować próbki następnego stanu i nagradzać w przypadku dowolnego stanu i działania. (Zauważ, że jest to inne znaczenie niż termin model generatywny w kontekście klasyfikacji statystycznej.) W algorytmach wyrażanych za pomocą pseudokodu , jest często używany do reprezentowania modelu generatywnego. Na przykład wyrażenie może oznaczać czynność próbkowania z modelu generatywnego, gdzie i są stanem bieżącym i czynnością, a i są nowym stanem i nagrodą. W porównaniu z symulatorem epizodycznym, model generatywny ma tę zaletę, że może dostarczać dane z dowolnego stanu, nie tylko tych napotkanych na trajektorii. ${\ Displaystyle G}$${\displaystyle s',r\gets G(s,a)}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\ Displaystyle r}$

Te klasy modeli tworzą hierarchię zawartości informacji: model jawny w trywialny sposób daje model generatywny poprzez próbkowanie z rozkładów, a wielokrotne stosowanie modelu generatywnego daje epizodyczny symulator. W przeciwnym kierunku możliwe jest jedynie poznanie modeli przybliżonych poprzez regresję . Rodzaj modelu dostępnego dla konkretnego MDP odgrywa istotną rolę w określeniu, które algorytmy rozwiązania są odpowiednie. Na przykład algorytmy programowania dynamicznego opisane w następnej sekcji wymagają modelu jawnego, a wyszukiwanie drzewa 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 odnoszą się do MDP ze skończonymi przestrzeniami stanów i akcji oraz wyraźnie określonymi prawdopodobieństwami przejścia i funkcjami nagrody, ale podstawowe koncepcje można rozszerzyć o obsługę innych klas problemów, na przykład za pomocą aproksymacji funkcji .

Standardowa rodzina algorytmów do obliczania optymalnych polityk dla skończonych stanów i działań MDP wymaga przechowywania dwóch tablic indeksowanych według stanu: value , która zawiera wartości rzeczywiste, oraz policy , która zawiera akcje. Na końcu algorytmu będzie zawierał rozwiązanie i będzie zawierał zdyskontowaną sumę nagród do zdobycia (średnio) podążając za tym rozwiązaniem ze stanu . ${\ Displaystyle V}$ ${\displaystyle \pi}$${\displaystyle \pi}$${\ Displaystyle V (s)}$${\displaystyle s}$

Algorytm składa się z dwóch etapów, (1) aktualizacji wartości i (2) aktualizacji polityki, 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 wartości polityki i stanu przy użyciu starszego oszacowania tych wartości.

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

${\ Displaystyle \ pi (s): = \ operatorname {argmax} _ {a} \ lewo \ {\ suma _ {s'} P (s' \ średni s, a) \ lewo (R (s' \ średni s) ,a)+\gamma V(s')\prawo)\prawo\}}$

Ich kolejność zależy od wariantu algorytmu; można je również wykonać dla wszystkich stanów naraz lub stan po stanie, a częściej do niektórych stanów niż do innych. Dopóki żaden stan nie zostanie trwale wykluczony z żadnego z kroków, algorytm w końcu 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ą , funkcja nie jest używana; zamiast tego wartość jest obliczana w czasie, gdy jest to potrzebne. Zastąpienie obliczenia w obliczeniu daje połączony krok: ${\displaystyle \pi}$${\ Displaystyle \ pi (s)}$${\ Displaystyle V (s)}$${\ Displaystyle \ pi (s)}$${\ Displaystyle V (s)}$

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

gdzie jest numer iteracji. Iteracja wartości zaczyna się od i jako odgadnięcie funkcji wartości . Następnie wykonuje iteracje, wielokrotnie obliczając dla wszystkich stanów , aż zbiegnie się z lewą stroną równą stronie prawej (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 dostrzeżono to dopiero później. ${\displaystyle i}$${\displaystyle i=0}$${\displaystyle V_{0}}$${\ Displaystyle V_ {i+1}}$${\displaystyle s}$${\ Displaystyle V}$

Iteracja zasad

W iteracji polityki ( Howard 1960 ) krok pierwszy jest wykonywany raz, a następnie krok drugi jest powtarzany aż do zbieżności. Następnie krok pierwszy jest powtarzany raz i tak dalej.

Zamiast powtarzać krok drugi do zbieżności, można go sformułować i rozwiązać jako zestaw równań liniowych. Równania te są uzyskiwane jedynie poprzez wykonanie równania drugiego kroku. Zatem powtórzenie kroku drugiego do zbieżności może być interpretowane jako rozwiązywanie równań liniowych metodą relaksacji (metoda iteracyjna)${\displaystyle s=s'}$

Wariant ten ma tę zaletę, że istnieje określony warunek zatrzymania: gdy tablica nie zmienia się w trakcie stosowania kroku 1 do wszystkich stanów, algorytm jest zakończony. ${\displaystyle \pi}$

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 krok drugi jest powtarzany kilka razy. Następnie krok pierwszy jest powtarzany raz i tak dalej.

Zamiatanie priorytetowe

W tym wariancie kroki są preferencyjnie stosowane do stanów, które są w jakiś sposób ważne – czy oparte na algorytmie (w ostatnim czasie nastąpiły duże zmiany w tych stanach lub wokół nich), czy też na podstawie użycia (te stany są blisko stanu początkowego lub w inny sposób interesujące osoby lub program korzystający z algorytmu). ${\ Displaystyle V}$${\displaystyle \pi}$

Rozszerzenia i uogólnienia

Proces decyzyjny Markowa to gra stochastyczna, w której bierze udział tylko jeden gracz.

Częściowa obserwowalność

Powyższe rozwiązanie zakłada, że wiadomo, kiedy należy podjąć działania; inaczej nie można obliczyć. Gdy to założenie nie jest prawdziwe, problem nazywa się częściowo obserwowalnym procesem decyzyjnym Markowa lub POMDP. ${\displaystyle s}$${\ Displaystyle \ pi (s)}$

Znacznego postępu w tej dziedzinie dokonali Burnetas i Katehakis w „Optymalnej polityce adaptacyjnej dla procesów decyzyjnych Markowa”. W tej pracy, przy założeniu skończonych przestrzeni stan-działanie i nieredukowalności prawa przejścia, skonstruowano klasę polityk adaptacyjnych, które posiadają jednostajnie maksymalne własności współczynnika zbieżności dla całkowitej oczekiwanej nagrody o skończonym horyzoncie. Zasady te określają, że wybór działań, w każdym stanie i okresie czasu, powinien opierać się na wskaźnikach, które są inflacją prawej strony szacowanych równań optymalności średniej nagrody.

Nauka wzmacniania

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

W tym celu warto zdefiniować dalszą funkcję, która odpowiada podjęciu działania, a następnie optymalnemu kontynuowaniu (lub zgodnie z jakąkolwiek aktualnie posiadaną polityką): ${\displaystyle a}$

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

Chociaż ta funkcja jest również nieznana, doświadczenie podczas uczenia się opiera się na parach (wraz z wynikiem ; czyli „byłem w stanie i próbowałem zrobić i stało się”). W ten sposób ma się tablicę i wykorzystuje doświadczenie do jej bezpośredniej aktualizacji. Jest to znane jako Q-learning . ${\displaystyle (s,a)}$${\displaystyle s'}$${\displaystyle s}$${\displaystyle a}$${\displaystyle s'}$${\displaystyle Q}$

Uczenie się ze wzmocnieniem może rozwiązywać procesy Markowa-Decyzji 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 ze wzmacnianiem, zamiast wyraźnego określenia prawdopodobieństw przejścia, prawdopodobieństwa przejścia są dostępne za pośrednictwem symulatora, który jest zazwyczaj wielokrotnie uruchamiany ponownie z jednorodnie losowego stanu początkowego. Uczenie się ze wzmacnianiem można również połączyć z aproksymacją funkcji, aby rozwiązać problemy z bardzo dużą liczbą stanów.

Uczenie się automatów

Innym zastosowaniem procesu MDP w teorii uczenia maszynowego jest uczenie automatów. Jest to również jeden rodzaj uczenia się przez wzmacnianie, jeśli środowisko jest stochastyczne. Pierwszy szczegółowy artykuł o uczących się automatach został omówiony przez Narendra i Thathachara (1974), które pierwotnie zostały opisane jako automaty skończone . Podobnie jak w przypadku uczenia się ze wzmocnieniem, algorytm uczenia automatów ma również tę zaletę, że rozwiązuje problem, gdy prawdopodobieństwo lub nagrody są nieznane. Różnica między uczeniem się automatami a Q-learningiem polega na tym, że pierwsza technika pomija pamięć wartości Q, ale aktualizuje prawdopodobieństwo działania bezpośrednio, aby znaleźć wynik uczenia się. Uczenie się automatów to schemat uczenia się z rygorystycznym dowodem zbieżności.

W uczeniu się teorii automatów 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 akcji, z r ≤ s ,
• wektor prawdopodobieństwa stanu początkowego p (0) = ≪ p ₁ (0), ..., p _s (0) ≫,
• obliczeniowy funkcja który po każdym kroku czasowym T wytwarza p ( t + 1) z p ( t ), przy czym napięcia wejściowego, a stan, oraz
• funkcję G : Φ → α, która generuje wyjście w każdym kroku czasowym.

Stany takiego automatu odpowiadają stanom „ procesu Markowa o parametrach dyskretnych w stanie dyskretnym ”. 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ępnika zgodnie z prawdopodobieństwa P( t + 1) i wyprowadza odpowiednie działanie. Z kolei środowisko automatu odczytuje akcję i wysyła kolejne dane wejściowe do automatu.

Kategoria interpretacja teoretyczna

Poza nagrodami, proces decyzyjny Markowa może być rozumiany w kategoriach teorii kategorii . Mianowicie oznaczmy swobodny monoid ze zbiorem generującym A . Niech Dist oznaczają kategorię Kleisli z monady Giry . Następnie funktor koduje zarówno zbiór S stanów, jak i funkcję prawdopodobieństwa P . ${\ Displaystyle (S, A, P)}$${\ Displaystyle {\ Mathcal {A}}}$${\ Displaystyle {\ mathcal {A}} \ do \ mathbf {Odległość}}$

W ten sposób procesy decyzyjne Markowa można uogólnić z monoidów (kategorii z jednym obiektem) na kategorie arbitralne. Można nazwać wynikiem jest proces decyzyjny Markowa zależne od kontekstu , ponieważ przejście z jednego obiektu do drugiego w zmianach zestaw dostępnych działań i zbiór możliwych stanów. ${\ Displaystyle ({\ mathcal {C}}, F: {\ mathcal {C}} \ do \ mathbf {odleg.})}$${\displaystyle {\mathcal {C}}}$

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 można podejmować w dowolnym momencie, jaki wybierze decydent. 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 o dynamice ciągłej , tj. dynamika systemu jest zdefiniowana przez równania różniczkowe cząstkowe (PDE).

Definicja

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

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

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

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)}$: , funkcja szybkości przejścia;${\displaystyle {\mathcal {X}}\razy {\mathcal {U}}\rightarrow \trójkąt {\mathcal {X}}}$
• ${\displaystyle r(x,u)}$: , funkcja wskaźnika nagrody taka, że , gdzie jest funkcją nagrody omówioną w poprzednim przypadku.${\displaystyle {\mathcal {X}}\razy {\mathcal {U}}\rightarrow \mathbb {R}}$${\displaystyle r(x(t),u(t))\,dt=dR(x(t),u(t))}$${\displaystyle R(x,u)}$

Problem

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

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

gdzie ${\ Displaystyle 0 \ leq \ gamma <1.}$

Formuła programowania liniowego

Jeśli przestrzeń stanów i przestrzeń działań są skończone, moglibyśmy użyć programowania liniowego, aby znaleźć optymalną politykę, co było jednym z najwcześniejszych zastosowanych podejść. Tutaj rozważamy tylko model ergodyczny, co oznacza, że ​​nasz ciągły MDP staje się ergodycznym ciągłym łańcuchem Markowa w ramach polityki stacjonarnej . Zgodnie z tym założeniem, chociaż decydent może podjąć decyzję w dowolnym momencie w obecnym stanie, nie odniósłby większych korzyści, podejmując więcej niż jedno działanie. Lepiej dla nich, aby podejmowali akcję tylko w momencie, gdy system przechodzi ze stanu obecnego do innego. W pewnych warunkach (szczegółowe informacje można znaleźć w Wniosku 3.14 z procesów decyzyjnych Markowa w czasie ciągłym ), jeśli nasza funkcja wartości optymalnej jest niezależna od stanu , będziemy mieli następującą nierówność: ${\ Displaystyle V ^ {*}}$${\displaystyle i}$

${\ Displaystyle g \ geq R (i a) + \ suma _ {j \ w S} q (j \ średni ja a) h (j) \ quad \ forall ja \ w S {\ tekst { i }} a\w A(i)}$

Jeżeli istnieje funkcja , to będzie najmniejsza spełniająca powyższe równanie. Aby znaleźć , moglibyśmy użyć następującego liniowego modelu programowania: ${\ Displaystyle h}$${\ Displaystyle {\ bar {V}} ^ {*}}$${\displaystyle g}$${\ Displaystyle {\ bar {V}} ^ {*}}$

• Podstawowy program liniowy (P-LP)

${\ Displaystyle {\ zacząć {wyrównany} {\ tekst {Minimalizuj}} \ quad & g \ \ {\ tekst {st}} \ quad & g- \ suma _ {j \ w S} q (j \ mid ja, a) h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}$

• Podwójny program liniowy (D-LP)

${\ Displaystyle {\ zacząć {wyrównany} {\ tekst {maksymalizacja}} i \ 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{ i }}\forall i\in S\end{wyrównane}}}$

${\ Displaystyle y (ja, a)}$jest wykonalnym rozwiązaniem problemu D-LP, jeśli nie jest natywne i spełnia ograniczenia w problemie D-LP. Wykonalne rozwiązanie D-LP jest uważane za optymalne rozwiązanie, jeśli: ${\ Displaystyle y (ja, a)}$${\ Displaystyle y ^ {*} (ja, a)}$

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

dla wszystkich możliwych rozwiązań D-LP. Po znalezieniu optymalnego rozwiązania możemy go użyć do ustalenia optymalnych zasad. ${\ Displaystyle y (ja, a)}$${\ Displaystyle y ^ {*} (ja, a)}$

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-Jacobi-Bellmana (HJB) . Aby omówić równanie HJB, musimy przeformułować nasz problem

${\ Displaystyle {\ zacząć {wyrównany} V (x (0), 0) = {} i \ 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ównany}}}$

${\displaystyle D(\cdot)}$jest końcową funkcją nagrody, jest wektorem stanu systemu, jest wektorem kontroli systemu, który próbujemy znaleźć. pokazuje, jak wektor stanu zmienia się w czasie. Równanie Hamiltona-Jacobi-Bellmana wygląda następująco: ${\displaystyle x(t)}$${\ Displaystyle u (t)}$${\displaystyle f(\cdot)}$

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

Moglibyśmy rozwiązać równanie, aby znaleźć optymalną kontrolę , która może dać nam funkcję wartości optymalnej${\ Displaystyle u (t)}$ ${\ Displaystyle V ^ {*}}$

Podanie

Procesy decyzyjne Markowa w czasie ciągłym mają zastosowanie w systemach kolejkowych , procesach epidemicznych i procesach populacyjnych .

Alternatywne notacje

Terminologia i notacja dla MDP nie są do końca 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 współczynnik dyskontowy lub , podczas gdy drugi koncentruje się na problemach minimalizacji z inżynierii i nawigacji, używając terminów kontrola, koszt , koszt docelowy i wywołanie współczynnika rabatu . Ponadto zmienia się zapis prawdopodobieństwa przejścia. ${\ Displaystyle \ beta}$${\ Displaystyle \ gamma}$${\ Displaystyle \ alfa}$

w tym artykule	alternatywny	komentarz
akcja ${\displaystyle a}$	kontrola ${\ Displaystyle u}$
nagroda ${\ Displaystyle R}$	koszt ${\displaystyle g}$	${\displaystyle g}$ jest negatywem ${\ Displaystyle R}$
wartość ${\ Displaystyle V}$	koszt-to-go ${\ Displaystyle J}$	${\ Displaystyle J}$ jest negatywem ${\ Displaystyle V}$
polityka ${\displaystyle \pi}$	polityka ${\ Displaystyle \ mu}$
współczynnik dyskontowania ${\ Displaystyle \ \ Gamma \ }$	współczynnik dyskontowania ${\ Displaystyle \ alfa}$
prawdopodobieństwo przejścia ${\ Displaystyle P_ {a} (s, s')}$	prawdopodobieństwo przejścia ${\displaystyle p_{ss'}(a)}$

Ponadto prawdopodobieństwo przejścia czasami napisane , lub, rzadziej,${\ Displaystyle \ Pr (s, a, s')}$${\ Displaystyle \ Pr (s' \ mid s, a)}$${\displaystyle p_{s}(a).}$

Ograniczone procesy decyzyjne Markowa

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

• Istnieje wiele kosztów poniesionych po zastosowaniu działania zamiast jednego.
• 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 zastosowań CMDP. Jest ostatnio używany w scenariuszach planowania ruchu w robotyce.

Zobacz też

Bibliografia

Dalsza lektura

• Bellman., RE (2003) [1957]. Programowanie dynamiczne (Dover miękka wyd.). Princeton, NJ: Princeton University Press. Numer ISBN 978-0-486-42809-3.
• Bertsekas, D. (1995). Dynamiczne programowanie i optymalna kontrola . 2 . MA: Ateno.
• Derman, C. (1970). Markowskie procesy decyzyjne w stanie skończonym . Prasa akademicka.
• Feinberg, EA; Shwartz, A., wyd. (2002). Podręcznik procesów decyzyjnych Markowa . Boston, MA: Kluwer. Numer ISBN 9781461508052.
• Guo, X.; Hernández-Lerma, O. (2009). Procesy decyzyjne Markowa w czasie ciągłym . Modelowanie stochastyczne i prawdopodobieństwo stosowane. Skoczek. Numer ISBN 978364205464.
• Meyn, SP (2007). Techniki sterowania dla złożonych sieci . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-88441-9. Zarchiwizowane z oryginału w dniu 19 czerwca 2010 r.Dodatek zawiera skrócone "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ę przez wzmacnianie: wprowadzenie . Cambridge, MA: Wydawnictwo MIT.
• Tijms., HC (2003). Pierwszy kurs modeli stochastycznych . Wileya. Numer ISBN 9780470864289.

Zewnętrzne linki

• Uczenie się rozwiązać Procesy decyzyjne Markoviana przez Satinde P. Singh