Revision sheet: Techniques d'Optimisation en Apprentissage par Renforcement

📋 Plan du Cours

1. Apprentissage par Renforcement
2. Processus de Décision Markovien
3. Méthodes model-based
4. Politique et Retour
5. Value functions
6. Équations de Bellman
7. Méthodes policy iteration
8. Méthodes value iteration
9. Méthodes modified policy iteration
10. Méthodes model-free

📖 1. Apprentissage par Renforcement

🔑 Notions clés & Définitions

• Agent : Entité qui interagit avec l’environnement, apprend de ses propres expériences pour atteindre un objectif donné, notamment dans des problèmes interactifs et décisionnels séquentiels. Saulières (2022) : un agent apprend un comportement optimal en expérimentant dans un environnement inconnu ou partiellement connu.
• Apprentissage par expérience : Processus par lequel un agent acquiert des connaissances en expérimentant directement dans l’environnement, sans modèle préalable des dynamiques. Saulières (2022) : l’agent apprend en observant ses transitions et récompenses réelles lors de ses interactions.
• Problèmes interactifs et décision séquentielle : Situations où l’agent doit prendre une série de décisions dans un environnement dynamique, en tenant compte des conséquences futures de ses actions. Saulières (2022) : la décision courante influence le futur, nécessitant une stratégie globale.
• Objectif d’apprentissage d’un comportement optimal : L’agent cherche à maximiser une fonction de récompense cumulée sur le long terme, en adoptant une politique qui optimise ses retours. Saulières (2022) : la politique optimale équilibre entre exploration et exploitation pour atteindre cet objectif.
• Exemples d’applications : Suivi de route (Wayve.ai), refroidissement de data centers (DeepMind), jeux de stratégie (AlphaGo/AlphaZero), trading (IBM), traitement médical. Saulières (2022) : illustrent la diversité des domaines où l’apprentissage par renforcement est pertinent.
• Types de méthodes : Approches basées sur la valeur (value-based), sur la politique (policy-based), ou hybrides (actor-critic). Saulières (2022) : chaque méthode a ses avantages pour apprendre des stratégies optimales dans différents contextes.

📝 Points essentiels

• L’agent doit apprendre à partir de ses interactions avec l’environnement, sans connaître à l’avance ses dynamiques (p et r).
• La formalisation repose sur le Processus de Décision Markovien (MDP), où l’état futur dépend uniquement de l’état et de l’action présents (propriété markovienne).
• La résolution du problème consiste à déterminer une politique π qui maximise le retour attendu, en utilisant des fonctions de valeur (v et q) et les équations de Bellman (espérance et optimalité).
• Les méthodes model-based (planification) utilisent la connaissance des dynamiques p et r pour simuler et optimiser, tandis que les méthodes model-free apprennent directement par interaction, sans modélisation préalable.
• Les principales techniques incluent la policy iteration, la value iteration et la modified policy iteration, qui diffèrent par leur approche de convergence vers la politique ou la valeur optimale.
• Des exemples concrets comme AlphaGo ou AlphaStar illustrent la puissance de ces méthodes pour des tâches complexes et séquentielles.

💡 À retenir

L’apprentissage par renforcement permet à un agent d’acquérir un comportement optimal en expérimentant dans un environnement inconnu, en utilisant des stratégies basées sur la valeur ou la politique, avec ou sans connaissance préalable des dynamiques.

📖 2. Processus de Décision Markovien

🔑 Notions clés & Définitions

• <S, A, p, r> (formalisme du MDP) : Ensemble S d’états, A d’actions, p : S × A × S → ℝ (fonction de transition), r : S × A × S → ℝ (fonction de récompense).
  Source : "Formalisation du Processus de Décision Markovien (MDP)".

  • S : espace d’états dans lequel l’agent évolue.
  • A : espace d’actions possibles pour l’agent.
  • p : probabilité de transition vers un état s’ donné, en prenant l’action a dans l’état s.
  • r : récompense immédiate reçue lors de la transition de s à s’ via a.

