TD — Séance 6 — L’IA qui apprend

Utilité espérée, processus de décision markoviens, Q-learning, descente de gradient

TD de la séance 6 d’Introduction à l’intelligence artificielle : décider et apprendre : utilité, processus de décision markoviens, Q-learning, descente de gradient.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Décider par l’utilité espérée et trouver un seuil de décision, écrire les transitions d’un MDP et des rendements actualisés, dérouler l’itération sur les valeurs et extraire une politique, appliquer la règle du Q-learning, dérouler une descente de gradient et choisir son taux d’apprentissage. Durée : une séance de TD.

NoteConventions

Dans les grilles, une case est notée (ligne, colonne), la ligne 0 en haut. L’action voulue réussit avec la probabilité indiquée ; sinon l’agent glisse perpendiculairement, à gauche ou à droite de sa direction, avec des probabilités égales ; un mouvement vers un bord ou un obstacle laisse l’agent sur place. La récompense est versée à l’arrivée dans une case ; un état terminal arrête l’épisode et vaut 0. \(V_0=0\) et \(Q=0\) au départ. Les valeurs sont données avec quatre décimales.

Exercice 1 : les semis de Kaffrine

À Kaffrine, un agriculteur doit décider, au début de l’hivernage, de semer de l’arachide maintenant, d’attendre une semaine, ou de semer du mil maintenant. Les pluies peuvent être installées (probabilité \(p=0{,}6\) selon son expérience) ou n’être qu’un faux départ. Ses gains, en centaines de milliers de francs CFA, sont les suivants : arachide maintenant, 8 si les pluies sont installées et \(-4\) en cas de faux départ ; attendre, 5 et 3 ; mil maintenant, 6 et 2.

  1. Remplir le tableau : utilité espérée de chaque action pour \(p=0{,}6\), puis comme fonction de \(p\). Quelle action le MEU choisit-il ?
  2. Calculer les seuils de \(p\) entre les actions, et donner l’action optimale selon la valeur de \(p\).
  3. Une prévision météorologique annonce des pluies installées avec la probabilité 0,8 quand elles le sont, et avec la probabilité 0,3 en cas de faux départ. Calculer la probabilité d’une annonce favorable, puis \(p\) après une annonce favorable et après une annonce défavorable. Quelle décision prendre dans chaque cas ?
  4. Quelle utilité espérée l’agriculteur obtient-il s’il écoute la prévision avant de décider ? Combien la prévision vaut-elle pour lui ?
action pluies installées faux départ \(EU\) (\(p=0{,}6\)) \(EU\) en fonction de \(p\)
arachide maintenant
attendre une semaine
mil maintenant

Exercice 2 : le port de Joal

Une pirogue manœuvre dans le port de Joal, une grille de \(3\times3\) cases dont la case centrale \((1,1)\) est un rocher infranchissable. L’action voulue réussit avec la probabilité 0,7 ; la pirogue dérive à gauche ou à droite de sa direction avec la probabilité 0,15 chacune.

  1. Pour chaque couple (état, action) du tableau, donner les états d’arrivée possibles et leurs probabilités, en regroupant les issues qui mènent au même état, puis vérifier que la somme vaut 1.
  2. Le pêcheur décrit l’état par la seule case de la pirogue. Quand le vent tourne en cours de journée et change les dérives, cet état vérifie-t-il encore la propriété de Markov ? Que proposer ?
  3. Deux manœuvres sont possibles : A rapporte 10 au quatrième pas (récompenses 0, 0, 0, 10) ; B rapporte 2 au premier pas, puis l’épisode s’arrête. Calculer le rendement actualisé de chaque manœuvre pour \(\gamma=0{,}5\) et \(\gamma=0{,}9\), puis la valeur de \(\gamma\) pour laquelle elles s’équilibrent.
  4. Donner la borne \(R_{\max}/(1-\gamma)\) du rendement pour \(R_{\max}=10\) et les deux valeurs de \(\gamma\).
\((s,a)\) états d’arrivée et probabilités somme
\((0, 0)\), bas
\((1, 0)\), droite
\((2, 1)\), haut
\((0, 2)\), droite

Exercice 3 : Awa, livreuse à Thiès

Awa livre à moto dans un quartier de Thiès représenté par une grille de trois lignes et deux colonnes. Le marché M, en \((0,1)\), rapporte \(+1\) ; le chantier H, en \((2,1)\), coûte \(-1\) ; tous deux sont terminaux. Chaque arrivée dans une case non terminale (a, b, c, d) coûte \(-0{,}1\) (carburant). L’action voulue réussit avec la probabilité 0,8, avec 0,1 de glissade de chaque côté ; \(\gamma=0{,}9\).

  1. Écrire \(Q(c,\text{haut})\) et \(Q(d,\text{droite})\) en fonction de \(V\).
  2. Calculer \(V_1\), \(V_2\) et \(V_3\) pour les quatre cases, en donnant pour chaque case la valeur des quatre actions. Remplir le tableau.
  3. À quelle itération la case d reçoit-elle une valeur positive ? Expliquer pourquoi elle est négative avant.
  4. L’itération converge vers \(V^*(a)=V^*(c)=0{,}9280\), \(V^*(b)=0{,}7161\), \(V^*(d)=0{,}3578\). Extraire la politique optimale en calculant les valeurs des actions dans chaque case. Pourquoi a et c ont-elles la même valeur ?
  5. Le coût par pas passe à \(-2\) (embouteillage). Sans calcul complet, prévoir ce que fait la case d, puis le vérifier par une itération de Bellman à partir des valeurs optimales \(V^*(a)=V^*(c)=0{,}2482\), \(V^*(b)=-1{,}9349\), \(V^*(d)=-1{,}5100\).
