Méthodes de Monte-Carlo

Section 8.1 Méthodes de Monte-Carlo

Dans cette section ous allons introduire unre première famille de méthodes d'apprentissage par renforcement qui n'utilise ni le modèle ni un modèle approcher. Il s'agit de méthode estimtant la fonction valeur ou la Q-fonction à partir d'approche Monte-Carlo.

L'objectif est d'estimer la fonction valeur et utiliser cette fonction valeur pour construire une politique. On va pour cela utiliser 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*}

qui consiste itérativement a améliorer la politique puis la fonction valeur. Avant de décrire ces processus d'évaluation/amélioration on va d'abord voir comment construire la fonction valeur à l'aide du méthode de Monte-Carlo.

Subsection 8.1.1 Approches Monte-Carlo classiques

On rappelle la définition de la fonction valeur:

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

Puisqu'il s'agit d'une espérance, par la loi des grand nombre Théorème 1.8 il est assez naturel d'utiliser l'estimateur de la moyenne empirique (1.1) pour approcher la fonction valeur. C'est le coeur de la méthode de Monte-Carlo. Naturellement l'idée serait donc de générer des echantillons de retour Définition 7.8 $(G_1,...G_n)$ qui suivent la loi de probabilité issu du MDP que l'on considère puis d'estimer la fonction valeur par

\begin{equation*} V(s) \approx \frac{1}{n}\sum_{i=1}^n G_i = \frac{1}{n}\sum_{i=1}^n \sum_{k=0}^T r_{\pi}(s_k) \end{equation*}

avec $s_0^i=s$ l'état initial de la ième trajectoire. On voit ce que la peut se réécrire comme:

\begin{equation*} V(s) \approx \frac{1}{N_s}\sum_{i=1}^n \sum_k^T r_{\pi}(s_k) \end{equation*}

avec $N_s$ le nombre de fois qu'on rencontre l'état $s$ et des épisodes en temps ou l'on choisit l'état initiale aléatoirement. Les échantillons sont généré par une série de trajectoire issu de $\pi\text{.}$ Il n'est pas a priori obligé d'utiliser toutes les transitions générées dans une trajectoire pour calculer notre esperance empirique. On peut définit a ce stade 2 méthodes de MC pour estimer notre espérance (fonction valeur):

Monte-Carlo à chaque visite: on utilise toute les transitions d'une trajectoire même si un état a déjà été visité,
Monte-Carlo première visite: on ne considère que la 1ère visite d'un état $s$ à chaque trajectoire.

Une fois votre méthode de Monte-Carlo choisie pour estimer la fonction valeur, on incorpore cela dans un processus d'évaluation/amélioration afin d'obtenir une méthode cosntructive pour la politique optimale. On préfere utiliser la fonction $Q$ plutôt que la fonction valeur. Elle est notamment plus naturelle pour calculer la politique. Le principe reste le même. L'approximation de Monte-Carlo est donnée par

\begin{equation*} Q(s,a) \approx \frac{1}{N_s}\sum_{i=1}^n \sum_k^T r_{\pi}(s_k) \end{equation*}

Ce qui change c'est juste que la 1ère action d'une trajectoire est choisie aléatoirement et non avec la politique. Si on choisit pas la 1ère action de façon aléatoire on risque de jamais passer par un certains nombre d'états et d'actions ce qui peut être problematique pour la convergence. On parle de méthode avec début exploratoire. A partir de tout cela on obtient deux algorithmes.

Algorithm 8.1. Algorithme Monte-Carlo à chaque visite.

Initialisation de $Q_0(.,.)$ et $\pi_0(.)$ arbitraire
$\displaystyle \forall k \leq K$
- initialiser $G(.,.)=0$ et $N(.,.)=0$
- choisir aléatoirement un état $s_0$ et une action $a_0$
- calculer une trajectoire $(s_0,a_0,r_1,.....s_{T-1},a_{T-1},r_{T})$ selon la politique $\pi_k$
- $\forall (s_t,a_t)$ de la trajectoire courante
  - $\displaystyle G_{loc}= \sum_{i=0}^T\gamma^i r_{r+t+1}$
  - $G(s_t,a_t)+=Gloc$ et $N(s_t,a_t)+=1$
  - $\displaystyle Q_k(s_t,a_t)= \frac{1}{N(s_t,a_t)}G(s_t,a_t)$
  - $\displaystyle \pi_{k+1}(s_t)=\operatorname{argmax}_{a}Q_k(s_t,a)$
