Q-learning
Q-learning est un algorithme fondamental d’apprentissage par renforcement, une branche de l’intelligence artificielle. Il s’agit d’une méthode sans modèle (model-free) et hors politique (off-policy) utilisée pour permettre à un agent d’apprendre une stratégie optimale d’actions dans un environnement donné, dans le but de maximiser une récompense cumulative sur le long terme. L’algorithme apprend la valeur de chaque action possible dans chaque état de l’environnement, sans nécessiter une connaissance préalable des règles ou de la dynamique de cet environnement.
Les concepts fondamentaux du Q-learning reposent sur le cadre de l’apprentissage par renforcement. Un agent interagit avec un environnement en passant d’un état à un autre. Dans chaque état, l’agent choisit une action. Cette action provoque une transition vers un nouvel état et l’agent reçoit une récompense (positive ou négative) de l’environnement. L’objectif de l’agent est d’apprendre une politique, c’est-à-dire une règle qui spécifie quelle action choisir dans chaque état pour maximiser la somme des récompenses futures (souvent actualisées). Le cœur du Q-learning est la fonction de valeur action, notée Q(s, a). Cette fonction représente la qualité attendue (la somme actualisée des récompenses futures) de prendre l’action ‘a’ dans l’état ‘s’, puis de suivre la politique optimale par la suite. L’algorithme met itérativement à jour les estimations de ces Q-valeurs en utilisant l’expérience acquise par l’agent.
La règle de mise à jour centrale du Q-learning est dérivée des équations de Bellman et s’effectue après chaque transition (s, a, r, s’). Elle est donnée par : Q(s, a) ← Q(s, a) + α [r + γ max_a’ Q(s’, a’) – Q(s, a)]. Ici, α est le taux d’apprentissage (learning rate), qui détermine dans quelle mesure les nouvelles informations supplantent les anciennes. γ est le facteur d’actualisation (discount factor), compris entre 0 et 1, qui pondère l’importance des récompenses futures par rapport aux récompenses immédiates. ‘r’ est la récompense reçue après avoir pris l’action ‘a’ dans l’état ‘s’. ‘s » est l’état résultant. Le terme max_a’ Q(s’, a’) représente l’estimation de la meilleure valeur future possible depuis le nouvel état s’, selon les Q-valeurs actuelles. Cette mise à jour rapproche l’estimation Q(s, a) de la valeur cible « r + γ max_a’ Q(s’, a’) », qui combine la récompense immédiate et la meilleure estimation de la valeur future.
Le Q-learning est qualifié de « model-free » car il n’a pas besoin de construire ou de connaître un modèle de l’environnement (c’est-à-dire les probabilités de transition entre états ou la fonction de récompense exacte). Il apprend directement à partir des interactions (expériences) de l’agent. Il est également « off-policy », ce qui signifie qu’il peut apprendre la politique optimale (basée sur l’action maximisant la Q-valeur) même si les actions effectivement prises par l’agent pendant l’apprentissage suivent une politique différente (par exemple, une politique incluant de l’exploration aléatoire). Ceci est crucial car l’agent doit explorer l’environnement (essayer des actions potentiellement sous-optimales) pour découvrir les meilleures stratégies, tout en apprenant sur la base de la politique optimale présumée (exploitation). Le dilemme exploration-exploitation est souvent géré par des stratégies comme epsilon-greedy, où l’agent choisit une action aléatoire avec une probabilité epsilon et l’action jugée la meilleure (selon les Q-valeurs actuelles) avec une probabilité 1-epsilon.
L’importance du Q-learning réside dans son rôle fondateur et son influence majeure sur le développement de l’apprentissage par renforcement. Sa simplicité conceptuelle, combinée à sa capacité à apprendre sans modèle et sa garantie théorique de convergence vers la politique optimale dans les environnements finis et stationnaires (sous réserve de conditions techniques comme une exploration suffisante et un taux d’apprentissage décroissant de manière appropriée), en ont fait un point de départ essentiel pour de nombreux chercheurs et praticiens. Il a démontré la faisabilité de l’apprentissage de stratégies optimales par essais et erreurs et a servi de base à des algorithmes plus avancés capables de traiter des problèmes plus complexes. Son impact se mesure par son adoption dans l’enseignement et la recherche, ainsi que par son rôle de composant clé dans des systèmes plus sophistiqués.
Les applications pratiques du Q-learning, en particulier dans sa forme tabulaire de base, sont souvent limitées aux problèmes avec des espaces d’états et d’actions relativement petits et discrets. Néanmoins, il a été appliqué avec succès dans divers domaines. En robotique, il peut être utilisé pour apprendre des tâches de navigation simples, comme un robot apprenant à trouver la sortie d’un labyrinthe en attribuant des valeurs aux mouvements possibles (avancer, tourner) dans chaque case (état). Dans les jeux, des agents peuvent apprendre à jouer à des jeux simples en maximisant leur score. Par exemple, un agent Pac-Man pourrait apprendre à choisir ses déplacements pour manger des gommes tout en évitant les fantômes. D’autres applications incluent l’optimisation de la gestion des stocks, le contrôle de feux de circulation, ou des systèmes de recommandation simples qui s’adaptent aux préférences de l’utilisateur au fil du temps. Les extensions modernes comme le Deep Q-learning ont considérablement élargi le champ d’application à des problèmes beaucoup plus vastes.
Il existe plusieurs nuances et variations importantes du Q-learning. La forme la plus basique est le Q-learning tabulaire, où les Q-valeurs sont stockées explicitement dans une table (ou un dictionnaire) indexée par les paires état-action. Cette approche devient rapidement irréalisable lorsque le nombre d’états ou d’actions est grand (malédiction de la dimensionnalité) ou lorsque les états/actions sont continus. Pour surmonter cette limitation, des techniques d’approximation de fonction sont utilisées. La variation la plus célèbre est le Deep Q-Network (DQN), qui utilise un réseau de neurones profond pour approximer la fonction Q(s, a). DQN a permis des succès spectaculaires, notamment dans l’apprentissage de jeux vidéo Atari directement à partir des pixels de l’écran. D’autres variations incluent le Double Q-learning, conçu pour atténuer le problème de la surestimation systématique des Q-valeurs qui peut survenir dans le Q-learning standard, en utilisant deux estimateurs de Q-valeurs distincts pour la sélection et l’évaluation de l’action dans la mise à jour. D’autres raffinements visent à améliorer la vitesse de convergence ou la stabilité.
Le Q-learning est étroitement lié à plusieurs concepts clés de l’apprentissage par renforcement et de la théorie de la décision. Il s’inscrit dans le cadre des Processus de Décision Markoviens (MDP), qui formalisent les problèmes de prise de décision séquentielle. Il est basé sur les équations de Bellman, qui expriment la relation récursive entre la valeur d’un état (ou d’une paire état-action) et les valeurs des états successeurs. C’est un exemple d’algorithme d’apprentissage par différence temporelle (Temporal Difference, TD), car il met à jour ses estimations en se basant sur d’autres estimations apprises (le terme Q(s’, a’)). Il se distingue des algorithmes « on-policy » comme SARSA (State-Action-Reward-State-Action), qui apprend la valeur de la politique effectivement suivie par l’agent, y compris ses actions d’exploration. Il s’oppose également aux méthodes « model-based » qui tentent d’abord d’apprendre un modèle de l’environnement pour ensuite planifier les actions optimales. Il est fondamentalement différent des paradigmes d’apprentissage supervisé (apprentissage à partir de données étiquetées) et non supervisé (découverte de structures dans des données non étiquetées).
Le Q-learning a été introduit par Christopher Watkins dans sa thèse de doctorat à l’Université de Cambridge en 1989. Il représentait une avancée significative car il combinait des idées de la programmation dynamique (via les équations de Bellman) avec l’apprentissage par différence temporelle, tout en étant « model-free » et « off-policy ». L’article influent « Q-learning » co-écrit par Watkins et Peter Dayan en 1992 a solidifié ses fondements théoriques et sa popularité. Pendant de nombreuses années, il est resté un algorithme central dans la recherche en RL. L’évolution majeure suivante est survenue avec l’avènement du deep learning, menant au développement des Deep Q-Networks (DQN) par l’équipe de DeepMind (publié initialement en 2013, puis dans Nature en 2015). DQN a démontré la capacité du Q-learning combiné aux réseaux neuronaux profonds à maîtriser des tâches complexes à haute dimensionnalité, relançant l’intérêt pour l’apprentissage par renforcement.
Le Q-learning présente plusieurs avantages notables. Sa relative simplicité conceptuelle (surtout dans sa forme tabulaire) le rend accessible pour l’apprentissage des bases du RL. Sa nature « model-free » le rend applicable même lorsque la dynamique de l’environnement est inconnue ou trop complexe à modéliser. Sa propriété « off-policy » offre une flexibilité dans la stratégie d’exploration et permet potentiellement d’apprendre à partir de données d’expérience collectées antérieurement ou par d’autres agents. Enfin, sa convergence vers l’optimum est théoriquement garantie pour les MDP finis sous certaines conditions.
Cependant, le Q-learning a aussi des inconvénients et des limitations significatifs. La « malédiction de la dimensionnalité » rend la version tabulaire impraticable pour les problèmes avec de grands espaces d’états ou d’actions. Même avec un nombre modéré d’états/actions, la convergence peut être très lente, nécessitant un grand nombre d’interactions avec l’environnement. La gestion du compromis exploration-exploitation est délicate et le choix des paramètres (taux d’apprentissage, facteur d’actualisation, stratégie d’exploration) peut fortement influencer les performances. Le Q-learning standard est connu pour surestimer les Q-valeurs, ce qui peut nuire à la politique apprise. Enfin, lorsqu’il est combiné avec une approximation de fonction non linéaire (comme les réseaux de neurones), les garanties de convergence sont perdues et l’apprentissage peut devenir instable, nécessitant des techniques de stabilisation supplémentaires (comme celles utilisées dans DQN : experience replay et target networks). La nécessité de discrétiser les espaces continus pour la version tabulaire est également une limitation importante.