Processus de décision markoviens et apprentissage par renforcement

Un processus de décision markovien décrit des décisions répétées lorsque les actions peuvent produire des résultats incertains. L'agent observe son état courant, choisit une action disponible, reçoit une récompense et passe à un nouvel état. Ces quatre éléments décrivent une transition ; une suite de transitions décrit une trajectoire.

Lire un modèle de transition

L'ensemble des états est $S$ et $A(s)$ énumère les actions autorisées dans l'état $s$. Le modèle de transition $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ donne la probabilité d'atteindre $s^{\mathrm{\prime }}$ après avoir effectué $a$ en $s$. Pour chaque paire état-action, toutes ces probabilités sont positives ou nulles et leur somme vaut 1. La récompense $R(s,a,s^{\mathrm{\prime }})$ est associée à cette transition. Une récompense négative représente un coût ou une pénalité.

Considère un robot de livraison dont les états sont Batterie haute, Batterie faible et Hors service. Hors service met fin à l'épisode. Son modèle est le suivant :

Dans chacune des deux lignes Travailler, la somme des probabilités vaut 1. Pour Travailler en Batterie faible, l'espérance de récompense immédiate est $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$. Cette moyenne est utile pour planifier, mais une tentative réelle rapporte soit 4, soit −10. Choisir Travailler détermine la distribution ; cela ne sélectionne pas le résultat favorable.

Inclure le passé pertinent dans l'état

La propriété de Markov signifie que l'état et l'action actuels contiennent les informations nécessaires pour prédire l'état suivant :

Le monde peut avoir une longue histoire. Celle-ci intervient par l'intermédiaire des variables incluses dans l'état courant. La seule position d'un robot peut être insuffisante si sa batterie détermine la réussite d'une livraison. Inclure le niveau de batterie permet au modèle de distinguer des situations présentant des risques différents.

Un processus de décision markovien standard suppose que l'agent observe exactement l'état. Si des parties importantes de l'état sont cachées, l'agent a besoin d'une croyance sur les états possibles ; cela mène à un processus de décision markovien partiellement observable.

Reconnaître les fins et les déplacements aléatoires

Un état terminal a une valeur de 0, car aucune récompense ne le suit. La récompense reçue en y entrant compte toujours : le robot reçoit −10 lors de sa dernière transition vers Hors service. Les tâches épisodiques se terminent dans un état terminal ; les tâches continues, comme la gestion permanente d'une température, n'ont pas besoin d'état terminal.

Dans un monde en grille, un déplacement prévu peut réussir avec une probabilité de 0,8 ou dévier dans l'une des deux directions perpendiculaires avec une probabilité de 0,1 chacune. Une tentative de déplacement vers un mur laisse l'agent sur place. Il faut additionner les probabilités des résultats qui mènent à une même case.

Les transitions déterministes sont un cas particulier : un seul successeur a une probabilité de 1. Pour un départ connu et une tâche adaptée qui consiste à atteindre un but, un plan fixe peut suffire. Lorsque les résultats sont incertains, une politique précise comment réagir dans l'état qui se présente effectivement. Certains ouvrages écrivent les récompenses sous la forme $R(s)$ ou $R(s,a)$ ; vérifie la convention relative au moment où elles sont reçues avant de reprendre une formule.

Une politique décrit la façon dont l'agent agit. Une politique déterministe et stationnaire $\pi (s)$ choisit une action pour chaque état et conserve ce choix au cours du temps. Pour le robot, « Travailler en Batterie haute, Recharger en Batterie faible » est une telle politique. Une politique stochastique $\pi (a\mid s)$ attribue des probabilités aux actions disponibles.

Calculer un gain

Le gain cumulé actualisé combine les récompenses d'une trajectoire :

La première transition rapporte $r_0$ avec un poids de 1. Chaque récompense ultérieure reçoit un facteur supplémentaire d'actualisation $\gamma$. Pour les récompenses −1, −1, −1 et +10 suivies d'une fin d'épisode, avec $\gamma =\mathrm{0,9}$, on obtient

Avec $\gamma =\mathrm{0,5}$, la même trajectoire donne $-1-\mathrm{0,5}-\mathrm{0,25}+10(\mathrm{0,125})=-\mathrm{0,5}$. Le gain différé perd une grande partie de son poids. L'actualisation peut représenter une préférence pour les récompenses précoces ou la probabilité que le processus se poursuive pendant une étape supplémentaire.

Une politique est évaluée selon son espérance de gain, calculée en faisant la moyenne sur ses trajectoires possibles. Une trajectoire chanceuse ne suffit pas à établir qu'une politique est bonne. Une politique optimale ${\pi }^{\ast }$ donne l'espérance de gain la plus élevée à partir de chaque état. Un processus de décision markovien fini et actualisé possède une politique optimale déterministe et stationnaire.

Garder une valeur finie pour un futur infini

Pour des récompenses bornées et $0\le \gamma <1$, la série géométrique permet de borner chaque gain. Si $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, alors

La plus grande valeur absolue d'une récompense du robot est 10 ; avec $\gamma =\mathrm{0,9}$, on obtient donc $\mathrm{\mid }U\mathrm{\mid }\le 100$. Comme sa plus grande récompense positive est 4, son gain ne peut pas non plus dépasser $4\mathrm{/}(1-\mathrm{0,9})=40$. Ce sont des bornes, qui n'affirment pas que le robot peut les atteindre.

La quantité $1\mathrm{/}(1-\gamma )$ donne un horizon effectif approximatif : environ 10 étapes pour $\gamma =\mathrm{0,9}$. Ce n'est pas une coupure. Une récompense reçue 10 étapes plus tard conserve un poids de ${\mathrm{0,9}}^{10}\approx \mathrm{0,35}$. Les tâches continues sans actualisation exigent une attention particulière : des récompenses positives répétées peuvent rendre les gains infinis. Un horizon fini fixe rend la somme finie ; les modèles épisodiques nécessitent aussi des durées d'épisode adaptées pour obtenir des espérances finies.

