Résumé Technique : Apprentissage On-Policy et Off-Policy pour les Espaces d'Actions de Grande Taille

Énoncé du Problème

La thèse traite du défi fondamental de l'apprentissage dans les systèmes interactifs, plus précisément les bandits contextuels, où l'espace d'actions $K$ est extrêmement vaste (allant de milliers à des millions). Dans de tels contextes, les algorithmes standards pour l'apprentissage à la fois on-policy (en ligne) et off-policy (hors ligne) font face à de graves goulots d'étranglement de scalabilité :

• On-Policy : Les stratégies d'exploration standard comme le Thompson Sampling (TS) ou l'Upper Confidence Bound (UCB) reposent généralement sur des modèles disjoints où chaque action possède un paramètre indépendant. Dans les espaces d'actions de grande taille, l'apprentissage de chaque paramètre de manière indépendante est statistiquement inefficace, entraînant un regret cumulé élevé. À l'inverse, les modèles joints qui partagent des paramètres à travers toutes les actions sont souvent informatiquement intraitables en raison de la complexité $O(K^2)$ ou $O(K^3)$ du maintien et de la mise à jour d'une matrice de covariance complète.
• Off-Policy : L'apprentissage à partir de données statiques enregistrées par une politique de logging $\pi_0$ fait face à trois problèmes principaux :
  1. Inefficacité statistique : Les méthodes directes (DM) souffrent d'un biais élevé lorsque les actions sont rarement observées.
  2. Variance : Les estimateurs par Inverse Propensity Scoring (IPS) présentent une variance explosive lorsque la probabilité de logging $\pi_0(a|x)$ est faible.
  3. Intraitabilité de l'optimisation : La thèse soutient que dans les grands espaces d'actions, le paysage d'optimisation des objectifs standards basés sur l'IPS devient hautement non-concave, avec des plateaux plats et un nombre exponentiel de maxima locaux, provoquant l'échec des optimiseurs basés sur le gradient, quel que soit la qualité statistique de l'estimateur.

Méthodologie et Contributions

La thèse est divisée en deux parties, proposant des méthodes novatrices pour chaque paradigme d'apprentissage.

Partie I : Apprentissage On-Policy (Scaler le Thompson Sampling)

L'idée centrale est de conserver la flexibilité des modèles de récompense disjoints tout en introduisant des priors bayésiens structurés qui permettent le partage d'informations entre les actions.

1. Mixed-Effect Thompson Sampling (meTS) - Chapitre 3

• Méthodologie : Les auteurs introduisent un modèle bayésien hiérarchique où les paramètres d'action $\theta_a$ sont couplés par $L$ paramètres d'effets latents partagés $\Psi = (\psi_\ell)_{\ell \in [L]}$. Le processus génératif suppose que $\theta_a | \Psi \sim p_0(\cdot|\Psi)$.
• Algorithme : meTS effectue un échantillonnage hiérarchique : d'abord l'échantillonnage des effets globaux $\Psi_t$ à partir de leur a posteriori, puis l'échantillonnage des paramètres d'action individuels $\theta_{t,a}$ conditionnés par $\Psi_t$.
• Résultats Théoriques : Pour les modèles linéaires-gaussiens, les auteurs dérivent des mises à jour a posteriori exactes en forme fermée. Ils prouvent une borne de regret bayésien de $\tilde{O}(\sqrt{Td K_{eff}})$, où $K_{eff}$ est un nombre effectif d'actions. Lorsque le nombre d'effets $L \ll K$, alors $K_{eff} \ll K$, ce qui produit une amélioration multiplicative par rapport au TS standard.
• Complexité : La méthode réduit la complexité mémoire de $O(K^2d^2)$ à $O((L^2 + K)d^2)$ et le temps d'exécution de $O(K^3d^3)$ à $O((L^3 + K)d^3)$.
• Extensions : Le cadre est étendu aux Modèles Linéaires Généralisés (GLM) en utilisant des approximations de Laplace tractables.

2. Diffusion Thompson Sampling (dTS) - Chapitre 4

• Méthodologie : Pour capturer des dépendances non linéaires plus complexes entre les actions, les auteurs remplacent la structure latente à couche unique par une hiérarchie profonde de variables latentes régies par des modèles de diffusion pré-entraînés. Le prior est défini par une chaîne de Markov de variables latentes $\psi_L \to \dots \to \psi_1 \to \theta_a$ connectées par des fonctions de lien non linéaires $f_\ell$.
• Algorithme : dTS emploie une procédure d'inférence récursive. Il approxime l'a posteriori intraitable en maintenant un "modèle de diffusion a posteriori" où les fonctions de lien et les covariances sont mises à jour via des mises à jour de type gaussien (combinant la précision du prior et la précision des données) sans rétropropagation à travers le réseau de neurones.
• Résultats Théoriques : Dans un cadre linéaire-gaussien, la borne de regret passe à l'échelle avec le nombre effectif d'actions et la somme des variances à travers les $L$ couches. La complexité est linéaire par rapport à $L$, soit $O((L+K)d^2)$, améliorant ainsi meTS.
• Signification : Cela démontre que les modèles génératifs profonds peuvent être utilisés non seulement pour la représentation, mais aussi pour structurer l'incertitude nécessaire à une exploration efficace.

