Processus de décision markovien

Une politique décrit les choix des actions à jouer par l'agent dans chaque état. Formellement, il s'agit donc d'une fonction ${\displaystyle \pi :S\to A}$ dans le cas d'une politique déterministe ou ${\displaystyle \pi :S\times A\to [0;1]}$ dans le cas stochastique. On note parfois ${\displaystyle \pi (a|s)}$ la probabilité de jouer a dans l'état s, i.e. ${\displaystyle \mathbb {P} [A_{t}=a\mid S_{t}=s]}$, la probabilité de jouer a à l'instant t sachant que l'état à l'instant t est s. Cette valeur est indépendante de t : on parle de politique stationnaire. Etant donné un MDP et une politique, on obtient une chaîne de Markov avec récompense. Nous nous plaçons dans le cas déterministe.

L'agent choisit une politique à l'aide de la fonction de récompense ${\displaystyle R}$. Notons ${\displaystyle r_{t}=R(s_{t},\pi (s_{t}),s_{t+1})}$ la récompense effective obtenue après avoir effectué l'action ${\displaystyle \pi (s_{t})}$ par l'agent qui suit la politique ${\displaystyle \pi }$. Voici plusieurs critères d'intérêts que l'agent peut chercher à maximiser :

• ${\displaystyle E\left(\sum _{t=0}^{h}r_{t}\right)}$: espérance de la somme des récompenses à un horizon fini fixé ${\displaystyle h}$ ;
• ${\displaystyle \liminf _{h\to +\infty }E\left({1 \over h}\sum _{t=0}^{h}r_{t}\right)}$ou ${\displaystyle \limsup _{h\to +\infty }E\left({1 \over h}\sum _{t=0}^{h}r_{t}\right)}$: récompense moyenne à long terme ;
• ${\displaystyle E\left(\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right)}$: récompense escomptée (ou amortie) à horizon infini où ${\displaystyle 0\leq \gamma <1}$.

Le dernier critère est courant et c'est celui que nous adoptons dans la suite. La valeur de ${\displaystyle \gamma }$ permet de définir l'importance que l'on donne au futur. Quand ${\displaystyle \gamma =0}$ nous sommes face à un agent «pessimiste» qui ne cherche qu'à optimiser son gain immédiat. À l'opposé si ${\displaystyle \gamma \to 1}$, l'agent est «optimiste» puisqu'il tient de plus en plus sérieusement compte du futur lointain (si ${\displaystyle \gamma =1}$, l'agent tient autant compte du futur lointain que du gain immédiat).

Lorsqu'une politique et un critère sont déterminés, deux fonctions centrales peuvent être définies :

• ${\displaystyle V^{\pi }:S\to \mathbb {R} }$: c'est la fonction de valeur des états; ${\displaystyle V^{\pi }(s)}$ représente le gain (selon le critère adopté) engrangé par l'agent s'il démarre à l'état ${\displaystyle s}$ et applique ensuite la politique ${\displaystyle \pi }$ ad infinitum.
• ${\displaystyle Q^{\pi }:S\times A\to \mathbb {R} }$: c'est la fonction de valeur des états-actions; ${\displaystyle Q^{\pi }(s,a)}$ représente le gain engrangé par l'agent s'il démarre à l'état ${\displaystyle s}$ et commence par effectuer l'action ${\displaystyle a}$, avant d'appliquer ensuite la politique ${\displaystyle \pi }$ ad infinitum.

Les deux fonctions sont intimement liées. On a toujours ${\displaystyle V^{\pi }(s)=Q^{\pi }(s,\pi (s))}$ et, dans le cas du gain amorti à horizon infini, on peut également écrire que:

${\displaystyle Q^{\pi }(s,a)=\sum _{s'\in S}[R(s,a,s')+\gamma V^{\pi }(s')]T(s,a,s').}$

Cette dernière relation montre que la fonction ${\displaystyle V^{\pi }}$ vérifie une relation de récurrence appelée équation de Bellman:

${\displaystyle V^{\pi }(s)=\sum _{s'\in S}[R(s,\pi (s),s')+\gamma V^{\pi }(s')]T(s,\pi (s),s').}$

L'équation de Bellman s'écrit comme l'équation linéaire suivante dans la chaîne de Markov avec récompenses "applatie" à partir du processus de décision markovien et la politique ${\displaystyle \pi }$ :

${\displaystyle V^{\pi }=R^{\pi }+\gamma P^{\pi }V^{\pi }}$

où ${\displaystyle V^{\pi }}$ est le vecteur contenant les valeurs pour chaque état, ${\displaystyle R^{\pi }}$ est la matrice des récompenses, ${\displaystyle P^{\pi }}$est la matrice des probabilités.