On renvoit $\pi_K$

Algorithm 8.2. Algorithme Monte-Carlo à la 1ière visite.

Initialisation de $Q_0(.,.)$ et $\pi_0(.)$ arbitraire
$\displaystyle \forall k \leq K$
- initialiser $G(.,.)=0$ et $N(.,.)=0$
- choisir aléatoirement un état $s_0$ et une action $a_0$
- calculer une trajectoire $(s_0,a_0,r_1,.....s_{T-1},a_{T-1},r_{T})$ selon la politique $\pi_k$
- $\forall (s_t,a_t)$ de la trajectoire courante
  - Si $(s_t,a_t)$ apparait pour la 1ère fois dans la trajectoire
    - $\displaystyle G_{loc}= \sum_{i=0}^T\gamma^i r_{r+t+1}$
    - $G(s_t,a_t)+=Gloc$ et $N(s_t,a_t)+=1$
    - $\displaystyle Q_k(s_t,a_t)= \frac{1}{N(s_t,a_t)}G(s_t,a_t)$
    - $\displaystyle \pi_{k+1}(s_t)=\operatorname{argmax}_{a}Q_k(s_t,a)$
On renvoit $\pi_K$

Pour ces deux méthodes de Monte-Carlo on utilise une politique Gloutonne pour générer les trajectoires. Afin de s'assurer que l'algorithme a des chances de mancher on souhaite vérifier que la politique est bien améliorée a chaque itération comme on le souhaite. Pour cela on veut juste vérifier que la fonction valeur va augmenter.

Proposition 8.3.

A chaque étape de l'algorithme Algorithm 8.1 ou Algorithm 8.2 la fonction valeur augmente.

Preuve.

Pour cela un rapide calcul suffit:

\begin{equation*} V_{\pi_{k+1}}(s) = Q_{\pi_{k}}(s,\pi_{k+1}(s))= Q_{\pi_l}(s,\operatorname{argmax}_{a}Q_{\pi_a}(s,a)) \end{equation*}

\begin{equation*} V_{\pi_{k+1}}(s) = \operatorname{max}_{a}Q_{\pi_k}(s,a). \end{equation*}

Par définition du maximum

\begin{equation*} V_{\pi_{k+1}}(s) \geq Q_{\pi_k}(s,\pi_k(s)) = V_{\pi_k}(s) \end{equation*}

ce qui montre bien l'amélioration de la politique a chaque itération.

Remarque 8.4.

Les méthodes de Monte-Carlo introduite juste au dessus utilise des estimations pour chaque étapes inxépendantes les une des autres. Contrairement à la programmation dynamique qui utilisait les fonction valeurs ou fonctions $Q$ associées aux autres états.

La conséquence naturelle de la remarque précédente est que le calcul de la fonction valeur pour un état ne dépend pas du nombre d'état contrairement à avant contraintement à la programmation dynamique. Si vous êtes intéréssé par la fonction valeur seulement pour un sous-ensemble d'état, il suffit de construire des épisodes dans ce sous-ensemble. Les méthodes de MC seront donc nettement moins couteuse que la programmation dynamique dans ce cadre. Un deuxième avantage évident c'est qu'il s'agit d'une méthode sans modèle. En effet on a juste besoin de l'environnement pour obtenir un transition entre $s_t$ et $s_{t+1}$ mais on a pas besoin de la connaissance des probabilité de transition. Les deux méthodes introduites utilisent donc un début exploratoire. C'est une approche qui n'est pas très populaire pour assurer l'exploration. En effet il faut s'assurer que l'algorithme balaye tous les couples état-action possibles. Dans le cadre d'un environnement ou le début est toujours le même (jeux d'echec ou de GO) cette approche ne peut pas marcher. On pourrait imaginer un environement qui génére aléatoirement des bouts de parties qui serait des configurations initiales. Cependant on préfère que ce soit l'agorithme qui génère cette exploration plus que l'environnement sur lequel on a pas forcement la main. Pour cela on propose d'utiliser une politique stochastique pour générer les trajectoires afin d'assurer suffisement d'exploration. Cela donne par exemple l'algorihme de Monte-Carlo soft (chaque visite ou première visite).

Algorithm 8.5. Algorithme Monte-Carlo soft à chaque visite.

