Fiche de révision : Introduction à l'apprentissage par renforcement

📋 Plan du Cours

1. Apprentissage par Renforcement
2. Processus de Decision Markovien
3. Méthodes model-based
4. Politique et Retour
5. Fonctions de valeur
6. Équations de Bellman
7. Méthodes de résolution MDP
8. Politique optimale
9. Algorithmes de planification
10. Méthodes de policy iteration
11. Méthodes de value iteration

📖 1. Apprentissage par Renforcement

🔑 Notions clés & Définitions

• Agent : Entité qui interagit avec son environnement, apprend de ses expériences et adapte son comportement pour atteindre un objectif donné. Saulières (2022) : "L’agent apprend en expérimentant dans un environnement dynamique et incertain."
• Apprentissage par expérience : Processus par lequel l’agent améliore ses comportements en accumulant des données issues de ses interactions avec l’environnement, sans modèle préalable des dynamiques.
• Problèmes interactifs et décision séquentielle : Situations où l’agent doit prendre une série de décisions dans un environnement changeant, en tenant compte des conséquences futures de ses actions.
• Objectif d’apprentissage d’un comportement optimal : Définir une stratégie ou politique qui maximise une fonction de récompense cumulée sur le long terme, en équilibrant exploration et exploitation.
• Types de méthodes :
  • value-based : Approche basée sur l’estimation de fonctions de valeur (ex : Q-learning, SARSA).
  • policy-based : Approche qui optimise directement la politique (ex : REINFORCE).
  • actor-critic : Combinaison des deux précédentes, où un acteur propose une politique et un critique évalue cette politique (ex : A2C, A3C).
• Exemples d’applications :
  • Wayve.ai : Suivi de route autonome.
  • DeepMind (Google) : Refroidissement des data centers, AlphaGo, AlphaStar.

📝 Points essentiels

• L’apprentissage par renforcement repose sur un agent qui apprend par essais et erreurs, en utilisant ses interactions pour maximiser une récompense cumulée.
• Le formalisme principal est le Processus de Décision Markovien (MDP), défini par l’espace d’états $S$, l’espace d’actions $A$, la fonction de transition $p$, et la fonction de récompense $r$.
• La résolution d’un MDP implique la recherche d’une politique $\pi$ qui détermine l’action à prendre dans chaque état, afin de maximiser le retour (cumul des récompenses).
• Les méthodes model-based (planification) utilisent la connaissance des dynamiques $p$ et $r$, avec des algorithmes comme la policy iteration, la value iteration et la modified policy iteration.
• Les équations de Bellman permettent d’exprimer récursivement les fonctions de valeur (v et q), essentielles pour évaluer et améliorer les politiques.
• La distinction entre approche model-based (avec connaissance du modèle) et model-free (sans connaissance, apprentissage par interaction) est fondamentale.

💡 À retenir

L’apprentissage par renforcement permet à un agent d’apprendre un comportement optimal dans un environnement inconnu en s’appuyant sur ses expériences, en utilisant des méthodes basées sur la valeur, la politique ou une combinaison des deux, avec des applications variées comme la robotique, les jeux ou la gestion de ressources.

📖 2. Processus de Decision Markovien

🔑 Notions clés & Définitions

• <S, A, p, r> (formalisme du MDP) : Représentation mathématique d’un Processus de Decision Markovien, où S est l’espace d’états, A l’espace d’actions, p la fonction de transition, et r la fonction de récompense (voir aussi "Formalismes" dans la source).
• Propriété markovienne : Le futur ne dépend que du présent, c’est-à-dire que la distribution de transition vers l’état suivant dépend uniquement de l’état actuel et de l’action choisie, et non du passé (source : "p : S x A x S → ℝ").
• Fonction de transition p : p : S x A x S → ℝ, indique la probabilité ou la densité de transition de l’état actuel s à un état s' après avoir effectué l’action a (source : "p : S x A x S → ℝ").
• Fonction de récompense r : r : S x A x S → ℝ, attribue une récompense immédiate à la transition de s vers s' via l’action a, permettant d’évaluer la qualité des transitions (source : "r : S x A x S → ℝ").
• <S, A, p, r> : Ensemble complet du formalisme du MDP, intégrant états, actions, transitions et récompenses, permettant de modéliser un environnement décisionnel markovien (source : "Formalismes").