• Propriété markovienne : La dynamique future (transition et récompense) ne dépend que de l’état actuel et de l’action choisie, et non des états passés.
  Source : "Propriété markovienne".

  • Dépendance uniquement du présent : la transition p(s, a, s’) et la récompense r(s, a, s’) sont conditionnées uniquement par l’état actuel s et l’action a.

• Fonction de transition p : p : S × A × S → ℝ, qui donne la probabilité que l’état suivant s’ soit atteint depuis s en prenant l’action a.
  Source : "Fonction de transition p".

  • Caractéristique essentielle : elle modélise la dynamique stochastique de l’environnement.

• Fonction de récompense r : r : S × A × S → ℝ, qui attribue une récompense immédiate lors de la transition.
  Source : "Fonction de récompense r".

  • Objectif : guider l’agent vers un comportement optimal en maximisant le retour.

📝 Points essentiels

• Le MDP est défini par le tuple <S, A, p, r> où S et A sont des espaces d’états et d’actions, p modélise la dynamique probabiliste, et r indique la récompense associée à chaque transition.
• La propriété markovienne garantit que la dynamique future ne dépend que de l’état et de l’action présents, ce qui simplifie la résolution du problème.
• La fonction de transition p et la fonction de récompense r sont essentielles pour la résolution du MDP, notamment dans les méthodes model-based telles que la policy iteration, value iteration, et modified policy iteration.
• La connaissance ou l’estimation précise de p et r détermine si l’approche est planifiée (model-based) ou basée sur l’interaction (model-free).
• La résolution du MDP consiste à déterminer une politique π qui maximise le retour attendu, en utilisant notamment les équations de Bellman pour évaluer et améliorer cette politique.

💡 À retenir

Le Processus de Décision Markovien formalise un environnement stochastique où la dynamique et la récompense dépendent uniquement de l’état actuel et de l’action, permettant de résoudre efficacement des problèmes séquentiels via des méthodes basées sur la modélisation des dynamiques.

📖 3. Méthodes model-based

🔑 Notions clés & Définitions

• Processus de Décision Markovien (MDP) : Formalisme mathématique représentant un environnement décisionnel où <S, A, p, r> avec S l’espace d’états, A l’espace d’actions, p la fonction de transition, et r la fonction de récompense (formalisé par SAULIÈRES). La propriété markovienne stipule que le futur dépend uniquement de l’état présent, pas du passé.

• Planification (Model-based) : Approche où l’agent connaît ou apprend explicitement les dynamiques p et r de l’environnement, puis utilise ces modèles pour simuler et planifier des stratégies optimales sans interaction directe avec l’environnement réel.

• Policy Iteration (PI) : Méthode itérative combinant évaluation de politique (calcul précis de la valeur d’une politique) et amélioration de politique (mise à jour vers une meilleure stratégie) jusqu’à convergence vers la politique optimale (voir SAULIÈRES).

• Modified Policy Iteration (MPI) : Variante de PI où l’évaluation de la politique n’est pas effectuée jusqu’à convergence, mais seulement après k itérations, permettant un compromis entre coût computationnel et rapidité de convergence.

• Value Iteration (VI) : Méthode qui combine évaluation et amélioration en une seule étape, en utilisant l’opérateur de Bellman optimal pour mettre à jour directement la fonction de valeur jusqu’à convergence vers la valeur optimale v* (voir SAULIÈRES).

📝 Points essentiels

• La planification avec modèle connu repose sur la connaissance exacte ou l’estimation précise des dynamiques p et r, permettant à l’agent de simuler des transitions et récompenses futures pour optimiser sa politique sans interaction réelle avec l’environnement (voir SAULIÈRES).

• La Policy Iteration consiste à calculer la valeur d’une politique donnée via une évaluation précise, puis à l’améliorer en choisissant les actions qui maximisent la valeur, itérant jusqu’à convergence vers la politique optimale π*.

• La Modified Policy Iteration réduit le coût de l’évaluation en ne réalisant que k itérations de mise à jour de la valeur avant de procéder à une amélioration, ce qui accélère la convergence tout en conservant une bonne qualité de la solution.

• La Value Iteration utilise l’opérateur de Bellman optimal pour mettre à jour la fonction de valeur directement, sans passer par une étape explicite d’évaluation de politique, garantissant la convergence vers v* et permettant de déduire la politique optimale à partir de v*.