Le but de l'agent est de trouver la politique optimale ${\displaystyle \pi ^{*}}$ qui lui permet de maximiser son gain, c'est-à-dire celle qui vérifie, pour tout état ${\displaystyle s\in S}$, ${\displaystyle V^{\pi ^{*}}(s)\geq V^{\pi }(s)}$ quelle que soit l'autre politique ${\displaystyle \pi }$. On peut montrer que la fonction de valeurs optimale ${\displaystyle V^{*}}$ vérifie l'équation d'optimalité de Bellman:

${\displaystyle V^{*}(s)=\max _{a\in A}\sum _{s'\in S}[R(s,\pi (s),s')+\gamma V^{*}(s')]T(s,a,s').}$

De manière analogue, la fonction ${\displaystyle Q}$ vérifie elle aussi une équation d'optimalité:

${\displaystyle Q^{*}(s,a)=\sum _{s'\in S}[R(s,a,s')+\gamma \max _{a'\in A}Q^{*}(s',a')]T(s,a,s').}$

Les équations d'optimalité de Bellman ne sont pas linéaires, il faut donc abandonner l'idée de les résoudre algébriquement. En revanche, l'opérateur de Bellman ${\displaystyle K^{*}}$ défini par

${\displaystyle K^{*}(f)(s)=\max _{a\in A}\sum _{s'\in S}[R(s,a,s')+\gamma f(s')]T(s,a,s'),}$

définit encore une contraction dont ${\displaystyle V^{*}}$ est un point fixe. La fonction de valeurs optimale peut donc à nouveau s'approcher par un processus itératif à convergence exponentielle.

La méthode itérative que nous venons de voir pour les équations d'optimalité de Bellman fournit un premier algorithme, appelé itération sur la valeur (VI: Value-Iteration) permettant de déterminer ${\displaystyle \pi ^{*}}$. Il suffit en effet de déterminer ${\displaystyle V^{*}}$ avec une précision donnée, et on peut en déduire la politique optimale par:

${\displaystyle \pi (s)=\arg \max _{a\in A}Q^{*}(s,a)=\arg \max _{a\in A}\sum _{s'\in S}[R(s,a,s')+\gamma V^{*}(s')]T(s,a,s').}$

Une difficulté dans cet algorithme est de déterminer la précision avec laquelle calculer ${\displaystyle V^{*}}$ de manière à être sûr d'en déduire effectivement la politique optimale.

Description générale d'un algorithme d'itération de la politique

Un autre algorithme, appelé itération de la politique (PI: Policy-Iteration) essaye d'obtenir la politique optimale sans nécessairement calculer «jusqu'au bout» les valeurs de ${\displaystyle V^{*}}$. L'idée est de partir d'une politique quelconque ${\displaystyle \pi _{0}}$, puis d'alterner une phase d'évaluation, dans laquelle la fonction ${\displaystyle V^{\pi _{n}}}$ est déterminée (avec une des techniques vues plus haut), et une phase d'amélioration, où l'on définit la politique suivante ${\displaystyle \pi _{n+1}}$ par:

${\displaystyle \pi _{n+1}(s)=\arg \max _{a\in A}\sum _{s'\in S}[R(s,a,s')+\gamma V^{\pi _{n}}(s')]T(s,a,s').}$.

Cet algorithme prend fin lorsqu'aucune évolution de la politique n'est observée, ie, lorsque ${\displaystyle \pi _{n+1}(s)=\pi _{n}(s)}$ pour tout ${\displaystyle s}$.

Si dans l'algorithme précédent l'on utilise une méthode itérative pour évaluer ${\displaystyle V^{\pi }}$, alors se pose la question de savoir à quelle précision s'arrêter. Ce problème n'en est en réalité pas un, car on peut montrer que même si l'on tronque l'évaluation de ${\displaystyle V^{\pi }}$, l'algorithme converge tout de même vers l'optimal. À l'extrême, c'est-à-dire lorsqu'une seule itération est utilisée pour évaluer ${\displaystyle V^{\pi }}$, et après avoir réuni en une seule étape de calcul la phase d'amélioration et la phase d'évaluation, on retombe sur l'algorithme VI.

L'algorithme PI peut également se formuler dans les termes de la fonction d'états-actions ${\displaystyle Q}$ plutôt que ${\displaystyle V}$. On voit donc qu'un grand nombre de variantes peuvent être imaginées, mais tournant toutes autour d'un même principe général qui est schématisé à la figure ci-contre.