Dlaczego Q-learning nie jest zbieżny podczas korzystania z aproksymacji funkcji?

Tabelaryczny algorytm uczenia Q gwarantuje znalezienie optymalnego $Q$ funkcjonować, $Q^*$, pod warunkiem spełnienia następujących warunków (warunki Robbins-Monro ) dotyczących wskaźnika uczenia się

1. $\sum_{t} \alpha_t(s, a) = \infty$
2. $\sum_{t} \alpha_t^2(s, a) < \infty$

gdzie $\alpha_t(s, a)$ oznacza współczynnik uczenia się używany podczas aktualizacji $Q$ wartość związana ze stanem $s$ i akcja $a$ w czasie $t$, gdzie $0 \leq \alpha_t(s, a) < 1$ zakłada się, że jest prawdą dla wszystkich stanów $s$ i działania $a$.

Najwyraźniej biorąc to pod uwagę $0 \leq \alpha_t(s, a) < 1$, aby te dwa warunki mogły być spełnione, wszystkie pary państwo-działanie muszą być odwiedzane nieskończenie często: jest to również stwierdzone w książce Reinforcement Learning: An Introduction , oprócz faktu, że powinno to być powszechnie znane i jest to uzasadnienie za używanie$\epsilon$-odpowiednia polityka (lub podobna polityka) podczas szkolenia.

Kompletny dowód, który to pokazuje $Q$-learning znajduje optymalne $Q$funkcję można znaleźć w artykule Convergence of Q-learning: A Simple Proof (Francisco S. Melo). Używa pojęć takich jak mapowanie skurczów w celu zdefiniowania optymalnego$Q$funkcja (patrz także Co to jest operator Bellmana w uczeniu się zbrojenia? ), który jest stałym punktem tego operatora skurczu. Używa także twierdzenia (n. 2) dotyczącego losowego procesu, który się zbiega$0$, biorąc pod uwagę kilka założeń. (Dowód może nie być łatwy do naśladowania, jeśli nie jesteś matematykiem).

Jeśli sieć neuronowa jest używana do reprezentowania $Q$ funkcja, wykonaj gwarancje konwergencji z $Q$-czy nadal się uczysz? Dlaczego (lub nie) Q-learning jest zbieżny podczas korzystania z aproksymacji funkcji? Czy istnieje formalny dowód na brak takiej konwergencji$Q$-uczenie przy użyciu aproksymacji funkcji?

Szukam różnych rodzajów odpowiedzi, od tych, które dają tylko intuicję stojącą za brakiem konwergencji $Q$-uczenie się podczas korzystania z aproksymacji funkcji do tych, które zapewniają formalny dowód (lub link do dokumentu z formalnym dowodem).

Oto intuicyjny opis odpowiedzi:

Przybliżenia funkcji można dokonać za pomocą dowolnej parametryzowalnej funkcji. Zastanów się nad problemem$Q(s,a)$ przestrzeń gdzie $s$ to pozytywne realia, $a$ jest $0$ lub $1$, a prawdziwą funkcją Q jest $Q(s, 0) = s^2$, i $Q(s, 1)= 2s^2$dla wszystkich stanów. Jeśli przybliżeniem funkcji jest$Q(s, a) = m*s + n*a + b$, nie ma parametrów, które mogłyby dokładnie reprezentować prawdę $Q$funkcja (staramy się dopasować linię do funkcji kwadratowej). W rezultacie, nawet jeśli wybierzesz dobry współczynnik uczenia się i odwiedzasz wszystkie stany nieskończenie często, twoja funkcja aproksymacji nigdy nie będzie zbieżna z prawdą$Q$ funkcjonować.

A oto trochę więcej szczegółów:

1. Przybliżone sieci neuronowe funkcje. Funkcja może być aproksymowana w większym lub mniejszym stopniu za pomocą mniej lub bardziej złożonych wielomianów w celu jej przybliżenia. Jeśli znasz przybliżenie serii Taylora, ten pomysł powinien wydawać się całkiem naturalny. Jeśli nie, pomyśl o funkcji takiej jak fala sinusoidalna w przedziale [0-$\pi/2$). Możesz to przybliżać (źle) linią prostą. Możesz to lepiej przybliżyć za pomocą krzywej kwadratowej. Zwiększając stopień wielomianu, którego używamy do przybliżania krzywej, możemy uzyskać coś, co bardziej pasuje do krzywej.

