Bezkresowy wzrost Q-wartości, konsekwencja powtarzającej się nagrody po powtórzeniu tego samego działania w Q-Learning

Question

Jestem w trakcie opracowywania prostej implementacji Q-Learning przez trywialną aplikację, ale jest coś, co mnie zastanawia .

Rozważmy standardowy preparat Q-learning

Q(S, A) = Q(S, A) + alpha * [R + MaxQ(S', A') - Q(S, A)] 

Załóżmy, że to jest stan K że ma dwa możliwe działania, zarówno przyznawanie nasz agent nagradza R i R' przez A i A'.

Jeśli zastosujemy podejście niemal całkowicie chciwe (załóżmy, że przyjmujemy 0,1 epsilon), najpierw wybiorę losowo jedno z działań, na przykład A. Następnym razem prawdopodobnie (90% razy) ponownie wybiorę A, co spowoduje, że Q (K, A) będzie rosnąć i rosnąć, co jest prawdą, że nawet jeśli przypadkowo wypróbuję A', prawdopodobnie jego Nagroda ma taką samą wartość, jak A, dojdziemy do sytuacji, w której praktycznie niemożliwe jest "odzyskanie" naszego pierwszego przypuszczenia podczas pozostałej części nauki.

Chyba tak nie powinno być, w przeciwnym razie agent zasadniczo się nie uczył - wystarczyłby prosty przepis: rób wszystko tak, jak robiłeś to po raz pierwszy.

Czy brakuje mi czegoś? Wiem, że mogę poprawić wartość alfa (ogólnie, zmniejszając ją w czasie), ale to w żaden sposób nie poprawia naszej sytuacji.

Answer 1

Q(K, A) nie tylko rośnie w nieskończoność, ze względu na termin minus Q(S, A). Jest to bardziej widoczne, jeśli przepisać regułę aktualizacji do:

Q(S, A) <-- Q(S, A)(1 - a) + a(R + maxQ(S', A'))

To pokazuje, że Q(K, A) powoli przesuwa się w kierunku jego „rzeczywistej” wartości R + maxQ(S', A'). Q(K, A) tylko się do tego zbliża; nieskończenie. Kiedy przestanie rosnąć (przybliżyło się do rzeczywistej wartości), Q(K, A) dla innych A s może nadrobić zaległości.

W każdym razie, celem epsilon jest kontrolowanie tego, czy chcesz, aby proces uczenia się był bardziej chciwy (heurystyczny) czy eksploracyjny (losowy), więc zwiększ go, jeśli proces uczenia jest zbyt wąski.

Należy również zauważyć, że jednym z formalnych warunków konwergencji QL jest to, że każda para (S, A) odwiedzana jest nieskończoną liczbę razy (parafrazując)! Więc tak, na końcu procesu treningowego chcesz, aby każda para była odwiedzana przyzwoitą ilość razy.

Powodzenia!

Answer 2

Od this wiemy:

Zbieżność Q-learning trzyma przy użyciu dowolnego politykę poszukiwawczą, a jedynie wymaga, aby każda para działania państwa (s,a) jest wykonywany nieskończenie często.

epsilon-greedy policy to równowaga między eksploracją a eksploatacją, która gwarantuje zarówno konwergencję, jak i często dobrą wydajność.Ale w praktycznych problemach często potrzebujemy heurystyki, aby zmienić prędkość nauki alpha, aby zapewnić lepszy zwrot. W przeciwnym razie trudno spełnić wymaganie infinite often.

Podam przykład poniżej. Jest to klasyczny problem, w którym masz siatkę i prawdopodobnie masz inną nagrodę w każdej komórce. Na przykład poniżej pokazano sieć 4x4, w której każda komórka zawiera nagrodę w wysokości 1, z wyjątkiem górnej lewej komórki (masz większą nagrodę o wartości 10). Robot porusza się w siatce. Czynności prawne są przenoszone LEFT, RIGHT, UP i DOWN, ale robot nie może się wyprowadzić z sieci.

Tak więc nasza przestrzeń stanów zawiera 16 odrębnych stanów, co odpowiada 16 komórkom. Dla każdego stanu istnieje różna liczba działań prawnych z powodu ograniczeń granicznych. Naszym celem jest obliczyć optymalną politykę (biorąc pod uwagę dowolny stan s, wyprowadzić optymalną akcję a).

+++++++++++++++++++++ 
+ 10 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 
+ 1 + 1 + 1 + 1 + 
+++++++++++++++++++++ 

