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 $t$,:

1. obserwuj aktualny stan $x_{t}$,;
2. wybierz akcję $a_{t}$, do wykonania w stanie $x_{t}$,;
3. wykonaj akcję $a_{t}$,;
4. obserwuj wzmocnienie $r_{t}$, i następny stan $x_{t+1}$,;
5. ucz się na podstawie doświadczenia $\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 $0$, ma za zadanie maksymalizowanie sumy:

$\mathbf {E} {\bigg [}\sum _{t=0}^{\infty }\gamma ^{t}r_{t}{\bigg ]}$,,

(1)

gdzie współczynnik dyskontowania $\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 $r_{1}$, we wszystkich krokach poprzedzających osiągnięcie sukcesu i $r_{2}\geq r_{1}$, w ostatnim kroku, po jego osiągnięciu. Należy przy tym zapewnić, że

$\sum _{t=0}^{n-1}\gamma ^{t}r_{1}+\gamma ^{n}r_{2}>\sum _{t=0}^{n}\gamma ^{t}r_{1}+\gamma ^{n+1}r_{2}$,

(2)

dla dowolnego $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ę $r_{1}$, we wszystkich krokach pośrednich i $r_{2}\leq r_{1}$, w kroku końcowym, to aby opłacało mu się odwlekać porażkę, musi być dla dowolnego $n>0$, spełniony warunek:

$\sum _{t=0}^{n-1}\gamma ^{t}r_{1}+\gamma ^{n}r_{2}<\sum _{t=0}^{n}\gamma ^{t}r_{1}+\gamma ^{n+1}r_{2}$,

(3)

Podanie przykładów wartości $r_{1}$,, $r_{2}$,, i $\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ę:

${\text{MDP}}=\langle X,A,\varrho ,\delta \rangle$,,

(4)

gdzie

• $X$, jest skończonym zbiorem stanów,
• $A$, jest skończonym zbiorem akcji,
• $\varrho$, jest funkcją nagrody (wzmocnienia),
• $\delta$, jest funkcją przejścia stanów.

Dla każdej pary $\langle x,a\rangle \in X\times A$, wartość $\varrho (x,a)$, jest zmienną losową oznaczającą nagrodę otrzymywaną po wykonaniu akcji $a$, w stanie $x$,, a wartość $\delta (x,a)$, jest zmienną losową oznaczającą następny stan po wykonaniu akcji $a$, w stanie $x$,. Oznacza to, wobec wprowadzonej wcześniej notacji, że $r_{t}$, jest realizacją zmiennej losowej $\varrho (x_{t},a_{t})$, oraz $x_{t+1}$, jest realizacją zmiennej losowej $\delta (x_{t},a_{t})$,.

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

$R(x,a)=$,	$\mathbf {E} {\big [}\varrho (x,a){\big ]}$,	(5)
$P_{xy}(a)=$,	$\mathrm {Pr} {\big (}\delta (x,a)=y{\big )}$,	(6)

Własność Markowa

Kluczowe znaczenie ma tzw. własność Markowa: $\varrho$, i $\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 $\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ą $\pi$,, jeśli w każdym kroku $t$, wykonuje on akcję $a_{t}=\pi (x_{t})$,.

Funkcja wartości ze względu na strategię $\pi$, jest dla każdego stanu $x\in X$, określona następująco: $V^{\pi }(x)=\mathbf {E} _{\pi }{\bigg [}\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\;{\Big |}\;x_{0}=x{\bigg ]}$, (7)

W powyższej definicji symbol $\mathbf {E} _{\pi }$, oznacza wartość oczekiwaną przy założeniu posługiwania się strategią $\pi$,. Zgodnie z nią funkcja wartości ze względu na strategię $\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ą $\pi$,.

Funkcja wartości akcji ze względu na strategię $\pi$, jest dla każdej pary stan-akcji $\langle x,a\rangle \in X\times A$, określona następująco: $Q^{\pi }(x,a)=\mathbf {E} _{\pi }{\bigg [}\varrho (x,a)+\sum _{t=1}^{\infty }\gamma ^{t}r_{t}\;{\Big |}\;x_{0}=x,a_{0}=a{\bigg ]}$, (8)

