Programmation dynamique

Section 7.3 Programmation dynamique

La programmation dynamique est une approche permettant de résoudre des problèmes de type MDP de façon plus efficace que les méthodes de recherche dans le cadre du modèle parfait.

La programmation dynamique ne fait pas partie des méthodes de reforcement. Cependant elle est intéressante et introduit des outils essentiel pour les méthodes de renforcement.

Subsection 7.3.1 Fonction valeur et équation de Bellman

On va introduire une théorie caractérisant les politiques optimales. Cela permettra par la suite de proposer des algorithmes.

Subsubsection 7.3.1.1 Fonction valeur et politique optimale

Afin de construire une relation d'ordre sur les politiques on souhaite évaluer une politique. Pour cela on introduit une notion fondamentale: La fonction valeur.

Définition 7.14. Fonction valeur.

La >fonction valeur associée à une politique $\pi$ et un etat $s$ est donnée par

\begin{equation*} V^{\pi}(s) = \mathbb{E}\left[ G_t \mid s_t = s, \pi \right] \end{equation*}

Il s'agit donc de l'espérance des recompenses lorsqu'on part d'un état $s$ et lorsqu'on les actions sont données par une politique $\pi\text{.}$ Dans la définition part de $s_t$ mais on peut changer la définition par $s_0\text{.}$ En effet le processus en temps étant Markovien il ne depend pas explicitement du temps, seulement de l'état courant. Bien qu'elle n'interviendra que plus tard on peut définir une autre fonction d'évaluation.

Définition 7.15. Q-Fonction.

La fonction valeur état-action ou la Q-fonction associée à une politique $\pi$ et un etat $s$ est donnée par

\begin{equation*} Q^{\pi}(s,a) = \mathbb{E}\left[ G_t \mid s_t = s, a_t=a, \pi \right] \end{equation*}

La Q-fonction calcul aussi l'espérance des récompenses partant d'un $s$ suivant la politique $\pi$ mais en laissant la 1er action libre de ne pas être donnée par la politique. Les deux fonctions sont liées par:

\begin{equation*} V(s) = Q(s,\mu(s)) \end{equation*}

dans le cas déterministe et

\begin{equation*} V(s) = \sum_{a\in A} \pi(a\mid s)Q(s,a) \end{equation*}

dans le cas stochastique.

Définition 7.16. Politique Gloutonne.

Une politique déterministe $\mu(.)$ est dite gloutonne si elle satisfait :

\begin{equation*} \mu(s) = \operatorname{argmax}_{a}Q^{\mu}(s,a) \end{equation*}

Maintenant ces fonctions d'évaluation de politique obtenues on peut définir une relation d'ordre sur les politiques et introduire la notion de politique optimale.

Définition 7.17.

La relation d'ordre sur les politiques par

\begin{equation*} \pi(.) \gt \pi^{'}(.) \mbox{ si } V^{\pi}(s) \gt V^{\pi^{'}}(s), \quad \forall s\in S \end{equation*}

Définition 7.18. Politique optimale.

Une politique $\pi^*$ est dite optimale si elle satisfait:

\begin{equation*} V^{\pi^*}(s) \in \operatorname{argmax}_{\pi} V^{\pi}(s), \quad \forall s \in S \end{equation*}

avec la fonction valeur optimale

\begin{equation*} V^{\pi^*}(s) = V^{*}(s)= max_{\pi} V^{\pi}(s), \quad \forall s \in S \end{equation*}

Définition 7.19. Q-fonction optimale.

On peut aussi définir la fonction Q optimale:

\begin{equation*} Q^{*}(s,a) = max_{\pi} Q^{\pi}(s,a), \quad \forall s \in S, \forall a \in A \end{equation*}

Une fois cette définition obtenue l'enjeu va être de caractériser le mieux possible ces politiques optimales et de proposer des algorithmes pour en calculer une. Avant d'aller plus loin on va montrer qu'on peut considérer uniquement que les politiques et règles de décisions Markovienne.

Proposition 7.20.

Soit $\pi_1 \in \Pi^{ha}$ une politique aléatoire histoire-dépendante. Pour chaque état initial $x\in S\text{,}$ il existe alors une politique aléatoire markovienne $\pi_2 \in \Pi^{ma}$ telle que

\begin{equation*} V^{\pi_1}(x)=V^{\pi_2}(x), \quad \forall x \in S \end{equation*}

Preuve.

On considère $\pi_1$ une politique histoire-dépendante et $s_i$ un état initial. Soit $\pi_2$ une politique Markovienne. On définit cette politique à partir de $\pi_1\text{.}$ On obtient donc

\begin{equation*} \pi_2(a\mid s) = P^{\pi_1}(a_{t+k}=a\mid s_{t+k}=s, s_t=s_i) \end{equation*}

donc $P^{\pi_2}(a_{t+k}=a\mid \mid s_{t+k}=s) = P^{\pi_1}(a_{t+k}=a\mid \mid s_{t+k}=s, s_t=s_i)\text{.}$ On souhaite maintenant montre par récurrence que

