Résumé Technique : Apprentissage Hors-Politique Séquentiel avec Lissage Logarithmique

Énoncé du Problème

L'apprentissage hors-politique permet l'entraînement de politiques à partir de données d'interaction journalisées générées par une politique de comportement. Bien que les fondements théoriques de l'apprentissage hors-politique soient bien établis dans le mode par lots (où une seule politique est apprise à partir d'un jeu de données statique généré par une politique de comportement), les systèmes réels fonctionnent différemment. En pratique, les politiques sont mises à jour et redéployées de manière répétée de façon séquentielle : une politique est entraînée sur l'ensemble des données historiques, déployée pour générer de nouvelles interactions, puis réentraînée sur le jeu de données élargi pour l'itération suivante.

Malgré l'omniprésence de ce paradigme séquentiel dans des applications telles que les systèmes de recommandation et le placement publicitaire, il reste largement inexploré sur le plan théorique. Les approches séquentielles existantes reposent souvent sur des hypothèses fortes, telles qu'une couverture uniforme de l'espace d'actions ou des stratégies de collecte de données irréalistes (par exemple, des tailles de lots croissant de manière exponentielle). De plus, les algorithmes hors-ligne actuels les plus avancés, qui utilisent le principe de pessimisme et les cadres PAC-Bayésiens, n'ont pas été étendus avec succès au contexte séquentiel avec des garanties de convergence rigoureuses. Cet article comble le fossé entre le déploiement séquentiel pratique et les garanties théoriques, visant à développer des algorithmes d'apprentissage hors-politique séquentiel qui soient à la fois théoriquement solides et empiriquement efficaces.

Méthodologie

Les auteurs proposent un cadre basé sur les Bandits Contextuels où un agent interagit avec un flux de données au cours des pas de temps $k \geq 0$. À chaque étape, une nouvelle politique de comportement $\pi_k$ est déployée pour collecter un lot de données $S_k$, et l'agent met à jour sa politique en utilisant l'historique cumulatif $S_{0:k}$.

La méthodologie repose sur deux contributions algorithmiques principales, toutes deux exploitant les outils d'apprentissage PAC-Bayésien en ligne et les estimateurs de Lissage Logarithmique (LS) :

1. Lissage Logarithmique Séquentiel (Algorithme 1)

La première contribution étend l'estimateur de Lissage Logarithmique hors-ligne (introduit par Sakhi et al., 2024) au contexte séquentiel.

• Estimateur : L'algorithme utilise le régularisateur LS standard $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$.
• Mécanisme : À chaque étape $k$, l'algorithme minimise une borne supérieure PAC-Bayésienne sur le risque, combinant le risque LS empirique sur toutes les données accumulées $S_{0:k}$ et un terme de divergence KL par rapport à une loi a priori $P$.
• Garantie Théorique : Le théorème 3.2 établit une borne de généralisation pour la sortie séquentielle $\pi_{k+1}$. Le taux de convergence est montré comme étant $O(1/\sqrt{N_k})$, où $N_k$ est le nombre total d'échantillons. Cela correspond au taux optimal du mode par lots mais s'applique à l'accumulation séquentielle de données.
• Limitation : Les auteurs identifient que le terme de pseudo-variance dans la borne de convergence ne disparaît pas même si la politique de comportement approche la politique optimale, conduisant à un taux de convergence qui ne s'accélère pas au-delà de $O(1/\sqrt{N_k})$.

2. Lissage Logarithmique Ajusté Séquentiel (Algorithme 2)

Pour surmonter la convergence lente de l'Algorithme 1, les auteurs introduisent un nouvel estimateur de Lissage Logarithmique Ajusté (AdjLS).

• Estimateur : Un nouveau régularisateur est défini : $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. Cet ajustement modifie l'objectif de performance pour contrôler la différence entre le risque de la politique actuelle et une moyenne pondérée des risques passés.
• Mécanisme : L'Algorithme 2 minimise l'estimateur de risque ajusté sur les données cumulatives.
• Garantie Théorique : Le théorème 4.4 prouve que sous des hypothèses légères (spécifiquement, que les actions optimales sont couvertes par la classe de politiques et que le problème présente un certain degré de séparabilité, quantifié par $\Delta_u > 0$), l'Algorithme 2 atteint un taux de convergence accéléré de $O(1/N_k^\alpha)$ pour tout $\alpha \in [0.5, 1)$.
• Insight Clé : Contrairement à l'estimateur LS standard, le terme d'erreur de l'estimateur ajusté $L(\pi^*, \pi_j)$ disparaît lorsque la politique de comportement $\pi_j$ approche la politique optimale $\pi^*$, permettant une convergence plus rapide.

Contributions Clés

1. Premiers Algorithmes PAC-Bayésiens Séquentiels : L'article présente les premiers algorithmes PAC-Bayésiens hors-politique conçus spécifiquement pour le contexte séquentiel, fournissant des garanties de convergence théorique qui interpolent entre les régimes entièrement par lots et entièrement en ligne.
2. Convergence Accélérée par Ajustement : Les auteurs identifient une limitation fondamentale dans l'application séquentielle des estimateurs hors-ligne standards et proposent un ajustement principiel (AdjLS) qui produit des taux de convergence prouvés comme accélérés sous des hypothèses raisonnables.
3. Hypothèses Assouplies : L'analyse théorique nécessite uniquement que la classe de politiques couvre les actions optimales (Hypothèse 3.4), ce qui est strictement plus faible que les hypothèses de couverture uniforme requises par les travaux séquentiels précédents (par exemple, Zenati et al., 2023).
4. Généralisation aux Contextes Non-IID : Le cadre est montré comme adaptable aux environnements non stationnaires où les distributions de contexte évoluent au fil du temps, assouplissant l'hypothèse d'indépendance et d'identité de distribution (i.i.d.) sur les contextes.

Résultats Empiriques

Les auteurs évaluent leurs méthodes sur des jeux de données multiclasse standards (MNIST, FashionMNIST, EMNIST, CIFAR100) convertis en problèmes de bandits contextuels.

• Séquentiel vs Par Lots : Les expériences démontrent que l'augmentation du nombre de mises à jour intermédiaires de la politique ($k$) améliore systématiquement les performances finales de la politique par rapport à une seule mise à jour par lot ($k=1$). Cela valide l'avantage du cadre séquentiel.
• Comparaison d'Algorithmes :
  • SeqAdjLS (Algorithme 2) surpasse constamment SeqLS (Algorithme 1), confirmant l'avantage théorique de l'estimateur ajusté.
  • Les deux méthodes proposées surpassent significativement SCRM (Minimisation du Risque Contrefactuel Séquentiel, Zenati et al., 2023). Les auteurs notent que SCRM a tendance à être excessivement conservateur, surtout au début des tours avec de petites tailles de lots, et repose sur des stratégies de collecte de données irréalistes (lots croissant de manière exponentielle) qui rejettent les données historiques.
• Impact de la Politique Initiale : L'approche séquentielle montre des gains substantiels lorsque la politique de comportement initiale est loin de l'optimum, en particulier dans les espaces d'actions de haute dimension (par exemple, CIFAR100 avec 100 actions).

Importance et Revendications

L'article revendique combler le fossé théorique entre l'apprentissage hors-politique séquentiel pratique et les garanties rigoureuses. En combinant des techniques PAC-Bayésiennes en ligne avec un nouvel estimateur de lissage logarithmique, les auteurs fournissent des algorithmes qui :

• Généralisent les approches hors-ligne les plus avancées (en égalant leurs performances dans la limite du mode par lots).
• Accélèrent l'apprentissage dans les contextes séquentiels en exploitant le raffinement progressif de la politique de comportement.
• Évitent les hypothèses irréalistes (comme la couverture uniforme) qui entravent l'applicabilité des méthodes séquentielles existantes.

Les auteurs soulignent que, bien que leur analyse théorique repose sur le fait que la classe de politiques couvre les actions optimales, cela constitue un assouplissement significatif par rapport aux travaux antérieurs. Ils concluent que la combinaison du PAC-Bayésien en ligne et des bandits contextuels séquentiels offre une direction prometteuse pour un apprentissage robuste et efficace dans les systèmes dynamiques du monde réel.