Markov Decision Process (MDP)

Un Markov Decision Process (MDP) est une extension du processus de Markov dans lequel un agent peut choisir une action à chaque étape.
Le passage d’un état à un autre ne dépend donc plus uniquement de l’état actuel, mais aussi de l’action effectuée.

L’idée global par rapport a MP :

À chaque état, l’agent choisit une action.
Cette action influence la probabilité des états futurs et la récompense qu’il reçoit.

Définition

Un MDP est défini par ces 5 variables :

$$(S,A,P,R,\gamma )$$

ou ($S$, $P$) est un MP

• $P(s,a,s^{\prime })=\mathbb{P}(S_{t+1}=s^{\prime }\mid S_t=s,A_t=a)$ : probabilité de transition
• $R(s,a)$ : récompense immédiate recue en faisant l’action $a$ dans l’état $s$
• $\gamma \in [0,1]$ : facteur d’actualisation (favorise les récompenses immédiates si $\gamma$ proche de 0, futures si proche de 1, en gros si on découvre ou si on joue avec nos connaissance)

Fonction de transition

La probabilité de transition dépend maintenant de l’action :

$$P(s,a,s^{\prime })=\mathbb{P}(S_{t+1}=s^{\prime }\mid S_t=s,A_t=a)$$

Pas comme le MP de base le MDP dépend de l'état et de la nouvelle variable l'action

Récompense

La récompense sert a savoir si une action étais bien ou pas:

$$R(s,a)=\mathbb{E}[\text{reˊcompense}\mid S_t=s,A_t=a]$$

Elle peut être positive (gain) ou négative (coût) ou neutre si elle n'a aucun importance.

Bien choisir ses récompenses fait change tout, si elles sont mal choisis cela peut mener a un mauvaise apprentissage (pour plus tard)

Politique

Une politique ou policy est une une fonction qui pour un état s nous dis quel action a effectuer :

$$\pi (s)=a$$

ou (si stochastique) :

$$\pi (a\mid s)=\mathbb{P}(A_t=a\mid S_t=s)$$

Valeur d’une politique

La valeur d’un état sous une politique $\pi$ est l’espérance des récompenses cumulées :

$$V^{\pi }(s)=\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t\cdot R(S_t,\pi (S_t))\mid S_0=s\right]$$

Cette formule mesure si dans longtemp nos action seront bien ou mal, (si le chemin est bon ou mauvais a long termes).

Objectif de l’agent

Trouver la meilleure politique ${\pi }^{\star }$ telle que :

$${\pi }^{\star }=\arg \underset{\pi }{\max }{V}^{\pi }(s)$$

Autrement dit : choisir les actions permettant d’obtenir le maximum de récompenses cumulées.

Exemple

Le joueur peut être dans deux états :

$$S=\{\text{Deˊbut},\text{Victoire}\}$$

À chaque tours, il a deux action possibles :

$$A=\{\text{Tenter},\text{Abandonner}\}$$

• Tenter : on lance une pièce.
  • Si c’est face -> on gagne -> on va dans l’état Victoire
  • Si c’est pile -> on reste dans l’état Début
• Abandonner : on tente rien, sans gagner -> on reste dans Début (et on gagne jamais)

Probabilités de transition

• Depuis Début :

  • $P(\text{Deˊbut},\text{Tenter},\text{Victoire})=0.5$
  • $P(\text{Deˊbut},\text{Tenter},\text{Deˊbut})=0.5$
  • $P(\text{Deˊbut},\text{Abandonner},\text{Deˊbut})=1$

• Depuis Victoire :

  • La partie est terminée (on reste en victoire ou on stop le jeu)

Récompenses

On gagne 1 point seulement quand on atteint Victoire :

$$R(\text{Deˊbut},\text{Tenter})=1\text{ si reˊussi, }0\text{ sinon}$$

Et :

$$R(\text{Deˊbut},\text{Abandonner})=0$$

La meilleure politique ${\pi }^{\star }$ est donc (je crois) :

