Incremento illimitato del Q-Value, conseguenza della ricompensa ricorrente dopo la ripetizione della stessa azione in Q-Learning

Question

Sono in fase di sviluppo di una semplice implementazione Q-Learning su un'applicazione banale, ma c'è qualcosa che mi tiene perplesso .

Consideriamo la formulazione standard di Q-Learning

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

Supponiamo che ci sia questo stato K che ha due azioni possibili, sia la concessione di nostro agente premia R e R' da A e A'.

Se seguiamo un approccio quasi totalmente avido (supponiamo di assumere 0.1 epsilon), in un primo momento selezionerò casualmente una delle azioni, ad esempio A. La prossima volta, probabilmente (il 90% delle volte) scelgo di nuovo A e questo farà sì che Q (K, A) continui a crescere e crescere, pur essendo vero che anche se per caso provo il A', come probabilmente il suo la ricompensa è della stessa grandezza di quella di A, ci troveremo in una situazione in cui è praticamente impossibile "recuperare" dalla nostra prima ipotesi, durante il resto dell'apprendimento.

Immagino che questo non deve essere così, altrimenti l'agente in pratica non imparerebbe - sarebbe solo seguire una semplice ricetta: fare tutto come hai fatto la prima volta.

mi sto perdendo qualcosa? So che posso modificare il valore alfa (generalmente, diminuendolo nel tempo), ma ciò non migliora in alcun modo la nostra situazione.

Answer 1

Q(K, A) non solo continua a crescere all'infinito, a causa del termine minus Q(S, A). Questo è più evidente se si riscrive la regola di aggiornamento per:

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

Questo dimostra che Q(K, A) si muove lentamente verso il suo valore "reale" di R + maxQ(S', A'). Q(K, A) cresce solo per avvicinarsi a quello; non infinitamente. Quando smette di crescere (ha approssimato il suo valore effettivo), lo Q(K, A) per altri A s può raggiungere.

In ogni caso, l'intero punto di epsilon è controllare se si desidera che il processo di apprendimento sia più goloso (euristico) o esplorativo (casuale), quindi aumentarlo se il processo di apprendimento è troppo ristretto.

Si noti inoltre che una delle condizioni formali per la convergenza QL è che ogni coppia di (S, A) viene visitata un numero infinito di volte (parafrasato)! Quindi sì, alla fine del processo di allenamento, vuoi che ogni coppia sia stata visitata una discreta quantità di volte.

Buona fortuna!

Answer 2

Da this, sappiamo:

La convergenza di Q-learning stive utilizzando qualsiasi politica di esplorazione, e richiede solo che ogni azione paio (s,a) stato viene eseguito infinite volte.

Il epsilon-greedy policy è un equilibrio tra esplorazione e sfruttamento, che garantisce sia la convergenza e spesso buone prestazioni.Ma nei problemi pratici, spesso abbiamo bisogno di alcune euristiche per cambiare la velocità di apprendimento alpha per rappresentare un ritorno migliore. In caso contrario, è difficile soddisfare il requisito infinite often.

I un esempio qui sotto. Questo è un problema classico, in cui hai una griglia e hai eventualmente una quantità di ricompensa diversa in ogni cella. Ad esempio, una griglia 4x4 viene mostrata di seguito, in cui ogni cella contiene una ricompensa di 1, ad eccezione della cella in alto a sinistra (hai una ricompensa maggiore con un importo di 10). Un robot si sta muovendo nella griglia. Le azioni legali si stanno muovendo LEFT, RIGHT, UP e DOWN, ma il robot non può spostarsi fuori dalla griglia.

Quindi il nostro spazio di stato contiene 16 stati distinti, che corrispondono alle 16 celle. Per ogni stato, ci sono diversi numeri di azioni legali a causa del vincolo di confine. Il nostro obiettivo è calcolare la politica ottimale (dato qualsiasi stato s, restituire un'azione ottimale a).

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

Supponiamo di utilizzare un epsilon-greedy policy con epsilon=0.1, un tasso di apprendimento costante alpha=0.1. Iniziamo con una posizione casuale sulla griglia. Ogni volta che raggiungiamo l'angolo in alto a sinistra, ricominciamo con una posizione casuale.

Di seguito è riportato un risultato dell'esecuzione di una simulazione di 200.000 movimenti. Il blocco più a sinistra mostra visivamente la politica avida corrente in ogni cella.

• --> lo spostamento a destra
• <-- spostandosi a sinistra
• ^ Salendo
• v Scendendo

Così si vede questo è ben lungi dall'essere una politica ottimale. Ovviamente in una politica ottimale, ogni cella dovrebbe puntare a sinistra o in alto perché abbiamo una ricompensa significativa maggiore nella posizione (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 

Il blocco di destra mostra quante volte visitiamo ogni cella fino a quel momento. Vedete che passiamo la maggior parte delle visite in fondo, ma visitiamo la fila in alto molto rara. Questo è il motivo per cui non abbiamo ancora raggiunto la politica ottimale.

Se cambiamo la velocità di apprendimento da alpha=1/(number of times you visited (s,a) so far), siamo in grado di raggiungere la politica ottimale (mostrata sotto) entro 20.000 passi. Inoltre, il numero di volte che abbiamo visitato ogni cella è distribuito in modo più uniforme, anche se non perfetto.

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

Per un problema più grande con più stati, ad esempio, un 10x10 griglie, trovo che sia meglio usare più grande epsilon. Ad esempio, di seguito è un risultato di una simulazione dopo 80.000 mosse su una griglia 10x10 con epsilon=0.5. È quasi ottimale tranne l'angolo in basso a destra. C'è anche idea sull'utilizzo di Simulation Annealing per aiutare a migliorare il tasso di convergenza del 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, il mio codice Python (~ 100 righe) per il problema giocattolo è here.

Answer 3

Come menzionato in uno dei commenti, il valore gamma inferiore a uno è ciò che garantisce che la somma non passerà all'infinito positivo (dato che i premi stessi sono limitati).

Ma potrebbe davvero rimanere bloccato su una cattiva scelta per un po '. Ci sono alcune cose che si possono fare:

inizializzazione Ottimista: Se si avvia fuori tutti i fattori Q ottimismo, quindi ogni volta che si tenta qualcosa di nuovo si otterrà una "delusione" in modo che la prossima volta che si vuole voglio provare qualcos'altro. Questo continua fino a quando non si ha un senso realistico del valore di ogni azione.

Utilizzo di funzioni di vantaggio: Nel caso in cui ogni azione sia buona, ma alcuni sono migliori di altri, è consigliabile utilizzare la funzione di vantaggio (ovvero quanto è meglio questa azione per il premio previsto di questo stato) per aggiornare i parametri. Questo è particolarmente utile per i gradienti di politica.