Q-learning - Q-learning

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Q -learning jest modelem wolne uczenie zbrojenie algorytm, aby dowiedzieć się wartość działania w określonym stanie. Nie wymaga modelu środowiska (stąd „bez modelu”) i może poradzić sobie z problemami z przejściami stochastycznymi i nagrodami bez konieczności adaptacji.

Dla każdego skończonego procesu decyzyjnego Markowa (FMDP), Q- learning znajduje optymalną politykę w sensie maksymalizacji oczekiwanej wartości całkowitej nagrody na wszystkich kolejnych etapach, zaczynając od aktualnego stanu. Q- learning może zidentyfikować optymalną politykę wyboru działań dla dowolnego FMDP, biorąc pod uwagę nieskończony czas eksploracji i politykę częściowo losową. „Q” odnosi się do funkcji obliczanej przez algorytm – oczekiwanej nagrody za akcję podjętą w danym stanie.

Nauka wzmacniania

Wzmocnienie nauka wiąże się z agentem , zestaw stanów oraz zbiór z działaniami na stanie. Wykonując akcję agent przechodzi ze stanu do stanu. Wykonanie akcji w określonym stanie zapewnia agentowi nagrodę (wynik liczbowy). ${\displaystyle S}$${\ Displaystyle A}$${\displaystyle a\w A}$

Celem agenta jest maksymalizacja jego całkowitej nagrody. Czyni to, dodając maksymalną nagrodę możliwą do osiągnięcia w przyszłych stanach do nagrody za osiągnięcie obecnego stanu, skutecznie wpływając na bieżące działanie poprzez potencjalną przyszłą nagrodę. Ta potencjalna nagroda jest ważoną sumą oczekiwanych wartości nagród wszystkich przyszłych kroków, począwszy od obecnego stanu.

Jako przykład rozważmy proces wsiadania do pociągu, w którym nagroda jest mierzona ujemnym całkowitym czasem wsiadania (alternatywnie koszt wsiadania do pociągu jest równy czasowi wsiadania). Jedną ze strategii jest wejście do drzwi pociągu, gdy tylko się otworzą, minimalizując początkowy czas oczekiwania. Jeśli jednak pociąg jest zatłoczony, po początkowej akcji wejścia do drzwi będziesz miał powolne wejście, ponieważ ludzie walczą z tobą o opuszczenie pociągu, gdy próbujesz wejść na pokład. Całkowity czas wejścia na pokład lub koszt wynosi wtedy:

• 0 sekund czasu oczekiwania + 15 sekund czasu walki

Następnego dnia przez przypadek (eksploracja) decydujesz się poczekać i pozwolić innym odejść pierwsi. Powoduje to początkowo dłuższy czas oczekiwania. Jednak czas walki z innymi pasażerami jest krótszy. Ogólnie rzecz biorąc, ta ścieżka ma wyższą nagrodę niż ta z poprzedniego dnia, ponieważ łączny czas wejścia na pokład wynosi teraz:

• 5 sekund czasu oczekiwania + 0 sekund czasu walki

Poprzez eksplorację, pomimo początkowego działania (pacjenta) skutkującego wyższym kosztem (lub negatywną nagrodą) niż w przypadku strategii siłowej, ogólny koszt jest niższy, co ujawnia bardziej satysfakcjonującą strategię.

Algorytm

Tablica Q-Learning stanów według działań, która jest inicjowana do zera, a następnie każda komórka jest aktualizowana podczas uczenia.

Po krokach w przyszłość agent zdecyduje o kolejnym kroku. Waga tego kroku jest obliczana jako , gdzie ( współczynnik dyskontowy ) jest liczbą z zakresu od 0 do 1 ( ) i skutkuje wyższą wyceną nagród otrzymanych wcześniej niż otrzymanych później (odzwierciedlającą wartość „dobrego początku”). można również interpretować jako prawdopodobieństwo sukcesu (lub przetrwania) na każdym kroku . ${\ Displaystyle \ Delta t}$${\ Displaystyle \ gamma ^ {\ Delta t}}$${\ Displaystyle \ gamma}$${\ Displaystyle 0 \ równoważnik \ gamma \ równoważnik 1}$${\ Displaystyle \ gamma}$${\ Displaystyle \ Delta t}$

