Mesurez la valeur d'une politique avec Bellman

Au chapitre précédent, le robot du lac gelé disposait d’une politique, mais rien ne permettait encore de dire si elle était bonne. Une politique se juge sur ce qu’elle rapporte en moyenne, depuis chaque case du lac. Cette moyenne porte un nom, la fonction de valeur, et elle obéit à une équation d’une grande élégance : l’équation de Bellman.

Ce chapitre est le cœur théorique du cours. Tous les algorithmes qui suivent, de la programmation dynamique au Q-learning, ne sont que des façons différentes de résoudre les équations que vous allez écrire ici.

La valeur d’un état

Placez le robot sur une case du lac et laissez-le suivre sa politique $\pi$. Le retour $G_t$ qu’il obtient est aléatoire : la politique peut tirer ses actions au hasard, et le lac peut être glissant. On définit donc la valeur de l’état $s$ sous la politique $\pi$ comme l’espérance de ce retour :

$$V^\pi(s) = \mathbb{E}_\pi\big[\, G_t \mid s_t = s \,\big]$$

• $V^\pi(s)$ est la fonction de valeur d’état (state-value function) ;
• $\mathbb{E}_\pi$ est l’espérance quand l’agent suit $\pi$ (et que l’environnement suit $P$) ;
• la condition $s_t = s$ signifie qu’on part de l’état $s$.

Au lac, où la seule récompense est le $+1$ de l’objectif, $V^\pi(s)$ se lit comme une probabilité d’atteindre G, pondérée par la durée du trajet. Une case proche de l’objectif, pour une bonne politique, a une valeur proche de 1 ; une case d’où l’on tombe presque toujours dans un trou a une valeur proche de 0.

Les états terminaux ont une valeur nulle : une fois dans un trou ou sur l’objectif, il n’y a plus de récompense à venir. La récompense de l’objectif est comptée au moment où l’on y entre, donc dans la valeur de la case d’avant.

La valeur d’une action

Pour décider, il est souvent plus utile de connaître la valeur d’une action précise. On définit la fonction de valeur d’action (action-value function), ou fonction Q :

$$Q^\pi(s, a) = \mathbb{E}_\pi\big[\, G_t \mid s_t = s, \, a_t = a \,\big]$$

C’est le retour espéré si l’on fait d’abord l’action $a$ dans l’état $s$, puis qu’on suit $\pi$ ensuite. Les deux fonctions sont liées très simplement : la valeur d’un état est la moyenne des valeurs de ses actions, pondérée par la politique.

$$V^\pi(s) = \sum_{a} \pi(a \mid s) \, Q^\pi(s, a)$$

Pourquoi s’embêter avec deux fonctions ? Parce que $V$ dit où il fait bon être, alors que $Q$ dit quoi faire. Nous verrons que, pour améliorer une politique, c’est $Q$ qu’il faut regarder.

L’équation de Bellman d’espérance

Voici l’idée qui change tout. Le retour se décompose en « ce que je gagne maintenant » plus « ce que je gagnerai ensuite, actualisé » :

$$G_t = r_{t+1} + \gamma \, G_{t+1}$$

En prenant l’espérance, et grâce à la propriété de Markov (la suite ne dépend que de l’état atteint), on obtient une relation entre la valeur d’un état et celle de ses successeurs. C’est l’équation de Bellman d’espérance :

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

Lisez-la de l’intérieur vers l’extérieur :

• $R(s, a, s') + \gamma V^\pi(s')$ est ce que rapporte une transition précise : la récompense immédiate, plus la valeur actualisée de l’état d’arrivée ;
• la somme sur $s'$, pondérée par $P(s' \mid s, a)$, fait la moyenne sur les issues possibles de l’action (c’est $Q^\pi(s, a)$) ;
• la somme sur $a$, pondérée par $\pi(a \mid s)$, fait la moyenne sur les actions que la politique peut choisir.

À retenir

La valeur d’un état est la récompense immédiate espérée, plus la valeur actualisée de l’état suivant. L’équation de Bellman traduit cette phrase : elle relie la valeur de chaque état à celle de ses voisins, et elle est vérifiée par $V^\pi$, et par elle seule.

Si vous avez suivi le cours de modèles stochastiques, ce raisonnement vous est familier : c’est exactement le conditionnement sur le premier pas qui sert à calculer les probabilités et les temps d’absorption d’une chaîne de Markov. Une politique fixée transforme le MDP en chaîne de Markov, et $V^\pi$ se calcule comme une quantité d’absorption.