• Ces méthodes exploitent la structure du MDP pour effectuer une planification efficace, en simulant les dynamiques p et r, ce qui leur confère une efficacité supérieure dans les environnements où ces modèles sont disponibles.

💡 À retenir

Les méthodes model-based utilisent la connaissance explicite des dynamiques p et r pour planifier et optimiser la politique via des algorithmes comme PI, MPI et VI, permettant une résolution efficace des MDP lorsque le modèle est connu ou appris.

📖 4. Politique et Retour

🔑 Notions clés & Définitions

• Politique π : Stratégie adoptée par l’agent pour choisir ses actions en fonction de l’état. Elle peut être déterministe (une action unique pour chaque état) ou stochastique (une distribution de probabilités sur les actions possibles). AUTEUR (date) : La politique définit le comportement de l’agent dans le cadre du processus de décision.

• Objectif : maximiser le retour : L’objectif de l’agent est de choisir une politique π qui maximise la somme attendue des récompenses cumulées (retour) sur le long terme, en tenant compte de la fonction de récompense r. AUTEUR (date) : La maximisation du retour guide l’apprentissage de la politique optimale.

• Retour (cumul des récompenses) : Quantité totale ou moyenne des récompenses accumulées par l’agent à partir d’un état ou d’une action, souvent pondérée par un facteur d’actualisation pour privilégier les récompenses proches dans le temps. AUTEUR (date) : Le retour est la métrique principale pour évaluer la performance d’une politique.

• Lien entre politique et fonction de récompense : La politique π influence directement la distribution des actions, qui détermine les états visités et donc la distribution des récompenses obtenues. La fonction de récompense r, combinée à π, permet de calculer le retour espéré. AUTEUR (date) : La politique doit être optimisée pour maximiser le retour en exploitant la fonction de récompense.

📝 Points essentiels

• La politique π est la stratégie de l’agent, qui peut être déterministe ou stochastique, définie pour chaque état.
• L’objectif principal est de maximiser le retour, c’est-à-dire la somme (ou la moyenne) des récompenses cumulées, en tenant compte d’un facteur d’actualisation si nécessaire.
• Le retour est une mesure de performance, dépendant de la politique choisie et de la fonction de récompense r.
• La relation entre politique et fonction de récompense est centrale : la politique détermine la distribution des actions, influençant directement la distribution des récompenses et donc le retour espéré.
• La recherche de la politique optimale consiste à ajuster π pour maximiser le retour, en utilisant des méthodes comme la programmation dynamique ou l’apprentissage par renforcement.

💡 À retenir

La politique π définit la stratégie de l’agent, dont l’objectif est de maximiser le retour, c’est-à-dire la somme des récompenses attendues, en exploitant la relation entre actions, récompenses et fonction de récompense.

📖 5. Value functions

🔑 Notions clés & Définitions

• State value function (vπ(s)) : Saulières (2022) : La valeur d’un état $s$ sous une politique $\pi$ correspond au retour moyen que l’on peut espérer en suivant cette politique à partir de cet état. Elle évalue la qualité d’un état dans le contexte de la politique $\pi$.

• State-action value function (qπ(s, a)) : Saulières (2022) : La valeur d’une action $a$ dans un état $s$ sous une politique $\pi$ représente le retour moyen attendu en prenant cette action dans cet état, puis en suivant $\pi$. Elle permet d’évaluer la qualité spécifique d’une paire état-action.

• Utilité des fonctions de valeur : Ces fonctions permettent d’évaluer la performance d’une politique $\pi$ en quantifiant ses retours attendus, facilitant ainsi la comparaison et l’optimisation des stratégies dans un MDP.

• Lien avec la résolution de MDP : Les fonctions de valeur sont fondamentales pour résoudre un MDP, car elles permettent de déterminer la politique optimale en utilisant les équations de Bellman, qui expriment la récursivité du retour espéré (voir section 6).

📝 Points essentiels

• La state value function $v^\pi(s)$ donne le retour moyen espéré en partant de l’état $s$ et en suivant la politique $\pi$. Elle est essentielle pour évaluer la performance d’une politique dans un état donné.

