Processus de décision markoviens : états, actions, récompenses et équations de Bellman

Un MDP sur un monde en grille avec une falaise, le retour et l’actualisation, la fonction de valeur et l’équation de Bellman, l’itération sur les valeurs et l’itération sur les politiques écrites de zéro, comment l’actualisation, le glissement et le coût d’un pas changent le comportement optimal, et un contrôle par simulation.

11 minutes Matěj Žalmánek 2026-10-16

Série Bases de l’IA Partie 47 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Jusqu’ici, les modèles de cette série apprenaient à partir d’exemples accompagnés de la bonne réponse, ou cherchaient une structure dans les données. L’apprentissage par renforcement est une troisième voie : un agent agit, le monde lui donne en retour des récompenses et des punitions, et l’agent doit découvrir comment agir pour en récolter le plus possible. Avant de passer à l’apprentissage, il nous faut un langage pour décrire précisément une telle tâche. Ce langage, c’est le processus de décision markovien. Dans cette partie, nous le construisons sur un petit monde avec une falaise et calculons exactement le meilleur comportement — en supposant que nous connaissons les règles du monde.

Elle fait suite aux parties Chaînes de Markov, Espérance, variance et covariance et Types d’apprentissage automatique.

1. Agent, environnement, récompense

Définition — processus de décision markovien (MDP)

Un MDP est un quintuplet (S, A, P, R, γ) : un ensemble d’états S, un ensemble d’actions A, des probabilités de transition P(s′ | s, a), une récompense R(s, a, s′) et un facteur d’actualisation γ ∈ [0, 1). À chaque pas, l’agent dans l’état s choisit une action a, le monde le déplace aléatoirement selon P vers s′ et l’agent reçoit une récompense. Propriété de Markov : l’état suivant ne dépend que de l’état actuel et de l’action, pas de l’historique.

Notre monde est une grille 6 × 5. L’agent part de la gauche (S) et peut aller vers le haut, vers la droite, vers le bas ou vers la gauche. Toute la rangée du bas est une falaise : qui y tombe reçoit −10 et la partie s’arrête. Non loin du départ se trouve un petit but valant +1, loin à droite un grand but valant +10. Deux murs ferment le chemin court par le haut. Et le sol peut être glissant : avec une probabilité p, l’agent glisse, au lieu de la direction voulue, dans l’une des deux directions perpendiculaires.

P(s′ | s, a) = (1 − p) · [s′ = pas dans la direction a] + p/2 · [s′ = pas perpendiculaire à gauche] + p/2 · [s′ = pas perpendiculaire à droite]

P(s′ | s, a)

avec quelle probabilité l’agent finit sur la case s′ après l’action a — toute la distribution, pas seulement « où il est censé aller », car la valeur d’un coup sera calculée comme une moyenne sur tous les points d’arrivée possibles

(1 − p) · […]

le mouvement voulu — il reçoit l’essentiel de la probabilité ; avec p = 0 il ne reste que ce terme et le monde est déterministe

p/2 · […]

la glissade sur le côté, à parts égales vers la gauche et vers la droite — c’est elle qui rend dangereuse la case voisine de la falaise, même quand on longe la falaise au lieu d’y aller

Exemple — un pas vers la droite le long de la falaise

L’agent se trouve sur la case à droite du départ (au-dessus de lui un mur, en dessous la falaise) et choisit « droite », p = 0,2 :

• 0,8 — la case suivante à droite,
• 0,1 — la falaise (récompense −10, fin),
• 0,1 — la case à droite du départ (glisse vers le haut contre le mur et reste sur place),

au total 0,8 + 0,1 + 0,1 = 1. La récompense immédiate espérée de ce coup est 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1 : en moyenne, un tel pas sur dix se termine par une chute.

2. Retour, actualisation et politique

Définition — retour et politique

Le retour (gain) à partir de l’instant t est la somme actualisée des récompenses futures G_t = r_t+1 + γ r_t+2 + γ² r_t+3 + …. Une politique (policy) π indique quelle action choisir dans quel état — de façon déterministe π(s) = a, ou comme une distribution π(a | s). Le but est la politique au plus grand retour espéré.

G_t = r_t+1 + γ · G_t+1

G_t

le retour de maintenant jusqu’à la fin — le nombre que l’agent veut rendre aussi grand que possible

r_t+1

la récompense du tout prochain pas — la seule qu’il reçoit sans attendre, donc sans actualisation

γ

l’actualisation — tout ce qui vient plus tard est déprécié d’un facteur γ ; c’est ainsi que « plus tard » devient « moins »

G_t+1

le retour à partir du pas suivant — la même grandeur un pas plus loin ; une récursion d’où va bientôt naître l’équation de Bellman

Théorème — avec γ < 1, le retour est toujours fini