Un exemple à la main : le couloir

Le lac a 64 états, c’est trop pour un calcul à la main. Prenons un couloir de trois cases, A, B et G (l’objectif, terminal). Deux actions : gauche et droite, sans glissade. Depuis A, gauche fait buter contre le mur (on reste en A) et droite mène en B. Depuis B, gauche ramène en A et droite atteint G, avec une récompense de $+1$. On prend $\gamma = 0{,}9$ et la politique aléatoire uniforme ($1/2$ pour chaque action).

Exemple

L’équation de Bellman donne une équation par état non terminal (et $V(G) = 0$) :

$$V(A) = \tfrac{1}{2} \big[ 0 + 0{,}9 \, V(A) \big] + \tfrac{1}{2} \big[ 0 + 0{,}9 \, V(B) \big]$$$$V(B) = \tfrac{1}{2} \big[ 0 + 0{,}9 \, V(A) \big] + \tfrac{1}{2} \big[ 1 + 0{,}9 \times 0 \big]$$

Deux équations linéaires, deux inconnues. La première donne $0{,}55 \, V(A) = 0{,}45 \, V(B)$. En remplaçant dans la seconde, on trouve $V(B) = 0{,}275 / 0{,}3475 \approx 0{,}791$, puis $V(A) \approx 0{,}647$.

Même en marchant au hasard, le robot finit toujours par atteindre G (il n’y a pas de trou), mais le détour coûte : depuis B, la valeur n’est que de 0,791 alors qu’aller directement à droite rapporterait 1.

Le couloir sous la politique aléatoire. Chaque flèche est suivie une fois sur deux ; les valeurs 0,647 et 0,791 sont la solution des deux équations de Bellman.

Une équation linéaire, un système à résoudre

L’exemple le montre : pour une politique fixée, l’équation de Bellman est linéaire en les valeurs. En notation matricielle, avec $P^\pi$ la matrice de transition de la chaîne obtenue en suivant $\pi$ et $R^\pi$ le vecteur des récompenses immédiates espérées, elle s’écrit :

$$V^\pi = R^\pi + \gamma \, P^\pi \, V^\pi \quad \Longleftrightarrow \quad V^\pi = (I - \gamma P^\pi)^{-1} R^\pi$$

• $V^\pi$ est le vecteur des valeurs, une composante par état ;
• $P^\pi(s, s') = \sum_a \pi(a \mid s) P(s' \mid s, a)$ est la probabilité de passer de $s$ à $s'$ en suivant $\pi$ ;
• $R^\pi(s)$ est la récompense espérée au prochain pas depuis $s$ ;
• $I$ est la matrice identité. Pour $\gamma < 1$, la matrice $I - \gamma P^\pi$ est toujours inversible.

import numpy as np

gamma = 0.9
# États non terminaux : 0 = A, 1 = B (G est terminal, de valeur 0)
# Transitions de la politique aléatoire, restreintes aux états non terminaux
P_pi = np.array([[0.5, 0.5],    # depuis A : reste en A ou va en B
                 [0.5, 0.0]])   # depuis B : va en A (l'autre moitié sort vers G)
R_pi = np.array([0.0, 0.5])     # depuis B, une chance sur deux de gagner 1

V = np.linalg.solve(np.eye(2) - gamma * P_pi, R_pi)
print(V.round(3))   # [0.647 0.791]

Pour un petit problème, cette résolution directe est parfaite. Mais inverser une matrice coûte de l’ordre de $\lvert S \rvert^3$ opérations : pour un million d’états, c’est hors de portée. On préfère alors itérer l’équation, et c’est tout l’objet du chapitre suivant.

Les valeurs optimales et l’équation de Bellman d’optimalité

Parmi toutes les politiques, certaines sont meilleures que d’autres. On définit la valeur optimale d’un état comme la meilleure valeur atteignable :

$$V^*(s) = \max_\pi V^\pi(s) \qquad Q^*(s, a) = \max_\pi Q^\pi(s, a)$$

Ces fonctions vérifient elles aussi une équation de Bellman, où la moyenne sur les actions est remplacée par un maximum : un agent optimal choisit toujours la meilleure action. C’est l’équation de Bellman d’optimalité :

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

