Section 7.2 Ojbectif et algorithmes de recherche
Ici on va rapidement introduire les questions que posent les MDP ainsi que les approches traditionnnelles.
Dans cette partie on considère les espaces des états \(S\) et des actions \(A\) comme dénombrable. A partir de la définition des problèmes de décision Markovien et la définition des notions de règles de décisions et de politiques deux questions se posent:
à partir d'un état \(s\text{,}\) quel est la meilleur action qui maximise les récompenses espérées,
pour l'ensemble des états \(s\text{,}\) quel est la meilleur politique qui maximise les récompenses espérées.
On va définir maintenant les différents termes qui correspondent à ces deux objectifs.
Plannification immédiate: recherche de la meilleur trajectoire à partir d'un état en utilisant modèle (recherche de politique locale, contrôle optimale en boucle ouverte),
Plannification globale: recherche de la meilleure politique globale à partir du modèle (contrôle en boucle fermé),
Apprentissage par renforcement: recherche de la meilleure politique en intéraction avec l'environnement donc sans connaitre le modèle.
La différence fondamententale entre l'apprentissage par renforcement et la plannification est la connaissance du modèle. Les méthodes de renforcement vont partir du principe qu'on ne connait pas le modèle mais qu'on peut intérargir avec lui. Cela veut dire qu'a chaque étape temporelle, on connair un état on peut proposer une action à l'environnement renvoit l'état suivant et la récompense. En pratique, les algorithmes d' apprentissage par renforcement vont construire le modèle (implicitement ou explicitement) et construire le contrôle. Une méthode de plannification immédiate peut (grâce au caractère Markovien) être utilisée sur chaque état pour construire une politique globale et faire de la plannification globale (en pratique peu optimal). Un problème de décision peut être écrit comme un arbre des trajectoires possibles (\ref{exemple_tree.jpg}) sur les états, avec les branches données par les actions et les poids sur ces branches données par les récompenses.
Dans le cadre dénombrable, la recherche de la meilleur action (plannification immédiate) revient a un problème de chemin maximisant les poids (équivalent à un problème de plus court chemin de graphe). On parle de recherche exhautive. Pour cela on peut utiliser l'algorithme du plus court chemin de Dijkstra, l'algorithme de recherche en largeur, ou des versions stochastiques (ref). Cependant ces algorithmes ne sont assez performant quand l'ensemble des états atteignables est très important. Après ces algorithmes de recherche classique, on peut utiliser des algorithmes de recherche heuristique qui utilise une information partielle (qu'on appelle une heuristique) qu'on aurait sur la solution. Dans tout les cas algorithmes sont vites très couteux (les arbres étant vite très profonds) et son inutilisable en pratique. Dans la suite on va introduire des méthodes de renforcement et de plannification permettant de traiter de genre de problème.