Algorytm posiada zatem funkcję obliczającą jakość kombinacji stan-działanie:

${\ Displaystyle Q: S \ razy A \ do \ mathbb {R}}$.

Przed rozpoczęciem nauki jest inicjowany na możliwie dowolną stałą wartość (wybraną przez programistę). Następnie, za każdym razem, gdy agent wybiera akcję , obserwuje nagrodę , wchodzi w nowy stan (który może zależeć zarówno od stanu poprzedniego, jak i wybranej akcji) i jest aktualizowany. Rdzeniem algorytmu jest równanie Bellmana jako prosta aktualizacja iteracji wartości , wykorzystująca średnią ważoną starej wartości i nowych informacji: ${\displaystyle Q}$${\displaystyle t}$${\displaystyle a_{t}}$${\displaystyle r_{t}}$${\displaystyle s_{t+1}}$${\displaystyle s_{t}}$${\displaystyle Q}$

${\ Displaystyle Q ^ {nowy} (s_ {t}, a_ {t}) \ leftarrow \ underbrace {Q (s_ {t}, a_ {t})} _ {\ tekst {stara wartość}} + \ underbrace { \alpha } _{\text{wskaźnik uczenia się}}\cdot \overbrace {{\bigg (}\underbrace {\underbrace {r_{t}} _{\text{nagroda}}+\underbrace {\gamma } _{ \text{współczynnik rabatowy}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{oszacowanie optymalnej przyszłej wartości}}} _{\text{nowa wartość (docelowa różnica czasowa)}}-\underbrace {Q(s_{t},a_{t})} _{\text{stara wartość}}{\bigg )}} ^{\text{różnica czasowa}}}$

gdzie jest nagroda otrzymana przy przejściu ze stanu do stanu i jest wskaźnikiem uczenia się . ${\displaystyle r_{t}}$${\displaystyle s_{t}}$${\displaystyle s_{t+1}}$${\ Displaystyle \ alfa}$ ${\ Displaystyle (0<\alfa \leq 1)}$

Zauważ, że jest to suma trzech czynników: ${\ Displaystyle Q ^ {nowy} (s_ {t}, a_ {t})}$

• ${\ Displaystyle (1-\ alfa) Q (s_ {t}, a_ {t})}$: aktualna wartość ważona szybkością uczenia. Wartości szybkości uczenia się bliskie 1 powodują, że zmiany są szybsze.${\displaystyle Q}$
• ${\ Displaystyle \ alfa \, r_ {t}}$: nagroda do uzyskania, jeśli działanie zostanie podjęte w stanie (ważone przez tempo uczenia się)${\ Displaystyle r_ {t} = r (s_ {t}, a_ {t})}$${\displaystyle a_{t}}$${\displaystyle s_{t}}$
• ${\ Displaystyle \ alfa \ gamma \ max _ {a} Q (s_ {t + 1}, a)}$: maksymalna nagroda, którą można uzyskać od państwa (ważona szybkością uczenia się i współczynnikiem dyskontowym)${\displaystyle s_{t+1}}$

Epizod algorytmu kończy się, gdy stan jest stanem końcowym lub końcowym . Jednak Q- learning może się również uczyć w zadaniach nieepizodycznych (w wyniku własności zbieżnych szeregów nieskończonych). Jeśli współczynnik dyskontowy jest mniejszy niż 1, wartości akcji są skończone, nawet jeśli problem może zawierać nieskończone pętle. ${\displaystyle s_{t+1}}$

Dla wszystkich stanów końcowych , nigdy nie jest aktualizowany, ale jest ustawiany na wartość nagrody obserwowaną dla stanu . W większości przypadków można ją przyjąć jako równą zero. ${\displaystyle s_{f}}$${\ Displaystyle Q (s_ {f}, a)}$${\ Displaystyle r}$${\displaystyle s_{f}}$${\ Displaystyle Q (s_ {f}, a)}$

Wpływ zmiennych

Szybkość nauki

