Sztuczna inteligencja/SI Moduł 13 - Uczenie się ze wzmocnieniem

Zadanie uczenia się ze wzmocnieniem

Uczenie się ze wzmocnieniem (reinforcement learning, RL) jest pod wieloma względami odmienne od innych form maszynowego uczenia się. W przeciwieństwie do klasyfikacji i regresji, jego celem nie jest aproksymowanie pewnego nieznanego odwzorowania przez generalizację na podstawie zbioru przykładów trenujących, chociaż wewnątrz systemów uczących się ze wzmocnieniem możemy łatwo odkryć wykorzystanie aproksymatorów. Jednak systemowi uczącemu się ze wzmocnieniem nie są dostarczane żadne przykłady trenujące, a jedynie wartościująca informacja trenująca, oceniające jego dotychczasową skuteczność.

Scenariusz

U podstaw uczenia się ze wzmocnieniem leżą dynamiczne interakcje ucznia ze środowiskiem, w którym działa, realizując swoje zadanie. Interakcje te odbywają się dyskretnych (na ogół) krokach czasu i polegają na obserwowaniu przez ucznia kolejnych stanów środowiska oraz wykonywaniu wybranych zgodnie z jego obecną strategią decyzyjną akcji. Po wykonaniu akcji uczeń otrzymuje rzeczywistoliczbowe wartości wzmocnienia lub nagrody, które stanowią pewną miarę oceny jakości jego działania. Wykonanie akcji może również powodować zmianę stanu środowiska.

W każdym kroku czasu Parser nie mógł rozpoznać (błąd składni): {\displaystyle t \} ,:

1. obserwuj aktualny stan Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_t \} ,;
2. wybierz akcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t \} , do wykonania w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_t \} ,;
3. wykonaj akcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t \} ,;
4. obserwuj wzmocnienie Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t \} , i następny stan Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_{t+1} \} ,;
5. ucz się na podstawie doświadczenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle x_t,a_t,r_t,x_{t+1}\rangle \} ,.

Środowisko

Środowisko pod wpływem wykonywanych przez ucznia akcji może zmieniać stany oraz dostarczać nagrody, stanowiące ocenę skuteczności działania ucznia. W uczeniu się ze wzmocnieniem dopuszcza się niepewność środowiska i zakłada się jego nieznajomość przez ucznia. Pierwsze oznacza, że generowane pod wpływem wykonywanych akcji wzmocnienia i zmiany stanów mogą być stochastyczne. Drugie oznacza, że leżące u podstaw tych stochastycznych mechanizmów rozkłady prawdopodobieństwa nie są znane uczniowi. Ponadto środowisko jest niekontrolowalne: uczeń nie ma na te rozkłady prawdopodobieństwa żadnego wpływu. To ostatnie założenie ma decydujące znaczenie na wytyczenie granicy między uczniem a środowiskiem: uczeń ma wpływ na swoje własne mechanizmy działania, parametry itp., lecz nie ma wpływu na środowisko.

Cel działania ucznia

Cel działania ucznia jest pośrednio określony przez wartości wzmocnienia. W najbardziej ogólnym przypadku możemy powiedzieć, że od ucznia oczekuje się nauczenia się strategii (czyli odwzorowania stanów na akcje do wykonania w tych stanach), która maksymalizuje pewne kryterium jakości zdefiniowane za pomocą otrzymywanych przez niego nagród. Rodzaj tego kryterium decyduje o konkretnym typie uczenia się ze wzmocnieniem.

Najciekawszy i najczęściej rozważany jest przypadek, kiedy uczeń ma maksymalizować swoje nagrody długoterminowo: dobra strategia niekoniecznie przynosi natychmiast wysokie nagrody, lecz jest opłacalna w dłuższym horyzoncie czasowym. Ten typ uczenia się ze wzmocnieniem wymaga uwzględnienia przez ucznia opóźnionych skutków wykonywanych przez niego akcji i określany jest mianem uczenia się z opóźnionym wzmocnieniem lub uczenia się na podstawie opóźnionych nagród. Stosowane wówczas algorytmy uczenia się rozwiązują tzw. problem temporalnego przypisania zasługi (temporal credit assignment), polegający na przypisaniu zasługi (bądź winy) za długoterminowe dochody ucznia jego poszczególnym akcjom, być może wykonanym wiele kroków przed faktycznym uzyskaniem tych dochodów.

