La plupart des annonces que vous voyez sont choisies par un modèle d'apprentissage par renforcement. Voici comment cela fonctionne

Chaque jour, les agences de publicité numérique diffusent des milliards d'annonces sur les sites Web d'actualités, les moteurs de recherche, les réseaux sociaux, les sites Web de streaming vidéo et d'autres plates-formes. Et ils veulent tous répondre à la même question: laquelle des nombreuses publicités qu'ils ont dans leur catalogue est plus susceptible d'attirer un certain spectateur? Trouver la bonne réponse à cette question peut avoir un impact énorme sur les revenus lorsque vous traitez avec des centaines de sites Web, des milliers d'annonces et des millions de visiteurs.

Heureusement (pour les agences de publicité, au moins), [19659003] l'apprentissage par renforcement la branche de l'intelligence artificielle devenue réputée pour la maîtrise des jeux de société et vidéo apporte une solution. Les modèles d'apprentissage par renforcement cherchent à maximiser les récompenses. Dans le cas des publicités en ligne, le modèle RL essaiera de trouver l'annonce sur laquelle les utilisateurs sont plus susceptibles de cliquer.

L'industrie de la publicité numérique génère des centaines de milliards de dollars chaque année et fournit une étude de cas intéressante sur les pouvoirs de apprentissage par renforcement.

Tests A / B / n naïfs

Pour mieux comprendre comment l'apprentissage par renforcement optimise les publicités, envisagez un scénario très simple: vous êtes propriétaire d'un site Web d'actualités. Pour payer les frais d'hébergement et de personnel, vous avez conclu un contrat avec une entreprise pour diffuser ses annonces sur votre site Web. L'entreprise vous a fourni cinq annonces différentes et vous versera un dollar chaque fois qu'un visiteur cliquera sur l'une des annonces.

Votre premier objectif est de trouver l'annonce qui génère le plus de clics. Dans le jargon publicitaire, vous voudrez maximiser votre taux de clics (CTR). Le CTR est le ratio de clics sur le nombre d'annonces affichées, également appelé impressions. Par exemple, si 1 000 impressions d'annonces vous rapportent trois clics, votre CTR sera de 3/1 000 = 0,003 ou 0,3 % .

Avant de résoudre le problème de l'apprentissage par renforcement, parlons des tests A / B, la technique standard pour comparer les performances de deux solutions concurrentes (A et B) telles que différentes mises en page de pages Web, recommandations de produits ou publicités. Lorsque vous avez affaire à plus de deux alternatives, cela s'appelle le test A / B / n.

