• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 20/01/2020

Formalisez mathématiquement le problème de prise de décision

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Jusqu’ici, nous avons défini un PDM comme un modèle capable à la fois de décrire la dynamique du système et de commander ce système. Pour prescrire des actions de façon rationnelle, il faut les ordonner suivant un jugement de valeur.

Comment modélise t-on ce jugement de valeur sur les différentes actions ? 

Fonction de récompense

Pour répondre à la question précédente, nous allons compléter la définition d’un PDM par une fonction supplémentaire, appelée fonction de récompense.

Les récompenses sont essentielles pour ordonner et évaluer nos préférences face à différentes situations dans lesquelles pourrait se trouver notre système.  Par exemple, si nous avons à ordonner deux situations — celle décrivant le crash de notre drone et celle décrivant une navigation sans heurt — notre préférence ira probablement au second scénario. Les jugements de valeur associés à ces deux scénarios seront choisis en accord avec cette préférence.

Intuitions derrière le concept de récompense.
Intuitions derrière le concept de récompense

Processus décisionnel de Markov récompensé

Nous avons défini un formalisme capable de représenter le système dans lequel évolue notre drone autonome, sa dynamique, ainsi que nos jugements de valeur en fonction des situations dans lesquelles il pourrait se retrouver.

Mais comment utiliser ce formalisme afin de définir un problème d’optimisation ? 

En connaissance d’un processus décisionnel de Markov récompensé, il nous faut définir un objectif qui guidera l’agent dans le choix des actions prescrites au drone autonome.

Critères objectifs

Dans un processus décisionnel de Markov récompensé, le but est d’optimiser l’espérance du cumul des récompenses immédiates, calculée pour toute la durée de vie du processus. Il existe pour cela trois principaux critères objectifs — tous font appel au concept de « retour ».

Dans l’expression du retour, Gt, le paramètre H indique la durée de vie maximale du processus. On distinguera les trois principaux critères objectifs suivant les valeurs de H :

  1. le critère décompté optimise l'espérance des retours lorsque la durée de vie du processus est non bornée, c'est-à-dire H= et αt=γt0<γ1 ;

  2. le critère total optimise l'espérance des retours lorsque la durée de vie du processus est bornée, c'est-à-dire H< et αt=1 ;

  3.  le critère moyen optimise la moyenne des retours durant la vie du processus, c'est-à-dire limH et  αt=1H pour tout t .

Décrivez le comportement d'un agent : politique

Le retour définit une mesure de performance associée à  une séquence donnée de transitions.

Mais comment sont choisies les actions qui permettent de générer ces transitions ?

Pour répondre à cette question, nous devons formaliser ce que signifie prendre une décision. Nous allons ainsi définir le concept de politique. Intuitivement, une politique définit le comportement de l'agent durant toute la durée de vie du processus.  

Notez que cette politique définit un comportement stochastique. En d’autres termes, si le système est dans l’état St=s , la politique prescrit la probabilité que l’action At=a soit exécutée par l'agent. Cette caractéristique est importante lorsque l'on souhaite un comportement non déterministe, notamment pour l'exploration d'un environnement. Nous distinguons ainsi des politiques déterministes et des politiques stochastiques

Une politique déterministe prescrit toujours, pour un même état, la même action. À l'opposé, une politique stochastique prescrit, pour un même état, différentes actions selon la distribution sur l'ensemble des actions sachant l'état. Une politique Markovienne est une politique qui ne dépend que de l'état.

Fonction de valeur dépendant de l’état

Sachant que le retour ne traduit que la mesure de performance d’une seule trajectoire générée sous le contrôle d’une politique donnée, un certain nombre de questions sur la mesure de performance associée à une politique restent ouvertes. Nous allons traiter une de ces questions :

Comment savoir à quel point il est bon d’être dans un état s lorsque le système est sous le contrôle d’une politique π ?  

Eh bien, il nous faut introduire pour cela le concept de fonction de valeur dépendant de l’état. Il s’agit d’une fonction Vπ:SR qui associe à chaque état sS une valeur réelle, Vπ(s) , correspondant à un des trois critères discutés plus haut lorsque l'agent part de l'état s et suit les actions prescrites par la politique π :

Vπ(s)=Eπs{G0|S0=s},sS.

Fonction de valeur dépendant de l’état et de l’action

Il est tout aussi important de définir le concept de fonction de valeur dépendant de l'état et de l'action. Cette fonction Qπ:S×AR associe à chaque état sS et chaque action aA une valeur réelle, Qπ(s,a) , correspondant à un des trois critères discutés plus haut lorsque l'agent part de l'état s et l'action a , puis suit les actions prescrites par la politique π :

Qπ(s,a)=Eπs,a{G0|S0=s,A0=a},sS,aA.

Équation d’optimalité de Bellman

Nous avons vu précédemment comment représenter le comportement d'un agent en utilisant le concept de politique. Nous avons également vu comment définir un jugement de valeur pour une politique donnée, à travers le concept de fonction de valeur dépendant de l'état (et de l'action). Cependant, nous n’avons toujours pas défini une méthode incrémentale pour le calcul d’une politique optimale. C’est l’objet de cette courte partie.

Le calcul d’une politique optimale, notée π , repose sur le principe d’optimalité de Bellman.

Ce principe se traduit formellement par l’équation d’optimalité de Bellman donnée par :

V(s)=maxaAsSP(s,a,s)(R(s,a,s)+αV(s)),sS.

En français, cela se lit comme suit : la fonction de valeur optimale en l’état s, notée V(s), est égale au maximum, sur l’ensemble des actions, de la moyenne des récompenses immédiates suivie de la valeur optimale en l’état successeur. 

Par la suite, nous allons étudier les méthodes d'apprentissage machine capables de résoudre l'équation d'optimalité de Bellman.

Exemple de certificat de réussite
Exemple de certificat de réussite