Perché il regolare Q-learning (e DQN) sovrastima i valori Q?
La motivazione per l'introduzione del doppio DQN (e del doppio Q-learning) è che il normale Q-learning (o DQN) può sovrastimare il valore Q, ma c'è una breve spiegazione del motivo per cui è sovrastimato?
Risposte
La sovrastima deriva dall'inizializzazione casuale delle stime del valore Q. Ovviamente questi non saranno perfetti (se lo fossero non avremmo bisogno di imparare i veri valori Q!). In molti metodi di apprendimento per rinforzo basati sul valore come SARSA o Q-learning gli algoritmi implicano a$\max$operatore nella costruzione del target policy. Il caso più ovvio è, come hai detto, Q-learning. L'aggiornamento dell'apprendimento è$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$La funzione Q per la tupla azione di stato che stiamo considerando è spostata verso la funzione Q massima allo stato successivo in cui la$\max$ è presa rispetto alle azioni.
Ora, come accennato, le nostre stime iniziali dei valori Q vengono inizializzate in modo casuale. Questo porta naturalmente a valori errati. La conseguenza di ciò è che quando calcoliamo$\max_aQ(s', a)$potremmo scegliere valori che sono grossolanamente sovrastimati .
Poiché è garantito che Q-learning (nel caso tabulare) converge (sotto alcune lievi ipotesi), la conseguenza principale del bias di sovrastima è che rallenta gravemente la convergenza. Questo ovviamente può essere superato con il Double Q-learning.
La risposta sopra è per il caso Q-Learning tabulare. L'idea è la stessa per il Deep Q-Learning, tranne per il fatto che il Deep Q-learning non ha garanzie di convergenza (quando si utilizza un NN come approssimatore di funzione) e quindi il bias di sovrastima è più un problema in quanto può significare i parametri della rete si bloccano su valori subottimali.
Come qualcuno ha chiesto nei commenti di inizializzare sempre i valori con numeri molto bassi, questo non funzionerebbe davvero.
Considera il seguente MDP tratto da Sutton e Barto: iniziamo dallo stato A, dal quale possiamo andare a destra con ricompensa 0 che porta a uno stato terminale o andare a sinistra con ricompensa 0 allo stato B. Dallo stato B possiamo prendere, diciamo, 100 azioni diverse, che portano tutte a uno stato terminale e hanno una ricompensa ricavata da una distribuzione Normale con media -0,1 e varianza 1.
Ora, chiaramente l'azione ottimale dallo stato A è andare a destra. Tuttavia, quando andiamo a sinistra e intraprendiamo un'azione nello stato B c'è una probabilità (quasi) 0,5 di ottenere una ricompensa maggiore di 0. Ora, ricorda che il valore Q è spostato verso$r(s, a) + \max_a Q(s', a)$; a causa delle ricompense stocastiche quando si esce dallo stato B e del fatto che probabilmente vedremo una ricompensa positiva il$\max_a Q(s', a)$ sarà positivo.
Ciò significa che quando eseguiamo l'azione a sinistra il valore Q (Q (A, sinistra)) viene spostato verso un valore positivo, il che significa che quando siamo nello stato A il valore dello spostamento a sinistra sarà più alto dello spostamento a destra (che sarà essere spostato gradualmente verso il valore vero di 0) e quindi quando si segue il $\epsilon$-Politica avida l'azione avida sarà quella di andare a sinistra quando in realtà questo non è ottimale.
Ora, ovviamente, sappiamo che i veri valori Q alla fine convergeranno, ma se abbiamo, diciamo, 100 azioni, allora puoi probabilmente vedere che il tempo necessario affinché i valori Q convergano al valore vero sarà potenzialmente sarà molto tempo perché dovremmo continuare a scegliere tutti i valori sovrastimati fino a quando non avremo la convergenza.