Markov Reward Process (MRP)

Un Markov Reward Process (MRP) est un processus de Markov avec une fonction qui indique combien on gagne (ou perd) à chaque transition.

Définition

Un MRP est défini par le quadruplet :

$(S, P, R, γ)$

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

$R (s, s^{'})$ : récompense associée à l’état ou à la transition
$γ \in [0, 1]$ : facteur d’actualisation (plus $γ$ est proche de 1, plus les récompenses futures comptent)

Autrement dit :

Un MRP = Processus de Markov + Récompenses + Facteur d’actualisation.

Récompense

Etant donné un MRP : $(S, P, R, γ)$

$R_{t}$ = Valeur aléatoire = R( $S_{t}$ - 1, $S_{t} + 1$ ), gain récolté en faisant la transition $S_{t}$ -> $S_{t + 1}$
$S_{t}$ par $G_{t}$ = $R_{t}$ + 1 + $γ$ + ...

PAS FINIT

Valeur d’un état

La valeur d’un état mesure la récompense totale attendue à long terme, en partant de cet état :

$V (s) = E (G_{t} ∣ S_{t} = s)$ $R (s) = E (R_{t + 1} ∣ S_{t} = s)$ $V (s) = E [t = 0 \sum \infty γ^{t} \cdot R (S_{t}) ∣ S_{0} = s]$

$R (s)$ = récompense immédiate obtenue en étant dans l’état
$V (s)$ = qualité long terme de l’état

C’est ce qui indique si un état est bon ou mauvais à long terme. Ainsi, un état avec une grande valeur $V (s)$ est considéré comme bon, car il mène en moyenne à beaucoup de récompenses futures.

Équation de Bellman

La fonction V vérifie l'équation de Bellman :

$V (s) = R (s) + γ s^{'} \sum P (s, s^{'}) V (s^{'})$ Cette équation exprime que :

on reçoit immédiatement $R (s)$
puis on se déplace vers un état futur $s^{'}$
avec probabilité $p (s, s^{'})$
tout en tenant compte de la valeur de cet état futur

Exemple

On a deux états :

$S = {Normal, Bonus}$

Transitions :

Depuis Normal :
- $P (Normal \to Bonus) = 0.3$
- $P (Normal \to Normal) = 0.7$
Depuis Bonus :
- $P (Bonus \to Normal) = 1$

Récompenses :

$R (Normal) = 0$
$R (Bonus) = + 5$

Facteur d’actualisation :

$γ = 0.9$

Interprétation

L’état Bonus rapporte +5, mais ne dure pas.
Depuis Normal, on peut atteindre Bonus, mais ce n’est pas garanti.
La valeur $V (s)$ permet de savoir si ça "vaut le coup" d’être dans un état.

Calcul de la valeur d'un MRP

Valeurs des variables sur les exemples :

P = np.array([[0.7, 0.3],
              [0.4, 0.6]])
R = np.array([5, 10])
gamma = 0.9

FORME VECTORIELLE

Fonction Bellman_Vector_Forme(P, R, gamma):

    n ← nombre de lignes de P

    I ← matrice identité de taille n × n

    A ← I - gamma × P

    A_inv ← inverse de A

    V ← A_inv × R

    Retourner V

Données :

$P = (0.7 0.4 0.3 0.6) R = (510) γ = 0.9$

Méthode vectorielle :

$V = (I - γ P)^{- 1} R$

I une matrice d'identité donc :

$I = (1001)$

donc :

$[I - γ P]^{- 1} = [(1001) - 0.9 (0.7 0.4 0.3 0.6)]^{- 1}$

$= [(1 - 0.63 - 0.36 - 0.27 1 - 0.54)]^{- 1} = (0.37 - 0.36 - 0.27 0.46)^{- 1}$

Il faut maintenant calculer l’inverse de cette matrice, pour résoudre cela on applique cette formule :

$A^{- 1} = \frac{1}{det ( A )} (d - c - b a)$

$det (I - γ P) = 0.37 \times 0.46 - (- 0.27) \times (- 0.36)$

$= 0.1702 - 0.0972 = 0.073$

$(I - γ P)^{- 1} = \frac{1}{0.073} (0.46 0.36 0.27 0.37) = (6.3013 4.9315 3.6986 5.0685)$

$V = (6.3013 4.9315 3.6986 5.0685) \cdot R = (6.3013 4.9315 3.6986 5.0685) \cdot (510)$

$= (6.3013 \times 5 + 3.6986 \times 10 4.9315 \times 5 + 5.0685 \times 10) = (68.4925 75.3425)$

$V = (68.4925 75.3425)$

FORME RECURSIVE

Fonction Bellman_Forme_Récursive(P, R, gamma):

    V ← vecteur nul de même taille que R
    seuil ← 0.0000001
    max_iterations ← 10000

    Pour k allant de 1 à max_iterations faire:

        V_nouveau ← R + gamma × P × V

        SI max(|V_nouveau − V|) < seuil alors:
            Sortir de la boucle
        FIN SI

        V ← V_nouveau
    FIN Pour

    Retourner V

Pour ( R, P ) et ( $γ$ ), on prendra les mêmes données que la forme vectorielle.

Méthode récursive :

$V (s) = R (s) + γ \sum P (s, s^{'}) V (s^{'})$

On commence la 1ʳᵉ itération avec un vecteur nul : $V_{0} (s) = (0, 0)$

On répète ces itérations jusqu’à atteindre un point de convergence lorsque la différence entre deux itérations devient minime.

Dans notre exemple, la convergence se fera à l’itération 172.

Itération 171 :

$V_{171} = (68.49374392 75.34264868)$

Itération 172 :

$V_{172} = (68.49374972 75.34265479)$

Donc :

$V (s_{1}) = 68.49374972 et V (s_{2}) = 75.34265479$

Traces écrites :

bellman vector

bellman recursive

Conclusion

Un Markov Reward Process est :

une chaîne de Markov
avec une récompense
et une notion de gain à long terme via la valeur $V (s)$

C’est une étape essentielle entre :

Chaînes de Markov (pas de choix)
MDP (prise de décision et recherche de meilleure politique)

SAE