Résumé Technique : Tarification Dynamique Non Stationnaire avec Adaptivité et Optimalité

1. Formulation du Problème

Le papier traite du problème de la tarification dynamique contextuelle sous non-stationnarité. Une entreprise vend des produits à $T$ consommateurs arrivant séquentiellement. À chaque instant $t$, un vecteur de contexte $z_t \in \mathbb{R}^d$ (encodant les informations sur le produit et le consommateur) est observé. L'entreprise fixe un prix $p_t \in [l, u]$ et observe une réponse de la demande $y_t$.

Le modèle de demande est supposé être un Modèle Linéaire Généralisé (GLM) avec un paramètre inconnu $\theta_t \in \mathbb{R}^{2d}$ qui évolue au fil du temps. Plus précisément, l'espérance de la demande est donnée par :
$$\mathbb{E}[y_t | x_t, \theta_t] = \psi'(x_t^\top \theta_t) = \psi'(z_t^\top \alpha_t - (z_t^\top \beta_t)p_t)$$
où $x_t = (z_t^\top, -p_t z_t^\top)^\top$.

Le défi central est que la séquence de paramètres $\{\theta_t\}_{t=1}^T$ est non stationnaire et sa nature est inconnue de l'entreprise. Le papier considère deux régimes distincts de non-stationnarité :

1. Non-stationnarité structurée : Les paramètres sont par morceaux constants avec $s_T - 1$ points de rupture abrupts inconnus.
2. Non-stationnarité non structurée : Les paramètres varient de manière fluide ou arbitraire, sous réserve d'un budget de variation totale $V_T$.

L'objectif est de concevoir une politique de tarification qui minimise le regret, défini comme la perte de revenus cumulée par rapport à un agent clairvoyant qui connaîtrait la séquence réelle $\{\theta_t\}$ et le prix optimal $p_t^*$ à chaque étape. Crucialement, l'algorithme doit être adaptatif, ce qui signifie qu'il doit atteindre une performance optimale sans connaissance préalable de la nature de l'environnement (structuré ou non), ni de la valeur spécifique de $s_T$ ou $V_T$.

2. Méthodologie : Algorithme MCP-DP

Les auteurs proposent l'algorithme Multiscale Change-Point Detection based Dynamic Pricing (MCP-DP). L'algorithme opère par époques, lesquelles sont ensuite partitionnées en blocs dyadiques. Au sein de chaque bloc, il combine une stratégie Explore-Then-Commit (ETC) avec un nouveau Schéma d'Échantillonnage Multi-échelle (MSS) et un Test de Rapport de Vraisemblance (LRT).

Composantes Clés :

• Estimation du Modèle de Référence : Au début d'un bloc, l'algorithme estime un paramètre de référence $\hat{\theta}$ en utilisant l'Estimation du Maximum de Vraisemblance (MLE) à partir d'un ensemble d'exploration de prix accumulé dans le bloc précédent.
• Exploration de Prix Localisée : Au lieu d'un échantillonnage de prix uniforme, MCP-DP utilise un schéma de perturbation localisé autour du prix gourmand $p^*(z_t, \hat{\theta})$. Cela réduit le regret pendant l'exploration tout en maintenant la validité statistique (en garantissant que la matrice de design reste bien conditionnée).
• Ordonnancement Multi-échelle (MSS) : Pour détecter des changements d'amplitude et de timing inconnus, le MSS planifie de manière aléatoire des intervalles d'exploration de prix de longueurs (échelles) variables au sein de chaque bloc. Les intervalles plus courts sont échantillonnés plus fréquemment pour détecter les changements abrupts et importants, tandis que les intervalles plus longs détectent les dérives graduelles et légères.
• Test de Rapport de Vraisemblance (LRT) : À la fin de chaque intervalle d'exploration programmé, l'algorithme effectue un LRT comparant le modèle de référence $\hat{\theta}_{pre}$ contre une nouvelle MLE $\hat{\theta}_J$ ajustée sur cet intervalle.
  • La statistique de test est $\Lambda_J(\hat{\theta}_{pre}) = L_J(\hat{\theta}_{pre}) - L_J(\hat{\theta}_J)$.
  • Si la statistique dépasse un seuil $\gamma \propto d \log(dT)$, l'algorithme suppose qu'un changement significatif a eu lieu, termine l'époque actuelle et redémarre avec une nouvelle époque.
• Adaptivité : La nature multi-échelle de l'exploration permet à l'algorithme de gérer simultanément les changements abrupts (structurés) et les variations fluides (non structurées) sans avoir besoin de connaître le régime spécifique ou les paramètres ($s_T, V_T$) à l'avance.

3. Contributions Clés

1. L'Algorithme MCP-DP et les Bornes de Regret

Le papier introduit MCP-DP, le premier algorithme de tarification dynamique prouvé comme étant adaptatif à la fois à la non-stationnarité structurée et non structurée.

• Borne Supérieure de Regret : L'algorithme atteint un regret de l'ordre de :
  $$\tilde{O}\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$
  Cette borne représente le taux "best-of-both-worlds", égalant les taux optimaux pour les contextes purement structurés et purement non structurés simultanément.