\begin{equation} P^{\pi_1}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i) = P^{\pi_2}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i), \quad \forall k\geq 0\tag{7.1} \end{equation}

Pour $k=0$ c'est évident. On suppose que c'ets vrai pour $k-1\text{.}$ On considère maintenant

\begin{equation*} P^{\pi_1}(s_{t+k}=s \mid s_t=s_i)=\sum_{s^{'}\in S}\sum_{a^{'}\in A} P^{\pi_1}(s_{t-1}=s^{'},a_{t-1}=a^{'}\mid s_t=s_i)P(s\mid s^{'},a^{'}) \end{equation*}

puisque on suppose que (7.1) vrai au temps $t+k-1\text{,}$ on a donc

\begin{equation*} P^{\pi_1}(s_{t+k}=s \mid s_t=s_i)=\sum_{s^{'}\in S}\sum_{a^{'}\in A} P^{\pi_2}(s_{t-1}=s^{'},a_{t-1}=a^{'}\mid s_t=s_i)P(s\mid s^{'},a^{'}) \end{equation*}

et donc

\begin{equation*} P^{\pi_1}(s_{t+k}=s \mid s_t=s_i)=P^{\pi_2}(s_{t+k}=s \mid s_t=s_i) \end{equation*}

Ensuite on remarque que:

\begin{equation*} P^{\pi_1}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i) = P^{\pi_1}(a_{t+k}=a \mid s_{t+k}=s)P^{\pi_1}(s_{t+k}=s \mid s_t=s_i) \end{equation*}

\begin{equation*} P^{\pi_2}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i) = P^{\pi_2}(a_{t+k}=a \mid s_{t+k}=s)P^{\pi_2}(s_{t+k}=s \mid s_t=s_i) \end{equation*}

les égalités précedentes donnent donc

\begin{equation*} P^{\pi_1}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i) = P^{\pi_2}(s_{t+k}=s,a_{t+k}=a \mid s_t=s_i) \end{equation*}

ce qui conclut la preuve par récurrence de (7.1). Ensuite on remarque la fonction valeur associée a une politique $\pi$ s'écrit:

\begin{equation*} V^{\pi}(s)= \mathbb{E}[\sum_{k}^{\infty}\gamma^t r_{t+k+1} \mid s_t=s; \pi] =\sum_{k}^{\infty}\gamma^t\mathbb{E}[ r_{t+k+1} \mid s_t=s; \pi] \end{equation*}

\begin{equation*} \mathbb{E}[ r_{t+k+1} \mid s_t=s; \pi]=\sum_{s\in S}\sum_{a\in A}r(s,a)\mathbb{P}^{\pi}(s_{t+k}=s, a_{t+k}=a \mid s_t=x) \end{equation*}

On voit donc que l'égalité des probabilités (7.1) permet d'obtenir l'égalité des fonctions valeurs.

Ce résultat montre que l'on peut considère uniquement les politiques Markoviennes pour résoudre le problème d'optimisation.

Subsubsection 7.3.1.2 Equation de Bellmann

Dans cette sous-section on souhaite exhiber une équation satisfaite par la politique optimale. On va d'abord caractériser les politiques stationnaires par une 1ère équation avant de construire l'équation de Bellman caractérisant la fonction valeur optimale et les politiques optimales.

Définition 7.21.

On se place dans le cadre horinzon infini amorti. Soit $\pi\in D^{am}$ une politique Markovienne aléatoire stationnaire. On définit l'opérator $L_{\pi}$ sur les fonctions valeurs définies par

\begin{equation*} L_{\pi} V= r_{\pi} + \gamma\mathbb{P}^{\pi} V \end{equation*}

avec

\begin{equation*} \mathbb{P}^{\pi}(s_{s+1}=s^{'} \mid s_t = s)=\sum_{a\in A}\pi(a\mid s)P(s^{'} \mid a,s), \quad r_{\pi}=\sum_{a\in A}\pi(a\mid s)r(s,a) \end{equation*}

dans le cas stochastique et

\begin{equation*} \mathbb{P}^{\pi}(s_{s+1}=s^{'} \mid s_t = s)=P(s^{'} \mid \mu(s),s), \quad r_{\pi}=(s,\mu(s)) \end{equation*}

dans le cas déterministe.

Maintenant on va relier cette opérateur à une politique stationnaire dans le cas $\gamma \lt 1\text{.}$ En pratique les futurs résultats sont aussi utilisé pour $\gamma=1\text{.}$

Théorème 7.22.

Soient $\gamma \lt 1$ et $\pi \in D^{ma}$ une politique stationnaire markovienne stationnaire. Alors la fonction valeur $V^{\pi}$ est l'unique solution de l'équation $V^{\pi} = L_{\pi} V^{\pi}\text{,}$ ce qui équivaut à