Jako dokładne kryterium jakości działania ucznia często przyjmuje się oczekiwaną zdyskontowaną sumy otrzymanych nagród. Uczeń rozpoczynający działalność w czasie Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , ma za zadanie maksymalizowanie sumy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{E}\bigg[\sum_{t=0}^{\infty}\gamma^tr_t\bigg], \} ,

(1)

gdzie współczynnik dyskontowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle \gamma\in[0,1] \} , reguluje względną ważność krótko- i długoterminowych nagród.

Zadania epizodyczne

Ważną podklasę zadań uczenia się ze wzmocnieniem stanowią zadania epizodyczne, w których interakcje ucznia ze środowiskiem są podzielone na serię niezależnych epizodów lub prób. Niezależność polega na tym, że akcje wykonane w ramach każdej próby nie mają wpływu na nagrody otrzymywane w innych próbach - maksymalizacja kryterium jakości działania systemu musi następować w każdej próbie niezależnie. W przypadku zdyskontowanej sumy nagród oznacza to zastąpienie nieskończoności w górnej granicy sumowania przez skończoną długość próby. Znaczna część praktycznych zadań ma charakter epizodyczny. Dla wygody i bez zmniejszania ogólności rozważań w dalszej dyskusji teoretycznej ograniczymy się do nieskończonego uczenia się, ale modyfikacja wyników dla przypadku epizodycznego uczenia się jest trywialna.

Dwoma najbardziej typowymi rodzajami zadań epizodycznych są zadania do-sukcesu oraz do-porażki. W pierwszym przypadku uczeń w ramach każdej próby ma do osiągnięcia pewien cel (najczęściej doprowadzenie środowiska do pewnego pożądanego stanu) i próba kończy się, kiedy osiągnie on sukces. Nagrody i współczynnik dyskontowania określa się tak, aby maksymalizacja kryterium jakości prowadziła do osiągnięcia celu w jak najmniejszej liczbie kroków. W najprostszym wariancie uczeń otrzymuje wzmocnienie Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_1 \} , we wszystkich krokach poprzedzających osiągnięcie sukcesu i Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_2\geq r_1 \} , w ostatnim kroku, po jego osiągnięciu. Należy przy tym zapewnić, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{t=0}^{n-1}\gamma^tr_1+\gamma^nr_2 > \sum_{t=0}^{n}\gamma^tr_1+\gamma^{n+1}r_2 \} ,

(2)

dla dowolnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle n>0 \} , (w przeciwnym przypadku nie będzie się opłacało osiągnąć celu jak najszybciej). W drugim przypadku uczeń stara się uniknąć pewnej niepożądanej sytuacji (stanu środowiska) możliwie jak najdłużej. Próba kończy się, kiedy starania te odniosą niepowodzenie. Jeśli przyjmiemy, że uczeń dostaje nagrodę Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_1 \} , we wszystkich krokach pośrednich i Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_2\leq r_1 \} , w kroku końcowym, to aby opłacało mu się odwlekać porażkę, musi być dla dowolnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle n>0 \} , spełniony warunek:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{t=0}^{n-1}\gamma^tr_1+\gamma^nr_2 < \sum_{t=0}^{n}\gamma^tr_1+\gamma^{n+1}r_2. \} ,

(3)

Podanie przykładów wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_1 \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_2 \} ,, i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \gamma \} ,, które odpowiadają zadaniom do-sukcesu i do-porażki pozostawiamy jako proste ćwiczenie.

Procesy decyzyjne Markowa

Modelem matematycznym problemu uczenia się ze wzmocnieniem (a właściwie modelem środowiska) jest proces decyzyjny Markowa (Markov decision process, MDP), który definiujemy jako czwórkę:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \text{MDP} = \langle X,A,\varrho,\delta\rangle, \} ,

(4)

gdzie

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle X \} , jest skończonym zbiorem stanów,
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle A \} , jest skończonym zbiorem akcji,
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho \} , jest funkcją nagrody (wzmocnienia),
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \delta \} , jest funkcją przejścia stanów.

Dla każdej pary Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle x,a\rangle\in X\times A \} , wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho(x,a) \} , jest zmienną losową oznaczającą nagrodę otrzymywaną po wykonaniu akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} ,, a wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \delta(x,a) \} , jest zmienną losową oznaczającą następny stan po wykonaniu akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} ,. Oznacza to, wobec wprowadzonej wcześniej notacji, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t \} , jest realizacją zmiennej losowej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho(x_t,a_t) \} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_{t+1} \} , jest realizacją zmiennej losowej Parser nie mógł rozpoznać (błąd składni): {\displaystyle \delta(x_t,a_t) \} ,.

