Arbitrez entre exploration et exploitation

Vous êtes à Rennes et vous connaissez une bonne crêperie. Ce soir, y retournez-vous, ou tentez-vous celle qui vient d’ouvrir rue Saint-Michel ? Si vous retournez toujours au même endroit, vous ne découvrirez jamais mieux. Si vous testez sans cesse de nouvelles adresses, vous mangerez souvent mal. Ce dilemme entre exploiter ce que l’on sait et explorer pour en savoir plus est au cœur de l’apprentissage par renforcement sans modèle.

Dans ce chapitre, vous allez l’étudier dans sa forme la plus simple, le bandit manchot, puis découvrir les stratégies classiques pour le résoudre. Elles serviront telles quelles dans les algorithmes du chapitre suivant.

Le bandit manchot, un MDP à un seul état

Un site web peut afficher trois bannières publicitaires, A, B et C. Chacune a un taux de clic inconnu. À chaque visiteur, le site choisit une bannière et observe une récompense : 1 si le visiteur clique, 0 sinon. Le but est de maximiser le nombre total de clics sur 5 000 visiteurs.

C’est un problème de bandit manchot à plusieurs bras (multi-armed bandit), du nom des machines à sous à levier. On peut le voir comme un MDP avec un seul état : chaque décision est indépendante des précédentes, il n’y a pas de conséquence à long terme, seulement une récompense immédiate. C’est donc le cas idéal pour étudier l’exploration, débarrassé de toute la mécanique de Bellman.

La valeur d’une action est ici simplement sa récompense moyenne, $q(a) = \mathbb{E}[r \mid a]$, c’est-à-dire le taux de clic de la bannière. L’agent l’estime par la moyenne des récompenses observées, notée $Q(a)$, et la met à jour au fil de l’eau :

$$Q(a) \leftarrow Q(a) + \frac{1}{N(a)} \big( r - Q(a) \big)$$

où $N(a)$ est le nombre de fois où la bannière $a$ a été affichée (compté en incluant l’affichage en cours). Vous reconnaissez la moyenne incrémentale du chapitre 5.

Dans notre simulation, les vrais taux de clic sont 2 % pour A, 5 % pour B et 8 % pour C. L’agent, lui, ne les connaît pas.

Pourquoi la stratégie gloutonne échoue

La stratégie la plus naturelle est gloutonne (greedy) : afficher toujours la bannière dont l’estimation $Q(a)$ est la plus haute. Que se passe-t-il ?

Au départ, toutes les estimations valent 0. L’agent affiche A (la première, par convention en cas d’égalité). Tant que personne ne clique, $Q(A)$ reste à 0, à égalité avec les autres, et l’agent continue d’afficher A. Dès qu’un visiteur clique, $Q(A)$ devient positif et dépasse les autres, qui valent toujours 0. L’agent affichera alors A pour toujours, sans jamais essayer B ni C.

Dans notre simulation (moyenne sur 200 répétitions), la stratégie gloutonne obtient environ 100 clics sur 5 000 visiteurs, soit le taux de la plus mauvaise bannière, et n’affiche jamais la meilleure. Un agent qui aurait connu les taux dès le départ aurait affiché C à tout le monde, pour environ 400 clics.

Piège

Une estimation n’est révisée que si l’on essaie l’action. Une stratégie purement gloutonne peut donc se bloquer définitivement sur une action médiocre, simplement parce qu’une mauvaise estimation initiale n’est jamais corrigée. Sans exploration, pas d’apprentissage.

La stratégie ε-greedy

La parade la plus simple s’appelle ε-greedy (epsilon-glouton) : on choisit la meilleure action connue la plupart du temps, mais, avec une petite probabilité $\varepsilon$, on choisit une action au hasard.

$$\pi(a) = \begin{cases} 1 - \varepsilon + \dfrac{\varepsilon}{\lvert A \rvert} & \text{si } a = \arg\max_b Q(b) \\[2mm] \dfrac{\varepsilon}{\lvert A \rvert} & \text{sinon} \end{cases}$$

• $\varepsilon \in [0, 1]$ est la probabilité d’explorer ;
• $\lvert A \rvert$ est le nombre d’actions ; le tirage au hasard peut aussi retomber sur la meilleure action, d’où le terme $\varepsilon / \lvert A \rvert$ dans les deux cas.

