Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Énoncé du Problème

L'article traite de l'efficacité statistique de l'apprentissage hors ligne dans les bandits contextuels (CB) lorsque l'objectif d'apprentissage implique une régularisation par divergence de Kullback-Leibler directe (Forward-KL). La fonction objectif est définie comme suit :
$$J_{FKL}(\pi) := \mathbb{E}[r] - \eta^{-1} \text{KL}(\pi_{\text{ref}} \| \pi)$$
où $r$ est la récompense, $\eta$ est l'intensité inverse de la régularisation, et $\pi_{\text{ref}}$ est une politique de référence (comportementale).

Alors que la régularisation par divergence de Kullback-Leibler inverse ($\text{KL}(\pi \| \pi_{\text{ref}})$) a été largement étudiée et s'est avérée admettre une complexité d'échantillonnage de $\tilde{O}(\epsilon^{-1})$ (taux rapides) sous concentrabilité d'une seule politique (où la politique de comportement ne couvre que la politique optimale), le cas Forward-KL reste un problème ouvert. Les analyses existantes pour Forward-KL soit ne s'appliquent pas, soit aboutissent à des taux lents de $\tilde{O}(\epsilon^{-2})$. De plus, il est incertain que la concentrabilité d'une seule politique soit suffisante pour Forward-KL, étant donné que Forward-KL est « couvrant la masse » (pénalisant $\pi \to 0$ là où $\pi_{\text{ref}} > 0$) plutôt que « recherche de modes », ce qui pourrait nécessiter des hypothèses de couverture plus fortes.

L'article cherche à répondre à deux questions fondamentales :

1. Quel est le taux statistique de prise de décision pour les objectifs régularisés par Forward-KL ?
2. La concentrabilité d'une seule politique est-elle suffisante pour un apprentissage hors ligne optimal en taux dans ce contexte ?

Méthodologie

Les auteurs proposent une analyse simplifiée pour les Bandits Contextuels Pessimistes Régularisés par Forward-KL (FKL-PCB). La méthodologie s'écarte considérablement des travaux antérieurs qui reposent sur les développements de Taylor et le théorème de la valeur moyenne (MVT).

1. Rejet de l'analyse traditionnelle basée sur le MVT :
Les travaux antérieurs analysant les objectifs régularisés utilisent souvent un développement de Taylor autour d'un point intermédiaire $\bar{u}$ (via le théorème de la valeur moyenne) pour décomposer le gap de sous-optimalité. Pour le KL inverse, les termes résultants présentent une propriété de monotonie sous le pessimisme qui permet de borner l'erreur en utilisant la concentrabilité d'une seule politique.
Cependant, les auteurs démontrent (via le lemme 5.3) que pour Forward-KL, la dérivée du terme de décomposition de la sous-optimalité implique une « asymétrie inclinée » d'une variable aléatoire centrée. Le signe de cette dérivée est indéfini, ce qui signifie que l'argument de monotonie échoue. Par conséquent, les routines standard basées sur le MVT ne peuvent pas atteindre des taux rapides sans recourir à des hypothèses de concentrabilité plus fortes (toutes les politiques).

2. Pipeline d'analyse convexe :
Pour contourner les limites du MVT, les auteurs introduisent une nouvelle technique de preuve basée sur les conjugués convexes et les divergences de Bregman :

• Perspective duale : Ils caractérisent l'objectif régularisé via son conjugué convexe sur le simplexe de probabilité.
• Argument d'auto-borne : Ils dérivent une identité pour le gap de sous-optimalité (lemme 5.5) qui exprime l'erreur directement en fonction du carré de la différence entre la récompense réelle et l'estimation pessimiste, pondérée par le rapport entre la politique optimale et la politique de référence.
• Identité clé : La contribution technique centrale est l'inégalité :
  $$\text{SubOpt}_{FKL}(\hat{\pi}) \leq 2\eta \sum_{a} \frac{(\pi^*_{FKL}(a))^2}{\pi_{\text{ref}}(a)} (r(a) - \hat{r}(a))^2$$
  Cette borne dépend uniquement du coefficient de concentrabilité d'une seule politique $C_{\pi^*} = \sup \frac{\pi^*}{\pi_{\text{ref}}}$, évitant ainsi le besoin de concentrabilité pour toutes les politiques.

