L’apprentissage par renforcement et le Q-learning

Les processus de décision markoviens ont résolu le problème de planification : étant donnés $P(s' \mid s, a)$ et $R(s)$, l’itération sur les valeurs renvoie une politique optimale. Mais un agent lâché dans un environnement inconnu n’a ni l’un ni l’autre. Il ne sait pas ce que font ses actions, ni où sont les récompenses. Il doit le découvrir en agissant.

C’est le problème de l’apprentissage par renforcement, et il est bien plus proche de la situation où se trouve tout agent réel.

A. Apprendre de la différence entre estimations successives

Supposons que l’agent suive une politique $\pi$ dans le monde $4 \times 3$ de Russell & Norvig, où chaque pas coûte $R = -0.04$ et où les récompenses ne sont pas actualisées ($\gamma = 1$), et croie actuellement $U^{\pi}(1,3) = 0.84$ et $U^{\pi}(2,3) = 0.92$. Il observe alors une transition de $(1,3)$ vers $(2,3)$. Si cette transition se produisait à chaque fois, les deux utilités devraient satisfaire la relation de Bellman pour $\pi$, $U^{\pi}(1,3) = -0.04 + 0.92 = 0.88$ - et elles ne la satisfont pas tout à fait. L’estimation en $(1,3)$ semble un peu basse. (Avec le $\gamma = 0.9$ utilisé plus loin dans cet article, la cible vaudrait $0.788$, et la même estimation semblerait haute.)

Le remède est de la pousser vers la cohérence. En observant une transition $s \to s'$ :

$$U^{\pi}(s) \leftarrow U^{\pi}(s) + \alpha\big(R(s) + \gamma\, U^{\pi}(s') - U^{\pi}(s)\big),$$

où $\alpha$ est un taux d’apprentissage. C’est la mise à jour par différence temporelle (TD), ainsi nommée parce qu’elle est pilotée par la différence entre les estimations d’utilité à des pas de temps successifs.

La quantité entre parenthèses est l’erreur TD : ce que nous venons d’observer, $R(s) + \gamma U(s')$, moins ce que nous croyions, $U(s)$. Une erreur nulle signifie que nos estimations sont localement cohérentes et rien ne change. Toutes les méthodes TD fonctionnent ainsi - en ajustant les estimations vers l’équilibre qui tient quand elles sont correctes.

Pourquoi c’est remarquable. La mise à jour ne mentionne aucune probabilité. L’agent n’estime jamais $P(s' \mid s, a)$. Pourtant, parce que les transitions sont échantillonnées depuis le vrai modèle, les transitions fréquentes déclenchent la mise à jour proportionnellement souvent, et le moyennage se fait implicitement. Le modèle n’est jamais appris, seulement obéi.

B. Des utilités aux valeurs d’action

Le TD tel qu’écrit apprend $U^{\pi}(s)$ - à quel point un état est bon. Ce n’est pas directement actionnable : pour choisir, un agent doit savoir à quel point chaque action disponible est bonne, et convertir $U$ en un choix suppose de savoir où mènent les actions, c’est-à-dire précisément le modèle dont nous ne disposons pas.

Apprenons donc plutôt des valeurs d’action. Définissons $Q(s, a)$ comme l’utilité espérée de prendre l’action $a$ dans l’état $s$. Les deux sont reliées par

$$U(s) = \max_{a} Q(s, a),$$

et un agent détenant $Q$ peut agir sans aucun modèle : consulter la ligne de l’état courant et prendre la plus grande entrée.

C. La mise à jour du Q-learning

$$Q(s, a) \leftarrow Q(s, a) + \alpha\Big(R(s) + \gamma \max_{a'} Q(s', a') - Q(s, a)\Big)$$

Elle s’applique chaque fois que l’action $a$ est prise en $s$ et mène à $s'$. C’est l’idée TD, l’utilité d’état étant remplacée par la meilleure valeur d’action disponible à l’état suivant.

Le $\max_{a'}$ est le détail crucial. L’agent remonte la valeur de la meilleure action en $s'$, indépendamment de ce qu’il fait ensuite. Cela rend le Q-learning hors politique : il apprend la politique optimale tout en se comportant selon une autre, plus exploratoire.

Son proche parent SARSA - pour state, action, reward, state, action - utilise à la place l’action $a'$ réellement prise :

$$Q(s, a) \leftarrow Q(s, a) + \alpha\big(R(s) + \gamma\, Q(s', a') - Q(s, a)\big).$$

Cela rend SARSA sur politique : il apprend la valeur de la politique suivie, exploration comprise. Pour un agent purement glouton les deux coïncident. Dès qu’il y a exploration ils diffèrent, et la différence compte : le Q-learning peut apprendre un bon comportement même guidé par une politique d’exploration aléatoire ou hostile, tandis que SARSA est plus réaliste quand la politique échappe en partie au contrôle de l’agent - par exemple quand d’autres agents partagent l’environnement.

D. La mécanique, pas à pas

Reprenons le monde de l’article précédent : états non terminaux $s_1, s_2$ avec $R(s) = -0.04$, terminaux GOAL $(+1)$ et PIT $(-1)$, et $\gamma = 0.9$. Toutes les valeurs $Q$ partent de zéro. Prenons $\alpha = 0.5$.

Supposons que l’agent fasse $s_1 \to s_2 \to$ GOAL, deux fois.

Mise à jour 1, $(s_1, \text{Right}) \to s_2$. Tous les $Q(s_2, \cdot)$ valent encore $0$ :

$$Q(s_1, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 0 - 0\big) = -0.02 .$$

Mise à jour 2, $(s_2, \text{Right}) \to$ GOAL, dont la valeur est $+1$ :

$$Q(s_2, \text{Right}) \leftarrow 0 + 0.5\big(-0.04 + 0.9 \times 1 - 0\big) = 0.5 \times 0.86 = 0.43 .$$

Mise à jour 3, $(s_1, \text{Right}) \to s_2$ à nouveau - mais $s_2$ a désormais une valeur :

$$Q(s_1, \text{Right}) \leftarrow -0.02 + 0.5\big(-0.04 + 0.9 \times 0.43 - (-0.02)\big) = 0.1635 .$$

Mise à jour 4, $(s_2, \text{Right}) \to$ GOAL : $0.43 + 0.5(0.86 - 0.43) = 0.645$.

Remarquez comment la valeur se propage à rebours : rien d’utile n’atteint $s_1$ avant que $s_2$ ait appris quelque chose.

Cette séquence particulière converge vers le mauvais nombre, et c’est tout l’intérêt. Les deux épisodes ci-dessus ont été choisis à la main pour atteindre GOAL. Ne répéter qu’eux pousse $Q(s_2, \text{Right})$ vers $-0.04 + 0.9(1) = 0.86$ - la valeur d’un Right qui réussit toujours. Mais Right n’atteint GOAL que 80 % du temps ; les 20 % restants il tombe dans PIT. La valeur correcte est $-0.04 + 0.9\,(0.8 \times 1 + 0.2 \times (-1)) = 0.5$. Le Q-learning y parvient uniquement parce que l’expérience réelle échantillonne les deux issues dans la bonne proportion. Un échantillon biaisé donne une réponse biaisée.

E. Exploration contre exploitation

Un agent qui prend toujours sa meilleure action courante peut ne jamais en découvrir une meilleure. Un agent qui agit toujours au hasard apprend sur tout et n’exploite rien. C’est le compromis exploration–exploitation.

La réponse praticable la plus simple est l’$\varepsilon$-glouton : agir de façon gloutonne avec probabilité $1 - \varepsilon$, au hasard avec probabilité $\varepsilon$. Pourvu que $\varepsilon$ décroisse avec le temps, l’agent explore assez tôt pour trouver les bonnes actions et exploite assez tard pour accumuler de la récompense. Des schémas plus raffinés utilisent une fonction d’exploration qui gonfle la valeur des paires état–action rarement essayées, ce qui demande de tenir des compteurs de visites.

La figure ci-dessous applique la même mise à jour dans un monde légèrement différent, si bien que ses nombres ne sont pas ceux du tableau : deux états A et B, un terminal valant $+1$ atteint en allant à droite depuis B, et un Right qui échoue 20 % du temps en ramenant l’agent en A plutôt que dans un piège. Elle commence par cinq trajets scriptés qui réussissent tous, dans l’ordre B, B, A, B, A. Parcourez-les et observez l’ordre plutôt que les nombres. A reste exactement à zéro pendant les deux premiers trajets, car aucun ne part de A, et sa première mise à jour trouve alors B déjà à $0.42$. Échantillonnez ensuite l’environnement réel de l’agent. Un régime de trajets toujours réussis converge vers 0,8600 pour B, la valeur d’un monde où aller à droite marche toujours. Seul le dérapage enseigne le contraire.

F. Retrouve-t-il vraiment l’optimum planifié ?

L’article précédent a calculé la réponse exacte en planifiant avec pleine connaissance du modèle : $U(s_1) = 0.3902$ et $U(s_2) = 0.5000$. Un Q-learner ne voit jamais ce modèle. Exécutons-le sur 200 000 épisodes avec $\varepsilon = 0.2$ et un taux d’apprentissage décroissant :

Il affiche :

Prendre $U(s) = \max_a Q(s,a)$ donne $0.3847$ et $0.4926$, contre les $0.3902$ et $0.5000$ planifiés - et la politique gloutonne lue sur ces valeurs est Right dans les deux états, exactement la politique produite par l’itération sur les valeurs. L’agent a retrouvé le comportement optimal sans qu’on lui dise jamais ce que font ses actions.

Le petit écart résiduel est une honnête erreur d’échantillonnage, non un bug : les estimations sont des moyennes sur un nombre fini de transitions échantillonnées, et elles se resserrent lentement à mesure que le taux d’apprentissage décroît. C’est le compromis standard - le Q-learning vous demande bien moins que l’itération sur les valeurs, et le paie en efficacité d’échantillonnage.

G. Les limites

Tout ce qui précède suppose une table $Q$ à une entrée par paire état–action. C’est très bien pour quatre entrées et sans espoir pour les échecs ou pour tout environnement à état continu. Les vrais problèmes exigent de la généralisation : approximer $Q$ par une fonction paramétrée plutôt que l’énumérer, et c’est là que l’apprentissage par renforcement rejoint le reste de l’apprentissage automatique.

Une seconde limite est que les agents Q-learning ne peuvent pas anticiper. Ne sachant pas où mènent les actions, ils ne peuvent pas planifier une séquence comme le fait un agent fondé sur un modèle - ils ne peuvent que comparer les valeurs d’action apprises. L’affranchissement du modèle s’achète au prix de la prévoyance.

À retenir

• L’apprentissage par renforcement abandonne l’hypothèse du PDM selon laquelle le modèle est connu ; l’agent apprend de l’expérience à la place.
• La mise à jour TD pousse les estimations vers la cohérence locale, sans aucune probabilité - l’échantillonnage fournit le moyennage implicitement.
• $Q(s,a)$ rend la sélection d’action indépendante du modèle, avec $U(s) = \max_a Q(s,a)$.
• La règle du Q-learning remonte $\max_{a'} Q(s', a')$, ce qui la rend hors politique ; SARSA remonte l’action réellement prise et est sur politique.
• La valeur se propage à rebours depuis les récompenses, une mise à jour par pas.
• Un échantillon de transitions biaisé donne un $Q$ biaisé ; la correction repose sur le fait d’expérimenter les issues dans leurs vraies proportions.
• Notre apprenant a atteint $0.3847$ et $0.4926$ contre les $0.3902$ et $0.5000$ planifiés, retrouvant la politique optimale sans modèle.
• Le $Q$ tabulaire ne passe pas à l’échelle ; la généralisation est le pont vers le reste de l’apprentissage automatique.

La suite

Le problème d’exploration, l’erreur d’échantillonnage ci-dessus et la question de l’attribution du mérite ont toutes une saveur théorie de l’information. L’entropie et l’information rend précise la notion de « combien d’incertitude reste-t-il ».