\begin{equation*} V^{\pi}(s) = r_{\pi}(s) +\gamma \sum_{s^{'} \in S}\mathbb{P}^{\pi}(s^{'} \mid s) V^{\pi}(s^{'}) \end{equation*}

Preuve.

On considère la fonction valeur au temps initial:

\begin{equation*} V_{\gamma}^{\pi}(s) =\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^k r_{t+1} \mid s_0=s\right] \end{equation*}

\begin{equation*} V_{\gamma}^{\pi}(s) =\mathbb{E}^{\pi}\left[r_1+\gamma r_2+\gamma^2 r_3 + ... \mid s_0=s\right] \end{equation*}

\begin{equation*} V_{\gamma}^{\pi}(s) =\mathbb{E}^{\pi}\left[r_1\mid s_0=s\right]+\gamma\mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_0=s\right] \end{equation*}

Si la politique est $\mathbb{E}^{\pi}\left[r_1\mid s_0=s\right]=R(s,\pi(s))=r_{\pi}(s)\text{.}$ Si la politique est stochastique, en utilisant la définition de l'espérance pour une variable aléatoire discrète on a:

\begin{equation*} \mathbb{E}^{\pi}\left[r_1\mid s_0=s\right] = \sum_{a}\pi(a\mid r)R(a,s) =\mathbf{r}_{\pi}(s) \end{equation*}

Dans ce cas: on a une variable aléatoire qui décrit les récompenses pour un état $s\text{,}$ la politique $\pi$ donne les probabilités des valeurs possibles et $r(.,.)$ donne les possibles valeurs. On a donc

\begin{equation*} V_{\gamma}^{\pi}(s) = r_{\pi}(s) +\gamma\mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_0=s\right] \end{equation*}

On souhaite maintenant estimer $\mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_0=s\right]\text{,}$ qui correspond à l'espérance des récompenses avec comme première état $s\text{.}$ La récompense cumulée dépend du 1er état seulement à travers la transition entre le 1er état et le second état $s^{'}\text{,}$ donc:

