Résumé Technique : Bandits Duels Linéaires et Neuronaux avec Feedback Différé

1. Définition du Problème

L'article aborde le problème des Bandits Duels Contextuels (CDB) dans un contexte de Feedback Différé Stochastique. Dans les configurations CDB standard, un agent sélectionne une paire de bras (candidats) et reçoit un feedback binaire de préférence immédiat (par exemple, $x_1 \succ x_2$) pour apprendre une fonction de récompense latente. Cependant, dans des applications réelles telles que l'alignement des Modèles de Langage (LLM), l'optimisation de prompts et la publicité display, le feedback est souvent asynchrone.

Le cadre spécifique formalisé dans ce travail suppose :

• Retards Stochastiques : Le feedback pour une action prise à l'étape $s$ arrive après un délai aléatoire $D_s$.
• Seuil Dur : Il existe une fenêtre d'observation maximale $M$. Si $D_s > M$, le feedback est considéré comme manquant (censuré).
• Probabilité d'Observation : La probabilité que le feedback arrive dans la fenêtre est $\rho = P(D_s \le M)$.
• Défi du Biais : Contrairement aux bandits linéaires où les estimateurs ont des solutions sous forme fermée (par exemple, la régression ridge), les bandits duels reposent sur l'estimation du maximum de vraisemblance (MLE) sous le modèle Bradley-Terry-Luce (BTL). L'absence de solutions sous forme fermée signifie que les adaptations naïves des techniques standard de feedback différé (telles que l'imputation simple ou l'ignorance des données manquantes) introduisent un biais systématique qui ne peut être facilement borné ou corrigé.

2. Méthodologie

Les auteurs proposent deux algorithmes novateurs conçus pour gérer ces retards sans imputation heuristique : Bandits Duels Linéaires avec Feedback Différé (LDB-DF) et Bandits Duels Neuronaux avec Feedback Différé (NDB-DF).

Mécanisme Central : Pondération par l'Inverse de la Probabilité (IPW)

L'innovation centrale est l'intégration d'un mécanisme de Pondération par l'Inverse de la Probabilité (IPW) directement dans la fonction de perte.

• Stratégie de Pondération : Pour une instance de feedback $y_s$ observée à l'étape $t$ (où $s < t$), l'algorithme attribue un poids $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Correction sans Biais : En mettant à l'échelle la contribution du feedback observé par $1/\rho$, le gradient attendu de la perte de substitution devient un estimateur sans biais du vrai gradient, neutralisant efficacement le biais introduit par le mécanisme d'observation stochastique et les données manquantes.

Algorithme 1 : LDB-DF (Configuration Linéaire)

• Modèle : Suppose une fonction de récompense linéaire $f(x) = \theta^\top \phi(x)$.
• Estimation : Minimise une perte logistique régularisée par IPW en utilisant uniquement le feedback « arrivé ».
• Exploration : Utilise une stratégie de borne supérieure de confiance (UCB). Le premier bras est sélectionné de manière gourmande en fonction de l'estimation actuelle $\theta_t$. Le second bras est sélectionné pour maximiser la borne UCB de la différence de préférence par rapport au premier bras, intégrant un rayon de confiance $\beta_t$ qui tient compte à la fois du bruit stochastique et de l'incertitude induite par les retards.
• Matrice d'Information : Mise à jour immédiatement en utilisant les vecteurs de caractéristiques des paires sélectionnées, indépendamment de la latence du feedback.

Algorithme 2 : NDB-DF (Configuration Neuronale)

• Modèle : Approxime la fonction de récompense non linéaire à l'aide d'un réseau de neurones entièrement connecté $h(x; \theta)$ avec des activations ReLU.
• Estimation : Entraîne le réseau en ligne en utilisant la même perte d'entropie croisée pondérée par IPW, apprenant uniquement à partir du sous-ensemble de feedbacks arrivés dans la fenêtre valide.
• Cadre Théorique : L'analyse est menée dans le régime du Neural Tangent Kernel (NTK). L'algorithme suppose que le réseau est suffisamment large ($m$) pour se comporter approximativement comme une fonction linéaire dans l'espace des caractéristiques du gradient à l'initialisation.
• Exploration : Similaire au cas linéaire, il emploie une stratégie UCB. Le bonus d'exploration est dérivé de l'espace des caractéristiques NTK, quantifiant l'incertitude épistémique dans la différence de préférence.

