Résumé Technique : Prudent-Banker : Pas de Frais Supplémentaires pour la Sécurité de Base dans les Bandits Adversariaux Avec et Sans Retards

1. Formulation du Problème

L'article aborde le problème de l'Apprentissage en Ligne Sécurisé dans les Retards (SOLID) dans le cadre des bandits multi-bras adversariaux (MAB) avec retour différé. Le cadre implique un apprenant interagissant avec un adversaire aveugle sur un horizon $T$. À chaque round $t$, l'apprenant sélectionne une distribution sur les bras, subit une perte et ne reçoit de retour qu'après un retard $d_t$. Le retard total est noté $D = \sum d_t$.

Le défi central est de satisfaire deux objectifs simultanés, souvent contradictoires :

1. Robustesse Globale (Optimalité Minimax) : Atteindre un pseudo-regret au pire des cas de $\tilde{O}(\sqrt{T} + \sqrt{D})$ par rapport au meilleur bras fixe a posteriori, même sous des séquences de pertes adversariales et des retards arbitraires.
2. Comportement Averse au Risque Sans Coût Supplémentaire : Maintenir un regret de comparateur de $\tilde{O}(1)$ par rapport à une politique de base sûre désignée $x_c$. Cela garantit que l'apprenant ne subit pas de perte supplémentaire significative par rapport à une stratégie de confiance, éprouvée (par exemple, un traitement médical standard ou une règle d'investissement conservatrice) tout en explorant.

L'article souligne que les approches existantes pour un retour immédiat (par exemple, Müller et al. [49]) échouent dans le contexte différé. Les retards créent une « dette cachée » où des pertes non observées faussent la perception de l'apprenant sur la performance de la base. Les mécanismes de sécurité standards, qui reposent sur la comparaison des écarts observés à un seuil, peuvent déclencher des transitions prématurées de la conservation à l'agressivité, violant ainsi la garantie de sécurité.

2. Méthodologie : L'Algorithme PRUDENT-BANKER

Les auteurs proposent PRUDENT-BANKER, un nouvel algorithme qui intègre une variante adaptée aux retards de la Descente de Miroir en Ligne (OMD) avec un mécanisme modifié d'agression par phases. L'algorithme opère sur trois niveaux hiérarchiques d'adaptation :

A. Adaptation par Étapes de Retard (Retard Total Inconnu)

Puisque le retard total $D$ est inconnu, l'algorithme emploie une astuce de doublement pour estimer l'échelle du retard. Il opère par « étapes » $s$. Si le retard accumulé au sein d'une étape dépasse l'estimation actuelle $\hat{D}_s$, l'algorithme déclenche un Redémarrage Dur :

• L'estimation du retard est doublée ($\hat{D}_{s+1} \approx 2\hat{D}_s$).
• L'état interne est réinitialisé pour s'adapter à la nouvelle échelle de retard.
• Cela garantit que l'algorithme s'adapte au paysage de retard inconnu sans connaissance préalable.

B. L'Apprenant de Base : Banker-OMD

L'apprenant de base utilise Banker-OMD (Huang et al. [31]), qui gère la latence du retour en maintenant un compte virtuel de « crédits de taille de pas ».

• Au lieu de mettre à jour immédiatement, l'algorithme alloue des taux d'apprentissage basés sur la disponibilité du retour.
• Il construit des estimateurs pondérés par l'importance uniquement lorsque le retour arrive.
• Ce mécanisme restaure la propriété d'annulation télescopique de l'OMD, garantissant que l'apprenant de base atteint un regret de $\tilde{O}(\sqrt{T} + \sqrt{D})$ indépendamment de l'ordre d'arrivée du retour.

C. Agression par Phases avec Redémarrages Calibrés sur les Retards

Le mécanisme de sécurité est contrôlé par un paramètre d'agression $\alpha_k \in [0, 1]$, qui mélange l'apprenant de base $\hat{x}_t$ avec la base sûre $x_c$ :
$$x_t = \alpha_k \hat{x}_t + (1 - \alpha_k) x_c$$
L'algorithme commence avec une faible agressivité (poids élevé sur $x_c$) et augmente $\alpha_k$ géométriquement ($2^{k-1}$) à mesure qu'il rassemble des preuves que la base est sous-optimale.

L'Innovation Clé : Seuil de Redémarrage Calibré sur les Retards
En l'absence de retards, un redémarrage est déclenché si l'écart empirique entre la base et l'apprenant dépasse un seuil $R$. Dans le contexte différé, les auteurs introduisent un terme de tolérance $\xi$ pour tenir compte des « pertes fantômes » (retours non observés) :
$$\text{Seuil } B(\hat{D}_s) = 2\hat{R}(\hat{D}_s) + \xi(\hat{D}_s)$$
où $\xi(\hat{D}_s) \approx O(\sqrt{\hat{D}_s/\delta})$.