Le symbole $\max_a$ prend la plus grande valeur sur toutes les actions possibles ; $a'$ désigne l’action choisie dans l’état suivant $s'$.

Les deux équations regardent un pas en avant, puis remontent les valeurs r + γV(s′) des feuilles. Seul le traitement des actions change : moyenne pondérée par π pour l'espérance, maximum pour l'optimalité.

Deux différences importantes avec l’équation d’espérance :

1. À cause du $\max$, l’équation est non linéaire : impossible de la résoudre par une simple inversion de matrice. On la résoudra par itérations (value iteration, chapitre 4).
2. Une fois $Q^*$ connue, la politique optimale s’en déduit immédiatement : dans chaque état, on prend l’action de plus grande valeur.

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

Le symbole $\arg\max_a$ désigne l’action qui réalise le maximum (et non la valeur de ce maximum). Un résultat fondamental garantit que, dans un MDP fini, il existe toujours une politique optimale déterministe, meilleure ou égale à toutes les autres dans tous les états à la fois.

Exemple

Reprenons le couloir. L’agent optimal va toujours à droite. Depuis B, il gagne 1 tout de suite : $V^*(B) = 1$. Depuis A, il atteint B en un pas, puis gagne 1 : $V^*(A) = 0{,}9 \times 1 = 0{,}9$.

Vérifions l’équation d’optimalité en A : aller à gauche vaut $Q^*(A, \text{gauche}) = 0 + 0{,}9 \, V^*(A) = 0{,}81$ ; aller à droite vaut $Q^*(A, \text{droite}) = 0 + 0{,}9 \, V^*(B) = 0{,}9$. Le maximum est bien 0,9, atteint pour « droite ».

Dans chaque état, la flèche verte (droite) a la plus grande valeur Q* : c'est l'action choisie par l'argmax, et V* reprend sa valeur.

Au lac gelé, le même raisonnement donne $V^*(S) = 0{,}9^{13} \approx 0{,}254$ pour $\gamma = 0{,}9$ : la valeur optimale du départ est le retour du plus court chemin. À titre de comparaison, si vous évaluez la politique aléatoire uniforme sur le même lac, vous obtenez une valeur de départ d’environ $3 \times 10^{-5}$ : en marchant au hasard, le robot tombe presque toujours dans un trou avant d’arriver.

Même échelle de couleurs pour les deux politiques. Au hasard, seules les cases voisines de G ont une valeur visible ; la politique optimale donne 0,254 dès le départ.

Piège

Ne confondez pas $V^\pi$ et $V^*$. La première mesure une politique donnée, bonne ou mauvaise ; la seconde est la meilleure valeur possible. L’équation d’espérance (avec $\sum_a \pi(a \mid s)$) caractérise $V^\pi$ ; l’équation d’optimalité (avec $\max_a$) caractérise $V^*$.

En entretien

« L’équation de Bellman dit que la valeur d’un état est la récompense immédiate plus la valeur actualisée de l’état suivant, en espérance. Pour une politique fixée, c’est un système linéaire ; dans sa version d’optimalité, on prend le maximum sur les actions, et la politique optimale consiste à choisir l’action qui maximise $Q^*$. »

En résumé

• $V^\pi(s)$ est le retour espéré en partant de $s$ et en suivant $\pi$ ; $Q^\pi(s, a)$ est le retour espéré en faisant d’abord $a$, puis en suivant $\pi$.
• $V^\pi(s) = \sum_a \pi(a \mid s) \, Q^\pi(s, a)$ : la valeur d’un état est la moyenne des valeurs de ses actions.
• L’équation de Bellman d’espérance relie la valeur d’un état à celle de ses successeurs ; pour une politique fixée, c’est un système linéaire, $V^\pi = (I - \gamma P^\pi)^{-1} R^\pi$.
• L’équation de Bellman d’optimalité remplace la moyenne sur les actions par un maximum ; elle est non linéaire et caractérise $V^*$ et $Q^*$.
• La politique optimale se lit sur $Q^*$ : $\pi^*(s) = \arg\max_a Q^*(s, a)$, et il en existe toujours une déterministe dans un MDP fini.
• Au lac gelé avec $\gamma = 0{,}9$, $V^*(S) \approx 0{,}254$, contre environ $3 \times 10^{-5}$ pour la politique aléatoire.

Exercices

Exercice · Passer de Q à V

facile

