Module 4 — Programmation dynamique et méthodes de Monte-Carlo

Deux familles d'algorithmes vivent aux extrêmes du spectre. La programmation dynamique exige de connaître entièrement la dynamique de l'environnement ; Monte-Carlo n'exige rien de plus qu'un simulateur. Comprendre ces deux extrêmes, c'est comprendre le compromis que toutes les méthodes intermédiaires — dont le Q-learning du module 5 — cherchent à équilibrer.

Programmation dynamique : quand $P$ est connu

La programmation dynamique itère les équations de Bellman jusqu'au point fixe. Deux algorithmes principaux, subtilement différents.

Itération de la valeur

Le plus simple. Partir de $V_0 = 0$ et appliquer l'équation d'optimalité comme mise à jour :

V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s' \mid s, a) \left[R(s, a, s') + \gamma\, V_k(s')\right]

La suite $V_k$ converge vers $V^*$ à vitesse géométrique en $\gamma$ . Après convergence, on extrait la politique optimale par $\arg\max$ .

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
P = env.unwrapped.P                                 # dictionnaire P[s][a] = [(proba, s', r, fini), ...]
nS, nA = env.observation_space.n, env.action_space.n
gamma = 0.99

V = np.zeros(nS)
for _ in range(1000):
    V_nouveau = np.zeros(nS)
    for s in range(nS):
        V_nouveau[s] = max(
            sum(p * (r + gamma * V[s2] * (0 if fini else 1)) for p, s2, r, fini in P[s][a])
            for a in range(nA)
        )
    if np.max(np.abs(V_nouveau - V)) < 1e-8:
        break
    V = V_nouveau

politique = np.array([
    np.argmax([
        sum(p * (r + gamma * V[s2] * (0 if fini else 1)) for p, s2, r, fini in P[s][a])
        for a in range(nA)
    ])
    for s in range(nS)
])

Itération de la politique

Alterne deux phases. Évaluation : résoudre l'équation d'espérance pour la politique courante (par inversion ou itération). Amélioration : passer à la politique gloutonne par rapport aux valeurs obtenues. La convergence est plus rapide en nombre d'itérations mais chaque itération coûte plus cher. Sur FrozenLake, itération de la valeur suffit ; sur des MDP plus grands, itération de la politique reprend l'avantage.

Les limites de la programmation dynamique

Deux plafonds dur, qui font de la DP un outil de laboratoire plus qu'un algorithme de production.

Le modèle $P$ est presque toujours absent. Un jeu, un robot, un marché : personne n'a écrit la fonction de transition. On observe seulement des échantillons.

La malédiction de la dimension. Le calcul balaie tous les états à chaque itération. Sur un MDP dérivé d'un jeu vidéo, $|\mathcal{S}|$ peut valoir $10^{20}$ ; itérer devient impossible avant même de manquer de mémoire.

D'où le besoin de méthodes qui apprennent à partir d'expériences réelles ou simulées, sans balayer l'espace et sans exiger $P$ .

Monte-Carlo : apprendre des trajectoires complètes

L'idée : estimer $V^{\pi}(s)$ ou $Q^{\pi}(s, a)$ par la moyenne des retours effectivement observés à partir de $s$ (ou $(s, a)$ ) dans des épisodes joués sous $\pi$ .

L'algorithme le plus simple, Monte-Carlo à premier passage :

Pour chaque episode joue sous pi :
    Calculer G_t = r_{t+1} + gamma*r_{t+2} + ... pour chaque t
    Pour chaque (s, a) rencontre pour la premiere fois dans l'episode :
        Ajouter G_t a la liste des retours de (s, a)
        Q(s, a) = moyenne de cette liste

Un pseudocode Python compact pour le contrôle Monte-Carlo :

import numpy as np
from collections import defaultdict

Q = defaultdict(lambda: np.zeros(nA))
retours = defaultdict(list)

for episode in range(50_000):
    trajectoire = jouer_un_episode(pi_epsilon_greedy(Q, epsilon=0.1))
    G = 0.0
    deja_vus = set()
    for s, a, r in reversed(trajectoire):
        G = r + gamma * G                            # calcul en arriere pour reutiliser G
        if (s, a) not in deja_vus:
            deja_vus.add((s, a))
            retours[(s, a)].append(G)
            Q[s][a] = np.mean(retours[(s, a)])

Trois points essentiels. Rien dans l'algorithme ne connaît $P$ — il ne voit que des transitions échantillonnées. Il attend la fin de l'épisode pour mettre à jour, ce qui l'exclut des tâches infinies. Et sa variance est très élevée : un retour dépend de toute la trajectoire suivante, donc de nombreuses actions aléatoires.

La variance de Monte-Carlo

L'estimateur Monte-Carlo est non biaisé : sa moyenne, sur un nombre infini d'épisodes, est exactement $V^{\pi}(s)$ . Mais sa variance peut être énorme, parce que $G_t$ est une somme de nombreuses récompenses actualisées, chacune bruitée.

C'est ce qui motive la différence temporelle du module suivant : mettre à jour à partir d'une seule transition en utilisant une estimation existante à la place du reste de la trajectoire. On échange un peu de biais contre beaucoup moins de variance.

Le piège de la politique déterministe

Monte-Carlo exige que chaque paire $(s, a)$ soit visitée « suffisamment souvent ». Avec une politique déterministe et gloutonne, la plupart des paires ne sont jamais explorées et leur $Q$ reste à zéro. C'est pourquoi Monte-Carlo se combine toujours avec une politique $\varepsilon$ -gloutonne (module 6), ou avec l'astuce des « débuts exploratoires » : forcer un premier couple $(s, a)$ aléatoire au démarrage de chaque épisode.

Ce qu'il faut retenir des deux extrêmes

	Programmation dynamique	Monte-Carlo
Connaît $P$ ?	Oui, requis	Non, pas nécessaire
Balaie tous les états ?	Oui	Non, seulement ceux visités
Attend la fin de l'épisode ?	Non	Oui
Biais	Nul (mise à jour exacte)	Nul en espérance
Variance	Nulle	Élevée
Tâches infinies	Applicable	Non applicable

Le module 5 introduit la différence temporelle, qui se place entre les deux : elle utilise des échantillons comme Monte-Carlo, mais met à jour à chaque pas comme la DP.

En résumé

La DP (itération de la valeur ou de la politique) résout un MDP quand $P$ est connu et l'espace d'états assez petit pour être balayé.
Monte-Carlo apprend à partir de trajectoires complètes sans connaître $P$ ; il est non biaisé mais à forte variance.
Monte-Carlo ne peut pas mettre à jour avant la fin d'un épisode, ce qui l'exclut des tâches infinies ou très longues.
L'exploration reste indispensable même sans modèle : une politique gloutonne pure sous Monte-Carlo laisse la plupart des paires $(s, a)$ inexplorées.

Module suivant : la différence temporelle et le Q-learning, l'algorithme central du renforcement tabulaire.

Programmation dynamique : quand PPP est connu​

Itération de la valeur​

Itération de la politique​

Les limites de la programmation dynamique​

Monte-Carlo : apprendre des trajectoires complètes​

La variance de Monte-Carlo​

Ce qu'il faut retenir des deux extrêmes​

En résumé​