Dla ułatwienia posługiwania się funkcjami przejścia i wzmocnienia wygodnie jest zdefiniować dodatkowe oznaczenia:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle R(x,a) = \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{E}\big[\varrho(x,a)\big], \} ,	(5)
Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{xy}(a) = \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\delta(x,a)=y\big). \} ,	(6)

Własność Markowa

Kluczowe znaczenie ma tzw. własność Markowa: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \varrho \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \delta \} , nie zależą od historii. W każdym kroku nagroda i następny stan zależą (probabilistycznie) tylko od aktualnego stanu i akcji. Własność ta jest teoretycznie warunkiem stosowalności wszystkich algorytmów, o których będziemy dalej mówić, chociaż w praktyce często można spotkać środowiska niemarkowowskie. Jeśli własność Markowa nie zachodzi, uczeń nie ma dostępu do informacji umożliwiającej wybór najlepszej akcji - mówi się wówczas o ukrytym stanie albo wręcz nazywa obserwacje ucznia sytuacjami, rezerwując termin stan dla prawdziwych (nieznanych) stanów środowiska, które zapewniałyby własność Markowa.

Strategie i funkcje wartości

Dla procesów decyzyjnych Markowa możemy formalnie zdefiniować strategie oraz funkcje wartości, wykorzystywane dalej do określania i obliczania strategii optymalnych.

Strategią dla procesu decyzyjnego Markowa jest dowolna funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi:X\mapsto A \} ,.

Ściślej rzecz biorąc, powyższa definicja określa strategię stacjonarną (nie zmienia się w kolejnych krokach czasu) i deterministyczną (stan determinuje akcję), podczas gdy praktyczne algorytmy uczenia się ze wzmocnieniem wykorzystują z reguły strategie niestacjonarne (podlegają modyfikacjom w trakcie uczenia się) i niedeterministyczne (wybór akcji jest stochastyczny), jednak wygodniej jest przedstawić najważniejsze podstawy teoretyczne przy uproszczonych założeniach. Będziemy mówić, że system odbywający interakcje z procesem decyzyjnym Markowa posługuje się strategią Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} ,, jeśli w każdym kroku Parser nie mógł rozpoznać (błąd składni): {\displaystyle t \} , wykonuje on akcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t=\pi(x_t) \} ,.

Funkcja wartości ze względu na strategię Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} , jest dla każdego stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x\in X \} , określona następująco: Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^{\pi}(x) = \mathbf{E}_{\pi}\bigg[\sum_{t=0}^{\infty}\gamma^tr_t \;\Big|\; x_0 = x\bigg]. \} , (7)

W powyższej definicji symbol Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{E}_{\pi} \} , oznacza wartość oczekiwaną przy założeniu posługiwania się strategią Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} ,. Zgodnie z nią funkcja wartości ze względu na strategię Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} , przyporządkowuje każdemu stanowi oczekiwaną wartość zdyskontowanej sumy przyszłych nagród, jakie będą otrzymane przez system rozpoczynający działalność w tym stanie i posługujący się strategią Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} ,.

Funkcja wartości akcji ze względu na strategię Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} , jest dla każdej pary stan-akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle x,a\rangle\in X\times A \} , określona następująco: Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^{\pi}(x, a) = \mathbf{E}_{\pi}\bigg[\varrho(x,a) + \sum_{t=1}^{\infty}\gamma^tr_t \;\Big|\; x_0=x,a_0=a\bigg]. \} , (8)

Funkcja wartości akcji ze względu na strategię Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} , przyporządkowuje każdej parze stan-akcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle x,a\rangle \} , oczekiwaną wartość zdyskontowanej sumy przyszłych nagród, jakie będą otrzymane przez system rozpoczynający działalność w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , od wykonania akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , i posługujący się następnie strategią Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} ,. Jak zobaczymy niżej, funkcja wartości akcji może stanowić wygodną ze względów obliczeniowych formę reprezentacji jednocześnie funkcji wartości i strategii.

Optymalność strategii

Posługując się powyższymi definicjami można sformalizować pojęcie optymalności strategii.

