Zadanie dotyczy rozwiązywania zagadnień typu dyskretnych problemów decyzyjnych Markowa (MDP), podobnych do omawianych na wykładzie. Zadanie składa się z dwóch części i należy napisać dwa programy rozwiązujące poszczególne części zadania. W pierwszej części należy rozwiązać bezpośrednio problem MDP o znanych parametrach metodą iteracji wartości albo iteracji polityki. W drugiej części należy rozwiązać problem MDP o nieznanych parametrach metodą Q-learning.
Agent porusza się w płaskim prostokątnym świecie o rozmiarze NxM ruchami poziomymi i pionowymi, po jednym polu, otrzymując nagrodę właściwą dla pola na które wszedł. W świecie występują pola zwane stanami: pojedynczy stan startowy (S), stany terminalne (T), stany zabronione (F), oraz stany specjalne (B). Działalność agenta rozpoczyna się w stanie startowym (S) i kończy wejściem do stanu terminalnego (T). Wyjście poza granice świata jest niemożliwe, podobnie jak wejście do stanu zabronionego (F). Wszystkie stany nieoznaczone są zwykłymi stanami, z domyślną wartością nagrody. Nagrody otrzymywane w stanach specjalnych (B) i terminalnych (T) są indywidualnie zdefiniowane dla każdego z tych stanów.
Uwaga: stany specjalne nie są terminalne. Stany specjalne są jak zwykłe stany nieterminalne, tylko mają indywidualne wartości nagrody.
Przykładowe światy MDP:
| T | |||
| F | T | ||
| S |
albo
| B | |||
| S | F | F | T |
| B |
albo
| T | B | T | ||
| F | F | |||
| B | S | B | ||
| F | F | |||
| T | B | T |
itp.
Szczegółowe zasady:
Agent może wykonywać ruchy: (L)eft, R(ight), (U)p, i D(own). Wykonanie ruchu w danym kierunku z prawdopodobieństwem p1 kończy się w zamierzonym miejscu, z prawdopodobieństwem p2 kończy się na lewo od punktu startu, z prawdopodobieństwem p3 kończy się na prawo od punktu startu, a z prawdopodobieństwem (1-p1-p2-p3) kończy się w miejscu przeciwnym do zamierzonego kierunku ruchu (w przykładach omawianych na wykładzie było p1=0.8 i p2,p3=0.1).
W przypadku gdy agent znajduje się przy ścianie i efekt danego ruchu wyprowadziłby go poza granice świata, albo do stanu zabronionego, w efekcie ruchu agent pozostaje w miejscu (i otrzymuje właściwą dla niego nagrodę). Można powiedzieć, że agent ,,odbija się'' od ścian i stanów zabronionych.
Każdy ruch powoduje otrzymanie nagrody przez agenta (którą, jeśli jest ujemna, można też interpretować jako koszt ruchu). Wartość otrzymanej nagrody zależy od stanu, do którego agent przeszedł. Dla zwykłych stanów obowiązuje domyślna wartość nagrody r. Natomiast dla każdego stanu terminalnego i specjalnego wartości nagrody są określone indywidualnie.
Wynikiem działania agenta jest suma nagród uzyskanych we wszystkich krokach, obliczona z uwzględnieniem współczynnika dyskontowania γ.
Parametrami zadania są zatem: N,M,p1,p2,p3,r,γ, oraz indywidualne wartości nagrody dla poszczególnych stanów terminalnych i specjalnych. Dodatkowo, w drugiej części zadania występuje parametr eksploracji ε.
Napisz program rozwiązujący DOWOLNE dyskretne problemy MDP opisanego typu, metodą iteracji wartości lub iteracji polityki. Program powinien wyświetlić na wyjściu obliczoną politykę agenta oraz rozkład funkcji użyteczności w formacie zgodnym z geometrią świata MDP.
Przez rejestrowanie przez program wyników częściowych, zaimplementuj analizę zbieżności algorytmu tworząc wykres wartości użyteczności stanów programem Gnuplot. Załącz zarówno wynikowy wykres, jak i opracowany komplet poleceń Gnuplota, oraz pliki danych, pozwalające wygenerować ten wykres dla każdej instancji problemu.
Oblicz rozwiązanie zagadnienia 4x3 omawianego na wykładzie, Rys.1,
γ=1.0. W raporcie podaj: komplet otrzymanych użyteczności stanów z
dokładnością do czwartego miejsca po przecinku, politykę, wykres zbieżności,
oraz liczbę wykonanych iteracji algorytmu. Użyteczności i politykę
przedstaw w tabelce zgodnej z układem świata. Politykę zapisz znakami:
> < ^ v. Jako kryterium stopu algorytmu możesz przyjąć zejście
wszystkich różnic wartości między kolejnymi iteracjami poniżej 0.0001.
Porównaj wyniki ze znanymi z literatury i wykładu. Jeśli Twoje wyniki
różnią się, to znaczy że masz niepoprawną implementację algorytmu!
Rys.1: +---+---+---+---+ | | | | T | +---+---+---+---+ | | F | | T | +---+---+---+---+ | S | | | | +---+---+---+---+
Znajdź rozwiązanie zagadnienia pokazanego na Rys.2 (N=4, M=4), przyjmując model niepewności ruchów dokładnie taki sam jak w przykładach omawianych na wykładzie (p1=0.8, p2,p3=0.1), i współczynnika dyskontowania γ=0.99. Funkcja nagrody wynosi +100 dla stanu terminalnego, -20 dla stanu specjalnego, i r=-1 dla zwykłych stanów. Podaj politykę optymalną, komplet wartości użyteczności (cztery miejsca po przecinku), i wykres zbieżności. Jako kryterium stopu algorytmu ponownie proszę przyjąć zejście wszystkich różnic wartości między kolejnymi iteracjami poniżej 0.0001.
Rys.2: +---+---+---+---+ | | | | | +---+---+---+---+ | | | | | +---+---+---+---+ | | | B | | +---+---+---+---+ | S | | F | T | +---+---+---+---+
Zmień funkcję nagrody dla stanów normalnych, specjalnych, i/lub terminalnych (względem podstawowej wersji zadania 4x4 z Rys.2) w taki sposób, aby skutkowało to zauważalną zmianą polityki optymalnej. Przedstaw komplet rozwiązań dla zmienionego zadania (użyteczności, politykę, wykres). Wyjaśnij uzyskane wyniki.
Zmień model niepewności ruchów (względem podstawowej wersji zadania 4x4 z Rys.2) w taki sposób, aby skutkowało to zmianą polityki optymalnej. Przedstaw komplet rozwiązań dla zmienionego zadania (użyteczności, politykę, wykres). Wyjaśnij uzyskane wyniki.
Zmień współczynnik dyskontowania (względem podstawowej wersji zadania 4x4 z Rys.2) w taki sposób, aby skutkowało to zmianą polityki optymalnej. Przedstaw komplet rozwiązań dla zmienionego zadania (użyteczności, politykę, wykres). Wyjaśnij uzyskane wyniki.
Modyfikacje w ostatnich trzech punktach zadania powinny być na tyle istotne, aby dało się zauważyć ich wpływ na politykę agenta, ale jednocześnie na tyle ograniczone, aby dało się sensownie porównać wersję zmodyfikowaną i oryginalną.
Zaimplementuj obliczanie optymalnej polityki agenta metodą Q-learning z eksploracją. Przyjmij te same podstawowe parametry co w pierwszej części zadania. Jednak model ruchów i wartości nagrody są tu nieznane agentowi, zostaną tylko użyte dla wygenerowania przebiegów uczących. Zatem program musi składać się z dwóch części: agenta, który generuje akcje i uczy się funkcji Q z przebiegów uczących, oraz symulatora, który te przebiegi uczące generuje począwszy od zadanego stanu startowego, przez generowanie losowych reakcji na akcje agenta.
Agent powinien generować akcje łączące eksploatację z eksploracją w następujący sposób, sterowany parametrem eksploracji ε. Najlepszy ruch dla danego stanu (eksploatacja) powinien być wybierany z prawdopodobieństwem 1-ε, a z prawdopodobieństwem ε powinien być wykonywany ruch wybrany losowo (eksploracja).
Rozwiąż instancję problemu dla świata z Rysunku 2 z ustawieniami: p1=0.8, p2,p3=0.1, γ=0.99 i współczynnikiem uczenia α=1/N(s,a) gdzie N(s,a) jest liczbą razy jaką akcja a została wybrana w stanie s w dotychczasowych przebiegach. Uwzględnij dwie strategie eksploracji, z ε=0.05 i ε=0.2.
W tej części zadania trudno będzie osiągnąć dokładność podobną jak w części pierwszej. Orientacyjnie pożądane byłoby osiągnięcie dokładności jednej cyfry dziesiętnej. Przeprowadź eksperymenty dla ustalenia ile przebiegów jest potrzebnych dla osiągnięcia takiego wyniku. Zacznij od 10,000 przebiegów. zawsze startując ze stanu startowego S aż do osiągnięcia stanu terminalnego. Oszacuj z jaką dokładnością obliczone zostały wartości funkcji Q, w szczególności ile przebiegów uczących było potrzebne dla osiągnięcia tej dokładności dla różnych wartości ε.
W raporcie przedstaw w postaci tabeli odpowiadającej geometrii świata: znalezioną politykę optymalną, użyteczności stanów oraz wartości Q (jedną cyfrę dziesiętną), z podaniem liczby wygenerowanych przebiegów uczących.
Opracowane programy powinny wyznaczać optymalną politykę, oraz rozkład funkcji użyteczności U (pierwsza część zadania), albo rozkład funkcji wartości akcji Q (druga część zadania). Programy mogą wykorzystywać dowolne ogólnie dostępne dla danego języka biblioteki i funkcje.
Każdy program powinien rozwiązać podane zadanie, wyniki częściowe (do tworzenia wykresów zbieżności) zapisać w pliku/ach na dysku, natomiast końcowe wyniki w postaci rozkładu polityki, użyteczności U lub wartości akcji Q, powinien wyświetlić w postaci tabeli zgodnej z geometrią świata. Pierwszy parametr rozmiaru świata traktujemy jako rozmiar poziomy, a drugi jako pionowy, z początkiem układu w lewym dolnym rogu.
Wszystkie wyniki należy wyswietlic w postaci tekstowej na wyjściu stdout.
Proszę używać czystego kodu ASCII (7-bitowego), bez znaków polskich, ani
żadnych znaków graficznych. Politykę proszę wyświetlić za pomocą znaków:
<,>,v,
Parametry zagadnienia MDP program powinien wczytać z zadanego pliku o formacie opisanym poniżej. Plik zawiera parametry N,M,p1,p2,p3,r, które są parametrami zagadnienia MDP, oraz może opcjonalnie zawierać parametry γ i ε, które są parametrami agenta wpływającymi na kształt i sposób wyznaczenia rozwiązania.
Parametry γ i ε program powinien przyjmować również jako argumenty wywołania zadane w wierszu wywołania w sposób pozycyjny (pierwszy γ i drugi ε). Argumenty wywołania są opcjonalne, i jeśli nie zostały podane, to obowiązują parametry wczytane z pliku zadania. Brak kompletu parametrów, lub ich nieprawidłowe wartości powinny spowodować zatrzymanie programu z odpowiednim komunikatem.
Dopuszczalne sposoby dostępu do pliku danych zadania: (0) otwarcie pliku tylko
do jednorazowego odczytu sekwencyjnego, (1) nazwa pliku może być zadana
argumentem wywołania w wierszu poleceń (w tym przypadku powinien to być
pierwszy argument pozycyjny, a po nim opcjonalnie parametry γ i
ε), albo (2) nazwa pliku może być ustalona na stałe i wbudowana w
program, albo (3) nazwa pliku może być zadana zmienną środowiskową (to jest
dobra opcja dla systemów rodziny Unix, ale nie wiem czy istnieje na Windows).
Niedopuszczalne jest aby program pytał interakcyjnie o nazwę pliku, ogólnie
wymagał jakiejkolwiek interakcji z użytkownikiem, albo w ogóle czytał
cokolwiek z wejścia stdin.
Program należy napisać w zadanym języku programowania w sposób niezależny od systemu operacyjnego i okienkowego: Windows, Linux, X11, Android, itp., również przy kompletnym braku systemu okienkowego.
Plik danych zawierający opis instancji świata i parametrów eksperymentu jest plikiem tekstowym składającym się z szeregu wierszy. Każdy wiersz zawiera na początku etykietę (napis tekstowy), i po niej jeden do trzech parametrów liczbowych. Dopuszczalne są następujące etykiety:
Stan startowy jest opcjonalny. Algorytm iteracji wartości nie używa go. W części II zadania (Q-learning), gdy nie został zadany stan startowy, należy losowo wybrać jeden ze stanów nieterminalnych jako początek każdego przebiegu.
Parametry γ i ε są opcjonalne, ponieważ mogą być również zadane jako argumenty wywołania programu.
Współrzędne stanów liczone są od 1 i początkiem układu współrzędnych jest lewy dolny narożnik wyświetlanej reprezentacji świata.
Dopuszczalna jest dowolna kolejność wierszy pliku, pod warunkiem wystąpienia dokładnie po jednym z wierszy obowiązkowych, i co najwyżej po jednym z wierszy opcjonalnych. Musi również wystąpić co najmniej jeden stan terminalny.
Ponadto parametry świata MDP muszą spełniać następujące warunki:
p1,p2,p3 >= 0.0 <= 1.0 p1+p2+p3 <= 1.0 ε > 0.0 <= 1.0 γ >= 0.0 <= 1.0 wszystkie jawnie zdefiniowane stany (S,T,B,F) muszą leżeć w określonych rozmiarach świata
Przykładowa treść pliku danych opisująca instancję problemu MDP z wykładu (i podręcznika Russella i Norviga):
W 4 3 S 1 1 P .8 .1 .1 R -0.04 G 1.00 T 4 3 1. T 4 2 -1. F 2 2
Należy opracować zwięzły raport opisujący wyniki uzyskane w poszczególnych częściach zadania, z niezbędnymi wyjaśnieniami, interpretacjami, oraz wnioskami.
Raport powinien być zwięzły. Nie wklejaj tekstu zadania ani jego interpretacji, ani żadnych teorii i formuł dostępnych w opublikowanej literaturze (zamiast tego cytuj źródła).
Prezentując wyniki należy stosować wszelkie rozsądne skróty, zaokrąglać wartości liczbowe do wymaganej i prawidłowej wielkości oraz podsumowywać. Nie prezentuj wielu wyników bez komentarzy i dyskusji.
Unikaj prezentowania wyników w postaci zrzutów ekranu (chyba, że przedstawiasz wygląd interfejsu programu, a nie wyniki). Wyniki tabelaryczne powinny być wyświetlane jako tekst, a nie obrazy. Jeśli dołączasz obrazy, upewnij się, że są czytelne. Na przykład biały tekst na jasnożółtym tle jest zwykle bardzo nieczytelny. Podobnie jak tekst wyświetlany bardzo małą czcionką na dużym tle.
W raporcie należy obowiązkowo wymienić wszystkie wykorzystane zasoby, zarówno literaturę, jak i konkretne moduły programu: biblioteki programowe inne niż domyślne oraz wszelkie wykorzystane gotowe programy lub fragmenty programów, wraz z ich źródłami.
Dodatkowo, należy stworzyć pakiet uruchomieniowy zawierający wszystkie niezbędne pliki źródłowe, utworzone zbiory danych, niezbędne do uruchomienia programów (jednak proszę nie przesyłać plików danych dostarczonych do zadania). Sposób kompilacji i uruchamiania programu powinien być jasno i precyzyjnie opisany w pliku README zawartym w pakiecie.
Pakiet powinien umożliwiać testowe uruchamianie opracowanych programów na innych instancjach MDP zgodnych z wymaganiami tego zadania.