Série : Reinforcement Learning | Notebook : 14/18 | Durée estimée : ~50 min
Navigation : RL-1 CartPole | RL-5 Tabulaire | RL-14 | RL-13 Curiosite | RL-16 Dream-RSI
L’abstraction temporelle répond à cela : au lieu d’une action haut, l’agent choisit une option — un macro-comportement « aller à la porte Ouest », « atteindre le but ». Une option est une politique qui s’exécute jusqu’à sa condition de fin, et l’agent n’a à apprendre que la séquence de ces macro-actions. C’est le Option framework de Sutton, Precup & Singh (1999), la brique qui relie les MDP « plats » au RL hiérarchique (et, en passant, aux skills des agents modernes).
Objectif de ce notebook : implémenter le framework depuis zéro sur un gridworld quatre-pièces, et mesurer — pas affirmer — le gain de l’abstraction temporelle, en ≥4 seeds, avec un verdict honnête.
Prérequis : numpy, matplotlib. Bases de Q-learning (notebook 5) et de SGD/politique (notebook 6). Durée : ~50 min.
Le problème RL standard cherche Q(s, a) pour l’action primaire a. Deux obstacles apparaissent dès que l’horizon s’allonge :
L’option framework pose un MDP semi-markovien (SMDP) : l’agent raisonne sur les options o ∈ O, chacune définie par un triplet (I_o, π_o, β_o) :
I_o — ensemble d’initiation : les états où l’option peut être choisie ;π_o(s, a) — la politique intra-option : comment agir une fois l’option lancée ;β_o(s) — la condition de fin : probabilité de terminer l’option en s.Exécuter une option ne fait pas un pas mais une séquence jusqu’à β. La transition SMDP porte donc (s, o) → (s', τ, r) : s' l’état d’arrivée, τ la durée, r la récompense accumulée. On apprend Q(s, o) par l’équation de Bellman au pas de l’option :
Q(s, o) ← Q(s, o) + α [ r + γ^τ · max_{o'} Q(s', o') − Q(s, o) ]L’état s dans la mise à jour est l’état où l’option a été CHOISIE, pas l’état d’arrivée s' : c’est le petit piège que ce notebook met en évidence. Le choix de haut niveau se fait sur 5 options (les portes + le but) au lieu de 4 actions primaires sur un très long horizon. C’est ce qu’on va mesurer — honnêtement, quitte à conclure qu’ici le gain est une case limite (des macros parfaites offertes résolvent le problème sans apprentissage), ce qui prépare l’intra-option learning, le vrai contenu d’apprentissage du framework.
Un couloir en forme de + sépare une grille 15×15 en quatre pièces. Les murs sont intérieurs (#), les portes sont les trous dans les murs : la grille est coupée par une barre verticale (colonnes 7) et une barre horizontale (ligne 7), chacune percée de deux portes. L’agent part en haut-gauche (1,1) et doit atteindre le coin en bas-droite (13,13) — deux portes à franchir, donc un long chemin minimal.
# # #
# HAUT # HAUT #
# GAUCHE # DROIT #
# # #
# # # # # # # # # # # # # # # #
# # #
# BAS # BAS #
# GAUCHE # DROIT (G) #
# # #(ligne, colonne).On compare deux apprenants à budget identique (même nombre d’épisodes) :
| Apprenant | Actions | Horizon du choix | Ce qu’il doit apprendre |
|---|---|---|---|
Flat (rl_5 Q-learning) |
4 primitives | chaque pas | toute la séquence de pas |
| Options | 5 options (portes + but) | chaque option | la séquence de portes |
numpy 2.4.2
matplotlib 3.10.8class FourRooms:
"""Gridworld 15x15 quatre-pièces, but éloigné, récompense -1/pas +20 au but."""
SIZE = 15
WALL = 7 # ligne/colonne des murs intérieurs
DOORS = (3, 11) # positions des portes (dans la verticale ET l'horizontale)
ACTIONS = ["U", "D", "L", "R"]
DELTA_LIST = [(-1, 0), (1, 0), (0, -1), (0, 1)] # action = index 0..3
DOORS_V = [(3, 7), (11, 7)] # portes de la barre verticale (c=7)
DOORS_H = [(7, 3), (7, 11)] # portes de la barre horizontale (r=7)
ALL_DOORS = DOORS_V + DOORS_H
def __init__(self, goal=(13, 13)):
self.goal = goal
self.start = (1, 1)
self.n = self.SIZE * self.SIZE
def is_wall(self, r, c):
if not (0 <= r < self.SIZE and 0 <= c < self.SIZE):
return True
if r == self.WALL and c not in self.DOORS:
return True
if c == self.WALL and r not in self.DOORS:
return True
return False
def encode(self, rc):
r, c = rc
return r * self.SIZE + c
def decode(self, s):
return divmod(s, self.SIZE)
def open_cells(self):
return [self.encode((r, c)) for r in range(self.SIZE) for c in range(self.SIZE)
if not self.is_wall(r, c)]
def step(self, s, a):
r, c = self.decode(s)
dr, dc = self.DELTA_LIST[a]
nr, nc = r + dr, c + dc
if self.is_wall(nr, nc):
return s, -1.0, False
s2 = self.encode((nr, nc))
if (nr, nc) == self.goal:
return s2, 20.0, True
return s2, -1.0, False
def bfs_policy(self, target):
"""Politique intra-option : depuis chaque état, l'action qui réduit la distance BFS à
`target` (état ENCODÉ, int). Retourne (policy, dist)."""
size = self.SIZE
dist = {target: 0}
q = deque([target])
while q:
cur = q.popleft()
r, c = self.decode(cur)
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
nxt = nr * size + nc
if (0 <= nr < size and 0 <= nc < size and not self.is_wall(nr, nc)
and nxt not in dist):
dist[nxt] = dist[cur] + 1
q.append(nxt)
policy = {}
for s in range(self.n):
r, c = self.decode(s)
if self.is_wall(r, c) or s == target:
continue
best, bestd = None, 1e9
for i, (dr, dc) in enumerate(((-1, 0), (1, 0), (0, -1), (0, 1))):
nr, nc = r + dr, c + dc
nxt = nr * size + nc
if (0 <= nr < size and 0 <= nc < size and not self.is_wall(nr, nc)
and dist.get(nxt, 1e9) < bestd):
bestd = dist[nxt]
best = i
if best is not None:
policy[s] = best
return policy, dist
def bfs_distance(self, target):
"""Distances BFS depuis `target` (état encodé, int) vers tous les états ouverts."""
size = self.SIZE
dist = {target: 0}
q = deque([target])
while q:
cur = q.popleft()
r, c = self.decode(cur)
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
nxt = nr * size + nc
if (0 <= nr < size and 0 <= nc < size and not self.is_wall(nr, nc)
and nxt not in dist):
dist[nxt] = dist[cur] + 1
q.append(nxt)
return dist
env = FourRooms()
print("cellules ouvertes :", len(env.open_cells()), "sur", env.n)
print("but :", env.goal, "| portes :", env.ALL_DOORS)
dgoal = env.bfs_distance(env.encode(env.goal))
print("distance BFS start->goal :", dgoal.get(env.encode(env.start)))cellules ouvertes : 200 sur 225
but : (13, 13) | portes : [(3, 7), (11, 7), (7, 3), (7, 11)]
distance BFS start->goal : 24Lecture de la sortie — l’environnement en trois chiffres. Avant de lancer le moindre apprentissage, trois valeurs méritent qu’on s’y arrête :
(7,7) étant partagée — 13 + 13 − 1 = 25 murs, donc 200 états navigables. L’espace d’états reste petit : c’est voulu, pour que la différence entre apprenants vienne de la structure temporelle du problème, pas de sa taille.distance BFS start->goal : 24 : le chemin optimal fait 24 pas, et il en existe deux (via (7,3) puis (11,7), ou via (3,7) puis (7,11)). Avec −1 par pas et +20 au but, le retour optimal non actualisé vaut −23 + 20 = −3 : la récompense est presque entièrement absorbée par le coût du trajet. Le signal existe, mais il est loin.(1,1), but (13,13) : coins opposés, deux portes à franchir dans le bon ordre — les deux obstacles annoncés (crédit long-horizon, exploration) sont bien là.Note : la distance BFS est calculée par le simulateur, qui connaît la carte. L’agent ne la verra jamais — c’est le but de l’expérience : mesurer ce que l’essai-erreur coûte quand la solution est connue du monde mais pas de l’apprenant.
def render_grid(env, path=None):
size = env.SIZE
grid = []
for r in range(size):
row = []
for c in range(size):
if env.is_wall(r, c):
row.append("#")
elif (r, c) == env.goal:
row.append("G")
elif (r, c) == env.start:
row.append("S")
else:
row.append(".")
grid.append(row)
for row in grid:
print("".join(row))
render_grid(env)
print("\nTrouver le chemin le plus court est facile (BFS). Apprendre à le FAIRE par essai-erreur est lent.").......#.......
.S.....#.......
.......#.......
...............
.......#.......
.......#.......
.......#.......
###.#######.###
.......#.......
.......#.......
.......#.......
...............
.......#.......
.......#.....G.
.......#.......
Trouver le chemin le plus court est facile (BFS). Apprendre à le FAIRE par essai-erreur est lent.Lecture de la grille. Le rendu confirme la structure annoncée : ligne 7 et colonne 7 forment une croix de #, percée de deux ouvertures chacune — les quatre trous visibles dans la croix sont les portes. S et G occupent les coins diagonalement opposés (haut-gauche, bas-droite).
Deux détails compteront pour la suite :
S à G impose de traverser une pièce intermédiaire et deux portes — et, dans la pièce intermédiaire, de ressortir par la bonne porte. Une exploration au hasard des portes fait errer d’une pièce à l’autre sans jamais accumuler de progrès.# Option « atteindre la porte (7,3) » : on montre SA politique intra-option (flèches).
def render_option_policy(env, target):
target_e = env.encode(target) if isinstance(target, tuple) else target
pol, dist = env.bfs_policy(target_e)
size = env.SIZE
arrows = {0: "\u2191", 1: "\u2193", 2: "\u2190", 3: "\u2192"}
target_rc = env.decode(target_e)
for r in range(size):
row = []
for c in range(size):
if env.is_wall(r, c):
row.append("#")
elif (r, c) == target_rc:
row.append("*")
else:
s = env.encode((r, c))
row.append((arrows[pol[s]] if s in pol else "."))
print("".join(row))
print("Politique intra-option de la porte (7,3) — '\u2192' entre dans la porte.")
render_option_policy(env, (7, 3))
print("\nCette politique est DONNÉE (BFS) : l'option est un macro-comportement prêt. Plus bas on l'apprendra.")Politique intra-option de la porte (7,3) — '→' entre dans la porte.
↓↓↓↓↓↓↓#↓↓↓↓↓↓↓
↓↓↓↓↓↓↓#↓↓↓↓↓↓↓
↓↓↓↓↓↓↓#↓↓↓↓↓↓↓
↓↓↓↓↓↓↓←←←←←←←←
↓↓↓↓↓↓↓#↑↑↑↑↑↑↑
↓↓↓↓↓↓↓#↑↑↑↑↑↑↑
→→→↓←←←#↑↑↑↑↑↑↑
###*#######↑###
→→→↑←←←#↓↓↓↓↓↓↓
↑↑↑↑↑↑↑#↓↓↓↓↓↓↓
↑↑↑↑↑↑↑#↓↓↓↓↓↓↓
↑↑↑↑↑↑↑←←←←←←←←
↑↑↑↑↑↑↑#↑↑↑↑↑↑↑
↑↑↑↑↑↑↑#↑↑↑↑↑↑↑
↑↑↑↑↑↑↑#↑↑↑↑↑↑↑
Cette politique est DONNÉE (BFS) : l'option est un macro-comportement prêt. Plus bas on l'apprendra.Lecture de la sortie — que dessinent les flèches ? Chaque flèche est l’action que prendrait l’option « atteindre la porte (7,3) » depuis cette cellule : la politique intra-option π_o est définie sur tous les états ouverts, pas seulement dans la pièce de la cible.
↓ entre dans la porte — le * marque la cible, où l’option s’arrête (c’est la condition de fin β_o).(3,7). Depuis la pièce bas-droite, il transite par (11,7) puis remonte vers la colonne 3. Autrement dit, cette π_o « sait » déjà qu’il faut franchir une autre porte avant d’atteindre la sienne — le routage multi-portes est embarqué dans le macro-comportement.Et c’est là le point à retenir : cette politique est calculée par BFS, donc parfaite. L’option est un macro-comportement tout prêt. Ce que l’agent aurait appris de moins bon — ou comment apprendre π_o au lieu de la recevoir — est renvoyé à l’intra-option learning, plus bas dans le notebook.
def run_option(env, s, option, max_steps=80):
"""Exécute l'option `option` = (target_encoded, policy_dict, init) depuis s.
L'option s'arrête quand on atteint `target` ou après max_steps.
Retourne (s', tau, r_total)."""
target, pol, _ = option
tau = 0
r_total = 0.0
while tau < max_steps and s != target:
a = pol.get(s)
if a is None:
break
s2, rr, _ = env.step(s, a)
r_total += rr
tau += 1
s = s2
if s == target:
break
return s, tau, r_total
# Petite démo : agent au haut-gauche, exécution de l'option « porte (7,3) ».
s0 = env.encode((1, 1))
t = env.ALL_DOORS[2]
pol_t, _ = env.bfs_policy(env.encode(t))
opt = (env.encode(t), pol_t, None)
s_end, tau, rr = run_option(env, s0, opt)
print("départ (1,1) -> option porte (7,3) : arrivée", env.decode(s_end), "| étapes:", tau, "| récompense:", rr)
print("L'option a 'sauté' plusieurs pas d'un coup : c'est l'abstraction temporelle.")départ (1,1) -> option porte (7,3) : arrivée (7, 3) | étapes: 8 | récompense: -8.0
L'option a 'sauté' plusieurs pas d'un coup : c'est l'abstraction temporelle.Lecture de la démo — une décision, huit pas. La sortie dit l’essentiel : parti de (1,1), un seul choix d’option (« porte (7,3) ») amène l’agent en (7,3) en 8 étapes, pour une récompense totale de −8.0 — exactement −1 par pas, aucun détour. Huit pas, c’est la distance de Manhattan |7−1| + |3−1| = 8 : la politique BFS ne gaspille rien.
La transition SMDP (s, o) → (s', τ, r) se lit directement sur ces trois nombres :
| Grandeur | Valeur | Rôle |
|---|---|---|
s' |
(7,3) |
l’état d’arrivée — celui sur lequel le haut niveau rechoisit |
τ |
8 | la durée de l’option ; l’actualisation du Bellman SMDP porte γ^τ (avec le γ = 0.99 des apprenants ci-dessous : 0.99^8 ≈ 0.92), pas γ |
r |
−8.0 | la récompense cumulée sur les 8 pas — un seul « retour » vu du haut niveau |
L’option s’est arrêtée sur sa cible : condition de fin β_o déterministe (1 sur la cible, 0 ailleurs), doublée d’un garde-fou max_steps qui coupe une option qui tournerait en rond.
Transition : cette option était parfaite et donnée. Avant de mesurer ce que l’agent apprend, il faut une référence — le Q-learning plat du notebook 5, sur les 4 actions primaires, au même budget d’épisodes. Cellule suivante.
def flat_qlearn(env, seed, episodes=3000, alpha=0.2, gamma=0.99, eps_start=0.4, eps_end=0.05):
rng = np.random.default_rng(seed)
n, na = env.n, 4
Q = [[0.0] * na for _ in range(n)]
first_solved = None
solved_last100 = 0
for ep in range(episodes):
eps = eps_start + (eps_end - eps_start) * (ep / episodes)
s = env.encode(env.start)
done = False
steps = 0
while not done and steps < 400:
if rng.random() < eps:
a = int(rng.integers(na))
else:
vals = Q[s]
a = vals.index(max(vals))
s2, r, done = env.step(s, a)
Q[s][a] += alpha * (r + gamma * max(Q[s2]) - Q[s][a])
s = s2
steps += 1
if done and first_solved is None:
first_solved = ep
if ep >= episodes - 100 and done:
solved_last100 += 1
return first_solved, solved_last100
SEEDS = [0, 1, 7, 42]
flat_res = {}
for seed in SEEDS:
t0 = time.time()
first, last = flat_qlearn(env, seed)
flat_res[seed] = (first, last)
print(f"seed={seed:2d} first_solved={first!s:>5} solved_last100={last:>3} ({time.time()-t0:.1f}s)")seed= 0 first_solved= 8 solved_last100=100 (0.2s)
seed= 1 first_solved= 13 solved_last100=100 (0.2s)
seed= 7 first_solved= 15 solved_last100=100 (0.3s)
seed=42 first_solved= 12 solved_last100=100 (0.2s)Lecture des quatre runs — que mesure chaque colonne ? Avant les statistiques, un décryptage ligne par ligne :
first_solved vaut 8, 13, 15 ou 12 selon le seed : le premier succès tombe dans la première quinzaine d’épisodes, pour les 4 seeds. Mais attention à ce que la métrique capture : à l’épisode 12 sur 3000, l’anneau d’exploration n’a presque pas bougé (ε passe de 0.40 à ≈ 0.398). Ce premier succès est donc un coup d’exploration — une séquence chanceuse de ~24 pas largement aléatoires — et non déjà un apprentissage.solved_last100 = 100 partout : ceci, en revanche, est la signature de l’apprentissage. Sur les 100 derniers épisodes, ε ≈ 0.05 : l’agent suit sa politique apprise et atteint le but à chaque épisode. La valeur s’est propagée le long du chemin, et la politique la suit.La dispersion 8 → 15 (facteur ~2) servira de référence : elle dit combien la découverte initiale dépend du hasard, là où la consolidation, elle, est systématique.
flat_firsts = [v[0] for v in flat_res.values() if v[0] is not None]
flat_lasts = [v[1] for v in flat_res.values()]
print("flat Q-learning, 4 seeds")
print(" épisodes-avant-premier-succès :", flat_firsts)
print(" médiane :", statistics.median(flat_firsts) if flat_firsts else "jamais (sur le budget)")
print(" taux de succès final (100 derniers ép.) :", [f"{v/100:.2f}" for v in flat_lasts])flat Q-learning, 4 seeds
épisodes-avant-premier-succès : [8, 13, 15, 12]
médiane : 12.5
taux de succès final (100 derniers ép.) : ['1.00', '1.00', '1.00', '1.00']L’apprenant plat (Q-learning sur les 4 actions primitives) réussit pour la première fois au bout d’une douzaine d’épisodes en médiane (first_solved), avec une dispersion inter-seed visible (min/max dans la cellule précédente). Une fois le chemin découvert par exploration, il le réutilise : le taux de succès final (100 derniers épisodes) monte à 1.00.
Mais il a fallu des dizaines de milliers de pas d’essais — et la découverte initiale tient en partie de la chance d’exploration. C’est le coût du crédit long-horizon : pour franchir deux portes dans le bon ordre, l’agent doit aligner une longue séquence cohérente de pas, que l’exploration aléatoire ne découvre qu’à force. C’est précisément le problème que l’abstraction temporelle attaque.
Transition — de la référence au cadre à options. Le plat a appris, mais il a payé chaque pas de sa découverte. On munit maintenant l’agent d’un niveau haut qui choisit non plus des pas mais des options — les quatre « atteindre la porte k » et « atteindre le but ». Deux changements structurels en découlent, tous deux mesurables :
Q(s, o) se met à jour à l’échelle de l’option : récompense cumulée r, durée τ, actualisation γ^τ.Et surtout : ces macros sont construites par BFS — parfaites, données. Retenez-le, c’est ce qui déterminera la lecture des résultats qui viennent.
# On définit les OPTIONS du haut niveau : atteindre chaque porte, et atteindre le but.
def build_options(env):
options = {}
for i, door in enumerate(env.ALL_DOORS):
t = env.encode(door)
pol, _ = env.bfs_policy(t)
options[f"porte_{i}"] = (t, pol, None) # (cible encodée, politique intra-option, initiation)
g = env.encode(env.goal)
pol_g, _ = env.bfs_policy(g)
options["but"] = (g, pol_g, None)
return options
options = build_options(env)
print("options définies :", list(options.keys()))
for k, (t, pol, _) in options.items():
print(f" {k:9s} -> cible {env.decode(t)} (politique intra-option : {len(pol)} états)")options définies : ['porte_0', 'porte_1', 'porte_2', 'porte_3', 'but']
porte_0 -> cible (3, 7) (politique intra-option : 199 états)
porte_1 -> cible (11, 7) (politique intra-option : 199 états)
porte_2 -> cible (7, 3) (politique intra-option : 199 états)
porte_3 -> cible (7, 11) (politique intra-option : 199 états)
but -> cible (13, 13) (politique intra-option : 199 états)Lecture de la sortie — le menu du haut niveau. Cinq options : quatre « porte k » et « but ». Deux détails dans la colonne de droite :
π_o.Noter l’asymétrie de rythme : le plat lit sa table 200 × 4 une fois par étape ; le SMDP lit sa table 200 × 5 une fois par option (le τ de la démo était 8 pour une porte voisine, ~24 pour le but — la distance BFS mesurée au départ). C’est cette différence de rythme de décision — pas la taille des tables — que la comparaison mesure.
def smdp_qlearn(env, options, seed, episodes=1500, alpha=0.2, gamma=0.99,
eps_start=0.4, eps_end=0.05, max_steps=80):
rng = np.random.default_rng(seed)
names = list(options.keys())
n = env.n
Q = {name: [0.0] * n for name in names}
first_solved = None
solved_last100 = 0
for ep in range(episodes):
eps = eps_start + (eps_end - eps_start) * (ep / episodes)
s = env.encode(env.start)
done = False
budget_steps = 0
while not done and budget_steps < 400:
if rng.random() < eps:
name = names[int(rng.integers(len(names)))]
else:
vals = [Q[nm][s] for nm in names]
name = names[vals.index(max(vals))]
target, pol, _ = options[name]
s_choose = s # l'état où l'option est CHOISIE
tau = 0
r_tot = 0.0
while tau < max_steps and s != target:
a = pol.get(s)
if a is None:
break
s2, rr, done = env.step(s, a)
r_tot += rr
tau += 1
budget_steps += 1
s = s2
if s == target:
break
# mise à jour SMDP : la valeur porte sur s_choose (pas sur l'état d'arrivée)
best_next = max(Q[nm][s] for nm in names)
Q[name][s_choose] += alpha * (r_tot + (gamma ** tau) * best_next - Q[name][s_choose])
if done:
break
if done and first_solved is None:
first_solved = ep
if ep >= episodes - 100 and done:
solved_last100 += 1
return first_solved, solved_last100
opt_res = {}
for seed in SEEDS:
t0 = time.time()
first, last = smdp_qlearn(env, options, seed)
opt_res[seed] = (first, last)
print(f"seed={seed:2d} first_solved={first!s:>5} solved_last100={last:>3} ({time.time()-t0:.1f}s)")seed= 0 first_solved= 0 solved_last100=100 (0.0s)
seed= 1 first_solved= 0 solved_last100=100 (0.0s)
seed= 7 first_solved= 0 solved_last100=100 (0.0s)
seed=42 first_solved= 0 solved_last100=100 (0.0s)Lecture des quatre runs — une uniformité parfaite. Contrairement au plat (8, 13, 15, 12), les quatre seeds rendent exactement le même résultat algorithmique : first_solved = 0, solved_last100 = 100. Le temps de run est affiché entre parenthèses en fin de chaque ligne.
first_solved = 0 : le premier épisode atteint déjà le but. L’explication est mécanique : parmi les 5 options du menu, l’une (but) est compétente depuis tout état — tôt ou tard dans l’épisode elle est sélectionnée, et elle résout.Le contraste avec le plat est frappant — mais il ne dit pas encore ce qu’il semble dire. Les statistiques et la lecture honnête qui suivent établissent pourquoi.
opt_firsts = [v[0] for v in opt_res.values() if v[0] is not None]
opt_lasts = [v[1] for v in opt_res.values()]
print("SMDP Q-learning (options), 4 seeds")
print(" épisodes-avant-premier-succès :", opt_firsts)
print(" médiane :", statistics.median(opt_firsts) if opt_firsts else "jamais")
print(" taux de succès final :", [f"{v/100:.2f}" for v in opt_lasts])
fm = statistics.median(flat_firsts) if flat_firsts else float("inf")
om = statistics.median(opt_firsts) if opt_firsts else float("inf")
print(f"\nMédiane épisodes-avant-succès : flat={fm} options={om}")
if fm != float("inf") and om != float("inf") and om > 0:
print(f"Facteur d'accélération médian : {fm/om:.1f}x")SMDP Q-learning (options), 4 seeds
épisodes-avant-premier-succès : [0, 0, 0, 0]
médiane : 0.0
taux de succès final : ['1.00', '1.00', '1.00', '1.00']
Médiane épisodes-avant-succès : flat=12.5 options=0.0L’apprenant à options réussit dès l’épisode 0. Il faut le lire avec honnêteté : ce n’est pas un acquis d’apprentissage — c’est la case limite du framework.
but porte une politique intra-option parfaite (BFS vers le but). La choisir une seule fois résout l’épisode. Le haut niveau n’a donc rien à apprendre : first_solved = 0.Deux leçons en découlent, et c’est la valeur pédagogique de ce notebook :
π_o ne sont pas offertes mais apprises.Transition — apprendre les macros au lieu de les recevoir. La case limite est établie ; que reste-t-il à apprendre dans le framework ? Les politiques intra-option π_o elles-mêmes. La cellule suivante ré-entraîne chaque option « porte k » de zéro, avec trois ingrédients qui changent la nature du problème :
Q_prim apprend « sa » politique orientée vers « sa » porte ;Le chiffre à surveiller : le taux d’atteinte du sous-objectif — combien d’épisodes atteignent leur cible avec une π_o partie de zéro.
# On APPREND maintenant les politiques intra-option (au lieu de les donner en BFS).
# Chaque option est « atteindre la porte k » ; on apprend Q_prim(s,a) mais on ne met à jour que
# les états où l'option est ACTIVE (intra-option learning) — c'est le cœur de Sutton et al.
def intra_option_learning(env, targets, seed, episodes=1500, alpha=0.2, gamma=0.99,
eps_start=0.5, eps_end=0.08, max_steps=40):
rng = np.random.default_rng(seed)
n, na = env.n, 4
Q = {tid: [[0.0] * na for _ in range(n)] for tid in targets}
successes = 0
for ep in range(episodes):
eps = eps_start + (eps_end - eps_start) * (ep / episodes)
s = env.encode(env.start)
done = False
steps = 0
while not done and steps < 400:
# oracle haut-niveau : on choisit l'option dont la cible est la plus proche (BFS),
# pour ISOLER l'apprentissage bas-niveau (le niveau haut est ici supposé bon).
tid = min(targets, key=lambda t: bfs_dist[t].get(s, 1e9))
if rng.random() < eps:
a = int(rng.integers(na))
else:
vals = Q[tid][s]
a = vals.index(max(vals))
s2, r, done = env.step(s, a)
target = env.encode(tid)
r_shaped = 1.0 if s2 == target else -1.0
Q[tid][s][a] += alpha * (r_shaped + gamma * max(Q[tid][s2]) - Q[tid][s][a])
s = s2
steps += 1
if s2 == target:
successes += 1
break
return Q, successes
# précalcul des distances BFS pour le choix de l'option la plus proche
targets = env.ALL_DOORS
bfs_dist = {t: env.bfs_distance(env.encode(t)) for t in targets}
_Q, succ = intra_option_learning(env, targets, SEEDS[0])
print(f"intra-option learning (seed {SEEDS[0]}) : atteintes de sous-objectif = {succ}")
print(f" -> taux d'atteinte du sous-objectif = {succ/1500:.2f} (sur 1500 épisodes)")
print("Les Q de chaque option apprennent la politique orientée vers SA porte.")intra-option learning (seed 0) : atteintes de sous-objectif = 1459
-> taux d'atteinte du sous-objectif = 0.97 (sur 1500 épisodes)
Les Q de chaque option apprennent la politique orientée vers SA porte.Lecture de la sortie — ce que la π_o apprise vaut. Sur 1500 épisodes, l’option active a atteint sa cible 1459 fois : un taux de 0.97. Décomposons ce que ce nombre mesure — et ce qu’il ne mesure pas :
Q_prim devient une politique qui mène à sa porte — le même routage que la cellule des flèches, mais reconstruit par essai-erreur au lieu d’être calculé par BFS. L’agrégat ne dit pas quand la convergence a eu lieu, seulement qu’à l’arrivée l’atteinte est quasi systématique.C’est pourtant ici que le framework « apprend » au sens propre — le contraste avec la case limite précédente est le message central du notebook.
π_o au lieu de le donnerLa vraie force du framework n’est pas que les sous-politiques soient bonnes, c’est qu’elles puissent être apprises. On apprend ici le niveau bas séparément — chaque option « atteindre la porte k » apprend sa propre Q_prim avec une récompense de sous-objectif (+1 en entrant dans la cible). Ce faisant, chaque option acquiert la politique orientée vers sa porte.
Ce découplage est ce qui permet le RL hiérarchique : un niveau haut choisit où aller, le niveau bas apprend comment y aller, et les deux peuvent se ré-entraîner.
Transition — le verdict par règles explicites. Reste à confronter les mécanismes sur les mêmes seeds {0, 1, 7, 42}. La cellule suivante n’improvise pas sa conclusion : elle calcule les médianes, rapporte la dispersion min/max, puis embranche sur un verdict parmi cinq cas codés — « case limite », « accélère », « accélère modérément », « inconclusif », « ne résout pas ». Les seuils sont écrits avant lecture des chiffres : c’est cette procédure, plus que la valeur du verdict, qui rend la comparaison honnête.
# Verdict multi-seed honnête : on recompile les résultats des DEUX mécanismes.
print("=== VERDICT MULTI-SEED (seeds", SEEDS, ") ===")
print(f"{'méthode':12s} {'first_solved médian':>20s} {'succès final moyen':>20s} {'min/max first':>18s}")
def row(name, res):
fs = [v[0] for v in res.values() if v[0] is not None]
last = [v[1] / 100 for v in res.values()]
med = statistics.median(fs) if fs else float("inf")
mn = min(fs) if fs else "-"
mx = max(fs) if fs else "-"
print(f"{name:12s} {str(med):>20s} {f'{statistics.mean(last):.2f}':>20s} {f'{mn}/{mx}':>18s}")
row("flat", flat_res)
row("options", opt_res)
adv = statistics.median([v[0] for v in opt_res.values() if v[0] is not None])
flt = statistics.median([v[0] for v in flat_res.values() if v[0] is not None])
print()
if adv is not None and adv == 0:
print("HONEST VERDICT : CASE LIMITE — l'option 'but' est une macro PARFAITE (BFS) ; le haut niveau")
print(" résout dès l'ép.0, il n'apprend RIEN. La comparaison d'apprentissage flat-vs-options n'est")
print(" PAS pertinente ici. Le contenu d'apprentissage réel est l'intra-option learning (section suivante).")
elif adv is not None and flt is not None and adv > 0:
ratio = flt / adv if adv else float("inf")
if ratio >= 1.5:
verdict = f"OPTIONS ACCÉLÈRENT (~{ratio:.1f}x) — l'abstraction temporelle réduit l'horizon du choix."
elif ratio >= 1.1:
verdict = f"OPTIONS ACCÉLÈRENT MODESTEMENT (~{ratio:.1f}x) — gain réel mais plus faible que prévu."
else:
verdict = "INCONCLUSIF / options ~ flat — sur cette instance, l'abstraction temporelle ne domine pas."
print("HONEST VERDICT :", verdict)
else:
print("HONEST VERDICT : options ne résout PAS dans le budget — l'abstraction temporelle n'aide pas ici.")
print("Dispersion inter-seed first_solved : flat =", sorted([v[0] for v in flat_res.values() if v[0] is not None]),
"| options =", sorted([v[0] for v in opt_res.values() if v[0] is not None]))=== VERDICT MULTI-SEED (seeds [0, 1, 7, 42] ) ===
méthode first_solved médian succès final moyen min/max first
flat 12.5 1.00 8/15
options 0.0 1.00 0/0
HONEST VERDICT : CASE LIMITE — l'option 'but' est une macro PARFAITE (BFS) ; le haut niveau
résout dès l'ép.0, il n'apprend RIEN. La comparaison d'apprentissage flat-vs-options n'est
PAS pertinente ici. Le contenu d'apprentissage réel est l'intra-option learning (section suivante).
Dispersion inter-seed first_solved : flat = [8, 12, 13, 15] | options = [0, 0, 0, 0]Le tableau compare flat et options à seeds identiques {0,1,7,42}, avec dispersion min/max rapportée. Que lit-on ?
first_solved médian ~12 ; succès final 1.00. Il apprend, mais lentement.first_solved = 0 ; succès final 1.00. Il n’apprend pas — le macro but résout à la première exécution.Conclusion honnête : ce n’est pas « les options apprennent plus vite » (elles n’apprennent rien), c’est « un macro parfait offert rend le problème trivial ». Le framework fait ici de la planification déguisée. La question « est-ce que l’abstraction temporelle accélère l’apprentissage ? » ne peut pas être tranchée par ce run — elle le sera par l’intra-option learning, où les macros ne sont plus données mais apprises.
Ce n’est pas un échec de l’expérience : c’est la bonne réponse à la mauvaise question. Le cadre nous force à identifier que sans macros apprises, l’option framework est un raccourci de planning, pas un algorithme d’apprentissage — et c’est exactement le point que Sutton et al. défendent pour justifier l’intra-option learning.
# Courbes médianes : taux de succès vs épisode (moyenne glissante sur 3 runs).
def run_curve(env, seed, method, episodes):
rng = np.random.default_rng(seed)
n = env.n
succ = []
if method == "flat":
Q = [[0.0] * 4 for _ in range(n)]
for ep in range(episodes):
s = env.encode(env.start); done = False; steps = 0
while not done and steps < 400:
if rng.random() < 0.2:
a = int(rng.integers(4))
else:
vals = Q[s]; a = vals.index(max(vals))
s2, r, done = env.step(s, a)
Q[s][a] += 0.2 * (r + 0.99 * max(Q[s2]) - Q[s][a])
s = s2; steps += 1
succ.append(1 if done else 0)
else:
names = list(options.keys())
Q = {nm: [0.0] * n for nm in names}
for ep in range(episodes):
s = env.encode(env.start); done = False; budget = 0
while not done and budget < 400:
if rng.random() < 0.2:
name = names[int(rng.integers(len(names)))]
else:
vals = [Q[nm][s] for nm in names]
name = names[vals.index(max(vals))]
target, pol, _ = options[name]
s_choose = s
tau = 0; r_tot = 0.0
while tau < 80 and s != target:
a = pol.get(s)
if a is None: break
s2, rr, done = env.step(s, a)
r_tot += rr; tau += 1; budget += 1; s = s2
if s == target: break
best_next = max(Q[nm][s] for nm in names)
Q[name][s_choose] += 0.2 * (r_tot + 0.99 ** tau * best_next - Q[name][s_choose])
if done: break
succ.append(1 if done else 0)
return succ
EP = 600
win = 60
def smooth(x):
arr = np.array(x, dtype=float)
return np.convolve(arr, np.ones(win) / win, mode="same")
curves = {}
for meth in ["flat", "options"]:
acc = np.zeros(EP)
for seed in [0, 1, 7]:
acc += np.array(run_curve(env, seed, meth, EP))
curves[meth] = smooth(acc / 3)
print("fin courbe", meth, "taux de succès (moyenne 3 runs) :", round(curves[meth][-1], 2))
plt.figure(figsize=(7.5, 4.2))
plt.plot(curves["flat"], label="flat Q-learning", color="#c0392b")
plt.plot(curves["options"], label="SMDP options", color="#2980b9")
plt.axhline(1.0, ls="--", lw=1, color="gray", alpha=0.6)
plt.ylabel("taux de succès (moyenne glissante)")
plt.xlabel("épisode")
plt.title("Abstraction temporelle : succès vs épisode (médiane 3 runs)")
plt.legend()
plt.tight_layout()
plt.show()
plt.close()fin courbe flat taux de succès (moyenne 3 runs) : 0.52
fin courbe options taux de succès (moyenne 3 runs) : 0.52Lecture des chiffres — pourquoi 0.52 et pas 1.00 ? Les deux courbes s’achèvent sur le même « taux de succès 0.52 », alors que leurs dynamiques n’ont rien en commun. Ce 0.52 identique est un artefact de bord, pas une mesure :
np.convolve(..., mode="same") sur une fenêtre de 60. Au dernier indice, la fenêtre ne couvre que 31 épisodes réels — le reste est du zéro-padding. Un taux brut de 1.00 s’affiche donc ≈ 31/60 ≈ 0.52. Que les DEUX méthodes affichent exactement 0.52 signifie que leurs derniers épisodes sont tous réussis — cohérent avec solved_last100 = 100 mesuré plus haut. Le même artefact déprime le début de chaque courbe (bord gauche).ε fixe à 0.2 (plus d’anneau 0.4 → 0.05), 600 épisodes, 3 seeds (0, 1, 7). La montée du plat est ici plus lente que dans le run à ε annealing — les courbes se comparent entre elles, pas aux médianes précédentes. (Détail : le calcul est une moyenne sur les 3 runs, acc/3, alors que le titre du graphe dit « médiane ».)UserWarning du backend Agg est bénin — il signale juste que la figure n’est pas affichée en interactif. La trace quantitative commitée, ce sont les deux valeurs imprimées ci-dessus.À retenir : une moyenne glissante sous-estime systématiquement en bord de série — lire la valeur brute ou le last-100 avant de conclure.
La courbe « options » est un créneau tout en haut : elle atteint 100 % dès le début, parce que le macro but est parfait. La courbe « flat » monte progressivement — c’est elle qui apprend. À budget égal, le niveau plat doit découvrir toute la séquence de pas ; les options n’ont rien eu à découvrir. La moyenne glissante sur 3 runs lisse la variance : c’est la tendance, pas une seed isolée.
Encore une fois, lecture honnête : plus haut ≠ plus appris. Le créneau des options est la signature d’un planner parfait, pas d’un learner. La courbe qui compte pour l’apprentissage est celle de l’intra-option learning, où les sous-politiques partent de zéro.
Synthèse — ce que l’expérience a établi. Trois mécanismes, trois résultats, un fil conducteur :
| Mécanisme | Ce qui est donné | Résultat mesuré | Ce que ça prouve |
|---|---|---|---|
| Q-learning plat | rien | first_solved médian 12.5 (dispersion 8–15), succès final 1.00 |
le crédit long-horizon se paie en épisodes de découverte aléatoire |
| SMDP à options | les π_o (BFS, parfaites) |
first_solved 0 sur les 4 seeds |
un macro parfait donné = planification, pas apprentissage |
| Intra-option learning | le haut niveau (oracle) | 1459/1500 = 0.97 (seed 0) | la vraie brique d’apprentissage : π_o reconstruite par essai-erreur |
Trois leçons à emporter :
Les exercices qui suivent attaquent chacun une hypothèse du protocole : la durée τ (exercice 1), l’initiation I_o (exercice 2), les options paresseuses (exercice 3).
Tous les stubs respectent la règle « pas d’erreur volontaire » : complétez, exécutez, commentez.
Le SMDP tient compte de la durée τ de l’option (facteur γ^τ). Comparez les deux variantes : celle qui utilise γ^τ et celle qui utilise un simple γ. Que se passe-t-il si l’option devient très longue ? Écrivez votre réponse dans la cellule suivante.
# Exercice 1 — complétez
def smdp_qlearn_no_tau(env, options, seed, episodes=600):
# Variante qui IGNORE la durée de l'option (gamma^tau -> gamma).
rng = np.random.default_rng(seed)
names = list(options.keys())
n = env.n
Q = {name: [0.0] * n for name in names}
first_solved = None
for ep in range(episodes):
s = env.encode(env.start); done = False
while not done:
if rng.random() < 0.2:
name = names[int(rng.integers(len(names)))]
else:
vals = [Q[nm][s] for nm in names]
name = names[vals.index(max(vals))]
target, pol, _ = options[name]
s_choose = s
tau = 0; r_tot = 0.0
while tau < 80 and s != target:
a = pol.get(s)
if a is None: break
s2, rr, done = env.step(s, a)
r_tot += rr; tau += 1; s = s2
if s == target: break
# TODO etudiant : remplacez gamma**tau par gamma ici, observez la différence
Q[name][s_choose] += 0.2 * (r_tot + (0.99 ** tau) * max(Q[nm][s] for nm in names) - Q[name][s_choose])
if done and first_solved is None:
first_solved = ep
return first_solved
print("Exercice 1 — à compléter (voir TODO dans la cellule) : l'effet de gamma^tau vs gamma.")Exercice 1 — à compléter (voir TODO dans la cellule) : l'effet de gamma^tau vs gamma.I_oNotre option peut être choisie partout (I_o = tous les états ouverts). Mais une option « atteindre la porte (7,3) » n’a de sens QUE dans les pièces haut-gauche / bas-gauche. Modifiez l’initiation set pour restreindre chaque option aux états de sa propre pièce, et mesurez si le haut niveau apprend plus vite (moins d’options ambiguës).
# Exercice 2 — complétez
def room_of(env, rc):
r, c = rc
w = env.WALL
if r < w and c < w: return 0
if r < w and c > w: return 1
if r > w and c < w: return 2
return 3
# TODO etudiant : construisez un dict option -> set d'initiation restreint à la pièce,
# puis refaites tourner smdp_qlearn avec cette contrainte et comparez first_solved.
print("Exercice 2 — à compléter (restreindre l'initiation set puis mesurer).")Exercice 2 — à compléter (restreindre l'initiation set puis mesurer).Une option intra-option apprise peut devenir une politique qui tourne en rond (elle n’atteint jamais sa cible mais ne coûte rien). Proposez et implémentez une pénalité de durée (au-delà de max_steps, l’option est coupée et reçoit une récompense négative), et vérifiez que cela réduit le comportement de tournoiement.
Exercice 3 — à compléter (pénalité de durée anti-tournoiement).Pour aller plus loin
rl_8 (model-based) et les skills des agents modernes (options = compétences).Voir #1454 (Training & Post-Training) — po-2024 pionnier ⇄ ai-01 approfondit. Issue #12597.