Résumé technique : Faisabilité ordonnée par coût pour les bandits à plusieurs bras avec subvention de coût

Formulation du problème

Ce papier traite du problème des Bandits à plusieurs bras avec subvention de coût (MAB-CS), un cadre conçu pour la prise de décision en ligne sensible aux coûts, où l'objectif est de minimiser le coût cumulatif sous une contrainte de qualité. Contrairement aux MAB standards qui maximisent la récompense cumulative, le MAB-CS cherche le bras le moins cher parmi ceux qui satisfont un seuil de récompense espérée minimale.

Le cadre spécifique investigué ici implique une contrainte de qualité définie par rapport à la meilleure récompense inconnue du système. Étant donné un ensemble de bras $\mathcal{A} = \{a_1, \dots, a_K\}$ avec des récompenses espérées $\mu_k$ et des coûts d'échantillonnage connus $c_k$, l'ensemble faisable est $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$. Le seuil est défini comme $\mu_{CS} = (1-\alpha)\mu^*$, où $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ est la meilleure récompense inconnue et $\alpha \in (0, 1)$ est un facteur de subvention. Le bras optimal $a^*$ est le bras le moins cher de l'ensemble faisable $S$.

Le papier définit deux métriques de regret :

1. Regret de coût : Le coût excédentaire encouru par rapport au bras optimal $a^*$.
2. Regret de qualité : La pénalité encourue lorsque la récompense espérée du bras sélectionné tombe en dessous du seuil de faisabilité $\mu_{CS}$.

Le défi central réside dans la minimisation conjointe de ces regrets tout en estimant simultanément le seuil inconnu $(1-\alpha)\mu^*$ et en identifiant le bras faisable le moins cher, sans connaissance préalable de $\mu^*$.

Méthodologie : L'algorithme COF

Les auteurs proposent l'algorithme de Faisabilité ordonnée par coût (COF) pour résoudre le problème MAB-CS. COF fonctionne en évaluant les bras par ordre croissant de leurs coûts connus. Pour chaque bras candidat $a_\ell$, l'algorithme détermine la faisabilité en le comparant à un ensemble de « bras de contrôle » (des bras plus chers que $a_\ell$).

Les mécanismes clés de COF incluent :

• Évaluation ordonnée par coût : Les bras sont testés séquentiellement du moins cher au plus cher. Le premier bras jugé faisable est sélectionné comme bras optimal pour le reste de l'horizon.
• Combinaison d'échantillons (Agrégation) : Pour déterminer si un bras candidat $a_\ell$ est infaisable, COF ne s'appuie pas sur une seule comparaison par paire. Au lieu de cela, il agrège les preuves issues des comparaisons avec tous les bras capables de disqualifier $a_\ell$. Il calcule une borne supérieure sur la probabilité que $a_\ell$ soit faisable par rapport à chaque bras de contrôle et juge $a_\ell$ infaisable dès que le produit de ces probabilités tombe en dessous d'une tolérance $\delta$.
• Échantillonnage exclusif : Si le nombre d'échantillons d'un bras candidat prend du retard par rapport au bras de contrôle le plus échantillonné, COF échantillonne le candidat exclusivement pour « rattraper son retard », réduisant ainsi le nombre total d'échantillons sous-optimaux requis.
• Filtre BAI : Lors de l'évaluation d'un candidat, COF utilise un filtre qui arrête l'échantillonnage des bras de contrôle dont les bornes de confiance supérieures (UCB) tombent en dessous de la borne de confiance inférieure (LCB) d'un autre bras de contrôle. Cela évite de gaspiller des échantillons sur des bras statistiquement peu susceptibles d'être le bras de meilleure récompense ($i^*$).

Contributions théoriques

Le papier fournit une analyse théorique rigoureuse du MAB-CS, établissant à la fois des bornes inférieures et supérieures sur le regret.

1. Bornes inférieures dépendantes de l'instance :

   • Les auteurs dérivent des bornes inférieures sur le nombre attendu d'échantillons pour les bras bon marché (coût $< c_{a^*}$) et les bras chers (coût $> c_{a^*}$).
   • Une contribution novatrice est une borne inférieure conjointe pour un ensemble de bras. Cette borne reflète l'idée qu'un bras peut être certifié infaisable si sa récompense est pire que la récompense subventionnée de n'importe quel bras arbitraire, et pas seulement du bras de meilleure récompense $i^*$. Cela généralise les bornes antérieures qui traitaient $i^*$ de manière singulière.

