Module 6 — Exploration : epsilon glouton et alternatives

Le Q-learning du module 5 supposait discrètement qu'une politique $\varepsilon$-gloutonne suffisait à visiter chaque paire $(s, a)$ assez souvent. Cette hypothèse est fausse en général, et c'est même la raison la plus fréquente d'un agent qui « ne converge pas ». Ce module traite l'exploration comme le sujet à part entière qu'elle est.

Le dilemme, formulé proprement

À chaque pas, l'agent doit choisir entre :

• exploiter — jouer l'action qu'il croit la meilleure selon ses estimations actuelles ;
• explorer — jouer une action différente pour affiner ses estimations, quitte à sacrifier un gain immédiat.

Ne jamais explorer garantit de rester sur la meilleure action connue, qui peut être arbitrairement pire que la meilleure action existante. Toujours explorer produit un comportement aléatoire qui ne récolte jamais les fruits de ce qui a été appris. La difficulté est que le bon dosage dépend de ce qu'on ignore encore — et par définition on ne le sait pas.

L'agent brebis : le contre-exemple qui convainc

Un exemple minimal, à deux actions, montre pourquoi l'exploration n'est pas facultative.

Deux bras : le premier donne une récompense de 0,5 à chaque coup. Le second donne 1 avec probabilité 0,9 et 0 avec probabilité 0,1 — donc une récompense moyenne de 0,9. Un agent qui commence par tirer une fois chaque bras et observe (0,5) puis (0) va évaluer le second comme pire et ne le retirera plus jamais. Il a « appris » à jouer le pire bras, et le fera à l'infini.

Sur un MDP, le même phénomène produit une politique qui contourne l'objectif à jamais, parce que l'unique chemin qui y mène passe par un état jamais visité — donc jamais évalué.

Epsilon glouton, la ligne de base

L'approche la plus simple. Avec probabilité $\varepsilon$, jouer une action aléatoire ; sinon, jouer $\arg\max_a Q(s, a)$.

def politique_epsilon_greedy(Q, s, epsilon, nA):
    if np.random.rand() < epsilon:
        return np.random.randint(nA)
    return int(np.argmax(Q[s]))

Trois recettes pratiques.

$\varepsilon$ fixe est simple mais problématique : l'agent continue d'explorer même quand ses estimations sont solides, ce qui plafonne sa performance et empêche la convergence en politique optimale.

Décroissance linéaire ou exponentielle est le standard. Partir de $\varepsilon = 1$ (aléatoire pur), descendre progressivement jusqu'à $\varepsilon_{\min} = 0{,}01$ à $0{,}1$ sur des dizaines de milliers d'épisodes. La formule $\varepsilon \leftarrow \max(\varepsilon_{\min}, \varepsilon \cdot 0{,}9995)$ est un bon point de départ.

Décroissance par nombre de visites — plus rare mais théoriquement propre — utilise $\varepsilon(s) = 1 / \sqrt{n(s)}$ où $n(s)$ est le nombre de visites de l'état $s$. Les états jamais visités restent explorés, les états connus deviennent gloutons.

Ce que epsilon glouton fait mal

Deux défauts qui ouvrent la porte aux alternatives.

L'exploration est uniforme sur les actions. Une action manifestement mauvaise a autant de chances d'être testée qu'une action prometteuse. Sur un espace de 10 actions avec une seule évidemment mauvaise, cela gaspille 10 % de l'exploration.

L'exploration ne tient pas compte de l'incertitude. Une action déjà jouée 1000 fois et une action jamais jouée reçoivent le même traitement, alors que la seconde a bien plus à apprendre.

Softmax, ou exploration proportionnelle à la valeur

Jouer chaque action avec une probabilité qui croît avec son $Q$ estimé :

$$\pi(a \mid s) = \frac{\exp\left(Q(s, a) / \tau\right)}{\sum_b \exp\left(Q(s, b) / \tau\right)}$$

Le paramètre $\tau$ — la température — contrôle le pointu de la distribution. $\tau \to 0$ redonne le glouton pur. $\tau \to \infty$ redonne l'aléatoire uniforme. Une valeur intermédiaire favorise les actions bien notées sans jamais fermer la porte aux autres. C'est plus fin que $\varepsilon$-glouton, mais sensible à l'échelle absolue des $Q$ et donc plus délicat à régler.

UCB : optimisme face à l'incertitude

Une idée puissante venue du problème des bandits. Ajouter à chaque action un bonus qui croît avec l'incertitude :

$$a_t = \arg\max_a \left[Q(s, a) + c \sqrt{\frac{\ln t}{n(s, a)}}\right]$$

où $n(s, a)$ compte le nombre de sélections de $(s, a)$ et $c$ dose l'exploration. Une action peu jouée voit son bonus grandir jusqu'à devenir irrésistible, ce qui force sa sélection ; une fois jouée, le bonus retombe. On teste ainsi systématiquement les actions incertaines, sans jamais rester bloqué sur une évaluation prématurée.

UCB est théoriquement optimal sur les bandits multi-bras. Sur les MDP, sa version simple ci-dessus a des limites (les visites dépendent de la politique) mais l'esprit inspire des méthodes profondes comme les bonus d'exploration ou la curiosité intrinsèque, où l'incertitude est mesurée par un réseau auxiliaire.

Démonstration : exploration trop faible sur FrozenLake

Lancer le Q-learning du module 5 avec $\varepsilon = 0{,}01$ constant dès le départ. Sur FrozenLake glissant, la courbe de récompense stagne à zéro pendant des milliers d'épisodes : l'agent, gloutonneux dès le début, tourne autour du départ sans jamais atteindre l'objectif. Avec $\varepsilon$ décroissant de 1 à 0,05, le même code résout l'environnement en 10 000 à 20 000 épisodes. Un unique hyperparamètre décide de tout.

L'exploration est un problème, pas un détail

En renforcement, un agent qui « ne converge pas » vient plus souvent d'une exploration insuffisante que d'un mauvais algorithme. Avant d'accuser Q-learning, tracer la couverture des paires $(s, a)$ visitées : si des paires restent à zéro alors qu'elles sont accessibles, aucun algorithme ne peut apprendre leur valeur. La bonne réponse est presque toujours plus d'exploration au démarrage, pas un modèle plus complexe.

En résumé

• Le dilemme exploration contre exploitation n'a pas d'analogue supervisé ; ne pas explorer garantit de rester coincé sur la meilleure action connue.
• $\varepsilon$-glouton avec décroissance est le standard ; $\varepsilon$ fixe empêche la convergence.
• Softmax module l'exploration par la valeur ; UCB ajoute un bonus qui reflète l'incertitude.
• Un agent qui « ne converge pas » a le plus souvent une exploration insuffisante ; tracer la couverture $(s, a)$ avant de changer d'algorithme.

Module suivant : quitter le tabulaire, remplacer $Q(s, a)$ par un réseau de neurones et découvrir les instabilités que cela crée.