Tenir compte du temps et des récompenses par étape

Avec une échéance, la meilleure action peut dépendre du temps restant. Considère une machine à l'état Usée. Mettre en marche rapporte 6 et laisse la machine Usée ou En panne avec des probabilités égales. Réparer rapporte −4 et la remet en Bon état. En Bon état, Mettre en marche rapporte 10 ; dans l'état En panne, Réparer rapporte −20. S'il reste une étape, en Usée, Mettre en marche est préférable : $6>-4$. S'il reste deux étapes et si $\gamma =\mathrm{0,9}$, Réparer donne $-4+\mathrm{0,9}(10)=5$. Mettre en marche donne $6+\mathrm{0,9}[\mathrm{0,5}(6)+\mathrm{0,5}(-20)]=-\mathrm{0,3}$. Le temps supplémentaire inverse le choix.

Dans un monde en grille, la récompense de survie, obtenue aux étapes non terminales, modifie le coût de l'attente. Des récompenses négatives par étape encouragent l'accès à une sortie ; une pénalité plus élevée peut rendre préférable une mauvaise sortie proche plutôt qu'un long trajet. Une récompense positive par étape suffisamment élevée peut favoriser le maintien dans la grille. Le choix exact dépend aussi de l'actualisation, des distances et des risques de déviation.

Formuler un processus de décision markovien transforme un objectif pratique en décisions qu'un ordinateur peut évaluer. Commence par choisir quand les décisions sont prises. Définis ensuite un état observable, les actions autorisées, les probabilités de transition, les récompenses, les éventuels états terminaux et un facteur d'actualisation ou un horizon. La qualité de la politique obtenue dépend de ces choix.

Modéliser la maintenance d'une machine

Supposons qu'une machine soit inspectée une fois par étape de décision. Son état est Bon état, Usée ou En panne. Le modèle est le suivant :

En panne n'est pas terminal : la réparation permet de poursuivre le travail. La tâche est continue, avec $\gamma =\mathrm{0,9}$. Remarque que les actions disponibles dépendent de l'état ; Mettre en marche n'est pas disponible dans l'état En panne.

La résolution de ce modèle donne des valeurs optimales d'environ 78,64 en Bon état, 66,78 en Usée et 50,78 dans l'état En panne. En Usée, Réparer a pour valeur $-4+\mathrm{0,9}(\mathrm{78,64})\approx \mathrm{66,78}$. Mettre en marche a pour valeur $6+\mathrm{0,9}[\mathrm{0,5}(\mathrm{66,78})+\mathrm{0,5}(\mathrm{50,78})]\approx \mathrm{58,90}$. La récompense immédiate négative de la réparation permet d'accéder à un futur plus productif.

Inclure assez d'informations dans l'état

L'état doit permettre de prédire les résultats et les récompenses. La position seule d'une balle en mouvement omet sa vitesse : deux positions identiques peuvent donc être suivies de positions différentes. Dans un jeu de plateau, l'état doit aussi préciser à qui est le tour. Si le temps restant modifie les actions avantageuses, inclus-le dans une règle de décision à horizon fini ou ajoute-le à l'état.

Les variables supplémentaires agrandissent l'espace d'états. Dix variables oui/non permettent $2^{10}=1024$ combinaisons. Garde les informations qui modifient les prédictions ou les récompenses ; stocker tout l'historique peut rendre inutilement volumineux un modèle exploitable. Le processus de décision markovien stationnaire usuel suppose que les règles de transition et de récompense restent les mêmes au cours du temps. Un état caché appelle un modèle de croyance, tandis que des adversaires stratégiques appellent un modèle de jeu.

Faire exprimer l'objectif par la récompense

Un robot de nettoyage récompensé pour chaque déchet ramassé peut tirer profit du fait de répandre des déchets et de les ramasser à nouveau. C'est un détournement de la récompense : l'optimisation réussie d'une mauvaise mesure. Une récompense liée à la propreté recherchée évite cette boucle particulière. Une récompense éparse attribuée au but exprime clairement la réussite, mais fournit peu de retours pendant une longue tentative.

Le façonnage de la récompense ajoute des retours sur les progrès. Des bonus arbitraires peuvent modifier l'objectif. Deux comparaisons utiles :

• Multiplier toutes les récompenses par un même nombre positif conserve le classement des politiques.
• Ajouter une constante à chaque récompense conserve les politiques optimales dans une tâche continue actualisée, car chaque politique gagne la même constante actualisée. Dans une tâche épisodique, les trajectoires longues et courtes gagnent des montants différents : le classement peut donc changer.

Un terme de façonnage qui conserve les politiques a la forme $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Ici, $\mathrm{\Phi }$ attribue un potentiel à chaque état. Avec des potentiels bornés dans une tâche continue actualisée, les termes actualisés ajoutés s'annulent, à l'exception d'un décalage lié à l'état initial. Pour les tâches épisodiques, fixer à 0 le potentiel de chaque état terminal supprime le terme terminal restant. Un potentiel terminal non nul peut modifier la fin ou le moment d'arrêt préféré.

Une valeur mesure le gain que l'on peut obtenir à partir d'une situation en adoptant une façon d'agir donnée. Elle inclut les récompenses futures, pondérées selon leurs probabilités et le moment où elles sont reçues. Les valeurs diffèrent ainsi de la récompense obtenue lors d'une seule transition.

Distinguer le choix initial

La valeur d'état $V^{\pi }(s)$ est l'espérance de gain cumulé actualisé en partant de l'état $s$ et en suivant la politique $\pi$. La valeur d'action $Q^{\pi }(s,a)$ fixe la première action à $a$, puis suit $\pi$ par la suite. Elle ne signifie pas que l'action $a$ est effectuée à toutes les étapes ultérieures.

Les valeurs optimales remplacent cette politique suivie ensuite par le meilleur comportement possible. Ainsi, $V^{\ast }(s)$ est la meilleure espérance de gain à partir de $s$ et $Q^{\ast }(s,a)$ la meilleure espérance de gain une fois la première action fixée. Leur relation est

Le maximum est un nombre ; l'argmax désigne une action qui l'atteint. Si plusieurs actions sont ex æquo, chacune d'elles peut être choisie.

Interpréter les choix du robot

Pour le robot de livraison avec $\gamma =\mathrm{0,9}$, les valeurs Q optimales sont :

Le maximum de chaque ligne est la valeur optimale de l'état. En Batterie haute, Travailler est préférable ; en Batterie faible, Recharger est préférable. Recharger rapporte immédiatement 0, mais en Batterie faible, cette action redonne accès à Batterie haute et à ses meilleures perspectives. Travailler en Batterie faible a tout de même une valeur Q optimale positive, car un robot encore en service peut se recharger ensuite.

La politique suivie par la suite compte. Avec « toujours Travailler », les valeurs d'état tombent à environ 8,27 en Batterie haute et −3,48 en Batterie faible. Le modèle n'a pas changé ; ce sont les décisions prises après chaque résultat qui ont changé. Un nombre présenté uniquement comme « la valeur » est incomplet si la politique considérée ou l'optimalité ne sont pas précisées.

Séparer les choix et le hasard en deux niveaux

Un arbre expectimax alterne deux types de nœuds. Dans un état, l'agent choisit une action ; pour une paire état-action, parfois appelée état Q, le hasard choisit l'état suivant selon le modèle de transition. L'agent maximise sur les actions et calcule une moyenne sur leurs résultats.

Un processus de décision markovien cyclique répète les mêmes états en de nombreux endroits de l'arbre. La programmation dynamique stocke une valeur pour chaque état et la réutilise. Cela évite de recalculer le même problème pour la suite chaque fois qu'un chemin de l'arbre revient à cet état.

Extraire une politique des valeurs disponibles

Avec une table Q, compare les valeurs d'action de la ligne courante. Aucun modèle de transition n'est nécessaire. Avec les seules valeurs d'état, calcule d'abord l'espérance de la récompense d'une action ajoutée à la valeur actualisée du successeur :

Ce calcul nécessite les transitions et les récompenses. Se contenter de choisir l'action qui peut atteindre le successeur de plus grande valeur revient à ignorer la probabilité d'atteindre ce successeur et le coût de l'action. Une espérance élevée laisse aussi place à une trajectoire malchanceuse : elle décrit une moyenne sur les résultats, et non une récompense garantie à chaque tentative.

Le gain d'une trajectoire peut être décomposé après sa première transition : la récompense immédiate plus le gain actualisé à partir de l'état suivant. Prendre une espérance donne une équation de Bellman. Elle relie la valeur d'un état à celles de ses successeurs, y compris lorsque l'état suivant peut être le même.

Évaluer une politique fixe

Pour une politique déterministe, seule l'action qu'elle choisit apparaît :

Chaque branche contribue à hauteur de sa probabilité multipliée par la somme de sa récompense immédiate et de sa valeur future. Il y a une équation par état. Dans un processus de décision markovien fini et actualisé, ce sont des équations linéaires qui ont une solution unique.

Pour la politique « toujours Travailler » du robot, partons de Batterie faible. Les deux transitions possibles donnent

Développons et regroupons les termes contenant l'inconnue : $V(L)=\mathrm{2,4}+\mathrm{0,54}V(L)-4$, donc $\mathrm{0,46}V(L)=-\mathrm{1,6}$. Ainsi, $V(L)\approx -\mathrm{3,48}$. La récompense de −10 demeure, même si la valeur future de Hors service est 0.

En Batterie haute, les deux résultats rapportent 4 : leurs récompenses immédiates se combinent donc en 4 :

En regroupant les termes, on obtient $\mathrm{0,37}V(H)=4+\mathrm{0,27}V(L)$. La valeur non arrondie de Batterie faible donne $V(H)\approx \mathrm{8,27}$. Garde toutes les décimales pendant les substitutions ; arrondis les valeurs indiquées à la fin.

Ajouter le choix de l'action

Pour les valeurs optimales, calcule l'espérance de chaque action disponible, puis prends la meilleure :

Le maximum se trouve à l'extérieur de la somme, car l'agent choisit une action avant de voir le résultat. Choisir une action courante différente pour chaque état suivant possible lui donnerait une information qu'il ne possède pas encore.

La forme Q fixe cette première action, mais permet de choisir la meilleure action suivante après avoir observé le successeur :

Ces équations d'optimalité contiennent des maximums : une seule résolution linéaire pour une politique fixe ne permet donc pas de les résoudre directement.

Vérifier les valeurs proposées

Utilise les valeurs optimales proposées pour le robot, $V(H)\approx \mathrm{31,50}$ et $V(L)\approx \mathrm{28,35}$. En Batterie haute, Travailler donne $4+\mathrm{0,9}[\mathrm{0,7}(\mathrm{31,50})+\mathrm{0,3}(\mathrm{28,35})]\approx \mathrm{31,50}$. Recharger donne $\mathrm{0,9}(\mathrm{31,50})=\mathrm{28,35}$. Le plus grand résultat correspond à la valeur proposée pour Batterie haute.

En Batterie faible, Travailler donne $\mathrm{0,6}[4+\mathrm{0,9}(\mathrm{28,35})]+\mathrm{0,4}(-10)\approx \mathrm{13,71}$ ; Recharger donne 28,35. Le maximum correspond aussi à la valeur proposée pour Batterie faible. Vérifier un seul état laisserait l'autre équation sans contrôle. De petits écarts sont attendus lorsque les valeurs proposées ont été arrondies.

Actualise uniquement le terme futur. Remplacer $R+\gamma V$ par $\gamma (R+V)$ reporte à tort la récompense immédiate d'une étape.

L'évaluation de politique cherche l'espérance de gain d'une politique fixe. Le modèle et la politique sont connus. Aucun choix d'action n'est amélioré pendant ce calcul ; le résultat est $V^{\pi }$, qui peut ensuite servir à une étape d'amélioration distincte.

Résoudre exactement les équations

Prenons la politique « Travailler en Batterie haute, Recharger en Batterie faible » et $\gamma =\mathrm{0,9}$. Recharger en Batterie faible ne donne aucune récompense immédiate et mène toujours à Batterie haute, donc $V(L)=\mathrm{0,9}V(H)$. Travailler en Batterie haute donne

Substituons la première équation dans la seconde :

On obtient alors $\mathrm{0,127}V(H)=4$, d'où $V(H)=4\mathrm{/}\mathrm{0,127}\approx \mathrm{31,50}$ et $V(L)\approx \mathrm{28,35}$. Cela établit les valeurs de cette politique. Pour prouver qu'elle est optimale, il faut aussi vérifier les autres actions.

L'évaluation exacte résout une équation linéaire par état non terminal. Une élimination classique sur un système dense coûte de l'ordre de $\mathrm{\mid }S{\mathrm{\mid }}^3$ opérations. La méthode convient à un petit modèle, car les relations peuvent être examinées directement.

Évaluer par balayages répétés

Une méthode itérative part de $V_0(s)=0$ et applique la mise à jour pour la politique fixe à chaque état :

Chaque nouvelle valeur utilise le tableau précédent. Pour « toujours Travailler », les trois premiers balayages, dans l'ordre Batterie haute puis Batterie faible, donnent :

Par exemple, la deuxième valeur de Batterie faible est $\mathrm{0,6}[4+\mathrm{0,9}(-\mathrm{1,6})]+\mathrm{0,4}(-10)=-\mathrm{2,464}$. Pour Batterie haute, ce même balayage utilise les anciennes valeurs 4 pour Batterie haute et −1,6 pour Batterie faible, ce qui donne $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(-\mathrm{1,6})]=\mathrm{6,088}$.

Avec un facteur d'actualisation inférieur à 1, les balayages convergent vers environ 8,27 et −3,48. Un balayage dense pour une politique fixe coûte de l'ordre de $\mathrm{\mid }S{\mathrm{\mid }}^2$ opérations, car chaque état fait la somme sur ses successeurs. Les modèles de transition creux peuvent ignorer les successeurs de probabilité 0.

Interpréter les valeurs intermédiaires

En partant de zéro, $V_k(s)$ est l'espérance de récompense cumulée actualisée sur les $k$ prochaines transitions selon la politique fixe, sans valeur au-delà de cet horizon. Le premier balayage ne voit que les récompenses immédiates. Le deuxième inclut une transition supplémentaire. Ces valeurs intermédiaires ont un sens clair avant même la convergence.

La mise à jour en place utilise certaines valeurs venant d'être calculées au cours du même balayage. Dans les conditions usuelles d'actualisation, elle peut aussi converger, mais ses tableaux intermédiaires ne correspondent pas nécessairement à ces valeurs synchrones à horizon fini. Dans un calcul à la main, sépare les anciens et les nouveaux tableaux lorsque tu compares des balayages synchrones.

N'ajoute pas de maximum sur les actions pendant l'évaluation. Cela permettrait à l'agent de changer de comportement et répondrait à une autre question que celle définie par la politique fixe.

L'itération sur les valeurs cherche à chaque fois ce qui est optimal lorsqu'une décision supplémentaire est autorisée. Elle part de $V_0=0$ et met à jour chaque état avec la meilleure espérance de récompense ajoutée à la valeur actualisée du successeur. Le même calcul traite les cycles, car les valeurs des successeurs proviennent d'un tableau stocké.

Effectuer un balayage complet

Pour chaque état non terminal, calcule

Pour le premier balayage du robot, tous les termes futurs valent 0. En Batterie haute, on compare Travailler à 4 et Recharger à 0, donc $V_1(H)=4$. En Batterie faible, on compare Travailler à $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$ et Recharger à 0, donc $V_1(L)=0$.

Le deuxième balayage utilise tout ce tableau précédent. En Batterie haute, Travailler donne $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(0)]=\mathrm{6,52}$, tandis que Recharger donne $\mathrm{0,9}(4)=\mathrm{3,6}$. En Batterie faible, Travailler donne toujours −1,6, tandis que Recharger donne 3,6. Ainsi, $V_2=(\mathrm{6,52};\mathrm{3,6})$. Un troisième balayage donne environ $(\mathrm{9,08};\mathrm{5,87})$.

Si la nouvelle valeur 6,52 de Batterie haute était utilisée immédiatement pour mettre à jour Batterie faible, le résultat serait différent. Il s'agirait d'une mise à jour en place, et non du deuxième balayage synchrone présenté ici.

Comprendre ce qui converge

En partant de zéro, $V_k$ est l'espérance de gain optimale lorsqu'il reste exactement $k$ occasions de décision, les épisodes terminaux pouvant se terminer plus tôt. Chaque balayage prolonge d'une étape l'horizon de planification utile. L'opérateur d'optimalité de Bellman est une contraction pour $\gamma <1$ : l'erreur maximale sur les états est réduite au moins d'un facteur $\gamma$ à chaque application. Les valeurs convergent vers l'unique $V^{\ast }$ à partir de tout tableau initial fini.

Un balayage dense examine les états, les actions et les successeurs, pour un coût de l'ordre de $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$ opérations. Un facteur d'actualisation proche de 1 ralentit généralement la convergence, car les récompenses lointaines conservent plus de poids.

S'arrêter avec une borne d'erreur

Posons ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. Pour $0<\gamma <1$, l'erreur maximale du nouveau tableau est bornée par $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$. Pour garantir une erreur inférieure à une tolérance choisie $\epsilon$, il suffit que

Pour $\gamma =\mathrm{0,9}$ et une tolérance de 0,01, le seuil est d'environ 0,00111. Un changement inférieur à 0,01 ne suffit pas à garantir une erreur sur les valeurs inférieure à 0,01. Avec $\gamma =0$, une seule mise à jour donne les récompenses immédiates optimales ; aucune division par le facteur d'actualisation n'est donc nécessaire.

Extraire la politique

Après l'arrêt, compare les espérances des actions à l'aide du tableau final des valeurs. Cette anticipation à un pas donne une politique gloutonne. La politique peut se stabiliser avant les valeurs : la politique gloutonne du robot obtenue à partir de $V_1$ indique déjà « Travailler en Batterie haute, Recharger en Batterie faible », mais ses valeurs nécessitent 77 balayages pour être à moins de 0,01 du couple optimal $(\mathrm{31,50};\mathrm{28,35})$.

Une politique qui semble stable et des valeurs précises sont deux choses à vérifier séparément. La mise à jour doit comparer les résultats attendus de chaque action ; choisir uniquement le successeur possible de plus grande valeur revient à omettre le risque et la récompense immédiate.

L'itération sur les politiques alterne deux tâches : mesurer une politique, puis améliorer ses actions à l'aide de cette mesure. Pars d'une politique déterministe quelconque. Un bon choix initial peut économiser du travail, mais il n'est pas nécessaire pour obtenir un résultat correct dans un processus de décision markovien fini et actualisé.

Séparer évaluation et amélioration

Calcule d'abord $V^{{\pi }_i}$, les valeurs de la politique courante. Puis, pour chaque état, compare toutes les actions à l'aide de ces mêmes valeurs :

L'évaluation décrit l'ancien comportement. L'amélioration cherche à savoir si changer la première action améliorerait le gain en suivant ensuite l'ancienne politique. Modifier toutes les actions concernées donne une politique au moins aussi bonne dans chaque état. Si l'ancienne politique n'est pas optimale, l'amélioration est stricte dans au moins un état.

Conserve l'action actuelle chaque fois qu'elle est ex æquo pour la meilleure valeur. Sinon, des actions aussi bonnes les unes que les autres peuvent donner l'impression que la politique continue de changer alors que sa valeur ne s'améliore pas.

Améliorer la politique du robot

Pars de « toujours Travailler ». L'évaluation exacte donne environ 8,27 pour Batterie haute et −3,48 pour Batterie faible. En Batterie haute, conserver Travailler donne 8,27 ; passer à Recharger donne $\mathrm{0,9}(\mathrm{8,27})\approx \mathrm{7,45}$. Conserve Travailler. En Batterie faible, Travailler donne −3,48 et Recharger environ 7,45. Passe à Recharger en Batterie faible.

Évalue maintenant la nouvelle politique « Travailler en Batterie haute, Recharger en Batterie faible ». Ses valeurs sont environ 31,50 et 28,35. Améliore-la à nouveau :

Aucune action ne change : l'itération sur les politiques s'arrête. Les valeurs de la politique fixe satisfont aussi les équations d'optimalité, ce qui établit que cette politique est optimale. Le robot a nécessité deux évaluations complètes à partir de cette politique initiale.

Expliquer pourquoi le processus se termine

Un processus de décision markovien fini ne possède qu'un nombre fini de politiques déterministes. Si chacun des $\mathrm{\mid }S\mathrm{\mid }$ états offre $\mathrm{\mid }A\mathrm{\mid }$ choix, il existe $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ politiques de ce type. Le robot possède deux états non terminaux avec deux actions chacun, ce qui donne $2^2=4$ politiques. Avec une amélioration stricte chaque fois que nécessaire et une gestion cohérente des ex æquo, le processus ne peut pas revenir à une politique moins bonne et doit se terminer.

Comparer les méthodes de planification

Les évaluations complètes rendent les tours d'itération sur les politiques plus coûteux, mais il en faut souvent moins. Les 77 balayages d'itération sur les valeurs du robot et les deux évaluations de politique sont des unités de travail différentes : ces nombres ne suffisent donc pas à établir quelle méthode est la plus rapide. Utilise les valeurs de la politique courante à chaque amélioration ; les mélanger avec celles d'une politique précédente fait perdre son sens à cette étape.

En apprentissage par renforcement, un agent apprend de l'expérience dans un problème de décision. Il observe un état, choisit une action disponible et reçoit un échantillon $(s,a,r,s^{\mathrm{\prime }})$ : l'état précédent, l'action, la récompense et l'état suivant. L'objectif reste une espérance de gain élevée, mais les probabilités de transition et les récompenses doivent être apprises.

Séparer apprentissage et planification

La planification utilise un modèle du processus de décision markovien pour calculer des valeurs ou des politiques. Elle peut avoir lieu avant d'agir ou pendant que l'agent planifie à nouveau en cours de fonctionnement. L'apprentissage utilise l'expérience observée, issue soit d'une interaction en cours, soit d'un jeu de données recueilli auparavant. L'apprentissage par renforcement hors ligne apprend lui aussi de l'expérience ; il utilise simplement une expérience enregistrée.

Dans l'apprentissage passif, une politique est fixe et la tâche consiste à estimer sa qualité. Dans l'apprentissage actif, l'agent choisit aussi des actions pour découvrir un meilleur comportement. Ces choix influent à la fois sur la récompense obtenue et sur les informations disponibles pour les mises à jour futures.

Estimer les transitions par dénombrement

Un agent qui apprend avec modèle enregistre le nombre de fois où chaque action est essayée dans chaque état. Soit $N(s,a)$ le nombre de ces essais et $N(s,a,s^{\mathrm{\prime }})$ le nombre d'essais qui aboutissent à un successeur donné. Alors

Les effectifs du numérateur répartissent les essais du dénominateur entre les successeurs : la somme de leurs probabilités estimées vaut donc 1. Une paire jamais essayée a un dénominateur égal à 0 et nécessite davantage d'expérience ou un choix explicite de modélisation ; elle n'a pas encore de distribution empirique des transitions.

Pour le robot, Travailler en Batterie haute a été essayé 20 fois : 13 transitions sont restées en Batterie haute et 7 ont atteint Batterie faible. Les estimations sont $13\mathrm{/}20=\mathrm{0,65}$ et $7\mathrm{/}20=\mathrm{0,35}$. Travailler en Batterie faible a été essayé 10 fois : le robot est resté en service 7 fois et a atteint Hors service 3 fois, ce qui donne 0,7 et 0,3. La seconde estimation sous-estime la probabilité réelle de tomber hors service, qui est de 0,4.

Enregistre aussi les récompenses de chaque transition. Les récompenses du robot sont fixes pour chacun de ses résultats. Si des transitions identiques répétées donnent des récompenses bruitées, estime leur récompense moyenne conditionnelle à partir des échantillons observés.

Planifier avec le modèle appris

Utilise les transitions et les récompenses estimées dans l'itération sur les valeurs ou sur les politiques. Pour ces dénombrements du robot, avec les transitions de Recharger connues et $\gamma =\mathrm{0,9}$, les valeurs optimales estimées sont environ $(\mathrm{30,42};\mathrm{27,38})$. Les choix d'actions optimaux correspondent toujours à ceux du modèle réel : Travailler en Batterie haute, Recharger en Batterie faible. Des estimations de valeurs différentes peuvent donc produire des politiques similaires.

Un petit nombre d'échantillons peut donner des modèles imprécis. Une expérience plus représentative améliore les estimations, mais recueillir des données uniquement selon une politique limitée peut laisser des actions utiles sans essai. Un agent qui apprend avec modèle doit lui aussi explorer.

Comparer deux approches d'apprentissage

Un modèle appris permet de réutiliser des échantillons pour de nombreuses mises à jour de planification et de planifier à nouveau lorsque les objectifs changent. Il nécessite aussi du stockage et des calculs, et ses erreurs peuvent fausser le plan. Les méthodes sans modèle évitent de construire une table de transition, mais nécessitent généralement une expérience importante pour fiabiliser leurs estimations de valeurs.

Une politique fixe peut être évaluée sans connaître son modèle de transition. L'évaluation directe calcule la moyenne de gains complets observés. L'apprentissage par différences temporelles effectue une mise à jour à partir d'une seule récompense et d'une estimation de la valeur du successeur. Les deux méthodes apprennent les valeurs de la politique à partir de l'expérience.

Calculer la moyenne des gains d'épisodes entiers

Suis « toujours Travailler » avec $\gamma =\mathrm{0,9}$. Un épisode du robot est Batterie haute → Batterie haute (+4), Batterie haute → Batterie faible (+4), Batterie faible → Hors service (−10). Les gains issus de ses visites de Batterie haute sont $4+\mathrm{0,9}(4)+\mathrm{0,81}(-10)=-\mathrm{0,5}$ et $4+\mathrm{0,9}(-10)=-5$. Son gain depuis Batterie faible est −10.

Un deuxième épisode est Batterie haute → Batterie faible (+4), Batterie faible → Batterie faible (+4), Batterie faible → Hors service (−10). Son gain depuis Batterie haute est −0,5 ; ses gains depuis Batterie faible sont −5 et −10. Les moyennes à chaque visite sont donc $(-\mathrm{0,5}-5-\mathrm{0,5})\mathrm{/}3=-2$ pour Batterie haute et $(-10-5-10)\mathrm{/}3\approx -\mathrm{8,33}$ pour Batterie faible. Une méthode à la première visite ne compterait que la première visite d'un état dans chaque épisode.

Ces estimations diffèrent fortement des valeurs réelles de la politique $(\mathrm{8,27};-\mathrm{3,48})$, car les deux épisodes se sont terminés rapidement. Les gains complets varient selon les échantillons. Avec suffisamment d'épisodes terminés et représentatifs, leurs moyennes se rapprochent des espérances de gain de la politique. L'évaluation directe attend que le gain nécessaire soit disponible à la fin de l'épisode et estime les états séparément.

Mettre à jour après une transition

L'apprentissage par différences temporelles utilise l'estimation courante de ce qui suit :

La cible est $r+\gamma V(s^{\mathrm{\prime }})$. L'erreur de différence temporelle est la cible moins l'estimation courante. Le taux d'apprentissage $\alpha$ détermine la fraction de cette erreur utilisée dans la mise à jour.

Supposons que $V(H)=10$, $V(L)=8$, $\gamma =\mathrm{0,9}$ et $\alpha =\mathrm{0,5}$. Après Batterie haute → Batterie faible avec une récompense de 4, la cible est $4+\mathrm{0,9}(8)=\mathrm{11,2}$. L'erreur est $\mathrm{11,2}-10=\mathrm{1,2}$ : la nouvelle estimation de Batterie haute est donc $10+\mathrm{0,5}(\mathrm{1,2})=\mathrm{10,6}$. La valeur stockée de Batterie faible reste égale à 8 lors de cette mise à jour. Un état suivant terminal n'apporte aucun terme futur.

L'apprentissage par différences temporelles utilise l'amorçage : il utilise une estimation pour en améliorer une autre. Cela transmet des informations entre états reliés et permet des mises à jour dans les tâches continues, mais les premières cibles peuvent être biaisées par de mauvaises estimations des successeurs.

Régler le poids des nouvelles observations

Un taux d'apprentissage élevé réagit fortement à chaque cible. Avec $\alpha =1$, l'ancienne estimation est remplacée par la dernière cible. Un taux positif fixe continue généralement de suivre le bruit des échantillons. Des taux qui diminuent convenablement, associés à des visites répétées et aux hypothèses usuelles d'un processus fini et actualisé, favorisent la convergence de l'apprentissage tabulaire par différences temporelles. Un taux $1\mathrm{/}N(s)$ calcule la moyenne de la suite des cibles observées ; ces cibles changent elles-mêmes à mesure que les estimations des successeurs s'améliorent.

Les seules valeurs d'état ne révèlent pas la meilleure action sans informations sur les transitions et les récompenses pour une anticipation. L'apprentissage passif par différences temporelles évalue le comportement qui produit ses échantillons. Apprendre les valeurs d'action donne à l'agent un moyen direct de comparer les actions sans apprendre d'abord un modèle.

Le Q-learning apprend les valeurs d'action à partir de transitions observées. Sa cible suppose la meilleure action suivante, même lorsque l'agent choisit des actions exploratoires. Cela lui permet d'apprendre à bien agir sans estimer de modèle de transition.

Remplacer une mise à jour fondée sur une espérance par un échantillon

Une mise à jour Q avec modèle calcule une moyenne sur tous les successeurs possibles :

Le Q-learning observe un successeur à la fois. Après un échantillon $(s,a,r,s^{\mathrm{\prime }})$, il calcule

et met à jour $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. Si le successeur est terminal, $y=r$. Le maximum porte sur les actions disponibles dans l'état suivant, et non dans l'état que l'agent vient de quitter.

Initialise la table Q, choisis une action selon une règle d'exploration, observe le résultat, mets à jour l'entrée choisie et continue à partir de l'état suivant. Recommence après la fin de l'épisode. Pour utiliser la politique apprise, sélectionne une action qui atteint la plus grande valeur Q dans la ligne courante.

Détailler deux mises à jour

Soit $\gamma =\mathrm{0,9}$ et $\alpha =\mathrm{0,5}$. Initialement, $Q(L,\text{Travailler})=5$. Le robot essaie Travailler en Batterie faible et tombe hors service avec une récompense de −10. La cible est −10, donc la nouvelle valeur est $5+\mathrm{0,5}(-10-5)=-\mathrm{2,5}$. Il n'y a pas de gain futur après Hors service.

Supposons ensuite que $Q(H,\text{Travailler})=6$ et que le robot travaille en Batterie haute, gagne 4 et atteigne Batterie faible. En Batterie faible, les estimations sont −2,5 pour Travailler et 3 pour Recharger. La meilleure valeur suivante est 3, ce qui donne la cible $4+\mathrm{0,9}(3)=\mathrm{6,7}$. La valeur mise à jour de Batterie haute-Travailler est $6+\mathrm{0,5}(\mathrm{6,7}-6)=\mathrm{6,35}$. Cet échantillon ne met à jour que cette entrée de la table.

Distinguer le comportement ciblé du comportement réel

Le Q-learning est un apprentissage hors politique : la suite de sa cible est gloutonne, même si sa règle de sélection des actions explore. SARSA apprend sur politique : il utilise $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ pour l'action effectivement choisie ensuite.

Près d'une falaise, un agent qui explore peut effectuer accidentellement des pas dangereux. SARSA tient compte de ces futures actions exploratoires et peut apprendre un trajet plus prudent. Le Q-learning cible la suite gloutonne et peut privilégier un trajet plus court au bord de la falaise, même si l'exploration rend ses trajets d'entraînement risqués.

Énoncer précisément la garantie tabulaire

Dans un processus de décision markovien fini et stationnaire, avec des récompenses bornées et $\gamma <1$, le Q-learning tabulaire converge vers $Q^{\ast }$ avec une probabilité de 1 lorsque chaque paire état-action reçoit une infinité de mises à jour et que ses taux d'apprentissage satisfont

Un taux par paire $1\mathrm{/}N(s,a)$ a cette forme. Un taux $1\mathrm{/}N(s,a{)}^2$ diminue trop vite : sa somme totale est finie, ce qui peut laisser trop peu d'ajustement pour supprimer une erreur initiale. Un ajustement total infini empêche l'apprentissage de s'arrêter trop tôt ; un ajustement au carré de somme finie maîtrise le bruit accumulé. Les taux constants maintiennent généralement des fluctuations dans les tâches stochastiques. Ces conditions portent sur la limite : un entraînement fini doit donc toujours être évalué.

L'exploitation sélectionne l'action qui semble actuellement la meilleure. L'exploration recueille des informations qui peuvent révéler un meilleur choix. Si une première tentative malchanceuse de Travailler conduit le robot à préférer Recharger en Batterie haute, une exploitation pure peut le maintenir indéfiniment en recharge et laisser l'estimation de Travailler sans correction.

Compter correctement la branche aléatoire

Une règle epsilon-gloutonne explore uniformément avec une probabilité $\epsilon$ et choisit sinon une action gloutonne. Supposons qu'il y ait une action gloutonne parmi quatre et que $\epsilon =\mathrm{0,2}$. Sa probabilité de sélection est $\mathrm{0,8}+\mathrm{0,2}\mathrm{/}4=\mathrm{0,85}$. Chaque autre action a une probabilité de 0,05. La branche aléatoire inclut aussi l'action gloutonne.

Une exploration trop faible au début de l'entraînement peut laisser des actions utiles sans essai ; une exploration élevée en fin d'entraînement continue de sacrifier des récompenses. Un schéma peut devenir glouton à la limite tout en essayant chaque paire pertinente une infinité de fois. Cette propriété GLIE est plus exigeante que la simple diminution d'epsilon, et l'accessibilité détermine si tous les états sont visités.

Favoriser les actions peu documentées

