Chaînes de Markov et compromis exploration-exploitation en Python

Le concept en termes simples

L'IA doit souvent agir dans l'incertitude. Une chaîne de Markov modélise la façon dont un système passe d'un état à l'autre avec des probabilités fixes, et un bandit manchot à plusieurs bras montre le choix central de l'apprentissage par renforcement : essayer quelque chose de nouveau ou utiliser ce qui a le mieux marché jusqu'ici.

Prédisez les états futurs avec une chaîne de Markov et équilibrez exploration et exploitation avec un bandit epsilon-greedy.

Idées clés

Dans une chaîne de Markov, l'état suivant ne dépend que de l'état actuel.
Les probabilités de transition qui sortent d'un état totalisent toujours 1.
Explorer permet de trouver de meilleures options ; exploiter rapporte des récompenses avec la meilleure option connue.
Epsilon règle l'équilibre : plus epsilon est grand, plus on explore.

Quand l’utiliser ?

Comprendre ce qui se passe à l'intérieur des réseaux de neurones et des bibliothèques d'IA.
Apprendre l'idée avant de l'implémenter dans les défis correspondants.
Se préparer aux cours d'apprentissage automatique, aux entretiens et aux projets.

À vous de jouer

Changez les probabilités de transition de la météo pour voir où la chaîne se stabilise. Appuyez sur Lecture pour que le bandit apprenne quelle machine rapporte le plus.

Code d’exemple

Exécuter le code →

main.py

import random

# Markov chain: tomorrow's weather depends only on today's.
transitions = {"sunny": {"sunny": 0.8, "rainy": 0.2}, "rainy": {"sunny": 0.4, "rainy": 0.6}}
dist = {"sunny": 1.0, "rainy": 0.0}
for day in range(1, 4):
    dist = {s: sum(dist[p] * transitions[p][s] for p in dist) for s in dist}
    print(f"day {day}:", {s: round(v, 3) for s, v in dist.items()})

# Epsilon-greedy bandit: usually pick the best arm so far, sometimes explore.
random.seed(1)
true_payouts = [0.3, 0.7]
counts, totals = [0, 0], [0.0, 0.0]
epsilon = 0.1
for _ in range(500):
    if random.random() < epsilon or 0 in counts:
        arm = random.randrange(2)                                  # explore
    else:
        arm = max(range(2), key=lambda a: totals[a] / counts[a])  # exploit
    reward = 1 if random.random() < true_payouts[arm] else 0
    counts[arm] += 1
    totals[arm] += reward
print("pulls per arm:", counts)
print("estimated payouts:", [round(t / c, 2) for t, c in zip(totals, counts)])

Résultat attendu

day 1: {'sunny': 0.8, 'rainy': 0.2}
day 2: {'sunny': 0.72, 'rainy': 0.28}
day 3: {'sunny': 0.688, 'rainy': 0.312}
pulls per arm: [25, 475]
estimated payouts: [0.16, 0.7]

Fonctionnement

Chaque jour, les nouvelles probabilités sont les anciennes multipliées par les probabilités de transition, donc « ensoleillé » passe de 1.0 à 0.688 en trois jours. Le bandit choisit un bras au hasard 10 % du temps et tire sinon le bras ayant la meilleure moyenne jusque-là ; il consacre vite la plupart des tirages au meilleur bras et estime son gain à environ 0.7.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices pratiques

Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.

Modifiez les entrées ou les poids et prédisez la sortie avant d'exécuter.
Affichez les valeurs intermédiaires pour suivre chaque étape du calcul.
Résolvez les défis liés ci-dessous pour implémenter l'idée vous-même.

Exécuter dans l’IDE Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis