Trouvez la politique optimale avec value iteration

Policy iteration trouve la politique optimale du lac gelé en quatre itérations seulement. Mais chacune de ces itérations contient une évaluation complète, avec ses dizaines de balayages. Faut-il vraiment attendre que l’évaluation ait convergé avant d’améliorer la politique ? Pas du tout, et c’est l’idée de value iteration : améliorer à chaque balayage.

Dans ce chapitre, vous allez construire cet algorithme, le comparer sans tricher avec policy iteration, puis faire le bilan complet du TP sur le lac gelé, y compris un résultat surprenant avec $\gamma = 1$. Nous terminerons par les limites de la programmation dynamique, qui motivent toute la partie 2.

Une seule mise à jour pour évaluer et améliorer

Rappelez-vous l’équation de Bellman d’optimalité du chapitre 2. Value iteration la transforme directement en règle de mise à jour, exactement comme l’évaluation de politique le faisait avec l’équation d’espérance :

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

La seule différence avec l’évaluation, c’est le $\max_a$ à la place de la moyenne $\sum_a \pi(a \mid s)$. On peut la lire de deux façons :

• c’est un balayage d’évaluation où, dans chaque état, on suppose que l’agent prend la meilleure action au vu des valeurs actuelles ;
• c’est policy iteration où l’évaluation est tronquée à un seul balayage avant chaque amélioration.

On arrête quand le plus grand changement $\Delta$ passe sous un seuil ($\theta = 10^{-6}$ en TP). La politique n’apparaît nulle part pendant les itérations : on l’extrait une seule fois à la fin, en prenant l’action gloutonne par rapport à la valeur obtenue.

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

Pourquoi est-ce que ça converge vers $V^*$ ? Pour la même raison que l’évaluation : l’opérateur de Bellman d’optimalité est une contraction de rapport $\gamma$ (en norme infinie, c’est-à-dire sur l’écart maximal entre deux états). Pour $\gamma < 1$, il a un unique point fixe, $V^*$, et les itérés s’en approchent géométriquement, quel que soit le point de départ.

import numpy as np

def value_iteration(env, gamma=0.9, theta=1e-6, max_balayages=1000):
    n_etats, n_actions = env.observation_space.n, env.action_space.n
    V = np.zeros(n_etats)

    def valeurs_actions(s):
        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])
        return q

    for k in range(max_balayages):
        delta = 0.0
        for s in range(n_etats):
            ancien = V[s]
            V[s] = valeurs_actions(s).max()      # Bellman d'optimalité, en place
            delta = max(delta, abs(ancien - V[s]))
        if delta < theta:
            print(f"Convergence après {k + 1} balayages")
            break

    # Extraction de la politique, une seule fois à la fin
    politique = np.zeros((n_etats, n_actions))
    for s in range(n_etats):
        politique[s, np.argmax(valeurs_actions(s))] = 1.0
    return politique, V

Exemple

Dans le couloir A, B, G ($\gamma = 0{,}9$), partons de $V = (0, 0)$ avec des balayages synchrones.

• Balayage 1 : en A, $\max(0{,}9 \times 0, \; 0{,}9 \times 0) = 0$ ; en B, $\max(0{,}9 \times 0, \; 1) = 1$. Donc $V_1 = (0, 1)$.
• Balayage 2 : en A, $\max(0{,}9 \times 0, \; 0{,}9 \times 1) = 0{,}9$ ; en B, $\max(0, 1) = 1$. Donc $V_2 = (0{,}9, 1)$.
• Balayage 3 : rien ne change, $\Delta = 0$.

On retrouve $V^* = (0{,}9, 1)$, et l’extraction donne « droite » dans les deux états. Là où policy iteration avait besoin d’une évaluation complète de la politique aléatoire, value iteration ne s’en est jamais préoccupée.

À retenir