Avec $\varepsilon = 0{,}1$ et trois bannières, la meilleure bannière estimée est affichée avec probabilité $0{,}9 + 0{,}1/3 \approx 0{,}933$, et chacune des deux autres avec probabilité $0{,}1/3 \approx 0{,}033$. Toutes les actions sont essayées une infinité de fois, donc toutes les estimations finissent par converger vers les vrais taux.

La part d'exploration ε est répartie également entre les trois bannières ; la meilleure estimée reçoit en plus toute la part d'exploitation, 1 − ε.

Le défaut d’un $\varepsilon$ fixe ? Même quand l’agent a parfaitement identifié la meilleure bannière, il continue d’en afficher une mauvaise une fois sur quinze. On fait donc souvent décroître $\varepsilon$ au fil du temps : beaucoup d’exploration au début, quand on ne sait rien, puis de moins en moins. Des choix courants sont $\varepsilon_t = 1/\sqrt{t}$, ou une décroissance linéaire de 1 à 0,05 sur une partie de l’apprentissage.

import math
import random

TAUX = [0.02, 0.05, 0.08]          # taux de clic réels, inconnus de l'agent

def simuler(strategie, n_visiteurs=5000, epsilon=0.1):
    Q = [0.0, 0.0, 0.0]            # taux de clic estimés
    N = [0, 0, 0]                  # nombre d'affichages de chaque bannière
    clics = 0
    for t in range(1, n_visiteurs + 1):
        if strategie == "glouton":
            eps = 0.0
        elif strategie == "epsilon":
            eps = epsilon
        else:                                            # "decroissant"
            eps = 1 / math.sqrt(t)
        if random.random() < eps:
            a = random.randrange(3)                      # exploration
        else:
            a = max(range(3), key=lambda b: Q[b])        # exploitation
        r = 1 if random.random() < TAUX[a] else 0        # le visiteur clique-t-il ?
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]                        # moyenne incrémentale
        clics += r
    return clics, N[2] / n_visiteurs

random.seed(1)
for strategie in ["glouton", "epsilon", "decroissant"]:
    res = [simuler(strategie) for _ in range(200)]       # 200 simulations par stratégie
    clics = sum(c for c, _ in res) / len(res)
    part = sum(p for _, p in res) / len(res)
    print(f"{strategie:12s} clics moyens {clics:6.1f}, part de la meilleure bannière {part:.0%}")

Le résultat, avec cette graine :

Stratégie	Clics moyens (sur 5 000)	Part des affichages de C
Gloutonne	99,6	0 %
ε-greedy, $\varepsilon = 0{,}1$	354,4	77 %
ε-greedy décroissant, $\varepsilon_t = 1/\sqrt{t}$	351,3	72 %
(référence : toujours C)	environ 400	100 %

Explorer un peu fait passer de 100 à plus de 350 clics. Sur cet horizon court, les deux versions d’ε-greedy se valent. Sur un horizon plus long (50 000 visiteurs), la version décroissante prend un léger avantage, car elle cesse peu à peu de gaspiller des affichages.

La stratégie gloutonne reste bloquée sur A et plafonne à 99,6 clics ; les deux ε-greedy suivent de près la référence (354,4 et 351,3) parce qu'elles finissent par afficher C la plupart du temps.

À retenir

Pour apprendre, il faut explorer ; pour gagner, il faut exploiter. La stratégie ε-greedy choisit une action au hasard avec probabilité $\varepsilon$ et la meilleure action connue sinon. On fait généralement décroître $\varepsilon$ : on explore beaucoup au début, puis on exploite de plus en plus.

Explorer plus intelligemment

ε-greedy explore à l’aveugle : quand il explore, il choisit aussi bien une action manifestement mauvaise et bien connue qu’une action prometteuse et encore peu testée. D’autres stratégies dirigent mieux l’exploration.

Les valeurs initiales optimistes

