Policy Evaluation

Qu’est-ce que la policy evaluation ?

La policy evaluation consiste à calculer la valeur d’une politique donnée.

Informellement : si l’agent suit cette politique, quelle récompense moyenne peut-il espérer ?

On cherche donc à calculer la fonction de valeur :

• $\pi$ : la policy/politique
• $V\pi (s)$ : la valeur d’un état $s$ en suivant la politique $\pi$.
• Optionnellement : $Q\pi (s,a)$ : la valeur d’état-action.

Pourquoi évaluer une politique ?

Avant de vouloir améliorer une politique (policy improvement), il faut savoir si elle est bonne.

La policy evaluation permet :

• d’estimer combien la politique rapporte en moyenne ;
• d’identifier les états bons/mauvais ;

Équations de Bellman

La valeur d’un état sous la politique $\pi$ est définie par :

$V_{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime }}P(s^{\prime }|s,a)[R(s,a,s^{\prime })+\gamma V_{\pi }(s^{\prime })]$

Ce que ça veut dire :

• On suit ce que la politique dit de faire ($\pi$).
• On regarde les transitions possibles.
• On ajoute la récompense immédiate + la valeur future.

Méthodes pour faire la policy evaluation

1 Approche exacte : Iterative Policy Evaluation

On applique l’équation de Bellman en boucle jusqu’à convergence.

Pseudo-code :

initialiser V(s) = 0 pour tout s

répéter
    pour chaque état s :
        V_new(s) = somme_a π(a|s) * somme_s' P(s'|s,a) * [R(s,a,s') + γ V(s')]
    remplacer V par V_new
jusqu’à convergence

2 Monte-Carlo Policy Evaluation

On fait plusieurs épisodes :

• on suit la politique $\pi$,
• on regarde le retour observé,
• on moyenne les retours pour estimer V$\pi$.

Adapté lorsque le modèle (transition, récompenses) n’est pas connu.

Résumé simple

Exemple

1) Rappel (formule utilisée — horizon fini)

On utilise la version horizon fini (avec discount) : si $V^{(h)}(s)$ est la valeur avec h étapes restantes et $V^{(0)}(s)=0$,

$$V^{(h)}(s)=\sum _a\pi (a|s)(R(s,a)+\gamma V^{(h-1)}(s^{\prime }))$$

où $s^{\prime }$ est l’état déterministe résultant de $(s,a)$.

Paramètres utilisés :

• états = {North, East, South, West}
• actions = {clock, anti-clock, stay}
• $\gamma$ = 0.9
• horizon (H = 10)
• politique $\pi (a|s)=1/3$ (uniforme)

2) Exemple de calcul manuel (pour h=1, état North)

Pour vérifier la formule :

• transitions depuis North :

  • clock → East, (R=2)
  • anti-clock → West, (R=2)
  • stay → North, (R=-2)

Avec $V^{(0)}(\cdot )=0$ :

$$V^{(1)}(North)=\frac{1}{3}(2+0.9\cdot 0)+\frac{1}{3}(2+0.9\cdot 0)+\frac{1}{3}(-2+0.9\cdot 0)=\frac{2+2-2}{3}=\frac{2}{3}\approx 0.6667$$

(Ça colle avec les calculs programmés ci-dessous.)

3) Résultats (valeurs $V^{(h)}(s)$ pour h = 0..10)

La colonne h donne le nombre d’étapes restantes. La dernière ligne est donc $V^{(10)}(s)$ (valeur attendue en suivant $\pi$ uniforme pendant 10 étapes).

4) Interprétation rapide

• East a la valeur la plus élevée (≈ 18.868 à l’horizon 10) : c’est logique car depuis East il y a une action avec grosse récompense (anti-clock = 10) et en moyenne la politique explore cette action 1/3 du temps.
• North a une valeur plus faible au départ (récompense de stay négative), mais en plusieurs étapes la valeur augmente car les transitions mènent à états plus rémunérateurs.
• Les valeurs augmentent avec h (plus d’étapes = plus de récompenses accumulées, malgré le discount).