📊 statistics

Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

Cet article introduit un algorithme piloté par les données pour un problème d'assortiment dynamique bilatéral avec des paramètres de choix inconnus des deux côtés, atteignant un regret polylogarithmique optimal en termes de taux en apprenant simultanément les préférences des clients et des vendeurs tout en maximisant les revenus de la plateforme.

Auteurs originaux : Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

Publié 2026-06-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez une place de marché numérique en pleine effervescence, comme une version technologique d'un marché de producteurs ou une application de rencontre. Vous avez deux groupes de personnes : des Clients (qui veulent acheter des services) et des Vendeurs (qui veulent les fournir). Votre tâche est de décider quels Vendeurs présenter à chaque Client qui franchit la porte.

Ce document traite d'un problème très complexe : vous ne savez pas ce que les gens aiment.

Le Problème Central : La Place de Marché du "Blind Date"

Dans la plupart des plateformes en ligne, le système essaie de deviner ce que les clients veulent. Mais dans le scénario de ce document, la plateforme est aveugle de deux manières :

Elle ne sait pas ce que les Clients veulent : Certains clients adorent les installateurs solaires ; d'autres préfèrent les rédacteurs indépendants. La plateforme ne sait pas quel type de client arrive ensuite.
Elle ne sait pas ce que les Vendeurs veulent : Même si un client choisit un vendeur, ce vendeur peut dire "Non merci". Peut-être que le vendeur déteste travailler avec ce type spécifique de client. La plateforme ignore également ces préférences.

C'est comme une mise en scène de "blind date" où l'entremetteur ne sait pas ce que l'homme aime, et ne sait pas non plus ce que la femme aime. Si l'homme choisit la femme, elle pourrait quand même le rejeter. Si l'entremetteur apprend seulement ce que l'homme aime mais ignore ce que la femme aime, il continuera de proposer de mauvais rendez-vous.

Le Cycle des Événements

Le document décrit un rythme spécifique dans lequel fonctionne cette place de marché :

L'Arrivée : Un client arrive.
Le Menu : La plateforme lui présente une petite liste (un "assortiment") de vendeurs.
La Proposition : Le client choisit un vendeur de la liste (ou aucun).
La Revue : Le vendeur reçoit un lot de propositions. Tous les quelques jours (un "cycle"), le vendeur examine les propositions et choisit au plus un client avec qui travailler.
La Récompense : La plateforme n'est payée (ou obtient un "match") que si le client a choisi le vendeur ET que le vendeur a choisi le client.

Le Défi : Apprendre tout en Agissant

Le gestionnaire de la plateforme doit prendre des décisions maintenant sans connaître l'avenir. Il doit déterminer :

"Quel type de vendeur le Type de Client A aime-t-il ?"
"Quels types de clients le Type de Vendeur B accepte-t-il ?"

Si la plateforme continue de montrer toujours les mêmes vendeurs populaires, elle n'apprendra jamais si un nouveau vendeur est en réalité un excellent partenaire pour un type de client spécifique. Mais si elle montre trop de vendeurs aléatoires, elle perd du temps et de l'argent sur de mauvais accords. C'est le classique dilemme "Exploration vs Exploitation".

La Solution : L'Algorithme de "Double Apprentissage" (Two-Way Learning)

Les auteurs ont créé un programme informatique intelligent (un algorithme) appelé TWL-UCB. Voyez cela comme un entremetteur super observateur qui garde un "score de confiance" pour chaque paire possible.

Le Jeu des Devinettes : L'algorithme commence par deviner à quel point les clients et les vendeurs s'apprécient.
Le Test du "Et si ?" : L'algorithme utilise un tour de passe-passe mathématique appelé "Borne Supérieure de Confiance" (Upper Confidence Bound - UCB). Imaginez que l'algorithme joue la prudence mais prend aussi des risques calculés. Il se dit : "Je suis sûr à 90 % que le Client A aime le Vendeur X, mais je ne suis sûr qu'à 50 % concernant le Vendeur Y. Essayons le Vendeur Y juste pour voir, car si j'ai raison, cela pourrait être une victoire énorme !"
La Double Vérification : Contrairement aux méthodes plus anciennes qui ne surveillaient que ce que faisaient les clients, cet algorithme surveille les deux côtés.
- Il met à jour ses suppositions sur ce que les clients aiment chaque fois qu'un client fait un choix.
- Il met à jour ses suppositions sur ce que les vendeurs aiment chaque fois qu'un vendeur accepte ou rejette une proposition.
Le Résultat : Avec le temps, l'algorithme devient incroyablement doué pour prédire la correspondance parfaite, minimisant ainsi le nombre de rendez-vous ratés (le regret).

Les Grandes Découvertes

Les auteurs prouvent trois points principaux à l'aide de mathématiques et de simulations informatiques :

