Por que o Q-learning regular (e DQN) superestima os valores de Q?
A motivação para a introdução do duplo DQN (e duplo Q-learning) é que o Q-learning regular (ou DQN) pode superestimar o valor de Q, mas há uma breve explicação de por que ele é superestimado?
Respostas
A superestimação vem da inicialização aleatória de suas estimativas de valor Q. Obviamente, eles não serão perfeitos (se fossem, não precisaríamos aprender os verdadeiros valores Q!). Em muitos métodos de aprendizagem por reforço baseados em valor, como SARSA ou Q-learning, os algoritmos envolvem um$\max$operador na construção da política de metas. O caso mais óbvio é, como você mencionou, Q-learning. A atualização de aprendizagem é$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$A função Q para a tupla de ação de estado que estamos considerando é deslocada para a função Q máxima no próximo estado onde o$\max$ é tomada em relação às ações.
Agora, como mencionado, nossas estimativas iniciais dos valores Q são inicializadas aleatoriamente. Isso naturalmente leva a valores incorretos. A consequência disso é que quando calculamos$\max_aQ(s', a)$poderíamos estar escolhendo valores grosseiramente superestimados .
Como o Q-learning (no caso tabular) tem garantia de convergência (sob algumas suposições moderadas), então a principal consequência do viés de superestimação é que diminui severamente a convergência. É claro que isso pode ser superado com o Double Q-learning.
A resposta acima é para o caso tabular do Q-Learning. A ideia é a mesma para o Deep Q-Learning, exceto pelo fato de que Deep Q-learning não tem garantias de convergência (ao usar um NN como o aproximador da função) e, portanto, o viés de superestimação é mais um problema, pois pode significar os parâmetros da rede ficam presos em valores abaixo do ideal.
Como alguém perguntou nos comentários sobre sempre inicializar os valores com números muito baixos, isso realmente não funcionaria.
Considere o seguinte MDP retirado de Sutton e Barto: Começamos no estado A, a partir do qual podemos ir para a direita com a recompensa 0 levando a um estado terminal ou ir para a esquerda com a recompensa 0 para o estado B. Do estado B podemos pegar, digamos, 100 ações diferentes, todas as quais levam a um estado terminal e têm recompensa extraída de uma distribuição Normal com média -0,1 e variância 1.
Agora, claramente a ação ótima do estado A é ir para a direita. No entanto, quando vamos para a esquerda e executamos uma ação no estado B, há uma probabilidade (quase) de 0,5 de obter uma recompensa maior do que 0. Agora, lembre-se de que o valor Q é deslocado para$r(s, a) + \max_a Q(s', a)$; por causa das recompensas estocásticas ao fazer a transição para fora do estado B e o fato de que provavelmente veremos uma recompensa positiva$\max_a Q(s', a)$ será positivo.
Isso significa que quando tomamos a ação para a esquerda, o valor Q (Q (A, esquerda)) é deslocado para um valor positivo, o que significa que quando estamos no estado A, o valor de mover para a esquerda será maior do que mover para a direita (o que será gradualmente sendo deslocado para o valor verdadeiro de 0) e, portanto, ao seguir o $\epsilon$-política gananciosa, a ação gananciosa será ir para a esquerda quando, na verdade, está abaixo do ideal.
Agora, é claro, sabemos que os verdadeiros valores Q irão eventualmente convergir, mas se tivermos, digamos, 100 ações, então você provavelmente pode ver que o tempo que levará para os valores Q convergirem para o valor verdadeiro irá potencialmente muito tempo pois teríamos que continuar escolhendo todos os valores superestimados até que tivéssemos convergência.