Q-learning est un algorithme d'apprentissage par renforcement sans modèle qui entraîne un agent à attribuer des valeurs à ses actions possibles en fonction de son état actuel, sans nécessiter de modèle de l'environnement. Il peut gérer des problèmes avec des transitions stochastiques et des récompenses sans nécessiter d'adaptations. Pour tout processus de décision markovien fini, Q-learning trouve une politique optimale dans le sens où il maximise la valeur attendue de la récompense totale sur toutes les étapes successives, à partir de l'état actuel, étant donné un temps d'exploration infini et une politique partiellement aléatoire. Le « Q » fait référence à la fonction que l'algorithme calcule : la récompense attendue - c'est-à-dire la qualité - d'une action entreprise dans un état donné.
Dans un exemple simple, un agent dans un labyrinthe en grille apprend à atteindre une sortie valant 10 points. À une jonction, Q-learning pourrait attribuer une valeur plus élevée au déplacement vers la droite qu'à gauche si la droite mène à la sortie plus rapidement, améliorant ce choix en essayant les deux directions au fil du temps. Cela illustre comment l'algorithme équilibre la récompense immédiate avec les résultats à long terme grâce à des mises à jour itératives.
Contexte de l'apprentissage par renforcement
L'apprentissage par renforcement implique un agent, un ensemble d'états \(\mathcal{S}\), et un ensemble \(\mathcal{A}\) d'actions par état. En effectuant une action \(a \in \mathcal{A}\), l'agent passe d'un état à un autre. Exécuter une action dans un état spécifique fournit à l'agent une récompense, un score numérique. L'objectif de l'agent est de maximiser sa récompense totale en ajoutant la récompense maximale atteignable depuis les états futurs à la récompense pour atteindre son état actuel, influençant ainsi l'action actuelle par la récompense future potentielle. Cette récompense potentielle est une somme pondérée des valeurs attendues des récompenses de toutes les étapes futures à partir de l'état actuel.
Comme exemple, considérons monter dans un train, où la récompense est mesurée par le négatif du temps total d'embarquement. Une stratégie consiste à entrer par la porte du train dès qu'elle s'ouvre, minimisant le temps d'attente initial. Si le train est bondé, cependant, l'entrée est lente car les passagers qui descendent se battent pour sortir. Le temps total d'embarquement est alors de 0 seconde d'attente plus 15 secondes de lutte. Le lendemain, par hasard (exploration), l'agent attend et laisse les autres descendre d'abord, résultant en une attente plus longue mais moins de temps de lutte. Dans l'ensemble, ce chemin a une récompense plus élevée puisque le temps total d'embarquement est de 5 secondes d'attente plus 0 seconde de lutte. Grâce à l'exploration, malgré l'action patiente initiale entraînant un coût plus élevé que la stratégie forcée, le coût global est plus faible, révélant une stratégie plus rémunératrice.
Mécanique de l'algorithme
Après \(\Delta t\) étapes dans le futur, l'agent décidera de la prochaine étape. Le poids pour cette étape est calculé comme \(\gamma^{\Delta t}\), où \(\gamma\) (le facteur d'actualisation) est un nombre entre 0 et 1. En supposant \(\gamma < 1\), il valorise les récompenses reçues plus tôt plus que celles reçues plus tard, reflétant la valeur d'un bon départ. \(\gamma\) peut également être interprété comme la probabilité de réussir ou de survivre à chaque étape \(\Delta t\).
L'algorithme a une fonction qui calcule la qualité d'une combinaison état-action : \(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\). Avant que l'apprentissage ne commence, \(Q\) est initialisé à une valeur fixe potentiellement arbitraire choisie par le programmeur. À chaque instant \(t\), l'agent sélectionne une action \(A_t\), observe une récompense \(R_{t+1}\), entre dans un nouvel état \(S_{t+1}\) (qui peut dépendre à la fois de l'état précédent \(S_t\) et de l'action sélectionnée), et \(Q\) est mis à jour. La mise à jour centrale est une équation de Bellman comme une simple mise à jour d'itération de valeur, utilisant la moyenne pondérée de la valeur actuelle et de la nouvelle information :
\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)
où \(\alpha\) est le taux d'apprentissage, contrôlant dans quelle mesure la nouvelle information remplace l'ancienne information.
Exploration et exploitation
L'algorithme repose sur un équilibre entre l'exploration (essayer de nouvelles actions pour découvrir leurs récompenses) et l'exploitation (choisir des actions connues pour produire des récompenses élevées). Une politique partiellement aléatoire, comme epsilon-greedy, sélectionne la meilleure action connue la plupart du temps mais choisit occasionnellement une action aléatoire pour explorer. Cela garantit que l'agent peut améliorer ses estimations au fil du temps, comme vu dans l'exemple de l'embarquement dans le train où l'exploration aléatoire a révélé une meilleure stratégie.
Convergence et optimalité
Pour tout processus de décision markovien fini, Q-learning converge vers une politique optimale qui maximise la récompense totale attendue depuis n'importe quel état de départ, à condition d'un temps d'exploration infini et d'un calendrier de taux d'apprentissage approprié. L'algorithme ne nécessite pas de modèle de la dynamique de transition de l'environnement, ce qui le rend applicable à des problèmes où un tel modèle est inconnu ou complexe. Cette propriété sans modèle le distingue des méthodes basées sur un modèle qui nécessitent des probabilités de transition explicites.
Applications et extensions
Q-learning a été appliqué en robotique, dans les jeux et dans les systèmes autonomes. Sa forme tabulaire fonctionne pour les petits espaces d'états, mais pour les espaces grands ou continus, des extensions comme les réseaux Q profonds combinent Q-learning avec des approximateurs de fonction apprentissage profond et réseau de neurones. Ces avancées ont permis des succès dans des domaines tels que les agents de jeu en intelligence artificielle et les tâches de contrôle en apprentissage automatique. Les principes de l'algorithme sous-tendent également la recherche moderne en apprentissage par renforcement dans des institutions comme BAIR (Berkeley AI Research) et MIT CSAIL.