Module 3 — Fonctions de valeur et équations de Bellman

Un MDP décrit un problème. Le résoudre demande une grandeur qui exprime « à quel point c'est bon d'être ici ». Cette grandeur, c'est la fonction de valeur, et l'outil qui la rend calculable est l'équation de Bellman. Presque tout le renforcement peut se lire comme différentes manières d'estimer ces valeurs.

Deux fonctions, deux points de vue

La fonction de valeur d'état $V^{\pi}(s)$ est le retour attendu si l'agent part de $s$ et suit la politique $\pi$ ensuite :

$$V^{\pi}(s) = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s\right]$$

La fonction de valeur d'action $Q^{\pi}(s, a)$ est le retour attendu si l'agent part de $s$, joue $a$, puis suit $\pi$ :

$$Q^{\pi}(s, a) = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s, a_t = a\right]$$

Les deux sont liées par $V^{\pi}(s) = \sum_a \pi(a \mid s)\, Q^{\pi}(s, a)$. $Q$ est plus riche : elle permet de choisir l'action sans avoir besoin du modèle des transitions. C'est pourquoi le Q-learning, au module 5, l'utilise plutôt que $V$.

L'équation de Bellman d'espérance

Le retour futur, décomposé en « la récompense immédiate plus la valeur du reste », donne l'équation qui porte le nom de Richard Bellman :

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

Lue lentement : la valeur d'un état est la moyenne, pondérée par la politique et par la dynamique, de « ce que je reçois tout de suite plus la valeur actualisée de là où j'atterris ». C'est une équation récursive et un système linéaire — pour $|\mathcal{S}|$ états on a $|\mathcal{S}|$ équations à $|\mathcal{S}|$ inconnues.

L'équivalent pour $Q$ s'écrit :

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

L'équation de Bellman d'optimalité

Pour la politique optimale $\pi^*$, remplacer la moyenne sur les actions par un maximum. La politique optimale ne joue jamais une action sous-optimale — sinon elle ne serait pas optimale.

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

À partir de $Q^*$, la politique optimale s'obtient sans calcul : $\pi^*(s) = \arg\max_a Q^*(s, a)$. C'est la raison profonde pour laquelle apprendre $Q$ suffit à résoudre un MDP.

Un exemple à la main : grille 3×3

Une grille 3×3 avec le départ en $(0, 0)$, un trou en $(1, 1)$ qui donne récompense -1 et termine, et l'objectif en $(2, 2)$ qui donne récompense +1 et termine. Actions déterministes, $\gamma = 0{,}9$, politique uniforme (25 % chaque direction).

En itérant l'équation de Bellman d'espérance à partir de $V_0 = 0$ partout, quelques passages suffisent à obtenir des estimations à 0,01 près. Un état bordant l'objectif reçoit une valeur proche de $0{,}9$ (récompense de 1 dans 25 % des cas plus 0 les autres, actualisée), et un état bordant le trou une valeur négative. La case départ vaut environ $-0{,}05$ sous cette politique — la politique aléatoire perd légèrement en moyenne, ce qui a du sens.

import numpy as np

etats = [(i, j) for i in range(3) for j in range(3)]
actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]        # haut, bas, gauche, droite
gamma = 0.9

def suivant(s, a):
    i, j = s[0] + a[0], s[1] + a[1]
    if 0 <= i < 3 and 0 <= j < 3:
        return (i, j)
    return s                                        # rebond sur les murs

def recompense_et_fin(s):
    if s == (1, 1): return -1.0, True
    if s == (2, 2): return  1.0, True
    return 0.0, False

V = {s: 0.0 for s in etats}
for _ in range(200):                                # iteration de Bellman d'esperance
    V_nouveau = dict(V)
    for s in etats:
        _, termine = recompense_et_fin(s)
        if termine:
            continue
        v = 0.0
        for a in actions:
            s2 = suivant(s, a)
            r, fini = recompense_et_fin(s2)
            v += 0.25 * (r + (0 if fini else gamma * V[s2]))
        V_nouveau[s] = v
    V = V_nouveau

for i in range(3):
    print([round(V[(i, j)], 2) for j in range(3)])

Ce que Bellman ne donne pas

Deux limites qui motivent tout le reste du cours.

Le système de Bellman exige la dynamique $P$. Dans une simulation on l'a, dans la vraie vie presque jamais. Les modules 4 à 8 remplacent ce système par des méthodes qui n'apprennent qu'à partir d'échantillons.

L'équation d'optimalité n'est plus linéaire à cause du max. Elle ne se résout plus par inversion de matrice ; il faut itérer. Le module suivant montre deux façons de le faire quand $P$ est connu (programmation dynamique), et une troisième quand il ne l'est pas (Monte-Carlo).

Comment interpréter une fonction Q apprise

Deux vérifications rapides sur un $Q$ appris : $\max_a Q(s, a) \approx V(s)$, et $\arg\max_a Q(s, a)$ correspond à une action que vous jugez sensée dans les états où vous avez une intuition. Un $Q$ qui donne des valeurs cohérentes mais un argmax absurde signale souvent une exploration insuffisante — l'agent n'a jamais visité l'action qu'il devrait choisir.

En résumé

• $V^{\pi}(s)$ est le retour attendu à partir de $s$ ; $Q^{\pi}(s, a)$ le retour attendu en jouant $a$ d'abord.
• L'équation de Bellman d'espérance est un système linéaire ; celle d'optimalité contient un max et exige l'itération.
• Connaître $Q^*$ suffit à extraire la politique optimale par $\arg\max$, sans avoir besoin du modèle.
• Résoudre Bellman à la main exige la dynamique $P$ ; le reste du cours s'en passe grâce aux échantillons.

Module suivant : deux familles de solveurs, la programmation dynamique quand on a $P$, et Monte-Carlo quand on ne l'a pas.