• Redémarrage Doux : Si l'écart observé dépasse $B(\hat{D}_s)$, l'algorithme entre dans une nouvelle phase, augmente $\alpha_k$ et réinitialise l'apprenant de base.
• Garantie de Sécurité : Le terme de tolérance $\xi$ agit comme un tampon contre la distorsion causée par les retours manquants. Il empêche l'algorithme de conclure à tort que la base est sous-optimale en raison de pertes non observées, préservant ainsi le regret de comparateur de $\tilde{O}(1)$.

3. Contributions Clés

1. Premier Algorithme pour SOLID avec Retards : PRUDENT-BANKER est le premier algorithme à atteindre le compromis optimal sécurité-robustesse dans les bandits adversariaux avec des retards arbitraires. Il garantit simultanément :

   • Regret au pire des cas : $\tilde{O}(\sqrt{T} + \sqrt{D})$.
   • Regret de comparateur : $\tilde{O}(1)$ (spécifiquement $O(\log D)$).

2. Mécanisme de Redémarrage Calibré sur les Retards : L'article identifie que les tests de sécurité standards échouent sous les retards en raison de la « dette cachée ». Les auteurs dérivent un seuil de redémarrage calibré sur les retards rigoureux qui tient compte de la distorsion au pire des cas induite par les retours non observés. Cela permet une transition sûre de la conservation à l'exploration sans violer les garanties de sécurité.

3. Optimalité via Bornes Inférieures : Les auteurs établissent de nouvelles bornes inférieures pour les bandits adversariaux différés contraints par la sécurité. Ils prouvent que le taux de regret $\tilde{O}(\sqrt{\delta^{-1}T} + \sqrt{\delta^{-1}D})$ atteint par PRUDENT-BANKER est inaméliorable (à des facteurs logarithmiques près) sous l'exigence de sécurité de base. Cela confirme que la surcharge $\delta^{-1/2}$ est le prix intrinsèque de la sécurité en présence de retards.

4. Résolution du « Meilleur des Deux Mondes » dans les Retards : Le travail étend le concept de « Meilleur des Deux Mondes » (BOBW) — garanties simultanées contre un comparateur spécifique et dans le pire des cas — au contexte de retour différé, comblant une lacune laissée par les cadres précédents à retour immédiat.

4. Résultats et Expériences

Résultats Théoriques

• Théorème 4.1 : PRUDENT-BANKER atteint $R_T \le \tilde{O}(\sqrt{C_1 C_2}(\sqrt{T} + \sqrt{D}))$ et $R_T(x_c) \le O(1 + \log D)$.
• Théorème 4.2 (Borne Inférieure) : Tout algorithme satisfaisant un regret de comparateur constant doit subir un regret au pire des cas d'au moins $\Omega(\sqrt{\delta^{-1}T} + \sqrt{\delta^{-1}D})$. Cela prouve l'optimalité de la dépendance de PRUDENT-BANKER envers $T$ et $D$.

Résultats Expérimentaux

Des expériences ont été menées sur un environnement synthétique non stationnaire ($T=50\,000$, $A=100$) sous trois régimes de retard : sans retard, retards géométriques et retards à queue lourde de Pareto.

• Sécurité : PRUDENT-BANKER a maintenu un écart borné (et souvent négatif) par rapport au comparateur sûr à travers tous les régimes de retard, validant la garantie $\tilde{O}(1)$. En revanche, des bases comme SAFE-EXP3-IX et CONSERVATIVE-UCB ont échoué à certifier la sécurité au niveau du comparateur sous retards.
• Adaptativité : Le coefficient de mélange $\alpha_t$ dans PRUDENT-BANKER s'est ajusté dynamiquement. Sous retards, l'algorithme a effectué à plusieurs reprises des redémarrages conservateurs lorsque le budget de retard réalisé dépassait les estimations, ne réentrant dans des phases agressives qu'après que le seuil calibré sur les retards ait été atteint.
• Compétitivité : PRUDENT-BANKER a surpassé SAFE-EXP3-IX en regret au pire des cas (perte pseudo) tout en maintenant la sécurité, démontrant qu'il équilibre efficacement exploration et sécurité sans l'exploration « gaspilleuse » des apprenants adversariaux standards.

5. Signification et Revendications

L'article revendique fournir la première résolution affirmative du problème SOLID dans le contexte de retour différé adversarial. Sa signification réside dans :

• Combler le Fossé : Il connecte la robustesse théorique des algorithmes de bandits différés optimaux au minimax avec la nécessité pratique de contraintes de sécurité dans des domaines à haut risque (par exemple, prise de décision clinique, robotique).
• Sécurité Rigoureuse : Il démontre que la sécurité peut être maintenue sans pénalité linéaire en regret, même lorsque le retour est différé, en tenant rigoureusement compte des déficits d'information.
• Optimalité : En prouvant des bornes supérieures et inférieures correspondantes, l'article établit que le compromis entre sécurité et robustesse sous retards est fondamentalement optimal, établissant une nouvelle référence pour l'apprentissage en ligne sécurisé dans des environnements asynchrones.

Les auteurs concluent que PRUDENT-BANKER équilibre efficacement sécurité et apprentissage, évitant les « transitions mal calibrées » qui mettent en danger les garanties de sécurité dans les bases de référence actuelles robustes aux retards.