Résumé Technique : Méthodes à Noyau pour les Inégalités de Prophète Raffinées

1. Énoncé du Problème

L'article traite de l'inégalité de prophète à sélection unique, un problème classique de sélection bayésienne en ligne où un décideur observe séquentiellement des variables aléatoires non négatives indépendantes $X_1, \dots, X_n$ et doit en sélectionner au plus une de manière irrévocable afin de maximiser l'espérance de la valeur par rapport au maximum a posteriori $M = \max_i X_i$.

Alors que les résultats classiques établissent des ratios de compétitivité dans le pire des cas qui sont serrés (par exemple, $1/2$ pour les distributions non identiques et $1-1/e$ pour les distributions IID utilisant des seuils uniques), ces garanties sont dictées par des « instances difficiles » caractérisées par des réalisations extrêmement grandes et rares du maximum. Ces instances présentent souvent une forte dispersion dans la référence du prophète, ce qui peut ne pas refléter les environnements à queue légère courants en pratique (par exemple, les mécanismes de prix affichés).

Les auteurs proposent de raffiner l'analyse du pire des cas en imposant une borne sur la variance relative de la valeur du prophète :
$$\Gamma^2(G) = \frac{\text{Var}(M)}{\mathbb{E}[M]^2} \leq \gamma$$
où $G$ est la distribution de $M$. Ce paramètre $\gamma$ sert de mesure de complexité non paramétrique :

• $\gamma = 0$ : Le maximum est déterministe, permettant à un seuil de récupérer exactement le prophète (ratio 1).
• $\gamma \to \infty$ : La contrainte disparaît, retrouvant les constantes classiques du pire des cas.

L'objectif est de caractériser le ratio de compétitivité optimal d'un seuil unique $C(\gamma)$ à travers trois modèles d'arrivée : IID, Ordre Fixe (indépendant non identique) et Prophète Secrétaire (ordre aléatoire).

2. Méthodologie : Le Cadre à Noyau (Kernel Framework)

La contribution technique centrale est une méthode à noyau qui transforme le problème d'inégalité de prophète en un programme convexe de dimension infinie sur les fonctions de quantiles.

2.1 Représentation par Quantiles

Le problème est reformulé en utilisant la fonction de quantile $Q = G^{-1}$ du maximum $M$. Après avoir normalisé $\mathbb{E}[M] = 1$, la contrainte de variance relative devient une contrainte convexe sur la norme $L^2$ de $Q$ :
$$\int_0^1 Q(u)^2 du \leq 1 + \gamma$$
L'ensemble admissible des fonctions de quantile est noté $\mathcal{Q}_\gamma$.

2.2 Noyau (Kernelization)

L'espérance de la récompense d'un seuil unique, paramétrée par le niveau de quantile maximal $q \in [0, 1]$, est exprimée comme une fonctionnelle linéaire de $Q$ :
$$L_K(Q, q) = \int_q^1 Q(u) K_q(u) du$$
Ici, $K_q(u)$ est un noyau spécifique au modèle d'arrivée. Cette représentation isole la dynamique du modèle dans le noyau, laissant une structure d'optimisation commune. Le ratio du pire des cas est la valeur d'un jeu de noyaux :
$$\text{Val}(\mathcal{Q}_\gamma, K) = \inf_{Q \in \mathcal{Q}_\gamma} \sup_{q \in [0, 1]} L_K(Q, q)$$

2.3 Outils Techniques Clés

1. Dualité Minimax Forte : Sous des conditions d'admissibilité topologique et de quasi-concavité modérées, les auteurs prouvent via le théorème de Sion que :
   $$\inf_{Q} \sup_{q} L_K(Q, q) = \sup_{q} \inf_{Q} L_K(Q, q)$$
   Cette dualité est valable dans l'espace des seuils de quantiles, permettant de résoudre le problème de l'adversaire (minimisation sur $Q$) pour un seuil $q$ fixé.

2. Réduction Variationnelle : Pour le cas de la variance bornée ($\mathcal{Q}_\gamma$), la minimisation interne sur $Q$ est réduite à une famille à un paramètre en utilisant des arguments d'Euler-Lagrange. Le quantile du pire des cas prend la forme :
   $$Q_{q,s}(u) = a_{q,s} + b_{q,s} (K_q(s) - K_q(u))_+$$
   où $s \in [q, 1)$ est un point de contact. Cela réduit le problème de dimension infinie en une optimisation scalaire sur $s$.

3. Réduction aux Points Extrêmes : Pour le modèle à horizon aléatoire (variance non contrainte), le problème se réduit à l'optimisation de fonctions en escalier normalisées (points extrêmes de $\mathcal{Q}_\infty$).

3. Contributions Clés et Résultats

3.1 Modèle IID