\begin{equation*} \mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_0=s\right] = \sum_{s^{'}} \mathbb{P}^{\pi}(s^{'}\mid s)\mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_1=s^{'}\right] \end{equation*}

avec $\mathbb{P}^{\pi}$ définit au dessus à l'aide de la politique et des probabilités de transition $p(.\mid.,.)\text{.}$ Pour finir la preuve il suffit de noter que $\mathbb{E}^{\pi}\left[r_2+\gamma^1 r_3 + ... \mid s_1=s^{'}\right]= V_{\pi}(s^{'})\text{.}$ On a donc prouvé que $V_{\gamma}^{\pi}$ satisfait l'équation vectorielle:

\begin{equation*} V_{\gamma}^{\pi} = L_{\pi} V_{\gamma}^{\pi} \end{equation*}

Maintenant on finira la preuve en montrant l'unicité. Pour ca on réécrit l'opérateur sous la forme suivante:

\begin{equation*} \left( I_d -\gamma \mathbb{P}^{\pi}\right) V_{\gamma}^{\pi}= \mathbf{r}_{\pi} \end{equation*}

Puisque $\mathbb{P}^{\pi}$ est une matrice de probabilité, toute les valeurs propres de module inférieur ou égal à 1. Si $\gamma\lt 1$ on a donc que toute les valeurs propres de $\gamma \mathbb{P}^{\pi}$ sont de modules strictement inférieur à 1. En diagonalisant la matrice $\left( I_d -\gamma \mathbb{P}^{\pi}\right)$ dans la base de $\mathbb{P}^{\pi}$ on obtient que toutes les valeurs propres sont strictement positives et donc l'opérateur est inversible.

Corollaire 7.23.

On peut caractériser la Q-fonction sous la forme:

\begin{equation*} Q(s,a) = r(s,a) +\gamma \sum_{s^{'} \in S}P(s^{'} \mid s, a) V^{\pi}(s^{'}), \quad \forall s\in S, a \in A \end{equation*}

Preuve.

Les calculs sont les mêmes que précédement. On ne considère juste pas qua la 1ère action est donnée par la politique.

Corollaire 7.24.

On peut réécrire la caractérisation de la fonction valeur et de la Q fonction sous la forme:

\begin{equation} V^{\pi}(s) = \mathbb{E}[r_{\pi}(s_t) +\gamma V_{\pi}(s_{t+1})\mid s_t=s ], \quad \forall s\in S\tag{7.2} \end{equation}

pour la fonction valeur et

\begin{equation} Q^{\pi}(s,a) = \mathbb{E}[r(s_t,a_t) +\gamma V_{\pi}(s_{t+1})\mid s_t=s, a_t=a], \quad \forall s\in S, a\in A\tag{7.3} \end{equation}

ce qui équivaut à:

\begin{equation} Q^{\pi}(s,a) = \mathbb{E}[r(s_t,a_t) +\gamma Q^{\pi}(s_{t+1},a_{t+1})\mid s_t=s, a_t=a], \quad \forall s\in S, a \in A\tag{7.4} \end{equation}

avec $s_{t+1}$ le nouvel état découlant de $(s,a)$ et $a_{t+1}$ l'action suivante donnée par la politique.

Preuve.

On rappelle que $V = L_{\pi} V\text{.}$ On détaille cela:

\begin{equation*} L_{\pi} V(s) = r_{\pi}(s) + \gamma \sum_{s^{'} \in S}\mathbb{P}^{\pi}(s^{'} \mid s) V^{\pi}(s^{'}), \quad \forall s\in S. \end{equation*}

Lorsqu'on redéveloppe on obtient

\begin{equation*} L_{\pi} V(s) = \sum_a r(s,a)\pi(a\mid s) + \gamma \sum_{s^{'} \in S} \left(\sum_a \pi(a \mid s)P(s^{'} \mid s, a)\right) V^{\pi}(s^{'}), \quad \forall s\in S. \end{equation*}

On réconnait les formules d'espérance on a donc

\begin{equation*} \sum_a \underbrace{r(s,a)}_{valeur}\underbrace{\pi(a\mid s)}_{proba} = E[ r_{\pi}(s)] \end{equation*}

\begin{equation*} \sum_{s^{'} \in S} \underbrace{\left(\sum_a \pi(a \mid s)P(s^{'} \mid s, a)\right)}_{proba} \underbrace{V^{\pi}(s^{'})}_{valeur} = E[V^{\pi}(s_{t+1}) ] \end{equation*}

Le principe est le même pour la fonction $Q\text{.}$ On rappelle juste que $a_{t+1}$ est donnée par la politique donc $V^{\pi}(s_{t+1})=Q^{\pi}(s_t,a_t)\text{.}$

Cette caractérisation utile princiaplement le coté Markovien du problème pour montrer qu'on peut êtablir une récurrence entre la fonction valeur à un état et la fonction valeur pour les états qui lui succède directement. Maintenant qu'on a démontré que les fonctions valeurs satisfont l'équation précédement introduite nous allons pouvoir caractériser la politique optimale. Avant cela on fait un rappel d'analyse.

Théorème 7.25. Point fixe de Banach.

Soient U un espace de Banach et $T$ une contraction sur $U$ ($\parallel Tu - Tv\parallel \leq \lambda \parallel u-v\parallel$ avec $0\leq\lambda \leq 1$). Alors

il existe un unique $u$ tel que $Tu =u\text{,}$
Pour tout $u_0$ la suite $u_n$ définie par

\begin{equation*} u_{n+1}=T u_n \end{equation*}

converge vers $u^*\text{.}$

L’espace $\mathcal{V}$ des fonctions valeurs correspond à $\mathbb{R}^{\mid S\mid}$ qui muni de la norme max est un espace vectoriel normé de dimension fini donc complet. Il suffit donc de montrer que l’opérateur L est une contraction pour cette norme.

Définition 7.26. Equation d'optimalité de Bellmann.

Soit $V$ une fonction valeur on définit l'opérateur $L$ sur les fonctions valeur:

\begin{equation*} L V(s) = \operatorname{max}_{a} \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} | s,a) V(s^{'})\right), \quad \forall s\in S. \end{equation*}

C'est équivalent à

\begin{equation*} L V = \operatorname{max}_{\mu \in D^m}(r_{\mu}+\gamma \mathbf{P}_{\mu} V) \end{equation*}

On va rapidement justifier l'équivalence:

\begin{equation*} L V(s) = \operatorname{max}_{\mu \in D^m}(r_{\mu}(s)+\gamma \mathbf{P}_{\mu} V)= \operatorname{max}_{\mu \in D^m}(r(s,\mu(s))+\gamma \sum_{s^{'}\in S}P(s^{'}\mid s,\mu(s)) V(s^{'})) \end{equation*}

ce qui est équivalent à

\begin{equation*} L V(s) = (r(s,\mu^*(s))+\gamma \sum_{s^{'}\in S}P(s^{'}\mid s,\mu^*(s)) V(s^{'})) \end{equation*}

avec $\mu^*(s) = \operatorname{argmax}_{\mu \in D^m} = a^*$ ou $a^* = \operatorname{argmax}_{a} \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} | s,a) V(s^{'})\right)\text{.}$ Cela justifie l'équivalence entre les deux formulations. On rappelle que dans cette définition la vonction valeur n'est pas liée à une politique.

Théorème 7.27. Equation d'optimalité de Bellmann.

On suppose que l'on maximise le critère d'horizon infini amorti. Pour $\gamma \lt 1\text{,}$ la fonction valeur $V^{\pi^*}(.) \in \mathcal{V}$ de la politique optimal $\pi^*$ est l'unique solution de l'équation de Bellman:

\begin{equation*} V^{\pi^*}(s) = L V^{\pi^*}(s), \quad \forall s\in S \end{equation*}

Preuve.

TOOO DOO / refaire.\\ Dans un 1er temps on va vérifier que la politique optimale si, elle existe satisfait l'équation de Bellman avant de montrer qu'il existe une unique solution. On suppose donc que $\pi^*$ existe par définition de la politique optimale:

\begin{equation*} \displaystyle V^{\pi^*}(s) =\operatorname{max}_{\pi} V_{\gamma}^{\pi} = \operatorname{max}_{\pi} \left(r_{\pi}+ \gamma \mathbb{P}^{\pi} V_{\gamma}^{\pi}\right), \quad \forall \mathbf{s} \in S \end{equation*}

Toutes les politiques $\pi$ peuvent être réécrite comme un couple $(\mathbf{a},\pi^{'})$ avec $a$ la 1ère action appliquée et $\pi^{'}$ la politique pour les actions suivante. Dans ce cas on obtient

\begin{equation*} \displaystyle V^{\pi^*}(s) =\operatorname{max}_{\pi} V_{\gamma}^{\pi} = \operatorname{max}_{(a,\pi^{'})} \left(r_{\pi}+ \gamma \mathbb{P}^{\pi} V_{\gamma}^{\pi}\right), \quad \forall \mathbf{s}\in S. \end{equation*}

Puisque $a$ est la 1ère action de la politique $\pi$ on a $r_{\pi}(s)=\sum_{a^{'}}\pi(a^{'} \mid s)r(s,a^{'})=r(s,a)$ puisque $\pi(a^{'} \mid s)=1$ pour $a^{'}=a$ et zéro sinon par construction. De la mêm façon:

\begin{equation*} \mathbb{P}^{\pi}(s_{s+1}=s^{'} \mid s_t = s)=\sum_{a^{'}\in A}\pi(a^{'}\mid s)P(s^{'} \mid a^{'},s)=P(s^{'} \mid a ,s) \end{equation*}

On a donc

\begin{equation*} \displaystyle V^{\pi^*}(s) = \operatorname{max}_{(a,\pi)} \left(r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} \mid s,a) V_{\gamma}^{\pi^{'}}(s^{'})\right), \quad \forall s \in S \end{equation*}

Puisque $r(s,a)$ et $P(s^{'} \mid a ,s)$ ne dépendent pas de $\pi^{'}$ et que $V_{\gamma}^{\pi^{'}}(s^{'})$ ne dépend pas de $a\text{,}$ on obtient

\begin{equation*} \displaystyle V^{\pi^*}(s) = \operatorname{max}_{a} \left(r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} \mid s,a) \operatorname{max}_{\pi^{'}}V_{\gamma}^{\pi^{'}}(s^{'})\right), \quad \forall s \in S, \end{equation*}

ce qui donne par définition de la fonction valeur optimale:

\begin{equation*} \displaystyle V^{\pi^*}(s) = \operatorname{max}_{a} \left(r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} \mid s,a) V^{\pi^*}(s^{'})\right), \quad \forall s \in S. \end{equation*}

fin TODO \\\\\\\ Maintenant on qu'on à montré que la politique optimale satisfait $V=LV$ on va montré que cette équation admet une unique solution. On remarque qu'il s'agit d'un problème de point fixe dans un espace de Banach, on peut donc appliquer de théorème de point-fixe. Pour cela on doit montrer que l'application $L$ est contractante pour la norme $L^\infty\text{.}$ On commence par regarder:

\begin{equation*} \mid L V(s) - LU(s) \mid \leq \mathrel{\bigg|} \operatorname{max}_{a} \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} | s,a) V(s^{'})\right) -\operatorname{max}_{a} \left( r(s,a)+ \gamma \sum_{s^{'}}P(a^{'} | s,a U(s^{'})\right) \mathrel{\bigg|}. \end{equation*}

Puisque le maximum des valeurs absolues défini une norme on peut donc utilise la propriété $\parallel \mathbf{x} \parallel-\parallel \mathbf{y} \parallel \lt \parallel \mathbf{x}-\mathbf{y} \parallel\text{.}$ On a donc

\begin{equation*} \mid LV(s) - L U(s) \mid \leq \operatorname{max}_{a} \mathrel{\bigg|} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} | s,a) V(s^{'})\right) - \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} | s,a) U(s^{'})\right) \mathrel{\bigg|}, \end{equation*}

\begin{equation*} \mid LV(s) - LU(s) \mid \leq \gamma \operatorname{max}_{a} \mathrel{\bigg|} \sum_{s^{'}}P(s^{'} | s,a) \left(V(s^{'}) - U(s^{'})\right) \mathrel{\bigg|}. \end{equation*}

Puisque la fonction valeur ne dépend pas de l'action on a:

\begin{equation*} \mid V(s) - U(s) \mid \leq \gamma \parallel V - U\parallel_{\infty}\operatorname{max}_{a}\sum_{s^{'}}P(s^{'} | s,a) = \gamma \parallel V(s^{'}) - U(s^{'})\parallel_{\infty}. \end{equation*}

Puisque la précédente relation est vrai pour tous les états on obtient le résultat final:

\begin{equation*} \parallel LV - LU\parallel_{\infty} = \operatorname{max}_{s} \mid V(s) - U(s) \mid \leq \gamma \parallel V - U\parallel_{\infty} \end{equation*}

La politique optimale est celle qui maximise la fonction valeur. En caractérisant la fonction valeur optimale on peut définir la politique optimale.

Corollaire 7.28.

Une politique stationnaire est dit optimale si et ssi sa fonction valeur satisfait l'équation de Bellman ce qui équivaut à

\begin{equation} \pi \in \operatorname{argmax}_a\left(r(s,a)+\gamma \sum_{s^{'}}p(s^{'}\mid s,a)V^*(s^{'})\right)\tag{7.5} \end{equation}

Preuve.

On commence par trouver l'implication de: (7.5) vers optimalité. L'équation (7.5) équivaut à $L V^* = L_{\pi}V^*$ car $L$ correspond à $L_{\pi}$ quand $\pi = \operatorname{argmax}_{\pi} V^*\text{.}$ On suppose que $\pi$ satisfait (7.5) donc

\begin{equation*} V^* = L V^* = L_{\pi} V^* = V^* \end{equation*}

et par unicité de l'équation $V = L_{\pi} V$ on a $V_{\pi} =V^*\text{.}$ Donc si $\pi$ dans (1) alors $V_{\pi}=V^*\text{.}$ Maintenant on va démontrer l'implication: Optimalité vers (7.5). On a donc $V_{\pi}=V^*\text{.}$ Puisque $V_{\pi} = L_{\pi} V_{\pi}$ on a $V^* = L_{\pi} V^*\text{.}$ Puisqu'elle est optimale $L_{\pi}=L$ donc $V^* = L V^*\text{.}$

Pour finir on souhaite obtenir les mêmes caractérisation pour la Q-fonction. On remarque que par définition:

\begin{equation*} V^{*}(s)= \operatorname{max}_a Q^*(s,a), \quad \forall s\in S \end{equation*}

et pour la politique optimale gloutonne

\begin{equation*} \mu^{*}(s)= \operatorname{argmax}_a Q^*(s,a), \quad \forall s\in S \end{equation*}

on voit donc que l'on obtient immédiatement le corollaire suivant.

Corollaire 7.29.

On suppose que l'on maximise le critère d'horizon infini amorti. Pour $\gamma \lt 1\text{,}$ la Q-fonction $Q^{\pi^*}(.,.)$ de la politique optimale $\pi^*$ est l'unique solution de l'équation de Bellman:

\begin{equation*} Q^{\pi^*}(s,a) = L_Q Q^{\pi^*}(s,a), \quad \forall s\in S, \forall a \in A \end{equation*}

avec l'opérateur

\begin{equation*} L_Q Q(s,a) = \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} | s,a) \operatorname{max}_{a^{'}} Q(s^{'},a^{'})\right) \end{equation*}

Corollaire 7.30.

On peut réécrire la caractérisation de la Q fonction optimale sous la forme:

\begin{equation*} Q^{\pi}(s,a) = \mathbb{E}[r(s_t,a_t) +\gamma \operatorname{max}_{a^{'}} Q(s_{t+1},a^{'})\mid s_t=s, a_t=a] \end{equation*}

avec $s_{t+1}$ le nouvel état découlant de $(s,a)\text{.}$

L'ensemble de ses résultats nous donne des caratérisations récurrentes des politiques, politiques optimales et des Q fonctions. Ces caractérisations récurrentes vont permettent de calculer de façon plus efficac ces quantités.

Subsection 7.3.2 Programmation dynamique et algorithmes

Les algorithmes de programmation dynamique utilise la caratérisation des politiques et la formule de Bellman afin de proposer des algorithmes plus efficace qu'une recherche exhaustive.

Subsubsection 7.3.2.1 Méthode itérative sur les valeurs

La formule de Bellman peut se voir comme un problème de point fixe linéaire de taille $\mid S\mid$ le nombre d'états. La façon la plus naturelle de construire la politique optimale est de résoudre le problème de point fixe précédemment introduit à l'aide d'une méthode de Picard. La convergence est assurée par le théorème de point fixe. En appliquant cette simple méthologie on obtient un algorithme qui construit la fonction valeur de façon itératif avant de calculer la politique associée.

Algorithm 7.31. Algorithme de Picard sur les valeurs.

Initialiser $V_0$ la fonction valeur initiale
$\displaystyle n= 0$
Tant que $\mid V_{n+1}-V_n\mid \gt \varepsilon$
- $\forall s \in S$ on calcul
  - $\displaystyle V_{n+1}=\operatorname{max}_{a} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} | s,a) V_n(s^{'})\right)$
$\forall s \in S$ on calcul
- $\displaystyle \pi(s)= \operatorname{argmax}_{a} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} | s,a) V_n(s^{'})\right)$

Une fois la fonction valeur calculée, on voit bien que le politique est obtenue à partir de l'équation de Bellman sur la fonction valeur finale. A chaque itération le nombre d'opération est en $O(\mid S\mid^2 \mid A \mid)\text{.}$ La complexité est la même pour le calcul de la politique. Dans l'algorithme précédent on calcul une fonction valeur $V_n$ puis on construit une politique $\pi_n$ en utilisant une politique dite gloutonne donc utilisant $V_n\text{.}$ En faisant cela on espère que la fonction valeur $V_{\pi^n}$ de notre politique est bien proche de la fonction valeur optimale $V^*\text{.}$ En pratique il n'y a pas de raison que $V_{\pi^n}$ soit égal à $V_n$ on souhaite donc quantifier l'erreur entre $V_{\pi^n}$ et $V^*\text{.}$

Lemme 7.32.

La politique gloutonne $V_{\pi^n}$ obtenu à partir de $V_n$ satisfait

\begin{equation*} \parallel V^{*} - V^{\pi^n}\parallel_{\infty} \leq \frac{2\gamma}{1-\gamma}\parallel V^{*} - V_{n}\parallel_{\infty} \end{equation*}

Preuve.

On part donc de $\parallel V^{*} - V^{\pi^n}\parallel_{\infty}$ et on développe:

\begin{align*} \parallel V^{*} - V^{\pi^n}\parallel_{\infty} \amp = \parallel V^{*} -V_n + V_n- V^{\pi^n}\parallel_{\infty} \\ \amp \leq \parallel V^{*} - L_{\pi} V_n \parallel + \parallel L_{\pi} V_n- V^{\pi^n}\parallel_{\infty} \\ \amp \leq \parallel L V^{*} - L_{\pi} V_n \parallel + \parallel L_{\pi} V_n- L_{\pi} V^{\pi^n}\parallel_{\infty} \end{align*}

On a utilisé que $L V^{*} = V^*$ par définition de la fonction valeur optimale et $L_{\pi} V^{\pi^n} = V^{\pi^n}$ (caractérisation des politiques). Puisque $\pi_n$ est gloutonne $L_{\pi} V^n = L V_n\text{.}$ On a donc

\begin{align*} \parallel V^{*} - V^{\pi^n}\parallel_{\infty} \amp \leq \parallel L V^{*} - L V_n \parallel + \parallel L_{\pi} V_n- L_{\pi} V^{\pi^n}\parallel_{\infty} \\ \amp \leq \gamma\parallel V^{*} - V_n \parallel + \gamma\parallel V_n- V^{\pi^n}\parallel_{\infty} \\ \amp \leq \gamma\parallel V^{*} - V_n \parallel + \gamma\left(\parallel V_n- V^{*}\parallel_{\infty} +\parallel V^*- V^{\pi^n}\parallel_{\infty} \right) \end{align*}

on a donc

\begin{equation*} (1-\gamma)\parallel V^{*} - V^{\pi^n}\parallel_{\infty} \leq 2\gamma \parallel V_n- V^{*}\parallel_{\infty} \end{equation*}

ce qui permet de conclure.

Il existe des variantes de cet algorithme que nous ne détaillerons pas. La stratégie proposée ici consiste à itérer sur la fonction valeur uniquement. Nous allons proposer un autre type de méthodes.

Subsubsection 7.3.2.2 Méthode itérative sur la politique

Une seconde famille de méthode est formée des algorithmes ou on itére pas seulement sur la fonction valeur mais aussi, voir seulement, sur la politique en elle même. Pour cela l'idée est simplement de construire la fonction valeur puis directement après la politique a chaque itération. On parle d'un processus d'évaluation/amélioration:

\begin{equation*} \pi_0 \xrightarrow{e} V_0 \xrightarrow{a} \pi_1 \xrightarrow{e} v_1 \xrightarrow{a} \pi_2 .... \xrightarrow{a} \pi_* \xrightarrow{e} v_{*} \end{equation*}

Algorithm 7.33. Algorithme d'itération sur les politiques.

Initialiser $\mu_0$ la politique initiale
$\displaystyle n= 0$
Tant que $\mid \mu_{n+1}-\mu_n\mid \gt \varepsilon$
- $\forall s \in S$ on calcul
  - \begin{equation*} V_{n}= \left( r(s,\mu_n(s)) + \gamma \sum_{s^{'}}P(s^{'} | s,\mu_n(s)) V_n(s^{'})\right), \quad \forall s \in S \end{equation*}
- $\forall s \in S$ on calcul
  - \begin{equation*} \mu_{n+1}(s)= \operatorname{argmax}_{a} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} | s,a) V_n(s^{'})\right) \end{equation*}

La méthode nécessite d'inverser un système linéaire à chaque itération. On obtient donc une complexité en $O(\mid A\mid \mid S\mid^2 + \mid S\mid^3)$ (la 1ère partie vient de calcul de la politique, la seconde de l'inversion). Pour des espaces d'état important et $\mid S\mid \gt\gt \mid A \mid$ la complexité par itération est nettment moins bonne que précédemment. Ici on itère pas sur la fonction valeur. La convergence c'est donc pas assurée par le théorème du point fixe. Cependant on peut montre qu'a chaque évaluation la politique obtenu augmente sa fonction valeur ce qui assure que l'on se dirige vers un résultat satisfaisant.

Proposition 7.34.

Soit $\mu,\mu^+ \in D^{m}$ des politiques Markoviennes stationnaires déterministes. Si

\begin{equation*} \mu^{+}\in \operatorname{argmax}_{\delta \in D^m}(r_{\delta} +\gamma \mathbb{P}_{\delta} V^{\mu}) \end{equation*}

alors $\mu^+ \geq \mu\text{.}$ Si $\mu^+ \geq \mu$ alors $\mu = \mu^*$

Preuve.

On considère

\begin{equation*} (r_{\mu^+} +\gamma \mathbb{P}_{\mu^+} V^{\mu}) = \operatorname{max}_{\delta \in D^m}(r_{\delta} +\gamma \mathbb{P}_{\delta} V^{\mu}) \end{equation*}

donc

\begin{equation*} (r_{\mu^+} +\gamma \mathbb{P}_{\mu^+} V^{\mu})\geq (r_{\mu} +\gamma \mathbb{P}_{\mu} V^{\mu}) \end{equation*}

et puisqu'on a, la phase d'évaluation $r_{\mu} +\gamma \mathbb{P}_{\mu} V^{\mu} = V^{\mu}$ donc

\begin{equation*} (r_{\mu^+} +\gamma \mathbb{P}_{\mu^+} V^{\mu})\geq V^{\mu} \end{equation*}

Ensuite on fait intervenir la nouvelle politique:

\begin{equation*} r_{\mu^+} + \gamma \mathbb{P}_{\mu^+} V^{\mu^+} + \gamma \mathbb{P}_{\mu^+} (V^{\mu} - V^{\mu^+} )\geq V^{\mu} \end{equation*}

La phase d'évaluation donnera $r_{\mu^+} +\gamma \mathbb{P}_{\mu^+} V^{\mu^+} = V^{\mu^+}$ et donc

\begin{equation*} V^{\mu^+} - \gamma \mathbb{P}_{\mu^+} V^{\mu^+} \geq V^{\mu} - \gamma \mathbb{P}_{\mu^+} V^{\mu} \end{equation*}

ce qui équivaut à

\begin{equation*} (I_d - \gamma \mathbb{P}_{\mu^+}) V^{\mu^+} \geq ( I_d - \gamma \mathbb{P}_{\mu^+}) V^{\mu} \end{equation*}

La matrice étant inversible on obtient $V^{\mu^+} \gt V^{\mu}\text{.}$ L'égalité est possible si

\begin{equation*} \operatorname{max}_{\delta \in D^m}(r_{\delta} +\gamma \mathbb{P}_{\delta} V^{\mu}) = V^{\mu}) \end{equation*}

On retrouve l'équation de Bellman et donc par conséquent $V^{\mu}=V^*\text{.}$

La résolution du problème $V_n = L^{\pi_n} V_n$ nécessite d'inverser un système linéaire. On peut évidemment l'inverser exactement mais c'est très lourd. On peut le résoudre de façon itérative. Dans l'algorithme qu'on souhaite introduire l'idée est de faire un faible nombre d'itération de la résolution du système linéaire. En effet converger précisement n'est pas nécessaire (on retrouve le même phénomène avec les méthodes de Newton Krylov).

Algorithm 7.35. Algorithme modifié d'itération sur les politiques.

Initialiser $V_0$ avec $LV_0 \geq V_0\text{,}$ $flag = 0\text{,}$ $n = 0$
Tant que flag$=0$
- $\forall s \in S$ on calcul
  - $\displaystyle \pi_{n+1}(s)= \operatorname{argmax}_{a} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} \mid s,a) V_n(s^{'})\right)$
  - $\displaystyle V_n^0 = \operatorname{max}_{a} \left( r(s,a)+ \gamma \sum_{s^{'}}P(s^{'} \mid s,a) V_n(s^{'})\right)$
- $\displaystyle m=0$
- Si $\mid V_n^0-V_n\mid \leq \epsilon$ alors $flag=1\text{.}$
- Sinon: tant que $\mid V_n^{m+1}-V_n^{m}\mid \leq \delta$
  - $\forall s \in S$
    - \begin{equation*} V_{n}^{m+1}=\operatorname{max}_{a} \left( r(s,a) + \gamma \sum_{s^{'}}P(s^{'} \mid s,a) V_n^m(s^{'})\right) \end{equation*}
  - $\displaystyle m++$
- $\displaystyle V_n= V_n^m$
- $\displaystyle n=n+1$

Les méthodes présentées ici sont très coûteuses puisque on parcours l'ensemble des états et des actions à chaque itérations. De plus ces algorithmes ne sont utilisable que dans les cas des modèles parfaits. Dans la plupart des applications les algorithmes de Programmation dynamique ne sont pas réellement utilisable. Dans le chapitre suivant nous allons introduire des méthodes permettant de lever ces contraintes. Il s'agit du coeur de l'apprentissage par renforcement.