Szybkość uczenia się lub wielkość kroku określa, w jakim stopniu nowo nabyte informacje zastępują stare informacje. Współczynnik 0 sprawia, że ​​agent niczego się nie uczy (wyłącznie wykorzystując wcześniejszą wiedzę), podczas gdy współczynnik 1 sprawia, że ​​agent bierze pod uwagę tylko najnowsze informacje (ignorując wcześniejszą wiedzę w celu zbadania możliwości). W środowiskach w pełni deterministycznych szybkość uczenia się jest optymalna. Gdy problem jest stochastyczny , algorytm zbiega się w pewnych warunkach technicznych na szybkości uczenia się, które wymagają jej zmniejszenia do zera. W praktyce często stosuje się stałą szybkość uczenia się, na przykład dla wszystkich . ${\ Displaystyle \ alfa _ {t} = 1}$${\ Displaystyle \ alfa _ {t} = 0,1}$${\displaystyle t}$

Współczynnik rabatu

Czynnik dyskontowy określa znaczenie przyszłych nagród. Współczynnik 0 sprawi, że agent będzie „krótkowzroczny” (lub krótkowzroczny), biorąc pod uwagę tylko bieżące nagrody, tj. (w powyższej regule aktualizacji), podczas gdy współczynnik zbliżający się do 1 sprawi, że będzie dążył do długoterminowej wysokiej nagrody. Jeżeli współczynnik dyskonta osiągnie lub przekroczy 1, wartości akcji mogą się różnić. Dla , bez stanu końcowego lub jeśli agent nigdy go nie osiągnie, wszystkie historie środowiska stają się nieskończenie długie, a narzędzia z addytywnymi, niedyskontowalnymi nagrodami na ogół stają się nieskończone. Nawet przy współczynniku dyskontowym tylko nieznacznie niższym niż 1, uczenie funkcji Q prowadzi do propagacji błędów i niestabilności, gdy funkcja wartości jest aproksymowana sztuczną siecią neuronową . W takim przypadku rozpoczęcie od niższego współczynnika dyskontowego i zwiększanie go w kierunku wartości końcowej przyspiesza naukę. ${\ Displaystyle \ gamma}$${\displaystyle r_{t}}$${\ Displaystyle \ gamma = 1}$

Warunki początkowe ( Q ₀ )

Ponieważ Q- learning jest algorytmem iteracyjnym, domyślnie zakłada stan początkowy przed pierwszą aktualizacją. Wysokie wartości początkowe, znane również jako „optymistyczne warunki początkowe”, mogą zachęcać do eksploracji: bez względu na wybrane działanie, reguła aktualizacji spowoduje, że będzie miała niższe wartości niż inne alternatywy, zwiększając w ten sposób prawdopodobieństwo ich wyboru. Pierwszą nagrodę można wykorzystać do zresetowania warunków początkowych. Zgodnie z tym pomysłem, przy pierwszym wykonaniu działania nagroda jest używana do ustalenia wartości . Pozwala to na natychmiastowe uczenie się w przypadku stałych, deterministycznych nagród. Oczekuje się, że model, który obejmuje resetowanie warunków początkowych (RIC), będzie lepiej przewidywać zachowanie uczestników niż model, który zakłada dowolne arbitralne warunki początkowe (AIC). RIC wydaje się być spójny z ludzkim zachowaniem w powtarzanych eksperymentach z wyborem binarnym. ${\ Displaystyle r}$${\displaystyle Q}$

Realizacja

Q- learning w swojej najprostszej postaci przechowuje dane w tabelach. Podejście to słabnie wraz ze wzrostem liczby stanów/działań, ponieważ prawdopodobieństwo, że agent odwiedzi dany stan i wykona określoną akcję, jest coraz mniejsze.

Przybliżenie funkcji

Q- learning można łączyć z aproksymacją funkcji . Umożliwia to zastosowanie algorytmu do większych problemów, nawet gdy przestrzeń stanów jest ciągła.

Jednym z rozwiązań jest użycie (dostosowanej) sztucznej sieci neuronowej jako aproksymatora funkcji. Aproksymacja funkcji może przyspieszyć uczenie się w problemach skończonych, ponieważ algorytm może uogólniać wcześniejsze doświadczenia na stany wcześniej niewidziane.