Mówimy, że strategia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi' \} , jest lepsza od strategii Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} , jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^{\pi'}(x)\geq V^{\pi}(x) \} , dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle x\in X \} , i przynajmniej dla jednego stanu nierówność jest ostra.

Strategią optymalną jest każda strategia, dla której nie istnieje strategia od niej lepsza.

Inaczej mówiąc, strategią optymalną jest (każda) strategia maksymalizująca wartość każdego stanu.

Strategią zachłanną względem funkcji wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle V \} , jest (każda) strategia określona następująco: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi(x) = \mathrm{arg}\max_a\Big[R(x,a)+\gamma\sum_yP_{xy}(a)V(y)\Big]. \} , (9)

Strategią zachłanną względem aukcji wartości akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} , jest (każda) strategia określona następująco: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi(x) = \mathrm{arg}\max_aQ(x,a). \} , (10)

Dowolna strategia zachłanna względem optymalnej funkcji wartości lub optymalnej funkcji wartości akcji jest strategią optymalną. Dowolną optymalną strategię oznaczać będziemy przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi^* \} ,, a odpowiadające jej funkcje wartości i wartości akcji odpowiednio przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^* \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^* \} ,.

Przykład: siatka Parser nie mógł rozpoznać (błąd składni): {\displaystyle 5\times 5 \} ,. Poniższa tablica przedstawia środowisko dwuwymiarowej siatki Parser nie mógł rozpoznać (błąd składni): {\displaystyle 5\times 5 \} ,. Poszczególnym komórkom odpowiadają stany. Zbiór akcji zawiera akcje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \leftarrow \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \downarrow \} ,. Wykonanie akcji powoduje w sposób deterministyczny przejście z aktualnej komórki do odpowiedniej komórki sąsiedniej, o ile ruch ten nie jest zablokowany przez granicę środowiska lub przeszkodę (komórki zawierające *) - wówczas stan nie ulega zmianie. W każdej komórce, do której można wejść, wpisano wartość nagrody uzyskiwanej po wejściu do niej.

	0	1	2	3	4
0	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_1 \} ,
1	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	*	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	*	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,
2	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,
3	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	*	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	*	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,
4	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1 \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_2 \} ,

Jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_1=r_2=0 \} ,, to dla dowolnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \gamma>0 \} , strategią optymalną jest np. strategia przedstawiona w poniższej tablicy. Znalezienie wszystkich innych strategii optymalnych pozostawiamy jako ćwiczenie.

	0	1	2	3	4
0	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,
1	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} ,
2	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \uparrow \} ,
3	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \downarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \downarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \downarrow \} ,
4	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \rightarrow \} ,

Dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \gamma=0.9 \} , mamy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^*(00) = \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1-0.9-0.81 = -2.71, \} ,	(11)
Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^*(00,\downarrow) = \} ,	Parser nie mógł rozpoznać (błąd składni): {\displaystyle -1-0.9+0.81\cdot(-2.71) = -4.0951. \} ,	(12)

Programowanie dynamiczne

Teoria programowania dynamicznego zainicjowana przez Bellmana w latach 50. gwarantuje, że dla dowolnego procesu decyzyjnego Markowa istnieje przynajmniej jedna (stacjonarna, deterministyczna) strategia optymalna. Każdej strategii optymalnej odpowiada ta sama optymalna funkcja wartości i optymalna funkcja wartości akcji. Metody programowania dynamicznego pozwalają na wyznaczenie dowolnej z tych funkcji pod warunkiem znajomości Parser nie mógł rozpoznać (błąd składni): {\displaystyle R(x,a) \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{xy}(a) \} , dla każdych Parser nie mógł rozpoznać (błąd składni): {\displaystyle x,y\in X \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle a\in A \} ,.

Metody programowania dynamicznego opierają się na różnych formach równania Bellmana. Poniżej przedstawiamy równania Bellmana dla funkcji wartości i funkcji wartości akcji:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^{\pi}(x) = R(x,\pi(x)) + \gamma\sum_yP_{xy}(\pi(x))V^{\pi}(y), \} ,	(13)
Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^{\pi}(x,a) = R(x,a)+\gamma\sum_yP_{xy}(a)Q^{\pi}(y,\pi(y)). \} ,	(14)

