Résumé Technique : PFN-TS

Énoncé du Problème

Les bandits contextuels traitent de la prise de décision séquentielle sous incertitude, où un apprenant observe un contexte, sélectionne une action et reçoit une récompense stochastique. L'objectif est de minimiser le regret cumulatif au fil du temps. L'échantillonnage de Thompson (TS) est une stratégie standard qui maintient une distribution a posteriori bayésienne sur les fonctions de récompense et échantillonne les actions de manière gourmande à partir de cette distribution. Cependant, l'efficacité du TS dépend de la qualité du modèle de récompense sous-jacent.

Dans les applications tabulaires (par exemple, la santé mobile, les recommandations), les modèles de récompense linéaires sont souvent mal spécifiés car ils échouent à capturer des comportements humains complexes tels que les interactions, les effets de seuil et l'hétérogénéité. Bien que des alternatives plus riches existent (méthodes à noyaux, réseaux de neurones, ensembles d'arbres), elles souffrent de problèmes d'évolutivité, de surcoûts computationnels élevés ou d'hypothèses structurelles rigides. De plus, ces modèles nécessitent généralement des hyperparamètres difficiles à régler dans des contextes en ligne.

Les Réseaux Ajustés aux Données Antérieures (PFN), tels que TabPFN et TabICL, offrent une alternative prometteuse. Ce sont des modèles basés sur des transformateurs entraînés pour approximer les distributions prédictives a posteriori (PPD) sur un large éventail de processus de génération de données. Ils fonctionnent via l'apprentissage en contexte (ICL), ne nécessitant aucune mise à jour de paramètres ni aucun réglage d'hyperparamètres. Cependant, un fossé critique existe : les PFN produisent des PPD (incertitude sur les récompenses futures bruyantes), alors que le TS nécessite une incertitude sur la fonction de récompense moyenne latente. Échantillonner directement à partir de la PPD n'équivaut pas à échantillonner à partir de l'a posteriori de la fonction moyenne, ce qui conduit à une exploration sous-optimale.

Méthodologie : PFN-TS

Les auteurs proposent PFN-TS, un algorithme d'échantillonnage de Thompson qui comble ce fossé en convertissant les prédictifs a posteriori des PFN en échantillons de la fonction de récompense moyenne latente. La méthodologie se compose de trois composants principaux :

1. Théorème Central Limite Prédictif sur Sous-échantillons (SubCLT)

Pour récupérer la distribution a posteriori de la moyenne latente $f_0(x)$ à partir de la séquence prédictive du PFN, les auteurs exploitent un théorème central limite (TCL) prédictif.

• Fondement Théorique : Sous des hypothèses spécifiques (variance asymptotique, conditions de quasi-martingale et moments bornés), la queue de la séquence de moyenne prédictive converge vers une distribution gaussienne centrée sur la moyenne latente.
• Innovation d'Efficacité : Les approches traditionnelles pour estimer la variance a posteriori nécessitent de calculer la moyenne prédictive sur tous les $n$ préfixes de l'ensemble de données, ce qui est prohibitif en termes de calcul pour les bandits en ligne ($O(n)$ passages avant). PFN-TS introduit un estimateur sous-échantillonné qui calcule la variance en utilisant uniquement $O(\log n)$ préfixes espacés géométriquement ($t_0, t_1, \dots, t_J$).
• Estimation de la Variance : La variance est estimée en utilisant les incréments de bloc $D_j = m_{t_j}(x) - m_{t_{j-1}}(x)$ pondérés harmoniquement ($w_j$). Les auteurs prouvent que cet estimateur sous-échantillonné est consistant ($\hat{V}_{s_n} \xrightarrow{p} V(x)$) et satisfait le TCL, permettant une approximation gaussienne traitable $N(m_{s_n}(x), \hat{V}_{s_n}(x)/s_n)$ pour l'échantillonnage de Thompson.

2. Mise en Cache et Optimisation Computationnelle

Pour réduire davantage le coût par tour, PFN-TS exploite l'architecture de TabICL (le PFN spécifique utilisé) :

