Les enchères en RTB vues sous le prisme de la recherche en machine learning

La publicité en ligne est une motivation centrale de la recherche en machine learning depuis une décennie. Elle prend une ampleur considérable depuis les années 2010 (depuis un boom en 2014, les dépenses globales en RTB ne cessent d’augmenter) et donne lieu à des collectes de données exploitables par les annonceurs comme par les éditeurs. En particulier, le Search Engine Advertising (SEA) et la publicité en RTB sont opérés grâce à différentes formes d’enchères : pour le premier, les keyword auctions, et pour le second, des enchères au premier ou au second prix historiquement. Alors que les différents mécanismes d’enchères intéressent depuis longtemps les théoriciens des jeux, le choix d’enchères en RTB ou en SEA pose un problème d’une nouvelle teneur. En effet, les enchères sont désormais répétées, et chaque acteur peut apprendre des données historisées pour ajuster sa stratégie.

Du point de vue des annonceurs, cette question du choix d’enchères est d’autant plus cruciale aujourd’hui dans un contexte où l’amélioration du processus de bidding (encore majoritairement manuel) pourrait permettre de compenser des pertes d’efficacité de ciblage liées aux problématiques cookieless.

De façon simplifiée, une enchère en RTB se déroule ainsi :

• Un emplacement publicitaire est mis aux enchères par un éditeur
• Les annonceurs placent leurs enchères
• Si le prix qu’il a proposé est au-dessus du prix de réserve fixé par l’éditeur, l’annonceur ayant proposé l’enchère la plus haute gagne le droit d’afficher la bannière de son choix.
• Il paie un prix qui dépend du modèle d’enchère en place :

– Le prix proposé ou un prix de réserve fixé par l’éditeur, si le prix proposé est trop bas pour une enchère au premier prix (majoritaire aujourd’hui),

– Le second plus haut prix ou un prix de réserve fixé par l’éditeur, si le second plus haut prix est trop bas pour une enchère au second prix.

• Il observe la réaction de l’utilisateur à la bannière (un clic, un achat, ou rien de tout ça) et en tire une certaine valeur.

L’objectif, lorsque l’on se place du côté de l’annonceur, est donc d’apprendre à proposer une enchère optimale.

Le feedback lié au RTB est particulier : lorsqu’un annonceur perd une enchère, il n’apprend rien de la valeur que lui aurait rapporté l’emplacement (similairement, en cas de prix de réserve trop haut, l’éditeur n’apprend rien de la distribution des prix proposés par les annonceurs). Ainsi, une fois l’enchère finie, le joueur ne connaît pas nécessairement la récompense qui aurait été attribuée en proposant un bid différent (respectivement, un prix de réserve différent, dans le cas de l’éditeur). Ce modèle de feedback fait penser à celui des bandits manchots (voir ici pour une introduction douce), où l’on observe uniquement la récompense liée à l’action choisie.
Le modèle des bandits a donc été souvent associé au problème du choix de bid optimal.

On peut faire deux sortes d’hypothèses sur la valeur de l’emplacement et sur les bids proposés par les autres annonceurs. L’hypothèse la plus simple est que ces deux quantités sont des variables aléatoires tirées d’une même loi de façon indépendante : c’est l’hypothèse “iid” (Online learning for Repeated Auctions, Real-time bidding with side information, Efficient Algorithms for Stochastic Repeated Second-price Auctions). Elle implique en particulier que la façon de jouer de l’annonceur principal n’a aucune influence sur l’environnement. On peut aussi supposer que ces variables peuvent être arbitraires : c’est l’hypothèse adversariale (Online learning for Repeated Auctions, Learning to Bid without Knowing your Value). Cette dernière hypothèse conduit à des stratégies beaucoup plus défensives.
D’autre part, les bids concurrents peuvent être supposés observés : à chaque coup, uniquement dans certains cas, ou jamais.

Un modèle plus élaboré considère que l’annonceur dispose aussi de données de contexte (sur l’utilisateur ou l’emplacement) dont la récompense dépend de façon linéaire. (Real-time bidding with side information).