3. Conception de l'algorithme :
L'article présente FKL-PCB, un algorithme pessimiste applicable aux deux contextes tabulaire et d'approximation de fonction :

• Estimation : Utilise les moindres carrés pour estimer la fonction de récompense.
• Pessimisme : Soustrait un terme de pénalité (borne de confiance) pour garantir que la récompense estimée $\hat{r}$ est minorée par la récompense réelle $r$ avec une forte probabilité.
• Optimisation : Produit la politique maximisant l'objectif régularisé pessimiste.

Contributions et Résultats Clés

1. Bornes supérieures de complexité d'échantillonnage rapides :
L'article établit les premières bornes de complexité d'échantillonnage de $\tilde{O}(\epsilon^{-1})$ pour les CB hors ligne régularisés par Forward-KL sous concentrabilité d'une seule politique :

• Contexte tabulaire : $\tilde{O}\left( \eta (C_{\pi^*})^2 |S||A| \epsilon^{-1} \right)$.
• Approximation de fonction : $\tilde{O}\left( \eta C_{\pi^*} D^2_{\pi^*} \log N_G \epsilon^{-1} \right)$, où $D^2_{\pi^*}$ est un coefficient de concentrabilité de type $D^2$ et $N_G$ est le nombre de recouvrement de la classe de fonctions.
• Ces résultats améliorent la borne précédente de l'état de l'art $\tilde{O}(\epsilon^{-2})$ d'Aminian et al. (2025) et relâchent l'exigence passant de la concentrabilité pour toutes les politiques à la concentrabilité d'une seule politique.

2. Bornes inférieures minimax :
Les auteurs fournissent des bornes inférieures correspondantes pour démontrer la justesse de leurs bornes supérieures :

• Borne inférieure tabulaire : $\Omega(\eta |S||A| \epsilon^{-1})$ dans le régime de forte régularisation. Cela confirme que la dépendance linéaire en $\eta$ et le taux $1/\epsilon$ sont optimaux.
• Transition de phase : Les bornes inférieures révèlent une « transition de phase » similaire au KL inverse. Dans le régime de faible régularisation (grand $\eta$), la complexité d'échantillonnage revient au taux lent $\tilde{O}(\epsilon^{-2})$, indiquant que la régularisation est nécessaire pour atteindre des taux rapides.

3. Nouveauté technique :
L'article affirme que le « pipeline d'analyse convexe » unifie les contextes tabulaire et d'approximation de fonction et contourne complètement les routines de preuve basées sur le théorème de la valeur moyenne. Cette approche est présentée comme étant d'intérêt indépendant pour l'analyse d'autres problèmes de prise de décision régularisés par divergence.

Importance et Revendications

L'article se positionne comme le premier travail à caractériser exactement les taux statistiques pour la régularisation Forward-KL dans l'apprentissage hors ligne. Son importance principale réside dans :

• Résolution d'un problème ouvert : Il tranche la question de savoir si la concentrabilité d'une seule politique est suffisante pour Forward-KL, en répondant par l'affirmative avec des taux rapides.
• Théorie unifiée : Il démontre que la nature « couvrant la masse » de Forward-KL n'exige pas intrinsèquement des hypothèses de couverture plus fortes que le KL inverse « recherche de modes », à condition d'utiliser une approche analytique novatrice.
• Simplicité algorithmique : Il montre qu'un algorithme minimaliste basé sur le pessimisme (FKL-PCB) suffit pour atteindre ces taux optimaux, sans nécessiter de modifications algorithmiques complexes.

Les auteurs restent modestes concernant les orientations futures, notant que s'ils établissent la suffisance, la nécessité de la concentrabilité d'une seule politique pour Forward-KL (même dans les bandits à plusieurs bras) reste une question ouverte. De plus, la dérivation d'une borne inférieure correspondant à la borne supérieure spécifiquement pour le coefficient de concentrabilité de type $D^2$ dans l'approximation de fonction est laissée pour un travail ultérieur.