FrozenLake RL

Méthodes classiques d’apprentissage par renforcement confrontées à l’optimum exact

Apprentissage par renforcement · oct. 2026 · Terminé

Quatorze méthodes classiques d’apprentissage par renforcement sur FrozenLake, Taxi et CliffWalking, chacune mesurée par rapport à l’optimum exact calculé à partir du modèle.

Dyna-Q optimal en 240 épisodes
4 environnements en grille

Construit avecPythonNumPyGymnasiumPyTorchMatplotlibpytest

Voir le code sur GitHub

Présentation

Les environnements toy-text de Gymnasium sont assez petits pour que la politique optimale se calcule exactement à partir du modèle de transition, ce qui en fait le bon terrain pour vérifier qu’une méthode d’apprentissage fonctionne vraiment, plutôt que de deviner à partir de courbes bruitées. J’ai construit un seul package où chaque méthode classique de Sutton et Barto se lance avec la même commande : itération sur les valeurs et sur les politiques, contrôle Monte Carlo first-visit et every-visit, SARSA, expected SARSA, Q-learning, double Q-learning, SARSA à n pas, SARSA(lambda) et Q(lambda) avec traces d’éligibilité, Dyna-Q, ainsi que DQN et REINFORCE sur des états one-hot.

Toutes les méthodes utilisent le même calendrier d’exploration et les deux mêmes évaluations : un score exact de la politique gloutonne calculé à partir du modèle dans la limite de temps, et 1,000 épisodes réels. Un programme dynamique à horizon fini donne le plafond de chaque environnement, si bien que chaque tableau se lit comme une distance à la meilleure politique possible. Le même code produit les cartes de chaleur des valeurs, les flèches de politique, les courbes d’apprentissage et les animations avant/après.

Les runs confirment le manuel et le chiffrent. Toutes les méthodes atteignent l’optimum sur le lac 4x4 glissant, mais Dyna-Q a besoin de 240 épisodes là où le Monte Carlo every-visit en demande 19,200. Sur le lac 8x8 glissant, Monte Carlo échoue nettement (0.62 et 0.03 de réussite) tandis que les méthodes TD atteignent 0.83-0.88. Sur CliffWalking, Q-learning trouve le chemin à -13 le long du bord et SARSA garde un chemin plus sûr à -17, exactement comme dans l’exemple 6.6 du livre.

La question

Quand le problème est assez petit pour que la politique optimale se calcule à partir du modèle, à quel point chaque méthode classique s’en approche-t-elle, et combien d’épisodes lui faut-il pour y parvenir ?

Fonctionnalités clés

Quatorze méthodes derrière un seul flag --method, regroupées en DP, Monte Carlo, TD, n pas et traces, planification et neuronales, sur six environnements : FrozenLake 4x4 et 8x8 avec et sans glissement, Taxi et CliffWalking.
Évaluation exacte de n’importe quelle politique à partir du modèle de transition P avec la limite de temps, plus une évaluation par rollouts sur 1,000 épisodes qui concorde avec elle à l’erreur Monte Carlo près.
Un plafond DP à horizon fini par environnement (0.744 et 0.913 sur les lacs glissants, 7.93 sur Taxi, -13 sur CliffWalking), pour que chaque résultat se lise comme une distance à l’optimum.
Un Tracker qui note la politique gloutonne en 100 points par run et rapporte le nombre d’épisodes jusqu’à la cible, avec courbes d’apprentissage et retours d’entraînement en ligne.
Cartes de chaleur des valeurs, flèches de politique, tables Q et figure récapitulative pour chaque run ; GIF avant/après rendus à partir des frames rgb_array de Gymnasium, avec les cases visitées marquées.
frozenlake-compare lance n’importe quel groupe de méthodes sur un environnement et écrit le tableau comparatif ; les six suites prennent 12 minutes sur un seul thread CPU.
40 tests pytest et six scripts d’exemple qui suivent l’ordre du livre, plus un notebook Kaggle/Colab qui montre le code de chaque méthode à côté de son run.

Comment ça marche