📝 Points essentiels

• La représentation <S, A, p, r> constitue la base pour modéliser tout processus décisionnel markovien, en intégrant la dynamique probabiliste et la fonction de récompense.
• La propriété markovienne garantit que la dynamique future dépend uniquement de l’état actuel et de l’action choisie, ce qui simplifie la résolution et l’analyse du MDP.
• La fonction de transition p : S x A x S → ℝ doit satisfaire la normalisation des probabilités : pour tout s et a, la somme de p(s, a, s') sur tous s' doit être égale à 1.
• La fonction de récompense r permet d’évaluer la qualité des transitions, essentielle pour définir l’objectif de maximisation du retour total (source : "r : S x A x S → ℝ").
• La formalisation <S, A, p, r> est utilisée dans les méthodes de résolution telles que policy iteration et value iteration, en se concentrant sur l’aspect probabiliste et récompense du processus.

💡 À retenir

Le Processus de Decision Markovien (MDP) formalise un environnement probabiliste où seul l’état présent et l’action en cours déterminent la dynamique future, permettant ainsi de modéliser et résoudre efficacement des problèmes séquentiels avec incertitude.

📖 3. Méthodes model-based

🔑 Notions clés & Définitions

• Connaissance des dynamiques p et r : La planification model-based repose sur la connaissance précise ou l'estimation des fonctions de transition p : S x A x S → ℝ et de récompense r : S x A x S → ℝ, permettant de simuler l’environnement. Saulières (2022) souligne que cette connaissance permet à l’agent de prévoir les conséquences de ses actions via des simulations.

• Planification (model-based) : Technique où l’agent utilise un modèle connu ou appris des dynamiques p et r pour déterminer une politique optimale en effectuant des simulations, sans interaction directe avec l’environnement réel. Saulières (2022) précise que cette approche permet d’anticiper et d’optimiser le comportement avant toute exécution.

• Algorithmes de planification : Méthodes telles que policy iteration, value iteration et modified policy iteration, qui exploitent le modèle pour calculer ou améliorer la politique en utilisant des équations de Bellman et des simulations. Saulières (2022) indique que ces algorithmes itèrent sur les fonctions de valeur ou directement sur la politique pour converger vers la solution optimale.

• Policy iteration : Approche consistant en une boucle alternant évaluation de la politique (calcul des valeurs) et amélioration (mise à jour de la politique) jusqu’à convergence vers la politique optimale. Saulières (2022) précise que cette méthode nécessite la connaissance ou l’estimation précise du modèle pour l’évaluation.

• Modified policy iteration : Variante de policy iteration où l’évaluation de la politique est effectuée seulement un nombre limité de fois (k), permettant un compromis entre rapidité et précision. Saulières (2022) mentionne que cette méthode accélère la convergence en évitant une évaluation exhaustive à chaque étape.

📝 Points essentiels

• La planification model-based nécessite la connaissance ou l’estimation précise des dynamiques p et r, ce qui permet à l’agent de simuler l’environnement et d’anticiper les conséquences de ses actions. Cette approche est particulièrement efficace lorsque ces dynamiques sont connues ou peuvent être modélisées avec précision, comme dans la robotique ou la gestion de systèmes complexes.

• Les algorithmes de planification exploitent ces modèles pour calculer la politique optimale sans interaction directe avec l’environnement réel, en utilisant des équations de Bellman pour évaluer et améliorer la politique. Parmi ces algorithmes, policy iteration, value iteration et modified policy iteration sont les plus couramment utilisés.

• La policy iteration consiste en une boucle d’évaluation puis d’amélioration, garantissant la convergence vers la politique optimale si le modèle est exact. La modified policy iteration permet de réduire le coût computationnel en limitant le nombre d’itérations d’évaluation, tout en conservant une convergence vers la solution optimale.

• La construction d’un environnement simulé basé sur p et r permet à l’agent de tester et d’optimiser ses stratégies avant déploiement dans le monde réel, ce qui est crucial dans des domaines où l’expérimentation coûteuse ou risquée.

💡 À retenir

Les méthodes model-based utilisent un modèle précis ou estimé des dynamiques pour planifier et optimiser le comportement de l’agent via des algorithmes comme policy iteration, value iteration et modified policy iteration, permettant une convergence vers la politique optimale en simulant l’environnement.

📖 4. Politique et Retour

🔑 Notions clés & Définitions

• Politique π : Stratégie ou plan que suit l’agent pour choisir ses actions en fonction de l’état actuel. Elle peut être déterministe (une action unique pour chaque état) ou stochastique (distribution de probabilités sur les actions possibles). Saulières (2022) définit la politique comme la stratégie de l’agent pour atteindre ses objectifs en sélectionnant des actions selon un certain plan.

• Objectif via fonction de récompense r : La fonction de récompense attribue une valeur numérique à chaque transition, permettant de quantifier la performance de l’agent. L’objectif est de maximiser le retour, c’est-à-dire la somme (ou la somme actualisée) des récompenses obtenues au cours de l’épisode ou de la tâche.

• Maximisation du retour : Processus par lequel l’agent cherche à optimiser la somme cumulée des récompenses futures, souvent pondérée par un facteur d’actualisation. La politique optimale est celle qui permet d’obtenir le retour le plus élevé à long terme.

• But d'apprendre une politique optimale : L’agent doit découvrir la stratégie qui maximise le retour attendu, en tenant compte de l’incertitude et de la dynamique de l’environnement. La politique optimale est celle qui, pour chaque état, maximise la valeur de retour future.

📝 Points essentiels

• La politique π définit la stratégie de l’agent pour sélectionner ses actions en fonction de l’état, et peut être déterministe ou stochastique, selon si elle associe une action unique ou une distribution de probabilités à chaque état (Saulières, 2022).

• La fonction de récompense r sert de guide pour l’apprentissage, en attribuant une valeur immédiate à chaque transition, permettant de mesurer la performance de la politique. La maximisation du retour implique de privilégier les actions qui conduisent à des récompenses élevées sur le long terme.

• La recherche de la politique optimale repose sur la maximisation du retour attendu, qui est souvent exprimé via des fonctions de valeur (V pour l’état, Q pour l’état-action). La politique optimale π* est celle qui maximise ces fonctions de valeur, conformément aux équations de Bellman d’optimalité.

• La différence entre politique déterministe et stochastique réside dans la façon dont l’agent choisit ses actions : la première choisit une action unique pour chaque état, la seconde une distribution de probabilités, permettant une exploration plus flexible.

• L’objectif ultime est d’apprendre une politique π* qui, en suivant la stratégie optimale, maximise le retour total, en tenant compte des récompenses immédiates et futures, conformément à la théorie de l’apprentissage par renforcement (Saulières, 2022).

💡 À retenir

La politique π est la stratégie de l’agent pour atteindre ses objectifs, et son optimisation repose sur la maximisation du retour attendu, en utilisant la fonction de récompense r pour guider l’apprentissage vers une stratégie optimale, déterministe ou stochastique.

📖 5. Fonctions de valeur

🔑 Notions clés & Définitions

• Fonction de valeur d'état (v) : La fonction de valeur d'état, notée v(s), représente le retour moyen attendu en suivant une politique π à partir de l’état s. Elle quantifie la qualité d’un état dans le contexte de la politique adoptée.
• Fonction de valeur d'état-action (q) : La fonction de valeur d’état-action, notée q(s, a), indique le retour moyen attendu en prenant l’action a dans l’état s, puis en suivant la politique π par la suite. Elle sert à évaluer la qualité spécifique d’une paire état-action.
• Retour moyen attendu en suivant π : La récompense espérée cumulée qu’un agent peut espérer obtenir en débutant dans un état s (ou en choisissant une action a), en suivant la politique π. Elle est essentielle pour comparer et optimiser les politiques.
• Utilité des fonctions de valeur pour évaluer une politique : Ces fonctions permettent de quantifier la performance d’une politique π sans simuler toutes les trajectoires, facilitant ainsi la recherche de politiques optimales (voir Bellman (1957) : équations de Bellman).

📝 Points essentiels

• La fonction de valeur d’état v(s) est définie comme la moyenne des retours futurs espérés en suivant π, à partir de l’état s. Elle est calculée récursivement via les équations de Bellman d’espérance.
• La fonction de valeur d’état-action q(s, a) permet d’évaluer la qualité d’une action spécifique dans un état, en tenant compte du retour attendu en suivant π après cette action. Elle est liée à v(s) par la relation :
  $v(s) = \sum_{a} \pi(a|s) q(s, a)$
• Ces fonctions sont fondamentales pour la résolution des MDP, car elles permettent de déterminer la politique optimale en utilisant des méthodes comme policy iteration ou value iteration (voir Bellman (1957)).
• La fonction de valeur d’état est souvent utilisée dans les méthodes model-based pour évaluer une politique, tandis que la fonction de valeur d’état-action est centrale dans les algorithmes de Q-learning et SARSA.
• La notion de retour moyen attendu est essentielle pour définir la performance d’une politique, en particulier dans le contexte de la maximisation du cumul des récompenses.

💡 À retenir

Les fonctions de valeur d’état et d’état-action sont des outils clés pour évaluer et optimiser une politique dans un processus de décision markovien, permettant de quantifier la performance attendue et de guider l’apprentissage vers la politique optimale.

📖 6. Équations de Bellman

🔑 Notions clés & Définitions

• Équation de Bellman d'espérance pour v :
  SAULIÈRES (2022) : Relation récursive exprimant la valeur d’un état en fonction des récompenses immédiates et des valeurs futures, en utilisant l’espérance sur la distribution des transitions.
  Formule :
  $v^{\pi}(s) = \mathbb{E}_{a \sim \pi(\cdot|s), s' \sim p(\cdot|s,a)} \left[ r(s,a,s') + \gamma v^{\pi}(s') \right]$

• Équation de Bellman d'espérance pour q :
  SAULIÈRES (2022) : Relation récursive pour la fonction de valeur d’état-action, reliant la valeur de faire une action spécifique à la récompense immédiate et à la valeur de l’état suivant.
  Formule :
  $q^{\pi}(s,a) = \mathbb{E}_{s' \sim p(\cdot|s,a)} \left[ r(s,a,s') + \gamma \mathbb{E}_{a' \sim \pi(\cdot|s')} \left[ q^{\pi}(s',a') \right] \right]$