Si chaque récompense est au plus R_max en valeur absolue, alors |G_t| ≤ R_max (1 + γ + γ² + …) = R_max / (1 − γ), même si l’épisode ne se termine jamais.

Démonstration. L’inégalité triangulaire donne |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k, et la série géométrique de raison 0 ≤ γ < 1 a pour somme 1/(1 − γ). ∎

Chez nous, R_max = 10 et γ = 0,9, donc |G| ≤ 10 / 0,1 = 100. Sans coût par pas, c’est même beaucoup moins : seule l’entrée dans un but ou dans la falaise donne une récompense non nulle, et au plus une fois par épisode, donc |G| ≤ 10. C’est pourquoi γ = 1 n’est utilisable que là où l’épisode se termine à coup sûr.

Exemple — le retour du plus court chemin vers le grand but

Sur un sol ferme, le plus court chemin vers le but +10 compte 6 pas. Les cinq premiers pas rapportent 0, le sixième (l’entrée dans le but) +10. Avec γ = 0,9 :

G₀ = 0 + 0,9 · 0 + 0,9² · 0 + 0,9³ · 0 + 0,9⁴ · 0 + 0,9⁵ · 10 = 0,59049 · 10 = 5,9049.

Sur un sol ferme, rien d’aléatoire ne se produit, c’est donc directement la valeur du départ — et le calcul par itération sur les valeurs dans la section sur les politiques donne effectivement 5,90. Le petit but +1, même atteint en 3 pas, ne donnerait que 0,9² · 1 = 0,81.

3. Valeur et équations de Bellman

Définition — fonction de valeur et équation d’optimalité de Bellman

La valeur d’un état sous la politique π est le retour espéré quand l’agent part de s et suit π : V^π(s) = E_π[G_t | s_t = s]. La valeur d’une action Q^π(s, a) est la même chose quand nous fixons nous-mêmes la première action. Les valeurs optimales satisfont l’équation de Bellman (Richard Bellman, 1957) :

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)],

et la politique optimale est π*(s) = argmax_a Q*(s, a), où Q*(s, a) est l’expression à l’intérieur du maximum.

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)]

V*(s)

le meilleur retour espéré depuis la case s — ce que nous cherchons ; il figure des deux côtés, l’équation est donc une condition que toutes les valeurs doivent satisfaire à la fois

max_a

le choix de l’agent — c’est lui qui choisit l’action, il prend donc la meilleure ; c’est ici que l’équation « d’optimalité » diffère de l’équation pour une politique fixe π, où π(s) remplace le maximum

∑_s′ P(s′ | s, a) […]

la moyenne sur les endroits où le monde envoie réellement l’agent — l’agent n’en décide pas, d’où une espérance et non un maximum

R(s, a, s′)

la récompense immédiate pour cette transition (+1, +10, −10 ou le coût d’un pas)

γ

l’actualisation — l’avenir est un pas plus loin, d’où un facteur γ (comme dans la formule G_t = r_t+1 + γ G_t+1)

V*(s′)

le meilleur retour depuis le point d’arrivée — tout l’avenir résumé en un seul nombre, si bien qu’il n’est pas nécessaire de parcourir tous les longs chemins

Exemple — l’équation de Bellman au départ (glissement 20 %, γ = 0,9)

Valeurs optimales déjà calculées des voisins du départ : case au-dessus du départ V* = 3,325, case à droite V* = 2,260, le départ lui-même V* = 2,854 ; la falaise est terminale (valeur 0, récompense −10). Nous remplaçons dans le membre de droite pour chaque action :

• ↑ : 0,8 · (0 + 0,9 · 3,325) + 0,1 · (0 + 0,9 · 2,260) + 0,1 · (0 + 0,9 · 2,854) = 2,854,
• → : 0,8 · (0 + 0,9 · 2,260) + 0,1 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 3,325) = 0,926,
• ↓ : 0,8 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 2,260) = −7,540,
• ← : 0,8 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 3,325) + 0,1 · (−10 + 0,9 · 0,000) = 1,354,

La plus grande est ↑ avec 2,854, et c’est exactement V*(départ) — l’équation est vérifiée (l’écart sur le dernier chiffre vient de l’arrondi). L’action « haut » vaut quelque chose malgré 10 % de chances que l’agent glisse vers la gauche, heurte le bord et reste au départ : c’est pourquoi V*(départ) apparaît aussi à droite. L’action « bas » mène à 80 % dans la falaise et donne une valeur très négative.

4. Itération sur les valeurs

Définition — itération sur les valeurs

Pars de V₀ = 0 et répète pour tous les états V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R + γ V_k(s′)], tant que les valeurs changent. Pour γ < 1, l’opérateur de Bellman est une contraction : max_s |V_k+1 − V*| ≤ γ · max_s |V_k − V*|, l’erreur décroît donc au moins comme γ^k.