Au lieu d’initialiser les estimations à 0, on les initialise à une valeur plus haute que tout ce qui est possible (par exemple $Q(a) = 1$ pour un taux de clic). Même un agent glouton va alors essayer toutes les actions : chacune le « déçoit » à son tour, son estimation baisse, et il passe à la suivante. C’est une astuce simple et efficace au début de l’apprentissage, mais elle n’explore plus du tout une fois les estimations redescendues.

UCB : l’optimisme face à l’incertitude

La méthode UCB (upper confidence bound, borne supérieure de confiance) choisit l’action qui maximise une estimation optimiste de sa valeur :

$$a_t = \arg\max_{a} \left[ Q(a) + c \sqrt{\frac{\ln t}{N(a)}} \right]$$

• $Q(a)$ est la moyenne observée ;
• $N(a)$ est le nombre de fois où $a$ a été choisie, et $t$ le nombre total de choix ;
• $c > 0$ règle la force de l’exploration (la version classique UCB1 prend $c = \sqrt{2}$).

Le bonus $c\sqrt{\ln t / N(a)}$ est grand pour une action peu essayée : on lui accorde le bénéfice du doute. À mesure qu’on l’essaie, $N(a)$ grandit et le bonus fond. Une action n’est donc explorée que si elle pourrait encore être la meilleure. Il faut toutefois régler $c$ à l’échelle des récompenses : avec des taux de clic de quelques pourcents, un bonus calibré pour des récompenses entre 0 et 1 surexplore longtemps.

Le bonus fond comme 1/√N(a) : une action peu essayée reçoit le bénéfice du doute. Mais avec c = √2, il reste bien plus grand que les écarts de taux de clic (bande ambrée), d'où la surexploration.

Softmax : explorer proportionnellement à la valeur

La stratégie softmax (ou de Boltzmann) tire les actions avec une probabilité qui croît avec leur valeur estimée :

$$\pi(a) = \frac{\exp\big(Q(a) / \tau\big)}{\sum_{b} \exp\big(Q(b) / \tau\big)}$$

où $\tau > 0$ est la température. Une température élevée rend les choix presque uniformes (beaucoup d’exploration) ; une température basse les rend presque gloutons. Contrairement à ε-greedy, une action très mauvaise est rarement choisie, même en exploration.

Avec les taux de clic comme valeurs, la température règle tout : à τ = 0,001 le choix est quasi glouton, vers τ = 1 il devient presque uniforme. Entre les deux, A est choisie moins souvent que B.

Stratégie	Idée	Avantage	Limite
Gloutonne	toujours la meilleure estimée	simple	se bloque sur une action médiocre
ε-greedy	au hasard avec probabilité $\varepsilon$	simple, universelle	explore à l’aveugle
Valeurs optimistes	tout surestimer au départ	aucune aléa nécessaire	n’explore qu’au début
UCB	bonus pour les actions peu essayées	exploration dirigée	bonus à calibrer, plus délicat en MDP
Softmax	probabilité croissante avec $Q$	évite les actions très mauvaises	température à régler

En entretien

« Le dilemme exploration-exploitation, c’est choisir entre la meilleure action connue et une action moins connue qui pourrait être meilleure. Sans exploration, l’agent peut rester bloqué sur une politique médiocre. La solution la plus simple est ε-greedy avec un ε qui décroît ; UCB fait mieux en explorant en priorité les actions encore incertaines. »

Du bandit au MDP

Dans un MDP, le dilemme est le même, mais avec une difficulté de plus : explorer ne coûte pas seulement une récompense immédiate, cela change aussi les états visités ensuite. Au lac gelé, un pas d’exploration à côté d’un trou peut terminer l’épisode.

Les algorithmes du chapitre suivant, SARSA et Q-learning, utilisent presque toujours une politique ε-greedy par rapport à leur estimation de $Q(s, a)$ : la même formule qu’ici, appliquée dans chaque état. Deux conditions garantissent en théorie qu’ils trouvent la politique optimale : toutes les paires (état, action) doivent être essayées une infinité de fois, et la politique doit devenir gloutonne à la limite. Un $\varepsilon$ qui décroît vers 0, ni trop vite ni trop lentement, remplit ces deux conditions (on parle de politique GLIE, pour greedy in the limit with infinite exploration).

