Policy Improvement

Définition de l’environnement

Valeurs des variables sur l’exemple :

states = ["North", "South", "East", "West"]
actions = ["clock", "anti-clock", "stay"]
gamma = 0.9  
horizon = 10  # noté H dans les diapositives

États et actions possibles

On considère un cercle découpé en 4 directions principales :
Nord, Est, Sud, Ouest, avec 3 actions possibles :

• clock (sens horaire)
• anti-clock (sens antihoraire)
• stay (rester sur place)

Chaque action entraîne une transition déterministe vers un nouvel état :

$$P(s,a)\to s^{\prime }$$

Probabilités de transition

$$P=\{\begin{array}{l}P(North,clock)=East\\ P(North,anti\text{-}clock)=West\\ P(North,stay)=North\\ P(East,clock)=South\\ P(East,anti\text{-}clock)=North\\ P(East,stay)=East\\ P(South,clock)=West\\ P(South,anti\text{-}clock)=East\\ P(South,stay)=South\\ P(West,clock)=North\\ P(West,anti\text{-}clock)=South\\ P(West,stay)=West\end{array}$$

Récompenses associées ( R(s,a) )

$$R=\{\begin{array}{l}R(North,clock)=2,R(North,anti\text{-}clock)=2,R(North,stay)=-2\\ R(East,clock)=3,R(East,anti\text{-}clock)=10,R(East,stay)=1\\ R(South,clock)=1,R(South,anti\text{-}clock)=3,R(South,stay)=1\\ R(West,clock)=10,R(West,anti\text{-}clock)=-1,R(West,stay)=1\end{array}$$

Étape 1 — Politique initiale

On commence avec une politique arbitraire (non optimale) :

$${\pi }_0=\{\begin{array}{l}\pi (North)=stay\\ \pi (South)=clock\\ \pi (East)=clock\\ \pi (West)=anti\text{-}clock\end{array}$$

Étape 2 — Évaluation de la politique

On estime la valeur des états sous la politique courante :

$$V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,\pi (s))V^{\pi }(s^{\prime })$$

L’algorithme procède par itérations successives (approche approchée sur un horizon (H = 10)) :

V = {s: 0 for s in states}
for _ in range(horizon):
    new_V = V.copy()
    for s in states:
        a = policy[s]
        new_V[s] = R[(s,a)] + gamma * sum(P[(s,a)][s2] * V[s2] for s2 in P[(s,a)])
    V = new_V

À la fin de cette boucle, on obtient une estimation stable de $$ (V^{\pi}) $$.

Étape 3 — Amélioration de la politique

Pour chaque état (s), on calcule la valeur d’action (Q(s,a)) :

$$Q(s,a)=R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })$$

et on met à jour la politique en choisissant l’action optimale :

$${\pi }^{\prime }(s)=\arg \underset{a}{\max }Q(s,a)$$

Code correspondant :

for s in states:
    Q_values = {}
    for a in actions:
        Q_values[a] = R[(s,a)] + gamma * sum(P[(s,a)][s2] * V[s2] for s2 in P[(s,a)])
    policy[s] = max(Q_values, key=Q_values.get)

Étape 4 — Vérification de la stabilité

Si la politique ne change plus $({\pi }^{\prime }=\pi )$, on a atteint une politique optimale :

$${\pi }^{\ast }={\pi }^{\prime }$$

Sinon, on retourne à l’étape d’évaluation et on répète jusqu’à convergence.

Résultat final

Après convergence :

$${\pi }^{\ast }=\{\begin{array}{l}{\pi }^{\ast }(North)=clock\\ {\pi }^{\ast }(South)=clock\\ {\pi }^{\ast }(East)=anti\text{-}clock\\ {\pi }^{\ast }(West)=clock\end{array}$$

et les valeurs d’état associées $(V^{\ast })$ maximisent les retours attendus sous cette politique optimale.

Formule générale de la Policy Iteration

Évaluation :

$$V^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,\pi (s))V^{\pi }(s^{\prime })$$

Amélioration :

$${\pi }^{\prime }(s)=\arg \underset{a}{\max }\left[R(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)V^{\pi }(s^{\prime })\right]$$

On alterne ces deux étapes jusqu’à convergence.