• La state-action value function $q^\pi(s, a)$ fournit une évaluation plus fine en considérant la valeur d’une action spécifique $a$ dans un état $s$, avant de suivre $\pi$.

• Ces fonctions sont liées par la relation :
  $v^\pi(s) = \sum_{a} \pi(a|s) q^\pi(s, a)$ permettant de passer de l’évaluation d’une politique à une évaluation d’un état ou d’un couple état-action.

• La résolution d’un MDP consiste à calculer ces fonctions pour identifier la politique optimale $\pi^*$, qui maximise le retour attendu dans tous les états (voir section 6 pour les équations de Bellman).

• La fonction de valeur d’un état est souvent utilisée dans les méthodes de policy evaluation, tandis que la fonction de valeur d’un couple état-action est centrale dans les méthodes basées sur l’action, comme Q-learning.

💡 À retenir

Les fonctions de valeur, $v^\pi$ et $q^\pi$, sont des outils clés pour évaluer et optimiser une politique dans un MDP, en permettant de quantifier le retour attendu et de guider la recherche de stratégies optimales.

📖 6. Équations de Bellman

🔑 Notions clés & Définitions

• Équations de Bellman d’espérance : Formulations récursives qui expriment la valeur d’un état ou d’une paire état-action en fonction des valeurs futures attendues, en utilisant l’espérance mathématique. Selon Bellman (1957), elles permettent de décomposer la valeur d’un état ou d’une action en termes de ses successeurs, facilitant ainsi leur calcul itératif.

• Équations d’optimalité de Bellman : Version des équations de Bellman qui caractérisent la valeur optimale en sélectionnant la meilleure action possible à chaque étape. Elles établissent que la valeur optimale d’un état ou d’une paire état-action est égale à la maximum sur toutes les actions possibles des valeurs espérées, comme formulé par Bellman (1957).

• Utilisation des équations pour calculer les fonctions de valeur : Les équations de Bellman servent de base pour déterminer de manière itérative ou directe la fonction de valeur (V ou Q) associée à une politique ou à la valeur optimale, en résolvant un système d’équations ou en appliquant des méthodes d’itération (ex. Value Iteration).

📝 Points essentiels

• Les équations de Bellman d’espérance expriment la valeur d’un état ou d’une action en fonction des valeurs futures, en intégrant la probabilité de transition et la récompense attendue, permettant une décomposition récursive essentielle pour l’apprentissage et la planification (Bellman, 1957).

• Les équations d’optimalité de Bellman introduisent la notion de maximisation, en indiquant que la valeur optimale d’un état ou d’une action est obtenue en choisissant l’action qui maximise la somme de la récompense immédiate et de la valeur espérée du prochain état, ce qui permet de définir la politique optimale (Bellman, 1957).

• La résolution de ces équations permet de calculer efficacement les fonctions de valeur (V et Q), soit par des méthodes itératives (Value Iteration), soit par des approches de programmation dynamique, en exploitant leur nature récursive pour converger vers la solution optimale.

• La récursivité des équations de Bellman facilite leur utilisation dans des algorithmes d’approximation ou de convergence, en permettant de mettre à jour successivement les valeurs jusqu’à atteindre la stabilité ou la convergence.

• Lien entre Bellman et l’optimalité : Les équations d’optimalité de Bellman sont à la base de la démonstration de la convergence vers la politique optimale dans les méthodes de planification, telles que la Value Iteration, en assurant que la solution trouvée satisfait la condition de Bellman optimalité.

💡 À retenir

Les équations de Bellman, qu’elles soient d’espérance ou d’optimalité, constituent le fondement mathématique permettant de décomposer, calculer et optimiser les fonctions de valeur dans les processus de décision markoviens, en assurant une convergence vers la politique ou la valeur optimale.

📖 7. Méthodes policy iteration

🔑 Notions clés & Définitions

