Off-Policy Learning in Large Action Spaces: Optimization Matters More Than Estimation

Résumé Technique : L'apprentissage hors-politique dans les espaces d'actions de grande dimension : l'optimisation importe plus que l'estimation

Énoncé du problème
L'apprentissage hors-politique (Off-Policy Learning - OPL) dans les bandits contextuels hors-ligne vise à apprendre une politique $\hat{\pi}$ à partir de données enregistrées $D_n = \{(X_i, A_i, R_i)\}$ qui maximise l'espérance de la récompense $V(\pi)$. Le paradigme dominant consiste à optimiser un estimateur d'évaluation hors-politique (Off-Policy Evaluation - OPE), typiquement basé sur le score d'importance inverse (Inverse Propensity Scoring - IPS), tel que $\hat{\pi} = \arg\max_\pi \hat{V}_{IPS}(\pi)$. Alors que la recherche récente s'est concentrée sur le développement d'estimateurs sophistiqués dotés de meilleures propriétés statistiques (par exemple, une variance ou un biais réduits) pour approximer plus précisément $V(\pi)$, cet article soutient que cette approche centrée sur l'estimateur néglige un obstacle pratique critique : le paysage d'optimisation.

Dans les espaces d'actions de grande dimension (où le nombre d'actions $K$ peut atteindre des millions), les objectifs basés sur l'IPS couplés à des paramétrages de politique standards (par exemple, softmax) présentent de graves pathologies d'optimisation. Celles-ci incluent de longs plateaux où la montée de gradient stagne et un nombre exponentiel de maxima locaux médiocres. L'article postule que même des estimateurs dotés de garanties statistiques supérieures échouent à produire de bonnes politiques car le problème d'optimisation sous-jacent devient intraitable à mesure que $K$ augmente.

Méthodologie et Analyse
Les auteurs fournissent à la fois une analyse théorique et des preuves empiriques pour soutenir l'affirmation selon laquelle la stabilité de l'optimisation est plus critique que la précision de l'estimation dans les espaces d'actions de grande dimension.

1. Analyse théorique des objectifs basés sur l'IPS :

   • L'article analyse les « politiques oracle » (les maximisateurs théoriques de l'objectif attendu) pour divers estimateurs basés sur l'IPS, incluant l'IPS standard, l'IPS tronqué (cIPS), l'Exponential Smoothing (ES), le Doubly Robust (DR), le Marginalized IPS (MIPS), l'OffCEM, le POTEC et le Policy Convolution (PC).
   • Pathologies d'optimisation : Les auteurs prouvent que pour les estimateurs linéaires en $\pi$ avec des politiques softmax, la montée de gradient peut rester piégée dans des régions sous-optimales pendant $O(K_{eff})$ itérations, où $K_{eff}$ est la taille de l'espace d'actions effectif. De plus, le paysage contient un nombre de maxima locaux exponentiel en $K_{eff}$.
   • Le rôle de $K_{eff}$ : Même les méthodes conçues pour les grands espaces d'actions (comme MIPS ou OffCEM) échouent souvent à atténuer ce problème si elles optimisent sur l'espace d'actions complet $A$ ($K_{eff} = K$). La seule exception identifiée est POTEC, qui restreint l'optimisation à un niveau de cluster, réduisant ainsi efficacement $K_{eff}$.
   • Paramétrage conscient de l'objectif : Les auteurs proposent d'aligner la classe de politique avec le biais inductif de l'estimateur. Par exemple, restreindre le support de la politique au support de la politique d'enregistrement $S_0$ pour les méthodes basées sur l'IPS, ou utiliser une décomposition en deux étapes pour les méthodes basées sur les clusters, peut réduire $K_{eff}$ et améliorer la capacité d'entraînement sans changer la cible statistique. Cependant, cela ne fait que mitiger les symptômes ; cela ne guérit pas la non-concavité fondamentale des objectifs basés sur l'IPS.

2. Objectifs de Log-Vraisemblance Pondérés par la Politique (Policy-Weighted Log-Likelihood - PWLL) :

   • Comme alternative fondamentale, l'article explore les objectifs PWLL, qui prennent la forme $\hat{U}_g(\pi) = \frac{1}{n} \sum g(R_i, \pi_0(A_i|X_i) \log \pi(A_i|X_i)$.
   • Concavité : Contra à les objectifs IPS, les objectifs PWLL sont intrinsèquement concaves (et fortement concaves avec une régularisation $\ell_2$) lorsqu'on utilise des politiques linéaires-softmax. Cela est dû au fait que la correspondance entre les scores et les log-probabilités est concave.
   • Garanties d'optimisation : Les auteurs établissent que la montée de gradient stochastique sur les objectifs PWLL atteint des taux de convergence globale de $O(1/\sqrt{T})$ en général, s'accélérant vers des taux géométriques avec la régularisation.
   • Variantes : L'étude évalue des variantes spécifiques de PWLL, notamment le Local Policy Improvement (LPI), le Clipped LPI (cLPI) et le Regularized KL (RegKL). Notamment, il est démontré que le cLPI induit la même règle de décision gloutonne que le cIPS mais via un problème d'optimisation convexe.

