Czym jest Proces decyzyjny Markowa (Markov decision process)?
Proces decyzyjny Markowa, często skracany do MDP, opisuje formalny schemat podejmowania decyzji w sytuacjach, w których wynik zależy zarówno od losowości, jak i od wyborów podejmowanych przez agenta. Model składa się z rozłącznych stanów środowiska, zestawu możliwych akcji, prawdopodobieństw przejść między stanami oraz funkcji nagrody. Całość opiera się na założeniu właściwości Markowa, zgodnie z którą pełną informacją o przyszłości jest obecny stan, a przeszłość nie wprowadza dodatkowych zależności poza zawartymi już w stanie bieżącym.
Jak dokładnie działa Proces decyzyjny Markowa (Markov decision process)
MDP można rozumieć jako cztero-elementową krotkę (S, A, P, R), gdzie S to zbiór stanów, A zbiór akcji, P funkcja przejścia określająca prawdopodobieństwa P(s’ | s, a), a R funkcja nagrody przypisująca wartość liczbową każdemu przejściu. Agent obserwuje stan, wybiera akcję, przechodzi do nowego stanu zgodnie z losowym mechanizmem P i otrzymuje nagrodę wyznaczoną przez R. Celem jest znalezienie polityki decyzyjnej maksymalizującej sumę zdyskontowanych nagród w długim horyzoncie. W praktyce stosuje się metody dynamicznego programowania, takie jak iteracja wartości lub polityk, a także algorytmy uczenia ze wzmocnieniem, wśród których Q-learning i SARSA przejmują strukturę MDP, ucząc się funkcji wartości na podstawie prób z interakcji.
Geneza i rozwój
Pojęcie procesu decyzyjnego Markowa zostało sformalizowane w latach 50. XX w. przez Ronalda A. Howarda z Uniwersytetu Stanforda, który w 1960 roku opublikował fundamentalną monografię „Dynamic Programming and Markov Processes”. Koncepcja bazuje na wcześniejszych pracach Andrieja Marka dotyczących łańcuchów Markowa oraz na teorii programowania dynamicznego rozwijanej przez Richarda Bellmana. Od tamtej pory MDP stał się podstawowym narzędziem opisu problemów sekwencyjnego podejmowania decyzji w informatyce, ekonomii i robotyce.
Zastosowania w praktyce
MDP znajduje zastosowanie przy tworzeniu autonomicznych systemów planowania tras w logistyce, w zarządzaniu portfelem inwestycyjnym, w optymalizacji zarządzania energią w inteligentnych sieciach oraz w sterowaniu robotami mobilnymi. Przykładowo, w magazynie zrobotyzowanym decyzje dotyczące wyboru kolejnego zadania przez robota – czy podnieść towar, naładować baterię, czy ominąć przeszkodę – można modelować jako MDP, gdzie stany opisują lokalizację i poziom energii, a funkcja nagrody premiuje szybkie kompletowanie zamówień przy minimalnym zużyciu energii.
Zalety i ograniczenia
Ścisła matematyczna definicja MDP pozwala na precyzyjne dowodzenie własności algorytmów i analizę zbieżności metod optymalizacji, dzięki czemu otrzymujemy powtarzalne rezultaty. Model ujednolica także opis różnych problemów decyzyjnych, co sprzyja przenoszeniu technik między dziedzinami. Ograniczeniem jest natomiast rosnąca złożoność obliczeniowa przy dużych przestrzeniach stanów i akcji, co wymusza stosowanie aproksymacji funkcji wartości lub uczenia głębokiego. Dodatkowo, założenie pełnej obserwowalności stanu bywa zbyt silne w realnych scenariuszach, gdzie konieczne jest rozszerzenie modelu do częściowo obserwowalnych procesów decyzyjnych (POMDP).
Na co uważać?
W praktyce największym wyzwaniem jest właściwe zdefiniowanie funkcji nagrody. Niewłaściwie zaprojektowana nagroda może prowadzić do niepożądanego zachowania agenta, na przykład do wykorzystania luk w środowisku zamiast realizacji zamierzonego celu. Drugą kwestią jest wybór parametru dyskontującego, który ustala, jak bardzo agent ceni nagrody odroczone – zbyt niska wartość może powodować myślenie krótkoterminowe, zbyt wysoka utrudnia konwergencję.
Dodatkowe źródła
Rozbudowane omówienie definicji i algorytmów znajduje się w artykule Wikipedia – Markov decision process.
Analizę złożoności MDP w dużych przestrzeniach stanów przedstawia praca „Playing Atari with Deep Reinforcement Learning” dostępna w serwisie arXiv.org.
Szczegóły historyczne i klasyczne algorytmy dynamicznego programowania można znaleźć w książce R. Suttona i A. Barto „Reinforcement Learning: An Introduction”.