• Policy evaluation : processus consistant à calculer la fonction de valeur d’une politique π jusqu’à ce qu’elle converge, c’est-à-dire que la différence entre deux itérations successives soit inférieure à un seuil. Elle permet d’obtenir une estimation précise du retour moyen associé à π.
• Policy improvement : étape qui consiste à déduire une nouvelle politique π' à partir des valeurs calculées lors de la policy evaluation, en choisissant pour chaque état l’action qui maximise la valeur d’état ou d’action.
• Boucle itérative Policy evaluation → Policy improvement : processus itératif où, à chaque cycle, la policy est évaluée jusqu’à convergence, puis améliorée, jusqu’à ce que la politique ne change plus, assurant la convergence vers la politique optimale π*.
• Convergence vers politique optimale π* : propriété selon laquelle la boucle itérative de policy evaluation et policy improvement aboutit à une politique qui ne peut plus être améliorée, c’est-à-dire optimale pour le problème donné.
• Entrées et sorties des étapes :
  • Policy evaluation : entrée : politique π, sortie : fonction de valeur Vπ ou Qπ ;
  • Policy improvement : entrée : Vπ ou Qπ, sortie : nouvelle politique π';
  • Boucle : alterne entre ces deux étapes jusqu’à convergence.

📝 Points essentiels

• La méthode de policy iteration combine deux étapes fondamentales : la policy evaluation, qui calcule la valeur d’une politique jusqu’à ce qu’elle soit stable, et la policy improvement, qui met à jour la politique en utilisant ces valeurs.
• La policy evaluation peut être effectuée par une convergence itérative ou par une méthode directe (ex. résolution d’un système d’équations).
• La policy improvement utilise la relation de Bellman pour déterminer la meilleure action dans chaque état, en maximisant la valeur d’état ou d’action.
• La boucle itérative entre policy evaluation et policy improvement garantit la convergence vers la politique optimale π* (voir PERROUX (date)).
• La méthode est dite "model-based" car elle suppose la connaissance du modèle p et r pour effectuer la policy evaluation et l’amélioration.
• La convergence est assurée sous des conditions de contraction, notamment lorsque la politique est évaluée jusqu’à convergence à chaque étape.

💡 À retenir

La policy iteration est une méthode efficace pour obtenir une politique optimale en alternant entre évaluation précise de la politique courante et amélioration basée sur ces évaluations, garantissant la convergence vers la solution optimale.

📖 8. Méthodes value iteration

🔑 Notions clés & Définitions

• Value Iteration : Méthode itérative visant à calculer directement la fonction de valeur optimale $v^*$ en utilisant l’opérateur de Bellman optimal, sans passer par une étape explicite d’amélioration de politique (voir aussi "Suppression de la boucle explicite d’amélioration de politique"). Elle converge vers $v^*$ en itérant jusqu’à ce que la différence entre deux estimations successives soit négligeable.
• Opérateur de Bellman optimal : Fonction mathématique qui met à jour la valeur d’un état en prenant la maximum sur toutes les actions possibles, intégrant la récompense immédiate et la valeur future estimée, permettant de dériver la politique optimale à partir de la valeur.
• Convergence vers $v^*$ : Propriété de la value iteration où, sous certaines conditions (par exemple, discount factor $\gamma < 1$), la suite des estimations de la fonction de valeur se rapproche de la valeur optimale $v^*$ à chaque itération, assurant ainsi la solution optimale du problème.
• Dérivation de la politique optimale : À partir de la fonction de valeur $v^*$, la politique optimale $\pi^*$ est obtenue en choisissant, pour chaque état, l’action qui maximise la somme de la récompense immédiate et de la valeur estimée de l’état suivant, selon l’équation de Bellman optimal.

📝 Points essentiels

• La value iteration remplace la boucle d’amélioration de politique par une mise à jour simultanée de la fonction de valeur à chaque étape, utilisant l’opérateur de Bellman optimal.
• La méthode consiste à appliquer itérativement l’opérateur de Bellman optimal à la fonction de valeur courante :
  $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]$ où $p(s'|s,a)$ est la probabilité de transition, $r(s,a,s')$ la récompense, et $\gamma$ le facteur d’actualisation.
