Résumé Technique : Échantillonnage de Thompson Corrigé par Flux pour les Bandits Contextuels Non Stationnaires

Formulation du Problème

L'article traite du défi des bandits contextuels linéaires non stationnaires, un cadre où la relation entre les contextes, les actions et les récompenses évolue au fil du temps. Dans les bandits contextuels classiques, le vecteur de paramètres $w_t$ est supposé stationnaire. Cependant, dans les applications du monde réel (ex. : systèmes de recommandation, tarification dynamique, finance), les préférences des utilisateurs et les conditions de marché dérivent, rendant les données historiques systématiquement biaisées si elles sont utilisées naïvement.

La difficulté fondamentale réside dans l'arbitrage entre conserver les données historiques pour réduire la variance du postérieur et rejeter les anciennes données pour éviter le biais provenant de modèles obsolètes. Les approches existantes — telles que les fenêtres glissantes, l'actualisation exponentielle et les redémarrages périodiques — traitent les données historiques principalement comme un passif qu'il faut gérer en les rejetant ou en les pondérant uniformément. Les auteurs soutiennent que lorsque la non-stationnarité présente une structure prévisible (ex. : dérive graduelle, périodicité ou régimes récurrents), les observations historiques contiennent des informations précieuses qui peuvent être exploitées si elles sont corrigées pour les changements environnementaux intermédiaires.

Méthodologie : Échantillonnage de Thompson Corrigé par Flux (FC-TS)

Les auteurs proposent l'Échantillonnage de Thompson Corrigé par Flux (FC-TS), un cadre bayésien qui transforme les observations historiques en « pseudo-observations de l'instant présent » avant de les incorporer dans le postérieur. La méthode découple la gestion de la non-stationnarité en deux composantes distinctes : un opérateur de transport et une règle de pondération de confiance.

1. Mécanisme Central

À chaque tour $t$, pour chaque observation passée $(x_s, a_s, r_s)$, le FC-TS construit une récompense transportée $\hat{r}_{s \to t}$ :
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
où $\hat{\Delta}_{s \to t}$ estime le décalage de la récompense moyenne de $s$ à $t$. Cela permet de faire « circuler » la récompense passée vers l'avant pour l'aligner sur le modèle de récompense actuel.

Pour éviter que le bruit ne provienne d'estimations de dérive inexactes, chaque observation transportée se voit assigner un poids de confiance $\omega_{s,t} \in [0, 1]$. Ce poids contrôle l'influence de l'observation sur le postérieur, en gonflant sa variance de bruit effective si la correction est incertaine.

Le postérieur pour une action $a$ est mis à jour en utilisant ces observations transportées et pondérées :
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
La sélection de l'action procède via un échantillonnage de Thompson standard utilisant le postérieur gaussien $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Instanciations Structurées

Le cadre fournit un modèle unifié avec des instanciations spécifiques pour trois motifs de non-stationnarité courants :

• Dérive Linéaire : Suppose que les paramètres évoluent selon $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$. L'opérateur de transport utilise une estimation de régression de Ridge en ligne $\hat{\delta}_t^{(a)}$ pour décaler les récompenses : $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. Les poids décroissent exponentiellement ($\omega_{s,t} = \gamma^{t-s}$) pour tenir compte de l'incertitude d'extrapolation.
• Variation Périodique : Suppose que les paramètres se répètent avec une période $P$. L'opérateur de transport est l'identité ($\hat{r}_{s \to t} = r_s$) pour les observations dans la même phase. Les poids sont déterminés par la distance circulaire entre les phases, permettant à l'algorithme de réutiliser les données des cycles précédents ($\omega_{s,t}$ dépend de la proximité des phases).
• Régimes Récurrents : Gère les environnements basculant entre un ensemble fini de régimes. L'algorithme maintient une banque de postérieurs spécifiques à chaque régime. Lors de la détection d'un point de rupture (via CUSUM sur les résidus de prédiction), il recharge le postérieur du régime récurrent plutôt que de repartir de zéro.

Le cadre supporte également la composition, permettant de gérer simultanément la dérive linéaire et la périodicité en combinant les règles de transport et de pondération respectives.

Contributions Clés