[Lire: Comment créer un gadget compatible avec les animaux? Nous avons demandé aux experts et aux propriétaires d'animaux ]

Dans les tests A / B / n, les sujets de l'expérience sont répartis au hasard en groupes séparés et chacun reçoit l'une des solutions disponibles. Dans notre cas, cela signifie que nous afficherons au hasard l'une des cinq annonces à chaque nouveau visiteur de notre site Web et évaluerons les résultats.

Supposons que nous effectuions notre test A / B / n pour 100 000 itérations, soit environ 20 000 impressions par annonce. Voici le taux de clics sur impression de nos annonces:

Annonce 1: 80/20 000 = 0,40% CTR

Annonce 2: 70/20 000 = 0,35% CTR

Annonce 3: 90/20 000 = 0,45 % CTR

Annonce 4: 62/20 000 = CTR de 0,31%

Annonce 5: 50/20 000 = CTR de 0,25%

Nos 100 000 impressions d'annonces ont généré des revenus de 352 USD avec un CTR moyen de 0,35%. Plus important encore, nous avons découvert que l'annonce numéro 3 fonctionne mieux que les autres, et nous continuerons à l'utiliser pour le reste de nos téléspectateurs. Avec l'annonce la moins performante (annonce numéro 2), nos revenus auraient été de 250 USD. Avec l'annonce la plus performante (annonce numéro 3), nos revenus auraient été de 450 USD. Ainsi, notre test A / B / n nous a fourni la moyenne des revenus minimum et maximum et nous a permis d'obtenir la connaissance très précieuse des taux de CTR que nous recherchions.

Les publicités numériques ont des taux de conversion très faibles. Dans notre exemple, il existe une légère différence de 0,2% entre nos annonces les plus performantes et les moins performantes. Mais cette différence peut avoir un impact significatif sur l'échelle. À 1 000 impressions, l'annonce numéro 3 générera 2 $ supplémentaires par rapport à l'annonce numéro 5. À un million d'impressions, cette différence deviendra 2 000 $. Lorsque vous diffusez des milliards d'annonces, un subtil 0,2 % peut avoir un impact énorme sur les revenus.

Par conséquent, il est très important de trouver ces différences subtiles dans l'optimisation des annonces. Le problème avec les tests A / B / n est qu'il n'est pas très efficace pour trouver ces différences. Il traite toutes les annonces de la même manière et vous devez exécuter chaque annonce des dizaines de milliers de fois jusqu'à ce que vous découvriez leurs différences à un niveau de confiance fiable. Cela peut entraîner une perte de revenus, en particulier lorsque vous disposez d'un catalogue d'annonces plus volumineux.

Un autre problème avec les tests A / B / n classiques est qu'ils sont statiques. Une fois que vous avez trouvé l'annonce optimale, vous devrez vous y tenir. Si l'environnement change en raison d'un nouveau facteur (saisonnalité, tendances des actualités, etc.) et fait que l'une des autres publicités a un CTR potentiellement plus élevé, vous ne le saurez que si vous exécutez le test A / B / n partout.

Et si nous pouvions changer les tests A / B / n pour les rendre plus efficaces et dynamiques?

C'est là que l'apprentissage par renforcement entre en jeu. Un agent d'apprentissage par renforcement commence par ne rien savoir des actions, récompenses et pénalités de son environnement. L'agent doit trouver un moyen de maximiser ses récompenses.

Dans notre cas, les actions de l'agent RL sont l'une des cinq annonces à afficher. L'agent RL recevra un point de récompense chaque fois qu'un utilisateur clique sur une annonce. Il doit trouver un moyen de maximiser les clics sur les annonces.

Le bandit multi-armé

Le Le bandit multi-armé doit trouver des moyens de découvrir l'une des nombreuses solutions par essais et erreurs

Dans certains environnements d'apprentissage par renforcement, les actions sont évaluées en séquences. Par exemple, dans les jeux vidéo, vous devez effectuer une série d'actions pour atteindre la récompense, qui consiste à terminer un niveau ou à gagner un match. Mais lors de la diffusion d'annonces, le résultat de chaque impression d'annonce est évalué indépendamment; il s’agit d’un environnement en une seule étape.

Pour résoudre le problème d’optimisation des publicités, nous utiliserons un «bandit multi-armé» (MAB), un algorithme d’apprentissage par renforcement adapté à l’apprentissage par renforcement en une seule étape. Le nom du bandit multi-armé vient d'un scénario imaginaire dans lequel un joueur se tient devant une rangée de machines à sous. Le joueur sait que les machines ont des taux de victoire différents, mais il ne sait pas laquelle offre la récompense la plus élevée.

S'il s'en tient à une machine, il risque de perdre la chance de sélectionner la machine avec le taux de victoire le plus élevé. Par conséquent, le joueur doit trouver un moyen efficace de découvrir la machine avec la récompense la plus élevée sans utiliser trop de ses jetons.

L'optimisation des publicités est un exemple typique d'un problème de bandit multi-armé. Dans ce cas, l'agent d'apprentissage par renforcement doit trouver un moyen de découvrir l'annonce avec le CTR le plus élevé sans gaspiller trop d'impressions d'annonces précieuses sur des annonces inefficaces.

Exploration vs exploitation

L'un des problèmes rencontrés par chaque modèle d'apprentissage par renforcement est le défi «exploration vs exploitation». L'exploitation signifie s'en tenir à la meilleure solution que l'agent RL a trouvée jusqu'à présent. L'exploration signifie essayer d'autres solutions dans l'espoir d'atterrir sur celle qui est meilleure que la solution optimale actuelle.

Dans le contexte de la sélection d'annonces, l'agent d'apprentissage par renforcement doit décider entre choisir l'annonce la plus performante et explorer d'autres options.

] Une solution au problème d'exploitation-exploration est l'algorithme «epsilon-gourmand» (ε-gourmand). Dans ce cas, le modèle d'apprentissage par renforcement choisira la meilleure solution la plupart du temps, et dans un pourcentage spécifié des cas (le facteur epsilon), il choisira l'une des annonces au hasard.

Chaque algorithme d'apprentissage par renforcement doit trouver le bon équilibre entre l'exploitation de solutions optimales et l'exploration de nouvelles options

Voici comment cela fonctionne dans la pratique. Supposons que nous ayons un agent MAB epsilon gourmand avec le facteur ε fixé à 0,2. Cela signifie que l'agent choisit l'annonce la plus performante 80 % du temps et explore d'autres options 20% du temps.

Le modèle d'apprentissage par renforcement démarre sans savoir laquelle des annonces fonctionne le mieux, donc il attribue à chacun d'eux une valeur égale. Lorsque toutes les annonces sont égales, il en choisit une au hasard chaque fois qu'il souhaite diffuser une annonce.

Après avoir diffusé 200 annonces (40 impressions par annonce), un utilisateur clique sur l'annonce numéro 4. L'agent ajuste le CTR. des annonces comme suit:

Annonce 1: 0/40 = 0,0%

Annonce 2: 0/40 = 0,0%

Annonce 3: 0/40 = 0,0%

Annonce 4: 1 / 40 = 2,5%

Annonce 5: 0/40 = 0,0%

Maintenant, l'agent pense que l'annonce numéro 4 est l'annonce la plus performante. Pour chaque nouvelle impression d'annonce, il choisira un nombre aléatoire entre 0 et 1. Si le nombre est supérieur à 0,2 (le facteur ε), il choisira le numéro d'annonce 4. S'il est inférieur à 0,2, il choisira l'une des autres annonces à

Maintenant, notre agent exécute 200 autres impressions d'annonces avant qu'un autre utilisateur ne clique sur une annonce, cette fois sur l'annonce numéro 3. Notez que sur ces 200 impressions, 160 appartiennent à l'annonce numéro 4, car c'était l'annonce optimale. Le reste est également réparti entre les autres annonces. Nos nouvelles valeurs de CTR sont les suivantes:

Annonce 1: 0/50 = 0,0%

Annonce 2: 0/50 = 0,0%

Annonce 3: 1/50 = 2,0%

Annonce 4: 1/200 = 0,5%

Annonce 5: 0/50 = 0,0%

L'annonce optimale devient désormais le numéro d'annonce 3. Elle obtiendra 80 % des impressions d'annonces. Supposons qu'après 100 impressions supplémentaires (80 pour l'annonce numéro trois, quatre pour chacune des autres annonces), quelqu'un clique sur l'annonce numéro 2. Voici à quoi ressemble la nouvelle répartition du CTR:

Annonce 1: 0/54 = 0,0 %

Annonce 2: 1/54 = 1,8%

Annonce 3: 1/130 = 0,7%

Annonce 4: 1/204 = 0,49%

Annonce 5: 0/54 = 0,0% [19659002] Maintenant, l'annonce numéro 2 est la solution optimale. Au fur et à mesure que nous diffusons plus d'annonces, les CTR refléteront la valeur réelle de chaque annonce. La meilleure annonce obtiendra la part du lion des impressions, mais l'agent continuera d'explorer d'autres options. Par conséquent, si l'environnement change et que les utilisateurs commencent à montrer des réactions plus positives à une certaine annonce, l'agent RL peut la découvrir.

Après avoir diffusé 100 000 annonces, notre distribution peut ressembler à ceci:

Annonce 1: 123 / 30 600 = 0,40% CTR

Annonce 2: 67/18 900 = 0,35% CTR

Annonce 3: 187/41 400 = 0,45% CTR

Annonce 4: 35/11 300 = 0,31% CTR

Annonce 5 : 15/5 800 = 0,26% CTR

Avec l'algorithme ε-gourmand, nous avons pu augmenter nos revenus de 352 $ à 426 $ sur 100 000 impressions d'annonces et un CTR moyen de 0,42%. C'est une grande amélioration par rapport au modèle de test A / B / n classique.

Amélioration de l'algorithme ε-gourmand

La ​​clé de l'algorithme d'apprentissage par renforcement ε-gourmand est l'ajustement du facteur epsilon. Si vous le définissez trop bas, il exploitera l'annonce qu'il juge optimale au détriment de ne pas trouver une solution éventuellement meilleure. Par exemple, dans l'exemple que nous avons exploré ci-dessus, l'annonce numéro quatre génère le premier clic, mais à long terme, elle n'a pas le CTR le plus élevé. Les petites tailles d'échantillon ne représentent pas nécessairement de vraies distributions.

D'un autre côté, si vous définissez le facteur epsilon trop haut, votre agent RL gaspillera trop de ressources à explorer des solutions non optimales.

Une façon d'améliorer le L'algorithme epsilon-gourmand consiste à définir une politique dynamique. Lorsque le modèle MAB est récent, vous pouvez commencer avec une valeur epsilon élevée pour faire plus d'exploration et moins d'exploitation. Au fur et à mesure que votre modèle diffuse plus d'annonces et obtient une meilleure estimation de la valeur de chaque solution, il peut réduire progressivement la valeur epsilon jusqu'à ce qu'elle atteigne une valeur seuil.

Dans le contexte de notre problème d'optimisation des annonces, nous pouvons commencer par un epsilon de 0,5 et réduisez-le de 0,01 toutes les 1 000 impressions d'annonces jusqu'à ce qu'il atteigne 0,1.

Une autre façon d'améliorer notre bandit multi-armé est de donner plus de poids aux nouvelles observations et de réduire progressivement la valeur des observations plus anciennes. Cela est particulièrement utile dans les environnements dynamiques tels que les publicités numériques et les recommandations de produits, où la valeur des solutions peut évoluer au fil du temps.

Voici une manière très simple de procéder. La manière classique de mettre à jour le CTR après avoir diffusé une annonce est la suivante:

(result + past_results) / impressions

Here, result is le résultat de l'annonce affichée (1 si vous avez cliqué dessus, 0 si vous n'avez pas cliqué dessus), past_results est le nombre cumulé de clics sur l'annonce jusqu'à présent, et impressions est le nombre total de fois où l'annonce a été diffusée.