• La convergence vers $v^*$ est garantie par le théorème de contraction de l’opérateur de Bellman, sous condition que $\gamma < 1$.
• Une fois $v^*$ obtenu, la politique optimale $\pi^*$ est dérivée en choisissant, pour chaque état, l’action qui maximise l’expression ci-dessus.
• La suppression de la boucle explicite d’amélioration de politique permet d’optimiser directement la fonction de valeur sans étape intermédiaire de mise à jour de la politique.

💡 À retenir

La value iteration est une méthode efficace pour obtenir la fonction de valeur optimale $v^*$ et la politique optimale $\pi^*$ en utilisant l’opérateur de Bellman optimal, avec convergence garantie vers la solution optimale, sans boucle explicite d’amélioration de politique.

📖 9. Méthodes modified policy iteration

🔑 Notions clés & Définitions

• Modified Policy Iteration (MPI) : Méthode hybride entre Policy Iteration (PI) et Value Iteration (VI), où l’évaluation de la politique est effectuée partiellement (k itérations) avant une étape d’amélioration, permettant de réduire le coût computationnel tout en conservant une convergence vers la politique optimale. (source : Léo Saulières, 22/23)

• Policy evaluation partielle : Processus consistant à effectuer un nombre limité d’itérations (k) pour estimer la valeur d’une politique donnée, sans attendre la convergence complète, afin d’accélérer la procédure d’optimisation. (source : Léo Saulières, 22/23)

• Compromis entre PI et VI : La MPI combine la rapidité de VI (mise à jour immédiate des valeurs) et la stabilité de PI (évaluation complète), en permettant une évaluation partielle pour réduire le coût tout en progressant vers la politique optimale. (source : Léo Saulières, 22/23)

📝 Points essentiels

• La MPI est conçue pour optimiser le processus de résolution d’un MDP en limitant le nombre d’itérations de l’évaluation de la politique (k) avant de procéder à une étape d’amélioration, ce qui permet de diminuer le coût computationnel par rapport à la PI classique.
• La méthode consiste à effectuer k itérations de l’évaluation de la valeur (similaire à VI partiel) puis à mettre à jour la politique en utilisant la fonction de valeur partiellement évaluée.
• La MPI est particulièrement utile lorsque l’évaluation complète (convergence de V) est coûteuse, mais qu’une approximation suffisante permet d’atteindre rapidement une politique proche de l’optimalité.
• Elle constitue un algorithme hybride entre la PI (évaluation complète) et la VI (mise à jour immédiate), permettant une meilleure gestion du coût de calcul tout en assurant la convergence vers la politique optimale.
• La mise en œuvre implique de choisir un nombre k d’itérations pour l’évaluation partielle, puis de faire une étape d’amélioration de la politique, et de répéter jusqu’à convergence ou satisfaction d’un critère d’arrêt.

💡 À retenir

La Modified Policy Iteration offre un compromis efficace entre la rapidité de la Value Iteration et la stabilité de la Policy Iteration, en utilisant une évaluation partielle pour réduire le coût tout en assurant la convergence vers la politique optimale.

📖 10. Méthodes model-free

🔑 Notions clés & Définitions

• Interaction avec l’environnement sans connaissance des dynamiques (p et r inconnus) : Approche où l’agent apprend en expérimentant directement dans l’environnement, sans accès préalable aux fonctions de transition p ou de récompense r, en observant uniquement les transitions et récompenses réelles (voir "Observation des transitions et récompenses réelles").
• Apprentissage par essais et erreurs : Processus où l’agent explore différentes actions, observe les résultats, et ajuste ses stratégies en fonction des récompenses obtenues, afin d’améliorer ses performances sans modèle explicite de l’environnement.
• Méthodes model-free comme Q-learning, SARSA : Techniques d’apprentissage où l’agent ne construit pas de modèle de l’environnement, mais apprend directement une politique ou une fonction de valeur à partir des expériences, en utilisant des algorithmes tels que Q-learning (Watkins, 1989) ou SARSA (Rummery & Niranjan, 1994).
• Apprentissage direct de la politique ou des fonctions de valeur : Approche où l’agent optimise directement sa stratégie (politique π) ou ses fonctions de valeur (v, q) en se basant uniquement sur les données d’expériences, sans modélisation préalable.
• Observation des transitions et récompenses réelles : Processus d’apprentissage basé sur les données collectées lors de l’interaction avec l’environnement, en enregistrant chaque transition (état, action, nouvel état, récompense) pour ajuster la stratégie.

