Double Q-Learning est une variante de l'algorithme Q-learning en apprentissage par renforcement, conçue pour réduire la surestimation des valeurs d'action qui peut survenir dans le Q-learning standard. Il a été introduit par Hado van Hasselt en 2010. La méthode maintient deux fonctions Q indépendantes et les utilise alternativement lors des mises à jour, ce qui atténue le biais positif qui découle de l'utilisation de la valeur estimée maximale dans l'équation de Bellman. Cela le rend particulièrement utile dans les environnements avec des récompenses bruitées ou stochastiques, où le Q-learning standard peut converger vers des politiques sous-optimales en raison d'estimations de valeurs gonflées.
L'algorithme est sans modèle, ce qui signifie qu'il ne nécessite pas de modèle de l'environnement, et il peut gérer des problèmes avec des transitions et des récompenses stochastiques sans adaptation. Pour tout processus de décision markovien fini, Double Q-Learning, comme le Q-learning, vise à trouver une politique optimale qui maximise la récompense totale attendue sur des étapes successives, étant donné un temps d'exploration infini et une politique partiellement aléatoire. Le nom « Q » fait référence à la fonction de qualité qui calcule la récompense attendue d'une action entreprise dans un état donné.
Surestimation dans le Q-learning
Le Q-learning standard met à jour sa fonction de valeur en utilisant la valeur Q estimée maximale sur toutes les actions possibles dans l'état suivant. Cette opération de maximum introduit un biais positif systématique car le maximum d'estimations bruitées tend à dépasser le vrai maximum. Dans des environnements avec une variance élevée des récompenses ou une approximation de fonction, cette surestimation peut conduire à de mauvaises performances, car l'agent peut sélectionner à plusieurs reprises des actions qui semblent meilleures qu'elles ne le sont réellement. Par exemple, dans un labyrinthe en grille où un agent apprend à atteindre une sortie valant 10 points, le Q-learning pourrait attribuer une valeur plus élevée à se déplacer à droite qu'à gauche si la droite atteint la sortie plus rapidement, mais la surestimation pourrait l'amener à favoriser un chemin sous-optimal si le bruit gonfle la valeur d'une route moins efficace.
Double Q-Learning aborde cela en découplant la sélection de l'action de l'évaluation de sa valeur. Au lieu d'utiliser une seule fonction Q, il maintient deux estimations distinctes, Q_A et Q_B. Lors de chaque mise à jour, une fonction est utilisée pour sélectionner la meilleure action dans l'état suivant, et l'autre est utilisée pour estimer sa valeur. Cela réduit le biais car la sélection et l'évaluation sont basées sur des estimations différentes et indépendantes.
Mécanique de l'algorithme
La règle de mise à jour centrale dans Double Q-Learning implique deux fonctions Q. À chaque pas de temps t, l'agent sélectionne une action A_t, observe une récompense R_{t+1}, et entre dans un nouvel état S_{t+1}. Avec une probabilité égale, l'algorithme met à jour soit Q_A soit Q_B. Par exemple, lors de la mise à jour de Q_A, il utilise Q_B pour déterminer la meilleure action dans l'état suivant, puis utilise Q_A pour évaluer la valeur de cette action. La mise à jour suit une équation de style Bellman, pondérée par un taux d'apprentissage alpha (entre 0 et 1) et un facteur d'actualisation gamma (également entre 0 et 1), qui valorise les récompenses immédiates plus que les futures. Cette mise à jour alternée garantit qu'aucune fonction ne domine, et la surestimation est réduite car l'opération de maximum est appliquée à une fonction tandis que la valeur est lue depuis l'autre.
Applications et extensions
Double Q-Learning a été largement adopté dans l'apprentissage par renforcement profond, où il constitue la base de l'algorithme Double Deep Q-Network (Double DQN), introduit en 2015 par van Hasselt et ses collègues. Double DQN combine l'idée avec des techniques de Deep learning, utilisant des réseaux de neurones pour approximer les fonctions Q, et a montré une stabilité et des performances améliorées dans des tâches telles que le jeu Atari. L'approche est également pertinente pour des domaines plus larges comme intelligence artificielle et apprentissage automatique, où les méthodes basées sur la valeur sont utilisées pour la prise de décision séquentielle. Les chercheurs ont étendu le concept à d'autres contextes, tels que les systèmes multi-agents et les espaces d'action continus, bien que ces extensions nécessitent souvent des modifications supplémentaires.
Relation avec d'autres méthodes
Double Q-Learning fait partie d'une famille d'algorithmes d'apprentissage par renforcement basés sur la valeur qui comprend le Q-learning standard et SARSA. Contrairement à SARSA, qui apprend la valeur de la politique suivie, Double Q-Learning est une méthode hors politique, ce qui signifie qu'il peut apprendre une politique optimale indépendamment des actions de l'agent. Cette propriété le rend plus flexible dans les stratégies d'exploration. Par rapport au Q-learning standard, Double Q-Learning échange un léger coût de calcul supplémentaire (en raison du maintien de deux fonctions) contre une réduction significative du biais, ce qui conduit souvent à une convergence plus rapide vers des politiques optimales en pratique. La technique est également liée aux méthodes d'ensemble, qui moyennent plusieurs estimations pour réduire la variance, bien que Double Q-Learning cible spécifiquement le biais plutôt que la variance.
Limites et considérations
Bien que Double Q-Learning réduise la surestimation, il ne l'élimine pas entièrement, surtout lorsque les deux fonctions Q deviennent corrélées au fil du temps. Dans certains cas, il peut introduire une sous-estimation, ce qui peut ralentir l'apprentissage dans les premières étapes. L'algorithme nécessite également un réglage minutieux des hyperparamètres tels que le taux d'apprentissage et le facteur d'actualisation. Dans l'apprentissage par renforcement profond, l'utilisation de réseaux cibles, comme dans Double DQN, ajoute une complexité supplémentaire mais est souvent nécessaire pour la stabilité. Malgré ces défis, Double Q-Learning reste une technique fondamentale dans le domaine, et ses principes ont influencé de nombreux algorithmes ultérieurs, y compris ceux utilisés dans des systèmes avancés développés dans des institutions comme BAIR (Berkeley AI Research) et MIT CSAIL.
Infobox
- type: concept
- introduced: 2010
- introduced_by: Hado van Hasselt
- related: q-learning
Catégories
- reinforcement-learning
- algorithm
- machine-learning
- value-based-methods