2. Sieci neuronowe są uniwersalnymi aproksymatorami funkcji . Oznacza to, że jeśli masz funkcję, możesz także utworzyć sieć neuronową, która jest wystarczająco głęboka lub szeroka, aby mogła przybliżać utworzoną funkcję w dowolnie precyzyjnym stopniu. Jednak żadna wybrana topologia sieci nie będzie mogła się wszystkiego nauczyć funkcji, chyba że będzie nieskończenie szeroka lub nieskończenie głęboka. Jest to analogiczne do tego, że jeśli wybierzesz odpowiednie parametry, linia może zmieścić dowolne dwa punkty, ale nie dowolne 3 punkty. Jeśli wybierzesz sieć o określonej skończonej szerokości lub głębokości, zawsze mogę zbudować funkcję, która potrzebuje kilku dodatkowych neuronów, aby prawidłowo się dopasować.

3. Granice uczenia się obowiązują tylko wtedy, gdy reprezentacja funkcji Q jest dokładna . Aby zobaczyć dlaczego, załóżmy, że wybrałeś przybliżenie swojej funkcji Q interpolacją liniową. Jeśli prawdziwa funkcja może w ogóle przybierać dowolny kształt, to oczywiście błąd w naszej interpolacji może zostać bezgranicznie duży po prostu poprzez zbudowanie funkcji Q-podobnej do XOR, a żadna ilość dodatkowego czasu ani danych nie pozwoli nam zredukować tego błędu . Jeśli używasz aproksymatora funkcji, a prawdziwa funkcja, którą próbujesz dopasować, nie jest czymś, co funkcja może dowolnie dobrze aproksymować, wtedy twój model nie zbiegnie się prawidłowo, nawet przy odpowiednio dobranym tempie uczenia się i wskaźniku eksploracji. Używając terminologii obliczeniowej teorii uczenia się, moglibyśmy powiedzieć, że dowody zbieżności dla uczenia się Q domyślnie przyjęły, że prawdziwa funkcja Q jest elementem przestrzeni hipotez, z której wybierzesz swój model.

O ile mi wiadomo, nadal dość otwartym problemem jest uzyskanie naprawdę jasnego, formalnego zrozumienia dokładnie, dlaczego / kiedy pojawia się brak konwergencji - lub, co gorsza, czasami istnieje niebezpieczeństwo rozbieżności. Zazwyczaj przypisuje się ją „śmiertelnej triadzie” (patrz 11.3 drugiego wydania książki Sutton i Barto), która jest kombinacją:

1. Przybliżenie funkcji, AND
2. Bootstrapping (wykorzystując własne oszacowania wartości do obliczenia naszych celów treningowych, tak jak zrobił to $Q$-learning), AND
3. Szkolenie poza polisą ($Q$- nauka jest rzeczywiście niezgodna z polityką).

To daje nam tylko (być może niewyczerpujący) opis przypadków, w których mamy brak konwergencji i / lub niebezpieczeństwo dywergencji, ale wciąż nie mówi nam, dlaczego tak się dzieje w takich przypadkach.

Odpowiedź Johna już zapewnia intuicję, że częścią problemu jest po prostu to, że użycie aproksymacji funkcji może łatwo prowadzić do sytuacji, w których aproksymator funkcji nie jest wystarczająco silny, aby reprezentować prawdziwą$Q^*$ funkcji, zawsze mogą występować błędy aproksymacji, których nie można się pozbyć bez przełączenia na inny aproksymator funkcji.

Osobiście uważam, że ta intuicja pomaga zrozumieć, dlaczego algorytm nie może zagwarantować zbieżności z optymalnym rozwiązaniem, ale nadal intuicyjnie oczekiwałbym, że może być w stanie „zbiegać się” do jakiegoś „stabilnego” rozwiązania, które jest najlepszym możliwym przybliżeniem ograniczenia związane z wybraną reprezentacją funkcji. Rzeczywiście, to obserwujemy w praktyce, kiedy przechodzimy na szkolenie w zakresie polityki (np. Sarsa), przynajmniej w przypadku aproksymatorów funkcji liniowych.