Les applications de la version « bandit » sont nombreuses en data science : tests A/B adaptatifs (envoyer progressivement plus de trafic vers la meilleure variante), recommandation, choix de prix, essais cliniques adaptatifs. Quand le choix dépend du profil du visiteur, on parle de bandit contextuel.

En résumé

• Le dilemme exploration-exploitation oppose l’usage de la meilleure action connue et l’essai d’actions moins connues qui pourraient être meilleures.
• Le bandit manchot est un MDP à un seul état ; la valeur d’une action y est sa récompense moyenne, estimée par une moyenne incrémentale.
• La stratégie gloutonne peut se bloquer définitivement : dans notre simulation, environ 100 clics contre plus de 350 avec ε-greedy.
• ε-greedy explore au hasard avec probabilité $\varepsilon$ ; on fait souvent décroître $\varepsilon$ au fil du temps.
• Les valeurs optimistes, UCB et softmax dirigent mieux l’exploration vers les actions prometteuses ou incertaines.
• Dans un MDP, SARSA et Q-learning utilisent ces stratégies état par état ; la convergence demande d’explorer indéfiniment tout en devenant glouton à la limite.

Exercices

Exercice · Probabilités d'une politique ε-greedy

facile

Au lac gelé, l’agent utilise une politique ε-greedy avec $\varepsilon = 0{,}2$ sur les 4 actions. Dans l’état courant, ses estimations sont $Q = (0{,}1 ; 0{,}4 ; 0{,}3 ; 0{,}0)$ pour gauche, bas, droite, haut. Quelle est la probabilité de chaque action ?

Voir la solution

L’action gloutonne est « bas » ($Q = 0{,}4$). Elle est choisie avec probabilité $1 - 0{,}2 + 0{,}2/4 = 0{,}85$. Chacune des trois autres est choisie avec probabilité $0{,}2/4 = 0{,}05$. On vérifie : $0{,}85 + 3 \times 0{,}05 = 1$.

En code

Python

import numpy as np

def probas_epsilon_greedy(Q, eps):
    p = np.full(len(Q), eps / len(Q))       # part de l'exploration, pour chaque action
    p[np.argmax(Q)] += 1 - eps              # l'action gloutonne récupère le reste
    return p

p = probas_epsilon_greedy(np.array([0.1, 0.4, 0.3, 0.0]), eps=0.2)
print(p, round(p.sum(), 3))                 # [0.05 0.85 0.05 0.05] 1.0

R

probas_epsilon_greedy <- function(Q, eps) {
  p <- rep(eps / length(Q), length(Q))    # part de l'exploration, pour chaque action
  p[which.max(Q)] <- p[which.max(Q)] + 1 - eps
  p
}

p <- probas_epsilon_greedy(c(0.1, 0.4, 0.3, 0), eps = 0.2)
p; sum(p)                                  # 0.05 0.85 0.05 0.05 ; 1

Exercice · Appliquer UCB

moyen

Après 550 visiteurs, les estimations et nombres d’affichages des trois bannières sont : A, $Q = 0{,}03$ et $N = 100$ ; B, $Q = 0{,}06$ et $N = 400$ ; C, $Q = 0{,}05$ et $N = 50$. Quelle bannière la stratégie gloutonne afficherait-elle ? Et UCB1 ($c = \sqrt{2}$) ? Commentez.

Voir la solution

La stratégie gloutonne prend la plus grande estimation : B ($0{,}06$).

Pour UCB1, on calcule $Q(a) + \sqrt{2 \ln 550 / N(a)}$, avec $\ln 550 \approx 6{,}31$ :

• A : $0{,}03 + \sqrt{12{,}62 / 100} \approx 0{,}03 + 0{,}355 = 0{,}385$ ;
• B : $0{,}06 + \sqrt{12{,}62 / 400} \approx 0{,}06 + 0{,}178 = 0{,}238$ ;
• C : $0{,}05 + \sqrt{12{,}62 / 50} \approx 0{,}05 + 0{,}502 = 0{,}552$.

UCB choisit C : son estimation est un peu plus basse que celle de B, mais elle repose sur seulement 50 affichages, et la vraie valeur de C pourrait être nettement plus haute. On remarque aussi que les bonus (de 0,18 à 0,50) écrasent les écarts entre taux de clic (quelques centièmes) : avec des récompenses aussi petites, il faudrait réduire $c$ pour ne pas explorer trop longtemps.

