Czym jest Częściowo obserwowalny proces decyzyjny Markowa (partially observable Markov decision process, POMDP)?
Pojęcie POMDP opisuje matematyczny model podejmowania decyzji sekwencyjnych w warunkach niepewności co do pełnego stanu otoczenia. Podobnie jak klasyczny proces decyzyjny Markowa (MDP) zakłada, że środowisko ewoluuje zgodnie z własnościami Markowa, jednak istotnym wyróżnikiem jest ograniczony dostęp do stanu – agent widzi jedynie przybliżone obserwacje powiązane ze stanem, a nie sam stan. Z tego powodu zamiast pojedynczego opisu sytuacji uwzględnia się rozkład przekonań (belief state), czyli wektor prawdopodobieństw dotyczący tego, gdzie agent może się znajdować w przestrzeni stanów. Formalnie POMDP definiuje się pięcioma składowymi: zbiorem stanów, zbiorem akcji, modelem przejść, modelem obserwacji i funkcją nagrody, a celem jest maksymalizacja oczekiwanej skumulowanej nagrody poprzez optymalną politykę zdefiniowaną na przestrzeni przekonań.
Jak dokładnie działa Częściowo obserwowalny proces decyzyjny Markowa (POMDP)
Działanie rozpoczyna się od inicjalnego rozkładu przekonań, najczęściej jednolicie rozproszonego, gdy wiedza agenta jest zerowa. Po wykonaniu akcji środowisko przechodzi do nowego stanu zgodnie z modelem przejść, jednak agent zamiast jawnego stanu otrzymuje obserwację generowaną losowo z modelu obserwacji. W odpowiedzi aktualizuje rozkład przekonań za pomocą reguły Bayesa, integrując wcześniejsze przekonania, wybraną akcję oraz nową obserwację. Kolejna decyzja podejmowana jest już w zaktualizowanej przestrzeni przekonań. Proces powtarza się, tworząc zamkniętą pętlę percepcji, aktualizacji i działania. W praktycznych implementacjach rozkład przekonań bywa aproksymowany, na przykład przy pomocy filtrów cząsteczkowych, sieci neuronowych lub metod Monte Carlo, ponieważ dokładne przeliczenie bywa zbyt kosztowne obliczeniowo.
Porównanie z klasycznym MDP
W klasycznym procesie decyzyjnym Markowa agent zna pełen stan, dzięki czemu decyzja zależy wyłącznie od bieżącej sytuacji. W POMDP obserwacje są niepełne lub zaszumione, stąd jedynym wystarczającym opisem jest rozkład przekonań. Problem optymalizacji komplikuje się tym samym z ustalonego, ewentualnie dużego, zbioru stanów do ciągłej przestrzeni rozkładów prawdopodobieństwa. Z tego powodu wiele algorytmów MDP nie może zostać bezpośrednio przeniesionych, a rozwiązania POMDP częściej wykorzystują programowanie dynamiczne w przestrzeni przekonań, przycinanie drzew decyzyjnych lub uczenie głębokie.
Kontekst historyczny
Za wczesne sformułowanie koncepcji częściowej obserwowalności uznaje się prace K.J. Åströma z 1965 roku, który analizował sterowanie systemami dynamicznymi z ograniczoną informacją sensoryczną. W latach 90. Kathryn B. Littman, Leslie Kaelbling i Michael Cassandra z Massachusetts Institute of Technology przedstawili szeroko cytowaną analizę metod rozwiązujących POMDP, nadając temu formalizmowi popularny kształt wykorzystywany do dziś. Rozwój uczenia ze wzmocnieniem oraz metod przybliżonych po 2010 roku, zwłaszcza technik głębokich sieci neuronowych trenowanych end-to-end, otworzył drogę do rozwiązywania POMDP o skali wcześniej nieosiągalnej.
Zastosowania w praktyce
POMDP znalazł zastosowanie w licznych zadaniach, w których agent musi postępować mimo niepewności sensorycznej. Autonomiczne pojazdy podejmują decyzje o manewrach na podstawie niedoskonałych danych z lidarów i kamer; asystenci głosowi korygują politykę dialogową po otrzymaniu rozmytych lub źle zrozumianych wypowiedzi użytkownika; roboty magazynowe manipulują obiektami, mimo że czujniki wizyjne niekiedy częściowo zasłaniają przedmioty. Model wyjątkowo dobrze sprawdza się także w leczeniu adaptacyjnym, gdzie lekarz-diagnosta jest reprezentowany przez algorytm przewidujący stan pacjenta na podstawie niepełnych pomiarów.
Zalety i ograniczenia
Mocną stroną formalizmu jest zdolność łączenia planowania z wnioskowaniem probabilistycznym, dzięki czemu agent potrafi nie tylko wybierać akcje maksymalizujące nagrodę, lecz również aktywnie redukować niepewność poprzez działanie eksploracyjne. Jednocześnie POMDP zyskuje odporność na błędne lub brakujące dane obserwacyjne. Cena za tę elastyczność przychodzi w postaci znacznie większej złożoności obliczeniowej. Problem określa się jako PSPACE-trudny, a dokładne rozwiązania możliwe są jedynie dla małych przestrzeni stanów. W praktyce korzysta się z aproksymacji, co wymaga ostrożności przy ocenie jakości uzyskiwanych polityk.
Na co uważać?
Projektując model POMDP, warto zwrócić uwagę na poprawne zdefiniowanie modeli przejść i obserwacji, ponieważ błędne założenia wprowadzają systematyczne odchylenia w przekonaniach. Przy aproksymacji filtrów cząsteczkowych należy kontrolować zjawisko degeneracji próbek, a w uczeniu głębokim – unikać nadmiernego dopasowania do symulowanego środowiska. Wreszcie, interpretacja polityk powstających w przestrzeni przekonań bywa trudniejsza niż w klasycznych MDP, co utrudnia audyt i certyfikację algorytmów w zastosowaniach krytycznych.
Dodatkowe źródła
Osoby zainteresowane szczegółami matematycznymi mogą sięgnąć do przekrojowego opracowania Kaelbling, Littman i Cassandry „Planning and Acting in Partially Observable Stochastic Domains”, dostępnego na stronie ACM. Wprowadzenie w języku polskim znajduje się na Wikipedii, a szczegółową definicję POMDP można znaleźć pod angielskim hasłem Partially Observable Markov Decision Process. Najnowsze techniki uczenia głębokiego opisuje artykuł „Deep Recurrent Models of POMDPs” na arXiv oraz przegląd „Learning POMDP Models” opublikowany pod adresem arXiv:1703.10471.