Moją intuicją w odniesieniu do tego pytania jest na ogół to, że ważnym źródłem problemu jest uogólnienie . W ustawieniu tabelarycznym mamy całkowicie odizolowane wpisy$Q(s, a)$ dla wszystkich $(s, a)$pary. Ilekroć aktualizujemy nasze oszacowanie dla jednego wpisu, pozostawia on wszystkie pozostałe wpisy niezmodyfikowane (przynajmniej początkowo - mogą wystąpić pewne skutki dla innych wpisów w przyszłych aktualizacjach z powodu ładowania początkowego w regule aktualizacji). Zaktualizuj reguły dla algorytmów takich jak$Q$-learning i Sarsa mogą czasami aktualizować się w kierunku „złego” kierunku, jeśli otrzymamy „pecha”, ale w oczekiwaniu na ogół aktualizują się w kierunku prawidłowego „kierunku”. Intuicyjnie oznacza to, że w ustawieniu tabelarycznym, w oczekiwaniu , będziemy powoli, stopniowo naprawiać wszelkie błędy w dowolnych wpisach w oderwaniu, nie powodując szkody dla innych wpisów.

Z aproksymacją funkcji, kiedy aktualizujemy nasze $Q(s, a)$ oszacuj na jeden $(s, a)$para, może potencjalnie wpłynąć również na wszystkie nasze inne szacunki dla wszystkich innych par państwo-akcja. Intuicyjnie oznacza to, że nie mamy już przyjemnej izolacji wpisów, jak w ustawieniu tabelarycznym, a „naprawianie” błędów w jednym wpisie może wiązać się z ryzykiem dodania nowych błędów do innych wpisów. Jednak, podobnie jak odpowiedź Johna, cała ta intuicja dotyczyłaby również algorytmów zgodnych z polityką, więc nadal nie wyjaśnia, co jest specjalnego$Q$-learning (i inne podejścia pozapolityczne).

Bardzo interesującym ostatnim artykułem na ten temat jest pozbawione złudzeń Q-learning i iteracja wartości . Wskazują na problem „złudzeń” w algorytmach, które łączą aproksymację funkcji z regułami aktualizacji obejmującymi a$\max$ operator, taki jak Q-learning (prawdopodobnie nie jest unikalny dla $\max$ operatora, ale prawdopodobnie dotyczy to ogólnie polis?).

Problem jest następujący. Załóżmy, że to uruchomimy$Q$-learning aktualizacja dla pary stan-akcja $(s, a)$:

Oszacowanie wartości $\max_{a'} Q(s', a')$ użyte tutaj opiera się na założeniu, że realizujemy politykę, która jest zachłanna w stosunku do naszych starszych wersji $Q$szacunki dotyczące - być może bardzo długiej - trajektorii. Jak już wspomniano w niektórych poprzednich odpowiedziach, nasz aproksymator funkcji ma ograniczoną pojemność reprezentacyjną, a aktualizacje jednej pary stanów-akcji mogą wpływać na oszacowania wartości dla innych par stanu-akcji. Oznacza to, że po uruchomieniu naszej aktualizacji do$Q(s, a)$, nasz aproksymator funkcji może już nie być w stanie jednocześnie wyrazić polityki prowadzącej do wysokich zwrotów, które nasze$\max_{a'} Q(s', a')$szacunek został oparty na . Autorzy tego artykułu twierdzą, że algorytm jest „urojeniowy”. Wykonuje aktualizację przy założeniu, że w dalszym ciągu może nadal uzyskiwać duże zwroty, ale w rzeczywistości może nie być wystarczająco silny, aby uzyskać te zwroty dzięki nowej wersji parametrów aproksymatora funkcji.

Wreszcie inny (nawet bardziej aktualny) artykuł, który, jak podejrzewam, jest istotny dla tego pytania, to Diagnozowanie wąskich gardeł w algorytmach głębokiego uczenia się , ale niestety nie miałem jeszcze czasu, aby przeczytać go wystarczająco szczegółowo i odpowiednio go streścić.