# itération sur les valeurs
V = 0 dans tous les états
répéter :
    pour chaque état non terminal s :
        pour chaque action a :
            Q[a] = ∑ sur s′ ( P(s′ | s, a) · (R(s, a, s′) + γ · V(s′)) )
        V_nouveau(s) = max(Q)
    variation = max sur s |V_nouveau(s) − V(s)|
    V = V_nouveau
jusqu’à ce que variation < 10⁻⁶
π(s) = action au plus grand Q[a] (calculé à partir du V final)

Exemple — les trois premiers tours (glissement 20 %, γ = 0,9)

Nous suivons deux cases de la rangée du milieu : A juste à gauche du grand but +10 et B une case plus loin, juste à droite du petit but +1. Au-dessus de B il y a un mur, au-dessus de A c’est libre, en dessous des deux un sol ordinaire.

tour k	Vk(A)	meilleure action en A	Vk(B)	meilleure action en B
1	8,000	→	0,800	←
2	8,000	→	5,832	→
3	9,166	→	6,343	→

Tour 1 (partout V₀ = 0) : depuis A, un pas vers la droite mène au but avec une probabilité de 0,8, soit 0,8 · 10 = 8,000. Depuis B, on ne voit encore rien de lointain ; le mieux est un pas vers la gauche, vers le petit but : 0,8 · 1 = 0,800.

Tour 2 : depuis B, vers la droite, on arrive en A, qui a déjà la valeur 8 : 0,8 · 0,9 · 8 = 5,76, plus 0,1 · 0,9 · 0,8 = 0,072 pour la glissade vers le haut (mur, il reste en B avec V₁ = 0,8) et 0 pour la glissade vers le bas — au total 5,832. La meilleure action en B a basculé de ← à → : l’information sur le grand but a avancé d’une case.

max_s |V_k+1(s) − V_k(s)| ≤ γ^k · max_s |V₁(s) − V₀(s)|

max |V_k+1 − V_k|

la plus grande variation au tour k + 1 — ce que le calcul surveille et ce qui décide de son arrêt ; dans le graphique ci-dessous, la courbe verte (γ = 0,9) et la bleue (γ = 0,99)

γ^k

chaque tour réduit l’écart entre deux estimations d’au moins un facteur γ (contraction) ; après k tours, donc d’un facteur γ^k — d’où la convergence lente pour γ proche de 1

max |V₁ − V₀|

la taille de la première variation ; avec V₀ = 0, c’est la plus grande récompense espérée en un pas, au plus 10 chez nous — d’où la borne en pointillés 10 · γ^k dans le graphique

Avec γ = 0,9, les valeurs se stabilisent (variation inférieure à 10⁻⁶) après 50 itérations, avec γ = 0,99 après 77. L’erreur décroît plus vite que ne le garantit la borne γ^k — celle-ci vaut toujours, mais pour un monde concret elle est souvent pessimiste. Plus γ est proche de un, plus l’information doit se propager loin dans l’avenir et plus le calcul est long.

5. Ce que changent l’actualisation, le glissement et le coût d’un pas

Venons-en au plus intéressant. Le même monde, seulement d’autres réglages — et la politique optimale est complètement différente.

Sur un sol ferme, le plus court chemin vers le grand but longe de près la falaise : 6 pas et une valeur du départ de 5,90. Quand le sol est glissant, le bord de la falaise est dangereux — chaque pas y signifie 10 % de risque de chute. La politique optimale contourne donc les murs par le haut : 10 pas au lieu de 6, mais seuls 0,7 % des épisodes finissent dans la falaise. Si nous utilisions sur sol glissant la politique risquée, l’agent tomberait dans 30 % des cas et la valeur du départ descendrait à 0,64 au lieu de 2,85.

Avec γ = 0,5, le grand but est si loin qu’il n’en vaut pas la peine — +10 dans 10 pas ne pèse aujourd’hui que 10 · 0,5¹⁰ ≈ 0,01. L’agent va prudemment par le haut vers le petit but. Quand, à l’inverse, chaque pas coûte −1, prendre des risques devient payant : l’agent va vers le grand but par le bord de la falaise et tombe dans 27 % des épisodes. Le long chemin sûr lui coûterait davantage que la perte moyenne due aux chutes.

La colonne « simulation » est un contrôle : le retour moyen sur 10 000 épisodes suivant la politique trouvée, avec un glissement aléatoire. Le retour moyen ne s’écarte de la valeur calculée du départ que de quelques centièmes au plus — l’équation de Bellman calcule bel et bien le retour espéré.

