Aktualności

Dodano: 2020-03-26

Jest to kolejny artykuł z serii o Reinforcement Learning - uczeniu maszynowym ze wzmocnieniem. Zalecamy przeczytanie poprzednich, zaczynając od pierwszego [LINK], by w pełni zrozumieć pojęcia, którymi się posługujemy.

Najpierw dokładnie zaplanuj strategię, a później trzymaj się planu - dewiza, na której bazuje logika Value Iteration oraz Policy Iteration. Agent wykorzystuje strategię na podstawie odpowiedzi środowiska, którego model matematyczny opiera się na procesie decyzyjnym Markova (ang. “Markov decision process“, MDP).

Rysunek 1: Proces decyzyjny Markova. [1]

MDP określamy jako zbiór elementów:
* S - zbiór wszystkich stanów,
* A - zbiór wszystkich akcji,
* P_a(s, s') - prawdopodobieństwo przejścia ze stanu s do stanu s' po podjęciu akcji a,
* R_a(s, s') - nagroda po przejściu ze stanu s do stanu s' po podjęciu akcji a.

Odpowiedź środowiska, czyli nagroda i następny stan, jest generowana z zachowaniem własności Markova, co oznacza, że nie zależy ona od poprzednich doświadczeń agenta w środowisku - sposób dotarcia do określonego stanu nie ma wpływu na wybór kolejnego stanu.

Agent nie ma wiedzy na temat środowiska, które jest od niego niezależne. Jedyne, co posiada, to odpowiedź środowiska na jego akcję. Na jej podstawie agent liczy wartość poprzedniego stanu i zapisuje sobie w pamięci, by w konsekwencji utworzyć tablicę wartości, którą wykorzystuje do opracowania optymalnej strategii.

Wybór strategii zależy sporo od jej rodzaju. Wyróżnia się tutaj dwie - stochastyczną i deterministyczną.

STOCHASTYCZNA	DETERMINISTYCZNA
każda możliwa w danym stanie akcja ma określone prawdopodobieństwo wykonania	stan determinuje akcję, tzn. tylko jedna z akcji może wykonać się z prawdopodobieństwem 1, reszta nie jest brana pod uwagę

Funkcja wartości stanu określa, jak dobrze być w danym stanie. Tablica z wartościami tej funkcji budowana jest na podstawie wybranej strategii oraz wzoru Bellmana, który korzysta z m.in. wartości następnego stanu. Wymusza to wielokrotną iterację po wszystkich stanach, aby uzyskać jak najlepsze efekty.

Działanie algorytmu Value Iteration będzie więc wyglądać tak, że na początku większość stanów będzie miało przypisaną zerową wartość, a dopiero z czasem tablica wartości funkcji zapełni się, biorąc pod uwagę najwyższą wartość następnego możliwego stanu. Krótko mówiąc, wartości są przypisywane w kolejności “od celu do gracza”.

Strategia w algorytmie Value Iteration jest określana poprzez wybór akcji dającej największy zysk.

Rysunek 2: Value Iteration - krok po kroku, zmiany w tablicy wartości.

Podsumowując, algorytm Value Iteration można opisać słowami w następujący sposób:

Stwórz tablicę wartości stanów i wypełnij ją zerami.
Przypisz delcie wartość zero.
Ustal wartość ograniczającą dla delty, np. 0.001.
Dla każdego stanu:
- zapamiętaj jego starą wartość,
- oblicz nową według optymalnego wzoru Bellmana: max_a⁡ ∑_s' p(s', r | s, a) [r + γV(s')], gdzie: s – stan, s' – następny stan, p – prawdopodobieństwo, a –akcja, r – nagroda dla wykonanej interakcji, γ – czynnik osłabiający,
- jeżeli wartość bezwzględna różnicy między nową wartością a starą jest większa od delty, nadpisz deltę.
Jeżeli delta jest większa od ustalonej wartości, przejdź do kolejnej iteracji, powtarzając krok 4.

Posiadając zaś strategię wyboru największej wartości: stwórz tablicę optymalnych akcji, dla każdego stanu znajdź w tablicy następny stan o największej wartości i zapisz odpowiadającą mu akcję.

Rysunek 3: Przebieg działania dla Policy Iteration do uzyskania optymalnej strategii, gdzie V - funkcja wartości, π - strategia. [2]

Innym podejściem jest aktualizowanie funkcji wartości dla danej strategii i na jej podstawie poprawianie strategii. Na początku strategia jest określana w sposób losowy. Dopiero po wielu oszacowaniach jej efektywności, strategia staje się optymalna, czyli taka, której nie da się już bardziej polepszyć. Ten sposób nauki nazywa się Policy Iteration.

Value i Policy Iteration znajdują swoje zastosowanie w sytuacjach, gdzie ilość kombinacji stanów jest mała, gdyż algorytmy, pomimo swojej dokładności, zajmują dużo pamięci i potrafią wykonywać się długo. Oba algorytmy zostały przez nas sprawdzone na grze Snake oraz Pacman.

W grze Snake przedstawiono na Rysunku 4. efekt wypracowanej strategii poruszania się agenta. Stanem tutaj jest para określająca położenie agenta oraz znajdki. Na danej planszy wygenerowano 625 stanów.

Rysunek 4: Policy Iteration - po lewej agent po nauce, po prawej jego strategia poruszania się:u(up - w górę), d(down - w dół), r (right - w prawo), l(left - w lewo).

Za to w grze Pacman z Rysunku 5. stanem określa się pozycję duszka, monety oraz gracza. Z taką liczbą zmiennych, wygenerowano 3375 możliwych stanów.

Rysunek 5: Pacman wykorzystujący wypracowaną strategię po nauce za pomocą Value i Policy Iteration.

Żródła:
[1] https://lilianweng.github.io/lil-log/2018/02/19/a-long-peek-into-reinforcement-learning.html
[2] Sutton, R., & Barto, A. (2017). Reinforcement learning: An introduction. Cambridge, MIT Press

Autorzy: Izabela Wiatrowska i Adrianna Cieńciała

Value i Policy Iteration - wszystko pod kontrolą!