Funkcja wartości akcji ze względu na strategię $\pi$, przyporządkowuje każdej parze stan-akcja $\langle x,a\rangle$, oczekiwaną wartość zdyskontowanej sumy przyszłych nagród, jakie będą otrzymane przez system rozpoczynający działalność w stanie $x$, od wykonania akcji $a$, i posługujący się następnie strategią $\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 $\pi '$, jest lepsza od strategii $\pi$, jeśli $V^{\pi '}(x)\geq V^{\pi }(x)$, dla każdego $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 $V$, jest (każda) strategia określona następująco: $\pi (x)=\mathrm {arg} \max _{a}{\Big [}R(x,a)+\gamma \sum _{y}P_{xy}(a)V(y){\Big ]}$, (9)

Strategią zachłanną względem aukcji wartości akcji $Q$, jest (każda) strategia określona następująco: $\pi (x)=\mathrm {arg} \max _{a}Q(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 $\pi ^{*}$,, a odpowiadające jej funkcje wartości i wartości akcji odpowiednio przez $V^{*}$, i $Q^{*}$,.

Przykład: siatka $5\times 5$,. Poniższa tablica przedstawia środowisko dwuwymiarowej siatki $5\times 5$,. Poszczególnym komórkom odpowiadają stany. Zbiór akcji zawiera akcje $\leftarrow$,, $\rightarrow$,, $\uparrow$, i $\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	$-1$,	$-1$,	$-1$,	$-1$,	$r_{1}$,
1	$-1$,	*	$-1$,	*	$-1$,
2	$-1$,	$-1$,	$-1$,	$-1$,	$-1$,
3	$-1$,	*	$-1$,	*	$-1$,
4	$-1$,	$-1$,	$-1$,	$-1$,	$r_{2}$,

Jeśli $r_{1}=r_{2}=0$,, to dla dowolnego $\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	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,
1	$\uparrow$,	$\rightarrow$,	$\uparrow$,	$\rightarrow$,	$\uparrow$,
2	$\uparrow$,	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,	$\uparrow$,
3	$\downarrow$,	$\rightarrow$,	$\downarrow$,	$\rightarrow$,	$\downarrow$,
4	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,	$\rightarrow$,

Dla $\gamma =0.9$, mamy

$V^{*}(00)=$,	$-1-0.9-0.81=-2.71$,	(11)
$Q^{*}(00,\downarrow )=$,	$-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 $R(x,a)$, i $P_{xy}(a)$, dla każdych $x,y\in X$, i $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:

$V^{\pi }(x)=R(x,\pi (x))+\gamma \sum _{y}P_{xy}(\pi (x))V^{\pi }(y)$,	(13)
$Q^{\pi }(x,a)=R(x,a)+\gamma \sum _{y}P_{xy}(a)Q^{\pi }(y,\pi (y))$,	(14)

Równania te są podstawą algorytmów obliczania funkcji $V^{\pi }$, i $Q^{\pi }$, dla ustalonej strategii $\pi$,. Równania optymalności Bellmana dla funkcji wartości i funkcji wartości akcji mają postać:

$V^{*}(x)=\max _{a}{\Big [}R(x,a)+\gamma \sum _{y}P_{xy}(a)V^{*}(y){\Big ]}$,	(15)
$Q^{*}(x,a)=R(x,a)+\gamma \sum _{y}P_{xy}(a)\max _{a'}Q^{*}(y,a')$,	(16)

Są one podstawą algorytmów obliczania odpowiednio funkcji $V^{*}$, i $Q^{*}$,.

Oczywiście, $V^{\pi }(x)=Q^{\pi }(x,\pi (x))$, oraz $V^{*}(x)=\max _{a}Q^{*}(x,a)=Q^{*}(x,\pi ^{*}(x))$, dla wszystkich stanów $x$,. Oznacza to, że $Q$, i $Q^{*}$, wystarczają do określenia $V$, i $V^{*}$,, odpowiednio, oraz $Q^{*}$, wystarcza do określenia $\pi ^{*}$, (jako strategii zachłannej), bez potrzeby znajomości $R(x,a)$, i $P_{xy}(a)$, dla żadnych $x,y\in X$, i $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 $R(x,a)$, dla wszystkich $x\in X$, i $a\in A$, oraz $P_{xy}(a)$, dla wszystkich $x,y\in X$, i $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 $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 $t$, do zmiany wartości akcji dla stanu $x_{t}$, i akcji $a_{t}$, ma postać:

$Q(x_{t},a_{t})\xrightarrow {\beta } r_{t}+\gamma \max _{a}Q(x_{t+1},a).$,

(17)

Jest to skrótowy zapis dla operacji polegającej na zmianie wartości $Q(x_{t},a_{t})$, w taki sposób, aby zbliżyła się ona do wartości $r_{t}+\gamma \max _{a}Q(x_{t+1},a)$,. Parametr $\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 $t$,:

1. obserwuj aktualny stan $x_{t}$,;
2. wybierz akcję $a_{t}$, do wykonania w stanie $x_{t}$,;
3. wykonaj akcję $a_{t}$,;
4. obserwuj wzmocnienie $r_{t}$, i następny stan $x_{t+1}$,;
5. $Q(x_{t},a_{t})\xrightarrow {\beta } r_{t}+\gamma \max _{a}Q(x_{t+1},a)$,.

Łatwo zauważyć podobieństwo wielkości $r_{t}+\gamma \max _{a}Q(x_{t+1},a)$,, w kierunku której „przesuwana” jest wartość $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 $r_{t}$,, a zamiast oczekiwanej wartości następnego stanu - wartość stanu $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 $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 $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 $\epsilon$,-zachłanna i strategia Boltzmanna. Każda z nich określa w pewien sposób prawdopodobieństwo wybrania akcji $a$, w stanie $x$,, które oznaczymy przez $\pi (x,a)$,, na podstawie (wyłącznie) wartości akcji $Q(x,a)$,. Bardziej zaawansowane strategie licznikowe dodatkowo biorą pod uwagę historię doświadczeń zgromadzonych przez ucznia dotyczących stanu $x$, i akcji $a$,.

Strategia $\epsilon$-zachłanna

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

$\pi (x,a^{*})={\begin{cases}{\frac {1-\epsilon }{|\mathrm {Arg} \max _{a}Q(x,a)|}}+{\frac {\epsilon }{|A|}}&{\text{jeśli }}a^{*}\in \mathrm {Arg} \max _{a}Q(x,a),\\{\frac {\epsilon }{|A|}}&{\text{w przeciwnym przypadku}}.\end{cases}}$,

(18)

Symbol $\mathrm {Arg} \max _{a}Q(x,a)$, oznacza zbiór wszystkich wartości $a$,, które maksymalizują $Q(x,a)$,.

Strategia Boltzmanna

Wadą strategii $\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 $\epsilon$, w trakcie uczenia się (pozostaje kwestia, w jaki sposób i jak szybko). Inny sposób to np. strategia Boltzmanna, opisana wzorem:

$\pi (x,a^{*})={\frac {\exp(Q(x,a^{*})/T)}{\sum _{a}\exp(Q(x,a)/T)}}$,,

(19)

gdzie parametr $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ą $Q$,-wartość od pozostałych. Oczywiście w trakcie uczenia się można „schładzać” tę strategię (redukować $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 $x$, i akcji $a$, liczbę $n_{x,a}$, razy, jaką akcja $a$, została dotychczas wykonana w stanie $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ść $Q$, (czy też $\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 $x$, i akcji $a$, wartość $Q(x,a)$, jest przechowywana w osobnej komórce pewnej tablicy. Wówczas aktualizacja (17) jest realizowana jako podstawienie:

$Q(x_{t},a_{t}):=(1-\beta )Q(x_{t},a_{t})+\beta {\big (}r_{t}+\gamma \max _{a}Q(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 $(x_{t},a_{t})$,, a docelową wartością funkcji jest $r_{t}+\gamma \max _{a}Q(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).