Partie II : Apprentissage Off-Policy (Traiter l'Estimation et l'Optimisation)

La thèse remet en question le paradigme dominant centré sur l'estimation et propose trois approches complémentaires.

1. Structured Direct Method (sDM) - Chapitre 6

• Méthodologie : Analogue à meTS, sDM introduit un vecteur latent partagé $\psi$ pour coupler les paramètres d'action dans le contexte hors ligne. Il calcule l'a posteriori des effets latents et les a posteriori conditionnels pour les paramètres d'action.
• Résultats : Les auteurs prouvent que sDM atteint une convergence de $O(1/\sqrt{n})$ en sous-optimalité bayésienne sans nécessendre l'hypothèse restrictive de "support complet de logging" (full logging support). La borne dépend de l'alignement entre la politique de logging et la politique optimale.
• Insight : Sous le critère de sous-optimalité bayésienne considéré, il est montré que les politiques gloutonnes sont optimales et peuvent surpasser les politiques pessimistes, contrastant avec les contextes fréquentistes où le pessimisme est souvent nécessaire.

2. L'Optimisation Importe Plus que l'Estimation - Chapitre 7

• Méthodologie : Les auteurs démontrent que dans les grands espaces d'actions, l'erreur d'optimisation domine l'erreur d'estimation. Les objectifs basés sur l'IPS standard induisent des paysages non-concaves qui piègent les optimiseurs.
• Proposition : Au lieu d'estimer la valeur puis d'optimiser, la thèse préconise des objectifs de Log-Vraisemblance Pondérés par la Politique (PWLL) :
  $$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$$
• Résultats : Pour les politiques softmax linéaires, les objectifs PWLL sont concaves (et fortement concaves avec une régularisation $\ell_2$), garantissant un maximum global unique. Des expériences sur des jeux de données comprenant jusqu'à un million d'actions montrent que ces objectifs simples et stables surpassent systématiquement les méthodes sophistiquées basées sur l'estimateur de valeur.

3. Pessimisme Fondé pour le Lissage Exponentiel - Chapitre 8

• Méthodologie : Pour traiter la variance de l'IPS, les auteurs introduisent des estimateurs de Lissage Exponentiel (ES) différentiables qui interpolent entre l'absence de régularisation et une réduction forte de la variance.
• Théorie : Une borne de généralisation PAC-Bayésienne à deux côtés est dérivée pour ces estimateurs régularisés. Cette borne décompose l'erreur en divergence, biais de régularisation et variance résiduelle.
• Application : La borne produit un objectif d'apprentissage pessimiste entièrement différentiable, qui peut être optimisé via la descente de gradient stochastique. Le cadre est unifié pour couvrir d'autres régularisations comme le clipping et l'exploration implicite.
• Extension : Les auteurs introduisent également le Lissage Logarithmique (LS), une alternative douce et différentiable au clipping qui permet d'obtenir des bornes de concentration plus serrées.

Résultats Expérimentaux

Les méthodes proposées sont validées sur des jeux de données synthétiques et réels :

• On-Policy : Dans les bandits linéaires et logistiques synthétiques, meTS et dTS surpassent significativement les bases (LinTS, GLM-TS, HierTS), l'écart de performance s'élargissant à mesure que l'espace d'actions $K$ augmente. Dans les expériences MovieLens (systèmes de recommandation), meTS obtient le regret le plus faible même lorsque le modèle de récompense réel est mal spécifié, démontrant sa robustesse.
• Off-Policy :
  • sDM surpasse les méthodes directes standards, avec des gains croissants à mesure que $K$ augmente.
  • Les objectifs PWLL (Chapitre 7) surpassent systématiquement les méthodes de pointe basées sur l'IPS sur des jeux de données allant jusqu'à un million d'actions, montrant une robustesse supérieure au réglage des hyperparamètres.
  • Les objectifs pessimistes PAC-Bayésiens (Chapitre 8) obtiennent de meilleurs récompenses que les bases (incluant London et al. et Sakhi et al.) à travers diverses qualités de politique de logging, particulièrement quand la politique de logging n'est pas uniforme.

Signification et Revendications

La thèse prétend combler le fossé entre les algorithmes de bandits théoriques et les contraintes des systèmes industriels modernes (ex: systèmes de recommandation avec des millions d'articles). Son argument central est que passer à l'échelle vers de grands espaces d'actions nécessite :

1. Structurer l'Incertitude : Utiliser des priors hiérarchiques et de diffusion pour partager la force statistique entre les actions (On-Policy).
2. Réévaluer les Objectifs : Reconnaître que dans les grands espaces, la tractabilité du paysage d'optimisation est aussi critique que la précision statistique de l'estimateur (Off-Policy).
3. Pessimisme Différentiable : Développer des objectifs pessimistes fondés sur la théorie, mais informatiquement réalisables, qui contrôlent la variance et le biais sans dépendre de constantes intraitables.

Le travail affirme qu'en s'éloignant de la modélisation d'actions indépendantes et de l'estimation de valeur standard, les bandits contextuels peuvent être déployés efficacement dans des environnements où les espaces d'actions dépassent couramment des milliers ou des millions.