Kwantyzacja

Inna technika zmniejszania przestrzeni stanów/działań kwantyzuje możliwe wartości. Rozważmy przykład nauki balansowania kijem na palcu. Aby opisać stan w pewnym momencie, należy uwzględnić położenie palca w przestrzeni, jego prędkość, kąt nachylenia drążka i prędkość kątową drążka. Daje to czteroelementowy wektor, który opisuje jeden stan, tj. migawkę jednego stanu zakodowaną w cztery wartości. Problem polega na tym, że istnieje nieskończenie wiele możliwych stanów. Aby zmniejszyć możliwą przestrzeń prawidłowych działań, do zasobnika można przypisać wiele wartości. Dokładna odległość palca od jego pozycji początkowej (-Infinity to Infinity) nie jest znana, ale raczej czy jest daleko, czy nie (Near, Far).

Historia

Q- learning został wprowadzony przez Chrisa Watkinsa w 1989 roku. Dowód zbieżności przedstawili Watkins i Peter Dayan w 1992 roku.

Watkins zajmował się tytułem swojej pracy doktorskiej „Uczenie się z opóźnionych nagród”. Osiem lat wcześniej, w 1981 roku, ten sam problem, pod nazwą „Opóźnione uczenie się ze wzmocnieniem”, został rozwiązany przez Crossbar Adaptive Array (CAA) Bozinowskiego. Macierz pamięci była taka sama, jak osiem lat później Q-tablica Q-learningu. Architektura wprowadziła termin „ocena stanu” w uczeniu się ze wzmocnieniem. Algorytm uczenia krzyżowego, zapisany w artykule pseudokodem matematycznym , w każdej iteracji wykonuje następujące obliczenia: ${\ Displaystyle W = \ | w (a, s) \ |}$

