¿Por qué el Q-learning regular (y DQN) sobreestima los valores de Q?
La motivación para la introducción de doble DQN (y doble Q-learning) es que el Q-learning (o DQN) regular puede sobreestimar el valor Q, pero ¿hay una breve explicación de por qué se sobreestima?
Respuestas
La sobreestimación proviene de la inicialización aleatoria de sus estimaciones de valor Q. Obviamente, estos no serán perfectos (si lo fueran, ¡no necesitaríamos aprender los verdaderos valores Q!). En muchos métodos de aprendizaje por refuerzo basados en valores, como SARSA o Q-learning, los algoritmos implican un$\max$operador en la construcción de la política objetivo. El caso más obvio es, como mencionaste, Q-learning. La actualización de aprendizaje es$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$La función Q para la tupla de acción de estado que estamos considerando se desplaza hacia la función Q máxima en el siguiente estado donde el$\max$ se toma con respecto a las acciones.
Ahora, como se mencionó, nuestras estimaciones iniciales de los valores Q se inicializan aleatoriamente. Esto, naturalmente, conduce a valores incorrectos. La consecuencia de esto es que cuando calculamos$\max_aQ(s', a)$podríamos estar eligiendo valores que están muy sobreestimados .
Dado que se garantiza que el Q-learning (en el caso tabular) convergerá (bajo algunas suposiciones leves), la consecuencia principal del sesgo de sobreestimación es que ralentiza gravemente la convergencia. Esto, por supuesto, se puede superar con Double Q-learning.
La respuesta anterior es para el caso tabular de Q-Learning. La idea es la misma para el Deep Q-Learning, excepto que tenga en cuenta que Deep Q-learning no tiene garantías de convergencia (cuando se usa un NN como aproximador de función) y, por lo tanto, el sesgo de sobreestimación es un problema mayor, ya que puede significar los parámetros de la red se atascan en valores subóptimos.
Como alguien preguntó en los comentarios acerca de inicializar siempre los valores para que sean números muy bajos, esto realmente no funcionaría.
Considere el siguiente MDP tomado de Sutton y Barto: Comenzamos en el estado A, desde el cual podemos ir a la derecha con la recompensa 0 que conduce a un estado terminal o ir a la izquierda con la recompensa 0 al estado B. Del estado B podemos tomar, digamos, 100 acciones diferentes, todas las cuales conducen a un estado terminal y tienen una recompensa extraída de una distribución normal con media -0,1 y varianza 1.
Ahora, claramente, la acción óptima del estado A es ir a la derecha. Sin embargo, cuando vamos a la izquierda y tomamos una acción en el estado B, existe una probabilidad de (casi) 0.5 de obtener una recompensa mayor que 0. Ahora, recuerde que el valor Q se desplaza hacia$r(s, a) + \max_a Q(s', a)$; debido a las recompensas estocásticas al hacer la transición fuera del estado B y al hecho de que probablemente veremos una recompensa positiva$\max_a Q(s', a)$ será positivo.
Esto significa que cuando tomamos la acción de la izquierda, el valor Q (Q (A, izquierda)) se desplaza hacia un valor positivo, lo que significa que cuando estamos en el estado A, el valor de moverse a la izquierda será más alto que moverse a la derecha (lo que gradualmente se desplazará hacia el valor real de 0) y, por lo tanto, al seguir el $\epsilon$-política codiciosa la acción codiciosa será ir a la izquierda cuando en realidad esto es subóptimo.
Ahora, por supuesto, sabemos que los valores Q verdaderos eventualmente convergerán, pero si tenemos, digamos, 100 acciones, entonces probablemente pueda ver que el tiempo que tomarán los valores Q para converger al valor verdadero será potencialmente Pasaría mucho tiempo ya que tendríamos que seguir eligiendo todos los valores sobreestimados hasta que tuviéramos convergencia.