Apprentissage par renforcement : apprendre en agissant.

• Formuler un problème de contrôle comme un MDP.
• Implémenter itération de la valeur, Q-learning et REINFORCE, et les comparer sur un même environnement.
• Faire apprendre à un robot simulé à atteindre une cible en évitant des obstacles.
• Expliquer pourquoi le RL est difficile (crédit temporel, exploration, variance) et ce qu’on fait pour y remédier.

Références : Reinforcement Learning: An Introduction (Sutton & Barto, gratuit), cours de David Silver (DeepMind), « Spinning Up in Deep RL » (OpenAI), CS285 (Berkeley).

Exploiter = jouer le bras qu’on croit le meilleur ; explorer = en essayer d’autres pour vérifier. Le glouton pur se bloque sur un bras médiocre si les premiers tirages ont été malchanceux. ε-glouton explore au hasard, à taux constant : regret linéaire. UCB explore les bras incertains (bonus √(ln t / n)) : regret logarithmique, prouvé optimal à constante près. Ce dilemme est partout : essais cliniques, publicité, choix de la prochaine expérience scientifique, et chaque décision d’un robot qui apprend.

Un processus de décision markovien : états S, actions A, transitions P(s′ | s, a), récompenses R(s, a, s′), facteur d’actualisation γ ∈ [0, 1[. Une politique π(a | s) dit quoi faire. On cherche π qui maximise le retour espéré G = Σ γᵗ rₜ. γ < 1 rend la somme finie et exprime que « 10 maintenant vaut plus que 10 dans 100 pas ». Les récompenses négatives par pas (−0,1) poussent à aller vite : le façonnage de récompense est un art — une récompense mal choisie et le robot apprend à tourner en rond pour collecter des points.

L’opérateur de Bellman T(V)(s) = max_a Σ p(r + γV(s′)) est une contraction de facteur γ pour la norme sup : ‖T(V) − T(W)‖ ≤ γ‖V − W‖. Par le théorème du point fixe de Banach, itérer converge géométriquement vers l’unique V* — une preuve d’une page, classique en prépa. La politique gloutonne par rapport à V* est optimale. Cette approche (programmation dynamique, module L04) exige de connaître le modèle P et R et d’énumérer les états : impossible pour un robot réel (états continus, modèle inconnu). D’où la suite.

Q(s, a) estime le retour si on fait a dans s puis on joue au mieux. Après une transition (s, a, r, s′), la cible r + γ max Q(s′, ·) est une meilleure estimation que Q(s, a) : on s’en rapproche d’un pas α. C’est une version stochastique de l’itération de la valeur, qui ne demande que des échantillons. Q-learning est hors-politique : il apprend la valeur de la politique gloutonne même en explorant au hasard. Converge vers Q* si chaque (s, a) est visité infiniment souvent et α décroît convenablement (Watkins, 1989). Avec un réseau de neurones à la place de la table (DQN, 2015 : Atari depuis les pixels), la convergence n’est plus garantie ; on stabilise avec un tampon de rejeu et un réseau cible.

Q-learning apprend des valeurs et en déduit une politique déterministe : efficace en échantillons, mais limité aux actions discrètes et parfois instable avec des réseaux. Le gradient de politique optimise directement une politique stochastique, marche en actions continues (couples moteurs !), mais souffre d’une variance énorme (un épisode entier pour une estimation). Les méthodes acteur-critique combinent les deux : l’acteur (politique) est corrigé par un critique (valeur) qui remplace G par une estimation moins bruitée. PPO (2017), l’algorithme du RLHF et de la marche des robots, est un acteur-critique qui limite la taille de chaque mise à jour.

def evaluer_politique(P, R, pi, gamma):
    n = len(pi); Ppi = np.array([P[pi[s]][s] for s in range(n)]); Rpi = np.array([R[pi[s]][s] for s in range(n)])
    return np.linalg.solve(np.eye(n) - gamma * Ppi, Rpi)
def amelioration(P, R, V, gamma):
    return np.argmax([R[a] + gamma * P[a] @ V for a in range(len(P))], axis=0)
def iteration_valeur_mat(P, R, gamma, tol=1e-10):
    V = np.zeros(len(R[0]))
    while True:
        V2 = np.max([R[a] + gamma * P[a] @ V for a in range(len(P))], axis=0)
        if np.abs(V2 - V).max() < tol: return V2
        V = V2

def temps_attendu():
    V = np.zeros(11)
    for _ in range(2000):
        V2 = V.copy()
        for s in range(10):
            av = 1 + 0.8 * V[min(s + 1, 10)] + 0.2 * V[max(s - 1, 0)]
            sa = 1 + 0.5 * V[min(s + 3, 10)] + 0.5 * V[s]
            V2[s] = min(av, sa)
        V = V2
    pol = ["avancer" if 1 + 0.8 * V[min(s + 1, 10)] + 0.2 * V[max(s - 1, 0)] <= 1 + 0.5 * V[min(s + 3, 10)] + 0.5 * V[s] else "sauter" for s in range(10)]
    return V[0], pol

Ici on minimise un coût (temps) : le « max » de Bellman devient un « min ». Sauter vaut 1,5 cases par pas en moyenne contre 0,6 : sauter presque partout, sauf près du but où dépasser ne coûte rien (10 est absorbant).

def apprendre(algo, episodes=500, eps=0.1, alpha=0.5, gamma=1.0):
    Q = {(i, j): np.zeros(4) for i in range(H) for j in range(W)}; chutes = 0
    choisir = lambda s: int(rng.integers(4)) if rng.random() < eps else int(np.argmax(Q[s]))
    for _ in range(episodes):
        s = DEP; a = choisir(s); fini = False
        while not fini:
            s2, r, fini, chute = pas_falaise(s, a); chutes += chute; a2 = choisir(s2)
            cible = r + (0 if fini else gamma * (Q[s2][a2] if algo == "sarsa" else Q[s2].max()))
            Q[s][a] += alpha * (cible - Q[s][a]); s, a = s2, a2
    return Q, chutes

def reinforce_critique(iters=4000, lr=0.1):
    theta = np.zeros((3, 3)); V = np.zeros(3)
    for _ in range(iters):
        c = rng.integers(3); p = np.exp(theta[c]) / np.exp(theta[c]).sum(); a = rng.choice(3, p=p)
        r = R[c, a] + rng.normal(0, 0.3); g = -p; g[a] += 1
        theta[c] += lr * g * (r - V[c]); V[c] += 0.05 * (r - V[c])
    c = 0; p = np.ones(3) / 3; b = R[c].mean(); sans, avec = [], []          # variance de l'estimateur sous la politique uniforme
    for _ in range(2000):
        a = rng.choice(3, p=p); r = R[c, a] + rng.normal(0, 0.3); g = -p[0] + (a == 0)
        sans.append(g * r); avec.append(g * (r - b))
    return theta, V, float(np.var(sans)), float(np.var(avec))

γ petit : myope, ignore la charge lointaine et se contente d’éviter les trous. γ proche de 1 : planifie loin. α grand : bruyant, oscille. ε = 0 : se bloque sur le premier chemin trouvé. Récompense par pas positive : le robot apprend à ne jamais arriver (il collecte +0,05 indéfiniment) — c’est le piratage de récompense le plus simple. Glisse 0,4 : la politique optimale longe les bords loin des trous, quitte à faire plus de pas.

cx, cv = np.meshgrid(np.linspace(-0.3, 0.3, 8), np.linspace(-2, 2, 8))
def f(s): return np.exp(-((s[0] - cx.ravel()) / 0.1)**2 - ((s[1] - cv.ravel()) / 0.7)**2)
FORCES = [-5, 0, 5]; w = np.zeros(64); theta = np.zeros((64, 3)); gamma = 0.98; durees = []
for ep in range(600):
    s = np.array([rng.uniform(-0.05, 0.05), 0.0]); k = 0
    while k < 200 and abs(s[0]) < 0.3:
        fs = f(s); p = np.exp(theta.T @ fs - (theta.T @ fs).max()); p /= p.sum()
        a = int(rng.choice(3, p=p)); s2 = pendule_pas(s, FORCES[a]); fini = abs(s2[0]) >= 0.3
        r = 1.0; delta = r + (0 if fini else gamma * w @ f(s2)) - w @ fs        # erreur TD = avantage
        w += 0.02 * delta * fs
        grad = -p; grad[a] += 1; theta += 0.02 * delta * np.outer(fs, grad)
        s = s2; k += 1
    durees.append(k)
print("durée moyenne des 50 derniers épisodes :", np.mean(durees[-50:]))

Après quelques centaines d’épisodes, la politique apprise pousse à droite quand θ > 0 ou θ̇ > 0 : elle a redécouvert la structure d’un régulateur PD, sans connaître la physique. Avec un réseau et PPO, la même recette fait marcher un robot à 12 moteurs.

def mcts(env, racine, simulations=200, gamma=0.95, c=1.4, horizon=30):
    N, W = {}, {}                                                # visites et somme des retours par (état, action)
    def deroulement(s, k):
        G, fac = 0.0, 1.0
        for _ in range(k):
            if env.terminal(s): break
            s, r, _ = env.pas(s, int(rng.integers(4))); G += fac * r; fac *= gamma
        return G
    for _ in range(simulations):
        s, chemin, fac, G = racine, [], 1.0, 0.0
        for prof in range(horizon):
            if env.terminal(s): break
            n_s = sum(N.get((s, a), 0) for a in range(4))
            if any((s, a) not in N for a in range(4)):
                a = [a for a in range(4) if (s, a) not in N][0]; N[(s, a)] = 0; W[(s, a)] = 0.0
                s2, r, _ = env.pas(s, a); chemin.append((s, a, fac)); G += fac * r; fac *= gamma
                G += fac * deroulement(s2, horizon - prof); break                    # extension + simulation
            a = max(range(4), key=lambda a: W[(s, a)] / N[(s, a)] + c * math.sqrt(math.log(n_s + 1) / N[(s, a)]))
            s2, r, _ = env.pas(s, a); chemin.append((s, a, fac)); G += fac * r; fac *= gamma; s = s2
        for s_, a_, fac_ in chemin:                                   # rétropropagation
            N[(s_, a_)] += 1; W[(s_, a_)] += G
    return max(range(4), key=lambda a: N.get((racine, a), 0))

s, G, k, fini = (0, 0), 0.0, 0, False
while not fini and k < 50:
    a = mcts(env, s); s, r, fini = env.pas(s, a); G += 0.95**k * r; k += 1
print("MCTS : retour", round(G, 2), "en", k, "pas")

MCTS planifie en ligne à partir d’un simulateur, sans apprentissage ; il est fort quand on peut simuler beaucoup. Un réseau appris guide la sélection (politique) et remplace les déroulements aléatoires (valeur) : l’arbre devient étroit et profond. Réciproquement, MCTS produit des cibles d’entraînement meilleures que le réseau seul : la boucle d’auto-amélioration d’AlphaZero. L’article (Silver et al., 2017, Nature) est lisible avec les outils de ce module.