Apprentissage Q

Une fonction de valeur sur les seuls états n’est pas directement actionnable sans modèle : savoir qu’un état voisin est précieux ne dit pas quelle action y mène, à moins que les probabilités de transition ne soient connues. Une fonction Q contourne cela en attachant des valeurs directement aux paires état-action, si bien que la meilleure action dans un état est simplement celle de plus grande valeur Q.

Russell et Norvig rendent la conséquence explicite : parce qu’un apprenant détenant une fonction Q n’a besoin d’aucun modèle de transition, ni pour apprendre ni pour choisir ses actions, l’apprentissage Q est une méthode sans modèle. Il se relie à la fonction de valeur d’état par l’identité selon laquelle la valeur d’un état est la valeur Q maximale sur les actions qui y sont disponibles.

L’apprentissage procède par mises à jour de différence temporelle. Après avoir joué une action et observé la récompense ainsi que l’état résultant, l’agent forme une cible : la récompense reçue plus la meilleure valeur Q actualisée disponible au nouvel état. L’écart entre cette cible et l’estimation courante est l’erreur de différence temporelle, et l’estimation est déplacée vers la cible d’une fraction fixée par le taux d’apprentissage.

L’algorithme est hors politique, et c’est sa propriété structurelle la plus utile. La mise à jour prend toujours le maximum sur les actions suivantes : elle apprend donc la politique optimale quel que soit le comportement effectif de l’agent pendant la collecte de l’expérience. Cela autorise une exploration délibérée, typiquement ε-gloutonne, prenant la meilleure action connue la plupart du temps et une action au hasard à l’occasion, sans corrompre ce qui est appris.

Dans un monde en grille, l’agent tient une table à une entrée par paire état-action, initialisée arbitrairement. Il agit de façon ε-gloutonne, observe la récompense et la case suivante, et applique la mise à jour. Au début, les estimations n’ont aucun sens et le comportement paraît aléatoire.

L’information se propage à rebours depuis la récompense. La première fois que le but est atteint, la valeur Q de l’action qui y est entrée augmente. Lors d’une visite ultérieure à l’état précédent, la mise à jour voit un maximum désormais plus grand à l’état suivant, si bien que sa propre valeur augmente aussi. La valeur se répand depuis le but à raison d’un pas par visite.

Cette propagation à rebours est aussi la faiblesse pratique de la méthode : avec des récompenses rares, il peut falloir un très grand nombre d’épisodes pour que le signal atteigne les états où se prennent les décisions initiales décisives. Le façonnage des récompenses et les techniques de rejeu existent en grande partie pour l’accélérer.