Dans un état $s$, une politique choisit gauche avec probabilité 0,5, bas avec probabilité 0,3 et droite avec probabilité 0,2 (jamais haut). On connaît $Q^\pi(s, \text{gauche}) = 0{,}2$, $Q^\pi(s, \text{bas}) = 0{,}6$, $Q^\pi(s, \text{droite}) = 0{,}5$ et $Q^\pi(s, \text{haut}) = 0{,}9$.

1. Calculez $V^\pi(s)$.
2. Quelle action une politique « gloutonne » par rapport à $Q^\pi$ choisirait-elle ici ?

Voir la solution

1. $V^\pi(s) = 0{,}5 \times 0{,}2 + 0{,}3 \times 0{,}6 + 0{,}2 \times 0{,}5 + 0 \times 0{,}9 = 0{,}1 + 0{,}18 + 0{,}1 = 0{,}38$.
2. L’action de plus grande valeur est « haut » ($0{,}9$), que la politique actuelle ne choisit jamais. Une politique gloutonne choisirait « haut » dans cet état. Nous verrons au chapitre 3 que ce changement ne peut qu’améliorer la politique.

En code

Python

import numpy as np

actions = ["gauche", "bas", "droite", "haut"]
pi = np.array([0.5, 0.3, 0.2, 0.0])        # pi(a | s)
Q = np.array([0.2, 0.6, 0.5, 0.9])         # Q^pi(s, a)

print(round(pi @ Q, 3))                    # V^pi(s) = somme pi * Q : 0.38
print(actions[np.argmax(Q)])               # action gloutonne : haut

R

actions <- c("gauche", "bas", "droite", "haut")
pi <- c(0.5, 0.3, 0.2, 0)          # pi(a | s)
Q  <- c(0.2, 0.6, 0.5, 0.9)        # Q^pi(s, a)

sum(pi * Q)                        # V^pi(s) : 0.38
actions[which.max(Q)]              # action gloutonne : "haut"

Exercice · Le couloir avec une autre politique

moyen

Dans le couloir A, B, G du chapitre ($\gamma = 0{,}9$), on considère la politique déterministe suivante : en A aller à droite, en B aller à gauche.

1. Écrivez les équations de Bellman de cette politique et résolvez-les. Qu’observez-vous ?
2. Calculez $Q^\pi(B, \text{droite})$ pour cette politique. Qu’en concluez-vous ?

Voir la solution

1. Les équations sont $V(A) = 0 + 0{,}9 \, V(B)$ et $V(B) = 0 + 0{,}9 \, V(A)$. En substituant, $V(A) = 0{,}81 \, V(A)$, donc $V(A) = 0$ et $V(B) = 0$. Le robot fait des allers-retours entre A et B sans jamais atteindre G : il ne reçoit aucune récompense.
2. $Q^\pi(B, \text{droite}) = 1 + 0{,}9 \, V(G) = 1$, puisque G est terminal. Faire une seule fois « droite » en B rapporte 1, contre $V^\pi(B) = 0$ en suivant la politique. Il suffit donc de changer l’action en B pour améliorer nettement la politique. C’est exactement le principe de l’amélioration de politique.

En code

Python

import numpy as np

gamma = 0.9
# Politique : A -> droite (va en B), B -> gauche (va en A). G n'est jamais atteint.
P_pi = np.array([[0.0, 1.0],     # depuis A : B
                 [1.0, 0.0]])    # depuis B : A
R_pi = np.array([0.0, 0.0])      # aucune récompense sur ces transitions

V = np.linalg.solve(np.eye(2) - gamma * P_pi, R_pi)
print(V)                         # [0. 0.]

# Q(B, droite) : on atteint G (terminal, valeur 0) avec la récompense 1
print(1 + gamma * 0)             # 1.0 > V(B) = 0 : changer l'action en B améliore

R

gamma <- 0.9
# Politique : A -> droite (va en B), B -> gauche (va en A). G n'est jamais atteint.
P_pi <- matrix(c(0, 1,
                 1, 0), nrow = 2, byrow = TRUE)
R_pi <- c(0, 0)                    # aucune récompense sur ces transitions

solve(diag(2) - gamma * P_pi, R_pi)   # 0 0

# Q(B, droite) : on atteint G (terminal, valeur 0) avec la récompense 1
1 + gamma * 0                      # 1 > V(B) = 0 : changer l'action en B améliore

Exercice · Vérifier l'optimalité sur le lac

difficile