Równania te są podstawą algorytmów obliczania funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^{\pi} \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^{\pi} \} , dla ustalonej strategii Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi \} ,. Równania optymalności Bellmana dla funkcji wartości i funkcji wartości akcji mają postać:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^*(x) = \max_a\Big[R(x,a)+\gamma\sum_yP_{xy}(a)V^*(y)\Big], \} ,	(15)
Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^*(x,a) = R(x,a)+\gamma\sum_yP_{xy}(a)\max_{a'}Q^*(y,a'). \} ,	(16)

Są one podstawą algorytmów obliczania odpowiednio funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^* \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^* \} ,.

Oczywiście, Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^{\pi}(x)=Q^{\pi}(x,\pi(x)) \} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^*(x)=\max_aQ^*(x,a)=Q^*(x,\pi^*(x)) \} , dla wszystkich stanów Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} ,. Oznacza to, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^* \} , wystarczają do określenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle V \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle V^* \} ,, odpowiednio, oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q^* \} , wystarcza do określenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi^* \} , (jako strategii zachłannej), bez potrzeby znajomości Parser nie mógł rozpoznać (błąd składni): {\displaystyle R(x,a) \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{xy}(a) \} , dla żadnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle x,y\in X \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle a\in A \} ,.

Programowanie dynamiczne a uczenie się ze wzmocnieniem

Uczenie się ze wzmocnieniem można porównać z programowaniem dynamicznym w następujący sposób:

• programowanie dynamiczne wymaga znajomości Parser nie mógł rozpoznać (błąd składni): {\displaystyle R(x,a) \} , dla wszystkich Parser nie mógł rozpoznać (błąd składni): {\displaystyle x\in X \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle a\in A \} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{xy}(a) \} , dla wszystkich Parser nie mógł rozpoznać (błąd składni): {\displaystyle x,y\in X \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle a\in A \} ,, podczas gdy uczenie się ze wzmocnieniem nie zakłada, że wielkości te są znane, i wykorzystuje faktycznie zaobserwowane nagrody i przejścia stanów,
• programowanie dynamiczne opiera się na wyczerpującym przeglądaniu całej przestrzeni stanów i akcji, podczas uczenie się ze wzmocnieniem wykorzystuje faktyczne trajektorie,
• programowanie dynamiczne prowadzi do obliczenia pełnej strategii optymalnej, podczas gdy uczenie się ze wzmocnieniem ma w gruncie rzeczy na celu działanie (w przybliżeniu) optymalne, które może być oparte na częściowej strategii (nie jest konieczne nauczenie się optymalnej strategii dla stanów, które nie występują w trakcie faktycznego działania ucznia).

Uczenie się strategii

Celem uczenia się ze wzmocnieniem jest nauczenie się strategii optymalnej (lub strategii dobrze przybliżającej strategię optymalną). Środkiem do osiągnięcia tego celu jest uczenie się funkcji wartości lub funkcji wartości akcji bez znajomości środowiska, na podstawie obserwowanych interakcji (sekwencji stanów, akcji i nagród). Przez uczenie się funkcji należy w tym przypadku rozumieć proces iteracyjnego modyfikowania funkcji, reprezentowanej w pewien ustalony sposób (np. w postaci stablicowanej bądź za pomocą aproksymatora funkcji), na podstawie kolejnych obserwacji ucznia. Jest to zasada działania najbardziej znanego algorytmu uczenia się ze wzmocnieniem, znanego jako Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} ,-learning.

Algorytm Q-learning

Algorytm Q-learning, zgodnie z tym co sugeruje jego nazwa, uczy się funkcji wartości akcji. Ściślej, uczy się on optymalnej funkcji wartości akcji, tak aby móc uzyskać strategię optymalną jako zachłanną względem niej.

Reguła aktualizacji stosowana w kroku Parser nie mógł rozpoznać (błąd składni): {\displaystyle t \} , do zmiany wartości akcji dla stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_t \} , i akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t \} , ma postać:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x_t,a_t) \xrightarrow{\beta} r_t+\gamma\max_aQ(x_{t+1},a). \} ,

(17)

Jest to skrótowy zapis dla operacji polegającej na zmianie wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x_t,a_t) \} , w taki sposób, aby zbliżyła się ona do wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t+\gamma\max_aQ(x_{t+1},a) \} ,. Parametr Parser nie mógł rozpoznać (błąd składni): {\displaystyle \beta \} ,, nazywany rozmiarem kroku lub współczynnikiem uczenia się, określa wielkość dokonywanej modyfikacji. Pełny zapis algorytmu przedstawiony jest poniżej.

