Online Price Competition under Generalized Linear Demands

Résumé Technique : Compétition sur les Prix en Ligne sous Demandes Linéaires Généralisées

Formulation du Problème
Le document traite du problème de la compétition séquentielle sur les prix entre $N$ vendeurs opérant sur un horizon temporel fini $T$. Contrairement aux modèles monopolistiques traditionnels ou aux modèles compétitifs antérieurs supposant une demande linéaire, ce travail considère un cadre de demande linéaire généralisée (modèle à indice unique). Pour chaque vendeur $i$, la demande attendue est modélisée par :
$$\lambda_i(p) = \mu_i(\langle \theta_{i,0}, p \rangle) = \mu_i(-\beta_{i,0}p_i + \langle \gamma_{i,0}, p_{-i} \rangle)$$
où :

• $p$ est le vecteur des prix fixés simultanément par tous les vendeurs.
• $\mu_i$ est une fonction de lien connue, strictement croissante (par exemple, logistique pour des résultats binaires, identité pour le cas linéaire).
• $\theta_{i,0}$ est un vecteur de paramètres inconnus contenant la sensibilité au propre prix du vendeur ($-\beta_{i,0}$) et la sensibilité aux prix des concurrents ($\gamma_{i,0}$).
• Les observations de la demande $y_i(t)$ suivent une distribution de la famille exponentielle canonique conditionnée par les prix.

Structure de l'Information et Contraintes
Le cadre est caractérisé par une asymétrie d'information spécifique, distincte du Multi-Agent Reinforcement Learning (MARL) standard :

1. Observabilité Partielle : Chaque vendeur n'observe que sa propre demande réalisée (ou son propre revenu) et les prix fixés par ses rivaux. Ils n'observent pas les demandes ou revenus réalisés par les concurrents.
2. Mouvements Simultanés : Les vendeurs choisissent leurs prix simultanément. Par conséquent, un vendeur n'observe le contexte (prix des rivaux $p_{-i}$) qu' après avoir choisi sa propre action $p_i$, créant une asymétrie de temporalité qui empêche l'application des analyses classiques de bandits contextuels où le contexte est observé avant la sélection de l'action.
3. Absence de Coordination : La politique doit être entièrement décentralisée ; les vendeurs ne peuvent pas coordonner leurs phases d'exploration.

Méthodologie : PML-GLUCB
Les auteurs proposent PML-GLUCB (Penalized Maximum Likelihood Generalized Linear Upper Confidence Bound), un algorithme décentralisé qui élimine le besoin d'une phase d'exploration initiale coordonnée et frontale. La méthode fonctionne comme suit :

1. Estimation par Maximum de Vraisemblance Pénalisée (PMLE) : À chaque tour $t$, le vendeur $i$ met à jour son estimation de $\theta_{i,0}$ en maximisant une fonction de log-vraisemblance pénalisée basée sur les données historiques $(p(s), y_i(s))_{s < t}$. Pour garantir que l'estimateur reste dans l'espace paramétrique borné $\Theta_i$, une étape de projection est appliquée si le PMLE brut dépasse la borne de norme.
2. Prix Optimiste (UCB) : Au lieu d'une stratégie pure de type "explorer puis s'engager" (explore-then-commit), l'algorithme utilise une approche de Borne Supérieure de Confiance (UCB). Le vendeur construit une estimation optimiste de la fonction de revenu en ajoutant un bonus de confiance à la recette estimée. Le bonus est dérivé d'une inégalité de concentration adaptée au modèle linéaire généralisé, utilisant une borne de potentiel elliptique adaptée aux mouvements simultanés.
3. Mise à jour de la Meilleure Réponse : Le vendeur sélectionne le prix $p_i(t)$ qui maximise cette fonction de revenu optimiste, étant donné les prix observés des concurrents lors du tour précédent (ou du tour actuel selon la temporalité spécifique de mise à jour dans l'algorithme, bien que le texte souligne que $p_{-i}$ est observé après le choix de $p_i$ dans le cadre général, l'algorithme utilise $p(t-1)_{-i}$ pour la décision à $t$).

Principales Contributions

1. Apprentissage sans Exploration Frontale : Le papier introduit une politique qui apprend et optimise simultanément sans nécessiter de phase initiale d'exploration par tirage i.i.d. aléatoire. Cela répond aux limites pratiques où "expérimenter avec les prix" est souvent irréalisable et évite la dépendance à des constantes spécifiques au problème nécessaires pour déterminer la longueur de l'exploration dans les travaux antérieurs.
2. Généralisation des Modèles de Demande : Le cadre généralise strictement les modèles de demande linéaire existants pour inclure une large classe de modèles à indice unique non linéaires et monotones. Il unifie l'analyse de la demande binaire (achat/non-achat) et des observations de demande continues sous un même parapluie théorique.
3. Nouveaux Outils de Concentration : En raison de la nature des mouvements simultanés du jeu, les lemmes de potentiel elliptique standards (qui supposent un contexte exogène) ne peuvent être directement appliqués. Les auteurs dérivent une nouvelle borne de type elliptique (Lemme C.2) adaptée aux contextes endogènes observés avec un retard par rapport à l'action.

Résultats

• Borne de Regret : Par rapport à un benchmark dynamique (la meilleure réponse à la séquence des prix des rivaux dans le passé), chaque vendeur atteint une borne de regret de :
  $$\text{Reg}_i(T) = \tilde{O}(N^2 \sqrt{T})$$
  Cela correspond au taux optimal $\tilde{O}(\sqrt{T})$ connu pour la tarification compétitive linéaire, à l'exclusion des facteurs logarithmiques et de la dépendance au nombre de vendeurs $N$.
• Convergence vers l'Équilibre : L'algorithme garantit que l'écart quadratique moyen du vecteur de prix par rapport au vecteur de prix de l'Équilibre de Nash (NE) décroît comme :
  $$\frac{1}{T} \sum_{t=1}^T \mathbb{E}[\|p(t) - p^*\|_2^2] = \tilde{O}\left(\frac{N^2}{\sqrt{T}}\right)$$
  Cela indique que le jeu à regret optimal maintient le marché proche de l'équilibre de Nash en moyenne.
• Complexité Computationnelle : L'algorithme est calculable de manière efficace, avec une complexité par tour de $O(N^2)$ par vendeur (dominée par les mises à jour de matrices et les produits vectoriels), ce qui le rend scalable pour un $N$ modéré.

Signification et Revendications
Le papier affirme que PML-GLUCB est ordre-optimal (minimax optimal à un facteur logarithmique près) dans le cadre linéaire généralisé. En supprimant l'exigence d'une exploration coordonnée, la méthode s'aligne davantage sur les conditions de marché réelles où les entreprises agissent de manière indépendante et ne peuvent pas pré-engager de calendriers d'exploration. Ce travail comble le fossé entre l'apprentissage de la demande théorique et la mise en œuvre pratique dans des environnements compétitifs dotés de structures de demande non linéaires.

Les auteurs notent que si la dépendance en $\sqrt{T}$ est optimale, la dépendance en $N^2$ vis-à-vis du nombre de vendeurs reste une question ouverte quant à sa précision. De plus, le papier reconnaît que si l'écart moyen par rapport à l'équilibre est contrôlé, la convergence ponctuelle de la séquence de prix vers le NE n'est pas garantie sans une phase d'exploration i.i.d. initiale, ce qui est cohérent avec la littérature plus large sur les algorithmes de bandits adaptatifs.