• W stanie s wykonaj akcję a ;
• Odbierz stan konsekwencji s' ;
• Ocena stanu obliczeniowego ;${\displaystyle v(s')}$
• Zaktualizuj wartość poprzeczki .${\ Displaystyle w '(a, s) = w (a, s) + v (s')}$

Termin „wtórne wzmocnienie” zapożyczono z teorii uczenia się zwierząt, aby modelować wartości stanu poprzez wsteczną propagację : wartość stanu sytuacji konsekwencji jest wstecznie propagowana do wcześniej napotkanych sytuacji. CAA oblicza wartości stanu w pionie i działania w poziomie ("poprzeczka"). Wykresy demonstracyjne przedstawiające opóźnione uczenie się ze wzmacnianiem zawierały stany (stany pożądane, niepożądane i neutralne), które zostały obliczone przez funkcję oceny stanu. Ten system uczenia się był prekursorem algorytmu Q-learning. ${\displaystyle v(s')}$

W 2014 r. firma Google DeepMind opatentowała aplikację Q-learning do głębokiego uczenia , zatytułowaną „głębokie uczenie ze wzmocnieniem” lub „głębokie Q-learning”, w której można grać w gry na Atari 2600 na poziomie eksperta.

Warianty

Głębokie Q-learning

System DeepMind wykorzystywał głęboką konwolucyjną sieć neuronową z warstwami kafelkowych filtrów konwolucyjnych, które naśladowały efekty pól receptywnych. Uczenie się ze wzmocnieniem jest niestabilne lub rozbieżne, gdy do reprezentacji Q używany jest aproksymator funkcji nieliniowej, taki jak sieć neuronowa. Ta niestabilność wynika z korelacji występujących w sekwencji obserwacji, faktu, że małe aktualizacje Q mogą znacząco zmienić politykę agenta oraz rozkład danych i korelacje między Q a wartościami docelowymi.

Technika ta wykorzystywała powtórkę doświadczeń, mechanizm inspirowany biologią, który wykorzystuje losową próbkę wcześniejszych działań zamiast ostatnich działań, aby kontynuować. Usuwa to korelacje w sekwencji obserwacji i wygładza zmiany w dystrybucji danych. Aktualizacje iteracyjne dostosowują Q do wartości docelowych, które są aktualizowane tylko okresowo, dodatkowo zmniejszając korelacje z wartością docelową.

Podwójne Q-learning

Ponieważ przyszła maksymalna przybliżona wartość działania w Q-learningu jest oceniana przy użyciu tej samej funkcji Q, co w obecnej polityce wyboru działań, w hałaśliwym otoczeniu Q-learning może czasami przeszacować wartości działań, spowalniając uczenie. Aby to naprawić, zaproponowano wariant zwany Double Q-learning. Double Q-learning to algorytm uczenia się ze wzmocnieniem poza polityką , w którym do oceny wartości używana jest inna polityka niż ta, która jest używana do wyboru następnego działania.

W praktyce dwie oddzielne funkcje wartości są szkolone w sposób wzajemnie symetryczny przy użyciu oddzielnych doświadczeń oraz . Podwójny krok aktualizacji Q-learning jest wtedy następujący: ${\ Displaystyle Q ^ {A}}$${\ Displaystyle Q ^ {B}}$

${\ Displaystyle Q_ {t + 1} ^ {A} (s_ {t}, a_ {t}) = Q_ {t} ^ {A} (s_ {t}, a_ {t}) + \ alfa _ {t }(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{B}\left(s_{t+1},\mathop {\nazwa operatora {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)}$, oraz

${\ Displaystyle Q_ {t + 1} ^ {B} (s_ {t}, a_ {t}) = Q_ {t} ^ {B} (s_ {t}, a_ {t}) + \ alfa _ {t }(s_{t},a_{t})\left(r_{t}+\gamma Q_{t}^{A}\left(s_{t+1},\mathop {\nazwa operatora {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right). }$

Teraz szacowana wartość zdyskontowanej przyszłości jest wyceniana przy użyciu innej polityki, co rozwiązuje problem przeszacowania.

Algorytm ten został później zmodyfikowany w 2015 roku i połączony z głębokim uczeniem , tak jak w algorytmie DQN, co dało Double DQN, który przewyższa oryginalny algorytm DQN.

Inni

Opóźnione Q-learning jest alternatywą wdrożenie internetowego Q -Learning algorytmu, z prawdopodobnie około prawidłowej (PAC) uczenia się .

Greedy GQ jest odmianą Q- learningu do użycia w połączeniu z (liniowym) aproksymacją funkcji. Zaletą Greedy GQ jest to, że zbieżność jest gwarantowana nawet wtedy, gdy aproksymacja funkcji jest używana do szacowania wartości akcji.

Dystrybucyjny Q-learning jest wariantem Q -Learning dążącej do modelowania rozkładu zwrotów zamiast oczekiwanego zwrotu z każdej akcji. Zaobserwowano, że ułatwia szacowanie przez głębokie sieci neuronowe i może umożliwić alternatywne metody kontroli, takie jak kontrola wrażliwa na ryzyko.

Ograniczenia

Standardowy algorytm Q-learning (używający tabeli) dotyczy tylko akcji dyskretnych i przestrzeni stanów. Dyskretyzacja tych wartości prowadzi do nieefektywnego uczenia się, głównie z powodu przekleństwa wymiarowości . Istnieją jednak adaptacje Q-learningu, które próbują rozwiązać ten problem, takie jak Q-Learning z wykorzystaniem przewodowej sieci neuronowej. ${\displaystyle Q}$

Zobacz też

• Nauka wzmacniania
• Nauka różnic czasowych
• SARSA
• Powtarzany dylemat więźnia
• Teoria gry

Bibliografia

Zewnętrzne linki

• Watkins, CJCH (1989). Uczenie się z opóźnionych nagród. Praca doktorska, Uniwersytet Cambridge, Cambridge, Anglia.
• Strehl, Li, Wiewiora, Langford, Littman (2006). Nauka ze wzmacnianiem bez modelu PAC
• Nauka przez wzmacnianie: wprowadzenie autorstwa Richarda Suttona i Andrew S. Barto, podręcznik online. Zobacz "6.5 Q-Learning: Kontrola TD poza zasadami" .
• Piqle: ogólna platforma Java do uczenia się przez wzmacnianie
• Reinforcement Learning Maze , pokaz prowadzenia mrówki przez labirynt za pomocą Q- learningu
• Q- learningowa praca Geralda Tesauro