1. Mises à jour du Postérieur Corrigées par Flux : L'article introduit une vision du transport pour la non-stationnarité où les récompenses passées sont corrigées en pseudo-observations de l'instant présent et incorporées via des mises à jour bayésiennes pondérées par la confiance, plutôt que d'être uniformément rejetées.
2. Conception Algorithmique Modulaire : Le FC-TS est défini par un opérateur de transport et une règle de pondération génériques, instanciés pour la dérive linéaire, la variation périodique et les régimes récurrents. Cela inclut une variante adaptative combinant tendances et multiplicités de périodicité.
3. Validation Empirique : Une évaluation approfondie à travers cinq études de cas (dérive linéaire, variation périodique, régimes récurrents, non-stationnarité composée et sélection de portefeuille semi-synthétique) démontre que le FC-TS surpasse les meilleures lignes de base basées sur l'oubli.

Résultats Expérimentaux

Les auteurs ont évalué le FC-TS par rapport à quatre lignes de base : Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) et Restarting TS (R-TS).

• Gains de Performance : Le FC-TS a obtenu le regret cumulé le plus bas dans les cinq configurations, avec des améliorations allant de 14,1 % à 59,0 % par rapport à la meilleure ligne de base dans chaque environnement spécifique.

• Aperçus Spécifiques aux Cas :

  • Dérive Linéaire : Le FC-TS a égalé le SW-TS pendant la phase de chauffe (warm-up), mais s'est progressivement distingué à mesure que les estimations de dérive se stabilisaient, l'emportant sur 8 graines (seeds) sur 10.
  • Variation Périodique : Le FC-TS a montré le gain synthétique le plus important (50,0 %) grâce à la « mémoire de phase », accumulant les données des cycles précédents. Le regret par cycle est passé d'environ 70 à 4, tandis que les lignes de base stagnaient.
  • Régimes Récurrents : Le FC-TS a obtenu une amélioration de 59,0 % en rechargeant les postérieurs spécifiques au régime lors de la détection d'un changement, évitant ainsi la pénalité de « démarrage à froid » (cold start) des redémarrages.
  • Non-Stationnarité Composée : Dans des environnements présentant à la fois une dérive et des changements abrupts, le FC-TS a réussi à combiner la correction de dérive (pour l'évolution fluide) et les réinitialisations de régime (pour les changements abrupts), produisant une amélioration de 29,5 %.
  • Portefeuille Semi-Synthétique : Dans une tâche financière avec des cycles mensuels/trimestriels chevauchants et une dérive de croissance vers la valeur, la variante adaptative du FC-TS a amélioré le regret de 28,1 % par rapport à la meilleure ligne de base (D-TS). Les études d'ablation ont confirmé que la correction de dérive était la composante dominante de ce gain.

• Résultats d'Ablation :

  • Taille d'Échantillon Efficace : Conserver davantage de données sans correction de transport (l'ablation « no-transport ») a entraîné un regret plus élevé que les méthodes qui rejettent les données, confirmant que les données obsolètes introduisent un biais systématique.
  • Valeur du Transport : L'opérateur de transport lui-même a représenté une réduction de regret de 47 à 57 % par rapport à la variante sans transport à travers diverses échelles de dérive, prouant que le mécanisme de correction, et non seulement la reconstruction du postérieur, pilote la performance.

Signification et Revendications

L'article affirme que la non-stationnarité structurée est mieux traitée en corrigeant et en réutilisant l'expérience qu'en la rejetant uniformément.

Les auteurs soulignent que lorsque la dérive de l'environnement est prévisible (graduelle, périodique ou récurrente), les données historiques sont un atout plutôt qu'un passif. En modélisant explicitement le « flux » de la distribution des récompenses au fil du temps, le FC-TS maintient une taille d'échantillon effective bien plus grande que les méthodes d'oubli. Les résultats suggèrent que la clé de l'efficacité de l'échantillonnage dans les bandits non stationnaires réside dans le repondération et la correction des observations historiques basées sur la structure temporelle spécifique de l'environnement, plutôt que dans l'application d'une règle d'oubli uniforme.

L'article conclut modestement, notant que les travaux futurs incluent l'apprentissage en ligne des structures de dérive avec une incertitude calibrée, l'extension du cadre aux bandits linéaires généralisés ou neuronaux, et le développement de garde-fous pour les contextes à enjeux élevés avec des changements de distribution non modélisés.