Skip to content
Retour aux résultats

Q-Learning

Introduite par
Christopher Watkins & Peter Dayan
Année
1992
Type
Model-free reinforcement-learning control algorithm
Famille
Reinforcement learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Le Q-learning, introduit par Christopher Watkins et Peter Dayan en 1992, est un algorithme d'apprentissage par renforcement sans modèle qui apprend la valeur de chaque action dans chaque état — la fonction Q — purement par l'expérience, sans modèle de l'environnement.

Il est hors-politique (off-policy) : il apprend les valeurs d'action optimales tout en suivant une politique de comportement exploratoire, et sous des conditions standard, il converge de manière prouvée vers la politique optimale.

L’intuition derrière la méthode

Un agent apprenant par essais et erreurs doit savoir, pour chaque situation, la valeur de chaque action possible à long terme. Le Q-learning maintient précisément cela : une table (ou fonction) de valeurs Q estimant la récompense future totale d'une action dans un état et d'un comportement optimal par la suite. Chaque fois que l'agent agit, observe une récompense et atteint un nouvel état, il ajuste la valeur Q vers ce qu'il vient d'expérimenter plus le meilleur qu'il pense pouvoir faire ensuite. Crucialement, il se met à jour vers la MEILLEURE action suivante indépendamment de ce qu'il a réellement fait ensuite — ainsi, il peut explorer librement tout en apprenant la stratégie optimale.

Histoire

Christopher Watkins a introduit le Q-learning dans sa thèse de 1989, et Watkins et Dayan (1992) ont fourni la preuve de convergence, l'établissant comme une pierre angulaire de l'apprentissage par renforcement. Il généralise l'apprentissage par différence temporelle au contrôle et sous-tend des jalons ultérieurs — notamment les Deep Q-Networks (Mnih et al., 2015), qui ont combiné le Q-learning avec des réseaux profonds pour jouer à des jeux Atari à partir de pixels. Il est traité de manière canonique dans le manuel de Sutton et Barto et reste un point de départ par défaut pour l'apprentissage par renforcement basé sur la valeur.

Quand l’utiliser

Utilisez le Q-learning pour les problèmes de décision séquentielle formulés comme un processus de décision markovien où vous pouvez échantillonner des transitions et des récompenses mais n'avez pas de modèle (ou un modèle peu fiable) de la dynamique — contrôle, jeux, routage, ordonnancement et systèmes adaptatifs. Le Q-learning tabulaire convient aux espaces d'états-actions petits et discrets et converge vers l'optimum avec une exploration suffisante et une taille de pas décroissante. Pour les espaces grands ou continus, la table est remplacée par un approximateur de fonction (Deep Q-Networks). Il suppose la propriété de Markov et un environnement stationnaire, peut être inefficace en termes d'échantillons, et l'opérateur max induit un biais optimiste (maximisation) traité par des variantes comme le Double Q-learning. Lorsqu'une politique stochastique ou à action continue est nécessaire, les méthodes de gradient de politique sont l'alternative.

Limites et points d’attention

  • La forme tabulaire ne s'adapte pas aux grands espaces d'états/actions ou aux espaces continus.
  • Inefficace en termes d'échantillons ; peut nécessiter de nombreux épisodes pour converger.
  • Biais de maximisation (sur-estimation) dû à l'opérateur max ; atténué par le Double Q-learning.
  • Suppose un processus de décision markovien (stationnaire) ; rencontre des difficultés sous une observabilité partielle ou une dérive.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Sans modèle (Model-free) : ne nécessite pas de modèle de transition/récompense, seulement une expérience échantillonnée.
  • Hors-politique (Off-policy) : apprend la politique optimale tout en explorant avec une autre politique.
  • Converge de manière prouvée vers les valeurs d'action optimales sous des conditions standard.
  • Simple, fondamental, et la base des Deep Q-Networks et de nombreuses extensions.

Applications

  • Jeux et tâches de contrôle simulées.
  • Navigation robotique et contrôle adaptatif.
  • Routage dynamique, ordonnancement et allocation de ressources.
  • Politiques de recommandation et d'interaction adaptative.
  • Une méthode de base basée sur la valeur avant les Deep Q-Networks.

Comment ça marche

Comment ça marche

1

Q(s, a) estime la somme actualisée attendue des récompenses futures en prenant l'action a dans l'état s et en agissant ensuite de manière optimale. Le facteur d'actualisation γ pondère davantage les récompenses proches que celles lointaines. Apprendre Q pour toutes les paires état-action est équivalent à résoudre le problème de contrôle.

Formule
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]
2

Après chaque transition (état s, action a, récompense r, état suivant s'), le Q-learning met à jour Q(s, a) par un pas α vers la cible de différence temporelle r + γ·max sur les actions suivantes de Q(s', a'). Le 'max' est ce qui le rend hors-politique et dirige l'apprentissage vers la valeur optimale, indépendamment de l'action effectivement prise ensuite.

Formule
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]
3

Pour recueillir de l'expérience, l'agent agit selon une politique d'exploration, communément ε-gloutonne : choisir généralement la meilleure action actuelle, mais avec une probabilité ε choisir une action aléatoire. L'exploration garantit que toutes les paires état-action sont essayées, ce que la garantie de convergence exige ; ε diminue généralement avec le temps.

Formule
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}
4

Une fois que Q a convergé vers les valeurs d'action optimales Q*, la politique optimale consiste simplement à prendre, dans chaque état, l'action ayant la valeur Q la plus élevée. En pratique, la politique gloutonne par rapport au Q actuel est extraite à la fin (ou utilisée au déploiement).

Formule
\pi^*(s) = \arg\max_a Q^*(s,a)

Pièges courants

  • Exploration insuffisante (ε trop petit/diminué trop rapidement), laissant l'optimum non appris.
  • Mauvais calendrier de taux d'apprentissage, provoquant une divergence ou un apprentissage péniblement lent.
  • Application du Q-learning tabulaire à de grands espaces au lieu d'un approximateur de fonction.
  • Ignorer le biais de sur-estimation sur des problèmes stochastiques où le Double Q-learning aide.

Questions fréquentes

Que signifie 'hors-politique' (off-policy) en Q-learning ?

Cela signifie que le Q-learning apprend la valeur de la politique optimale pendant que l'agent suit une politique de comportement différente (exploratoire). Les cibles de mise à jour sont r + γ·max Q(s', a') — la meilleure action suivante — et non l'action réellement prise, de sorte que l'exploration ne biaise pas l'optimum appris.

Comment le Q-learning est-il lié aux Deep Q-Networks (DQN) ?

DQN remplace la table Q par un réseau neuronal profond qui approxime Q(s, a), permettant le Q-learning dans des espaces d'états grands ou continus (par exemple, à base de pixels). Il ajoute des astuces de stabilisation — relecture d'expérience et réseau cible — mais la règle d'apprentissage de base est la mise à jour par différence temporelle du Q-learning.

Pourquoi le Q-learning surestime-t-il les valeurs ?

L'opérateur max dans la mise à jour a tendance à sélectionner des estimations trop optimistes, biaisant Q à la hausse, surtout avec des récompenses bruitées. Le Double Q-learning réduit cela en dissociant la sélection d'action de l'évaluation de la valeur à l'aide de deux estimateurs, produisant des politiques moins biaisées et souvent meilleures.

Méthodes associées

Sources

  1. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.

    Ouvrir la référence DOI
    Copié.
  2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.

    ISBN : 978-0-262-03924-6
    Copié.