Résumé Technique : Bandits Duelistes Linéaires Robustes avec Contexte Post-Service sous Délais Inconnus et Corruptions Adversarielles

1. Formulation du Problème

Cet article traite d'un problème de prise de décision complexe au sein du cadre des Bandits Duelistes Contextuels Linéaires (CDB), ciblant spécifiquement les environnements volatils caractérisés par trois défis simultanés :

1. Contextes Post-Service : Contrairement aux bandits contextuels standards où l'utilité est déterminée uniquement par les caractéristiques pré-action (ex: démographie de l'utilisateur), l'utilité réelle dépend ici de caractéristiques latentes révélées seulement après que l'action a été entreprise (ex: temps de livraison, température de la nourriture). L'apprenant doit estimer une application $\phi^*$ de $x_t$ (contextes pré-service) vers $y_t$ (contextes post-service).
2. Délais de Feedback Inconnus : Le feedback arrive avec des délais $\tau_t$ qui sont soit stochastiques (sous-gaussiens), soit adversariels. L'apprenant ne sait pas quel régime est actif, ni la séquence spécifique des délais.
3. Corruption Adversarielle : Un adversaire peut corrompre les résultats de préférence observés (inversant 0 en 1 ou vice versa) sous réserve d'un budget cumulatif $C$.

La difficulté centrale réside dans l'interaction multiplicative de ces facteurs. Les délais réduisent la taille effective de l'échantillon, amplifiant le levier statistique des signaux corrompus. De plus, l'apprenant doit estimer l'application post-service $\phi^*$ en utilisant un feedback déjà compromis par les délais et la corruption, créant un cercle vicieux d'erreur d'estimation.

L'objectif est de minimiser le regret cumulatif $R_T$, défini comme l'écart d'utilité entre la paire de bras optimale et la paire sélectionnée, tout en restant agnostique au régime de délai spécifique et à la présence de corruption.

2. Méthodologie : RCDP-UCB

Les auteurs proposent RCDP-UCB (Robust to Corruption, Delay, and Post-serving UCB), un cadre algorithmique conçu pour gérer ces défis entrelacés.

Composantes Clés :

• Prédiction de Contexte : L'algorithme utilise un approximateur appris $\hat{\phi}_t$ (par exemple, un réseau de neurones) pour prédire les contextes post-service $y_t$ à partir des contextes pré-service $x_t$ avant la sélection de l'action. Le vecteur de caractéristiques est construit comme $\hat{z}_t = (x_t, \hat{\phi}_t(x_t))$.
• Matrices de Design Duales : L'algorithme maintient deux matrices distinctes pour découpler la sélection de l'estimation :
  • $\tilde{V}_t$ : La Matrice d'Historique Complet, construite en utilisant tous les contextes chronologiques (arrivés et en attente). Cette matrice est utilisée pour la sélection des bras et le calcul des poids afin d'assurer l'optimisme et la stabilité.
  • $\hat{W}_t$ : La Matrice d'Historique Observé, construite uniquement à partir du feedback qui est réellement arrivé au temps $t$. Elle est utilisée strictement pour l'estimation des paramètres ($\Theta_t$) afin d'assurer la validité statistique.
• Stratégie de Pondération Adaptative : Un mécanisme de pondération unifié est introduit pour atténuer à la fois la corruption et le biais induit par les délais. Pour un échantillon $s$, le poids $\omega_s$ est défini par :
  $$\omega_s = \min\left(1, \frac{\alpha}{\|\Delta z_s\|_{\tilde{V}_{s-1}^{-1}}}\right)$$
  où $\alpha$ est un paramètre de robustesse. Cette stratégie de "clipping" (écrêtage) réduit l'importance des échantillons ayant un fort levier statistique (normes élevées), limitant ainsi l'influence des observations adversariellement corrompues et des feedbacks retardés qui faussent la géométrie de l'information.
• Minimisation du Regret : L'algorithme sélectionne des paires de bras $(a_t, b_t)$ en utilisant une stratégie de Borne Supérieure de Confiance (UCB) basée sur $\tilde{V}_t$ et les caractéristiques prédites, équilibrant l'exploration et l'exploitation tout en tenant compte de l'incertitude tant pour le paramètre de préférence $\Theta^*$ que pour l'application post-service $\phi^*$.

3. Principales Contributions