Au lac gelé non glissant avec $\gamma = 0{,}9$, on admet que $V^*$ vaut 1 sur la case 62 (juste à gauche de G) et 0,9 sur la case 61 (deux cases à gauche de G). La case 54, au-dessus de 62, est un trou.

1. À l’aide de l’équation de Bellman d’optimalité, calculez $Q^*(62, a)$ pour les quatre actions (la case 62 est sur la dernière ligne ; son voisin de gauche est 61, celui de droite est 63).
2. Supposons maintenant le lac glissant : chaque action réussit avec probabilité $1/3$ et dérape vers chacune des deux directions perpendiculaires avec probabilité $1/3$. On garde, pour simplifier, les valeurs $V(61) = 0{,}9$ et $V(62) = 1$. Calculez $Q(62, \text{droite})$ et $Q(62, \text{bas})$. Laquelle de ces deux actions paraît préférable ?

Voir la solution

1. En déterministe, $Q^*(62, a) = R + 0{,}9 \, V^*(s')$ :

   • gauche : arrivée en 61, $Q^* = 0 + 0{,}9 \times 0{,}9 = 0{,}81$ ;
   • bas : on bute contre le bord et on reste en 62, $Q^* = 0 + 0{,}9 \times 1 = 0{,}9$ ;
   • droite : arrivée en G, $Q^* = 1 + 0{,}9 \times 0 = 1$ ;
   • haut : chute dans le trou 54, $Q^* = 0 + 0{,}9 \times 0 = 0$.

   Le maximum vaut 1, pour « droite », ce qui est cohérent avec $V^*(62) = 1$.

2. En glissant :

   • droite : réussite vers G (1), dérapage vers le haut dans le trou (0), dérapage vers le bas qui laisse en 62 ($0{,}9 \times 1$). $Q = \tfrac{1}{3}(1 + 0 + 0{,}9) \approx 0{,}633$.
   • bas : réussite qui laisse en 62 ($0{,}9$), dérapage à gauche vers 61 ($0{,}9 \times 0{,}9 = 0{,}81$), dérapage à droite vers G (1). $Q = \tfrac{1}{3}(0{,}9 + 0{,}81 + 1) \approx 0{,}903$.

   « Bas » devient préférable : il ne peut jamais faire tomber dans le trou, et il atteint G une fois sur trois par dérapage. Ces valeurs ne sont qu’un calcul d’une étape (les vraies valeurs du lac glissant sont différentes), mais elles montrent que la meilleure action dépend des probabilités de transition, et pas seulement de la case visée.

En code

Python

gamma = 0.9
V = {61: 0.9, 62: 1.0, 63: 0.0, 54: 0.0}     # 63 = G et 54 = trou : terminaux
issue = {"gauche": (61, 0), "bas": (62, 0),   # (état d'arrivée, récompense) depuis 62
         "droite": (63, 1), "haut": (54, 0)}

def q(action):
    s_suiv, r = issue[action]
    return r + gamma * V[s_suiv]

# 1. Lac déterministe
print({a: round(q(a), 3) for a in issue})
# {'gauche': 0.81, 'bas': 0.9, 'droite': 1.0, 'haut': 0.0}

# 2. Lac glissant : l'action visée et ses deux perpendiculaires, 1/3 chacune
glisse = {"droite": ["droite", "haut", "bas"], "bas": ["bas", "gauche", "droite"]}
for a, issues in glisse.items():
    print(a, round(sum(q(b) for b in issues) / 3, 3))
# droite 0.633
# bas 0.903

R

gamma <- 0.9
V <- c("61" = 0.9, "62" = 1, "63" = 0, "54" = 0)   # 63 = G et 54 = trou : terminaux
# depuis 62 : état d'arrivée et récompense de chaque direction
arrivee <- c(gauche = "61", bas = "62", droite = "63", haut = "54")
recomp  <- c(gauche = 0, bas = 0, droite = 1, haut = 0)
q <- function(a) recomp[[a]] + gamma * V[[arrivee[[a]]]]

# 1. Lac déterministe
sapply(names(arrivee), q)
# gauche 0.81, bas 0.9, droite 1, haut 0

# 2. Lac glissant : l'action visée et ses deux perpendiculaires, 1/3 chacune
round(mean(sapply(c("droite", "haut", "bas"), q)), 3)     # droite : 0.633
round(mean(sapply(c("bas", "gauche", "droite"), q)), 3)   # bas    : 0.903