3. Contributions Théoriques

L'article fournit des bornes de regret rigoureuses pour les deux configurations, caractérisant explicitement l'impact des paramètres de délai ($M$ et $\rho$).

• Borne de Regret Linéaire : Le regret cumulatif pour LDB-DF est établi comme $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • Le terme $\frac{M}{\rho}$ agit comme une pénalité multiplicative. Une probabilité d'observation $\rho$ plus faible (moins d'échantillons) et un seuil $M$ plus élevé (retards potentiels plus longs) augmentent linéairement le regret.
  • Lorsque $\rho=1$ et $M=1$ (aucun retard), la borne retrouve l'état de l'art $\tilde{O}(d\sqrt{T})$ pour les bandits duels linéaires standard.

• Borne de Regret Neuronale : Le regret cumulatif pour NDB-DF est établi comme $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, où $\tilde{d}$ est la dimension effective de la matrice NTK.

  • La preuve repose sur une technique de décomposition « ajouter et soustraire » novatrice pour séparer le bruit de martingale du biais systématique induit par les retards.
  • L'analyse confirme que la difficulté fondamentale du problème (compromis entre la probabilité d'observation et l'ampleur du délai) persiste même avec des approximateurs de fonctions non linéaires complexes.

4. Résultats Expérimentaux

Les auteurs évaluent LDB-DF et NDB-DF par rapport à des lignes de base qui ignorent soit les retards, soit utilisent une imputation heuristique.

• Lignes de Base :
  • Ignorer : Utilise la même architecture de modèle mais rejette le feedback en attente jusqu'à son arrivée sans pondération.
  • Heuristique : Impute le feedback manquant en utilisant la préférence prédite par le modèle actuel (proxy biaisé).
• Ensembles de Données :
  • Synthétique : Fonctions de récompense linéaires, quadratiques et cubiques avec des retards géométriques stochastiques.
  • Monde réel : Optimisation automatisée de prompts utilisant le benchmark InstructZero (29 tâches d'induction d'instructions).
• Constats :
  • Les deux algorithmes proposés surpassent significativement les lignes de base en termes de regret cumulatif.
  • Dans les configurations non linéaires, la ligne de base Heuristique converge souvent vers des régions sous-optimales en raison d'erreurs de prédiction auto-renforçantes (hallucinations), tandis que la ligne de base Ignorer souffre de la parcimonie des données.
  • LDB-DF et NDB-DF démontrent une robustesse face à la latence du feedback, naviguant efficacement dans l'espace de recherche des tâches d'optimisation de prompts.

5. Importance et Revendications

L'article revendique combler un vide critique dans l'apprentissage basé sur les préférences en fournissant le premier cadre unifié traitant simultanément :

1. Feedback de Préférence (Duels) : Résultats relatifs binaires plutôt que des récompenses absolues.
2. Approximation Non Linéaire (Neuronale) : Paysages de récompenses complexes via des réseaux de neurones.
3. Retards Stochastiques / Données Manquantes : Latence de feedback réaliste et censure.

Les auteurs soulignent que leur approche s'éloigne de l'imputation heuristique, offrant une solution fondée sur des principes et sans biais via l'IPW. L'analyse théorique établit les premières bornes de regret pour cette configuration spécifique, démontrant que la dégradation des performances est prévisible et dépend linéairement des caractéristiques de délai ($M/\rho$). Ce travail est présenté comme une étape fondamentale pour améliorer l'apprentissage asynchrone basé sur les préférences dans les systèmes à boucle humaine, en particulier pour l'alignement des LLM et l'optimisation de prompts.