1. Il s'améliore rapidement (Le gain "Polylogarithmique")
Les auteurs ont prouvé que leur algorithme apprend si efficacement que les "erreurs" qu'il commet croissent très lentement au fil du temps. En termes mathématiques, l'erreur croît comme le carré d'un logarithme (une courbe très lente).

Analogie : Imaginez un étudiant passant un examen. La plupart des méthodes d'apprentissage font des erreurs qui s'accumulent comme une colline escarpée. Cet algorithme fait des erreurs qui s'accumulent comme une pente douce. Il apprend les règles du jeu beaucoup plus vite que quiconque.

2. On ne peut pas faire mieux (La "Borne Inférieure")
Les auteurs ont également prouvé qu'aucune autre stratégie possible ne pourrait apprendre significativement plus vite que la leur. Ils ont montré que même un algorithme "parfait" ferait un nombre similaire d'erreurs dans le pire des scénarios.

Analogie : Ils ont prouvé que leur algorithme est le "Médaillé d'Or". Vous ne pouvez pas gagner une course plus vite parce que la piste elle-même est aussi rapide.

3. Plus grand n'est pas forcément mieux (La surprise de la "Taille du Menu")
Ils ont lancé des simulations pour voir ce qui se passe si la plateforme présente une liste immense de vendeurs (un grand menu) par rapport à une liste courte.

Le constat : Une fois que le menu atteint une certaine taille (environ 30 vendeurs dans leur simulation), agrandir le menu n'aide plus beaucoup.
Analogie : Pensez à un menu de restaurant. Si vous avez 5 plats excellents, ajouter 50 autres plats médiocres ne rendra pas le client plus heureux ; cela va simplement le confondre. La plateforme obtient le même nombre de correspondances réussies avec un menu de taille moyenne qu'avec un menu massif.

Pourquoi cela importe

Ce document est le premier à résoudre l'énigme de l'apprentissage simultané des deux côtés d'une place de marché lorsque l'on ignore ce que chacun des deux veut. Il démontre qu'en traitant le problème comme un défi d'apprentissage "à deux voies" plutôt que comme un simple défi de "choix du client", les plateformes peuvent prendre des décisions beaucoup plus intelligentes, plus rapides et plus rentables.

En bref : Pour gérer une place de marché à deux versants avec succès, vous ne pouvez pas seulement deviner ce que l'acheteur veut, vous devez aussi apprendre ce que le vendeur veut. Et si vous faites les deux en même temps avec la bonne mathématique, vous gagnez.

Résumé Technique : Assortiment Dynamique Piloté par les Données dans les Plateformes en Ligne : Apprendre des Deux Côtés

Formulation du Problème
L'article traite d'un problème d'assortiment dynamique de sélection sur une plateforme de services à deux faces opérant sous une information incomplète. Contrairement aux problèmes d'assortiment traditionnels où un décideur sélectionne des produits pour maximiser les revenus en se basant uniquement sur les préférences des clients, ce cadre implique des participants « actifs » tant du côté de la demande (clients) que du côté de l'offre (vendeurs).

Le système fonctionne en temps discret sur un horizon de $T$ périodes. La plateforme gère un ensemble de $N$ vendeurs et rencontre une séquence de clients arrivants présentant des types hétérogènes. À chaque période, le gestionnaire de la plateforme sélectionne un assortiment (un sous-ensemble de vendeurs de taille au plus $B$ ) à afficher à un client arrivant. Le client choisit ensuite au plus un vendeur parmi l'assortiment affiché selon un modèle de choix Multinomial Logit (MNL), régi par des paramètres de préférence inconnus $v_{z,i}$ (où $z$ est le type de client et $i$ le vendeur).

Crucialement, une transaction n'est pas finalisée dès le choix du client. Au lieu de cela, la proposition du client est conservée pendant une durée fixe de $K$ périodes. À la fin de chaque époque (un bloc de $K$ périodes), les vendeurs examinent les propositions qu'ils ont reçues et décident d'accepter ou non au plus un client, sur la base de leurs propres paramètres de préférence MNL inconnus $u_{i,z}$ . Une transaction (et la récompense subséquente) ne se produit que si un vendeur accepte une proposition. L'objectif du gestionnaire de la plateforme est de maximiser la récompense totale attendue sur l'horizon de planification.

Le défi central est l'Apprentissage Bidirectionnel (Two-Way Learning) : la plateforme ne connaît ni les paramètres de choix des clients ( $V$ ) ni ceux des vendeurs ( $U$ ), et doit les apprendre dynamiquement tout en prenant des décisions d'assortiment. Cela diffère de la littérature existante, qui suppose généralement un apprentissage unidirectionnel (seules les préférences des clients sont inconnues) ou une réalisation immédiate des gains.

Méthodologie
Les auteurs proposent un algorithme en ligne piloté par les données nommé TWL-UCB (Two-Way Learning via Upper Confidence Bound). L'algorithme est conçu pour équilibrer l'exploration et l'exploitation tout en gérant la structure de rétroaction asynchrone d'un marché à deux faces.