• Réutilisation du Cache KV : TabICL met en cache les matrices d'attention clé-valeur pour un ensemble de données fixe. PFN-TS réutilise ces représentations mises en cache d'un tour à l'autre.
• Points de Rafraîchissement : L'algorithme ne effectue de nouveaux passages avant qu'aux « points de rafraîchissement » géométriques ($t_j$) définis par la grille SubCLT. Entre les points de rafraîchissement, il utilise l'approximation gaussienne instantanée dérivée du dernier état mis en cache. Cela réduit la complexité de $O(n)$ à $O(\log n)$ passages avant par bras par tour.

3. Stratégie de Codage Adaptatif

L'article aborde le choix de conception concernant la représentation de l'identité du bras dans l'entrée :

• Codage Disjoint : Maintient des modèles indépendants par bras.
• Codage Joint : Ajoute l'identité du bras sous forme de vecteur one-hot au contexte, permettant un partage d'information entre les bras.
• Sélection Adaptative : Puisqu'aucun codage ne domine universellement, PFN-TS exécute les deux en parallèle pendant une phase de « double codage ». Il sélectionne le codage actif basé sur le Score de Probabilité Classée Continue (CRPS), une règle de notation strictement propre qui mesure l'étalonnage. Le codage avec le CRPS cumulatif le plus bas est conservé, et le challenger est éliminé après un temps de commutation prédéfini.

Contributions Clés

1. Pont Algorithmique : PFN-TS est la première méthode à adapter avec succès les PFN (qui produisent des PPD) pour l'échantillonnage de Thompson en dérivant un estimateur consistant de la variance a posteriori de la moyenne latente via un TCL sous-échantillonné.
2. Garanties Théoriques :
   • Consistance : Prouve la consistance de l'estimateur de variance sous-échantillonné sous des hypothèses légères.
   • Bornes de Regret : Déduit une borne de regret bayésien pour PFN-TS. La borne se décompose en le regret de l'échantillonnage de Thompson exact sous l'a priori du PFN plus un terme d'erreur dépendant de la qualité d'approximation du PFN et du processus de sous-échantillonnage.
3. Efficacité : Démontre que $O(\log n)$ passages avant suffisent pour une estimation de variance consistante, rendant les bandits basés sur PFN réalisables pour un déploiement en ligne.
4. Performance Empirique :
   • Benchmarks Synthétiques : PFN-TS obtient le meilleur rang moyen sur les tâches synthétiques non linéaires (variantes de Friedman) et reste compétitif sur les tâches linéaires.
   • Benchmarks OpenML : Surpasse les lignes de base (LinTS, NeuralTS, BFTS, XGBoostTS) sur six des huit jeux de données de classification vers bandit.
   • Application Réelle : Dans une évaluation hors ligne de l'essai de santé mobile Drink Less, PFN-TS atteint la valeur de politique estimée la plus élevée (SNIPS) à l'horizon final, surpassant BFTS et autres lignes de base.

Importance et Revendications

L'article affirme que PFN-TS démontre que l'apprentissage en contexte tabulaire peut servir de modèle de récompense efficace pour la prise de décision séquentielle une fois l'extraction efficace de l'incertitude et le codage adaptatif mis en œuvre.

• Flexibilité du Modèle : Contrairement aux modèles traditionnels, PFN-TS ne nécessite aucun réglage d'hyperparamètres et s'adapte automatiquement à la structure des données (sparsité, régularité, non-linéarité) inhérente au large a priori du PFN.
• Viabilité Pratique : En réduisant le goulot d'étranglement computationnel de l'estimation de l'incertitude de linéaire à logarithmique par rapport à la taille de l'ensemble de données, la méthode rend le déploiement de modèles de base dans des contextes de bandits en ligne pratique.
• Robustesse : La méthode s'avère robuste à travers divers processus de génération de données, performante aussi bien sur des tâches synthétiques non linéaires que sur des données réelles de santé mobile.

Les auteurs restent modestes concernant les limites, notant que le temps d'exécution reste une contrainte en raison des évaluations répétées du modèle, et que l'étalonnage sur des échantillons finis peut être médiocre lorsque les historiques de bras sont courts ou faiblement informatifs. Ils suggèrent des travaux futurs sur l'estimation de variance régularisée et des bornes de regret plus précises pour les a priori spécifiques TabPFN/TabICL.