En code

Python

import numpy as np

bannieres = np.array(["A", "B", "C"])
Q = np.array([0.03, 0.06, 0.05])
N = np.array([100, 400, 50])
t, c = N.sum(), np.sqrt(2)                    # t = 550

bonus = c * np.sqrt(np.log(t) / N)
print(bannieres[np.argmax(Q)])                # gloutonne : B
print((Q + bonus).round(3))                   # [0.385 0.238 0.552]
print(bannieres[np.argmax(Q + bonus)])        # UCB1 : C

R

bannieres <- c("A", "B", "C")
Q <- c(0.03, 0.06, 0.05)
N <- c(100, 400, 50)
t <- sum(N); c <- sqrt(2)                    # t = 550

ucb <- Q + c * sqrt(log(t) / N)
bannieres[which.max(Q)]                      # gloutonne : "B"
round(ucb, 3)                                # 0.385 0.238 0.552
bannieres[which.max(ucb)]                    # UCB1 : "C"

Exercice · Mesurer le regret

difficile

On appelle regret la différence entre la récompense qu’aurait obtenue un agent omniscient (qui affiche toujours la meilleure bannière) et celle obtenue réellement.

1. À partir du tableau de la simulation, estimez le regret moyen de la stratégie gloutonne et de ε-greedy ($\varepsilon = 0{,}1$) sur 5 000 visiteurs.
2. Avec $\varepsilon$ fixe, même après avoir parfaitement identifié C, l’agent explore encore. Quelle part des affichages va à C à long terme ? Quel regret moyen par visiteur subsiste alors ? Que dire du regret total quand le nombre de visiteurs tend vers l’infini ?

Voir la solution

1. L’agent omniscient obtient en moyenne $5\,000 \times 0{,}08 = 400$ clics. Regret glouton : $400 - 99{,}6 \approx 300$ clics. Regret ε-greedy : $400 - 354{,}4 \approx 46$ clics.
2. À long terme, C est affichée avec probabilité $0{,}9 + 0{,}1/3 \approx 0{,}933$, et A et B chacune avec probabilité $0{,}033$. Chaque affichage de A coûte $0{,}08 - 0{,}02 = 0{,}06$ clic, chaque affichage de B coûte $0{,}03$. Le regret par visiteur vaut donc environ $0{,}033 \times 0{,}06 + 0{,}033 \times 0{,}03 = 0{,}003$ clic. Il est constant : le regret total croît linéairement avec le nombre de visiteurs. C’est pourquoi on fait décroître $\varepsilon$, ou qu’on utilise UCB, dont le regret ne croît que comme le logarithme du nombre de visiteurs.

En code

Python

import numpy as np

taux = np.array([0.02, 0.05, 0.08])
n = 5000
omniscient = n * taux.max()                     # 400 clics
print(round(omniscient - 99.6, 1), round(omniscient - 354.4, 1))   # regret : 300.4 et 45.6

# epsilon fixe à 0.1, C déjà identifiée
eps = 0.1
p = np.full(3, eps / 3)
p[2] += 1 - eps                                 # [0.033 0.033 0.933]
regret_par_visiteur = np.sum(p * (taux.max() - taux))
print(p.round(3), round(regret_par_visiteur, 4))   # 0.003 clic par visiteur
print([round(regret_par_visiteur * m) for m in (10**4, 10**5, 10**6)])   # [30, 300, 3000]

R

taux <- c(0.02, 0.05, 0.08)
n <- 5000
omniscient <- n * max(taux)                  # 400 clics
c(omniscient - 99.6, omniscient - 354.4)     # regret : 300.4 et 45.6

# epsilon fixe à 0.1, C déjà identifiée
eps <- 0.1
p <- rep(eps / 3, 3); p[3] <- p[3] + 1 - eps  # 0.033 0.033 0.933
regret_par_visiteur <- sum(p * (max(taux) - taux))
round(regret_par_visiteur, 4)                  # 0.003 clic par visiteur
round(regret_par_visiteur * c(1e4, 1e5, 1e6))  # 30 300 3000 : croissance linéaire