Anytime-valid Optimal Policy Identification

Résumé Technique : Identification de Politiques Optimales Valides à Tout Moment

1. Énoncé du Problème

L'article traite du défi consistant à identifier une politique optimale ($\pi^\star$) à partir d'une classe de candidats finie $\Pi = \{\pi_1, \dots, \pi_m\}$ en utilisant des données de bandits contextuels enregistrées. Dans de nombreux contextes pratiques, les données sont générées par une politique d'enregistrement externe ($h_t$) que l'analyste ne contrôle pas. Cette politique d'enregistrement peut être une randomisation fixe ou un algorithme adaptatif optimisé pour des objectifs autres que celui de l'analyste (par exemple, maximiser l'engagement des utilisateurs plutôt que de minimiser la désinformation).

La difficulté centrale réside dans deux contraintes :

1. Contexte Hors-Politique (Off-Policy) : L'analyste doit inférer la valeur des politiques cibles $\nu(\pi)$ à partir de données collectées sous une politique différente $h_t$, sans pouvoir orienter la collecte de données vers l'objectif d'identification.
2. Surveillance Séquentielle : Les praticiens souhaitent souvent surveiller les preuves de manière continue, éliminer les politiques clairement sous-optimales à mesure que les données s'accumulent, et arrêter la collecte de données une fois la politique optimale identifiée, plutôt que de s'engager sur une taille d'échantillon fixe ($N$) à l'avance.

La littérature existante sur l'identification de politiques optimales suppose généralement que l'analyste contrôle la collecte de données (échantillonnage adaptatif) ou ne fournit des garanties inférentielles qu'à une taille d'échantillon fixe et pré-spécifiée. Cet article cherche à combler cette lacune en fournissant des garanties valides à tout moment pour l'identification de politiques optimales hors-politique.

2. Méthodologie

Le cadre proposé construit un ensemble de politiques candidates optimales, $S_t$, qui évolue à mesure que les données arrivent. La méthodologie repose sur trois composantes principales :

A. Pseudo-Résultats à Double Robustesse
Pour estimer les valeurs de politique $\nu(\pi)$ à partir de données enregistrées, la méthode utilise des poids d'importance $w_t(\pi) = \pi(A_t|X_t) / h_t(A_t|X_t)$. Pour améliorer l'efficacité et la stabilité, ceux-ci sont combinés avec un modèle de récompense $b_{rt}(x,a)$ afin de construire des pseudo-résultats à double robustesse (DR). Plus précisément, des pseudo-résultats inférieurs et supérieurs ($\phi^{DRL}_t$ et $\phi^{DRU}_t$) sont définis de telle sorte que leurs espérances conditionnelles soient égales respectivement à la valeur réelle de la politique $\nu(\pi)$ et à $1-\nu(\pi)$. Crucialement, la validité ne dépend pas de la spécification correcte du modèle de récompense, mais seulement des probabilités d'enregistrement connues.

B. Séquences de Confiance (CS) Valides à Tout Moment
S'appuyant sur les travaux de Waudby-Smith et al. (2024), l'article construit des séquences de confiance pour les valeurs de politique. Une séquence d'intervalles $[L_t(\pi), U_t(\pi)]$ est une CS $(1-\alpha)$ si la valeur réelle $\nu(\pi)$ reste dans l'intervalle pour tout $t \geq 1$ avec une probabilité d'au moins $1-\alpha$. Ces intervalles sont construits à l'aide des pseudo-résultats DR et d'un processus de variance $V_t(\pi)$ qui tient compte de l'accumulation de preuves. La largeur de ces intervalles diminue à un taux de $O(\sqrt{(\log \log t + \log m)/t})$.

C. Élimination Séquentielle et Règle d'Arrêt
En utilisant une borne supérieure de l'union sur la classe de politiques $\Pi$, la méthode construit des séquences de confiance simultanées pour toutes les politiques. L'ensemble candidat $S_t$ est défini comme :
$$S_t := \left\{ \pi \in \Pi : U_t\left(\pi; \frac{\alpha}{m}\right) \geq \max_{\pi' \in \Pi} L_t\left(\pi'; \frac{\alpha}{m}\right) \right\}$$
Une politique est éliminée de $S_t$ si sa borne de confiance supérieure tombe en dessous de la borne de confiance inférieure maximale de toute politique concurrente. La procédure s'arrête à un temps dépendant des données $\tau$ lorsque $S_\tau$ devient un singleton (contenant une seule politique).

3. Principales Contributions

L'article présente deux contributions théoriques majeures :

1. Garantie de Couverture Valide à Tout Moment : Les auteurs prouvent que l'ensemble $S_t$ construit satisfait une garantie de couverture uniforme :
   $$P(\Pi^\star \subseteq S_t \text{ pour tout } t \geq 1) \geq 1 - \alpha$$
   où $\Pi^\star$ est l'ensemble des politiques réellement optimales. Cela garantit qu'avec une probabilité élevée, aucune politique optimale n'est jamais éliminée, quel que soit le moment où l'analyste choisit de s'arrêter.

2. Bornes de Complexité d'Échantillonnage : Lorsque la politique $\pi^\star$ est unique, l'article définit un temps d'arrêt $\tau$ pour son identification. Sous une condition de régularité de croissance linéaire de la variance (Hypothèse 1), la complexité d'échantillonnage est dérivée comme suit :
   $$\tau = O\left( \frac{\log m + \log \log(1/\Delta_{\min})}{\Delta_{\min}^2} \right)$$
   où $\Delta_{\min}$ est l'écart entre la meilleure et la deuxième meilleure valeur de politique. Cette borne indique que le nombre d'échantillons requis croît logarithmiquement avec la taille de la classe de politiques et inversement avec le carré de l'écart de sous-optimalité.

4. Résultats Empiriques

L'article valide le cadre via trois démonstrations empiriques :

• Illustration Synthétique : Dans un cadre de bandit contextuel simulé avec six politiques, le cadre a réussi à éliminer précocement les politiques clairement sous-optimales tout en conservant la politique optimale jusqu'à ce qu'elle soit identifiée de manière unique. Les séquences de confiance pour les valeurs de politique ont convergé vers les valeurs réelles comme attendu.
• Efficacité d'Échantillonnage : En comparant la procédure valide à tout moment à un plan à $N$ fixe (où $N$ est calculé sur la base d'un écart cible), les auteurs ont constaté des économies substantielles d'échantillons lorsque le véritable écart était supérieur à l'écart cible. Par exemple, si le véritable écart était le double de l'écart cible, la méthode valide à tout moment a économisé en moyenne 60 à 80 % de la taille d'échantillon prévue.
• Application au Monde Réel : La méthode a été appliquée à une expérience adaptative de grande ampleur (Offer-Westort et al., 2024) impliquant 15 292 utilisateurs au Kenya et au Nigeria, visant à réduire le partage de désinformation. Le cadre a reproduit la conclusion de l'étude originale (identifiant le "incitation à la précision" et les "conseils Facebook" comme les meilleures performances) tout en fournissant une vue dynamique de l'accumulation des preuves. Il a montré que les pires politiques pouvaient être éliminées avec une fraction seulement des données finales, tandis que les meilleurs candidats restaient dans l'ensemble candidat tout au long du processus.

5. Signification et Limites

Signification :
L'article fournit un cadre inférentiel rigoureux pour la surveillance séquentielle dans les contextes hors-politique. Il permet aux analystes de prendre des décisions d'arrêt dépendantes des données sans invalider les garanties statistiques, répondant ainsi à une limitation clé des approches à $N$ fixe. Cela est particulièrement précieux dans les applications réelles où la collecte de données est contrainte par des politiques d'enregistrement externes et où les ressources sont limitées.

Limites :
Les auteurs notent explicitement deux limites :

1. Invariance Temporelle : Le cadre suppose que les valeurs de politique sont constantes dans le temps. Il ne gère pas actuellement les environnements non stationnaires où les effets de traitement évoluent (par exemple, en raison de la nouveauté ou de la fatigue).
2. Exigence de Recouvrement (Overlap) : La méthode exige que chaque politique cible soit absolument continue par rapport à la politique d'enregistrement (recouvrement strict). Cela exclut les scénarios où la politique d'enregistrement assigne de manière déterministe une probabilité nulle à des actions qu'une politique cible emprunterait, ce qui peut se produire dans des algorithmes adaptatifs très concentrés (par exemple, de type UCB).

L'article conclut que bien que ces limites existent, le cadre offre une solution robuste pour une large classe de politiques de logging stochastiques couramment rencontrées en pratique.