\(k\) \(V_k(a)\) \(V_k(b)\) \(V_k(c)\) \(V_k(d)\)
1
2
3

Exercice 4 : le Q-learning d’Awa

Awa ne connaît pas les probabilités de glissade ; elle apprend dans le même quartier, avec \(\alpha=0{,}4\) et \(\gamma=0{,}9\). Elle vit quatre épisodes : (1) \((d,\text{haut},-0{,}1,b)\), \((b,\text{haut},-0{,}1,a)\), \((a,\text{droite},1,M)\) ; (2) \((b,\text{droite},-0{,}1,c)\), \((c,\text{haut},1,M)\) ; (3) \((d,\text{droite},-1,H)\) ; (4) \((d,\text{haut},-0{,}1,b)\), \((b,\text{droite},-0{,}1,c)\), \((c,\text{haut},1,M)\).

  1. Appliquer la règle du Q-learning à chaque transition, dans l’ordre, et remplir le tableau.
  2. Donner la table \(Q\) finale des cases a, b, c, d, puis l’action gloutonne de chaque case. Que se passe-t-il en d ?
  3. Comparer avec la politique optimale de l’exercice 3, et expliquer les écarts.
  4. Avec une stratégie \(\varepsilon\)-gloutonne, \(\varepsilon=0{,}3\) et quatre actions, quelle est la probabilité de jouer l’action gloutonne en b ?
transition \(\max_bQ(s',b)\) cible \(Q(s,a)\) avant \(Q(s,a)\) après
1 : \((d,\text{haut},-0{,}1,b)\)
2 : \((b,\text{haut},-0{,}1,a)\)
3 : \((a,\text{droite},1,M)\)
4 : \((b,\text{droite},-0{,}1,c)\)
5 : \((c,\text{haut},1,M)\)
6 : \((d,\text{droite},-1,H)\)
7 : \((d,\text{haut},-0{,}1,b)\)
8 : \((b,\text{droite},-0{,}1,c)\)
9 : \((c,\text{haut},1,M)\)

Exercice 5 : l’eau des rizières de Podor

À Podor, un groupement relève la consommation d’eau de trois parcelles : 1 ha pour 3 milliers de m\(^3\), 2 ha pour 4, 4 ha pour 9. On modélise la consommation par \(w\times\)surface et l’on minimise \(J(w)=\frac13\sum_i(y_i-wx_i)^2\), en partant de \(w_0=0\).

  1. Calculer \(J'(w)\), le minimum \(w^*\) et \(J(w^*)\), en fractions.
  2. Faire trois pas de descente de gradient avec \(\eta=0{,}05\) (remplir le tableau), puis avec \(\eta=0{,}1\) et avec \(\eta=0{,}15\). Décrire le comportement de chaque descente.
  3. Écrire \(w_{k+1}-w^*\) en fonction de \(w_k-w^*\) et en déduire le taux maximal.
  4. Sur \(J(w_1,w_2)=w_1^2+4w_2^2\), faire deux pas depuis \((2,1)\) avec \(\eta=0{,}2\). Que fait chacune des deux coordonnées ?
\(k\) \(w_{k-1}\) \(J'(w_{k-1})\) \(w_k\) \(J(w_k)\)
1
2
3

Exercice 6 (approfondissement) : le taxi-brousse de Kaolack

Un chauffeur de taxi-brousse est soit en ville (V), soit en brousse (B). En ville, il peut attendre un client (récompense 1, il reste en ville) ou partir vers la brousse (récompense 0 ; il arrive en brousse avec la probabilité 0,9 et reste en ville avec 0,1). En brousse, il peut travailler (récompense 2 ; il reste en brousse avec 0,8 et rentre en ville avec 0,2) ou rentrer (récompense 0,5 ; il arrive en ville). On note \(R(s,a)\) la récompense de l’action \(a\) dans l’état \(s\) : \(R(V,\text{attendre})=1\), \(R(V,\text{partir})=0\), \(R(B,\text{travailler})=2\), \(R(B,\text{rentrer})=0{,}5\). L’horizon est infini, \(\gamma=0{,}9\), et il n’y a pas d’état terminal.

L’itération sur les politiques alterne deux étapes : évaluer la politique courante \(\pi\) en résolvant le système linéaire \(V^\pi(s)=R(s,\pi(s))+\gamma\sum_{s'}P(s'\mid s,\pi(s))\,V^\pi(s')\) ; puis l’améliorer en choisissant dans chaque état l’action de plus grande valeur \(Q(s,a)\) calculée avec \(V^\pi\). Elle s’arrête quand la politique ne change plus.

  1. Évaluer \(\pi_0=(\text{attendre},\text{rentrer})\), puis l’améliorer.
  2. Évaluer et améliorer la nouvelle politique, et continuer jusqu’à stabilité. Remplir le tableau.
  3. Vérifier que la politique finale satisfait l’équation de Bellman avec le \(\max\). Interpréter la décision en ville.
  4. L’itération sur les valeurs, sur ce MDP, demande 93 itérations pour un écart inférieur à 0,0001. Comparer le travail des deux méthodes.
\(n\) politique \(\pi_n\) \(V^{\pi_n}(V)\) \(V^{\pi_n}(B)\) politique améliorée
0
1
2

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet