Chapitre 1 : Introduction à l'apprentissage par renforcement (PDF)

Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Chapitre 1 : Introduction à l’apprentissage par renforcement Processus de Décisions Markoviens...

Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Chapitre 1 : Introduction à l’apprentissage par renforcement Processus de Décisions Markoviens Emmanuel Hyon Université de Paris Nanterre M2 MIAGE Nanterre 2024-2025 Chap. 1 Master M2 MIAGE 2024-2025 1 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction Positionnement du RL Quelques Exemples 2 Les systèmes contrôlés Systèmes contrôlés Descriptions des Eléments 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 2 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction Positionnement du RL Quelques Exemples 2 Les systèmes contrôlés 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 3 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Positionnement du R.L. Il y a 3 grands types d’apprentissage 1. Apprentissage supervisé. But trouver une fonction de Prédiction ou de classification. On apprend à partir de données étiquetées. On utilise des Réseaux de neurones, Forêt Aléatoire, SVM, Mélange de lois, similarité (k plus proches voisin). 2. Apprentissage non supervisé. But regrouper (Clustering) ou associer entre elles des données On apprend à partir de données sans informations. On utilise l’algorithme de K -moyenne, réduction de la dimension. 3. Apprentissage par renforcement. But trouver une politique de contrôle d’un système aléatoire. On apprend à partir du comportement d’un système dynamique On utilise Q learning, Gradient, Monte Carlo Tree Search Chap. 1 Master M2 MIAGE 2024-2025 4 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Hypothèses de l’apprentissage par renforcement Deux grand éléments composent l’apprentissage par renforcement Environnement ▶ Le système évolue au cours du temps : il évolue de manière aléatoire il évolue suite à des actions ▶ le système possède un état qui permet de le décrire ▶ cet état peut être observé Agent ▶ Il agit sur le système (ou environnement) ▶ Il observe le système ▶ Il reçoit des gains suite à une action. Chap. 1 Master M2 MIAGE 2024-2025 5 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Domaines d’application du RL 1. Les Jeux Echec Backgammon (avec des approches de TD learning) jeu de Go (alphago) Deep Q Learning (mélange RL et NN) et MCTS Atari (pong) ou Sous Marin 2. Conduite autonome. 3. Gestion des ressources (stock, énergie, ressources naturelles). Gestion de l’énergie dans un cloud. 4. Exploration par des robots 5. Télécoms et Réseau 6. Planification avec aléa. Chap. 1 Master M2 MIAGE 2024-2025 6 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Plan du cours 1. Système contrôlés. Les éléments constitutifs d’un système contrôlé La manière de les résoudre 2. Apprentissage par renforcement Les algorithmes de résolutions : méthodes tabulaires Q-learning Les tenseurs Manipulation de la bibliothèque OpenAI Gymnasium 3. Le Deep Q learning Principe du Deep Q learning Manipulation avec Tensorflow/Keras Chap. 1 Master M2 MIAGE 2024-2025 7 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmote La montagne Vous êtes en vacances à la montagne. Chaque matin vous regardez par la fenêtre pour voir si il y a une marmotte La marmotte bouge durant la nuit Chap. 1 Master M2 MIAGE 2024-2025 8 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmote La montagne Vous êtes en vacances à la montagne. Chaque matin vous regardez par la fenêtre pour voir si il y a une marmotte Chaque matin la montagne sur laquelle est la marmotte change Chap. 1 Master M2 MIAGE 2024-2025 8 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmote La montagne Vous êtes en vacances à la montagne. Chaque matin vous regardez par la fenêtre pour voir si il y a une marmotte La marmotte bouge de manière aléatoire Chap. 1 Master M2 MIAGE 2024-2025 8 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmote La montagne Vous êtes en vacances à la montagne. Chaque matin vous regardez par la fenêtre pour voir si il y a une marmotte Vous ne connaissez pas sa manière d’évoluer Chap. 1 Master M2 MIAGE 2024-2025 8 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte Le bonheur Voir la marmotte sur une montagne vous procure une satisfaction : Très forte sur la montagne 1 Chap. 1 Master M2 MIAGE 2024-2025 9 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte Le bonheur Voir la marmotte sur une montagne vous procure une satisfaction : Moyenne sur la montagne 2 Chap. 1 Master M2 MIAGE 2024-2025 9 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte Le bonheur Voir la marmotte sur une montagne vous procure une satisfaction : Faible sur la montagne 3 Chap. 1 Master M2 MIAGE 2024-2025 9 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte Le bonheur Voir la marmotte sur une montagne vous procure une satisfaction : On transforme cela en valeur 10, 1, 0.1 Chap. 1 Master M2 MIAGE 2024-2025 9 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte L’effort Vous voudriez modifier le comportement de la marmotte pour avoir le plus de satisfaction. En mettant de la nourriture à des endroits stratégique Chap. 1 Master M2 MIAGE 2024-2025 10 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte L’effort Vous voudriez modifier le comportement de la marmotte pour avoir le plus de satisfaction. La nourriture va modifier le comportement de la marmotte Chap. 1 Master M2 MIAGE 2024-2025 10 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte L’effort Vous voudriez modifier le comportement de la marmotte pour avoir le plus de satisfaction. Mais il faut aller porter la nourriture (cela vous coûte) Chap. 1 Master M2 MIAGE 2024-2025 10 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte L’effort Vous voudriez modifier le comportement de la marmotte pour avoir le plus de satisfaction. Vous ne connaissez pas l’effet de vos actions. Chap. 1 Master M2 MIAGE 2024-2025 10 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography La Marmotte L’effort Vous voudriez modifier le comportement de la marmotte pour avoir le plus de satisfaction. Vous allez apprendre quelles sont les meilleures actions Chap. 1 Master M2 MIAGE 2024-2025 10 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exploration Quelle est la meilleure manière de lui faire traverser cet environnement ? ▶ Vous contrôlez un robot Chap. 1 Master M2 MIAGE 2024-2025 11 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exploration Quelle est la meilleure manière de lui faire traverser cet environnement ? ▶ Dans un environnement inconnu Chap. 1 Master M2 MIAGE 2024-2025 11 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exploration Quelle est la meilleure manière de lui faire traverser cet environnement ? ▶ Qu’il doit traverser (avec un puit au milieu) Chap. 1 Master M2 MIAGE 2024-2025 11 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exploration Quelle est la meilleure manière de lui faire traverser cet environnement ? ▶ Il ne répond pas bien à vos actions Chap. 1 Master M2 MIAGE 2024-2025 11 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Gestion d’une maladie Vous avez à votre disposition un médicament. 1. Un médicament soigne avec une probabilité donnée. 2. Un médicament provoque des effets indésirables 3. Administrer le médicament à un coût 4. Ne pas administrer le médicament donne une probabilité de guérir (faible). Faut-il prescrire ce médicament à un patient ? Chap. 1 Master M2 MIAGE 2024-2025 12 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction 2 Les systèmes contrôlés Systèmes contrôlés Descriptions des Eléments 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 13 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Présentation Description des éléments Un système contrôlé est décrit par les éléments suivants : Définition Un processus de décision Markovien est un n-uplet X , A, (P)a , R : ▶ X l’espace d’état : un ensemble d’états. ▶ A l’espace d’action : un ensemble d’actions. ▶ (P)a une collection de probabilités de transition : (Pa )x,x ′ = P [xk+1 = x ′ | xk = x, ak = a]. ▶ R une fonction de gain R (xk+1 , xk , ak ). On va en tirer r (xk , ak ). Comme les transitions et les gains sont identiques quelque soit l’étape on a un modèle stationnaire. Un Markov Decision Process est un outil pour modéliser des problèmes de contrôle dynamique et fournit une théorie pour les résoudre. Chap. 1 Master M2 MIAGE 2024-2025 14 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Fonctionnement d’un espace d’état contrôlé Chap. 1 Master M2 MIAGE 2024-2025 15 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Espace d’Etat L’espace d’état est l’ensemble discret qui représente l’ensemble des valeurs que peut prendre votre système au cours du temps. Une proposition [Powell] propose une “définition” : Etat représente l’état physique du système ainsi que l’ensemble des informations requises pour prendre la décision. Chap. 1 Master M2 MIAGE 2024-2025 16 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple d’état Espace d’état de la marmotte Donner une représentation de l’état pour l’exemple de la marmotte. Chap. 1 Master M2 MIAGE 2024-2025 17 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple d’état II Espace d’état du Robot Donner une représentation de l’état pour l’exemple du robot Chap. 1 Master M2 MIAGE 2024-2025 18 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple d’état III Espace d’état du malade Donner une représentation de l’état pour l’exemple du malade Quelles variations sur l’exemple du malade pourrait-on aborder ? Chap. 1 Master M2 MIAGE 2024-2025 19 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Probabilités de transitions Evolution dynamique : Système stochastique dynamique On suppose que l’état est l’enregistrement de la position de la marmotte. On note par xk la position de la marmotte au jour k. La suite des enregistrements quotidiens est : (x1 , x2 ,... , x9 ,...) Elle est appelée path ou episode. Elle peut prendre plusieurs valeurs : - (M1, M2, M3, M3, M2, M3, M2, M1, M1,...) - (M1, M2, M2, M1, M1, M2, M2, M2, M2,...) - (H, H, H, H, H, H, H, H, H, H, H,......) - (H, M3, M2, M3, H, H, H, M3, M2, M1,...) Chap. 1 Master M2 MIAGE 2024-2025 20 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Système dynamique Système dynamique Le système que vous observez est un système dynamique : ▶ l’“état” du système evolue au cours du temps. ▶ le prochain état peut être déterminé gràce à une fonction de transition : xk+1 = fk (xk , xk−1 ,... , x1 ). Système dynamique stochastique L’état suivant est donné par une fonction de transition stochastique (ε(ω) l’aléa) : xk+1 = fk (xk , xk−1 ,... , x1 , ε(ω)) Chaı̂ne de Markov La fonction de transition ne dépend que de l’état précédent et d’un aléa. xk+1 = fk (xk , ε(ω)) Chap. 1 Master M2 MIAGE 2024-2025 21 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Probabilité de transition Soit l’espace d’état qui est {M1, M2, M3}, où Mi est la montagne i. Le graphe de transition est La matrice de transition est   M1 0.25 0.25 0.5 0.25 P =  0.4 0.2 0.4  0.5 0.4 0.4 0.3 0.3 M2 0.2 0.25 0.4 Une matrice de transition décrit les probabilités de passer d’un état i à un 0.4 0.4 état j. M3 0.3 P(i, j) donne la probabilité de passer de i à j. Chap. 1 Master M2 MIAGE 2024-2025 22 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography L’espace d’action Effet de l’action On peut agir sur le système au moyen d’une action ou d’un contrôle. Le contrôle va modifier le système et les transitions. La fonction de transition depend maintenant de l’état, de l’action et du hasard : xk+1 = f (xk , ak , εk+1 ). Il y a maintenant une matrice de transition pour chaque action. Le gain reçu dépend de l’état actuel, de l’état suivant et de l’action. R (xk+1 , xk , ak ) ⇒ r (xk , ak ) Chap. 1 Master M2 MIAGE 2024-2025 23 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography L’espace d’action Définition Espace d’Actions L’ensemble des actions possibles dans chaque état En théorie il y a un espace d’action pour chaque états A(x). En effet, il peut y avoir des actions impossibles. Adapté pour l’analyse. En pratique un seul espace commun et des actions considérées comme sans effets. Adapté programmation. Chap. 1 Master M2 MIAGE 2024-2025 24 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple d’action Donner une représentation de l’espace d’action pour ▶ L’exemple de la marmotte. ▶ L’exemple du robot ▶ L’exemple du malade ▶ Quelles variations sur l’exemple du malade pourrait-on aborder ? Chap. 1 Master M2 MIAGE 2024-2025 25 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Probabilité de transition avec contrôle Illustration Espace d’état : {1, 2, 3}, avec i qui représente la montagne Mi. Espace d’Action : {0, 1, 2, 3}, où i signifie “mettre la nourriture” sur la montagne Mi (et 0 signifie “ne rien faire”). Probabilités de Transition :     0.25 0.5 0.25 0.5 0.25 0.25 P0 =  0.4 0.2 0.4  , P1 = 0.6 0.2 0.2  ; 0.4 0.3 0.3 0.5 0.4 0.1     0.25 0.55 0.2 0.1 0.2 0.7 P2 =  0.2 0.4 0.4 , P3 = 0.0 0.1 0.9 0.3 0.4 0.3 0 0 1 Chap. 1 Master M2 MIAGE 2024-2025 26 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains Gains fixes Voir la marmotte sur la montagne 1 rapporte 10 unités de satisfaction. Voir la marmotte sur la montagne 2 rapporte 1 unité de satisfaction. Voir la marmotte sur la montagne 3 rapporte 0.1 unités de satisfaction. Coûts Mettre de la nourriture sur la montagne 1 coûte 5 unités de satisfaction. Mettre de la nourriture sur la montagne 2 coûte 1 unités de satisfaction. Mettre de la nourriture sur la montagne 3 coûte 0.5 unités de satisfaction. Calcul de gains Soit i l’état initial. 1. On place de la nourriture on impute les coûts 2. On regarde au matin où est la marmotte et on collecte les gains Chap. 1 Master M2 MIAGE 2024-2025 27 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains Exemple de la marmote sous forme graphique On veut X r (x, a) = R(y |x, a) · p(y |x, a) y ∈X r = 10 x(k+1)=1 g=10 w.p.=0.25 p=0.25 r=1 x(k+1)=2 g=1 w.p.=0.5 p=0.5 a=0 p=0.25 r=0 r = 0.1 x(k+1)=3 g=0.1 w.p.=0.25 x(k)=1 r = -5 p=0.5 r = 10 x(k+1)=1 g=5 w.p.=0.5 a=1 p=0.25 p=0.25 r=1 x(k+1)=2 g=-4 w.p.=0.25 r = 0.1 x(k+1)=3 g=-4.9 w.p.=0.25 Chap. 1 Master M2 MIAGE 2024-2025 28 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains Exemple de la marmote (etat 1) Exprimons formellement les gains pour l’état 1 : r (1|1, 0) = 10 , r (2|1, 0) = 1 , r (3|1, 0) = 0.1 r (1|1, 1) = 5 , r (2|1, 1) = −4 , r (3|1, 1) = −4.9 r (1|1, 2) = 9 , r (2|1, 2) = 0 , r (3|1, 2) = −0.9 r (1|1, 3) = 9.5 , r (2|1, 3) = 0.5 , r (3|1, 3) = −0.4 Pour obtenir r (x, a) : on sait que le gain moyen r (x, a) est X r (x, a) = R(y |x, a) · p(y |x, a) y ∈X et donc nous obtenons : r (1, 0) = p(1|1, 0) · r (1|1, 0) + p(2|1, 0) · r (2|1, 0) + p(3|1, 0) · r (3|1, 0) r (1, 1) = p(1|1, 1) · r (1|1, 1) + p(2|1, 1) · r (2|1, 1) + p(3|1, 1) · r (3|1, 1) r (1, 2) = p(1|1, 2) · r (1|1, 2) + p(2|1, 2) · r (2|1, 2) + p(3|1, 2) · r (3|1, 2) r (1, 3) = p(1|1, 3) · r (1|1, 3) + p(2|1, 3) · r (2|1, 3) + p(3|1, 3) · r (3|1, 3) Chap. 1 Master M2 MIAGE 2024-2025 29 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains Exemple de la marmote (etat 1) On remplace les probabilités par leur valeurs, nous obtenons : r (1, 0) = 0.25 · r (1|1, 0) + 0.5 · r (2|1, 0) + 0.25 · r (3|1, 0) r (1, 1) = 0.5 · r (1|1, 1) + 0.25 · r (2|1, 1) + 0.25 · r (3|1, 1) r (1, 2) = 0.25 · r (1|1, 2) + 0.55 · r (2|1, 2) + 0.2 · r (3|1, 2) r (1, 3) = 0.1 · r (1|1, 3) + 0.2 · r (2|1, 3) + 0.7 · r (3|1, 3) et enfin les coûts par leurs valeurs : r (1, 0) = 0.25 · 10 + 0.5 · 1 + 0.25 · 0.1 = 3.025 r (1, 1) = 0.5 · 5 + 0.25 · −4 + 0.25 · −4.9 = 0.275 r (1, 2) = 0.25 · 9 + 0.55 · 0 + 0.2 · −0.9 = 2.07 r (1, 3) = 0.1 · 9.5 + 0.2 · 0.5 + 0.7 · −0.4 = 0.77 Chap. 1 Master M2 MIAGE 2024-2025 30 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains (etat 2 et 3) Exemple de la marmote On peut compter les gains dans les autres états de la même manière, nous obtenons : r (2, 0) = 10 · 0.4 + 1 · 0.2 + 0.1 · 0.4 = 4.24 r (2, 1) = 5 · 0.6 − 4 · 0.2 − 4.9 · 0.2 = 1.22 r (2, 2) = 9 · 0.2 + 0 · 0.4 − 0.9 · 0.4 = 1.44 r (2, 3) = 9.5 · 0.0 + 0.5 · 0.1 − 0.4 · 0.9 = −0.31 r (3, 0) = 10 · 0.4 + 1 · 0.3 + 0.1 · 0.3 = 4.33 r (3, 1) = 5 · 0.5 − 4 · 0.4 − 4.9 · 0.1 = 0.41 r (3, 2) = 9 · 0.3 + 0 · 0.4 − 0.9 · 0.3 = 2.43 r (3, 3) = 9.5 · 0 + 0.5 · 0 − 0.4 · 1 = −0.4 Chap. 1 Master M2 MIAGE 2024-2025 31 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Expression des gains (Matrice) Exemple de la marmote On obtient   3.025 0.275 2.0 0.77 r (x, a) =  4.24 1.22 1.44 −0.31. 4.33 0.41 2.43 −0.4 Chap. 1 Master M2 MIAGE 2024-2025 32 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction 2 Les systèmes contrôlés 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 33 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Gains collectés Soit Vk (x) la somme des gains collectés à partir de x pendant k étapes : i=k X Vk (x) = ri. i=0 Il est plus intéressant d’utiliser l’espérance de la somme " i=k # X Vk (x) = E ri |x0 = x i=0 Path : Retour : (M1, M2, M3, M3, M3, M3) 11.4 avec probabilité 0.0054 (0.5 × 0.4 × 0.3 × 0.3 × 0.3) = 0.0054 (M1, M2, M3, M2, M1, M2) 23.1 avec probabilité 0.012 (0.5 × 0.4 × 0.3 × 0.4 × 0.5) = 0.012 (M1, M2, M1, M1, M2, M1) 42 avec probabilité 0.01 (0.5 × 0.4 × 0.25 × 0.5 × 0.4) = 0.01 Gains espérés : 22, 18 Chap. 1 Master M2 MIAGE 2024-2025 34 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Gains collectés Intérêt de l’espérance Imaginons qu’on veuille comparer l’ensoleillement dans une station balnéaire entre deux villes ▶ une sur la côte d’Azur. ▶ une sur la côte normande. Est ce que calculer l’ensoleillement sur une semaine dans chacune des villes est pertinent ? Chap. 1 Master M2 MIAGE 2024-2025 35 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Définitions des objectifs Objectifs qu’il faudra optimiser Coût escompté à horizon fini d’horizon N Le gain est la somme espérée des gains pondérés sur une trajectoire d’horizon N : ! N−1 X θ i VN = E θ r (xi , ai ) i=0 où r (xi , ai ) est le gain au temps i et θ ∈ [0, 1) le facteur de discount. Critère escompté à horizon infini Le gain est l’espérance de la somme des gains collectés sur une trajectoire infinie : ∞ ! X Vθ = E θi r (xi , ai ) i=0 où r (xi , ai ) est le gain à l’étape i et θ ∈ [0, 1) le facteur d’escompte. Chap. 1 Master M2 MIAGE 2024-2025 36 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction 2 Les systèmes contrôlés 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 37 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Résoudre le problème de contrôle dynamique On suppose que notre MDP est complètement défini (le modélisateur a fait son travail). On veut optimiser le coût discounted pour un horizon fini : " k=7 # X θ k V =E θ r (xk , ak ) (1) k=0 Comment optimiser notre problème ? Deux points majeurs : Chap. 1 Master M2 MIAGE 2024-2025 38 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Résoudre le problème de contrôle dynamique On suppose que notre MDP est complètement défini (le modélisateur a fait son travail). On veut optimiser le coût discounted pour un horizon fini : " k=7 # X θ k V =E θ r (xk , ak ) (1) k=0 Comment optimiser notre problème ? Deux points majeurs : 1. Une action a un effet à long terme. Chap. 1 Master M2 MIAGE 2024-2025 38 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Résoudre le problème de contrôle dynamique On suppose que notre MDP est complètement défini (le modélisateur a fait son travail). On veut optimiser le coût discounted pour un horizon fini : " k=7 # X θ k V =E θ r (xk , ak ) (1) k=0 Comment optimiser notre problème ? Deux points majeurs : 1. Une action a un effet à long terme. 2. Le benefice d’une action dépend des actions suivantes et des gains futurs. Chap. 1 Master M2 MIAGE 2024-2025 38 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Règle de décision et politique Définition. On definit une decision rule comme l’application qui permet de sélectionner l’action à effectuer. C’est une fonction de l’état courant vers une action π : S 7→ A Une decision rule peut être : -Deterministe et définit une action simple A 7→ a -Random et définit une probabilité de selectionner les actions A 7→ P(a). On note par πk la decision rule qui est appliquée au pas k. Définition. Une Politique Π est une suite de decision rules Π = (π1 , π2 ,... , πn ,...). Une politique peut être stationaire : la même régle est appliquée à chaque slot Π = (π, π,... , π). Chap. 1 Master M2 MIAGE 2024-2025 39 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple de politique Régle déterministe On reprend l’exemple de la marmotte : La règle qui consiste à ne jamais déposer de nourriture est : π = (π(1) = 0, π(2) = 0, π(3) = 0) , La règle qui consiste à : déposer de la nourriture sur la montage 1 quand la marmotte est sur la montagne 3 et ne pas en déposer quand la marmote est sur la montagne 1 ou la montagne 2 est : π̃ = (π̃(1) = 0, π̃(2) = 0, π̃(3) = 1). La règle qui consiste à : marmotte sur montagne 1 ne pas déposer de nourriture marmotte sur montagne 2 déposer de la nourriture sur la montagne 1 marmotte sur montagne 3 déposer de la nourriture sur la montagne 2 est : π̂ = (π̂(1) = 0, π̂(2) = 1, π̂(3) = 2). Chap. 1 Master M2 MIAGE 2024-2025 40 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple de politique Politique déterministe La politique qui consiste à ne jamais déposer de nourriture pendant 5 jours est : Π = (π, π, π, π, π). La politique qui consiste à déposer de la nourriture un jour sur deux est : Π = (π̃, π, π̃, π, π̃). La politique Π = (π̂, π̂, π̂, π, π). est ? Chap. 1 Master M2 MIAGE 2024-2025 41 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Exemple de politique Règle de décision aléatoire On définit π(a|s) la probabilité de tirer l’action a dans l’état s. Une règle déterministe peut toujours être exprimée avec une règle stochastique. π(0|1) = 1, π(1|1) = 0, π(2|1) = 0, π(3|1) = 0 La règle qui consiste à tirer les éléments avec une probabilité uniforme dans l’état i est : π(0|i) = 1/4, π(1|i) = 1/4, π(2|i) = 1/4, π(3|i) = 1/4 Chap. 1 Master M2 MIAGE 2024-2025 42 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Fonction de valeur Comment évaluer le gain d’une politique ? Pour faire cela, on definit une fonction de valeur ou value function. Définition. Une fonction de valeur est definie pour ▶ une politique fixée Π ▶ un état initial fixé x ∈ X et calcule ▶ un gain espéré collecté au cours du temps, ▶ en partant de l’état initial ▶ suivant la politique Π. C’est un vecteur de dimension l’espace d’état ou une fonction qui à chaque état renvoie une valeur. Chap. 1 Master M2 MIAGE 2024-2025 43 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Fonction Valeur (suite) Pour une politique Π fixée, on a un vecteur tel que V Π : X 7→ R. Fonction Valeur pour un horizon infini et un critère discounté La fonction Valeur pour critère discounté est VθΠ telle que ∀x ∈ X : ∞ X  VθΠ (x) = EΠ θk r xkΠ , π(xkΠ ) |x0 = x.
k=0 Fonction Valeur pour un coût escompté et un horizon fini N La fonction valeur pour un coût escompté est VθΠ telle que ∀x ∈ X : N X  VθΠ (x) = EΠ θk r xkΠ , π(xkΠ ) |x0 = x.
k=0 Chap. 1 Master M2 MIAGE 2024-2025 44 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Fonction de valeur Calcul Pour calculer la fonction de valeur ▶ Par simulation, on fait tourner le système et à chaque état on applique l’action donnée par la politique ▶ Formellement, On crée la chaine de Markov associée à la politique on la résoud formellement et on en déduit les valeurs du gain. Optimisation Comment trouver la politique optimale. 1. En comparant toutes les politiques (brut force) 1.1 On définit une politique 1.2 On calcule sa valeur 1.3 On regarde si elle est meilleure que celle déjà vue Chap. 1 Master M2 MIAGE 2024-2025 45 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Equation de Bellman Une autre méthode de calcul Pour connaitre la meilleur des fonctions de valeurs on va utiliser l’équation de Bellman. On décompose la collecte des gains en deux parties : 1. le gain immediat du à l’action 2. le gain futur dû aux effets de l’action. ∞ X  Vθ∗ (x) = max ∞ E θ k r (x , k ka )|x0 = x , a,...,a∈A k=0 ! X Vθ∗ (x) = max r (x, a) + θ p(y |x, a)Vθ∗ (y ). a∈A y ∈X La seule solution de cette équation de point fixe est la solution optimale. Résoudre l’équation donne la solution. Chap. 1 Master M2 MIAGE 2024-2025 46 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Utilisation de l’équation de Bellman Il y a deux grands usages de l’équation de Bellman (BE) : ▶ Prediction : Calculer la valeur d’une politique ! X VθΠ (x) = r (x, π(x)) + θ p(y |x, π(x))VθΠ (y ). y ∈X ▶ Planification : Calculer à la fois la politique Optimale la fonction de valeur Optimale ! X Vθ∗ (x) = max r (x, a) + θ p(y |x, a)Vθ∗ (y ). a∈A y ∈X Chap. 1 Master M2 MIAGE 2024-2025 47 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Méthode de résolution Trois grandes méthodes de calcul pour la planification : 1. Value Iteration (VI) ou itération sur les valeurs On approche la fonction de valeur V puis on calcule la solution optimale 2. Policy Iteration (PI) ou itérations sur les politiques A chaque étape : On améliore la politique à l’aide des performances calculées avec la politique de l’étape précédente On évalue les performances de cette politique 3. Linear Programming (LP) ou programmation linéaire Chap. 1 Master M2 MIAGE 2024-2025 48 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Itération de la valeur Pour un critère escompté à horizon infini algorithme d’iteration de valeur : critère θ-discounted cost Initialise V0 k←0 repeat for x ∈ X do   X Vk+1 (x) = max r (x, a) + θ P(y |x, a)Vk (y ) a∈A y ∈S k ←k +1 until ∥Vk+1 − Vk ∥ ≤ ϵ for x ∈ X do  P  π(x) ∈ arg maxa∈A r (x, a) + θ p(y |x, a)Vk+1 (y ) y ∈X return Vk+1 , π Chap. 1 Master M2 MIAGE 2024-2025 49 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Sommaire 1 Introduction 2 Les systèmes contrôlés 3 Objectifs 4 Outil pour la résolution 5 Bibliography Chap. 1 Master M2 MIAGE 2024-2025 50 / 51  Introduction Les systèmes contrôlés Objectifs Outil pour la résolution Bibliography Bibliography References that present the main concepts of MDP F. Garcia. Processus Décisionnels de Markov Chapter 1 in Processus Décisionnels de Markov en Intelligence Artificielle Hermes, 2008. W.B. Powell Introduction to Markov Decision Processes Chapter 3 in Approximate Dynamic Programming, Solving the Curses of Dimensionality Wiley, 2011. Chap. 1 Master M2 MIAGE 2024-2025 51 / 51