• Équations d’optimalité de Bellman :
  SAULIÈRES (2022) : Relations qui caractérisent la valeur optimale en exprimant la valeur d’un état ou d’un état-action comme le maximum (ou minimum) sur toutes les actions possibles, permettant de déterminer la politique optimale.
  Formules :
  $v^{*}(s) = \max_{a} \mathbb{E}_{s' \sim p(\cdot|s,a)} \left[ r(s,a,s') + \gamma v^{*}(s') \right]$
  $q^{*}(s,a) = \mathbb{E}_{s' \sim p(\cdot|s,a)} \left[ r(s,a,s') + \gamma \max_{a'} q^{*}(s',a') \right]$

• Expression récursive des fonctions de valeur :
  SAULIÈRES (2022) : La valeur d’un état ou d’un état-action peut être calculée par une formule récursive, intégrant la récompense immédiate et la valeur attendue de l’état suivant, ce qui permet leur calcul itératif ou analytique.

📝 Points essentiels

• Les équations de Bellman d’espérance pour $v^{\pi}$ et $q^{\pi}$ permettent de décrire la valeur d’un état ou d’un état-action sous une politique donnée, en utilisant l’espérance sur la distribution des transitions et des actions.
• Les équations d’optimalité de Bellman définissent la valeur optimale $v^{*}$ et $q^{*}$ en maximisant sur toutes les actions possibles, ce qui est essentiel pour déterminer la politique optimale.
• La relation récursive de ces équations facilite leur résolution par méthodes itératives telles que la valeur itération ou la politique itération.
• La connexion entre ces équations et le calcul des fonctions de valeur est fondamentale pour l’algorithme de résolution des MDP, permettant de déduire la politique optimale à partir des fonctions de valeur.
• La propriété markovienne garantit que la valeur dépend uniquement de l’état actuel, ce qui simplifie la formulation et la résolution des équations.

💡 À retenir

Les équations de Bellman établissent une relation récursive essentielle entre la valeur d’un état ou d’un état-action et celles des états suivants, permettant de calculer ou d’approximer efficacement les fonctions de valeur et de déterminer la politique optimale dans un MDP.

📖 7. Méthodes de résolution MDP

🔑 Notions clés & Définitions

• Méthodes model-based : Techniques qui utilisent explicitement la connaissance des dynamiques p (fonction de transition) et r (fonction de récompense) pour planifier et apprendre un comportement optimal en simulant des transitions (voir AUTEUR (date) : planification dans le contexte des MDP).
• Policy iteration : Méthode itérative consistant à évaluer une politique puis à l’améliorer jusqu’à convergence vers la politique optimale, en utilisant des équations de Bellman pour l’évaluation (voir AUTEUR (date) : principe de la policy iteration).
• Approche itérative : Processus répétitif d’amélioration progressive des politiques ou des valeurs, en utilisant des algorithmes comme policy iteration, value iteration ou modified policy iteration pour converger vers la politique ou la valeur optimale.
• Fonctions de valeur : Fonction qui associe à chaque état ou état-action un retour moyen attendu en suivant une politique donnée, permettant d’évaluer la qualité d’une politique (voir AUTEUR (date) : rôle des fonctions de valeur).
• Équations de Bellman : Relations récursives exprimant la valeur d’un état ou d’un état-action en fonction des valeurs des états suivants, essentielles pour calculer ou optimiser les politiques dans un MDP (voir AUTEUR (date) : formulation des équations d’espérance et d’optimalité).

📝 Points essentiels

• La résolution d’un MDP repose sur la connaissance ou l’estimation des dynamiques p et r. En mode model-based, l’agent utilise ces dynamiques pour simuler et planifier, en appliquant des algorithmes comme policy iteration, value iteration ou modified policy iteration.
• La policy iteration consiste en deux étapes : évaluation de la politique (calcul des fonctions de valeur) puis amélioration de la politique en utilisant ces valeurs, répétées jusqu’à convergence vers la politique optimale (AUTEUR (date) : principe de la policy iteration).
• La value iteration cherche directement à obtenir la valeur optimale v* en appliquant l’opérateur de Bellman optimal de façon itérative, sans passer par une évaluation explicite de politique (voir AUTEUR (date) : principe de la value iteration).
• La approche itérative permet une convergence progressive vers la solution optimale, en ajustant à chaque étape la politique ou la valeur, ce qui est crucial pour traiter des problèmes complexes ou de grande taille.
• La distinction entre méthodes model-based et model-free réside dans la connaissance ou non des dynamiques p et r : la planification (model-based) nécessite leur connaissance, tandis que l’interaction (model-free) apprend par expérimentation dans l’environnement (AUTEUR (date) : comparaison entre planification et interaction).

💡 À retenir

Les méthodes de résolution des MDP, telles que policy iteration et value iteration, exploitent les fonctions de valeur et les équations de Bellman pour converger vers la politique optimale, en utilisant soit la connaissance explicite des dynamiques (model-based), soit l’apprentissage par interaction (model-free).

📖 8. Politique optimale

🔑 Notions clés & Définitions

• Politique optimale π* : stratégie ou plan d’action qui maximise le retour attendu à long terme pour un agent dans un environnement donné, en suivant la fonction de récompense et les dynamiques du processus de décision (voir section 4).
• Fonction de valeur optimale v* : fonction qui associe à chaque état s la valeur maximale du retour attendu en suivant une politique optimale π*, c’est-à-dire la meilleure estimation du gain futur possible depuis cet état (voir section 5).
• Fonction de valeur d’état-action q* : fonction qui donne le retour maximal attendu en commençant depuis un état s en prenant une action a, puis en suivant la politique optimale π* (voir section 5).
• Caractérisation via équations de Bellman d’optimalité : ensemble d’équations récursives qui permettent de déterminer v* et q* en maximisant sur toutes les actions possibles, établissant ainsi la condition d’optimalité pour la politique π* (voir section 6).
• Objectif de maximisation du retour à long terme : but fondamental dans la définition de la politique optimale, qui consiste à choisir des actions pour maximiser la somme des récompenses futures, souvent pondérée par un facteur d’actualisation.
• Lien avec les équations d’optimalité de Bellman : la politique π* est celle qui satisfait les équations d’optimalité de Bellman, en assurant que pour tout état s, la valeur v*(s) est égale au maximum sur toutes les actions a de l’espérance du retour immédiat plus la valeur optimale du nouvel état (voir section 6).

📝 Points essentiels

• La politique optimale π* est celle qui maximise la fonction de valeur v* ou q* pour chaque état ou état-action, respectivement.
• La caractérisation de π* repose sur les équations d’optimalité de Bellman, qui sont des équations récursives permettant de calculer v* et q* sans ambiguïté.
• La recherche de π* peut se faire via des méthodes telles que la policy iteration ou la value iteration, qui exploitent ces équations pour converger vers la solution optimale.
• La fonction de valeur optimale v* donne la meilleure estimation du retour futur possible depuis chaque état, tandis que q* fournit cette estimation en tenant compte de l’action spécifique.
• La maximisation du retour à long terme implique souvent l’utilisation d’un facteur d’actualisation pour équilibrer l’importance des récompenses immédiates et futures.
• La convergence vers π* garantit que l’agent adopte la stratégie la plus efficace pour atteindre ses objectifs dans un environnement markovien.

💡 À retenir

La politique optimale π* est celle qui maximise le retour à long terme, caractérisée par les fonctions de valeur v* et q* qui satisfont les équations d’optimalité de Bellman, assurant ainsi la stratégie la plus efficace pour l’agent dans un environnement donné.

📖 9. Algorithmes de planification

🔑 Notions clés & Définitions

• Algorithmes de planification utilisant modèle connu : Méthodes qui exploitent explicitement la connaissance des dynamiques de l’environnement (p et r) pour déterminer une politique optimale, en simulant ou en calculant directement les valeurs de l’état ou de l’action.
• Simulation des dynamiques pour évaluer politiques : Technique consistant à utiliser un modèle connu pour générer des transitions et des récompenses simulées, permettant d’évaluer la performance d’une politique sans interaction réelle avec l’environnement (voir AUTEUR (date)).
• Policy iteration : Méthode itérative qui alterne évaluation de politique (calcul des valeurs) et amélioration de politique (mise à jour basée sur ces valeurs) jusqu’à convergence vers la politique optimale (voir AUTEUR (date)).
• Value iteration : Approche qui calcule directement la politique optimale en itérant sur l’opérateur de Bellman optimal, sans passer par une étape explicite d’évaluation de politique, en mettant à jour simultanément les valeurs d’état (voir AUTEUR (date)).
• Construction et implémentation d'environnements pour planification : Processus de création d’un environnement simulé ou modélisé permettant de tester, d’évaluer et d’optimiser des politiques via des algorithmes de planification, en utilisant un modèle précis des dynamiques (voir AUTEUR (date)).

📝 Points essentiels

• Les algorithmes de planification exploitent la connaissance préalable des dynamiques p et r dans un environnement modélisé, permettant une planification hors ligne efficace (voir AUTEUR (date)).
• La policy iteration consiste à évaluer une politique donnée via des fonctions de valeur, puis à l’améliorer en choisissant des actions qui maximisent ces valeurs, répétant ce cycle jusqu’à convergence vers la politique optimale (voir AUTEUR (date)).
• La value iteration, en revanche, met à jour simultanément les valeurs d’état en utilisant l’équation de Bellman optimal, sans étape explicite d’évaluation de politique, ce qui accélère la convergence vers la solution optimale (voir AUTEUR (date)).
• La modified policy iteration combine aspects de policy et value iteration, en effectuant un nombre limité d’itérations d’évaluation avant d’améliorer la politique, permettant un compromis entre rapidité et précision (voir AUTEUR (date)).
• La construction d’un environnement pour la planification implique de modéliser précisément les dynamiques p et r, afin de simuler efficacement le comportement de l’agent dans des scénarios variés, facilitant la recherche de politiques optimales (voir AUTEUR (date)).

💡 À retenir

Les algorithmes de planification utilisant modèle connu exploitent la connaissance des dynamiques pour calculer directement ou itérativement la politique optimale via simulation ou mise à jour des valeurs, permettant une planification hors ligne efficace.

📖 10. Méthodes de policy iteration

🔑 Notions clés & Définitions

• Policy iteration : Méthode itérative pour résoudre un MDP, consistant à évaluer une politique jusqu’à convergence, puis à l’améliorer en utilisant la fonction de valeur obtenue, et ce, jusqu’à atteindre la politique optimale. Saulières (2022) : "évaluation de politique jusqu'à convergence, puis amélioration basée sur cette évaluation".
• Évaluation de politique : Étape consistant à calculer la fonction de valeur d’une politique donnée, en résolvant de manière itérative ou directe les équations de Bellman pour cette politique, jusqu’à convergence. Saulières (2022) : "mise à jour des valeurs jusqu’à stabilité pour une politique fixe".
• Amélioration de politique : Processus de déduction d’une nouvelle politique en utilisant la fonction de valeur évaluée, en choisissant pour chaque état l’action qui maximise la valeur d’état-action. Saulières (2022) : "mise à jour de la politique en sélectionnant les actions optimales selon la fonction de valeur".
• Boucle évaluation → amélioration : Cycle itératif où l’évaluation de la politique est suivie d’une amélioration, répété jusqu’à ce que la politique ne change plus, c’est-à-dire qu’elle devienne optimale. Saulières (2022) : "procédé convergeant vers la politique optimale π*".
• Entrées et sorties :
  • Étape d’évaluation : entrée : politique π, sortie : fonction de valeur vπ ou qπ,
  • Étape d’amélioration : entrée : fonction de valeur, sortie : nouvelle politique π', qui est meilleure ou égale à la précédente.

📝 Points essentiels

• La policy iteration alterne entre deux étapes : l’évaluation de la politique (calcul de vπ ou qπ) et l’amélioration de cette politique (mise à jour vers une politique meilleure).
• La convergence est assurée vers la politique optimale π* lorsque la politique ne change plus après une étape d’amélioration.
• La mise en contexte : cette méthode est classiquement utilisée dans le cadre des méthodes model-based, où l’agent connaît ou peut simuler les dynamiques p et r du MDP.
• La fonction de valeur évaluée lors de l’étape d’évaluation permet de guider l’amélioration, en choisissant pour chaque état l’action qui maximise la valeur d’état-action.
• La boucle se répète jusqu’à ce que la politique ne soit plus modifiée, garantissant la convergence vers la politique optimale.

💡 À retenir

La policy iteration est une méthode efficace pour obtenir la politique optimale en alternant évaluation précise et amélioration itérative, garantissant la convergence vers π* dans un nombre fini d’étapes.

📖 11. Méthodes de value iteration

🔑 Notions clés & Définitions

• Value Iteration : méthode de résolution d’un MDP qui consiste à rechercher directement la valeur optimale $v^*$ en itérant sur l’opérateur de Bellman optimal, sans passer par une politique explicite. Elle ne nécessite pas de boucle d’évaluation de politique, mais met à jour la valeur de chaque état en utilisant la formule de Bellman optimalité jusqu’à convergence.
  Source : Saulières (2022)

• Itérations sur l’opérateur de Bellman optimal : processus consistant à appliquer de façon répétée l’opérateur de Bellman optimal $T^*$ sur la fonction de valeur, afin de faire converger cette dernière vers $v^*$. Chaque itération améliore la valeur en utilisant la relation récursive de Bellman.
  Source : Saulières (2022)

• Absence de boucle explicite d’évaluation → amélioration : caractéristique de la value iteration où, contrairement à policy iteration, il n’est pas nécessaire d’évaluer une politique jusqu’à convergence avant de l’améliorer. La mise à jour des valeurs se fait directement via l’opérateur de Bellman, ce qui accélère la convergence vers la valeur optimale.
  Source : Saulières (2022)

• Modified Policy Iteration (MPI) : méthode hybride qui combine aspects de policy iteration et de value iteration. Elle limite le nombre d’itérations d’évaluation de la valeur avant de procéder à une étape d’amélioration de la politique, permettant un compromis entre rapidité et précision.
  Source : Saulières (2022)

📝 Points essentiels

• La value iteration est une méthode itérative qui met à jour la valeur de chaque état en utilisant la formule de Bellman optimalité :
  $v_{k+1}(s) = \max_{a \in A(s)} \left[ \sum_{s'} p(s'|s,a) \left( r(s,a,s') + \gamma v_k(s') \right) \right]$
  jusqu’à ce que la différence entre $v_{k+1}$ et $v_k$ soit négligeable.

• Elle repose sur l’opérateur de Bellman optimal $T^*$, qui est une contraction dans l’espace des fonctions de valeur, garantissant la convergence vers $v^*$.

• La absence de boucle d’évaluation explicite permet d’accélérer la convergence, car la mise à jour ne nécessite pas de calculs d’évaluation de politique jusqu’à la stabilité.

• La Modified Policy Iteration limite le nombre d’itérations d’évaluation de la valeur, puis effectue une étape d’amélioration, ce qui peut réduire le nombre total d’itérations nécessaires pour atteindre $v^*$.

• La convergence de la value iteration est assurée par le théorème de contraction de Bellman, et la méthode est souvent plus simple à implémenter que policy iteration.

💡 À retenir

La value iteration est une méthode efficace pour obtenir la valeur optimale $v^*$ en itérant directement sur l’opérateur de Bellman optimal, sans boucle d’évaluation de politique, et peut être améliorée par la technique de Modified Policy Iteration pour un compromis entre rapidité et précision.

📊 Tableaux de Synthèse

⚠️ Pièges & Confusions Fréquentes

1. Confondre approche model-based (utilise un modèle p, r) et model-free (apprend par interaction sans modèle).
2. Confondre policy iteration (alternance évaluation et amélioration) et value iteration (mise à jour simultanée des valeurs).
3. Mauvaise compréhension de la propriété markovienne : penser que le passé influence la dynamique, alors que seul l’état actuel compte.
4. Confusion entre fonction de transition p (probabilités) et fonction de récompense r (valeurs immédiates).
5. Négliger l’importance de la normalisation de p : la somme sur tous s’'s' doit être 1.
6. Confondre approche model-based avec approche déterministe : la dynamique peut être stochastique.
7. Erreur dans la distinction entre policy (stratégie) et fonction de valeur : la politique est une règle, la valeur une estimation.

✅ Checklist Examen

• Connaître la définition de l’agent selon Saulières (2022) et son rôle dans l’apprentissage par renforcement.
• Maîtriser la formalisation du Processus de Décision Markovien (MDP) : <S, A, p, r> et la propriété markovienne.
• Savoir expliquer la différence entre approche model-based et model-free.
• Connaître les équations de Bellman pour la valeur d’état et la valeur d’action.
• Identifier les méthodes de résolution : policy iteration, value iteration, modified policy iteration.
• Comprendre le concept de politique optimale et comment elle est déterminée.
• Savoir décrire le fonctionnement des algorithmes de planification utilisant un modèle.
• Connaître les applications principales de l’apprentissage par renforcement : jeux, robotique, gestion de ressources.
• Maîtriser la distinction entre fonctions de valeur (V, Q) et politique.
• Savoir ce qu’est une politique stationnaire et une politique déterministe.
• Connaître la différence entre approche model-based et approche model-free.
• Vérifier la maîtrise des fonctions de transition p et de récompense r dans le contexte du MDP.