Estimations par Borne Supérieure de Confiance (UCB) : L'algorithme maintient des estimations UCB pour les paramètres de préférence des clients ( $v_{z,i}$ $v_{z, i}$ ) et des vendeurs ( $u_{i,z}$ $u_{i, z}$ ).
- Mises à jour des Clients (Étape II) : Après chaque période, la plateforme met à jour les estimations des clients sur la base des choix (propositions) observés au sein des assortiments proposés.
- Mises à jour des Vendeurs (Étape III) : Les estimations des vendeurs sont mises à jour uniquement à la fin de chaque époque ( $K$ périodes), sur la base des décisions de correspondance observées (acceptations/rejets) par les vendeurs.
Optimisation de l'Assortiment (Étape I) : À chaque période, la plateforme sélectionne un assortiment qui maximise l'augmentation marginale estimée de l'espérance de correspondances (expected matches). Cette métrique, notée $\Delta_M$ , capture le gain attendu de correspondances pour l'époque actuelle compte tenu de l'état actuel des propositions et des estimations UCB des préférences des clients et des vendeurs.
Minimisation du Regret : La performance est évaluée à l'aide du regret, défini comme la différence entre la récompense totale obtenue par une politique clairvoyante (qui connaît tous les paramètres et les séquences d'arrivées) et la récompense obtenue par l'algorithme proposé.

Résultats Clés et Contributions Théoriques
L'article établit l'optimalité théorique de l'algorithme TWL-UCB en faisant correspondre les bornes supérieures et inférieures du regret :

Borne Supérieure (Théorème 1) : Les auteurs prouvent que le regret dans le pire des cas de l'algorithme TWL-UCB croît de manière polylogarithmique avec le temps : $O(\log^2(NT))$ . Il s'agit d'une amélioration significative par rapport aux bornes de regret en $\tilde{O}(\sqrt{T})$ trouvées dans la littérature existante sur l'assortiment dynamique axée sur l'apprentissage unidirectionnel.
Borne Inférieure (Théorème 2) : L'article dérive une borne inférieure correspondante, montrant que pour toute politique admissible, le regret dans le pire des cas est au moins de l'ordre de $\tilde{\Omega}(\log^2(NT))$ .
Optimalité du Taux : L'alignement des bornes supérieure et inférieure établit que l'algorithme TWL-UCB est optimal en termes de taux pour le problème d'Apprentissage Bidirectionnel.
Résultats de Simulation :
- L'algorithme TWL-UCB surpasse systématiquement les versions adaptées d'algorithmes d'apprentissage unidirectionnel (spécifiquement l'algorithme UCB d'Agrawal et al., 2019) dans les contextes à deux faces. Ces dernières échouent car elles ne peuvent pas prendre en compte la rétroaction différée et l'incertitude du côté des vendeurs.
- L'étude identifie un effet de seuil concernant la taille de l'assortiment : augmenter la taille maximale de l'assortiment ( $B$ ) au-delà d'un certain point (observé autour de 30 dans les simulations) produit des rendements décroissants en termes de récompense totale pour la plateforme.

Extensions et Robustesse
L'article analyse deux extensions pour démontrer la robustesse de l'algorithme :

Transparence de l'Information : L'algorithme maintient sa borne de regret $O(\log^2(NT))$ même si le gestionnaire de la plateforme ne partage que des informations partielles spécifiques aux clients avec les vendeurs (Théorème 3).
Récompenses Dépendantes du Client : La borne de regret est maintenue même lorsque la récompense pour une correspondance réussie dépend du type spécifique de client associé, plutôt que d'une valeur fixe par époque (Théorème 4).

Signification et Revendications
Les auteurs affirment qu'il s'agit de la première étude ayant formulé et analysé un problème d'assortiment dynamique où le décideur doit apprendre simultanément les paramètres de choix des deux côtés d'un marché à deux faces.

La signification de ce travail réside dans :

La Nouveauté du Problème : Dépasser l'apprentissage unidirectionnel vers un cadre d'« Apprentissage Bidirectionnel » qui reflète la nature active des participants dans les plateformes de services modernes (ex. : Airbnb, Upwork, HomeAdvisor).
L'Avancée Algorithmique : Démontrer qu'un regret polylogarithmique est réalisable dans ce contexte complexe de rétroaction différée, alors que les problèmes d'apprentissage unidirectionnel souffrent généralement d'un regret de type racine carrée.
L'Aperçu Pratique : Souligner que les algorithmes conçus pour l'apprentissage unilatéral sont inefficaces dans les environnements à deux faces et que les gestionnaires de plateformes doivent être prudents quant à l'expansion de la taille des assortiments en raison des rendements décroissants.

L'article conclut que l'algorithme TWL-UCB proposé offre une solution théoriquement optimale et robuste pour les gestionnaires de plateformes opérant sous une information incomplète dans des marchés à deux faces.