2. Bornes supérieures de regret pour COF :

   • Le papier établit des bornes supérieures dépendantes de l'instance sur le coût cumulatif attendu et le regret de qualité pour COF.
   • Pour les bras bon marché, la borne est montrée comme étant optimale en ordre, correspondant à la dépendance $O(\log T / \Delta_{Q,k}^2)$ trouvée dans les bornes inférieures.
   • Pour les bras chers, la borne dépend du maximum de deux termes : l'un lié à l'écart entre le bras et le bras optimal, et l'autre lié à l'écart conjoint requis pour éliminer le meilleur bras bon marché. Les auteurs notent une légère discordance entre les bornes inférieures et supérieures pour les bras chers, suggérant une marge d'amélioration dans l'analyse théorique de la complexité en échantillons.

Résultats expérimentaux

Les auteurs valident COF par le biais de simulations extensives sur :

• Ensembles de données réels : Goodreads (notations de livres) et MovieLens (notations de films), où les genres servent de bras de bandit.
• Instances synthétiques : Problèmes conçus à la main pour tester des comportements algorithmiques spécifiques.

Constats clés :

• Performance : COF surpasse constamment les algorithmes de base, notamment ETC-CS (exploration à budget fixe), PE-CS (élimination par paires), UCB-CS et TS-CS.
• Robustesse : Contrairement à UCB-CS et TS-CS, qui peuvent souffrir d'un regret linéaire en raison de l'inclusion incorrecte de bras bon marché et infaisables dans leurs ensembles faisables empiriques, COF maintient un regret sous-linéaire en testant rigoureusement la faisabilité.
• Sensibilité au facteur de subvention : Bien que PE-CS performe légèrement mieux pour de très petits facteurs de subvention ($\alpha$) en raison d'intervalles de confiance plus serrés dans les régimes à fort échantillonnage, COF évite le plafonnement des performances observé dans PE-CS lorsque $\alpha$ augmente.
• Études d'ablation : Les expériences confirment que les fonctionnalités « combinaison d'échantillons » et « échantillonnage exclusif » sont critiques pour l'efficacité de l'algorithme, réduisant considérablement le regret par rapport à des variantes sans ces mécanismes.

Importance et revendications

Le papier affirme que COF offre un cadre théorique qualitativement supérieur et des performances empiriques pour les problèmes de bandits sensibles aux coûts où la contrainte de qualité est relative à la meilleure récompense inconnue.

• Avancement théorique : Le travail fournit les premières bornes inférieures dépendantes de l'instance qui caractérisent conjointement la complexité en échantillons de plusieurs bras, offrant un aperçu plus profond des défis structurels du MAB-CS que les analyses antérieures basées sur le pire des cas ou sur un seul bras.
• Efficacité algorithmique : En évitant une phase dédiée d'identification du meilleur bras (BAI) pour trouver $\mu^*$ avant de tester la faisabilité, COF réduit l'échantillonnage inutile. La stratégie de « combinaison d'échantillons » permet à l'algorithme d'éliminer les bras infaisables plus efficacement que les méthodes de comparaison par paires.
• Applicabilité pratique : Les auteurs soulignent la pertinence du MAB-CS pour des scénarios réels tels que le routage de modèles LLM, où différents modèles ont des coûts variables et une qualité inconnue, et où le système doit équilibrer le coût par rapport à un plancher de performance relatif au meilleur modèle disponible. De même, le cadre s'applique à la sélection de modalités publicitaires et à la diffusion de contenu dans les services de streaming.

Les auteurs concluent que, bien que COF atteigne des performances optimales en ordre pour les bras bon marché et démontre de solides résultats empiriques, les travaux futurs devraient combler l'écart entre les bornes inférieures et supérieures pour les bras chers et explorer des variantes d'échantillonnage biaisées par le coût pour des applications avec des distributions de coûts très inégales.