Une fonction d'exploration peut ajouter un bonus à une estimation de valeur. Avec $f(u,n)=u+k\mathrm{/}n$ pour une action déjà essayée, choisis l'action dont le score est le plus élevé. Donne la priorité aux actions non essayées, par exemple avec un score de $+\mathrm{\infty }$. Avec $k=10$, une valeur de 5 après 20 essais obtient 5,5 ; une valeur de 4 après deux essais obtient 9. L'action la moins essayée est sélectionnée malgré son estimation courante plus faible.

Le bonus peut aussi entrer dans une cible de mise à jour : $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. Cela propage l'attrait des actions inexplorées vers les états précédents. Des valeurs Q initiales optimistes peuvent aussi encourager l'essai d'actions dont les estimations n'ont pas encore été corrigées par l'expérience.

Utiliser une borne de confiance pour les bandits

Un bandit à plusieurs bras possède un seul état de décision et plusieurs bras dont les récompenses moyennes sont fixes et inconnues. Chaque tirage renseigne l'agent sur la distribution des récompenses d'un bras. UCB1 suppose des tirages de récompense indépendants et bornés, avec une distribution fixe par bras ; ramène les récompenses à l'intervalle de 0 à 1. Tire chaque bras une fois, puis choisis le score le plus élevé

Ici, ${\bar{x}}_j$ est la moyenne observée du bras $j$, $n_j$ son nombre de tirages et $N$ le nombre total de tirages sur tous les bras. Le bonus augmente pour les bras peu échantillonnés. Avec des moyennes de 0,6 et 0,5 après respectivement 10 et 2 tirages, $N=12$. Les scores sont environ 1,30 et 2,08 : le second bras est donc sélectionné. Le score peut dépasser 1 même si les récompenses observées ne le peuvent pas : c'est un indice de décision, pas une récompense observée.

Mesurer le coût de l'apprentissage

Le regret compare la récompense obtenue à celle que des choix optimaux auraient rapportée. Dans un bandit stationnaire comportant un bras réellement moins bon, un epsilon positif fixe continue de sélectionner ce bras à une fréquence positive, ce qui produit un regret espéré linéaire. Sous ses hypothèses de bandit stochastique, UCB1 présente un regret espéré logarithmique. Un schéma d'epsilon décroissant soigneusement réglé peut aussi atteindre cet ordre de grandeur ; une diminution arbitraire ne peut pas le garantir.

La cible hors politique du Q-learning permet d'utiliser des échantillons exploratoires sans redéfinir les valeurs optimales recherchées. L'exploration influe néanmoins sur la récompense obtenue pendant l'entraînement. Pour les systèmes physiques, utilise la simulation, l'expérience enregistrée ou des restrictions sur les actions autorisées afin d'éviter que l'exploration cause des dommages.

Une table Q stocke un nombre pour chaque paire état-action. Dans un grand problème, de nombreuses paires risquent de ne jamais être visitées. Des entrées distinctes ne permettent pas non plus de partager les observations entre des situations similaires. Le Q-learning approché remplace la table par une fonction de caractéristiques.

Représenter les valeurs par une somme pondérée

Une caractéristique $f_i(s,a)$ est un nombre qui décrit un aspect de l'état et de l'action. Pour un robot de livraison, les caractéristiques pourraient décrire le niveau de batterie, la distance à une borne de recharge et les colis en attente. Une approximation linéaire s'écrit

Les poids $w_i$ indiquent l'importance de la contribution de chaque caractéristique. Les caractéristiques peuvent dépendre de l'action comme de l'état, ce qui permet d'attribuer des valeurs différentes à plusieurs choix dans un même état.

Mettre à jour chaque poids à partir d'une erreur

Calcule la valeur Q courante, puis la cible $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. La différence $\delta =y-Q(s,a)$ détermine chaque mise à jour :

Toutes les valeurs utilisées pour la cible et l'erreur proviennent des poids avant la mise à jour. Une caractéristique nulle ne modifie pas son poids. Une caractéristique non nulle module l'ajustement, y compris son signe.

Pour les poids $(1;-\mathrm{0,5})$ et les caractéristiques courantes $(1;2)$, l'estimation est $1(1)+(-\mathrm{0,5})(2)=0$. Supposons que la récompense soit 4, que la meilleure valeur Q suivante soit 4 et que $\gamma =\mathrm{0,9}$. La cible est $4+\mathrm{0,9}(4)=\mathrm{7,6}$, donc $\delta =\mathrm{7,6}$. Avec $\alpha =\mathrm{0,1}$ :

La nouvelle estimation pour les mêmes caractéristiques devient $\mathrm{1,76}+\mathrm{1,02}(2)=\mathrm{3,8}$. Une mise à jour de poids partagés ne revient pas à remplacer une entrée indépendante de table par la cible.

Comprendre la portée et les limites du partage

Un poids intervient dans de nombreuses prédictions. Le mettre à jour modifie les valeurs de toutes les paires pour lesquelles cette caractéristique est non nulle. C'est la généralisation, qui peut aider l'agent à agir de manière pertinente dans des états inconnus. Elle peut aussi propager une mise à jour erronée.

Si deux situations ont des vecteurs de caractéristiques identiques pour chaque action correspondante, le modèle doit leur attribuer des valeurs d'action identiques. Si elles nécessitent des actions différentes, aucun réglage des poids ne peut représenter correctement les deux décisions. Il faut de meilleures caractéristiques ou une fonction plus riche. L'apprentissage tabulaire est le cas particulier où chaque paire état-action possède une caractéristique indicatrice, active uniquement pour cette paire.

La garantie de convergence du Q-learning tabulaire ne s'étend pas à toute approximation de fonction. L'amorçage hors politique avec des prédictions partagées peut osciller ou diverger : évalue donc la politique apprise sur des essais distincts. Les réseaux Q profonds apprennent des caractéristiques à partir d'entrées comme les pixels d'un écran de jeu ; la recherche de politique ajuste directement une politique pour augmenter le gain.