Value iteration applique l’équation de Bellman d’optimalité comme règle de mise à jour : $V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a)[R + \gamma V_k(s')]$. Elle converge vers $V^*$ car c’est une contraction de rapport $\gamma$, et la politique optimale s’extrait à la fin par un argmax.

Policy iteration ou value iteration ?

En TP, sur le lac 8x8 non glissant avec $\gamma = 0{,}9$, value iteration a convergé en 15 balayages. Policy iteration, elle, avait trouvé la politique optimale en 4 itérations. La réponse rédigée en TP concluait donc : « policy iteration converge plus vite, 4 itérations contre 15 ».

C’est un piège classique. Ces deux nombres ne mesurent pas la même chose ! Une itération de policy iteration contient une évaluation complète, et nous avons vu au chapitre 3 que ces évaluations avaient demandé 26, 15, 15 et 15 balayages. Le bon décompte est donc :

	Policy iteration	Value iteration
Itérations « externes »	4	15
Balayages de tous les états	26 + 15 + 15 + 15 = 71	15
Améliorations de politique	4	1 (l’extraction finale)

Le coût réel d’un balayage est le même dans les deux cas : pour chaque état, parcourir chaque action et chaque transition. En balayages, value iteration est ici près de cinq fois moins coûteuse que policy iteration. La conclusion honnête n’est donc pas celle du TP.

Comptées en balayages, les « 4 itérations » de policy iteration pèsent 71 balayages contre 15 pour value iteration ; l'écart grandit avec γ à cause de la première évaluation.

Piège

Comparer policy iteration et value iteration en « itérations » est trompeur : une itération de policy iteration contient une évaluation complète, soit de nombreux balayages. Comparez toujours en balayages (ou en temps de calcul). Sur le lac du TP : 71 balayages pour policy iteration, 15 pour value iteration.

Cela ne veut pas dire que value iteration gagne toujours. Quand $\gamma$ est très proche de 1 et que l’espace d’états est grand, value iteration peut demander énormément de balayages, alors que policy iteration trouve la bonne politique en très peu d’améliorations. Le tableau suivant résume les deux approches.

	Policy iteration	Value iteration
Équation utilisée	Bellman d’espérance, puis argmax	Bellman d’optimalité (max dans la mise à jour)
Nombre d’itérations externes	faible	plus élevé
Coût d’une itération	élevé (évaluation complète)	un seul balayage
Critère d’arrêt	la politique ne change plus	$\Delta < \theta$
Politique	disponible à chaque itération	extraite à la fin

Entre les deux extrêmes, on peut évaluer une politique avec quelques balayages seulement avant de l’améliorer (on parle de policy iteration modifiée). Toutes ces variantes sont des cas de l’itération généralisée sur les politiques (generalized policy iteration) : évaluation et amélioration alternent, plus ou moins poussées, et se tirent mutuellement vers l’optimum. Ce schéma reviendra dans toute la partie 2.

L'itération généralisée : chaque évaluation rapproche V de la valeur de π, chaque amélioration rend π gloutonne par rapport à V, et le processus converge vers le seul point qui satisfait les deux.

En entretien

« Policy iteration évalue complètement la politique puis l’améliore : peu d’itérations, mais chacune coûteuse. Value iteration fait un seul balayage avec un max de Bellman à chaque fois : beaucoup d’itérations bon marché. Les deux convergent vers $V^*$, et les deux exigent de connaître le modèle. »

Le bilan du TP sur le lac gelé

Voici les résultats du TP, pour les quatre valeurs de $\gamma$ testées (lac 8x8 non glissant).

$\gamma$	Évaluation de la politique aléatoire	Policy iteration	Value iteration
0,8	17 balayages	3 itérations (17 + 15 + 15 balayages)	15 balayages
0,9	26 balayages	4 itérations (26 + 15 + 15 + 15)	15 balayages
0,95	37 balayages	4 itérations (37 + 15 + 15 + 15)	15 balayages
1,0	71 balayages	plafond de 200 itérations atteint	15 balayages

Les deux méthodes donnent-elles la même politique ?

Oui : pour $\gamma = 0{,}9$, policy iteration et value iteration renvoient la même politique. C’est attendu, puisque les deux convergent vers $V^*$ et en extraient une politique par le même argmax (qui prend la première action en cas d’égalité). En général, s’il y a plusieurs actions optimales dans un état, deux méthodes peuvent renvoyer des politiques différentes mais également optimales, avec la même fonction de valeur.

Voici la fonction de valeur optimale pour $\gamma = 0{,}9$ (valeurs recalculées et arrondies ; les trous et l’objectif valent 0) :

0.254 0.282 0.314 0.349 0.387 0.430 0.478 0.531
0.282 0.314 0.349 0.387 0.430 0.478 0.531 0.590
0.314 0.349 0.387   H   0.478 0.531 0.590 0.656
0.349 0.387 0.430 0.478 0.531   H   0.656 0.729
0.314 0.349 0.387   H   0.590 0.656 0.729 0.810
0.282   H     H   0.590 0.656 0.729   H   0.900
0.314   H   0.478 0.531   H   0.810   H   1.000
0.349 0.387 0.430   H   0.810 0.900 1.000   G

Chaque valeur est une puissance de 0,9 : une case à $d$ pas de l’objectif vaut $0{,}9^{d-1}$. La case de départ, à 14 pas, vaut $0{,}9^{13} \approx 0{,}254$. La carte se lit comme une carte de distances à l’objectif, déformée par les trous.

Les mêmes valeurs que le tableau, en nuances : elles croissent vers G par puissances de 0,9. Les flèches (argmax) descendent le gradient de distance et forment le chemin de 14 pas depuis S.

Pourquoi value iteration converge-t-elle toujours en 15 balayages ?

Le nombre de balayages de value iteration ne dépend pas de $\gamma$ ici. Le lac est déterministe : la valeur d’une case est fixée dès que celle de la case suivante sur le meilleur chemin l’est. Comme au chapitre 3, l’information remonte depuis l’objectif d’environ une case par balayage, le chemin le plus long vers G fait 14 pas, et le 15e balayage constate que plus rien ne bouge. La valeur de $\gamma$ change les nombres (0,9 puissance $d-1$ ou 0,8 puissance $d-1$), pas le nombre d’étapes pour les obtenir.

Et si l’on part de la politique optimale ?

En TP, relancer policy iteration à partir de la politique optimale a donné une seule itération (une évaluation de 15 balayages) : l’amélioration redonne la même politique, et l’algorithme s’arrête aussitôt. C’est rassurant, et c’est une propriété utile en pratique : si l’environnement change un peu, repartir de l’ancienne politique (démarrage à chaud, warm start) coûte beaucoup moins cher que repartir de zéro.

Le cas surprenant de γ = 1

Avec $\gamma = 1$, policy iteration n’a jamais déclaré la politique stable : le plafond de 200 itérations a été atteint, avec des évaluations de 3, 4 et 5 balayages qui se répétaient en boucle. Que s’est-il passé ?

En rejouant le calcul pas à pas, on comprend le mécanisme. Sans actualisation, atteindre l’objectif rapporte 1 quelle que soit la durée du trajet. Après la deuxième évaluation, toutes les cases depuis lesquelles G est accessible valent donc exactement 1. Mais alors, dans une telle case, pousser contre le mur ou reculer vaut aussi 1 : on reste sur une case qui vaut 1 ! Beaucoup d’actions sont à égalité, et np.argmax prend la première, « gauche ». La nouvelle politique va à gauche presque partout, se coince contre les bords ou tourne en rond, et n’atteint plus jamais l’objectif : sa valeur retombe à 0. L’amélioration suivante ne répare que quelques cases proches de G (les seules qui valent encore 1), et le même mécanisme se reproduit : les évaluations courtes de 3, 4 et 5 balayages s’expliquent ainsi, puisque presque toutes les valeurs sont nulles.

Value iteration n’est pas épargnée. Elle converge bien, en 15 balayages, vers la bonne valeur ($V^*(S) = 1$). Mais si l’on déroule la politique qu’elle extrait avec $\gamma = 1$, le robot parti de S reste bloqué et n’atteint jamais G : la valeur est juste, la politique extraite par argmax ne l’est pas.

Même algorithme, même nombre de balayages. Avec γ = 1, toutes les actions qui ne tombent pas dans un trou valent 1 : l'argmax prend « gauche » à égalité, et le robot reste en S.

Attention

Avec $\gamma = 1$, rien ne pousse l’agent à progresser : un chemin de 14 pas et un chemin infini qui finirait par arriver ont la même valeur, et faire du surplace ne coûte rien. Trois correctifs classiques : prendre $\gamma < 1$ ; ne changer d’action que si l’amélioration est strictement positive ; ou ajouter une petite pénalité à chaque pas (par exemple $-0{,}01$), qui rend les chemins courts préférables même sans actualisation.

Les limites de la programmation dynamique

Dernière question du TP : pourquoi toutes ces méthodes exigent-elles de connaître $P$ et $R$, et qu’est-ce que cela implique ?

Chaque mise à jour calcule une espérance exacte : $\sum_{s'} P(s' \mid s, a) [\dots]$. Sans les probabilités de transition, impossible de faire cette somme. Et l’amélioration de politique a besoin de comparer les actions via $Q$, donc de savoir où chaque action peut mener. D’où plusieurs limites :

• Le modèle est rarement connu. Un robot réel, un marché, un joueur humain : personne ne fournit les probabilités de transition. FrozenLake est un cas d’école où env.unwrapped.P donne tout.
• Chaque balayage parcourt tous les états. Pour chaque état et chaque action, il faut sommer sur les états suivants, soit jusqu’à $\lvert S \rvert^2 \lvert A \rvert$ opérations par balayage. C’est trivial pour 64 cases, impossible pour les positions d’un jeu de go (plus de $10^{170}$).
• La malédiction de la dimension. Si l’état est décrit par plusieurs variables, leur nombre de combinaisons explose. Un état continu (une position, une vitesse) doit être discrétisé, ce qui aggrave encore le problème.

Les réponses à ces limites structurent la suite du cours : apprendre à partir d’échantillons au lieu de calculer des espérances exactes (Monte-Carlo, différences temporelles, Q-learning), et approcher $V$ ou $Q$ par une fonction paramétrée, typiquement un réseau de neurones (deep RL). Une troisième voie, l’apprentissage avec modèle (model-based RL), consiste à apprendre $P$ et $R$ à partir des interactions, puis à planifier avec le modèle appris.

En entretien

« La programmation dynamique, ce n’est pas vraiment de l’apprentissage : on connaît le modèle et on planifie. Dès que le modèle est inconnu ou que l’espace d’états est immense, on passe à des méthodes qui apprennent à partir d’échantillons, comme Q-learning, et on approche les valeurs par des réseaux de neurones. »

En résumé

• Value iteration applique l’équation de Bellman d’optimalité balayage après balayage, puis extrait la politique optimale par un argmax final.
• Elle converge vers $V^*$ car l’opérateur d’optimalité est une contraction de rapport $\gamma$.
• En TP : 15 balayages pour value iteration, contre 4 itérations mais 71 balayages pour policy iteration ; il faut comparer en balayages, pas en itérations.
• Les deux méthodes ont donné la même politique ; partir de la politique optimale ne demande qu’une itération de policy iteration.
• Avec $\gamma = 1$, les égalités entre actions ont fait échouer le critère d’arrêt de policy iteration (plafond de 200 itérations) : rien ne pousse l’agent à progresser.
• La programmation dynamique exige le modèle et un balayage de tous les états : elle ne passe pas à l’échelle, d’où les méthodes sans modèle et l’approximation de fonctions.

Exercices

Exercice · Compter le coût réel

facile

À partir des résultats du TP, calculez le nombre total de balayages de policy iteration pour $\gamma = 0{,}8$ et pour $\gamma = 0{,}95$, et comparez à value iteration. Qu’en concluez-vous ?

Voir la solution

• $\gamma = 0{,}8$ : $17 + 15 + 15 = 47$ balayages pour policy iteration, contre 15 pour value iteration (environ 3 fois moins).
• $\gamma = 0{,}95$ : $37 + 15 + 15 + 15 = 82$ balayages, contre 15 (plus de 5 fois moins).

Sur ce lac déterministe, value iteration est toujours la moins coûteuse en balayages, et l’écart grandit avec $\gamma$, parce que la première évaluation (celle de la politique aléatoire) devient de plus en plus longue.

En code

Python

# Balayages des évaluations successives de policy iteration (résultats du TP)
policy_iteration = {0.8: [17, 15, 15], 0.9: [26, 15, 15, 15], 0.95: [37, 15, 15, 15]}
value_iteration = 15

for gamma, balayages in policy_iteration.items():
    total = sum(balayages)
    print(gamma, total, round(total / value_iteration, 1))
# 0.8 47 3.1
# 0.9 71 4.7
# 0.95 82 5.5

R

# Balayages des évaluations successives de policy iteration (résultats du TP)
policy_iteration <- list("0.8" = c(17, 15, 15), "0.9" = c(26, 15, 15, 15),
                         "0.95" = c(37, 15, 15, 15))
value_iteration <- 15

total <- sapply(policy_iteration, sum)
rbind(total, rapport = round(total / value_iteration, 1))
#          0.8  0.9 0.95
# total   47.0 71.0 82.0
# rapport  3.1  4.7  5.5

Exercice · Value iteration sur un lac glissant miniature

moyen

Un couloir A, B, G : depuis A, l’action « droite » mène en B avec probabilité 0,8 et laisse en A avec probabilité 0,2 ; l’action « rester » laisse en A. Depuis B, « droite » atteint G (récompense 1) avec probabilité 0,8 et laisse en B avec probabilité 0,2 ; « rester » laisse en B. On prend $\gamma = 0{,}9$ et on part de $V = (0, 0)$.

1. Faites deux balayages synchrones de value iteration.
2. Calculez la valeur exacte $V^*(B)$ et $V^*(A)$ en résolvant les équations de Bellman d’optimalité (en supposant que « droite » est optimale partout).

Voir la solution

1. Balayage 1 : en A, droite vaut $0{,}8 \times 0{,}9 \times 0 + 0{,}2 \times 0{,}9 \times 0 = 0$ et rester vaut 0, donc $V_1(A) = 0$ ; en B, droite vaut $0{,}8 \times 1 + 0{,}2 \times 0{,}9 \times 0 = 0{,}8$, donc $V_1(B) = 0{,}8$. Balayage 2 : en A, droite vaut $0{,}8 \times 0{,}9 \times 0{,}8 + 0{,}2 \times 0{,}9 \times 0 = 0{,}576$ ; en B, droite vaut $0{,}8 + 0{,}2 \times 0{,}9 \times 0{,}8 = 0{,}944$. Donc $V_2 = (0{,}576, \; 0{,}944)$.
2. En B : $V^*(B) = 0{,}8 + 0{,}18 \, V^*(B)$, donc $V^*(B) = 0{,}8 / 0{,}82 \approx 0{,}976$. En A : $V^*(A) = 0{,}72 \, V^*(B) + 0{,}18 \, V^*(A)$, donc $V^*(A) = 0{,}72 \times 0{,}976 / 0{,}82 \approx 0{,}857$. On vérifie que « rester » est moins bon : en B, il vaut $0{,}9 \times 0{,}976 \approx 0{,}878 < 0{,}976$. Avec l’aléa, la convergence n’est plus finie en quelques balayages : les valeurs s’approchent de la limite géométriquement.

En code

Python

import numpy as np

gamma = 0.9

def balayage(V):
    """Un balayage synchrone de value iteration : renvoie V et Q (actions : droite, rester)."""
    VA, VB = V
    qA = [0.8 * gamma * VB + 0.2 * gamma * VA, gamma * VA]
    qB = [0.8 * 1 + 0.2 * gamma * VB, gamma * VB]    # G terminal : valeur 0
    return np.array([max(qA), max(qB)]), (qA, qB)

V = np.zeros(2)
for k in range(1, 3):
    V, _ = balayage(V)
    print(k, V.round(3))
# 1 [0.  0.8]
# 2 [0.576 0.944]

for k in range(500):                       # on itère jusqu'à convergence
    V, (qA, qB) = balayage(V)
print(V.round(3), round(qB[1], 3))         # [0.857 0.976], rester en B : 0.878
print(round(0.8 / 0.82, 3), round(0.72 * (0.8 / 0.82) / 0.82, 3))   # 0.976 0.857 (formules exactes)

R

gamma <- 0.9
balayage <- function(V) {        # actions : droite, rester ; G terminal de valeur 0
  qA <- c(0.8 * gamma * V[2] + 0.2 * gamma * V[1], gamma * V[1])
  qB <- c(0.8 * 1 + 0.2 * gamma * V[2], gamma * V[2])
  list(V = c(max(qA), max(qB)), qB = qB)
}

V <- c(0, 0)
for (k in 1:2) { V <- balayage(V)$V; cat(k, round(V, 3), "\n") }
# 1 0 0.8
# 2 0.576 0.944

for (k in 1:500) { res <- balayage(V); V <- res$V }   # jusqu'à convergence
round(V, 3); round(res$qB[2], 3)       # 0.857 0.976 ; rester en B : 0.878
round(c(0.72 * (0.8 / 0.82) / 0.82, 0.8 / 0.82), 3)   # 0.857 0.976 (formules exactes)

Exercice · Réparer policy iteration pour γ = 1

difficile

Reprenez la fonction amelioration_politique du chapitre 3. Modifiez-la pour qu’elle ne change l’action d’un état que si une autre action est strictement meilleure (de plus de $10^{-9}$) que l’action actuelle. Expliquez pourquoi cette modification règle le problème observé avec $\gamma = 1$.

Voir la solution

def amelioration_prudente(env, V, politique, gamma=1.0, tol=1e-9):
    n_etats, n_actions = env.observation_space.n, env.action_space.n
    nouvelle = politique.copy()
    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])
        actuelle = np.argmax(politique[s])        # l'action (ou la plus probable) de la politique actuelle
        meilleure = np.argmax(q)
        if q[meilleure] > q[actuelle] + tol:      # on ne change que si c'est strictement mieux
            nouvelle[s] = 0.0
            nouvelle[s, meilleure] = 1.0
    return nouvelle