Les auteurs dérivent une caractérisation exacte de la courbe de variance bornée $C^2_{\text{IID}}(\gamma)$.

• Résultat : La valeur est donnée par un programme max-min sur une fonction à forme fermée $\psi(q, s)$ (Théorème 2).
• Asymptotique :
  • Lorsque $\gamma \to 0$ : $C^2_{\text{IID}}(\gamma) = 1 - \Theta(\gamma^{1/3} / \log^{2/3}(1/\gamma))$.
  • Lorsque $\gamma \to \infty$ : $C^2_{\text{IID}}(\gamma) = 1 - 1/e + \Theta(1/\gamma)$.
• Implication Algorithmique : La solution duale $q^\star$ fournit un seuil à horizon fini asymptotiquement optimal $T_n = F^{-1}(1 + (\log q^\star)/n)$.

3.2 Modèle à Ordre Fixe

Pour les variables indépendantes non identiques dans un ordre fixe, le noyau est $K^{\text{FO}}_q(u) = q/u^2$.

• Résultat : L'absence de termes logarithmiques dans le noyau permet une solution en forme fermée (Théorème 3) :
  $$C^2_{\text{FO}}(\gamma) = \frac{3 + 2x_\gamma^2}{2(3 + x_\gamma^2)}, \quad \text{où } x_\gamma = 2 \sinh\left(\frac{1}{3} \text{arsinh}\sqrt{\frac{3}{4\gamma}}\right)$$
• Asymptotique : Lorsque $\gamma \to 0$, la convergence vers 1 est de $1 - \Theta(\gamma^{1/3})$, ce qui est légèrement plus lent que le cas IID en raison de l'absence d'amélioration logarithmique.

3.3 Modèle Prophète Secrétaire

Dans ce modèle, la distribution du maximum ne détermine pas uniquement l'instance. La méthode du noyau fournit une borne inférieure calculable (Théorème 4).

• Résultat de Séparation : Une découverte surprenante est que pour toute valeur finie de $\gamma > 0$, le ratio du Prophète Secrétaire est strictement inférieur au ratio IID ($C^2_{\text{PS}}(\gamma) < C^2_{\text{IID}}(\gamma)$), malgré le partage de la même constante de pire des cas non restreinte ($1-1/e$). Ceci est prouvé par la construction d'une décomposition non-IID de la même distribution de maximum qui introduit un « signal de sommet rare » préjudiciable aux seuils uniques.

3.4 Modèle à Horizon Aléatoire

Le cadre est appliqué à des valeurs IID observées jusqu'à un horizon aléatoire $N$ avec une fonction génératrice de probabilité $\phi$.

• Résultat : Une borne inférieure serrée est dérivée : $C_{\text{IID}}(\phi) \geq 1 - \phi(1 - 1/\mu)$.
• Condition : L'égalité est vérifiée si $z \mapsto (1-z)/(1-\phi(z))$ est convexe, une condition satisfaite par les distributions à taux de hasard monotone (MHR) (ex: géométrique, Poisson, binomiale).

4. Signification et Revendications

L'article prétend fournir une alternative systématique aux constructions ad hoc typiquement requises dans la littérature sur les inégalités de prophète. En déplaçant l'attention de l'invention d'instances spécifiques difficiles pour chaque modèle vers la vérification des conditions structurelles d'un noyau correspondant, les auteurs unifient l'analyse de divers modèles d'arrivée.

Les principales revendications concernant la portée de ce travail incluent :

• Raffinement du Pire des Cas : La contrainte de variance relative offre une interpolation non paramétrique entre les instances concentrées et le pire des cas classique, traitant le « pessimisme » des ratios de compétitivité standards.
• Restauration de la Dualité : La formulation par noyau restaure la dualité minimax forte dans l'espace des quantiles, explant pourquoi les règles de quantiles uniformes peuvent atteindre des garanties de type prophète malgré l'échec des garanties max-min dans l'espace primal.
• Caractérisations Exactes : La méthode produit des formules exactes pour la courbe IID et la courbe d'Ordre Fixe, ainsi qu'une séparation stricte entre les modèles IID et Prophète Secrétaire à variance finie.
• Large Applicabilité : La technique s'étend au-delà de la variance relative à des contraintes convexes plus larges (ex: espaces $L^p$, espaces d'Orlicz) et à différents réglages d'horizon, suggérant un cadre général pour les contextes de seuil unique.

Les auteurs notent explicitement que si la méthode du noyau fournit des résultats exacts pour les modèles IID et d'Ordre Fixe, elle ne donne qu'une borne inférieure pour le modèle Prophète Secrétaire, laissant la caractérisation exacte de $C^2_{\text{PS}}(\gamma)$ comme un problème ouvert. De même, l'extension aux seuils dynamiques (adaptatifs) est identifiée comme une direction future, car le cadre actuel est spécifique aux seuils uniques statiques.