La façon la plus simple de résoudre le problème du choix d’enchères est de considérer qu’on a le choix entre un nombre fini de valeurs de bids et d’ignorer la structure de feedback particulière au RTB. On peut ainsi utiliser n’importe quel algorithme de bandits à K bras. Les limites de cette approche sont les suivantes :

• En réalité le nombre de choix de bids possibles est immense, ce qui implique que l’exploration durerait trop longtemps
• C’est se priver d’une grande partie de l’information. Lorsque l’enchère est gagnée, on sait que tout bid supérieur aurait également gagné, et on connaît la valeur qu’il aurait rapporté. On connaît donc la récompense associée à tout bid supérieur. De la même façon, lorsque l’on a perdu, on connaît la récompense associée à tout bid inférieur.

Les enchères au second prix ont été prédominantes dans le RTB jusqu’à l’année 2018 environ. Elles ont peu à peu été remplacées par les enchères au premier prix, avec l’introduction du header bidding¹. La prédominance historique des enchères au second prix n’explique pourtant qu’en partie la concentration des recherches sur ce type d’enchères. En effet, l’étude des enchères au second prix est beaucoup plus simple, du fait que ces enchères incitent à proposer une enchère égale à la valeur du placement (on dit qu’elles sont truthful). Les bids des concurrents n’ont alors que peu d’influence sur la façon d’enchérir d’annonceurs rationnels, et il suffit d’apprendre la valeur de l’emplacement pour se rapprocher du bid optimal. Au contraire, lors d’enchères au premier prix, le bid optimal dépend du bid des autres autant que de la valeur de l’emplacement.

La question centrale est de trouver une façon d’équilibrer l’exploration, qui se matérialise par des bids hauts permettant d’apprendre la valeur, et l’exploitation, qui se matérialise par des bids proches du bid optimal estimé (soit de la valeur estimée dans le cas du second prix).

Dans les modélisations iid, on va donc utiliser des algorithmes proches d’UCB ou de linUCB² dans le cas contextuel (les stratégies les plus classiques pour des bandits à K bras et des bandits linéaires) qui proposent en tant que bid des bornes supérieures de confiance du bid optimal.

Dans les modélisations adversariales (Online learning for Repeated Auctions, Learning to Bid without Knowing your Value), des méthodes plus proches d’Exp3 (pour les bandits adversariaux) ont été développées. Le passage d’un choix entre un nombre de bids finis à un choix entre des bids continus est alors plus complexe.

La problématique du choix de bid a donné lieu à plusieurs modélisations différentes, dont beaucoup sont liées au modèle de bandits. Chez Numberly, nous nous sommes penchés sur un modèle stochastique “iid”, dans Efficient Algorithms for Stochastic Repeated Second-price Auctions et Fast Rate Learning in Stochastic First Price Bidding. Ces articles montrent, entre autres, qu’il est possible de mettre en œuvre des algorithmes qui tirent parti de la structure des enchères pour obtenir des performances bien meilleures que celles d’algorithmes génériques. Le modèle choisi est certes très simple, mais il est à nos yeux assez proche de la réalité. Cependant, certaines limites n’ont pas été prises en compte : le délai entre l’impression d’une bannière et le clic ou l’achat, ou le comportement d’algorithmes qui ne nécessitent pas la mise à jour de la stratégie à chaque enchère par exemple.

• Learning in repeated auctions
• Online learning for Repeated Auctions
• Real-time bidding with side information
• Efficient Algorithms for Stochastic Repeated Second-price Auctions
• Fast Rate Learning in Stochastic First Price Bidding
• Learning to Bid without Knowing your Value
• Optimal No regret Learning in Repeated First-price Auctions

¹ Le header bidding est une technique permettant de mettre en concurrence plusieurs ad-exchanges sur les inventaires choisis
² UCB (pour Upper Confidence Bound) est un algorithme classique pour les bandits à K bras d’abord proposé par Auer et qui consiste à choisir le bras dont la borne supérieure de confiance sur la récompense est la plus haute. LinUCB (voir ici) en est une généralisation au cas contextuel.