Évaluez puis améliorez une politique

Vous savez maintenant ce que vaut une politique : sa fonction de valeur, solution de l’équation de Bellman. Deux questions pratiques restent ouvertes. Comment calculer cette valeur quand le système est trop grand pour être inversé ? Et, une fois la valeur connue, comment s’en servir pour faire mieux ?

Ce chapitre répond aux deux, avec les deux premières briques de la programmation dynamique : l’évaluation de politique (policy evaluation) et l’amélioration de politique (policy improvement). En les alternant, on obtient un premier algorithme qui trouve la politique optimale : l’itération sur les politiques (policy iteration). C’est exactement ce que nous avons programmé en TP sur le lac gelé.

Évaluer une politique par itérations

L’idée est de transformer l’équation de Bellman en règle de mise à jour. On part de valeurs arbitraires (des zéros), puis on applique l’équation à chaque état, encore et encore :

$$V_{k+1}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma \, V_k(s') \Big]$$

• $V_k$ est l’estimation de $V^\pi$ après $k$ passages ;
• un passage sur tous les états s’appelle un balayage (sweep).

Pourquoi est-ce que ça converge ? Parce que l’opération qui transforme $V_k$ en $V_{k+1}$ est une contraction de rapport $\gamma$ : l’écart maximal entre deux fonctions de valeur est multiplié par au plus $\gamma$ à chaque application. L’erreur par rapport à $V^\pi$ diminue donc au moins comme $\gamma^k$, et $V_k$ converge vers l’unique point fixe, qui est $V^\pi$.

En pratique, on s’arrête quand un balayage ne change presque plus rien. On mesure le plus grand changement du balayage :

$$\Delta = \max_{s} \big\lvert V_{k+1}(s) - V_k(s) \big\rvert$$

et on arrête dès que $\Delta < \theta$, un petit seuil fixé à l’avance ($\theta = 10^{-5}$ en TP).

Synchrone ou en place ?

Il existe deux façons de faire un balayage. La version synchrone calcule toutes les nouvelles valeurs à partir de l’ancien tableau $V_k$, puis remplace tout d’un coup (il faut deux tableaux). La version en place (in-place) écrase chaque valeur dès qu’elle est calculée : les états traités plus tard dans le balayage profitent déjà des valeurs à jour. C’est le principe de la méthode de Gauss-Seidel en analyse numérique. Elle converge aussi vers $V^\pi$, et en général plus vite.

Exemple

Reprenons le couloir A, B, G du chapitre 2 (politique aléatoire, $\gamma = 0{,}9$), dont la solution exacte est $V(A) \approx 0{,}647$ et $V(B) \approx 0{,}791$. On part de $V = (0, 0)$ et on traite A puis B.

Balayage	Synchrone : $V(A)$	Synchrone : $V(B)$	En place : $V(A)$	En place : $V(B)$
1	0	0,5	0	0,5
2	0,225	0,5	0,225	0,601
3	0,326	0,601	0,372	0,667

Au deuxième balayage, la version en place calcule $V(B)$ avec le $V(A) = 0{,}225$ tout juste mis à jour : $V(B) = 0{,}5 \times 0{,}9 \times 0{,}225 + 0{,}5 = 0{,}601$. Elle prend ainsi un balayage d’avance.

Les deux versions convergent vers les mêmes valeurs. La version en place (traits pleins) profite dès le 2e balayage de la nouvelle valeur de A et garde un balayage d'avance.

Voici la fonction écrite en TP, qui travaille en place. Elle lit la dynamique du lac dans env.unwrapped.P, présentée au chapitre 1.

import numpy as np

def evaluation_politique(env, politique, gamma=0.9, theta=1e-5):
    """Calcule V^pi par balayages successifs de l'équation de Bellman."""
    n_etats = env.observation_space.n
    V = np.zeros(n_etats)
    balayages = 0
    while True:
        delta = 0.0
        for s in range(n_etats):
            v = 0.0
            for a, proba_a in enumerate(politique[s]):
                for p, s_suiv, r, termine in env.unwrapped.P[s][a]:
                    v += proba_a * p * (r + gamma * V[s_suiv])
            delta = max(delta, abs(V[s] - v))
            V[s] = v                      # mise à jour en place
        balayages += 1
        if delta < theta:
            return V, balayages

Sur le lac 8x8 non glissant, en TP, l’évaluation de la politique aléatoire uniforme avec $\gamma = 0{,}9$ a convergé en 26 balayages. Nous avons ensuite fait varier $\gamma$ :

$\gamma$	0,8	0,9	0,95	1,0
Balayages jusqu’à $\Delta < 10^{-5}$	17	26	37	71

Plus $\gamma$ est grand, plus l’évaluation est lente. C’est la contraction qui l’explique : avec $\gamma = 0{,}8$, chaque balayage réduit fortement l’erreur ; avec $\gamma$ proche de 1, beaucoup moins, et l’information venue de l’objectif doit se propager plus loin avant de devenir négligeable. Avec $\gamma = 1$, il n’y a même plus de contraction garantie. L’évaluation converge quand même ici, parce que tous les épisodes finissent dans un trou ou sur l’objectif, mais elle est plus de quatre fois plus lente qu’avec $\gamma = 0{,}8$.

Le plus grand changement Δ décroît à peu près géométriquement ; plus γ est proche de 1, plus la pente est douce et plus il faut de balayages pour passer sous θ.

À retenir

L’évaluation de politique applique l’équation de Bellman d’espérance comme une règle de mise à jour, balayage après balayage, jusqu’à ce que le plus grand changement $\Delta$ passe sous un seuil $\theta$. Elle converge parce que la mise à jour est une contraction de rapport $\gamma$ : plus $\gamma$ est proche de 1, plus elle est lente.

Améliorer une politique : devenir glouton

Supposons que nous connaissions $V^\pi$. Dans un état $s$, demandons-nous : que se passerait-il si je faisais l’action $a$ une fois, puis que je reprenais ma politique habituelle ? La réponse est justement $Q^\pi(s, a)$, qu’on calcule à partir de $V^\pi$ en regardant un pas en avant :

$$Q^\pi(s, a) = \sum_{s'} P(s' \mid s, a) \Big[ R(s, a, s') + \gamma \, V^\pi(s') \Big]$$

Si une action fait mieux que la politique actuelle, autant la prendre. La politique gloutonne (greedy) choisit, dans chaque état, l’action de plus grande valeur :

$$\pi'(s) = \arg\max_{a} Q^\pi(s, a)$$

Le théorème d’amélioration de politique garantit que ce changement ne peut pas nuire : $V^{\pi'}(s) \geq V^\pi(s)$ pour tous les états. Et si l’on n’a rien gagné nulle part, c’est que $\pi$ vérifiait déjà l’équation de Bellman d’optimalité : elle était optimale.

Pourquoi ? L’intuition tient en une phrase. Dans chaque état, faire $\pi'(s)$ une fois puis suivre $\pi$ rapporte $\max_a Q^\pi(s, a) \geq V^\pi(s)$ ; en répétant l’argument à chaque pas, suivre $\pi'$ tout le temps rapporte au moins autant.

def amelioration_politique(env, V, gamma=0.9):
    """Renvoie la politique déterministe gloutonne par rapport à V."""
    n_etats, n_actions = env.observation_space.n, env.action_space.n
    politique = np.zeros((n_etats, n_actions))
    for s in range(n_etats):
        q = np.zeros(n_actions)
        for a in range(n_actions):
            for p, s_suiv, r, termine in env.unwrapped.P[s][a]:
                q[a] += p * (r + gamma * V[s_suiv])
        politique[s, np.argmax(q)] = 1.0   # un 1 sur la meilleure action
    return politique

Piège

Il est tentant de dire : « je vais vers la case voisine qui a la plus grande valeur ». C’est faux dès que l’environnement est aléatoire. Sur le lac glissant, viser une case ne garantit pas d’y arriver : il faut calculer $Q$, qui moyenne sur toutes les issues de l’action, avant de prendre l’argmax. C’est aussi pour cela que l’amélioration a besoin du modèle $P$.

Exemple

Dans le couloir, la politique aléatoire a pour valeurs $V(A) \approx 0{,}647$ et $V(B) \approx 0{,}791$. Calculons $Q$ en regardant un pas en avant ($\gamma = 0{,}9$) :

• en A : gauche donne $0{,}9 \times 0{,}647 \approx 0{,}583$, droite donne $0{,}9 \times 0{,}791 \approx 0{,}712$ ;
• en B : gauche donne $0{,}9 \times 0{,}647 \approx 0{,}583$, droite donne $1 + 0 = 1$.

La politique gloutonne va à droite partout. Sa valeur est $V(A) = 0{,}9$ et $V(B) = 1$ : elle a bien progressé dans les deux états, comme le promet le théorème.

Dans chaque état, l'action gloutonne est celle dont la barre Q est la plus haute (droite). La nouvelle valeur dépasse l'ancienne dans les deux états, comme le garantit le théorème.

Policy iteration : alterner jusqu’à la stabilité

On a maintenant deux opérations complémentaires : l’évaluation mesure une politique, l’amélioration en produit une meilleure. L’itération sur les politiques (policy iteration) les enchaîne :

1. Partir d’une politique $\pi_0$ quelconque (la politique aléatoire uniforme en TP).
2. Évaluer : calculer $V^{\pi_k}$ par évaluation itérative.
3. Améliorer : $\pi_{k+1} \leftarrow$ la politique gloutonne par rapport à $V^{\pi_k}$.
4. Si $\pi_{k+1} = \pi_k$, s’arrêter : la politique est optimale. Sinon, revenir à l’étape 2.

$$\pi_0 \xrightarrow{\text{éval.}} V^{\pi_0} \xrightarrow{\text{amélio.}} \pi_1 \xrightarrow{\text{éval.}} V^{\pi_1} \xrightarrow{\text{amélio.}} \pi_2 \longrightarrow \dots \longrightarrow \pi^*$$

Pourquoi est-on sûr que ça s’arrête ? Dans un MDP fini, il n’y a qu’un nombre fini de politiques déterministes ($\lvert A \rvert^{\lvert S \rvert}$). Chaque itération produit une politique strictement meilleure, sauf si elle est déjà optimale. On ne peut donc pas tourner en rond, et l’algorithme termine. En pratique, il lui faut remarquablement peu d’itérations.

def policy_iteration(env, gamma=0.9, max_iterations=200):
    n_etats, n_actions = env.observation_space.n, env.action_space.n
    politique = np.ones((n_etats, n_actions)) / n_actions   # départ aléatoire
    for i in range(max_iterations):
        V, balayages = evaluation_politique(env, politique, gamma)
        nouvelle = amelioration_politique(env, V, gamma)
        if np.array_equal(nouvelle, politique):
            print(f"Politique stable après {i + 1} itérations")
            return politique, V
        politique = nouvelle
    print("Nombre maximal d'itérations atteint")
    return politique, V

Sur le lac, en TP, avec $\gamma = 0{,}9$, la politique optimale a été trouvée en 4 itérations. Les quatre évaluations successives ont demandé 26, 15, 15 et 15 balayages. La première évaluation, celle de la politique aléatoire, est la plus longue ; les suivantes portent sur des politiques déterministes, et se stabilisent en 15 balayages.

Policy iteration vue balayage par balayage : une longue évaluation de la politique aléatoire, puis trois évaluations de politiques déterministes, où Δ reste grand puis tombe d'un coup à 0 au 15e balayage.

Pourquoi 15 ? Une explication tient à la forme du lac. Avec une politique déterministe dans un environnement déterministe, la valeur d’une case est fixée dès que celle de sa case suivante l’est. Or la politique mène surtout vers le bas et la droite, c’est-à-dire vers des cases que le balayage (dans l’ordre 0, 1, …, 63) traite après : l’information venue de l’objectif ne remonte donc que d’une case par balayage. Le chemin le plus long vers G fait 14 pas ; au 14e balayage, toutes les valeurs sont en place, et le 15e constate qu’il n’y a plus rien à changer ($\Delta = 0$).

Évaluation de la politique optimale, en place : la valeur définitive remonte d'environ une case par balayage depuis G et atteint le départ au 14e.

Attention

Le critère d’arrêt « $\pi_{k+1} = \pi_k$ » est fragile quand plusieurs actions ont exactement la même valeur. np.argmax prend alors la première, qui n’est pas forcément l’action actuelle : la politique change sans s’améliorer, et le critère peut ne jamais être satisfait. Une parade simple consiste à ne changer d’action que si la nouvelle est strictement meilleure. Nous verrons au chapitre suivant ce que ces égalités ont provoqué en TP avec $\gamma = 1$.

En résumé

• L’évaluation de politique itère l’équation de Bellman d’espérance jusqu’à $\Delta < \theta$ ; elle converge car la mise à jour est une contraction de rapport $\gamma$.
• La version en place (façon Gauss-Seidel) réutilise immédiatement les nouvelles valeurs et converge en général plus vite que la version synchrone.
• En TP, l’évaluation de la politique aléatoire a demandé 17, 26, 37 et 71 balayages pour $\gamma$ = 0,8, 0,9, 0,95 et 1 : plus $\gamma$ est grand, plus c’est lent.
• L’amélioration de politique rend la politique gloutonne par rapport à $Q^\pi$ ; le théorème d’amélioration garantit $V^{\pi'} \geq V^\pi$ partout.
• Policy iteration alterne évaluation complète et amélioration jusqu’à ce que la politique ne change plus ; elle termine en un nombre fini d’itérations.
• En TP ($\gamma = 0{,}9$) : 4 itérations, avec des évaluations de 26, 15, 15 et 15 balayages.

Exercices

Exercice · Dérouler une évaluation à la main

facile

Dans le couloir A, B, G ($\gamma = 0{,}9$), on évalue la politique « toujours à droite » par balayages synchrones, en partant de $V = (0, 0)$.

1. Calculez $V_1$, $V_2$ et $V_3$.
2. Au bout de combien de balayages $\Delta$ devient-il nul ?

Voir la solution

Les équations sont $V_{k+1}(A) = 0{,}9 \, V_k(B)$ et $V_{k+1}(B) = 1$ (aller à droite depuis B atteint G).

1. $V_1 = (0{,}9 \times 0, \; 1) = (0, 1)$ ; $V_2 = (0{,}9 \times 1, \; 1) = (0{,}9, 1)$ ; $V_3 = (0{,}9, 1)$.
2. Le premier balayage change $V(B)$ de 1, le deuxième change $V(A)$ de 0,9, le troisième ne change rien : $\Delta = 0$ au 3e balayage. C’est le même mécanisme qu’au lac : la valeur remonte d’une case par balayage depuis l’objectif, et un balayage de plus constate la stabilité. (En place, dans l’ordre A puis B, ce serait identique : A est traité avant que B ne soit mis à jour.)

En code

Python

import numpy as np

gamma = 0.9
V = np.zeros(2)                          # V(A), V(B)
for k in range(1, 4):
    nouveau = np.array([0 + gamma * V[1],     # A --droite--> B, récompense 0
                        1 + gamma * 0])       # B --droite--> G, récompense 1
    delta = np.abs(nouveau - V).max()
    V = nouveau                               # balayage synchrone
    print(k, V, round(delta, 3))
# 1 [0. 1.] 1.0
# 2 [0.9 1. ] 0.9
# 3 [0.9 1. ] 0.0   -> Delta nul au 3e balayage

R

gamma <- 0.9
V <- c(A = 0, B = 0)
for (k in 1:3) {
  nouveau <- c(A = 0 + gamma * V[["B"]],   # A --droite--> B, récompense 0
               B = 1 + gamma * 0)          # B --droite--> G, récompense 1
  delta <- max(abs(nouveau - V))
  V <- nouveau                             # balayage synchrone
  cat(k, V, delta, "\n")
}
# 1 0 1 1
# 2 0.9 1 0.9
# 3 0.9 1 0     -> Delta nul au 3e balayage

Exercice · Améliorer une politique médiocre

moyen

Dans le couloir, on part de la politique « en A aller à gauche, en B aller à gauche ».

1. Que vaut $V^\pi$ ?
2. Calculez les valeurs $Q^\pi$ des quatre couples (état, action) et la politique gloutonne. Pourquoi est-ce ennuyeux en A ?
3. Déroulez policy iteration jusqu’au bout. Combien d’itérations faut-il ?

Voir la solution

1. Le robot ne va jamais en G : $V^\pi(A) = V^\pi(B) = 0$.
2. $Q^\pi(A, \text{gauche}) = 0{,}9 \times 0 = 0$, $Q^\pi(A, \text{droite}) = 0{,}9 \times V^\pi(B) = 0$, $Q^\pi(B, \text{gauche}) = 0$, $Q^\pi(B, \text{droite}) = 1$. En B, la politique gloutonne passe à « droite ». En A, les deux actions sont à égalité (0 et 0) : l’argmax choisit la première, « gauche ». La politique ne progresse pas en A à cette itération, car la valeur de B n’a pas encore profité du changement.
3. Itération 1 : on évalue ($V = (0, 0)$), on améliore, on obtient (gauche, droite), différente de la politique de départ. Itération 2 : on évalue (gauche, droite), qui donne $V(A) = 0$ (le robot reste bloqué contre le mur) et $V(B) = 1$ ; on améliore : en A, droite vaut $0{,}9$ contre $0$ pour gauche, on obtient (droite, droite). Itération 3 : on évalue, $V = (0{,}9, 1)$, l’amélioration redonne (droite, droite) : la politique est stable. Il faut 3 itérations, dont la dernière sert seulement à constater la stabilité.

En code

Python

import numpy as np

gamma = 0.9
# Couloir : états 0 = A, 1 = B, 2 = G (terminal) ; actions 0 = gauche, 1 = droite
suivant = np.array([[0, 1], [0, 2]])
recompense = np.array([[0.0, 0.0], [0.0, 1.0]])

def evaluer(pol):
    """Résout V = R + gamma P V pour une politique déterministe."""
    P, R = np.zeros((2, 2)), np.zeros(2)
    for s in range(2):
        s2 = suivant[s, pol[s]]
        R[s] = recompense[s, pol[s]]
        if s2 < 2:
            P[s, s2] = 1.0
    return np.linalg.solve(np.eye(2) - gamma * P, R)

pol = np.array([0, 0])                        # gauche partout
for it in range(1, 10):
    V = np.append(evaluer(pol), 0.0)          # V(G) = 0
    Q = recompense + gamma * V[suivant]       # Q[s, a], un pas en avant
    nouvelle = Q.argmax(axis=1)               # en cas d'égalité : la première action
    print(it, V[:2].round(3) + 0.0, Q.round(3).tolist(), nouvelle)
    if np.array_equal(nouvelle, pol):
        break
    pol = nouvelle
# 1 [0. 0.]   [[0.0, 0.0], [0.0, 1.0]]  [0 1]
# 2 [0. 1.]   [[0.0, 0.9], [0.0, 1.0]]  [1 1]
# 3 [0.9 1. ] [[0.81, 0.9], [0.81, 1.0]] [1 1]  -> stable après 3 itérations

R

gamma <- 0.9
# Couloir : états 1 = A, 2 = B, 3 = G (terminal) ; actions 1 = gauche, 2 = droite
suivant    <- matrix(c(1, 2,  1, 3), nrow = 2, byrow = TRUE)
recompense <- matrix(c(0, 0,  0, 1), nrow = 2, byrow = TRUE)

evaluer <- function(pol) {             # résout V = R + gamma P V
  P <- matrix(0, 2, 2); R <- numeric(2)
  for (s in 1:2) {
    s2 <- suivant[s, pol[s]]; R[s] <- recompense[s, pol[s]]
    if (s2 < 3) P[s, s2] <- 1
  }
  solve(diag(2) - gamma * P, R)
}

pol <- c(1, 1)                                     # gauche partout
for (it in 1:10) {
  V <- c(evaluer(pol), 0)                          # V(G) = 0
  Q <- recompense + gamma * matrix(V[suivant], 2)  # Q[s, a], un pas en avant
  nouvelle <- apply(Q, 1, which.max)               # égalité : la première action
  cat(it, round(V[1:2], 3), "| Q :", round(t(Q), 3), "|", nouvelle, "\n")
  if (all(nouvelle == pol)) break
  pol <- nouvelle
}
# 1 0 0     | Q : 0 0 0 1         | 1 2
# 2 0 1     | Q : 0 0.9 0 1       | 2 2
# 3 0.9 1   | Q : 0.81 0.9 0.81 1 | 2 2   -> stable après 3 itérations

Exercice · Pourquoi γ ralentit l'évaluation

difficile

On admet que chaque balayage synchrone multiplie l’erreur maximale $\lVert V_k - V^\pi \rVert_\infty$ par au plus $\gamma$, et que l’erreur initiale (avec $V_0 = 0$) vaut au plus $1/(1-\gamma)$ quand les récompenses sont comprises entre 0 et 1.

1. Majorez le nombre de balayages nécessaires pour garantir une erreur inférieure à $10^{-5}$, pour $\gamma = 0{,}8$ puis $\gamma = 0{,}9$.
2. En TP, il a fallu 17 et 26 balayages. Pourquoi ces nombres sont-ils plus petits que vos bornes ?

Voir la solution

1. Après $k$ balayages, l’erreur est au plus $\gamma^k / (1 - \gamma)$. On cherche le plus petit $k$ tel que $\gamma^k / (1 - \gamma) < 10^{-5}$, soit $k > \ln\big(10^{-5}(1-\gamma)\big) / \ln \gamma$.
   • $\gamma = 0{,}8$ : $\ln(2 \times 10^{-6}) / \ln 0{,}8 \approx -13{,}12 / -0{,}223 \approx 58{,}8$, donc 59 balayages.
   • $\gamma = 0{,}9$ : $\ln(10^{-6}) / \ln 0{,}9 \approx -13{,}82 / -0{,}105 \approx 131{,}1$, donc 132 balayages.
2. Ce sont des bornes dans le pire des cas. Au lac, elles sont très pessimistes : les récompenses sont presque toutes nulles, les trous arrêtent les épisodes (ce qui accélère la convergence), la mise à jour en place va plus vite que la version synchrone, et le critère du TP porte sur le changement $\Delta$ entre deux balayages, pas sur l’erreur réelle. La borne garde toutefois le bon sens de variation : le nombre de balayages croît avec $\gamma$, et explose quand $\gamma$ s’approche de 1.

En code

Python

import numpy as np

# Plus petit k tel que gamma^k / (1 - gamma) < 1e-5
for gamma in (0.8, 0.9):
    borne = np.log(1e-5 * (1 - gamma)) / np.log(gamma)
    print(gamma, round(borne, 1), int(np.floor(borne)) + 1)
# 0.8 58.8 59
# 0.9 131.1 132   (contre 17 et 26 balayages observés en TP)

R

# Plus petit k tel que gamma^k / (1 - gamma) < 1e-5
for (gamma in c(0.8, 0.9)) {
  borne <- log(1e-5 * (1 - gamma)) / log(gamma)
  cat(gamma, round(borne, 1), floor(borne) + 1, "\n")
}
# 0.8 58.8 59
# 0.9 131.1 132   (contre 17 et 26 balayages observés en TP)