1. Cadre Analytique Unifié : L'article formalise le premier cadre de bandit duel linéaire qui intègre simultanément les contextes post-service, les délais inconnus (stochastiques ou adversariels) et la corruption adversarielle.
2. Conception Algorithmique (RCDP-UCB) : Il introduit un nouvel algorithme qui intègre l'estimation de la mise en correspondance contextuelle avec un mécanisme de clipping adaptatif. Crucialement, le schéma de pondération est agnostique au régime de délai, ceما signifie qu'il ne nécessite pas de connaissance préalable pour savoir si les délais sont stochastiques ou adversariels pour fonctionner efficacement.
3. Garanties Théoriques :
   • Borne Supérieure : Sous des conditions de régularité standard, l'algorithme atteint une borne supérieure de regret de $\tilde{O}(d(\sqrt{T} + C + D))$, où $d$ est la dimension des caractéristiques, $T$ est l'horizon temporel, $C$ est le budget de corruption, et $D$ représente la complexité du délai ($D = \max(\sqrt{\Lambda}, \mu_\tau)$).
   • Borne Inférieure : Les auteurs dérivent une borne inférieure minimax de $\Omega(\sqrt{dT} + dC + D')$ (où $D' = \max(\sqrt{d\Lambda}, d\mu_\tau)$) en l'absence de contextes post-service. Cela confirme que l'overhead introduit par les délais et la corruption est inévitableable d'un point de vue informationnel.
   • Optimalité : La borne supérieure correspond à la borne inférieure à un facteur $\sqrt{d}$ près pour les délais adversariels, démontrant une efficacité quasi-optimale.

4. Résultats Expérimentaux

Les auteurs évaluent RCDP-UCB sur des environnements synthétiques et des jeux de données réels (UCI et OpenML) sous diverses conditions :

• Environnements Synthétiques : Les expériences couvrent des mises en correspondance post-service linéaires et non-linéaires (Polynomiale, Sinusoïdale, Absolue) avec des budgets de corruption ($C$) et des régimes de délai (Stratégique/Adversariel et Stochastique) variables.
• Baselines : L'algorithme est comparé à des méthodes de pointe incluant RCDB (robuste à la corruption), ColSTIM, MaxInP, et MaxPairUCB.
• Constats :
  • RCDP-UCB surpasse systématiquement les baselines en termes de regret cumulatif dans tous les régimes de délai et niveaux de corruption.
  • L'algorithme démontre une robustesse supérieure dans les environnements "latents" où les contextes post-service sont critiques ; les baselines qui échouent à modéliser ces contextes ou qui manquent de pondération robuste souffrent d'un regret nettement plus élevé.
  • Le mécanisme de pondération adaptative neutralise efficacement le bruit combiné de la corruption et du délai, maintenant des performances stables même lorsque la dimensionnalité du contexte ($d$) et le nombre de bras ($K$) augmentent.
  • Les expériences sur des jeux de données réels confirment la scalabilité et la robustesse de l'algorithme, même lorsque l'hypothèse de préférence linéaire n'est qu'une approximation.

5. Signification et Revendications

L'article affirme être le premier travail à traiter simultanément les défis conjoints des corruptions adversarielles, des délais de feedback inconnus et des contextes post-service au sein du cadre des bandits contextuels duels.

• Impact Théorique : Il établit que l'effet combiné de ces facteurs est fondamentalement multiplicatif mais peut être géré via une stratégie de pondération unifiée ancrée dans la géométrie de l'information complète ($\tilde{V}_t$). Les résultats fournissent des garanties "le meilleur des deux mondes" pour les régimes de délai, s'adaptant aux contextes stochastiques et adversariels sans détection explicite.
• Pertinence Pratique : Ce travail est motivé par les systèmes interactifs modernes, particulièrement l'Apprentissage par Renforcement à partir de Feedback Humain (RLHF) pour les modèles de langage (LLM). Dans ces systèmes, les préférences des utilisateurs sont souvent relatives (duels), le feedback est retardé, et les données peuvent être bruitées ou manipulées. Le cadre proposé offre une voie vers des alignements plus fiables, robustes et précis des systèmes d'IA avec l'intention humaine en tenant compte des facteurs latents post-action et des irrégularités des données.

Les auteurs reconnaissent des limites, notant que l'écart $\sqrt{d}$ dans la borne inférieure des délais adversariels reste un problème ouvert et que l'extension du cadre pour gérer les contextes post-service retardés constitue une direction pour les recherches futures.