• Aucune Connaissance Préalable : L'algorithme ne nécessite pas la connaissance du nombre de points de rupture $s_T$, du budget de variation $V_T$, de la taille minimale du changement, ou des longueurs de segments.

2. Budget de Variation Ajusté au Design

Les auteurs introduisent un nouveau concept appelé budget de variation ajusté au design ($V_T$). Contrairement aux budgets de variation existants qui mesurent la distance brute entre les paramètres $\|\theta_t - \theta_{t-1}\|$, $V_T$ pondère la variation par la distribution du contexte (spécifiquement la matrice de design $\Sigma_z$).

• Signification : Cela fournit une caractérisation plus fine de la non-stationnarité dans les contextes. Cela capture l'intuition selon laquelle les changements de paramètres dans des directions rarement représentées par le contexte $z_t$ ont moins d'impact sur la demande et le regret. Cette définition généralise et resserre les bornes existantes dans la littérature.

3. Bornes Inférieures Minimax

Le papier établit une nouvelle borne inférieure minimax pour la tarification dynamique contextuelle non stationnaire :
$$\Omega\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$

• Dépendance à la Dimensionnalité : C'est la première borne inférieure dans la littérature de la tarification dynamique qui caractérise explicitement la dépendance à la dimension du contexte $d$ pour les cas structurés et non structurés.
• Nouveauté Technique : La preuve utilise une nouvelle construction basée sur le lemme d'Assouad pour gérer la dimension divergente $d$ lorsque $T \to \infty$, reliant le regret à un problème de classification multiple.

4. Fondations Théoriques et Statistiques

• Bornes de la MLE à Haute Probabilité : Les auteurs dérivent une nouvelle borne supérieure à haute probabilité sur l'erreur de prédiction de la MLE pour un mélange de GLM sous non-stationnarité. Ce résultat est d'intérêt indépendant et soutient l'optimalité du LRT.
• Le LRT comme Substitut de Regret : Le papier prouve que la statistique du LRT sert de substitut au regret d'exploitation non observé, permettant à l'algorithme de détecter un excès de regret sans connaître les paramètres réels.

4. Résultats et Validation Empirique

Des expériences numériques approfondies ont été menées sur des modèles de demande linéaires et logistiques avec des dimensions de contexte ($d$) et des horizons temporels ($T$) variables.

• Paramètres de Référence (Baselines) : MCP-DP a été comparé à CPDP (optimisé pour les changements abrupts) et MWDP (optimisé pour les changements fluides).
  • Dans les contextes stationnaires, MCP-DP a égalé la performance de CPDP et a surpassé MWDP.
  • Dans les contextes de changements abrupts, MCP-DP a égalé CPDP.
  • Dans les contextes de changements fluides, MCP-DP a égalé MWDP.
  • Crucialement, MCP-DP a maintenu une performance robuste à travers tous les régimes sans réglage, là où les modèles de référence ont échoué lorsque l'environnement ne correspondait pas à leurs hypothèses spécifiques.
• Contextes Complexes : Dans des scénarios de changements adverses (où le calendrier fixe de CPDP échoue) ou de budgets/comptages de changements divergents, MCP-DP a démontré une robustesse supérieure et un regret plus faible par rapport aux références non adaptatives.
• Validation du Budget Ajusté au Design : Des expériences avec différents contextes (Z1 vs Z2) ont confirmé que la performance de MCP-DP reste stable lorsqu'elle est mesurée par rapport au budget ajusté au design, alors que les budgets de variation $L_2$ standards n'ont pas réussi à expliquer cette stabilité.

5. Signification et Revendications

Le papier affirme combler un fossé de longue date dans la littérature de la tarification dynamique. Les travaux antérieurs sur la tarification non stationnaire étaient non adaptatifs, nécessitant des algorithmes distincts pour les changements abrupts versus fluides, et exigeaient souvent la connaissance de l'ampleur des changements ou des budgets.

• Premier Algorithme Adaptatif : MCP-DP est présenté comme le premier algorithme capable d'atteindre des taux de regret optimaux pour la non-stationnarité structurée et non structurée dans un cadre unique et adaptatif sans nécessiter de connaissance préalable de la nature du changement ($s_T$ ou $V_T$).
• Optimalité : L'algorithme est montré comme étant minimax optimal (à un facteur logarithmique près), correspondant aux nouvelles bornes inférieures dérivées.
• Avancée Méthodologique : Ce travail souligne que la littérature existante sur les bandits adaptatifs (ex: switching bandits) ne peut pas être directement appliquée à la tarification dynamique contextuelle en raison de l'espace d'action continu et du fait que le "meilleur bras" (prix optimal) change avec le contexte. L'approche proposée basée sur le LRT répond spécifiquement à cela en suivant le regret de la politique de tarification par rapport à la distribution du contexte.

Les auteurs notent que bien que le présent travail suppose des contextes stochastiques, l'extension de la méthode aux contextes adverses demeure une direction future, car le succès actuel du LRT repose sur la nature stochastique de la matrice de design.