Principales Contributions

1. Théorie de l'échelle de l'optimisation avec l'espace d'actions : L'article formalise comment les pathologies d'optimisation (plateaux et maxima locaux) évoluent avec le nombre d'actions $K$, expliquant pourquoi les objectifs basés sur l'IPS deviennent de plus en plus difficiles à optimiser à mesure que $K$ croît.
2. Paramétrage conscient de l'objectif : Les auteurs identifient des structures de politique minimales suffisantes pour divers objectifs (dérivées des politiques oracle) et démontrent que restreindre ou factoriser la politique pour correspondre à ces structures améliore la capacité d'entraînement et la performance.
3. PWLL comme un objectif favorable à l'optimisation : L'article démontre que pour les politiques linéaires-softmax, les objectifs PWLL produisent des paysages d'optimisation bien comportés et concaves, offrant une alternative robuste à la maximisation directe de la valeur.
4. Tests de stress empiriques à grande échelle : Des expériences approfondies sur trois jeux de données à grande échelle (MovieLens avec $K=60k$, Twitch avec $K=200k$, et GoodReads avec $K=1M$) montrent que les méthodes basées sur l'IPS sont très sensibles aux hyperparamètres (taille de lot, calendriers de taux d'apprentissage), tandis que les méthodes PWLL sont robustes et atteignent systématiquement des récompenses plus élevées.
5. Orientation actionnable : L'article distille des règles de conception pour les grands espaces d'actions : prioriser la stabilité de l'optimisation en utilisant des paramétrages conscients de l'objectif et préférer les objectifs de type PWLL aux estimateurs IPS complexes pour l'apprentissage de politique.

Résultats

• Sensibilité à l'optimisation : Dans des balayages contrôlés, les objectifs basés sur l'IPS (incluant des méthodes de pointe comme POTEC) ont montré une variance élevée et un effondrement des performances sous des hyperparamètres sous-optimaux. En revanche, les méthodes PWLL (spécifiquement cLPI) ont maintenu une performance élevée dans toutes les configurations.
• Estimation vs Apprentissage : L'article met en évidence un résultat contre-intuitif : les méthodes ayant une erreur quadratique moyenne (MSE) plus faible en tant qu'estimateurs de valeur (ex: MIPS) n'ont pas nécessairement produit de meilleures politiques. Inversement, les méthodes PWLL, qui sont de mauvais estimateurs de valeur (MSE élevé), ont produit les meilleures politiques. Cela suggère que dans les grands espaces d'actions, la capacité à optimiser l'objectif est un prédicteur plus fort de la qualité de la politique que la précision statistique de l'estimation de la valeur.
• Impact du paramétrage : Restreindre l'espace d'actions effectif pour correspondre au biais inductif de l'objectif (par exemple, utiliser des politiques à support restreint pour l'IPS) a considérablement amélioré la stabilité et la performance des méthodes IPS, bien qu'elles restent en retrait par rapport aux méthodes PWLL.
• Robustesse : Les méthodes PWLL ont démontré une robustesse supérieure au bruit de récompense et aux différents supports de la politique d'enregistrement par rapport aux approches basées sur l'IPS.

Signification et Revendications
L'article affirme que le domaine de l'apprentissage hors-politique s'est trop concentré sur le raffinement des estimateurs tout en négligeant le paysage d'optimisation, un goulot d'étranglement critique dans les grands espaces d'actions. Les auteurs soutiennent que :

• L'optimisation est le goulot d'étranglement : Dans les grands espaces d'actions, la difficulté d'optimiser les objectifs IPS non-concaves mine l'utilité pratique même des estimateurs les plus statistiquement sophistiqués.
• La simplicité l'emporte : Les objectifs plus simples et favorables à l'optimisation comme le PWLL (spécifiquement le cLPI) surpassent les estimateurs IPS complexes et réduisant la variance, car ils permettent une convergence stable et fiable.
• Changement de conception : Le développement d'algorithmes d'OPL pour les grands espaces d'actions doit explicitement traiter les considérations d'optimisation. L'article préconise un passage d'une conception « centrée sur l'estimateur » à une conception « centrée sur l'optimisation », suggant que garantir un paysage d'optimisation traitable est plus important que d'obtenir une estimation de valeur de haute fidélité pour l'apprentissage d'une politique.

Les auteurs notent des limites : les objectifs PWLL ne sont pas adaptés à l'évaluation hors-politique (OPE) ou à la sélection de politique où des estimations de valeur précises sont requises. De plus, les garanties de concavité pour PWLL tiennent strictement pour les politiques linéaires-softmax ; bien que les réseaux profonds puissent perdre la concavité formelle, la structure du gradient reste plus bénigne que celle des objectifs basés sur l'IPS.