La leçon pour les applications réelles : le comportement d’un agent n’est pas déterminé seulement par « ce qu’est le but », mais aussi par des détails comme l’actualisation et le coût d’un pas. Qui conçoit les récompenses conçoit le comportement — y compris celui qu’il ne voulait pas.

6. Itération sur les politiques

Définition — itération sur les politiques

L’itération sur les politiques (Ronald Howard, 1960) alterne deux étapes. Évaluation : pour une politique fixe π, calcule V^π en résolvant le système V^π(s) = ∑_s′ P(s′ | s, π(s)) [R + γ V^π(s′)]. Amélioration : dans chaque état, choisis l’action de plus grande valeur selon V^π. Quand la politique cesse de changer, elle est optimale.

# itération sur les politiques
π = « partout vers le haut »
répéter :
    # évaluation : V^π en résolvant le système (ici par substitution répétée)
    V = 0
    répéter tant que V change de plus de 10⁻⁹ :
        V(s) = ∑ sur s′ ( P(s′ | s, π(s)) · (R + γ · V(s′)) )   pour chaque s
    # amélioration : dans chaque état, la meilleure action selon V^π
    π_nouvelle(s) = argmax sur a  ∑ sur s′ ( P(s′ | s, a) · (R + γ · V(s′)) )
    modifiés = nombre d’états où π_nouvelle(s) ≠ π(s)
    π = π_nouvelle
jusqu’à ce que modifiés = 0

Théorème — d’amélioration de la politique

Si la nouvelle politique π′ choisit dans chaque état l’action de plus grand Q^π(s, a), alors V^π′(s) ≥ V^π(s) dans tous les états. Si π′ ne diffère pas de π, V^π satisfait l’équation d’optimalité de Bellman, et π est donc optimale.

Esquisse de démonstration. Par le choix de π′, V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. Dans V^π(s′), nous substituons la même inégalité, puis encore… Une fois tout déroulé, il reste le retour espéré de la politique qui joue π′ à tous les pas, c’est-à-dire V^π′(s). ∎

Les politiques déterministes sont en nombre fini — chez nous, 4 actions sur 19 cases non terminales, soit 4¹⁹ ≈ 2,7 · 10¹¹. Aucune ne peut se répéter (chaque tour améliore la valeur ou s’arrête), l’itération sur les politiques se termine donc toujours. En pratique, il faut étonnamment peu de tours : chez nous, 6.

Sur sol glissant avec γ = 0,9, en partant de la politique « partout vers le haut » :

Après 6 tours, la politique est la même que celle de l’itération sur les valeurs. Les tours sont peu nombreux, mais chacun contient une évaluation complète (chez nous, des dizaines à des centaines de passages sur le monde). Laquelle des deux méthodes est la plus rapide dépend du problème ; en pratique, on les combine.

7. Quand on ne connaît pas les règles du monde

Tout ce qui précède suppose que nous connaissons P et R — que nous pouvons « regarder dans les règles ». C’est de la planification (programmation dynamique). Dans l’apprentissage par renforcement véritable, l’agent est jeté dans un monde dont il ignore les règles : il doit essayer, accumuler de l’expérience et en estimer les valeurs. L’équation de Bellman reste pourtant le cœur de presque toutes les méthodes — simplement, au lieu de la moyenne exacte sur P, on utilise un échantillon tiré d’un seul pas réel. C’est le Q-learning, sujet de la prochaine partie.

Le même cadre décrit un robot qui apprend à marcher, la gestion des stocks d’un entrepôt, un système de recommandation et aussi un modèle de langage entraîné à partir de préférences humaines dans la partie sur le RLHF — l’état y est le texte écrit jusque-là, l’action le jeton suivant et la récompense l’évaluation de la réponse.

8. Résumé

• MDP = états, actions, transitions aléatoires, récompenses et actualisation ; l’état suivant ne dépend que de l’état actuel et de l’action.
• La valeur d’un état est le retour actualisé espéré ; les valeurs optimales satisfont l’équation de Bellman.
• L’itération sur les valeurs répète l’équation de Bellman ; l’erreur décroît au moins comme γ^k (chez nous, 50 itérations pour γ = 0,9).
• Le glissement éloigne le chemin de la falaise (chute dans 0,7 % des cas au lieu de 30 %), un petit γ mène au petit but proche, un coût par pas à la prise de risque.
• L’itération sur les politiques alterne évaluation et amélioration ; chez nous, 6 tours.
• Sans connaître les règles du monde, les valeurs doivent être apprises par l’expérience — c’est l’apprentissage par renforcement.

Envie de mettre la main à la pâte ? Demandez à un agent d’IA de programmer ce monde avec sa falaise et d’y faire varier interactivement γ, le glissement et le coût d’un pas — et observez à quel moment la politique « bascule » d’un chemin à un autre.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.