Załóżmy używamy epsilon-greedy policy z epsilon=0.1, stała szybkość uczenia alpha=0.1. Zaczynamy od losowej pozycji na siatce. Za każdym razem, gdy docieramy do lewego górnego rogu, ponownie uruchamiamy losową pozycję.

Poniżej znajduje się wynik uruchomienia symulacji 200 000 ruchów. Lewy blok pokazuje wizualnie obecną chciwą politykę w każdej komórce.

• --> ruchu w prawo
• <-- ruchu w lewo
• ^ Poruszanie się
• v Przesuwanie w dół

Więc widzisz ten jest daleki od optymalnej polityki. Oczywiście w optymalnej polityce każda komórka powinna wskazywać w lewo lub w górę, ponieważ mamy znaczącą większą nagrodę na pozycji (0,0).

v v v v |  2  9  5  4 
v v v v |  14  98  75  14 
--> v v <-- | 258 3430 3312 245 
--> --> <-- <-- | 3270 93143 92978 3191 

Prawy blok pokazuje, ile razy odwiedzamy dotychczasową komórkę. Widzisz, że większość odwiedzin spędzamy na dole, ale odwiedzamy najwyższy rząd bardzo rzadko. Właśnie dlatego nie osiągnęliśmy jeszcze optymalnej polityki.

Jeśli zmienimy współczynnik uczenia się na alpha=1/(number of times you visited (s,a) so far), jesteśmy w stanie osiągnąć optymalną politykę (pokazaną poniżej) w ciągu 20 000 kroków. Również liczba odwiedzin każdej komórki jest rozkładana bardziej równomiernie, choć nie jest idealna.

--> <-- <-- <-- |  34 7997 7697 294 
^^^<-- | 731 898 524 132 
^^^^ | 709 176  88  94 
^^^^ | 245 256  96  77 

Dla większego problemu z większą liczbą państw, na przykład, kratki 10x10, uważam, że lepiej jest użyć większych epsilon. Na przykład poniżej jest wynik symulacji po 80 000 ruchów na siatce 10x10 z epsilon=0.5. Jest niemal optymalny, z wyjątkiem prawego dolnego rogu. Istnieje również idea o używaniu symulowanego wyżarzania, aby poprawić współczynnik konwergencji Q-learning.

v <-- <-- <-- <-- <-- <-- <-- <-- <-- |  19 2500 1464 716 386 274 216 159 121  71 
^ <-- <-- <-- <-- v <-- <-- <-- <-- | 9617 11914 3665 1071 580 410 319 225 207 131 
^ ^^<-- <-- <-- <-- v <-- <-- | 5355 5716 2662 1675 1465 611 302 183 162 101 
^ ^^^^<-- <-- <-- <-- <-- | 1604 1887 1192 621 1056 882 693 403 206 100 
^ ^^^^^^<-- <-- <-- | 639 735 731 333 412 399 480 294 172 114 
^ ^^<--^^^<-- <--^ | 373 496 640 454 272 266 415 219 107  98 
^ ^^^^^^^<--^ | 251 311 402 428 214 161 343 176 114  99 
^ ^^^<-- -->^<-- <-- <-- | 186 185 271 420 365 209 359 200 113  70 
^ ^^^^^^^ v v | 129 204 324 426 434 282 235 131  99  74 
^ ^^^^<--^<-- <-- <-- | 100 356 1020 1233 703 396 301 216 152  78 

BTW, mój kod Python (~ 100 linii) dla problemu zabawka jest here.

Answer 3

Jak wspomniano w jednym z komentarzy, wartość gamma wynosząca mniej niż jeden gwarantuje to, że suma nie będzie dryfować do dodatniej nieskończoności (biorąc pod uwagę, że same nagrody są ograniczone).

Ale może rzeczywiście utknąć na złym wyborem na chwilę. Jest kilka rzeczy, które można zrobić:

Optymistyczne Inicjalizacja: Jeśli zaczniesz wszystkie wartościach Q optymistycznie, a następnie za każdym razem spróbować czegoś nowego dostaniesz „rozczarowanie” tak, że następnym razem, gdy będzie chcesz spróbować czegoś innego. To trwa, dopóki nie będziesz miał realistycznego poczucia wartości każdego działania.

Praca z funkcjami zaletę: w przypadku, gdy każde działanie jest dobre, ale niektóre są lepsze od innych, to jest dobry pomysł, aby korzystać z funkcji przewagi (czyli o ile lepsze działanie to jest z oczekiwanym wynagrodzeniem tego stan), aby zaktualizować parametry. Jest to szczególnie przydatne w przypadku gradientów polityki.