Initialisation de $Q_0(.,.)$ et $\pi_0(.)$ arbitraire
$\displaystyle \forall k \leq K$
- initialiser $G(.,.)=0$ et $N(.,.)=0$
- choisir aléatoirement un état $s_0$ et une action $a_0$
- calculer une trajectoire $(s_0,a_0,r_1,.....s_{T-1},a_{T-1},r_{T})$ selon la politique $\pi_k$
- $\forall (s_t,a_t)$ de la trajectoire courante
  - $\displaystyle G_{loc}= \sum_{i=0}^T\gamma^i r_{r+t+1}$
  - $G(s_t,a_t)+=Gloc$ et $N(s_t,a_t)+=1$
  - $\displaystyle Q_k(s_t,a_t)= \frac{1}{N(s_t,a_t)}G(s_t,a_t)$
  - $\displaystyle a^*=\operatorname{argmax}_{a}Q_k(s_t,a)$
  - la politique est donnée par
    
    \begin{equation*} \pi( a\mid s_t) =\left\{\begin{array}{l} 1-\epsilon + \frac{\epsilon}{\mid A(s_t) \mid} \mbox{ si } a=a^* \\ \frac{\epsilon}{\mid A(s_t) \mid } \mbox{ si } a \neq a^* \end{array}\right. \end{equation*}
    
    avec $A(s_t)$ le nombre d'action possible en partant de $s_t\text{.}$
On renvoit $\pi_K$

Remarque 8.6.

La politique aléatoire permet de faire de l'exploration. Afin s'assurer une convergence plus rapide en général on utilise une stratégie adaptative en $\epsilon$ qui commence proche de 1 et qui diminue régulièrement}.

Proposition 8.7.

A chaque étape de l'algorithme Algorithm 8.5 la fonction valeur augmente.

Preuve.

\begin{equation*} V_{\pi_{k+1}}(s) = Q_{\pi_{k}}(s,\pi_{k+1}(s))= \sum_{a}\pi_{k+1}(a \mid s) Q_{\pi_{k}}(s,a). \end{equation*}

Puisque on utilise une politique stochastique avec $\sum_{a}\pi_{k+1}(a \mid s)=1\text{.}$

\begin{equation*} V_{\pi_{l+1}}(s) = \frac{\epsilon}{\mid A(s)\mid}\sum_{a}Q_{\pi_{k}}(s,a) + (1-\epsilon)\operatorname{max}_{a}Q_{\pi_{k}}(s,a). \end{equation*}

On utilise l'inégalité

\begin{equation*} \operatorname{max}_{a}Q_{\pi_{k}}(s,a) \geq \sum_{a} \frac{\pi_k(a\mid s)-\frac{\epsilon}{\mid A(s) \mid} }{1-\epsilon}Q_{\pi_{lk}}(s,a). \end{equation*}

Pour obtenir cette inégalité on utilise que $\sum_{a} \frac{\pi_k(a\mid s)-\frac{\epsilon}{\mid A(s) \mid} }{1-\epsilon}=1$ et que tout les coefficients sont positifs. On a donc une combinaison convexe. Par définition, la combinaison convexe est égale ou plus petite que le maximum de la fonction $Q\text{.}$ En utilisant l'inégalité précédente on obtient:

\begin{equation*} V_{\pi_{k+1}}(s) \geq \frac{\epsilon}{\mid A(s)\mid}\sum_{a}Q_{\pi_{l}}(s,a) - \frac{\epsilon}{\mid A(s)\mid}\sum_{a}Q_{\pi_{k}}(s,a)+ \sum_{a}\pi_{k}(a \mid s) Q_{\pi_{k}}(s,a) \end{equation*}

\begin{equation*} V_{\pi_{k+1}}(s) \geq V_{\pi_{k}}(s) \end{equation*}

ce qui assure l'amélioration à chaque itération.

Subsection 8.1.2 Méthodes "on/off policy"

Il est assez fréquent dans la communauté d'apprentissage par renforcement de séparé les méthodes notamment stochastique en deux sous familles.

Définition 8.8.

On appelle la politique d'exploration la politique utilisée pour générer les trajectoires et les transitions. On appelle la politique cible celle dont on construit la fonction valeur ou la fonction Q. On dit qu'un algorithme est "on policy" si les deux politiques sont les mêmes. On parle d'algorithme "off policy" si les deux politiques sont différentes.