(Pour la toute première amélioration, qui part de la politique aléatoire, on peut garder la version d’origine afin d’obtenir une politique déterministe.)

Avec $\gamma = 1$, le problème venait des égalités : dès qu’une politique atteint l’objectif depuis toutes les cases possibles, toutes ces cases valent 1, et np.argmax remplaçait l’action actuelle par « gauche », qui vaut aussi 1 sur le papier mais fait tourner en rond. Avec la version prudente, l’action actuelle, qui vaut déjà le maximum, est conservée : l’amélioration renvoie exactement la même politique et l’algorithme s’arrête. Le théorème d’amélioration reste valable, puisqu’on ne change une action que pour une action strictement meilleure.

En code

Python

import numpy as np

# Couloir A (0), B (1), G (2, terminal), gamma = 1 ; 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, balayages=200):
    V = np.zeros(3)
    for _ in range(balayages):                 # évaluation en place (gamma = 1)
        for s in range(2):
            V[s] = recompense[s, pol[s]] + V[suivant[s, pol[s]]]
    return V

def policy_iteration(prudente, n_iter=7):
    pol = np.array([0, 0])     # résultat de la 1re amélioration depuis l'aléatoire
    historique = ["gg"]                        # (action en A, action en B), g = gauche, d = droite
    for _ in range(n_iter):
        Q = recompense + evaluer(pol)[suivant]
        nouvelle = Q.argmax(axis=1)            # égalité : la première action (gauche)
        if prudente:                           # ne change que si c'est strictement mieux
            garder = Q.max(axis=1) <= Q[[0, 1], pol] + 1e-9
            nouvelle = np.where(garder, pol, nouvelle)
        if np.array_equal(nouvelle, pol):
            return " -> ".join(historique) + " : stable"
        pol = nouvelle
        historique.append("".join("gd"[a] for a in pol))
    return " -> ".join(historique) + " : jamais stable"

