MDP
Jak działa
W każdym kroku t agent obserwuje stan s_t ∈ S, wybiera akcję a_t ∈ A zgodnie z polityką π(a|s), środowisko przechodzi do stanu s_{t+1} ~ P(·|s_t, a_t) i zwraca nagrodę r_t = R(s_t, a_t). Cel: znaleźć politykę π* maksymalizującą funkcję wartości V^π(s) = E[Σ γ^t · r_t | s_0=s, π]. Optymalna funkcja wartości spełnia równanie Bellmana: V*(s) = max_a [R(s,a) + γ Σ_{s'} P(s'|s,a) V*(s')]. MDP jest rozwiązywany metodami: Value Iteration (iteracyjne zastosowanie operatora Bellmana), Policy Iteration (naprzemiennie ocena polityki i jej poprawa), oraz programowaniem liniowym. Gdy P i R są nieznane (model-free), używa się algorytmów RL (Q-learning, SARSA, policy gradients) operujących na próbkach trajektorii. Własność Markowa gwarantuje, że optymalna polityka jest stacjonarna i deterministyczna (dla MDP z dyskretnym S i A).
Rozwiązany problem
Jak matematycznie sformalizować problem podejmowania decyzji przez agenta w stochastycznym środowisku — tak, aby możliwe było udowodnienie istnienia optymalnej polityki i konstruowanie algorytmów ją znajdujących.
Komponenty
Zbiór wszystkich możliwych stanów środowiska. Może być dyskretny (skończony lub przeliczalny) lub ciągły (np. R^n).
Zbiór akcji dostępnych dla agenta. Może być dyskretna (np. {lewo, prawo, góra, dół}) lub ciągła (np. moment obrotowy w robotyce).
P(s'|s,a) — prawdopodobieństwo przejścia do stanu s' po wykonaniu akcji a w stanie s. Definiuje stochastyczną dynamikę środowiska.
R(s,a) lub R(s,a,s') — skalarna nagroda zwracana przez środowisko. Definiuje cel agenta — wszystko, co MDP optymalizuje, jest sumą zdyskontowanych nagród.
γ ∈ [0,1]. Waga przyszłych nagród względem bieżących. γ < 1 gwarantuje zbieżność szeregu nagród dla horyzontu nieskończonego.
Oficjalna
π(a|s) — funkcja mapująca stan na rozkład prawdopodobieństwa akcji. Rozwiązaniem MDP jest polityka optymalna π*.
Oficjalna
Implementacja
Jeśli stan nie zawiera pełnej informacji potrzebnej do predykcji przyszłości, problem nie jest poprawnym MDP — algorytmy mogą nie zbiegać do optymalnej polityki.
Wykładniczy wzrost rozmiaru przestrzeni stanów przy wzroście wymiarowości czyni egzakcjne rozwiązania niewykonalnymi.
W rzeczywistych zadaniach agent rzadko obserwuje pełny stan — naiwne stosowanie MDP zamiast POMDP prowadzi do suboptymalnej polityki.
Standardowe MDP zakłada stacjonarność P i R. Gdy środowisko się zmienia, optymalna polityka też się zmienia — wymaga rozszerzeń (non-stationary MDP, contextual MDP).
Ewolucja
Andriej Markow definiuje stochastyczne procesy z własnością memoryless — matematyczny prekursor MDP.
Richard Bellman wprowadza programowanie dynamiczne i zasadę optymalności — fundament metod rozwiązywania MDP.
Pierwsza formalna definicja MDP — krotka (S, A, P, R) z funkcją wartości i równaniem Bellmana.
Ronald Howard publikuje "Dynamic Programming and Markov Processes" — wprowadza Policy Iteration jako alternatywę dla Value Iteration.
Åström rozszerza MDP o przypadek, gdy agent nie widzi pełnego stanu — fundament dla problemów z niepełną informacją.
Chris Watkins udowadnia zbieżność Q-learning do optymalnej polityki w MDP bez znajomości P i R — model-free RL.
Pierwsza systematyczna analiza MDP z aproksymacją funkcji wartości — przygotowanie gruntu pod Deep RL.
Kanoniczne podsumowanie pola — MDP staje się powszechnie używanym formalizmem w RL.
Hiperparametry (konfigurowalne osie)
Liczba (lub wymiarowość) stanów. Krytycznie wpływa na wykonalność algorytmów dokładnych — value iteration ma złożoność O(|S|² · |A|) na iterację.
Liczba akcji w stanie (lub wymiarowość ciągłej przestrzeni akcji).
γ ∈ [0,1]. Definiuje horyzont planowania. Zbliżone do 1 → długi horyzont, wolniejsza zbieżność algorytmów.
Liczba kroków decyzyjnych — skończony lub nieskończony. Wpływa na wybór algorytmu (finite-horizon DP vs. infinite-horizon iteracje).
Złożoność obliczeniowa
Złożoność czasowa: O(|S|² · |A|) per iteracja (Value Iteration). Złożoność przestrzenna: O(|S|² · |A|).
Wąskie gardło obliczeniowe
Rozmiar tablicy stanów rośnie wykładniczo z liczbą wymiarów stanu — egzakcjne rozwiązanie staje się niewykonalne dla |S| > ~10⁶. Stąd potrzeba aproksymacji funkcji (Deep RL) lub abstrakcji.
Paradygmat wykonania
MDP to formalny model, nie architektura obliczeniowa — sposób wykonania zależy od wybranego algorytmu (Value Iteration, Policy Iteration, RL).
Równoległość
Aktualizacje value iteration są niezależne per stan — można paralelizować obliczenia max_a Q(s,a) dla różnych s. Asynchroniczny DP (Sutton) dopuszcza nierównoległą aktualizację stanów.
Wymagania sprzętowe
MDP to formalny model matematyczny — nie ma preferencji sprzętowych jako takich. Implementacja konkretnych algorytmów (VI, PI, Q-learning, Deep RL) ma swoje preferencje sprzętowe.