Dans le cas "on policy", la dépendance que cela induit entre l’exploration et l’apprentissage complique enormement les preuves de convergence en comparaison au cas "off policy". Les méthodes "on-policy" sont, en général, plus simple à mettre en oeuvre et converge plus vite. Par contre les méthodes "off-policy" sont plus génerales et robuste mais nécessite d'introduire des outils supplémentaires. Les méthodes de Monte-Carlo précédentes sont "on policy" car on évalue la fonction Q (donc une espérance) par une méthode de Monte-Carlo ou les trajectoires sont générée par une politique donc par définition la fonction Q est celle de cette même politique. Pour cela on commence par définir deux politiques:

$\pi(.\mid .)$ est la politique cible,

$b(.\mid .)$ est la politique d'exploration,

Pour pouvoir correctement évaluer $\pi$ a l'aide de trajectoires générées par $b$ il faut que les actions données par $\pi$ puisse être aussi systèmatiquement données par $b\text{.}$ Cela revient à dire que si $\pi (a\mid s) \gt 0 \Rightarrow b (a\mid s) \gt 0\text{.}$ On appelle cela la condition de converture. Par contre l'inverse est pas vrai. On peut par exemple avec une politique $\pi$ déterministe (politique gloutonne par exemple) et une politique $b$ stochastique.

Afin de construire notre algorithme "off policy" on va utiliser l'échantillonnage préférentiel. Cette méthode de réduction de variance est utilisée en pratique dans la plupart des méthodes "off policy" puisqu'elle permet de générer l'céhantillon avec une autre loi de probabilité (politique d'exploration ici) que la loi dont on veut calculer l'espérance (politique cible). L'idée est de pondérer les retours en fonction de la probabilité que leur trajectoires soit données par les politiques cible et d'exploration. On parle d'échantillonnage préférentiel par ratio. Pour cela on va définir le ratio entre les probabilités d'une trajectoire qui génère un retour $G_t\text{:}$

\begin{equation*} \rho_{t:T-1} = \frac{\mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, \pi)}{\mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, b)} \end{equation*}

On remarque rapidement que

\begin{equation*} \mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, \pi) = \pi(a_t\mid s_t)P(s_{t+1} \mid s_t, a_t)\pi(a_{t+1}\mid s_{t+1}) ... P(s_T \mid s_{T-1}, a_{T-1}) \end{equation*}

\begin{equation*} \mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, \pi) = \displaystyle\Pi_{k=t}^{T-1} \pi(a_k \mid s_k)P(s_{k+1} \mid s_k, a_k) \end{equation*}

ce qui donne

\begin{equation*} \displaystyle \rho_{t:T-1} = \frac{\Pi_{k=t}^{T-1} \pi(a_k \mid s_k)P(s_{k+1} \mid s_k, a_k) }{\Pi_{k=t}^{T-1} b(a_k \mid s_k)P(s_{k+1} \mid s_k, a_k)} = \displaystyle \Pi_{k=t}^{T-1}\frac{ \pi(a_k \mid s_k) }{b(a_k \mid s_k)} \end{equation*}

Lorsqu'on génére les trajectoires avec la politique $b(.,\mid .)$ et qu'on estime $\mathbb{E}[G_t \mid s_t=s]$ en pratique on calcul $\mathbb{E}[G_t \mid s_t=s; b] = V_b(s)\text{.}$ Par contre si on estime, avec les trajectoires générés par $b\text{,}$ l'espérance:

\begin{equation*} \mathbb{E}[\rho_{t:T-1} G_t \mid s_t=s] \end{equation*}

On est bien entrain de calculer $V_{\pi}(s)$ (il s'agit d'échantillonnage préférentielle). Lorsqu'on applique directement la méthode de Monte-carlo à l'espérance précédente on obtient

\begin{equation*} V_n =\frac{\sum_{t \in \mathcal{\tau}(s)} \rho_{t:T-1} G_t}{\mid \mathcal{\tau}(s)\mid } \end{equation*}

avec $\mathcal{\tau}(s)$ l'ensemble des temps ou on passe par l'état $s\text{.}$ On parle ici de d'échantillonnage préférentiel ordinaire. Il existe une variante appelée échantillonnage préférentiel à poids ou on utilise comme approximation de Monte-Carlo la quantité suivante

\begin{equation*} V_n =\frac{\sum_t \in \mathcal{\tau}(s) \rho_{t:T-1} G_t}{\sum_t \in \mathcal{\tau}(s) \rho_{t:T-1} } \end{equation*}

Pour comparer un peu les deux approches on va se place dans le "1ère visite" et le cas ou on regarde un seul retour (une seule trjactoire). Il y a deux cas:

échantillonnage préférentiel ordinaire $V(s)= G_t$
échantillonnage préférentiel à poids: $V(s) = \rho_{t:T-1}G_t$

Imaginons qu'une trajectoire soit très représentée dans $\pi(.)$ alors

\begin{equation*} \mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, \pi) \approx 1 \end{equation*}

et peu répresentée dans $b$ alors

\begin{equation*} \mathbb{P}(a_t,s_{t+1},a_{t+1},...,s_{T} \mid s_t, b) \approx 0.1 \end{equation*}

L'approche ordinaire va générer l'estimation suivante: $V(s) = 10 G_t$ alors qu'on devrait être proche de $G_t\text{.}$ La méthode ordinaire peut donc générer des valeurs abérantes. On peut résumer en disant (dans le cas 1ère visite) que la méthode ordinaire est un estimateur sans biais mais la variance peut être non bornée si le ratio entre les deux politiques ne l'est pas. La méthode a poids est biaisée mais la variance reste bornée. En pratique la variance pour échantillonnage préférentiel à poids est très nettement inférieur et donc on utilise souvent cette méthode. Dans le cas "chaque visite" les deux méthodes sont biaisées. L'approche "chaque visite" est souvent préférée car elle est plus simple a implémenter. On va donc détailler par la suite le cas "chaque visite" avec échantillonnage préférentiel à poids. Pour finir on va choisir quelle politique utiliser pour $\pi$ et pour $b\text{.}$ Pour $b$ on se propose d'utiliser une politique stochastisque "softmax" et comme politique $\pi$ une politique gloutonne. Le but est donc de construire une politique déterministe mais en explorant à l'aide d'une politique stochastique. Puisque la politique $\pi$ est gloutonne:

\begin{equation*} \pi (a \mid s)=1 \rightarrow \displaystyle \rho_{t:T-1} = \Pi_{k=t}^{T-1}\frac{ 1}{b(a_k \mid s_k)} \end{equation*}

On considère $G_1,....G_T)$ associé au même état de départ. Pour l'algorithme plutot que d'utiliser:

\begin{equation*} V_n =\frac{\sum_k W_k G_k}{\sum_k W_k } \end{equation*}

avec $W_k =\rho_{t_k:T(t-k)-1}$ on va utiliser l'algorithme itératif (rappel sur Monte Carlo) pour calculer l'espérance. Ce qui donne

\begin{equation*} V_{n+1} = V_n + \frac{W_n}{C_n}(G_n - V_n) \end{equation*}

avec $C_n$ la somme cumulée des poids.

Algorithm 8.9. Algorithme Monte-Carlo soft "off-policy" à chaque visite.

Initialisation de $Q_0(.,.)$ arbitraire et $\pi_0(.)= \operatorname{argmax}_a Q_0(.,a)$ $
$\displaystyle \forall k \leq K$
- initialiser $b(.\mid .)$ une politique soft
- choisir aléatoirement un état $s_0$
- calculer une trajectoire $(s_0,a_0,r_1,.....s_{T-1},a_{T-1},r_{T})$ selon la politique $b$
- mettre $G(.,.)=0, W=1$
- $\displaystyle \forall t \in \left\{ T-1,.....,1,0\right\}$
  - $\displaystyle G= \gamma G + R_{t+1}$
  - $\displaystyle C(s_t,a_t)=C(s_t,a_t)+W$
  - $\displaystyle Q_k(s_t,a_t)= Q_k(s_t,a_t)+ \frac{W}{C(s_t,a_t)}(G - Q_k(s_t,a_t))$
  - $\displaystyle \pi_{k+1}(s_t)=\operatorname{argmax}_{a}Q_k(s_t,a)$
  - Si $a_t \neq \pi_{k+1}(s_t)$ on sort de la boucle.
  - $\displaystyle W = \frac{W}{b(a_t\mid s_t)}$
On renvoit $\pi$

La condition à la fin permet d'appendre que lorsque l'action améliore la politique gloutonne. Cela peut poser un problème dans les cas ou il y a pas mal d'action qui n'améliore pas la politique gloutonne (cas ou la condition du "if" est rapidement vrai) car l'apprentissage se fait surtout à partir des fin d'épisode ce qui peut ralentir considérable l'apprentissage pour les états qui appararaissent en début d'apprentissage. Il existe encore des variantes plus raffiner pour traiter ce genre de problème mais on propose de d'arreter ici.