print(policy_iteration(prudente=False))
# gg -> gd -> dd -> gg -> gd -> dd -> gg -> gd : jamais stable
print(policy_iteration(prudente=True))
# gg -> gd -> dd : stable

R

# Couloir A (1), B (2), G (3, terminal), gamma = 1 ; 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, balayages = 200) {
  V <- c(0, 0, 0)
  for (k in 1:balayages) for (s in 1:2)          # évaluation en place (gamma = 1)
    V[s] <- recompense[s, pol[s]] + V[suivant[s, pol[s]]]
  V
}

policy_iteration <- function(prudente, n_iter = 7) {
  pol <- c(1, 1)            # résultat de la 1re amélioration depuis l'aléatoire
  historique <- "gg"        # (action en A, action en B), g = gauche, d = droite
  for (k in 1:n_iter) {
    Q <- recompense + matrix(evaluer(pol)[suivant], 2)
    nouvelle <- apply(Q, 1, which.max)           # égalité : la première action
    if (prudente) {                              # ne change que si strictement mieux
      garder <- apply(Q, 1, max) <= Q[cbind(1:2, pol)] + 1e-9
      nouvelle[garder] <- pol[garder]
    }
    if (all(nouvelle == pol)) return(paste(paste(historique, collapse = " -> "), ": stable"))
    pol <- nouvelle
    historique <- c(historique, paste(c("g", "d")[pol], collapse = ""))
  }
  paste(paste(historique, collapse = " -> "), ": jamais stable")
}

policy_iteration(prudente = FALSE)
# gg -> gd -> dd -> gg -> gd -> dd -> gg -> gd : jamais stable
policy_iteration(prudente = TRUE)
# gg -> gd -> dd : stable