W każdym kroku czasu Parser nie mógł rozpoznać (błąd składni): {\displaystyle t \} ,:

1. obserwuj aktualny stan Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_t \} ,;
2. wybierz akcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t \} , do wykonania w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_t \} ,;
3. wykonaj akcję Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_t \} ,;
4. obserwuj wzmocnienie Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t \} , i następny stan Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_{t+1} \} ,;
5. Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x_t,a_t) \xrightarrow{\beta} r_t+\gamma\max_aQ(x_{t+1},a) \} ,.

Łatwo zauważyć podobieństwo wielkości Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t+\gamma\max_aQ(x_{t+1},a) \} ,, w kierunku której „przesuwana” jest wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x_t,a_t) \} ,, do prawej strony równania optymalności Bellmana dla funkcji wartości akcji (16). Różnica polega na tym, że zamiast nieznanej wartości oczekiwanej nagrody wykorzystywana jest faktycznie otrzymana wartość nagrody Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t \} ,, a zamiast oczekiwanej wartości następnego stanu - wartość stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_{t+1} \} ,, który faktycznie stał się następnym stanem środowiska.

Wybór akcji

Podany wyżej algorytm nie precyzuje sposobu wybierania akcji na podstawie funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} ,. Chociaż do nauczenia się przez algorytm optymalnej funkcji wartości akcji wystarczy dowolna strategia wyboru akcji, która zapewnia, że każda akcja zawsze zachowuje niezerowe prawdopodobieństwo wykonania, w praktyce pożądane są strategie wyraźnie faworyzujące akcje o większych wartościach Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} ,, gdyż tylko one pozwalają uczniowi poprawiać jakość swojego działania.

Wybór akcji wymaga rozstrzygnięcia wymiany pomiędzy eksploracją a eksploatacją, czyli między działaniem w celu pozyskania wiedzy a działaniem w celu pozyskania nagród. Jest oczywiste, że oczekujemy od ucznia poprawy działania (czyli zwiększania dochodów) w trakcie uczenia się, a więc eksploatacji. Z drugiej strony, jeśli jego aktualna strategia nie jest optymalna, to musi on poznać (i docenić) efekty innych akcji, niż wynikające z tej strategii, a więc eksplorować. Eksploracja wpływa na szybkość zbieżności i jakość uzyskanej strategii (zbyt mała eksploracja może powodować przedwczesną zbieżność do strategii suboptymalnej, zbyt duża eksploracja powoduje, że zbieżność jest powolna, a po nauczeniu się optymalnej strategii uczeń się nią nie posługuje).

Często stosowane są bardzo proste strategie „prawie zachłannego” wyboru akcji znane jako strategia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon \} ,-zachłanna i strategia Boltzmanna. Każda z nich określa w pewien sposób prawdopodobieństwo wybrania akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} ,, które oznaczymy przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi(x,a) \} ,, na podstawie (wyłącznie) wartości akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x,a) \} ,. Bardziej zaawansowane strategie licznikowe dodatkowo biorą pod uwagę historię doświadczeń zgromadzonych przez ucznia dotyczących stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , i akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} ,.

Strategia $ϵ$-zachłanna

Najprostszą strategią stochastyczną jest strategia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon \} ,-zachłanna, w której z pewnym prawdopodobieństwem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon>0 \} , wybiera się dowolną akcję losowo według rozkładu równomiernego, a z prawdopodobieństwem Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1-\epsilon \} , wybiera się akcję zachłanną (jeśli jest ich wiele, to także losowo). Formalnie można to zapisać następująco:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi(x,a^*) = \begin{cases} \frac{1-\epsilon}{|\mathrm{Arg}\max_aQ(x,a)|} + \frac{\epsilon}{|A|} & \text{jeśli }a^*\in\mathrm{Arg}\max_aQ(x,a),\\ \frac{\epsilon}{|A|} & \text{w przeciwnym przypadku}. \end{cases} \} ,

(18)

Symbol Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Arg}\max_aQ(x,a) \} , oznacza zbiór wszystkich wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} ,, które maksymalizują Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x,a) \} ,.

Strategia Boltzmanna