Exposer le modèle
La table de transition P(s', r | s, a) de chaque environnement est lue une fois depuis Gymnasium. Seuls la programmation dynamique et l’évaluateur exact s’en servent ; les agents qui apprennent ne voient que env.step().
Programmation dynamique
L’itération sur les valeurs applique l’équation d’optimalité de Bellman à tous les états jusqu’à ce que les valeurs ne bougent plus (39 balayages sur le lac 8x8 glissant) ; l’itération sur les politiques alterne évaluation exacte et amélioration gloutonne (8 balayages).
Apprendre à partir d’épisodes
Monte Carlo rapproche Q(s, a) du retour complet ; SARSA, expected SARSA, Q-learning et double Q-learning font du bootstrap à un pas avec leur propre cible ; SARSA à n pas, SARSA(lambda) et Q(lambda) répartissent chaque erreur TD sur les paires récemment visitées ; Dyna-Q rejoue un modèle de comptage appris 10 fois par pas réel.
Versions neuronales
DQN entraîne un Q-network MLP sur des états one-hot avec un replay buffer et un réseau cible ; REINFORCE entraîne une politique softmax avec une baseline de valeur apprise et moyenne 10 épisodes par mise à jour, sans quoi il reste bloqué à 60 % sur le lac 4x4 glissant.
Évaluer exactement, puis pour de vrai
La probabilité de réussite ou le retour espéré de la politique gloutonne est calculé à partir de P dans la limite de temps, puis mesuré à nouveau sur 1,000 épisodes réels ; le premier des 100 points d’évaluation où le score exact atteint la cible donne le nombre d’épisodes jusqu’à la cible.

Exemples

FrozenLake 8x8, glissant, même graine des deux côtés. À gauche : des actions aléatoires tombent dans un trou en quelques pas. À droite : la politique Q-learning (85 % de réussite) zigzague loin des trous, car sur la glace un déplacement peut glisser sur le côté mais jamais vers l’arrière. Les points orange marquent les cases visitées.

Taxi, même graine. À gauche : des actions aléatoires errent pendant 200 pas sans livrer personne (chaque prise en charge ou dépose illégale coûte -10). À droite : le taxi entraîné par Q-learning rejoint le passager, le prend et le dépose à l’hôtel en 15 pas, pour un retour de 6.

CliffWalking, les deux entraînés avec epsilon 0.1. SARSA apprend la valeur de la politique exploratoire et reste loin de la falaise (retour -17) ; Q-learning apprend les valeurs gloutonnes et prend le chemin le plus court le long du bord (-13).

Itération sur les valeurs sur le lac 8x8 glissant, balayage par balayage : la valeur de l’objectif se propage en arrière d’un pas par balayage, et les flèches gloutonnes se stabilisent une fois que les valeurs atteignent le départ.

Tableau récapitulatif des six suites : le score exact final de chaque méthode à côté du plafond de son environnement. Monte Carlo sur le lac 8x8 glissant et les méthodes on-policy sur CliffWalking sont celles qui restent en deçà.

Cartes de chaleur des valeurs et flèches gloutonnes apprises par chaque méthode sur le lac 8x8 glissant. Les politiques TD, Dyna-Q et neuronales ressemblent à celle de l’itération sur les valeurs ; les deux panneaux Monte Carlo, non.

Politiques sur CliffWalking : Q-learning et Dyna-Q longent le bord de la falaise, SARSA, expected SARSA et SARSA(lambda) passent une ou deux lignes plus haut.

Entrée

frozenlake-train --env frozenlake-4x4-slippery --method q-learning

Sortie

runs/frozenlake-4x4-slippery/q-learning/ (agent.npz, summary.json, history.json, run.png): 10,000 episodes in 5.5 s, target reached after 1,400 episodes, exact greedy success 0.740, rollout success 0.729 over 1,000 episodes

Une méthode sur un environnement ; les chiffres sont ceux de la ligne Q-learning du tableau du lac 4x4 glissant, dont le plafond est 0.744.

Stack technique

Python
Tous les algorithmes, l’évaluateur exact et les CLI
NumPy
Tables Q, modèle de transition P et évaluation exacte
Gymnasium
FrozenLake, Taxi et CliffWalking (toy-text) et le rendu rgb_array pour les GIF
PyTorch
DQN et REINFORCE sur des états one-hot
Matplotlib
Cartes de chaleur, flèches de politique, courbes d’apprentissage et tableau récapitulatif
pytest
40 tests, dont la concordance entre évaluation exacte et rollouts

Ce que j’ai appris

Évaluer exactement la politique gloutonne à partir du modèle de transition supprime le bruit des rollouts, et c’est ce qui fait du nombre d’« épisodes jusqu’à la cible » une grandeur mesurable sur un lac glissant
Le contrôle Monte Carlo casse sur les épisodes longs et stochastiques : avec 50-200 pas glissants par retour, le MC every-visit n’apprend jamais de politique 8x8 exploitable, alors que le TD à un pas y parvient

Limites

Une seule graine par run : des écarts de quelques centièmes entre méthodes sur les lacs glissants restent dans le bruit
Taxi et CliffWalking n’ont été lancés qu’avec les méthodes DP, TD et Dyna-Q (10 sur 14)

Mots-clés

apprentissage par renforcement · RL tabulaire · FrozenLake · Taxi · CliffWalking · Gymnasium · programmation dynamique · itération sur les valeurs · itération sur les politiques · contrôle Monte Carlo · SARSA · Q-learning · traces d’éligibilité · Dyna-Q · Sutton et Barto