Pour atténuer progressivement les anciens résultats, nous ajoutons un nouveau facteur alpha (entre 0 et 1), et effectuez le changement suivant:

(result + past_results * alpha) / impressions

Ce petit changement donnera plus de poids aux nouvelles observations. Par conséquent, si vous avez deux annonces concurrentes qui ont un nombre égal de clics et d'impressions, celles dont les clics sont les plus récents seront favorisées par votre modèle d'apprentissage par renforcement. De plus, si une annonce avait un taux de CTR très élevé dans le passé mais ne répond plus ces derniers temps, sa valeur diminuera plus rapidement dans ce modèle, obligeant le modèle RL à passer plus tôt à d'autres alternatives et gaspiller moins de ressources sur l'annonce inefficace.

Ajout de contexte au modèle d'apprentissage par renforcement

Les bandits contextuels utilisent l'approximation des fonctions pour tenir compte des caractéristiques individuelles des téléspectateurs d'annonces

À l'ère d'Internet, les sites Web, les médias sociaux et les applications mobiles ont beaucoup d'informations sur chaque utilisateur telles que leur emplacement géographique, le type d'appareil et l'heure exacte de la journée à laquelle ils regardent l'annonce. Les entreprises de médias sociaux ont encore plus d'informations sur leurs utilisateurs, y compris l'âge et le sexe, les amis et la famille, le type de contenu qu'ils ont partagé dans le passé, le type de messages qu'ils ont aimé ou sur lesquels ils ont cliqué dans le passé, et plus encore.

Cette riche information donne à ces entreprises la possibilité de personnaliser les publicités pour chaque spectateur. Mais le modèle de bandit multi-armé que nous avons créé dans la section précédente montre la même publicité à tout le monde et ne prend pas en compte les caractéristiques spécifiques de chaque spectateur. Et si nous voulions ajouter du contexte à notre bandit multi-armé?

Une solution est de créer plusieurs bandits multi-armés, chacun pour un sous-domaine spécifique d'utilisateurs. Par exemple, nous pouvons créer des modèles RL distincts pour les utilisateurs d'Amérique du Nord, d'Europe, du Moyen-Orient, d'Asie, d'Afrique, etc. Et si nous voulions également prendre en compte le sexe? Ensuite, nous aurions un modèle d'apprentissage par renforcement pour les femmes en Amérique du Nord, un pour les hommes en Amérique du Nord, un pour les femmes en Europe, les hommes en Europe, etc. Maintenant, ajoutez des tranches d'âge et des types d'appareils, et vous pouvez voir qu'il deviendra rapidement un gros problème, créant une explosion de bandits multi-armés qui deviendront difficiles à entraîner et à entretenir.

Une solution alternative consiste à utiliser un «bandit contextuel», une version améliorée du bandit multi-armé qui prend en compte les informations contextuelles. Au lieu de créer un MAB distinct pour chaque combinaison de caractéristiques, le bandit contextuel utilise « l'approximation de la fonction », qui tente de modéliser les performances de chaque solution en fonction d'un ensemble de facteurs d'entrée.

Sans aller trop loin dans les détails (qui pourraient faire l'objet d'un autre article), notre bandit contextuel utilise l'apprentissage automatique supervisé pour prédire les performances de chaque annonce en fonction de l'emplacement, du type d'appareil, du sexe, de l'âge, etc. L'avantage du bandit contextuel est qu'il utilise un modèle d'apprentissage automatique par annonce au lieu de créer un MAB par combinaison de caractéristiques.

Ceci conclut notre discussion sur l'optimisation des publicités avec l'apprentissage par renforcement. Les mêmes techniques d'apprentissage par renforcement peuvent être utilisées pour résoudre de nombreux autres problèmes, tels que la recommandation de contenu et de produits ou la tarification dynamique, et sont utilisées dans d'autres domaines tels que les soins de santé, l'investissement et la gestion de réseau. Cet article a été initialement publié par Ben Dickson sur TechTalks une publication qui examine les tendances technologiques, comment elles affectent la façon dont nous vivons et faisons des affaires, et les problèmes qu'elles résolvent. Mais nous discutons également du côté pervers de la technologie, des implications plus sombres des nouvelles technologies et de ce que nous devons surveiller. Vous pouvez lire l'article original ici .

Publié le 28 février 2021 – 16:00 UTC