Wadą strategii Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon \} ,-zachłannej jest to, że prawdopodobieństwo losowego zachowania się ucznia nie zależy od tego, czego już zdołał się nauczyć. Jednym ze sposobów przezwyciężenia tego mankamentu jest redukowanie wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon \} , w trakcie uczenia się (pozostaje kwestia, w jaki sposób i jak szybko). Inny sposób to np. strategia Boltzmanna, opisana wzorem:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi(x,a^*) = \frac{\exp(Q(x,a^*)/T)}{\sum_a\exp(Q(x,a)/T)}, \} ,

(19)

gdzie parametr Parser nie mógł rozpoznać (błąd składni): {\displaystyle T>0 \} , (temperatura) reguluje stopień losowości. Przy tej strategii prawdopodobieństwo wyboru akcji niezachłannej jest tym mniejsze, im bardziej akcja zachłanna ma większą Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} ,-wartość od pozostałych. Oczywiście w trakcie uczenia się można „schładzać” tę strategię (redukować Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} ,).

Strategie licznikowe

Bardziej zaawansowane mechanizmy eksploracji na ogół mają na celu większe eksplorowanie w obszarach przestrzeni stanów i akcji, dla których dotychczasowa wiedza ucznia jest niekompletna lub niepewna, a eksploatować w obszarach, dla których wartości są poznane z dużą pewnością. Typowe podejścia polegają na przechowywaniu i aktualizowaniu różnego typu liczników, w najprostszym przypadku śledzących dla każdego stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , i akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , liczbę Parser nie mógł rozpoznać (błąd składni): {\displaystyle n_{x,a} \} , razy, jaką akcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , została dotychczas wykonana w stanie Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} ,, lub liczbę kroków czasu, jakie upłynęły od jej ostatniego wykonania w tym stanie. Podczas wyboru akcji akcja może być wówczas preferowana z dwóch powodów: ma wysoką wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q \} , (czy też Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mu \} ,) lub była dotychczas mało razy wykonana w aktualnym stanie (bądź od dawna nie była w nim wykonywana). Zaproponowanie konkretnych strategii opartych na tej heurystyce pozostawiamy jako ćwiczenie.

Reprezentacja funkcji

Dokładny sposób realizacji operacji aktualizacji funkcji w uczeniu się ze wzmocnieniem jest ściśle związany z metodą przyjętą jej reprezentacji. Podstawowa reprezentacja tablicowa zakłada, że dla każdego stanu Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \} , i akcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x,a) \} , jest przechowywana w osobnej komórce pewnej tablicy. Wówczas aktualizacja (17) jest realizowana jako podstawienie:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Q(x_t,a_t) := (1-\beta)Q(x_t,a_t)+ \beta\big(r_t+\gamma\max_aQ(x_{t+1},a)\big). \} ,

(20)

Istniejące teoretyczne wyniki dotyczące zbieżności algorytmów uczenia się ze wzmocnieniem na ogół wymagają założenia o tablicowej reprezentacji funkcji, lecz w wielu praktycznych zastosowaniach jej użycie nie jest możliwe ze względu na duży rozmiar przestrzeni stanów lub jej ciągłość. Jeśli przestrzeń stanów jest duża, to przechowywanie wartości, wartości akcji lub funkcji strategii dla wszystkich stanów może wymagać bardzo dużo pamięci. Jeśli nawet potrzebna ilość pamięci jest dostępna, to uczenie się będzie niezwykle powolne: potrzeba bardzo wielu kroków, aby wypełnić wiarygodnymi wartościami tablice o tak dużych rozmiarach. W celu przezwyciężenia tych trudności łączy się algorytmy uczenia się ze wzmocnieniem z metodami regresji. Pozwalają one na przechowywanie przybliżonych wartości funkcji dla wielu stanów w rozsądnej ilości pamięci, a dzięki generalizacji przyspieszają uczenie się.

Aproksymator funkcji wartości musi umożliwiać przyrostowe modyfikacje na podstawie pojedynczych przykładów. Operacja aktualizacji funkcji wartości akcji (17) jest realizowana przez dostarczenie aproksymatorowi przykładu trenującego, w którym argumentem funkcji jest para Parser nie mógł rozpoznać (błąd składni): {\displaystyle (x_t,a_t) \} ,, a docelową wartością funkcji jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle r_t+\gamma\max_aQ(x_{t+1},a) \} ,. Często wygodne jest dokonywanie dekompozycji aproksymatora ze względu na akcje, czyli tworzenie oddzielnego aproksymatora, dla którego argumentem jest tylko stan, dla każdej możliwej akcji.