$${\pi }^{\star }(\text{Deˊbut})=\text{Tenter}$$

car c’est la seul qui permet d’obtenir une récompense.

MDP + politique

Il est possible d'obtenir un Markov Reward Process (MRP) à partir d'un MDP, en lui ajoutant une politique. Le MRP correspondant possède les propriétés suivantes:

$$P^{\pi }(s^{\prime }|s)=\sum _{a\in A}\pi (a|s)P(s^{\prime }|s,a)$$

$$R^{\pi }(s)=\sum _{a\in A}\pi (a|s)R(s,a)$$

Exemple

Données

$$P(s^{\prime }|s,a_0)=\left(\begin{array}{cc}0.8& 0.2\\ 0.4& 0.6\end{array}\right)P(s^{\prime }|s,a_1)=\left(\begin{array}{cc}0.9& 0.1\\ 0.5& 0.5\end{array}\right)$$

$$R(s,a_0)=(5,10)R(s,a_1)=(2,8)$$

$$\pi (a|s_0)=(0.6,0.4)\pi (a|s_1)=(0.3,0.7)$$

Calcul de $P^{\pi }$

Pour $s_0$

$$P(0,0)=\pi (a_0|s_0)\times P(s_0^{\prime }|s_0,a_0)+\pi (a_1|s_0)\times P(s_0^{\prime }|s_0,a_1)$$

$$=(0.6\times 0.8)+(0.4\times 0.9)=0.84$$

$$P(0,1)=\pi (a_0|s_0)\times P(s_1^{\prime }|s_0,a_0)+\pi (a_1|s_0)\times P(s_1^{\prime }|s_0,a_1)$$

$$=(0.6\times 0.2)+(0.4\times 0.1)=0.16$$

Pour $s_1$

$$P(1,0)=\pi (a_0|s_1)\times P(s_0^{\prime }|s_1,a_0)+\pi (a_1|s_1)\times P(s_0^{\prime }|s_1,a_1)$$

$$=(0.3\times 0.4)+(0.7\times 0.5)=0.47$$

$$P(1,1)=\pi (a_0|s_1)\times P(s_1^{\prime }|s_1,a_0)+\pi (a_1|s_1)\times P(s_1^{\prime }|s_1,a_1)$$

$$=(0.3\times 0.6)+(0.7\times 0.5)=0.53$$

Résultat final

$$P^{\pi }=\left(\begin{array}{cc}0.84& 0.16\\ 0.47& 0.53\end{array}\right)$$

Calcul de $R^{\pi }$

$$R^{\pi }(s_0)=\pi (a_0|s_0)\times R(s_0,a_0)+\pi (a_1|s_0)\times R(s_0,a_1)$$

$$=(0.6\times 5)+(0.4\times 10)=7$$

$$R^{\pi }(s_1)=\pi (a_0|s_1)\times R(s_1,a_0)+\pi (a_1|s_1)\times R(s_1,a_1)$$

$$=(0.3\times 2)+(0.7\times 8)=6.2$$

Résultat final

$$R^{\pi }=\left(\begin{array}{c}7\\ 6.2\end{array}\right)$$

En code

Fonction Construire_MRP_Depuis_MDP(P, R, Politique):

    n_etats ← nombre d'états dans P
    n_actions ← nombre d'actions dans P

    P_MRP ← matrice n_etats × n_etats remplie de 0
    R_MRP ← vecteur de taille n_etats rempli de 0

    Pour chaque état s de 0 à n_etats−1 faire:
        Pour chaque action a de 0 à n_actions−1 faire:

            P_MRP[s] ← P_MRP[s] + Politique[s][a] × P[s][a]

            R_MRP[s] ← R_MRP[s] + Politique[s][a] × R[s][a]
        FIN Pour
    FIN Pour
    Retourner P_MRP, R_MRP

Conclusion

Un MDP est donc un modèle qui fait une prise de décision étape par étape.
en gros il ajoute au MP de base :

• Le choix d’actions
• La récompense
• La notion de politique optimale

Traces écrites :

MRP à partir d'un MDP