Séance 6 — L’IA qui apprend
Décider et apprendre : utilité espérée, processus de décision markoviens, Q-learning, descente de gradient
Amont. L’agent rationnel et sa mesure de performance (Séance 1) ; le Monde de Bouki (Séance 2) ; la recherche d’un chemin et le hill climbing (Séance 3) ; les croyances, le théorème de Bayes et la mise à jour séquentielle (Séance 5).
Aval. Le cours de Machine Learning : apprendre les paramètres d’un modèle à partir de données en minimisant une perte par descente de gradient (régression, classification, réseaux de neurones) ; l’apprentissage par renforcement y prolonge le Q-learning.
- Calculer une utilité espérée, décider par le principe de l’utilité espérée maximale (MEU), trouver un seuil de décision.
- Formuler un processus de décision markovien : états, actions, transitions, récompenses, facteur d’actualisation.
- Définir la fonction de valeur, la fonction \(Q\) et la politique, et lire le rôle du facteur d’actualisation \(\gamma\).
- Écrire l’équation de Bellman, dérouler l’itération sur les valeurs à la main, puis extraire la politique optimale.
- Appliquer la règle du Q-learning à une suite de transitions observées, et choisir entre explorer et exploiter.
- Dérouler une descente de gradient, choisir le taux d’apprentissage, et la relier au hill climbing de la Séance 3.
- Situer ces outils dans le paysage du Machine Learning.
De la croyance à la décision
Ce que la Séance 5 laisse ouvert
La Séance 5 a appris à un agent à raisonner sous incertitude. Au centre de santé de la Médina, le Dr Ndoye a commencé par le prior d’août (paludisme 0,40), puis il a mis à jour sa croyance à chaque observation de Fatou : 0,711 après les frissons, 0,910 après la température, 0,990 après un test de diagnostic rapide (TDR) positif. Ce résultat est une réussite, mais il ne dit rien de ce que le médecin doit faire. Traiter tout de suite, ou renvoyer Fatou chez elle en attendant le TDR ? Et si l’état de la patiente évolue, faut-il réévaluer dans 48 heures, changer de médicament, hospitaliser ? Les outils de la Séance 5 répondent à la question « quelle est la meilleure croyance ? » ; ils ne répondent pas à « quelle est la meilleure action ? », surtout quand les conséquences s’enchaînent dans le temps.
Le même manque apparaît dans le Monde de Bouki. À la fin de la Séance 5, Ousmane sait que Bouki se trouve en \((2,2)\) avec la probabilité 0,876. Il lui reste à choisir un chemin vers l’or, en tenant compte du risque d’être dévoré, de la récompense à atteindre et du coût de chaque pas.
Cette séance suit trois étapes. La décision ponctuelle d’abord : une seule action à choisir, par le principe de l’utilité espérée maximale. La décision séquentielle ensuite : une règle de conduite sur plusieurs pas, par les processus de décision markoviens et l’équation de Bellman. L’apprentissage enfin, quand l’agent ne connaît pas le modèle du monde : le Q-learning, puis la descente de gradient, qui ouvre sur le cours de Machine Learning.
Le fil rouge : Amadou, taxi à Dakar
Amadou est chauffeur de taxi. Chaque matin, il part du Plateau et veut rejoindre la gare TER de Diamniadio, où l’attendent des voyageurs (récompense \(+1\)). En hivernage, deux zones inondées bloquent des quartiers et lui coûtent du temps (récompense \(-1\)). La circulation est imprévisible : quand il choisit une direction, il la suit avec la probabilité 0,8, et il est dévié à gauche ou à droite avec la probabilité 0,1 chacune. Quelle règle de conduite doit-il adopter pour maximiser ses gains en espérance, non pas pour un trajet, mais quel que soit l’endroit où la circulation l’a mené ?
A* (Séance 3) donnerait un chemin, calculé en supposant les rues libres. Ce n’est pas ce dont Amadou a besoin : une seule déviation rend ce chemin inutilisable. Il lui faut une règle qui dise quoi faire depuis chaque quartier.
Les trois piliers d’une décision
Russell et Norvig décrivent un agent qui décide sous incertitude par trois théories assemblées :
| pilier | théorie | question |
|---|---|---|
| 1 | probabilités | qu’est-ce qui est probable ? (Séance 5) |
| 2 | utilité | qu’est-ce qui est désirable ? |
| 3 | décision (MEU) | quelle action prendre ? |
La Séance 5 a construit le premier pilier. Le second manque encore : même avec \(P(\text{palu})=0{,}910\), la décision de traiter dépend de ce que coûte chaque erreur. Deux scénarios le montrent. Dans le scénario A, l’artémisinine est bien tolérée et bon marché : traiter à tort coûte peu, et le médecin traite. Dans le scénario B, le seul médicament disponible provoque des complications graves chez certains patients : la même probabilité peut conduire à ne pas traiter et à attendre un examen de plus. La probabilité est identique, la décision est opposée ; ce qui change, ce sont les conséquences, c’est-à-dire les utilités.
L’utilité
Une fonction d’utilité \(U\) associe à chaque résultat possible \(s\) un nombre réel qui traduit la préférence de l’agent pour ce résultat : \(U(s)>0\) pour un résultat désirable (gain, guérison), \(U(s)<0\) pour un résultat indésirable (perte, complication), \(|U(s)|\) grand pour une conséquence importante. L’utilité place sur une même échelle des conséquences de nature différente : du temps perdu, de l’argent, la santé.
\(P(s\mid a)\) mesure la vraisemblance que l’action \(a\) mène au résultat \(s\) : elle dépend du monde. \(U(s)\) mesure la valeur que l’agent attribue à \(s\) : elle dépend de l’agent et de ses objectifs. Un événement peut être très probable et peu désirable (un embouteillage sur la VDN aux heures de pointe), ou très improbable et très désirable (trouver l’or de Bouki). Une décision rationnelle tient compte des deux à la fois.
Le principe de l’utilité espérée maximale
L’agent choisit l’action qui maximise l’utilité espérée : \[a^*=\arg\max_{a}\;EU(a\mid\mathbf e),\qquad EU(a\mid\mathbf e)=\sum_s P\bigl(\text{Résultat}(a)=s\mid\mathbf e\bigr)\,U(s),\] où \(\mathbf e\) désigne les observations de l’agent et où la somme parcourt tous les résultats possibles.
Chaque morceau de la formule a un rôle. \(\arg\max_a\) désigne l’action qui rend maximale l’expression qui suit. La somme sur \(s\) n’ignore aucun scénario. La probabilité \(P(\text{Résultat}(a)=s\mid\mathbf e)\) est celle que fournit le raisonnement bayésien de la Séance 5. L’utilité \(U(s)\) est la valeur du scénario pour l’agent. Le produit des deux, sommé, est une espérance : la moyenne des utilités pondérée par les probabilités. Le MEU assemble ainsi les deux premiers piliers en un critère unique.
Pour Fatou, le médecin hésite entre deux actions, traiter et renvoyer la patiente chez elle sans traitement. Il fixe ses utilités pour chaque couple (action, réalité) :
| résultat réel | traiter | renvoyer |
|---|---|---|
| Fatou a le paludisme (\(P=0{,}91\)) | \(+10\) (guérison) | \(-100\) (maladie grave) |
| Fatou n’a pas le paludisme (\(P=0{,}09\)) | \(-5\) (traitement inutile) | \(+2\) (traitement évité) |
La pénalité \(-100\) (laisser sans traitement un vrai paludisme) est vingt fois plus grande que l’inconvénient \(-5\) (traiter à tort). Elle traduit une asymétrie clinique réelle : en saison des pluies, rater un paludisme peut être fatal, alors qu’un traitement superflu reste un coût.
Exemple pas à pas : le MEU du Dr Ndoye
Le programme suivant calcule les deux utilités espérées et retient la meilleure action. La boucle extérieure parcourt les actions, la boucle intérieure les deux réalités possibles ; la variable eu accumule les termes \(P(h)\,U(a,h)\) et meilleure garde le couple (action, utilité espérée) le plus élevé rencontré.
P = {"palu": 0.91, "non": 0.09}
U = {("traiter", "palu"): 10,
("traiter", "non"): -5,
("renvoyer", "palu"): -100,
("renvoyer", "non"): 2}
meilleure = None
for a in ("traiter", "renvoyer"):
eu = 0.0
for h in P:
eu = eu + P[h] * U[a, h]
print(a, round(eu, 2))
if meilleure is None or eu > meilleure[1]:
meilleure = (a, eu)
print("decision :", meilleure[0])La table suivante donne chaque passage dans la boucle intérieure, avec les lignes exécutées, le terme ajouté, la valeur de eu et l’effet du test de la ligne 12.
| Tour | Lignes | action, \(h\) | terme \(P(h)\,U(a,h)\) | eu |
décision |
|---|---|---|---|---|---|
| 1 | 10 | traiter, palu | \(0{,}91\times(10)=9{,}1\) | \(9{,}1\) | |
| 2 | 10–13 | traiter, non | \(0{,}09\times(-5)=-0{,}45\) | \(8{,}65\) | meilleure \(=\) traiter |
| 3 | 10 | renvoyer, palu | \(0{,}91\times(-100)=-91\) | \(-91\) | |
| 4 | 10–12 | renvoyer, non | \(0{,}09\times(2)=0{,}18\) | \(-90{,}82\) | inchangée |
Pour « traiter », les deux termes valent \(9{,}10\) et \(-0{,}45\) : \(EU(\text{traiter})=8{,}65\), et cette action devient la meilleure connue (lignes 12 et 13). Pour « renvoyer », le terme du paludisme, \(0{,}91\times(-100)=-91\), écrase le gain de \(0{,}18\) : \(EU(\text{renvoyer})=-90{,}82\), et le test de la ligne 12 échoue. La figure de gauche montre l’état après le second terme de « traiter » (cases examinées en orange, case calculée en rouge), celle de droite l’état final.
La sortie est :
traiter 8.65
renvoyer -90.82
decision : traiterL’écart, \(8{,}65-(-90{,}82)=99{,}47\), vient presque entièrement du scénario « paludisme non traité » : une perte de \(-100\) pondérée par 0,91.
Le seuil de décision
Avec ces utilités, les deux utilités espérées sont des fonctions affines de \(p=P(\text{palu}\mid\mathbf e)\) : \[EU(\text{traiter})=10p-5(1-p)=15p-5,\qquad EU(\text{renvoyer})=-100p+2(1-p)=-102p+2.\] Elles se croisent quand \(15p-5=-102p+2\), soit \(p^*=7/117\approx0{,}060\). Le médecin traite dès que la probabilité du paludisme dépasse 6 % : il aurait déjà traité après les seuls frissons (\(32/45\approx0{,}711\)), et même avant tout examen (0,40).
Le scénario B change ce seuil. Si le traitement provoque des complications graves chez un patient qui n’a pas le paludisme, \(U(\text{traiter},\text{non})=-500\), et \(EU(\text{traiter})=10p-500(1-p)=510p-500\). Le seuil devient \(p^*=251/306\approx0{,}820\). Après les frissons seuls (\(p=0{,}711\)), \(EU(\text{traiter})=-137{,}33\) et \(EU(\text{renvoyer})=-70{,}53\) : le médecin attend le résultat du TDR. Après la température (\(p=0{,}910\)), \(EU(\text{traiter})=-35{,}90\) contre \(-90{,}82\) : il traite. La figure montre les trois droites et les deux seuils.
Dans le scénario B, après les seuls frissons, attendre le TDR avant de décider a une valeur. Le test est positif avec la probabilité \(0{,}7044\) ; \(P(\text{palu})\) passe alors à \(0{,}959\) et le médecin traite ; s’il est négatif, \(P(\text{palu})\) tombe à \(0{,}120\) et il renvoie la patiente. L’utilité espérée de cette stratégie est \(-10{,}72\), contre \(-70{,}53\) en décidant tout de suite : la valeur de l’information du TDR est \(59{,}81\). Dans le scénario A, elle est nulle : le médecin traiterait quel que soit le résultat. Une information ne vaut que par les décisions qu’elle peut changer.
Trois leçons se dégagent. Les probabilités seules ne décident pas : c’est la combinaison des probabilités et des utilités qui tranche. L’asymétrie des risques gouverne la décision : le seuil s’établit d’autant plus bas que l’erreur « ne pas traiter » coûte cher. Enfin, une probabilité modérée peut justifier une action si les enjeux sont très asymétriques : avec \(U(\text{renvoyer},\text{palu})=-1000\) et \(p=0{,}3\), \(EU(\text{traiter})=0{,}3\times10+0{,}7\times(-5)=-0{,}5\), bien meilleure que \(EU(\text{renvoyer})=0{,}3\times(-1000)+0{,}7\times2=-298{,}6\).
Du MEU à la décision séquentielle
Le MEU résout la décision ponctuelle : une action, des conséquences qui s’arrêtent là. Or, après avoir traité Fatou, le Dr Ndoye la réévalue dans 48 heures ; il observe de nouveaux symptômes, recalcule sa croyance, prend une nouvelle décision, qui change l’état de la patiente, donc les décisions suivantes. Il faut un outil pour une suite de décisions : le processus de décision markovien.
| MEU (une décision) | MDP (une suite de décisions) | |
|---|---|---|
| critère | \(EU(a)=\sum_s P(s\mid\mathbf e)\,U(s)\) | \(V^*(s)=\max_a\bigl[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V^*(s')\bigr]\) |
| résultat | une action | une politique \(\pi^*\) |
| horizon | un pas | une suite de transitions |
| gain | une utilité finale | des récompenses cumulées et actualisées |
La valeur \(V^*(s)\) d’un état, définie plus loin, est une utilité espérée calculée récursivement sur plusieurs pas : le processus de décision markovien généralise le MEU à un horizon de plusieurs décisions.
Les processus de décision markoviens
Les cinq ingrédients
Un processus de décision markovien (MDP, Markov decision process) décrit une situation où l’agent se trouve dans un état, choisit une action, voit le monde réagir de façon probabiliste, reçoit une récompense, et cherche à maximiser ses récompenses sur le long terme, celles d’un avenir lointain comptant un peu moins que celles du pas suivant.
| \(\mathcal S\) | états | toutes les situations possibles ; pour Amadou, les 16 quartiers de la grille |
|---|---|---|
| \(\mathcal A\) | actions | ce que l’agent peut faire : haut, bas, gauche, droite |
| \(P(s'\mid s,a)\) | transitions | probabilité d’arriver en \(s'\) depuis \(s\) en faisant \(a\) ; \(\sum_{s'}P(s'\mid s,a)=1\) |
| \(R(s,a)\) | récompense | gain espéré du pas : ici, \(+1\) à l’arrivée à Diamniadio, \(-1\) en zone inondée |
| \(\gamma\in[0,1)\) | actualisation | une récompense reçue un pas plus tard est multipliée par \(\gamma\) |
Dans le gridworld de Dakar, la récompense est versée à l’arrivée dans une case : \(r(s')=+1\) à Diamniadio, \(-1\) dans une zone inondée, 0 ailleurs. La récompense espérée d’une action est alors \(R(s,a)=\sum_{s'}P(s'\mid s,a)\,r(s')\). La gare de Diamniadio et les zones inondées sont des états terminaux : l’épisode s’y arrête, et leur valeur est nulle (plus rien ne peut être gagné ensuite).
À chaque pas, l’agent observe l’état \(s_t\), choisit \(a_t\) ; le monde tire l’état suivant \(s_{t+1}\) selon \(P(\cdot\mid s_t,a_t)\) et verse \(r_{t+1}\). La règle qui choisit l’action est la politique de l’agent ; son objectif est de maximiser l’espérance de \(r_1+\gamma r_2+\gamma^2r_3+\cdots\).
La propriété de Markov
Le « M » de MDP désigne une hypothèse : \[P(s_{t+1}\mid s_t,a_t,s_{t-1},a_{t-1},\dots,s_0,a_0)=P(s_{t+1}\mid s_t,a_t).\] Pour prédire la suite, l’état présent et l’action présente contiennent toute l’information utile : le passé y est déjà résumé.
Amadou est à Médina. Si la propriété de Markov tient, la probabilité d’un embouteillage au prochain carrefour est la même pendant sa première heure de service et pendant sa dixième, qu’il vienne du Plateau ou de Pikine, pourvu que son état soit le même. Si au contraire la fatigue d’Amadou s’accumule au fil de la journée et change ses réflexes, « être à Médina » ne décrit plus l’état : être à Médina après deux heures de conduite n’est pas être à Médina après dix. Il faut alors enrichir l’état, par exemple d’un niveau de fatigue. Un état trop pauvre viole la propriété de Markov ; un état trop riche multiplie le nombre d’états. Le choix de l’état est une décision de modélisation.
La propriété de Markov est l’indépendance conditionnelle de la Séance 5, appliquée dans le temps : \(S_{t+1}\perp(S_{t-1},A_{t-1},\dots)\mid(S_t,A_t)\). Un MDP est un réseau bayésien qui se déroule pas après pas ; la table \(P(S_{t+1}\mid S_t,A_t)\) y joue le rôle d’une table de probabilités conditionnelles.
La politique : une règle, pas un chemin
En Séance 3, A* rendait un chemin : une suite fixe d’états, planifiable d’avance parce que chaque action avait un résultat certain. Dans un MDP, le résultat d’une action est aléatoire ; un plan « droite, puis haut, puis droite » peut être rendu caduc par la première glissade. On ne planifie donc pas un chemin mais une politique.
Une politique associe une action à chaque état : \(\pi:\mathcal S\to\mathcal A\) (politique déterministe), ou une distribution sur les actions, \(\pi(a\mid s)=P(A=a\mid S=s)\) (politique stochastique). La politique optimale \(\pi^*\) maximise la récompense cumulée espérée depuis tout état de départ.
Pour Amadou, un chemin serait « Plateau, HLM, Pikine, Keur Massar, Rufisque, Bargny, Diamniadio » : une glissade vers Thiaroye, et le plan ne dit plus quoi faire. Une politique dit « depuis Thiaroye : droite ; depuis Parcelles : haut ; depuis Bargny : bas », et donne une consigne pour chaque case, y compris celles qu’Amadou ne comptait pas traverser.
Le gridworld de Dakar
La grille de la figure range seize lieux de la région de Dakar sur quatre lignes et quatre colonnes, de l’ouest (à gauche) vers l’est (à droite) : les quartiers de Dakar dans la première colonne, puis la banlieue, puis Rufisque, Bargny et Diamniadio à l’est. Le Plateau est en haut à gauche, la gare de Diamniadio en bas à droite ; deux zones inondées occupent la case sous Parcelles et la case à gauche de Diamniadio. Les lignes ne suivent pas le nord et le sud : la grille est un schéma.
Les transitions. L’action voulue réussit avec la probabilité 0,8 ; avec 0,1, Amadou est dévié perpendiculairement vers la gauche de sa direction, et avec 0,1 vers la droite. Un mouvement qui sortirait de la grille le laisse sur place. Depuis Pikine, en voulant aller à droite vers Keur Massar : Keur Massar avec 0,8 ; vers le haut (la gauche de sa direction), le bord, donc Pikine avec 0,1 ; vers le bas, Thiaroye avec 0,1. La somme vaut \(0{,}8+0{,}1+0{,}1=1\), comme pour tout couple \((s,a)\).
Le programme suivant écrit ces transitions. Une case est un couple (ligne, colonne) ; COTES donne, pour chaque direction, la direction de gauche et celle de droite ; bouger renvoie la case d’arrivée, ou la case de départ si le mouvement sort de la grille.
CASES = [(l, c) for l in range(4) for c in range(4)]
ACTIONS = ["haut", "bas", "gauche", "droite"]
DIRS = {"haut": (-1, 0), "bas": (1, 0), "gauche": (0, -1), "droite": (0, 1)}
COTES = {"haut": ("gauche", "droite"), "bas": ("droite", "gauche"),
"gauche": ("bas", "haut"), "droite": ("haut", "bas")}
def bouger(s, d):
n = (s[0] + DIRS[d][0], s[1] + DIRS[d][1])
return n if n in CASES else s
def transitions(s, a):
g, d = COTES[a]
return [(0.8, bouger(s, a)), (0.1, bouger(s, g)), (0.1, bouger(s, d))]
print(transitions((0, 2), "droite"))
print(transitions((2, 3), "bas"))La sortie est :
[(0.8, (0, 3)), (0.1, (0, 2)), (0.1, (1, 2))]
[(0.8, (3, 3)), (0.1, (2, 3)), (0.1, (2, 2))]La première ligne est l’exemple de Pikine : \((0,3)\) Keur Massar, \((0,2)\) Pikine, \((1,2)\) Thiaroye. La seconde est Bargny \((2,3)\) en voulant descendre : Diamniadio \((3,3)\) avec 0,8, Bargny elle-même (vers la droite, le bord) avec 0,1, Yeumbeul \((2,2)\) avec 0,1.
Valeur et actualisation
La fonction de valeur
Une fois le MDP posé, il faut mesurer la qualité d’une politique. La question centrale est : si Amadou est à Médina et suit une politique donnée, combien peut-il espérer gagner, au total, jusqu’à la fin de son trajet ? Cette grandeur, la somme actualisée des récompenses futures espérées, est la fonction de valeur.
La fonction de valeur d’une politique \(\pi\) est la récompense cumulée espérée en partant de \(s\) et en suivant \(\pi\) : \[V^\pi(s)=\mathbb E_\pi\Bigl[\sum_{t=0}^{\infty}\gamma^t\,r_{t+1}\;\Big|\;s_0=s\Bigr].\] \(r_{t+1}\) est la récompense reçue au pas \(t+1\) ; le poids \(\gamma^t\) diminue avec \(t\) ; l’espérance porte sur tous les scénarios que produisent les transitions aléatoires et les choix de \(\pi\). La valeur optimale est \(V^*(s)=\max_\pi V^\pi(s)\).
\(V^*(s)\) répond à la question : « en partant de \(s\) et en agissant au mieux, combien vais-je récolter en espérance ? » C’est l’utilité espérée du MEU, étendue à une suite de pas. Dans le gridworld de Dakar, \(V^*(\text{Plateau})=0{,}474\) : la récompense \(+1\) de Diamniadio, atténuée par la distance, par les glissades et par l’actualisation.
Le facteur d’actualisation
Trois raisons conduisent à prendre \(\gamma<1\).
Une raison économique. Un franc CFA aujourd’hui vaut plus qu’un franc demain, parce qu’on peut le placer entre-temps à un taux \(i\) : le facteur d’actualisation est \(\gamma=1/(1+i)\), soit environ 0,909 pour \(i=10\) %.
Une raison d’incertitude. Si, à chaque pas, l’épisode peut s’arrêter avec la probabilité \(1-\gamma\) (Amadou tombe en panne, le marché ferme), une récompense prévue dans \(t\) pas n’est reçue qu’avec la probabilité \(\gamma^t\) : son espérance est multipliée par \(\gamma^t\).
Une raison mathématique. Sans actualisation, la somme \(\sum_t r_{t+1}\) peut diverger sur un horizon infini. Avec \(\gamma<1\) et \(|r|\le R_{\max}\), elle est bornée par \(R_{\max}/(1-\gamma)\) : 2, 10 et 100 pour \(\gamma=0{,}5\) ; 0,9 ; 0,99. Cette borne garantit l’existence d’une solution optimale.
La figure montre le poids \(\gamma^t\) des récompenses futures. Avec \(\gamma=0{,}5\), l’agent est myope : après trois pas, presque plus rien ne compte. Avec \(\gamma=0{,}9\), une récompense dans cinq pas vaut encore \(0{,}9^5=0{,}59\) fois une récompense reçue tout de suite ; avec \(\gamma=0{,}99\), l’agent valorise un avenir lointain.
Amadou peut prendre une route courte et risquée, qui rapporte tout de suite \(+0{,}8\) avec la probabilité 0,7 et \(-0{,}5\) avec 0,3, soit une espérance de \(0{,}7\times0{,}8+0{,}3\times(-0{,}5)=0{,}41\) ; ou une route longue et sûre, qui rapporte \(+0{,}70\) de façon certaine, mais trois pas plus tard. Le gain est \(r_1+\gamma r_2+\gamma^2r_3+\gamma^3r_4\) : la route courte paie en \(r_1\), sans actualisation ; la route longue paie en \(r_4\), et sa valeur actualisée est \(\gamma^3\times0{,}70\) :
| \(\gamma\) | \(\gamma^3\times0{,}70\) | choix |
|---|---|---|
| 0,5 | 0,0875 | route courte (0,41) |
| 0,9 | 0,5103 | route longue |
Les deux routes s’équilibrent quand \(\gamma^3\times0{,}70=0{,}41\), soit \(\gamma=(0{,}41/0{,}70)^{1/3}\approx0{,}837\). La même situation et les mêmes récompenses conduisent à deux décisions opposées selon \(\gamma\) : le facteur d’actualisation est un paramètre de conception, qui fixe la prévoyance de l’agent.
La fonction \(Q\)
\(V^*(s)\) dit ce que vaut un état quand on agit au mieux. Une question plus fine est utile : que vaut-il de faire précisément l’action \(a\) maintenant, puis d’agir au mieux ensuite ?
\[Q^*(s,a)=R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V^*(s'),\qquad V^*(s)=\max_a Q^*(s,a),\qquad\pi^*(s)=\arg\max_a Q^*(s,a).\] \(Q^*(s,a)\) est la récompense espérée du pas, plus la valeur actualisée des états suivants quand on agit au mieux à partir d’eux : un MEU sur un pas, suivi d’une conduite optimale.
L’intérêt de \(Q^*\) apparaîtra avec le Q-learning : celui qui connaît \(Q^*\) choisit la meilleure action en chaque état par un maximum sur les actions, sans avoir besoin de \(P\). À Bargny, \(Q^*(\text{Bargny},\text{bas})=0{,}943\), puis \(Q^*(\text{Bargny},\text{droite})=0{,}852\), \(Q^*(\text{Bargny},\text{haut})=0{,}730\) et \(Q^*(\text{Bargny},\text{gauche})=0{,}635\) : la politique optimale y descend vers Diamniadio.
L’équation de Bellman
L’origine de la récurrence
Richard Bellman (1957) a observé que la valeur optimale d’un état s’exprime par les valeurs optimales de ses successeurs. L’idée semble circulaire ; c’est précisément ce qui la rend utile. Supposons connues les valeurs optimales de tous les quartiers sauf Bargny. Depuis Bargny, Amadou peut tenter de descendre vers Diamniadio : avec 0,8 il y arrive et reçoit \(+1\) (l’épisode s’arrête) ; avec 0,1 il est dévié vers la droite de la grille, contre le bord, et reste à Bargny ; avec 0,1 il est dévié vers la gauche de la grille, à Yeumbeul. Il peut aussi tenter de monter vers Rufisque, ou d’aller à gauche, ou à droite. La meilleure de ces actions détermine \(V^*(\text{Bargny})\).
\[V^*(s)=\max_{a}\Bigl[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V^*(s')\Bigr]\]
Cette équation admet trois lectures. C’est un MEU récursif : le MEU de la première section, appliqué non à des résultats finaux mais à des états qui ont eux-mêmes une valeur. C’est une décomposition : la valeur de \(s\) est le gain du pas plus la valeur actualisée de l’avenir. C’est un système : \(|\mathcal S|\) équations à \(|\mathcal S|\) inconnues ; le \(\max\) le rend non linéaire, de sorte qu’on ne le résout pas par l’algèbre linéaire, mais par itération.
Bellman à Bargny
Les valeurs optimales des voisins de Bargny, calculées plus loin par l’itération sur les valeurs avec \(\gamma=0{,}9\), sont \(V^*(\text{Yeumbeul})=0{,}642\), \(V^*(\text{Rufisque})=0{,}815\) et \(V^*(\text{Bargny})=0{,}943\) ; Diamniadio est terminale, de valeur nulle.
\[ \begin{aligned} Q^*(\text{Bargny},\text{bas})&=0{,}8\times(1+0{,}9\times0)+0{,}1\times(0+0{,}9\times0{,}943)+0{,}1\times(0+0{,}9\times0{,}642)\\ &=0{,}8+0{,}0848+0{,}0578=0{,}943,\\ Q^*(\text{Bargny},\text{haut})&=0{,}8\times0{,}9\times0{,}815+0{,}1\times0{,}9\times0{,}642+0{,}1\times0{,}9\times0{,}943\\ &=0{,}5869+0{,}0578+0{,}0848=0{,}730. \end{aligned} \]
Pour « haut », la gauche de la direction est Yeumbeul et la droite le bord (Bargny). La deuxième action est « droite », contre le bord : \(Q^*(\text{Bargny},\text{droite})=0{,}852\). Le maximum, 0,943, est atteint par « bas » : c’est à la fois \(V^*(\text{Bargny})\) et la consigne de la politique optimale en ce quartier. \(V^*(\text{Bargny})\) apparaît des deux côtés de l’équation : on ne la lit pas, on l’obtient en itérant.
La valeur d’une action en Python
Pour suivre l’itération à la main, on utilise une grille réduite à six cases : A, B, C sur la ligne du haut, D, E, F sur la ligne du bas ; E est un danger (\(r=-1\)), F le but (\(r=+1\)), tous deux terminaux ; les transitions sont celles de Dakar (0,8, 0,1, 0,1) et \(\gamma=0{,}9\). La fonction q_valeur calcule \(\sum_{s'}P(s'\mid s,a)\,[r(s')+\gamma V(s')]\), c’est-à-dire \(R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\).
CASES = [(l, c) for l in range(2) for c in range(3)]
RECOMP = {(1, 1): -1, (1, 2): 1} # E : danger, F : but
TERMINAUX = {(1, 1), (1, 2)}
ETATS = [s for s in CASES if s not in TERMINAUX]
GAMMA = 0.9
def q_valeur(s, a, V):
q = 0.0
for p, s2 in transitions(s, a):
q = q + p * (RECOMP.get(s2, 0) + GAMMA * V[s2])
return q
V0 = {s: 0.0 for s in CASES}
print(round(q_valeur((0, 2), "bas", V0), 3))
print(round(q_valeur((0, 2), "droite", V0), 3))La sortie est :
0.8
0.1Avec des valeurs encore nulles, « bas » depuis C atteint F avec 0,8 : \(Q=0{,}8\). « Droite » envoie C contre le bord ; seule la glissade vers le bas (0,1) atteint F : \(Q=0{,}1\).
L’itération sur les valeurs
L’idée : partir de zéro et propager
L’équation de Bellman définit \(V^*\) comme la solution d’un système non linéaire. Pour l’obtenir, on part de valeurs nulles, qui traduisent l’absence de toute connaissance, et l’on applique l’équation à tous les états, encore et encore, jusqu’à ce que plus rien ne change.
Initialisation. \(V_0(s)=0\) pour tout \(s\).
Mise à jour, à chaque itération \(k\). Pour tout état non terminal : \[V_{k+1}(s)=\max_a\Bigl[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V_k(s')\Bigr].\] Arrêt. Quand \(\max_s|V_{k+1}(s)-V_k(s)|<\varepsilon\).
Politique. \(\pi(s)=\arg\max_a\bigl[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V(s')\bigr]\), calculée avec les valeurs finales.
Les récompenses se propagent depuis les états terminaux vers les états lointains, comme une onde à la surface de l’eau. À la première itération, seuls les voisins d’un terminal ont une valeur non nulle ; à la deuxième, les états à deux pas ; à l’itération \(k\), les états à au plus \(k\) pas. À chaque saut de distance, la valeur est multipliée par \(\gamma\) et par la probabilité de réussir le mouvement : les états lointains ont une valeur plus faible.
Exemple pas à pas : la grille de six cases
Le programme applique la mise à jour six fois à la petite grille. À chaque itération, il construit un nouveau dictionnaire nouveau à partir des valeurs V de l’itération précédente : toutes les cases sont mises à jour avec les mêmes anciennes valeurs, puis V est remplacé d’un bloc (ligne 7).
V = {s: 0.0 for s in CASES}
for k in range(1, 7):
nouveau = dict(V)
for s in ETATS:
qs = [q_valeur(s, a, V) for a in ACTIONS]
nouveau[s] = max(qs)
V = nouveau
print(k, [round(V[s], 3) for s in ETATS])La table suivante donne les valeurs successives jusqu’à la convergence (en gras, les valeurs qui changent), avec l’écart maximal entre deux itérations.
| \(k\) | \(V_k(A)\) | \(V_k(B)\) | \(V_k(C)\) | \(V_k(D)\) | écart |
|---|---|---|---|---|---|
| 0 | \(0\) | \(0\) | \(0\) | \(0\) | – |
| 1 | \(0\) | \(0\) | \(\mathbf{0{,}8}\) | \(0\) | \(0{,}8\) |
| 2 | \(0\) | \(\mathbf{0{,}476}\) | \(\mathbf{0{,}872}\) | \(0\) | \(0{,}476\) |
| 3 | \(\mathbf{0{,}3427}\) | \(\mathbf{0{,}5707}\) | \(\mathbf{0{,}9213}\) | \(0\) | \(0{,}34272\) |
| 4 | \(\mathbf{0{,}4417}\) | \(\mathbf{0{,}6147}\) | \(\mathbf{0{,}9343}\) | \(\mathbf{0{,}1468}\) | \(0{,}14676\) |
| 5 | \(\mathbf{0{,}4956}\) | \(\mathbf{0{,}628}\) | \(\mathbf{0{,}9394}\) | \(\mathbf{0{,}2313}\) | \(0{,}0845\) |
| 6 | \(\mathbf{0{,}5176}\) | \(\mathbf{0{,}6329}\) | \(\mathbf{0{,}9411}\) | \(\mathbf{0{,}2776}\) | \(0{,}04636\) |
| 7 | \(\mathbf{0{,}5273}\) | \(\mathbf{0{,}6345}\) | \(\mathbf{0{,}9417}\) | \(\mathbf{0{,}2976}\) | \(0{,}02003\) |
| 8 | \(\mathbf{0{,}5311}\) | \(\mathbf{0{,}6351}\) | \(\mathbf{0{,}9419}\) | \(\mathbf{0{,}3064}\) | \(0{,}00877\) |
| 9 | \(\mathbf{0{,}5326}\) | \(\mathbf{0{,}6353}\) | \(\mathbf{0{,}9419}\) | \(\mathbf{0{,}31}\) | \(0{,}00356\) |
| 10 | \(\mathbf{0{,}5332}\) | \(\mathbf{0{,}6354}\) | \(\mathbf{0{,}9419}\) | \(\mathbf{0{,}3114}\) | \(0{,}00143\) |
| 11 | \(\mathbf{0{,}5335}\) | \(\mathbf{0{,}6354}\) | \(\mathbf{0{,}942}\) | \(\mathbf{0{,}312}\) | \(0{,}00056\) |
| 12 | \(\mathbf{0{,}5336}\) | \(\mathbf{0{,}6354}\) | \(\mathbf{0{,}942}\) | \(\mathbf{0{,}3122}\) | \(0{,}00022\) |
| 13 | \(\mathbf{0{,}5336}\) | \(\mathbf{0{,}6354}\) | \(\mathbf{0{,}942}\) | \(\mathbf{0{,}3123}\) | \(0{,}00008\) |
Le détail des valeurs des actions pendant les quatre premières itérations montre d’où vient chaque nombre (\(Q_k(s,a)\) est calculée avec \(V_{k-1}\) ; en gras, l’action de plus grande valeur quand elle est unique).
| \(k\) | \(s\) | haut | bas | gauche | droite | \(V_k(s)\) |
|---|---|---|---|---|---|---|
| 1 | A | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 1 | B | \(\mathbf{0}\) | \(-0{,}8\) | \(-0{,}1\) | \(-0{,}1\) | \(0\) |
| 1 | C | \(0\) | \(\mathbf{0{,}8}\) | \(0{,}1\) | \(0{,}1\) | \(0{,}8\) |
| 1 | D | \(-0{,}1\) | \(-0{,}1\) | \(\mathbf{0}\) | \(-0{,}8\) | \(0\) |
| 2 | A | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| 2 | B | \(0{,}072\) | \(-0{,}728\) | \(-0{,}1\) | \(\mathbf{0{,}476}\) | \(0{,}476\) |
| 2 | C | \(0{,}648\) | \(\mathbf{0{,}872}\) | \(0{,}172\) | \(0{,}748\) | \(0{,}872\) |
| 2 | D | \(-0{,}1\) | \(-0{,}1\) | \(\mathbf{0}\) | \(-0{,}8\) | \(0\) |
| 3 | A | \(0{,}0428\) | \(0{,}0428\) | \(0\) | \(\mathbf{0{,}3427}\) | \(0{,}3427\) |
| 3 | B | \(0{,}4212\) | \(-0{,}7215\) | \(-0{,}0572\) | \(\mathbf{0{,}5707}\) | \(0{,}5707\) |
| 3 | C | \(0{,}7492\) | \(\mathbf{0{,}9213}\) | \(0{,}5212\) | \(0{,}8063\) | \(0{,}9213\) |
| 3 | D | \(-0{,}1\) | \(-0{,}1\) | \(\mathbf{0}\) | \(-0{,}8\) | \(0\) |
| 4 | A | \(0{,}329\) | \(0{,}0822\) | \(0{,}2776\) | \(\mathbf{0{,}4417}\) | \(0{,}4417\) |
| 4 | B | \(0{,}5247\) | \(-0{,}6862\) | \(0{,}1981\) | \(\mathbf{0{,}6147}\) | \(0{,}6147\) |
| 4 | C | \(0{,}7976\) | \(\mathbf{0{,}9343}\) | \(0{,}5938\) | \(0{,}8463\) | \(0{,}9343\) |
| 4 | D | \(\mathbf{0{,}1468}\) | \(-0{,}1\) | \(0{,}0308\) | \(-0{,}7692\) | \(0{,}1468\) |
Les itérations clés se lisent ainsi.
- Itération 1. Seule C est voisine de F : \(Q_1(C,\text{bas})=0{,}8\times(1+0{,}9\times0)=0{,}8\). B est voisine de E : toutes ses actions qui risquent E sont négatives, et « haut », contre le bord, vaut 0 ; \(V_1(B)=0\). A et D restent à 0.
- Itération 2. B reçoit la valeur de C : \(Q_2(B,\text{droite})=0{,}8\times(0+0{,}9\times0{,}8)+0{,}1\times(-1)+0{,}1\times(0+0{,}9\times0)=0{,}576-0{,}1=0{,}476\) ; la glissade vers E coûte 0,1. C passe à 0,872 : sa glissade contre le bord la laisse en C, qui vaut désormais 0,8, d’où \(0{,}8+0{,}1\times0{,}9\times0{,}8=0{,}872\).
- Itération 3. A reçoit \(Q_3(A,\text{droite})=0{,}8\times0{,}9\times0{,}476=0{,}343\) (arrondi). D reste à 0 : « haut » vers A, qui valait encore 0, l’exposerait à une glissade vers E (\(-0{,}1\)) ; la meilleure action est « gauche », contre le mur, qui ne risque rien.
- Itération 4. A vaut maintenant 0,343 : \(Q_4(D,\text{haut})=0{,}8\times0{,}9\times0{,}343-0{,}1=0{,}147>0\), et D quitte le mur.
La politique ne change plus à partir de la quatrième itération ; les valeurs, elles, montent encore jusqu’à la treizième, où l’écart passe sous 0,0001. Les deux figures montrent l’état après la deuxième et après la quatrième itération : cases modifiées en rouge, case détaillée dans le commentaire en orange, flèche de l’action de plus grande valeur.
La sortie est :
1 [0.0, 0.0, 0.8, 0.0]
2 [0.0, 0.476, 0.872, 0.0]
3 [0.343, 0.571, 0.921, 0.0]
4 [0.442, 0.615, 0.934, 0.147]
5 [0.496, 0.628, 0.939, 0.231]
6 [0.518, 0.633, 0.941, 0.278]La mise à jour utilise \(V_k\) pour toutes les cases et produit \(V_{k+1}\) d’un bloc. Écrire directement dans V pendant le parcours donne une autre méthode (les cases traitées en premier profitent des nouvelles valeurs de leurs voisines) ; elle converge aussi, mais ses itérations ne sont plus celles de la table.
Convergence et politique
La fonction suivante répète la mise à jour jusqu’à ce que l’écart maximal passe sous \(\varepsilon=0{,}0001\), et rend les valeurs et le nombre d’itérations.
def iteration_valeurs(eps=0.0001):
V = {s: 0.0 for s in CASES}
k = 0
while True:
nouveau = dict(V)
for s in ETATS:
qs = [q_valeur(s, a, V) for a in ACTIONS]
nouveau[s] = max(qs)
ecart = max(abs(nouveau[s] - V[s]) for s in CASES)
V = nouveau
k = k + 1
if ecart < eps:
return V, k
V, k = iteration_valeurs()
print(k, [round(V[s], 3) for s in ETATS])La sortie est :
13 [0.534, 0.635, 0.942, 0.312]Il faut 13 itérations. Les valeurs finales suivent la distance à F, corrigée par le danger : C 0,942, B 0,635, A 0,534, et D, coincée entre le bord et E, 0,312. Ces valeurs sont, à \(10^{-3}\) près, le point fixe exact de l’équation de Bellman pour la politique trouvée (calculé en résolvant le système linéaire de ses quatre équations) : \(V^*(A)=0{,}5336\), \(V^*(B)=0{,}6354\), \(V^*(C)=0{,}9420\), \(V^*(D)=0{,}3123\).
La politique s’en déduit par un pas de Bellman de plus, en gardant l’action de plus grande valeur :
def politique(V):
pi = {}
for s in ETATS:
pi[s] = max(ACTIONS, key=lambda a: q_valeur(s, a, V))
return pi
print(politique(V))
print({a: round(q_valeur((1, 0), a, V), 3) for a in ACTIONS})La sortie est :
{(0, 0): 'droite', (0, 1): 'droite', (0, 2): 'bas', (1, 0): 'haut'}
{'haut': 0.312, 'bas': 0.153, 'gauche': 0.301, 'droite': -0.724}A et B vont à droite, C descend vers F, D monte vers A. En D, « gauche » (0,301), contre le mur, est presque aussi bonne que « haut » (0,312) : la glissade vers E retire 0,1 à « haut », et « droite », vers E, vaut \(-0{,}724\). La table complète des \(Q^*\) est la suivante (en gras, la meilleure action de chaque case).
| \(Q\) | haut | bas | gauche | droite |
|---|---|---|---|---|
| A | \(0{,}489\) | \(0{,}33\) | \(0{,}46\) | \(\mathbf{0{,}534}\) |
| B | \(0{,}59\) | \(-0{,}667\) | \(0{,}341\) | \(\mathbf{0{,}635}\) |
| C | \(0{,}82\) | \(\mathbf{0{,}942}\) | \(0{,}642\) | \(0{,}863\) |
| D | \(\mathbf{0{,}312}\) | \(0{,}153\) | \(0{,}301\) | \(-0{,}724\) |
Le gridworld de Dakar résolu
Les mêmes fonctions s’appliquent à la grille de Dakar : seules changent les cases, les récompenses et les terminaux.
CASES = [(l, c) for l in range(4) for c in range(4)]
# Diamniadio (gare TER), puis les deux zones inondees
RECOMP = {(3, 3): 1, (2, 1): -1, (3, 2): -1}
TERMINAUX = {(3, 3), (2, 1), (3, 2)}
ETATS = [s for s in CASES if s not in TERMINAUX]
V, k = iteration_valeurs()
PI = politique(V)
print(k, round(V[(0, 0)], 3), round(V[(2, 3)], 3))
print([PI[(0, c)] for c in range(4)])
print([PI[(1, c)] for c in range(4)])La sortie est :
23 0.474 0.943
['droite', 'droite', 'droite', 'bas']
['haut', 'haut', 'droite', 'bas']L’itération converge en 23 itérations ; \(V^*(\text{Plateau})=0{,}474\) et \(V^*(\text{Bargny})=0{,}943\). La courbe de chaque quartier montre la propagation : Bargny, voisine de Diamniadio, reçoit sa valeur dès la première itération (0,8) ; Thiaroye à la troisième, Pikine à la quatrième, le Plateau, à six pas de Diamniadio, à la sixième.
La valeur décroît avec la distance à Diamniadio. La politique optimale suit la route la plus directe, sauf là où une glissade mènerait dans l’eau : Parcelles monte vers HLM au lieu de descendre, car la case du dessous est inondée ; Yeumbeul va vers Bargny plutôt que vers le bas, qui est inondé ; Guédiawaye, entre deux zones inondées, s’en éloigne vers la gauche. La politique contourne le danger avec une marge que le chemin le plus court n’aurait pas.
L’effet du facteur d’actualisation
for GAMMA in (0.5, 0.9, 0.99):
V, k = iteration_valeurs()
pi = politique(V)
print(GAMMA, k, round(V[(0, 0)], 3), pi[(2, 0)])
GAMMA = 0.9
V, k = iteration_valeurs()La sortie est :
0.5 11 0.014 gauche
0.9 23 0.474 haut
0.99 65 0.904 gauche| \(\gamma\) | itérations | \(V^*(\text{Plateau})\) | \(\pi^*(\text{Fann})\) |
|---|---|---|---|
| \(0{,}5\) | 11 | \(0{,}014\) | gauche |
| \(0{,}9\) | 23 | \(0{,}474\) | haut |
| \(0{,}99\) | 65 | \(0{,}904\) | gauche |
Plus \(\gamma\) est grand, plus les valeurs sont grandes (0,014, 0,474, 0,904 au Plateau) et plus la convergence est lente (11, 23, 65 itérations) : un avenir qui compte davantage met plus de temps à se stabiliser. La politique change aussi. À Fann, juste à gauche d’une zone inondée, « haut » risque une glissade vers l’eau. Avec \(\gamma=0{,}9\), le gain de la montée l’emporte. Avec \(\gamma=0{,}5\), la récompense lointaine ne vaut presque rien et le risque domine ; avec \(\gamma=0{,}99\), l’agent est assez patient pour rester contre le bord, sans risque, et attendre que les glissades le fassent avancer.
Le coût par pas
Dans le gridworld de Dakar, seules les cases terminales rapportent quelque chose. On peut aussi faire payer chaque pas : chaque arrivée dans une case non terminale coûte \(c\) (du carburant, du temps), comme le coût d’un chemin en Séance 3. Avec \(c=-0{,}04\), \(V^*(\text{Plateau})\) tombe de 0,474 à 0,274 (21 itérations), et deux cases changent d’action : Médina et Parcelles, qui montaient pour s’éloigner de l’eau, vont désormais à droite ; la prudence a maintenant un prix. Avec \(c=-0{,}5\), \(V^*(\text{Plateau})=-1{,}937\) (16 itérations) et cinq cases changent : Médina, Fann, Mermoz et Guédiawaye vont à droite, Parcelles descend. Parcelles, Fann et Guédiawaye vont ainsi droit dans une zone inondée : une pénalité de \(-1\), une seule fois, vaut mieux qu’une suite de pas à \(-0{,}5\). L’agent optimise exactement les récompenses qu’on lui donne ; un coût mal choisi produit une politique optimale pour le modèle et absurde pour le chauffeur.
La convergence de l’itération
L’opérateur de Bellman \(\mathcal T\), défini par \((\mathcal TV)(s)=\max_a[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')]\), est une contraction de facteur \(\gamma\) pour la norme du maximum : \(\|\mathcal TV-\mathcal TV'\|_\infty\le\gamma\|V-V'\|_\infty\).
Fixons un état \(s\) et notons \(a_1\) l’action qui atteint le maximum dans \((\mathcal TV)(s)\). Comme \((\mathcal TV')(s)\) est un maximum, il est au moins égal à la valeur de \(a_1\) calculée avec \(V'\) : \[(\mathcal TV)(s)-(\mathcal TV')(s)\le\gamma\sum_{s'}P(s'\mid s,a_1)\,[V(s')-V'(s')]\le\gamma\|V-V'\|_\infty,\] car les \(P(s'\mid s,a_1)\) sont positives et somment à 1. Par symétrie, \(|(\mathcal TV)(s)-(\mathcal TV')(s)|\le\gamma\|V-V'\|_\infty\) pour tout \(s\). Par le théorème du point fixe de Banach, \(V_k=\mathcal T^kV_0\) converge vers l’unique point fixe de \(\mathcal T\), qui est \(V^*\).
En appliquant l’inégalité \(k\) fois, \(\|V_k-V^*\|_\infty\le\gamma^k\|V_0-V^*\|_\infty\). Pour \(\gamma=0{,}9\) et un écart initial d’au plus 1 (les récompenses valent au plus 1 en valeur absolue et \(V^*\) reste dans \([-1,1]\) ici), une précision de \(10^{-3}\) est garantie après \(\lceil\ln10^{-3}/\ln0{,}9\rceil=66\) itérations. C’est une borne de pire cas : à Dakar, les valeurs sont stables à trois décimales après au plus 20 itérations, et le critère \(10^{-4}\) s’arrête à la vingt-troisième.
Elle exige le modèle : \(P\) et \(R\) doivent être connus d’avance. Chaque itération parcourt tous les états, toutes les actions et tous les successeurs : un coût de l’ordre de \(|\mathcal S|^2|\mathcal A|\). Aux échecs, avec environ \(10^{47}\) états, aucune table ne tient en mémoire. Enfin, \(\gamma\) proche de 1 ralentit la convergence (65 itérations pour \(\gamma=0{,}99\) à Dakar).
L’itération sur les politiques
L’itération sur les valeurs améliore les valeurs, et la politique ne s’en déduit qu’à la fin. L’itération sur les politiques (Russell et Norvig, section 17.2.2) travaille directement sur les politiques, en alternant deux étapes.
Évaluation. Pour la politique courante \(\pi\), résoudre le système linéaire \[V^\pi(s)=R(s,\pi(s))+\gamma\sum_{s'}P(s'\mid s,\pi(s))\,V^\pi(s')\qquad\text{pour tout état non terminal}.\] Sans \(\max\), ce sont \(|\mathcal S|\) équations linéaires à \(|\mathcal S|\) inconnues.
Amélioration. Dans chaque état, \(\pi(s)\leftarrow\arg\max_a\bigl[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)\,V^\pi(s')\bigr]\).
Arrêt. Quand l’amélioration ne change plus aucune action : la politique vérifie alors l’équation de Bellman avec le \(\max\), elle est optimale.
À Dakar, en partant de la politique « droite partout », la première évaluation donne \(V^\pi(\text{Plateau})=0{,}0375\), et l’amélioration change 10 cases sur 13. La deuxième évaluation donne \(0{,}3801\), et 3 cases changent. La troisième donne \(0{,}4743\), la valeur optimale, et aucune case ne change : trois évaluations, chacune un système de 13 équations, au lieu de 23 itérations sur les valeurs. Chaque amélioration ne fait pas baisser la valeur, et le nombre de politiques est fini : la méthode s’arrête toujours. Son coût est l’évaluation exacte, qui devient lourde quand les états se comptent par milliers.
Le Q-learning : apprendre sans modèle
L’absence de modèle
L’itération sur les valeurs suppose que l’agent connaît exactement \(P(s'\mid s,a)\) et \(R(s,a)\) avant d’agir : c’est un MDP à modèle connu. Dans la réalité, Amadou n’a pas de tableau de probabilités de Dakar ; il ne sait pas que la probabilité d’un bouchon sur la VDN, un lundi entre 8 h et 9 h 30, vaut telle valeur. Il doit l’apprendre en conduisant. On entre dans l’apprentissage par renforcement : apprendre une politique à partir de la seule expérience.
| MDP à modèle connu | apprentissage par renforcement (sans modèle) | |
|---|---|---|
| \(P(s'\mid s,a)\) | connu avant d’agir | inconnu ; une transition observée après chaque action |
| \(R(s,a)\) | connu | reçu après l’action |
| méthode | itération sur les valeurs | Q-learning |
| calcul | planification hors ligne | apprentissage en agissant |
| pour Amadou | étudier une carte avant le trajet | apprendre la ville en conduisant |
La règle du Q-learning
\(Q^*\) a une propriété précieuse : qui la connaît en déduit la politique optimale, \(\pi^*(s)=\arg\max_aQ^*(s,a)\), sans \(P\) ni \(V^*\). L’idée de Watkins (1989) est d’estimer \(Q^*\) directement à partir des transitions vécues, en se servant de la récurrence de Bellman comme d’une règle de mise à jour. Si \(Q\) était exacte, chaque transition \((s,a,r,s')\) vérifierait en moyenne \(Q(s,a)=r+\gamma\max_{a'}Q(s',a')\). Après une transition observée, le membre de droite fournit une nouvelle estimation, la cible, qui contient une information réelle : la récompense \(r\) et l’état \(s'\) effectivement atteint. On déplace \(Q(s,a)\) vers cette cible, d’un pas \(\alpha\).
\[Q(s,a)\leftarrow Q(s,a)+\alpha\,\bigl[\,r+\gamma\max_{a'}Q(s',a')-Q(s,a)\,\bigr]\] Le crochet est l’erreur de différence temporelle (erreur TD), notée \(\delta\) ; \(\alpha\in(0,1]\) est le taux d’apprentissage.
Si \(\delta>0\), la cible est meilleure que prévu : \(Q(s,a)\) augmente ; si \(\delta<0\), c’est une déception : \(Q(s,a)\) diminue ; si \(\delta=0\), l’estimation est cohérente avec l’observation. Un grand \(\alpha\) fait confiance à la dernière observation (apprentissage rapide mais instable) ; un petit \(\alpha\) change lentement ; en pratique, \(\alpha\) décroît au fil de l’apprentissage. La cible utilise la meilleure action en \(s'\), même si l’agent en jouera une autre au pas suivant : le Q-learning est un apprentissage hors politique (off-policy).
La règle se réécrit \(Q\leftarrow(1-\alpha)\,Q+\alpha\cdot\text{cible}\) : une moyenne pondérée entre l’ancienne estimation et la nouvelle observation, qui oublie peu à peu les observations anciennes. C’est un mécanisme de révision des croyances, comme la mise à jour bayésienne de la Séance 5, où le posterior combine le prior et la vraisemblance ; ici, le poids de l’observation est le taux \(\alpha\).
Exemple pas à pas : trois épisodes sur la grille de six cases
Sur la petite grille, Amadou vit trois épisodes. Les deux premiers suivent A, B, C puis F (récompense \(+1\)) ; dans le troisième, depuis B, il glisse vers E (récompense \(-1\)). L’agent ne voit que ces quadruplets \((s,a,r,s')\) ; il ne connaît pas \(P\).
EXPERIENCE = [("A", "droite", 0, "B"), ("B", "droite", 0, "C"),
("C", "bas", 1, "F"),
("A", "droite", 0, "B"), ("B", "droite", 0, "C"),
("C", "bas", 1, "F"),
("A", "droite", 0, "B"), ("B", "droite", -1, "E")]
print(len(EXPERIENCE), "transitions observees")Le programme applique la règle à chaque transition, dans l’ordre où elle a été vécue, avec \(\alpha=0{,}5\) et \(\gamma=0{,}9\) ; \(Q(E,\cdot)\) et \(Q(F,\cdot)\) restent nulles, puisque l’épisode s’y arrête.
ALPHA = 0.5
Q = {(s, a): 0 for s in "ABCDEF" for a in ACTIONS}
for s, a, r, s2 in EXPERIENCE:
meilleur = max(Q[s2, b] for b in ACTIONS)
cible = r + GAMMA * meilleur
Q[s, a] = Q[s, a] + ALPHA * (cible - Q[s, a])
print(s, a, s2, round(Q[s, a], 4))| Tour | transition \((s,a,r,s')\) | \(\max_b Q(s',b)\) | cible | \(Q(s,a)\) |
|---|---|---|---|---|
| 1 | \((A,\text{droite},0,B)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 2 | \((B,\text{droite},0,C)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 3 | \((C,\text{bas},1,F)\) | \(0\) | \(1\) | \(0\to\mathbf{0{,}5}\) |
| 4 | \((A,\text{droite},0,B)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 5 | \((B,\text{droite},0,C)\) | \(0{,}5\) | \(0{,}45\) | \(0\to\mathbf{0{,}225}\) |
| 6 | \((C,\text{bas},1,F)\) | \(0\) | \(1\) | \(0{,}5\to\mathbf{0{,}75}\) |
| 7 | \((A,\text{droite},0,B)\) | \(0{,}225\) | \(0{,}2025\) | \(0\to\mathbf{0{,}1013}\) |
| 8 | \((B,\text{droite},-1,E)\) | \(0\) | \(-1\) | \(0{,}225\to\mathbf{-0{,}3875}\) |
Les deux premières transitions n’apprennent rien : \(\max Q(B,\cdot)\) et \(\max Q(C,\cdot)\) valent encore 0, la cible est nulle. La récompense apparaît à la troisième : \(Q(C,\text{bas})=0+0{,}5\times(1-0)=0{,}5\). Au deuxième épisode, A n’apprend toujours rien (B vaut encore 0 au moment où A est mise à jour), mais B reçoit \(0{,}5\times0{,}9\times0{,}5=0{,}225\), et \(Q(C,\text{bas})\) monte à 0,75. Au troisième, A reçoit enfin \(0{,}5\times0{,}9\times0{,}225=0{,}1013\) (arrondi), puis la glissade vers E fait chuter \(Q(B,\text{droite})\) à \(0{,}225+0{,}5\times(-1-0{,}225)=-0{,}3875\) : une seule mauvaise expérience pèse lourd quand \(\alpha=0{,}5\).
La sortie est :
A droite B 0.0
B droite C 0.0
C bas F 0.5
A droite B 0.0
B droite C 0.225
C bas F 0.75
A droite B 0.1013
B droite E -0.3875La valeur de F ne remonte que d’une case par épisode : il faut trois épisodes pour qu’elle atteigne A. Les estimations sont encore loin de \(Q^*\) (table de la section précédente : \(Q^*(C,\text{bas})=0{,}942\), \(Q^*(B,\text{droite})=0{,}635\), \(Q^*(A,\text{droite})=0{,}534\)) ; elles s’en approchent avec des centaines d’épisodes.
Le Q-learning met à jour \(Q(s,a)\) au moment où la transition est vécue, dans l’ordre chronologique. Repasser l’épisode à l’envers, de la fin vers le début, propagerait la récompense jusqu’à A en un seul épisode ; c’est une autre méthode (un rejeu de l’expérience), qui donne d’autres nombres.
Le dilemme exploration–exploitation
Pour que ses estimations soient fiables, l’agent doit visiter tous les états et essayer toutes les actions assez souvent. Mais une action d’exploration coûte des récompenses.
Exploiter, c’est jouer \(\arg\max_aQ(s,a)\), la meilleure action selon la connaissance actuelle ; si certaines routes n’ont jamais été essayées, cette connaissance est incomplète, et une route meilleure ne sera jamais découverte. Explorer, c’est essayer une action peu testée ; cela coûte des récompenses tout de suite, mais peut révéler une stratégie meilleure et corriger des estimations fausses. Amadou qui n’exploite que ce qu’il connaît peut rater une route bien meilleure ; Amadou qui explore sans cesse ne profite jamais de ce qu’il a appris.
À chaque pas, avec la probabilité \(\varepsilon\), choisir une action au hasard ; sinon, choisir \(\arg\max_aQ(s,a)\). On fait décroître \(\varepsilon\) : au début, quand toutes les estimations sont mauvaises, beaucoup d’exploration ; ensuite, de moins en moins. Avec 4 actions et \(\varepsilon=0{,}2\), la meilleure action est jouée avec la probabilité \(0{,}8+0{,}2/4=0{,}85\) (elle peut aussi sortir du tirage au hasard).
L’agent complet à Dakar
Pour apprendre, l’agent a besoin d’un environnement qui lui renvoie l’état suivant et la récompense. On le simule : la fonction agir tire l’état suivant selon les probabilités de transitions, que l’agent, lui, ne consulte jamais.
def agir(s, a): # l'environnement simule : un tirage
u = random.random()
for p, s2 in transitions(s, a):
if u < p:
return s2, RECOMP.get(s2, 0)
u = u - p
return s2, RECOMP.get(s2, 0)
random.seed(1)
print([agir((0, 2), "droite")[0] for i in range(8)])La sortie est :
[(0, 3), (0, 2), (0, 3), (0, 3), (0, 3), (0, 3), (0, 3), (0, 3)]Sur huit essais de « droite » depuis Pikine, Amadou arrive sept fois à Keur Massar et reste une fois à Pikine (glissade contre le bord) : des fréquences proches de 0,8 et 0,1.
L’agent part du Plateau à chaque épisode, choisit ses actions de façon \(\varepsilon\)-gloutonne (\(\varepsilon\) décroît de 1 à 0,05 sur la première moitié des épisodes), et applique la règle du Q-learning après chaque transition.
def q_learning(episodes, alpha=0.1):
Q = {(s, a): 0.0 for s in CASES for a in ACTIONS}
for n in range(episodes):
eps = max(0.05, 1 - n / (episodes / 2))
s = (0, 0)
while s not in TERMINAUX:
if random.random() < eps:
a = random.choice(ACTIONS)
else:
a = max(ACTIONS, key=lambda b: Q[s, b])
s2, r = agir(s, a)
cible = r + GAMMA * max(Q[s2, b] for b in ACTIONS)
Q[s, a] = Q[s, a] + alpha * (cible - Q[s, a])
s = s2
return Qrandom.seed(221)
Q = q_learning(3000)
appris = {}
for s in PI:
appris[s] = max(ACTIONS, key=lambda b: Q[s, b])
ok = [s for s in PI if appris[s] == PI[s]]
print(len(ok), "cases sur", len(PI))
print([s for s in PI if appris[s] != PI[s]])
print(round(Q[(0, 0), "droite"], 3))
print(round(q_valeur((0, 0), "droite", V), 3))La sortie est :
12 cases sur 13
[(3, 1)]
0.486
0.474Après 3000 épisodes, la politique apprise coïncide avec la politique optimale de l’itération sur les valeurs sur 12 cases sur 13. La case qui diffère, Guédiawaye \((3,1)\), n’est presque jamais visitée depuis le Plateau : ses estimations restent grossières. \(Q(\text{Plateau},\text{droite})\) vaut 0,486 pour une valeur exacte de 0,474 : avec \(\alpha\) constant, l’estimation fluctue autour de la vraie valeur sans s’y fixer.
La figure du haut donne le gain actualisé moyen par paquet de 100 épisodes : négatif au début, quand l’agent explore au hasard et tombe souvent dans l’eau, il remonte vers \(V^*(\text{Plateau})=0{,}474\) sans l’atteindre, parce que l’agent continue d’explorer 5 % du temps. La figure du bas suit \(Q(\text{Plateau},\text{droite})\), qui rejoint la valeur exacte en quelques centaines d’épisodes.
Ce que garantit le Q-learning, et ce qu’il ne garantit pas
La cible \(r+\gamma\max_{a'}Q(s',a')\) est un échantillon de l’équation de Bellman pour \(Q^*\). Si chaque couple \((s,a)\) est visité une infinité de fois et si le taux \(\alpha\) décroît convenablement, \(Q\) converge vers \(Q^*\) avec la probabilité 1 (Watkins et Dayan, 1992).
Exploration insuffisante : des cases rarement visitées restent mal estimées (Guédiawaye). Lenteur : la valeur remonte d’un pas par passage. Taille : la table a une case par couple \((s,a)\) ; au-delà de quelques millions de couples, elle ne peut pas être remplie par l’expérience. Il faut alors une fonction approchée, réglée par la descente de gradient.
La descente de gradient, pont vers le Machine Learning
Au-delà des tables
Dans tout ce qui précède, \(V\) et \(Q\) sont des tables : une valeur par case, une valeur par couple (case, action), soit 16 valeurs \(V\) et 64 valeurs \(Q\) pour la grille de Dakar. Le monde réel est d’une autre dimension : environ \(10^{47}\) positions aux échecs, \(10^{170}\) au go ; une image de \(224\times224\) pixels est un état de \(50\,176\) nombres. On remplace alors la table par une fonction à paramètres, \(V_{\boldsymbol\theta}(s)\) ou \(Q_{\boldsymbol\theta}(s,a)\), par exemple un réseau de neurones, et l’on cherche les paramètres \(\boldsymbol\theta\) qui rendent ses erreurs les plus petites possible. L’algorithme qui règle ces paramètres est la descente de gradient, le moteur de tout le Machine Learning.
Du hill climbing à la descente de gradient
La Séance 3 a présenté le hill climbing : depuis un état courant, évaluer les voisins et passer au meilleur, jusqu’à ce qu’aucun voisin ne soit meilleur. Sur le problème des reines, il minimisait le nombre de conflits \(h\). La descente de gradient fait la même chose dans un espace continu de paramètres : au lieu d’énumérer des voisins, elle calcule la pente de la fonction de coût et fait un pas dans la direction où le coût diminue le plus vite.
| hill climbing (Séance 3) | descente de gradient | |
|---|---|---|
| espace | états discrets, voisins énumérés | paramètres continus |
| direction | meilleur voisin, par évaluation | opposée au gradient, par dérivation |
| taille du pas | un voisin | \(\eta\,\|\nabla J\|\), réglée par le taux d’apprentissage \(\eta\) |
| arrêt | aucun voisin meilleur (optimum local) | gradient nul (minimum local) |
Les deux méthodes partagent leur limite : elles ne voient que les environs du point courant, et peuvent s’arrêter dans un minimum local.
La règle de mise à jour
Pour une fonction de coût \(J(\boldsymbol\theta)\) dérivable, la règle de mise à jour est \[\boldsymbol\theta_{k+1}=\boldsymbol\theta_k-\eta\,\nabla J(\boldsymbol\theta_k).\] Le gradient \(\nabla J\), vecteur des dérivées partielles de \(J\) par rapport à chaque paramètre, indique la direction de plus forte montée ; on le soustrait pour aller dans la direction de plus forte descente. Le taux d’apprentissage \(\eta>0\) règle la longueur du pas.
Quatre lectures éclairent cette règle. Géométrique : le gradient est orthogonal aux courbes de niveau de \(J\) ; en soustraire un multiple, c’est partir perpendiculairement à la courbe de niveau du point courant, comme un marcheur dans le brouillard sur les Mamelles qui sent la pente sous ses pieds et descend là où elle est la plus raide. Algébrique : pour \(J(w)=w^2\), \(J'(w)=2w\) et \(w\leftarrow w-2\eta w=w(1-2\eta)\) ; avec \(\eta=0{,}3\), \(w\) est multiplié par 0,4 à chaque pas et tend vers le minimum \(w^*=0\). Numérique : au premier ordre, \(J(\boldsymbol\theta-\eta\nabla J)\approx J(\boldsymbol\theta)-\eta\|\nabla J\|^2\), donc un pas assez petit diminue \(J\). Machine Learning : avec \(n\) exemples \((x_i,y_i)\) et un modèle \(f_{\boldsymbol\theta}\), on minimise l’erreur quadratique moyenne \(J(\boldsymbol\theta)=\frac1n\sum_i(y_i-f_{\boldsymbol\theta}(x_i))^2\) ; le gradient dit comment modifier \(\boldsymbol\theta\) pour rapprocher les prédictions des valeurs observées.
En deux dimensions, sur \(J(w_1,w_2)=w_1^2+5w_2^2\) avec \(\eta=0{,}18\), chaque pas multiplie \(w_1\) par \(1-0{,}36=0{,}64\) et \(w_2\) par \(1-1{,}8=-0{,}8\) : chaque pas part perpendiculairement à la courbe de niveau du point courant ; le chemin progresse régulièrement le long de l’axe doux et oscille le long de l’axe raide.
Exemple pas à pas : le tarif d’Amadou
Amadou relève trois courses : 2 km pour 1 400 F CFA, 4 km pour 1 800 F, 6 km pour 3 000 F. Il cherche un tarif au kilomètre \(w\) (en milliers de francs) tel que le prix prédit \(w\times\)distance soit le plus proche possible des prix observés, au sens de l’erreur quadratique moyenne.
X = [2, 4, 6] # distances (km)
Y = [1.4, 1.8, 3.0] # prix (milliers de F CFA)
def cout(w):
j = 0.0
for x, y in zip(X, Y):
j = j + (y - w * x) ** 2
return j / len(X)
print(round(cout(0), 4), round(cout(0.5), 4), round(cout(1), 4))La sortie est :
4.7333 0.0667 4.7333La perte est \(J(w)=\frac13\sum_i(y_i-wx_i)^2\) et sa dérivée \[J'(w)=-\frac23\sum_ix_i(y_i-wx_i)=\frac23\Bigl(w\sum_ix_i^2-\sum_ix_iy_i\Bigr)=\frac23(56w-28)=\frac{112w-56}{3},\] nulle en \(w^*=28/56=0{,}5\) : 500 F par kilomètre, avec une perte minimale \(J(0{,}5)=1/15\approx0{,}0667\). La descente retrouve ce minimum sans résoudre l’équation \(J'(w)=0\) :
def gradient(w):
g = 0.0
for x, y in zip(X, Y):
g = g - 2 * x * (y - w * x) / len(X)
return g
w = 0.0
ETA = 0.02
for k in range(1, 5):
w = w - ETA * gradient(w)
print(k, round(w, 4), round(cout(w), 4))| \(k\) | \(w_{k-1}\) | \(J'(w_{k-1})\) | \(w_k=w_{k-1}-0{,}02\,J'(w_{k-1})\) | \(J(w_k)\) |
|---|---|---|---|---|
| 1 | \(0\) | \(-18{,}6667\) | \(0{,}3733\) | \(0{,}3662\) |
| 2 | \(0{,}3733\) | \(-4{,}7289\) | \(0{,}4679\) | \(0{,}0859\) |
| 3 | \(0{,}4679\) | \(-1{,}198\) | \(0{,}4919\) | \(0{,}0679\) |
| 4 | \(0{,}4919\) | \(-0{,}3035\) | \(0{,}4979\) | \(0{,}0667\) |
Au départ, \(J'(0)=-18{,}6667\) : la pente est fortement négative, le coût diminue quand \(w\) augmente, et le pas \(-0{,}02\times(-18{,}6667)=0{,}3733\) porte \(w\) à 0,3733. La pente s’aplatit à l’approche du minimum, et les pas raccourcissent d’eux-mêmes : \(w_2=0{,}4679\), \(w_3=0{,}4919\), \(w_4=0{,}4979\). On peut le voir exactement : \(w_{k+1}-w^*=(1-\frac{112}{3}\eta)(w_k-w^*)\), et pour \(\eta=0{,}02\) l’écart est multiplié par \(0{,}2533\) à chaque pas. Les figures montrent la première itération (tangente en orange au point de départ) et la dernière.
La sortie est :
1 0.3733 0.3662
2 0.4679 0.0859
3 0.4919 0.0679
4 0.4979 0.0667Le taux d’apprentissage
for ETA in (0.005, 0.02, 0.05, 0.06):
w = 0.0
for k in range(20):
w = w - ETA * gradient(w)
print(ETA, round(w, 4))La sortie est :
0.005 0.492
0.02 0.5
0.05 0.4714
0.06 -36.4321| \(\eta\) | facteur \(1-\frac{112}{3}\eta\) | \(w_{20}\) | descente |
|---|---|---|---|
| \(0{,}005\) | \(0{,}8133\) | \(0{,}492\) | lente |
| \(0{,}02\) | \(0{,}2533\) | \(0{,}5\) | rapide |
| \(0{,}05\) | \(-0{,}8667\) | \(0{,}4714\) | oscillante |
| \(0{,}06\) | \(-1{,}24\) | \(-36{,}4321\) | divergente |
Le facteur \(1-\frac{112}{3}\eta\) décide de tout. Entre 0 et 1, la descente converge sans osciller, lentement si le facteur est proche de 1 (\(\eta=0{,}005\) : 0,8133, encore 0,492 après 20 pas). Entre \(-1\) et 0, elle converge en oscillant de part et d’autre du minimum (\(\eta=0{,}05\) : \(-0{,}8667\)). En dessous de \(-1\), l’écart grandit à chaque pas et la descente diverge (\(\eta=0{,}06\) : \(-1{,}24\), \(w_{20}=-36{,}4321\)). La condition de convergence est \(|1-\frac{112}{3}\eta|<1\), soit \(\eta<3/56\approx0{,}0536\).
Trop petit, il impose des milliers d’itérations ; trop grand, il fait sauter par-dessus le minimum, puis diverger. En pratique, on commence avec un taux assez grand et on le fait décroître au fil de l’entraînement. Un taux qui convient à des données n’est pas transposable tel quel à d’autres : il dépend de la courbure de \(J\), ici \(\frac23\sum_ix_i^2\).
Le Q-learning, une descente de gradient
La mise à jour du Q-learning a exactement la forme d’un pas de descente de gradient sur une perte quadratique. Pour \(J(\theta)=\frac12(y-\theta)^2\), de cible \(y\), \(J'(\theta)=-(y-\theta)\) et la descente s’écrit \(\theta\leftarrow\theta+\eta\,(y-\theta)\) :
| descente de gradient sur \(\frac12(y-\theta)^2\) | Q-learning | |
|---|---|---|
| paramètre | \(\theta\) | \(Q(s,a)\) |
| cible | \(y\) | \(r+\gamma\max_{a'}Q(s',a')\) |
| erreur | \(y-\theta=-J'(\theta)\) | \(\delta=r+\gamma\max_{a'}Q(s',a')-Q(s,a)\) |
| mise à jour | \(\theta\leftarrow\theta+\eta\,(y-\theta)\) | \(Q(s,a)\leftarrow Q(s,a)+\alpha\,\delta\) |
| pas | \(\eta\) | \(\alpha\) |
Le Q-learning fait un pas de gradient sur une case de la table, la cible étant tenue fixe pendant le pas. Quand on remplace la table par un réseau de neurones \(Q_{\boldsymbol\theta}(s,a)\) et qu’on applique la descente de gradient à ses poids \(\boldsymbol\theta\), on obtient le Deep Q-Network (DQN, Mnih et al., 2015), qui a appris à jouer à 49 jeux Atari à partir des seuls pixels de l’écran, sans connaître les règles.
Un taux trop grand fait osciller puis diverger (\(\eta=0{,}06\) sur les courses d’Amadou) ; un taux trop petit rend la descente très lente. Sur un coût non convexe, elle s’arrête dans un minimum local, comme le hill climbing. Quand les paramètres ont des échelles très différentes, le chemin zigzague (l’axe raide de la descente en deux dimensions).
Le Monde de Bouki revisité
Ousmane suit le cours depuis la Séance 2. Les trois approches le traitent différemment ; le MDP est la plus complète.
Ce que la logique donnait (Séance 2). Après « rien » en \((1,1)\), une odeur en \((2,1)\) et une odeur en \((1,2)\), avec un odorat infaillible et un seul Bouki, la logique concluait \(B_{2,2}\) : Bouki est en \((2,2)\), et \((1,3)\) et \((3,1)\) sont sûres. La seule odeur en \((2,1)\) ne donnait que \(B_{2,2}\lor B_{3,1}\). Si l’odorat peut se tromper, la logique ne conclut plus rien.
Ce que Bayes donnait (Séance 5). Avec un odorat imparfait, après « rien » en \((1,1)\), une odeur en \((2,1)\) et une odeur en \((1,2)\), \(P(\text{Bouki en }(2,2))=162/185\approx0{,}876\), \(P(\text{Bouki en }(1,3))=P(\text{Bouki en }(3,1))=9/185\approx0{,}049\), et \(1/370\approx0{,}003\) pour chacune des dix autres cases non visitées.
Le MEU d’un pas. Être dévoré coûte \(-1000\), un pas sans danger \(-1\). Passer par \((2,2)\) : \[EU\bigl((2,2)\bigr)=\tfrac{162}{185}\times(-1000)+\tfrac{23}{185}\times(-1)\approx-875{,}80,\] contre \(\frac{9}{185}\times(-1000)+\frac{176}{185}\times(-1)\approx-49{,}60\) pour \((1,3)\) ou \((3,1)\). Depuis les cases déjà visitées, \((1,1)\), \((1,2)\) et \((2,1)\), tout chemin vers l’or passe par l’une de ces trois cases : aucun chemin n’est sans risque, et le MEU écarte \((2,2)\) en chiffrant le risque des deux autres.
Le MDP. Les états sont les seize cases ; les déplacements sont sûrs ; entrer dans une case rapporte la récompense espérée \(-1000\,P(\text{Bouki})-(1-P(\text{Bouki}))\), plus \(+1000\) sur l’or, en \((4,4)\) ; \(\gamma=0{,}9\). Les croyances bayésiennes entrent dans les récompenses. L’itération sur les valeurs donne, entre autres chemins de même valeur, le chemin \((1,1)\), \((1,2)\), \((1,3)\), \((1,4)\), \((2,4)\), \((3,4)\), \((4,4)\) ; par symétrie des croyances, le chemin par \((3,1)\) vaut exactement autant. Si une nouvelle observation faisait baisser \(P(\text{Bouki en }(2,2))\), les récompenses changeraient, et la politique avec elles.
| logique (Séance 2) | Bayes et MEU (Séances 5, 6) | MDP (Séance 6) | |
|---|---|---|---|
| croyance | « \((2,2)\) », certain si l’odorat est infaillible | \(P(\text{Bouki en }(2,2))=0{,}876\) | intégrée aux récompenses |
| décision | explorer \((1,3)\) ou \((3,1)\), sûres | éviter \((2,2)\) au prochain pas | une politique jusqu’à l’or |
| horizon | aucun | un pas | tout le trajet |
| objectif | déduire la vérité | maximiser l’utilité d’un pas | maximiser la récompense cumulée |
Le paysage du Machine Learning
Le fil des séances
Chaque séance a levé une hypothèse de la précédente. La Séance 1 a défini un agent rationnel qui perçoit et agit pour maximiser sa performance ; restait à raisonner sur ce qu’il perçoit. La Séance 2 l’a fait par la logique ; mais le monde n’est pas seulement vrai ou faux. La Séance 3 a cherché une suite d’actions dans un monde connu avec certitude ; mais le monde est incertain. La Séance 5 a appris à croire et à réviser ses croyances ; mais croire ne dit pas quoi faire. Cette séance a appris à décider, sur un pas (MEU) et sur une suite de pas (MDP), puis à apprendre une politique par l’expérience (Q-learning). Il reste à apprendre, à partir de données, les modèles que le cours a jusqu’ici posés à la main : les tables de probabilités de la Séance 5, les transitions et les récompenses de cette séance.
Une formule commune
Tout le Machine Learning tient en une phrase : trouver les paramètres \(\boldsymbol\theta^*\) qui minimisent une fonction de perte \(J(\boldsymbol\theta)\) sur des données, le plus souvent par descente de gradient ou par l’une de ses variantes (gradient stochastique, Adam).
| approche | paramètres \(\boldsymbol\theta\) | perte \(J(\boldsymbol\theta)\) |
|---|---|---|
| régression linéaire | coefficients \(\mathbf w\), \(b\) | erreur quadratique \(\frac1n\sum_i(y_i-\mathbf w^\top\mathbf x_i-b)^2\) |
| régression logistique | poids \(\mathbf w\), \(b\) | log-vraisemblance négative |
| réseau de neurones | poids de toutes les couches | entropie croisée ou erreur quadratique |
| DQN | poids du réseau \(Q_{\boldsymbol\theta}\) | erreur TD au carré |
Les quatre familles du paysage s’y rattachent. L’apprentissage supervisé apprend une fonction \(f:\mathcal X\to\mathcal Y\) à partir de paires \((x_i,y_i)\) ; la log-vraisemblance \(\log P(y\mid x,\boldsymbol\theta)\), héritée de la Séance 5, est la perte des classifieurs probabilistes. L’apprentissage non supervisé découvre une structure sans étiquettes : les \(k\)-moyennes (k-means) regroupent, l’analyse en composantes principales compresse. Le Deep Learning n’est pas un paradigme à part : c’est une famille de fonctions très expressives, les réseaux de neurones profonds, entraînées par descente de gradient. L’apprentissage par renforcement prolonge le Q-learning : DQN remplace la table par un réseau.
Exercices corrigés
Les trois exercices reprennent les trois calculs centraux de la séance sous la forme des réponses attendues : une table des itérations de Bellman, une table des mises à jour du Q-learning, une table des pas de la descente de gradient. Ils portent sur Cheikh, coursier à vélo du Plateau.
Exercice 1 : l’itération sur les valeurs dans la rue de Kermel à Tilène
Cheikh attend une commande dans une rue de trois cases, numérotées 1, 2, 3 de gauche à droite. À gauche de la case 1, le marché Kermel offre une petite livraison (récompense \(+1\) à l’arrivée) ; à droite de la case 3, le marché Tilène en offre une grosse (\(+4\)). Kermel et Tilène sont terminaux. Depuis une case, Cheikh choisit gauche ou droite ; le mouvement réussit avec la probabilité 0,8 ; sinon (0,2), il reste sur place. Les autres récompenses sont nulles.
- Écrire \(Q(s,\text{gauche})\) et \(Q(s,\text{droite})\) en fonction de \(V\) pour les cases 1, 2 et 3.
- Avec \(\gamma=0{,}9\) et \(V_0=0\), calculer \(V_1\), \(V_2\) et \(V_3\), en donnant pour chaque case la valeur des deux actions.
- Donner l’action de plus grande valeur dans chaque case après chaque itération. Que se passe-t-il en case 1 ?
- L’itération converge en 11 itérations. Calculer exactement \(V^*\) en résolvant les équations de Bellman de la politique « toujours à droite », puis vérifier que cette politique est optimale.
- Reprendre (d) avec \(\gamma=0{,}5\). Quelle politique obtient-on ? L’expliquer.
Méthode. Chaque itération applique l’équation de Bellman à toutes les cases avec les valeurs de l’itération précédente ; pour chaque case, on calcule la valeur des deux actions et on garde la plus grande.
(a) Un mouvement qui réussit mène au voisin ; s’il échoue, Cheikh reste. Avec la récompense à l’arrivée et la valeur nulle des terminaux : \[Q(1,\text{g})=0{,}8\times(1+0)+0{,}2\,\gamma V(1), Q(1,\text{d})=0{,}8\,\gamma V(2)+0{,}2\,\gamma V(1),\] \[Q(2,\text{g})=0{,}8\,\gamma V(1)+0{,}2\,\gamma V(2), Q(2,\text{d})=0{,}8\,\gamma V(3)+0{,}2\,\gamma V(2),\] \[Q(3,\text{g})=0{,}8\,\gamma V(2)+0{,}2\,\gamma V(3), Q(3,\text{d})=0{,}8\times(4+0)+0{,}2\,\gamma V(3).\]
(b) et (c) La règle : \(Q_k(s,a)\) se calcule avec \(V_{k-1}\), et \(V_k(s)=\max_aQ_k(s,a)\). Le détail des trois itérations (en gras, la meilleure action) :
| \(k\) | case | \(Q_k(\cdot,\text{gauche})\) | \(Q_k(\cdot,\text{droite})\) | \(V_k\) | meilleure |
|---|---|---|---|---|---|
| 1 | 1 | \(\mathbf{0{,}8}\) | \(0\) | \(0{,}8\) | gauche |
| 1 | 2 | \(0\) | \(0\) | \(0\) | égalité |
| 1 | 3 | \(0\) | \(\mathbf{3{,}2}\) | \(3{,}2\) | droite |
| 2 | 1 | \(\mathbf{0{,}944}\) | \(0{,}144\) | \(0{,}944\) | gauche |
| 2 | 2 | \(0{,}576\) | \(\mathbf{2{,}304}\) | \(2{,}304\) | droite |
| 2 | 3 | \(0{,}576\) | \(\mathbf{3{,}776}\) | \(3{,}776\) | droite |
| 3 | 1 | \(0{,}9699\) | \(\mathbf{1{,}8288}\) | \(1{,}8288\) | droite |
| 3 | 2 | \(1{,}0944\) | \(\mathbf{3{,}1334}\) | \(3{,}1334\) | droite |
| 3 | 3 | \(2{,}3386\) | \(\mathbf{3{,}8797}\) | \(3{,}8797\) | droite |
| \(k\) | \(V_k(\text{1})\) | \(V_k(\text{2})\) | \(V_k(\text{3})\) | écart |
|---|---|---|---|---|
| 0 | \(0\) | \(0\) | \(0\) | – |
| 1 | \(\mathbf{0{,}8}\) | \(0\) | \(\mathbf{3{,}2}\) | \(3{,}2\) |
| 2 | \(\mathbf{0{,}944}\) | \(\mathbf{2{,}304}\) | \(\mathbf{3{,}776}\) | \(2{,}304\) |
| 3 | \(\mathbf{1{,}8288}\) | \(\mathbf{3{,}1334}\) | \(\mathbf{3{,}8797}\) | \(0{,}8848\) |
À l’itération 1, seules les cases voisines d’un terminal gagnent quelque chose : case 1, \(0{,}8\times1=0{,}8\) en allant à gauche ; case 3, \(0{,}8\times4=3{,}2\) en allant à droite ; la case 2 reste à 0 (égalité). À l’itération 2, la case 2 voit la valeur de la case 3 : \(Q_2(2,\text{d})=0{,}8\times0{,}9\times3{,}2=2{,}304\), contre \(0{,}8\times0{,}9\times0{,}8=0{,}576\) vers la gauche. La case 1 reste tournée vers Kermel (\(0{,}8+0{,}2\times0{,}9\times0{,}8=0{,}944\) contre \(0{,}144\)). À l’itération 3, la valeur de Tilène a atteint la case 2 : \(Q_3(1,\text{d})=0{,}8\times0{,}9\times2{,}304+0{,}2\times0{,}9\times0{,}944=1{,}8288\) dépasse \(Q_3(1,\text{g})=0{,}9699\), et la case 1 change d’avis. La politique gloutonne peut donc changer pendant les itérations : elle n’est fiable qu’une fois les valeurs proches de leur limite.
(d) Pour la politique « droite » partout, avec \(\gamma=0{,}9\), les équations de Bellman sont linéaires : \[V(3)=0{,}8\times4+0{,}18\,V(3),\qquad V(2)=0{,}72\,V(3)+0{,}18\,V(2),\qquad V(1)=0{,}72\,V(2)+0{,}18\,V(1).\] D’où \(V(3)=3{,}2/0{,}82=160/41\approx3{,}902\), puis \(V(2)=\frac{0{,}72}{0{,}82}V(3)=5760/1681\approx3{,}427\) et \(V(1)=\frac{0{,}72}{0{,}82}V(2)=207360/68921\approx3{,}009\). Chaque case vaut \(0{,}72/0{,}82\approx0{,}878\) fois sa voisine de droite. Pour vérifier l’optimalité, on calcule les valeurs des deux actions avec ces \(V^*\) :
| \(Q\) | gauche | droite |
|---|---|---|
| case 1 | \(1{,}342\) | \(\mathbf{3{,}009}\) |
| case 2 | \(2{,}783\) | \(\mathbf{3{,}427}\) |
| case 3 | \(3{,}17\) | \(\mathbf{3{,}902}\) |
Dans chaque case, « droite » l’emporte : aucune action ne fait mieux que la politique, qui satisfait donc l’équation de Bellman avec le \(\max\) ; elle est optimale.
(e) Avec \(\gamma=0{,}5\), l’itération converge en 7 itérations :
| \(k\) | \(V_k(\text{1})\) | \(V_k(\text{2})\) | \(V_k(\text{3})\) | écart |
|---|---|---|---|---|
| 0 | \(0\) | \(0\) | \(0\) | – |
| 1 | \(\mathbf{0{,}8}\) | \(0\) | \(\mathbf{3{,}2}\) | \(3{,}2\) |
| 2 | \(\mathbf{0{,}88}\) | \(\mathbf{1{,}28}\) | \(\mathbf{3{,}52}\) | \(1{,}28\) |
| 3 | \(\mathbf{0{,}888}\) | \(\mathbf{1{,}536}\) | \(\mathbf{3{,}552}\) | \(0{,}256\) |
| 4 | \(\mathbf{0{,}8888}\) | \(\mathbf{1{,}5744}\) | \(\mathbf{3{,}5552}\) | \(0{,}0384\) |
| 5 | \(\mathbf{0{,}8889}\) | \(\mathbf{1{,}5795}\) | \(\mathbf{3{,}5555}\) | \(0{,}00512\) |
| 6 | \(\mathbf{0{,}8889}\) | \(\mathbf{1{,}5802}\) | \(\mathbf{3{,}5556}\) | \(0{,}00064\) |
| 7 | \(\mathbf{0{,}8889}\) | \(\mathbf{1{,}5802}\) | \(\mathbf{3{,}5556}\) | \(0{,}00008\) |
| \(Q\) | gauche | droite |
|---|---|---|
| case 1 | \(\mathbf{0{,}889}\) | \(0{,}721\) |
| case 2 | \(0{,}514\) | \(\mathbf{1{,}58}\) |
| case 3 | \(0{,}988\) | \(\mathbf{3{,}556}\) |
En case 1, \(Q^*(1,\text{g})=0{,}8/(1-0{,}2\times0{,}5)=8/9\approx0{,}889\) dépasse \(Q^*(1,\text{d})=0{,}721\) : Cheikh va à Kermel. Les cases 2 et 3 restent tournées vers Tilène (\(V^*(2)=128/81\approx1{,}580\), \(V^*(3)=32/9\approx3{,}556\)). La grosse livraison est à trois pas de la case 1 ; avec \(\gamma=0{,}5\), chaque pas divise sa valeur par plus de deux, et la petite livraison voisine devient préférable. Le facteur d’actualisation retourne à lui seul une décision quand récompenses et distances diffèrent.
Erreur fréquente. Mettre à jour les cases avec les valeurs déjà recalculées dans la même itération (par exemple utiliser \(V_2(3)\) pour calculer \(V_2(2)\)) : on obtient une autre méthode, et d’autres nombres. Autre erreur : oublier le terme de la glissade (\(0{,}2\,\gamma V(s)\)), ou ajouter la récompense de Tilène à la valeur de Tilène, alors qu’un terminal vaut 0 et que la récompense est versée à l’arrivée.
Exercice 2 : le Q-learning dans la rue
Cheikh ne connaît pas la probabilité 0,8 ; il apprend en livrant. Dans la même rue, avec \(\alpha=0{,}5\), \(\gamma=0{,}9\) et \(Q=0\) au départ, il vit trois épisodes (\(d\) : droite, \(g\) : gauche, \(K\) : Kermel, \(T\) : Tilène) : (1) \((2,d,0,3)\), \((3,d,4,T)\) ; (2) \((1,d,0,1)\), \((1,d,0,2)\), \((2,d,0,3)\), \((3,d,4,T)\) ; (3) \((2,g,0,1)\), \((1,g,1,K)\).
- Que signifie la transition \((1,d,0,1)\) ?
- Appliquer la règle du Q-learning à chaque transition, dans l’ordre, et donner la table \(Q\) finale.
- En déduire la politique gloutonne et la comparer à la politique optimale de l’exercice 1 (\(\gamma=0{,}9\)).
- Avec \(\varepsilon=0{,}2\) et une stratégie \(\varepsilon\)-gloutonne, quelle est, en case 1, la probabilité de jouer « droite » au prochain passage ?
Méthode. Pour chaque transition \((s,a,r,s')\) : lire \(\max_bQ(s',b)\) dans la table actuelle (0 si \(s'\) est terminal), former la cible \(r+0{,}9\max_bQ(s',b)\), puis \(Q(s,a)\leftarrow Q(s,a)+0{,}5\,(\text{cible}-Q(s,a))\).
(a) Cheikh a voulu aller à droite depuis la case 1 et il est resté en case 1 : une glissade. L’agent ne sait pas qu’elle a la probabilité 0,2 ; il constate seulement ce qui s’est passé.
(b)
| épisode | \((s,a,r,s')\) | \(\max_b Q(s',b)\) | cible | \(Q(s,a)\) | |
|---|---|---|---|---|---|
| 1 | 1 | \((2,\text{droite},0,3)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 2 | 1 | \((3,\text{droite},4,T)\) | \(0\) | \(4\) | \(0\to\mathbf{2}\) |
| 3 | 2 | \((1,\text{droite},0,1)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 4 | 2 | \((1,\text{droite},0,2)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 5 | 2 | \((2,\text{droite},0,3)\) | \(2\) | \(1{,}8\) | \(0\to\mathbf{0{,}9}\) |
| 6 | 2 | \((3,\text{droite},4,T)\) | \(0\) | \(4\) | \(2\to\mathbf{3}\) |
| 7 | 3 | \((2,\text{gauche},0,1)\) | \(0\) | \(0\) | \(0\to\mathbf{0}\) |
| 8 | 3 | \((1,\text{gauche},1,K)\) | \(0\) | \(1\) | \(0\to\mathbf{0{,}5}\) |
La transition 1 n’apprend rien : la case 3 vaut encore 0. La récompense de Tilène apparaît à la transition 2 : \(Q(3,d)=0{,}5\times4=2\). Au deuxième épisode, les deux mises à jour de \(Q(1,d)\) restent nulles, car \(\max Q(1,\cdot)\) puis \(\max Q(2,\cdot)\) valent 0 à ce moment ; \(Q(2,d)\) reçoit \(0{,}5\times0{,}9\times2=0{,}9\), et \(Q(3,d)\) monte à \(2+0{,}5\times(4-2)=3\). Au troisième épisode, \(Q(2,g)\) reste nulle (la case 1 vaut encore 0) et Kermel donne \(Q(1,g)=0{,}5\times1=0{,}5\).
| \(Q\) | gauche | droite |
|---|---|---|
| case 1 | \(\mathbf{0{,}5}\) | \(0\) |
| case 2 | \(0\) | \(\mathbf{0{,}9}\) |
| case 3 | \(0\) | \(\mathbf{3}\) |
(c) En case 1, « gauche » (0,5) l’emporte sur « droite » (0) ; en cases 2 et 3, « droite ». La politique optimale (exercice 1) va à droite partout, avec \(Q^*(1,\text{d})=3{,}009\) contre \(Q^*(1,\text{g})=1{,}342\). L’écart ne vient pas d’une erreur de calcul : la valeur de Tilène n’a pas encore remonté jusqu’à la case 1, faute de passages. Avec des centaines d’épisodes et de l’exploration, \(Q(1,d)\) dépasserait \(Q(1,g)\).
(d) L’action gloutonne en case 1 est « gauche ». « Droite » n’est jouée que par l’exploration : avec la probabilité 0,2, une action tirée au hasard parmi les deux, d’où \(0{,}2\times\frac12=0{,}1\).
Erreur fréquente. Mettre à jour en remontant l’épisode depuis la fin : la récompense se propagerait jusqu’à la case 1 dès le deuxième épisode, mais ce n’est plus la règle du Q-learning, qui suit l’ordre chronologique. Autre erreur : prendre \(Q(s',a)\), la valeur de l’action jouée, au lieu de \(\max_bQ(s',b)\).
Exercice 3 : la descente de gradient sur les livraisons de Cheikh
Cheikh a livré à 1, 2 et 3 km en 3, 8 et 10 minutes. Il modélise la durée par \(w\times\)distance et cherche \(w\) (en minutes par kilomètre) qui minimise \(J(w)=\frac13\sum_i(y_i-wx_i)^2\), en partant de \(w_0=0\).
- Calculer \(J'(w)\) et le minimum \(w^*\).
- Faire trois pas de descente de gradient avec \(\eta=0{,}05\), en donnant \(w_k\), \(J'(w_k)\) et \(J(w_k)\).
- Faire trois pas avec \(\eta=0{,}25\). Que se passe-t-il ?
- Montrer que \(w_{k+1}-w^*=(1-\frac{28}{3}\eta)(w_k-w^*)\) et en déduire les valeurs de \(\eta\) pour lesquelles la descente converge. Quel taux donne la convergence la plus rapide ?
(a) \(\sum_ix_i^2=1+4+9=14\) et \(\sum_ix_iy_i=3+16+30=49\). Donc \[J'(w)=-\frac23\sum_ix_i(y_i-wx_i)=\frac23(14w-49),\] nulle en \(w^*=49/14=3{,}5\) min/km ; \(J(3{,}5)=\frac13(0{,}25+1+0{,}25)=0{,}5\). Au départ, \(J(0)=\frac13(9+64+100)=57{,}6667\) et \(J'(0)=-98/3\approx-32{,}6667\).
(b) La règle \(w_k=w_{k-1}-\eta J'(w_{k-1})\) avec \(\eta=0{,}05\) :
| \(k\) | \(w_{k-1}\) | \(J'(w_{k-1})\) | \(w_k\) | \(w_k-w^*\) | \(J(w_k)\) |
|---|---|---|---|---|---|
| 1 | \(0\) | \(-32{,}6667\) | \(1{,}6333\) | \(-1{,}8667\) | \(16{,}7607\) |
| 2 | \(1{,}6333\) | \(-17{,}4222\) | \(2{,}5044\) | \(-0{,}9956\) | \(5{,}1253\) |
| 3 | \(2{,}5044\) | \(-9{,}2919\) | \(2{,}969\) | \(-0{,}531\) | \(1{,}8156\) |
\(w_1=0-0{,}05\times(-32{,}6667)=49/30\approx1{,}6333\) ; puis \(w_2=1127/450\approx2{,}5044\) et \(w_3=20041/6750\approx2{,}9690\). Le coût diminue à chaque pas (57,67, puis 16,76, 5,13, 1,82) ; l’écart à \(w^*\) est multiplié par \(8/15\approx0{,}533\) à chaque pas.
(c) Avec \(\eta=0{,}25\) :
| \(k\) | \(w_{k-1}\) | \(J'(w_{k-1})\) | \(w_k\) | \(w_k-w^*\) | \(J(w_k)\) |
|---|---|---|---|---|---|
| 1 | \(0\) | \(-32{,}6667\) | \(8{,}1667\) | \(4{,}6667\) | \(102{,}1296\) |
| 2 | \(8{,}1667\) | \(43{,}5556\) | \(-2{,}7222\) | \(-6{,}2222\) | \(181{,}1749\) |
| 3 | \(-2{,}7222\) | \(-58{,}0741\) | \(11{,}7963\) | \(8{,}2963\) | \(321{,}6998\) |
Le premier pas, \(w_1=0{,}25\times32{,}6667=8{,}1667\), dépasse largement \(w^*\) ; la pente devient positive et le pas suivant renvoie \(w\) à \(-2{,}7222\), puis à \(11{,}7963\). Le coût augmente (102, 181, 322) : la descente diverge.
(d) \(J'(w)=\frac{28}{3}(w-w^*)\), donc \(w_{k+1}-w^*=w_k-w^*-\eta\frac{28}{3}(w_k-w^*)=(1-\frac{28}{3}\eta)(w_k-w^*)\). L’écart tend vers 0 si et seulement si \(|1-\frac{28}{3}\eta|<1\), soit \(0<\eta<\frac{6}{28}=\frac{3}{14}\approx0{,}214\). Pour \(\eta=0{,}05\) le facteur vaut \(8/15\), pour \(\eta=0{,}25\) il vaut \(-4/3\), d’où la divergence. Le facteur s’annule pour \(\eta=3/28\approx0{,}107\) : un seul pas atteint alors \(w^*\). Avec \(\eta=0{,}1\), proche de cette valeur, le facteur vaut \(1/15\) :
| \(k\) | \(w_{k-1}\) | \(J'(w_{k-1})\) | \(w_k\) | \(w_k-w^*\) | \(J(w_k)\) |
|---|---|---|---|---|---|
| 1 | \(0\) | \(-32{,}6667\) | \(3{,}2667\) | \(-0{,}2333\) | \(0{,}7541\) |
| 2 | \(3{,}2667\) | \(-2{,}1778\) | \(3{,}4844\) | \(-0{,}0156\) | \(0{,}5011\) |
| 3 | \(3{,}4844\) | \(-0{,}1452\) | \(3{,}499\) | \(-0{,}001\) | \(0{,}5\) |
Erreur fréquente. Ajouter le gradient au lieu de le soustraire (on monte au lieu de descendre), ou oublier le facteur 2 de la dérivée du carré. Autre erreur : croire qu’un taux plus grand converge toujours plus vite : au-delà de \(3/28\), la descente oscille, et au-delà de \(3/14\), elle diverge.
À retenir
- Le MEU choisit \(a^*=\arg\max_a\sum_sP(s\mid\mathbf e)\,U(s)\) ; l’asymétrie des utilités fixe le seuil de décision (0,060 pour Fatou, 0,820 avec un traitement risqué).
- Un processus de décision markovien a cinq ingrédients : états, actions, transitions, récompenses, facteur d’actualisation ; l’état présent résume le passé utile ; on cherche une politique, pas un chemin.
- Le facteur d’actualisation \(\gamma\) fixe la prévoyance de l’agent : la route longue est préférée dès que \(\gamma>0{,}837\).
- L’équation de Bellman, \(V^*(s)=\max_a[R(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^*(s')]\), est un MEU récursif ; \(V^*=\max_aQ^*\) et \(\pi^*=\arg\max_aQ^*\).
- L’itération sur les valeurs propage les récompenses d’un pas par itération et converge parce que l’opérateur de Bellman est une contraction de facteur \(\gamma\) ; elle exige le modèle.
- Le Q-learning apprend \(Q^*\) sans modèle : \(Q\leftarrow Q+\alpha\,(r+\gamma\max Q(s',\cdot)-Q)\), dans l’ordre des transitions vécues, avec une exploration \(\varepsilon\)-gloutonne.
- La descente de gradient, \(\boldsymbol\theta\leftarrow\boldsymbol\theta-\eta\nabla J(\boldsymbol\theta)\), est le hill climbing des paramètres continus ; un taux trop grand diverge ; le Q-learning en est un cas particulier, sur une table.
Prochaine séance
Les modèles de ce cours ont été posés à la main : les probabilités de la Séance 5, les transitions et les récompenses de cette séance. Le cours d’Introduction au Machine Learning les apprend à partir de données : régression, classification, réseaux de neurones, tous réglés par la descente de gradient.
Références
- Russell, Norvig — Artificial Intelligence: A Modern Approach, 4e éd., Pearson, 2020 (chap. 16, 17 et 22).
- Sutton, Barto — Reinforcement Learning: An Introduction, 2e éd., MIT Press, 2018.
- Bellman — Dynamic Programming, Princeton University Press, 1957.
- Watkins, Dayan — « Q-learning », Machine Learning, 8, 1992.
- Mnih et al. — « Human-level control through deep reinforcement learning », Nature, 518, 2015.
- Poole, Mackworth — Artificial Intelligence: Foundations of Computational Agents, 3e éd., Cambridge University Press, 2023.
- Goodfellow, Bengio, Courville — Deep Learning, MIT Press, 2016.
Pour cette séance
Les slides
À lire en ligne
À télécharger
- Code de départ du TP (ZIP, 4 Ko)