Aktualności

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.

Przed przystąpieniem do faktycznego omówienia algorytmów Q-Learning i SARSA istotne jest krótkie wprowadzenie na temat spotykanych metod uczenia oraz strategii, z której korzystają oba wymienione wcześniej algorytmy.

Istnieją trzy główne metody uczenia, wykorzystywane w Reinforcement Learning. Metoda programowania dynamicznego (ang. dynamic programming, DP), wykorzystywana przy algorytmie Value Iteration, metoda Monte Carlo oraz metoda różnic tymczasowych (ang. temporal difference, TD), która jest połączeniem dwóch poprzednich.

Dwie pierwsze metody są wykorzystywane jedynie w przypadku zadań epizodycznych (posiadających stan końcowy; np. gra Snake). Metoda różnic czasowych jest za to możliwa do implementacji dodatkowo w przypadku zadań ciągłych (bez stanu końcowego; np. przewidywanie sytuacji na giełdzie).

Algorytmy Q-Learning i SARSA do obliczenia wartości stanów korzystają z metody różnic tymczasowych, nie znając kompletnie prawdopodobieństw przejść. Czyni to z nich algorytmy model-free. Jest to przewaga nad Value Iteration, który jest algorytmem model-based - polegającym na modelu matematycznym z owymi prawdopodobieństwami. Sprawia to, iż algorytmy model-free są określane jako algorytmy bazujące na metodzie prób i błędów.

Warta wspomnienia jest jeszcze strategia ε-greedy. Bazuje ona na zbilansowaniu eksploatacji środowiska i jego eksploracji. Przy wyborze akcji, agent z prawdopodobieństwem 1 - ε będzie wybierał ją w sposób zachłanny (ang. greedy), czyli na podstawie maksymalnej wartości (eksploatacja). W przypadku kilku akcji o maksymalnej wartości, wybierana jest losowa z nich. Z prawdopodobieństwem ε zaś, agent wybiera losową z możliwych w danym stanie akcję (eksploracja).

Q-Learning to algorytm polegający na wyborze akcji wedle strategii ε-greedy i obliczenia wartości stanu na podstawie odpowiedzi środowiska. Wartość Q(s, a) przedstawia wartość nagrody, jaką spodziewamy się dostać po podjęciu akcji a w stanie s. Q wzięło się od Quality (z ang. jakość), co pomaga w zrozumieniu wzoru 1, wedle którego aktualizowana jest owa wartość.

Max_a oznacza, iż sprawdzamy wartości, jakie dadzą nam możliwe akcje w następnym stanie, i pod uwagę bierzemy tę najwyższą. Algorytm w ten sposób zakłada, że agent zawsze wybierze najbardziej “opłacalną jakościowo” akcję - rodzaj takich algorytmów nazywa się off-policy.

Podobnym algorytmem do Q-Learningu jest algorytm SARSA. Jego nazwa jest akronimem od wartości, które przyjmuje i zwraca: s, a, r, s’, a’. Łatwo zauważyć, że wykorzystuje on nie tylko obecny stan, wykonywaną akcję oraz zwrócone przez środowisko nagrodę i następny stan, ale również akcję następną, którą agent wykonuje w późniejszym kroku czasowym. Tutaj tkwi różnica w stosunku do algorytmu Q-Learning - SARSA jest algorytmem on-policy.

W obu algorytmach możliwe jest, by, zamiast na początku tworzyć tablicę wartości dla każdego stanu z każdą możliwą akcją, dodawać napotkane stany i interakcje na bieżąco, przy pierwszym zetknięciu się z nimi.

Jak wspomniano na początku artykułu, dzięki zastosowaniu metody różnic tymczasowych, powyższe algorytmy są możliwe do wykorzystania zarówno w zadaniach epizodycznych, jak i w zadaniach ciągłych. Wtedy zamiast powtarzać pętlę z kroku 3 do momentu wykonania zadania przez ustaloną wcześniej liczbę epizodów, możemy wykonywać ją w nieskończoność. Trzeba sobie jednak zdawać sprawę, że wielkość tablicy wartości bardzo szybko się powiększa. Lepsze zastosowanie znajdą więc nie w środowiskach ciągłych, a epizodycznych, z niezbyt wielką liczbą możliwych stanów.

Poniżej przedstawiamy oba algorytmy zaimplementowane przez nas w grach Snake oraz Pacman.