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

12

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. tαt(s,a)=
  2. tαt2(s,a)<

gdzie α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α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α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ϵ-odpowiednia polityka (lub podobna polityka) podczas szkolenia.

Kompletny dowód, który to pokazuje Q-learning znajduje optymalne Qfunkcję 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 optymalnegoQfunkcja (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ę zbiega0, 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 konwergencjiQ-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).

nbro
źródło
2
Świetne pytanie!
John Doucette
Książka, do której się odnosiłeś, mówi o tym problemie w rozdziale 11, abyś mógł go przeczytać. Nie sądzę też, aby istniał formalny dowód, dlaczego tak się dzieje, ale istnieje kilka przykładów, które pokazują rozbieżność nawet w prostych środowiskach (np. Tsitsiklis i van Roy).
Brale

Odpowiedzi:

8

Oto intuicyjny opis odpowiedzi:

Przybliżenia funkcji można dokonać za pomocą dowolnej parametryzowalnej funkcji. Zastanów się nad problememQ(s,a) przestrzeń gdzie s to pozytywne realia, a jest 0 lub 1, a prawdziwą funkcją Q jest Q(s,0)=s2, i Q(s,1)=2s2dla wszystkich stanów. Jeśli przybliżeniem funkcji jestQ(s,a)=ms+na+b, nie ma parametrów, które mogłyby dokładnie reprezentować prawdę Qfunkcja (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-π/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.

John Doucette
źródło
Gdzie możemy zobaczyć z dowodu, o którym wspomniałem, że „granice Q-learningu obowiązują tylko wtedy, gdy reprezentacja funkcji Q jest dokładna” jest prawdą?
nbro
Możemy więc aproksymować dowolną (rozsądną) funkcję za pomocą sieci neuronowej (architektury), ale biorąc pod uwagę stałą architekturę sieci neuronowej Z (którą musimy wybrać na początku fazy szkolenia Q-uczenie się), Q-learning może nie zbiegać się przy użyciu tej konkretnej architektury Z, ponieważ Z może nie być wystarczająco ekspresyjny, aby reprezentować Q.
nbro
@nbro Dowód nie mówi tego wprost, ale zakłada dokładną reprezentację funkcji Q (to znaczy, że dokładne wartości są obliczane i przechowywane dla każdej pary stan / akcja). W przypadku nieskończonych przestrzeni stanów jasne jest, że ta dokładna reprezentacja może być nieskończenie duża w najgorszym przypadku (prosty przykład: niech Q (s, a) = sth cyfra pi). Twój drugi komentarz dobrze to podsumowuje. Bardziej formalnie, jeśli prawdziwa hipoteza Q * nie jest elementem przestrzeni H hipotezy, z której wybierasz model, nie możesz zbiegać się do Q *, nawet przy nieskończonym czasie lub danych.
John Doucette
4

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 wpisyQ(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 jakQ-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 specjalnegoQ-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 amax 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 uruchomimyQ-learning aktualizacja dla pary stan-akcja (s,a):

Q(s,a)Q(s,a)+α[maxaQ(s,a)Q(s,a)].

Oszacowanie wartości maxaQ(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 Qszacunki 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 doQ(s,a), nasz aproksymator funkcji może już nie być w stanie jednocześnie wyrazić polityki prowadzącej do wysokich zwrotów, które naszemaxaQ(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ć.

Dennis Soemers
źródło
1
Ale czy wykorzystanie sieci neuronowej nie wynika również z założenia, że ​​niektóre stany są bardzo podobne do każdego z nich? Bardzo podobne stany (np. Kolejne klatki w grze) często mają bardzo podobne (lub takie same) działania optymalne, więc nie jestem pewien, czy wyjaśnienie w pierwszym artykule jest poprawne (powinienem je przeczytać, aby w pełni zrozumieć ich główne punkty).
nbro
1
@ nbro Tak, często uogólnienie jest uważane za zaletę, a nie problem właśnie z tego powodu. Jeśli okaże się to „zamierzone”, może być bardzo potężne i przyspieszyć naukę, ponieważ przenosimy wszystko, czego się uczymy, do podobnych stanów / podobnych działań, zamiast uczenia się dla każdego nieco innego stanu / akcji w izolacji. Ale może również prowadzić do problemów, szczególnie w teorii, ale także w praktyce. Przypuszczam, że to jak „obosieczny miecz”.
Dennis Soemers
1
@DennisSoemers Super interesująca odpowiedź. Non-urojenia punkt Q-uczenia się ma mnóstwo sensu. Znalezienie prawidłowej funkcji Q oznacza znalezienie stałego punktu dla reguły aktualizacji, ale z pewnością wygląda na to, że zbliżenie funkcji może prowadzić do cyklicznych aktualizacji w Q-learningu, jeśli pomyślisz o tym w ten sposób.
John Doucette