Uczenie się ze wzmocnieniem a przeszukiwanie

Uczenie się ze wzmocnieniem można traktować jako przeszukiwanie przestrzeni możliwych strategii. Jest ono realizowane w sposób powiązany z rzeczywistymi interakcjami ze środowiskiem. Każda kolejna strategia rozważana w trakcie procesu przeszukiwania powstaje przez modyfikację dotychczasowej strategii na podstawie zaobserwowanego doświadczenia (stanu, akcji, nagrody, następnego stanu). Jest to szczególny sposób niewyczerpującego przeglądania przestrzeni strategii.

Jednak również wędrówka po stanach środowiska, którą realizuje system uczący się ze wzmocnieniem, jest pod pewnymi względami analogiczna do wędrówki po przestrzeni przeszukiwania. Zauważmy, że funkcja wartości, reprezentująca przewidywaną sumę możliwych do uzyskania nagród przy rozpoczęciu działania od pewnego stanu, może pełnić rolę funkcji heurystycznej w przeszukiwaniu. W przypadku, gdy środowisko jest znane (tj. znany jest wpływ akcji na zmiany stanów środowiska i na uzyskiwane nagrody), można wybierać akcje na podstawie sumy nagrody i (zdyskontowanej) wartości następnego stanu, co w istocie jest wariantem strategii przeszukiwania typu „najpierw najlepszy”. Takie spostrzeżenia ujawniają możliwość stosowania uczenia się ze wzmocnieniem do takich zadań przeszukiwania, w których nie można ze względu na brak dostatecznej wiedzy zdefiniować użytecznej funkcji heurystycznej. Funkcja heurystyczna jest wtedy wyznaczana w procesie uczenia się, na podstawie wielokrotnych prób rozwiązywania zadania.

Stosowanie uczenia się ze wzmocnieniem

Nieco upraszczając sytuację, można sformułować następujące równanie:

które pokazuje, że konstruktor systemu uczącego się ze wzmocnieniem musi przede wszystkim określić odpowiednią reprezentację stanów i zbiór akcji oraz zaprojektować funkcję wzmocnienia, która dobrze określa stawiany projektowanemu systemowi cel. Chociaż istotnych decyzji do podjęcia jest znacznie więcej, te są najbardziej podstawowe. Reprezentacja stanów powinna zapewniać dostarczanie systemowi informacji potrzebnych do podejmowania optymalnych decyzji (zachowanie własności Markowa). Jeśli nie jest to możliwe, można rozważyć różne algorytmy uczenia się ze wzmocnieniem w środowiskach niemarkowowskich, których tu nie omawiamy (są dość nowe i tylko częściowo satysfakcjonujące). Akcje powinny być określane na odpowiednim poziomie abstrakcji: na tyle niskim, aby możliwe było ich bezpośrednie wykonywanie przez system, i na tyle wysokim, aby czas potrzebny do uzyskania za ich pomocą pożądanych celów nie był zbyt długi. Funkcja wzmocnienia oraz współczynnik dyskontowania muszą być tak dobrane, aby maksymalizacja zdyskontowanej sumy nagród była osiągana przez strategie realizujące cel, dla którego jest konstruowany system.

Paradygmat uczenia się ze wzmocnieniem jest prosty i abstrakcyjny na tyle, by być potencjalnie bardzo szeroko stosowalnym. Zakres tych zastosowań ograniczają wprawdzie, oprócz ludzkiej pomysłowości, ograniczenia obecnie znanych metod (związane zwłaszcza z niezadowalającą szybkością uczenia się), te jednak będą prawdopodobnie z czasem pokonywane. Dziedziny, w których możliwości zastosowań uczenia się ze wzmocnieniem wydają się w świetle dotychczasowych prac najbardziej obiecujące, to przede wszystkim:

• inteligentne sterowanie optymalne,
• uczące się roboty,
• gry planszowe,
• optymalizacja kombinatoryczna i szeregowanie.

Do najbardziej spektakularnych przykładów należy użycie uczenia się ze wzmocnieniem w połączeniu z reprezentacją funkcji wartości za pomocą sieci neuronowej do gry w trik-traka (backgammon): uzyskany w ten sposób program na podstawie własnej gry (ze sobą) doszedł do mistrzostwa (należy do kilku najlepszych graczy na świecie).