📝 Points essentiels

• Les méthodes model-free permettent à l’agent d’apprendre dans un environnement inconnu en se basant uniquement sur ses expériences, sans connaître p ou r à l’avance.
• Elles reposent sur l’observation directe des transitions et récompenses réelles, en utilisant des algorithmes comme Q-learning ou SARSA, qui ajustent les fonctions de valeur ou la politique en temps réel.
• Contrairement aux méthodes model-based, elles ne construisent pas de modèle de l’environnement, ce qui leur confère une plus grande flexibilité dans des environnements dynamiques ou inconnus.
• La convergence et la performance dépendent souvent de stratégies d’exploration (ex : ε-greedy) et de paramètres d’apprentissage (taux d’apprentissage, taux d’exploration).
• Ces méthodes sont particulièrement adaptées aux situations où la modélisation précise de l’environnement est difficile ou coûteuse, comme dans les jeux vidéo, la robotique ou la finance.

💡 À retenir

Les méthodes model-free permettent à un agent d’apprendre efficacement en expérimentant directement dans un environnement inconnu, en se basant uniquement sur ses observations, sans besoin de connaître ou de modéliser ses dynamiques.

📊 Tableaux de Synthèse

Méthode	Principe	Avantages	Inconvénients	Auteur / Référence
Policy Iteration	Alternance évaluation précise de la valeur puis amélioration de la politique	Convergence rapide vers la politique optimale	Coût élevé pour l’évaluation complète à chaque étape	Howard (1960), Saulières (2022)
Value Iteration	Mise à jour simultanée de la valeur via l’équation de Bellman optimale	Plus simple à implémenter, convergence assurée	Peut nécessiter de nombreuses itérations	Bellman (1957), Saulières (2022)
Modified Policy Iteration	Évaluation partielle de la politique, puis amélioration	Moins coûteux que Policy Iteration, bonne convergence	Moins précis dans l’évaluation, nécessite un compromis	Saulières (2022)

⚠️ Pièges & Confusions Fréquentes

1. Confondre policy iteration et value iteration : la première évalue puis améliore, la seconde met à jour directement la valeur optimale.
2. Croire que la connaissance exacte de p et r est toujours nécessaire : méthodes model-free n’en ont pas besoin.
3. Confondre modèle (p, r) et approche (model-based vs model-free) : l’un concerne la connaissance, l’autre la stratégie d’apprentissage.
4. Sous-estimer le coût de l’évaluation précise dans policy iteration : cela peut devenir prohibitif pour de grands espaces d’états.
5. Confondre la propriété markovienne avec la dépendance aux états passés : elle stipule uniquement que la dynamique dépend du présent.
6. Penser que la value iteration converge plus vite que policy iteration : cela dépend du problème, mais en général, policy iteration peut être plus rapide.
7. Mauvaise compréhension des modified policy iteration : une évaluation partielle permet de réduire le coût tout en maintenant une bonne convergence.

✅ Checklist Examen

1. Connaître la définition du processus de décision markovien (MDP) selon Saulières (2022).
2. Savoir expliquer la propriété markovienne et ses implications pour la modélisation.
3. Maîtriser la formulation <S, A, p, r> et leur rôle dans le MDP.
4. Savoir distinguer entre méthodes model-based et model-free, avec exemples.
5. Connaître le principe de la policy iteration, ses étapes et ses avantages.
6. Comprendre le fonctionnement de la value iteration et ses différences avec policy iteration.
7. Être capable d’expliquer la méthode de modified policy iteration et ses bénéfices.
8. Connaître les principales références : Bellman (1957), Howard (1960), Saulières (2022).
9. Savoir quand utiliser une méthode planifiée versus une méthode basée sur l’interaction.
10. Identifier les limites et pièges liés à la connaissance ou à l’estimation de p et r.
11. Savoir décrire comment la convergence est assurée dans ces méthodes.
12. Vérifier la compréhension de la différence entre la modélisation et l’apprentissage dans le contexte du RL.