Module 2 — Processus de décision markoviens

Le module précédent a décrit la boucle d'interaction en mots. Pour la calculer, il faut un objet mathématique : le processus de décision markovien, ou MDP. C'est le squelette formel sur lequel tout le reste du cours vient s'articuler.

Les cinq éléments d'un MDP

Un MDP est défini par le tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$.

L'espace des états $\mathcal{S}$ décrit toutes les situations possibles. Sur FrozenLake 4×4, il contient 16 cases numérotées de 0 à 15. Sur CartPole, il est continu et de dimension 4 (position, vitesse, angle, vitesse angulaire).

L'espace des actions $\mathcal{A}$ décrit ce que l'agent peut faire. Il peut être discret (les 4 mouvements gauche, bas, droite, haut de FrozenLake) ou continu (la poussée réelle d'un moteur, entre -1 et 1).

Les probabilités de transition $P(s' \mid s, a)$ décrivent la dynamique : la probabilité de se retrouver dans l'état $s'$ après avoir joué $a$ dans l'état $s$. C'est la seule chose que la nature contrôle et que l'agent ne peut qu'observer.

La fonction de récompense $R(s, a, s')$ associe une valeur numérique à chaque transition. Elle peut être déterministe ou aléatoire ; ce qui compte est son espérance.

Le facteur d'actualisation $\gamma$ complète le tuple, comme vu au module 1.

L'hypothèse de Markov, mot pour mot

L'hypothèse cruciale est la suivante :

$$P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t)$$

L'état actuel contient toute l'information utile pour prédire le prochain. Le passé, une fois cet état donné, n'ajoute rien. C'est ce qui rend le problème calculable : l'agent n'a pas à mémoriser une trajectoire, il n'a qu'à lire l'état courant.

Cette hypothèse est forte, et elle n'est pas toujours vraie du monde. Elle l'est du monde tel qu'on l'a modélisé. Choisir la représentation d'état, c'est décider ce qu'on met dedans pour que l'hypothèse tienne.

Quand Markov est violé

Trois cas classiques d'observation partielle, qui rendent le problème réellement non markovien.

Dans Pong, une image seule ne dit rien du sens du mouvement de la balle : il faut au moins deux images consécutives, ou empiler quatre images comme dans le DQN original, pour reconstituer la vitesse. Un état à une seule image viole Markov.

Dans un environnement de navigation partiellement visible (un labyrinthe où l'agent ne voit qu'une case autour de lui), deux positions différentes peuvent produire la même observation. La politique optimale peut alors dépendre du passé.

Dans un jeu à information cachée (le poker, une réserve d'énergie qui n'apparaît pas dans les capteurs), l'état observable ne suffit pas.

La solution générale est le POMDP — un MDP dont l'agent ne voit qu'une observation, pas l'état réel. En pratique, on empile des observations récentes, ou on utilise un LSTM qui construit un état résumé.

FrozenLake formalisé

Prenons FrozenLake, l'environnement fil rouge des cinq prochains modules.

Élément	Valeur
$\mathcal{S}$	16 cases : départ (0), gel (F), trou (H), objectif (15)
$\mathcal{A}$	4 actions : gauche (0), bas (1), droite (2), haut (3)
$P$	Déterministe en is_slippery=False, aléatoire sinon
$R$	+1 en arrivant sur l'objectif, 0 sinon
$\gamma$	Choix de l'expérience, typiquement 0,99

En mode glissant, une action « droite » a une probabilité de 1/3 de vraiment aller à droite, et 1/3 en haut, 1/3 en bas. C'est cette stochasticité qui rend l'environnement intéressant : la politique optimale doit prévoir de glisser.

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
print("Nombre d'etats :", env.observation_space.n)
print("Nombre d'actions :", env.action_space.n)

# La table interne P[s][a] donne les transitions : [(proba, s_suivant, r, termine), ...]
transitions = env.unwrapped.P[6][2]                # de la case 6, action "droite"
for proba, s_suivant, recompense, termine in transitions:
    print(f"  proba={proba:.2f}  -> case {s_suivant}  r={recompense}  fini={termine}")

Politique et objectif du renforcement

Une politique $\pi(a \mid s)$ est une distribution sur les actions étant donné un état. L'objectif de tout algorithme de renforcement est de trouver une politique optimale $\pi^*$ qui maximise l'espérance du retour :

$$\pi^* = \arg\max_{\pi} \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^t r_{t+1}\right]$$

L'espérance porte sur la distribution des trajectoires induite par $\pi$ et par $P$. Le module suivant introduit les fonctions de valeur, qui rendent cette espérance calculable au lieu de rester une définition.

Vérifier avant d'entraîner

Avant tout algorithme, écrire à la main le tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ de la tâche visée. Une confusion à ce stade — une action absente, un état qui viole Markov, une récompense mal placée — coûte des semaines de tâtonnements algorithmiques qui n'y changeront rien.

En résumé

• Un MDP est le tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ ; c'est le squelette formel de tout problème de renforcement.
• L'hypothèse de Markov dit que l'état courant contient toute l'information utile ; le passé n'ajoute rien.
• Elle est violée dès qu'une seule observation ne suffit pas : cadrage partiel, empilement d'images ou LSTM sont les remèdes usuels.
• FrozenLake en mode glissant a une dynamique stochastique — la politique optimale doit prévoir de glisser.

Module suivant : les fonctions de valeur et les équations de Bellman, qui transforment l'espérance ci-dessus en un système d'équations résolvable.