Efficient Inference after Directionally Stable Adaptive Experiments

1. Problématique et Contexte

L'article s'intéresse au problème de l'inférence statistique (estimation de paramètres et construction d'intervalles de confiance) dans des contextes de collecte de données adaptatives, tels que les algorithmes de bandits contextuels (ex: LinUCB, Thompson Sampling).

• Le défi : Dans les expériences adaptatives, les actions choisies à chaque étape dépendent des observations passées. Cela brise l'hypothèse d'indépendance et d'identique distribution (i.i.d.) classique. Par conséquent, les estimateurs standards (comme les moindres carrés ordinaires, OLS) peuvent rester cohérents, mais leur distribution asymptotique peut devenir non-normale, rendant l'inférence classique (tests t, intervalles de confiance) invalide.
• L'état de l'art : Les approches existantes tentent de corriger ce problème soit par des méthodes robustes mais conservatrices (séquences de confiance), soit par des scores doublement robustes pondérés par la propension (qui nécessitent une estimation précise des probabilités d'affectation), soit en imposant des conditions de stabilité forte (stabilité de la matrice de covariance complète).
• La limitation des conditions existantes : La condition de stabilité classique (stabilité de la matrice de covariance empirique entière) est souvent trop restrictive pour les algorithmes de bandits modernes qui minimisent le regret en concentrant l'exploration dans certaines directions ("bonnes" directions), créant une accumulation d'information anisotrope. Cette stabilité globale est souvent impossible à garantir sans sacrifier la performance du regret.

2. Contribution Principale : La Stabilité Directionnelle

L'article introduit une notion novatrice appelée stabilité directionnelle (directional stability).

• Concept clé : Au lieu d'exiger que toute la matrice de covariance empirique se stabilise, la stabilité directionnelle exige uniquement que la matrice se stabilise dans la direction spécifique où le paramètre d'intérêt (une cible scalaire) dépend du vecteur de coefficients.
• Avantage : Cette condition est strictement plus faible que la stabilité matricielle globale. Elle est compatible avec les schémas d'exploration anisotropes typiques des algorithmes de regret-minimisation.
• Conséquence majeure : Sous cette condition, les estimateurs qui seraient efficaces sous un échantillonnage i.i.d. (comme l'estimateur en un pas ou one-step estimator) restent asymptotiquement normaux et semi-paramétriquement efficaces même avec des données adaptatives. Aucune pondération par la propension ni stabilisation de variance ad hoc n'est nécessaire.

3. Méthodologie et Cadre Théorique

Les auteurs développent une théorie d'inférence basée sur l'analyse au niveau de la trajectoire (considérant l'histoire complète du bandit comme un seul tirage).

A. Gradient Canonique et Structure de Martingale

• Ils dérivent le gradient canonique (influence function) pour une cible fonctionnelle scalaire $\Psi_T$ définie sur la loi de la trajectoire.
• Sous l'hypothèse d'homoscédasticité, ce gradient prend une forme de martingale :
  $$D^*_T = \frac{1}{T} \sum_{t=1}^T \bar{\alpha}_T(Z_t) (Y_t - h_T(Z_t))$$
  où $\bar{\alpha}_T$ est le représentant de Riesz du paramètre cible.
• La stabilité directionnelle garantit la stabilisation de la variation quadratique prévisible de cette martingale, ce qui permet d'appliquer le Théorème Central Limite pour les Martingales (MCLT) même en régime de haute dimension.

B. Estimateur en Un Pas (One-Step Estimator)

• Les auteurs construisent un estimateur en un pas $\hat{\Psi}_T$ en utilisant des estimateurs régularisés (ridge) pour la régression de sortie ($h_T$) et le représentant de Riesz ($\alpha_T$).
• Résultat surprenant : Cet estimateur est algébriquement identique à l'estimateur en un pas standard utilisé en contexte i.i.d. (ou à un estimateur "plug-in" sous-lissé).
• Théorème 2 : Sous les hypothèses de stabilité directionnelle et de condition de Lindeberg, l'estimateur satisfait une expansion de von Mises et converge vers une loi normale :
  $$\sqrt{T} \frac{\hat{\Psi}_T - \Psi_T}{\hat{\sigma}_T} \xrightarrow{d} N(0, 1)$$

C. Théorie d'Efficacité

• Ils établissent un théorème de convolution pour une séquence d'expériences indexées par l'horizon $T$.
• Ils définissent la régularité des estimateurs le long de sous-modèles défavorables (least favorable submodels).
• Théorème 4 : Tout estimateur régulier satisfait une borne inférieure de variance (borne d'efficacité semi-paramétrique). L'estimateur en un pas atteint cette borne, prouvant qu'il est asymptotiquement efficace.

4. Application à LinUCB

L'article valide théoriquement ces résultats sur l'algorithme LinUCB (Linear Upper Confidence Bound), un cas d'usage majeur où la stabilité matricielle globale échoue souvent.

• Analyse : En utilisant la décomposition spectrale de la matrice de design empirique sous LinUCB (basée sur des travaux récents de Fan et al.), ils montrent que la stabilité directionnelle est satisfaite.
• Résultat : C'est la première garantie d'efficacité semi-paramétrique pour une cible scalaire régulière sous un échantillonnage LinUCB.
• Condition de régulation : Ils montrent que le compromis entre l'exploration (bonus d'exploration $\gamma$) et la dimension $d_T$ doit être soigneusement réglé pour que la stabilité directionnelle et la minimisation du regret coexistent (le terme d'erreur doit être $o(1)$).

5. Résultats Clés et Signification

1. Simplicité de l'inférence : Contrairement aux méthodes précédentes qui nécessitent des corrections complexes (pondération par propension, estimation de variance conditionnelle), la méthode proposée permet d'utiliser des estimateurs standards (OLS régularisé) sans modification, tant que la stabilité directionnelle est vérifiée.
2. Robustesse à l'anisotropie : La théorie reconnaît que l'information n'a pas besoin d'être uniforme dans toutes les directions pour permettre une inférence valide sur un paramètre spécifique. Seule la direction pertinente doit être stable.
3. Haute Dimension : La méthode fonctionne dans des régimes de haute dimension où $d_T$ peut croître avec $T$ (sous certaines conditions de régularisation), là où les asymptotiques classiques de l'OLS échouent.
4. Optimalité : L'estimateur proposé atteint la borne d'efficacité de Cramér-Rao semi-paramétrique adaptée au contexte adaptatif.

Conclusion

Cet article résout un problème fondamental en apprentissage par renforcement et en inférence adaptative. Il démontre que la complexité de l'inférence sous l'adaptativité ne réside pas dans la nécessité de méthodes compliquées, mais dans la compréhension de la géométrie directionnelle de la stabilité du design expérimental. En affaiblissant la condition de stabilité de "globale" à "directionnelle", les auteurs ouvrent la voie à une inférence efficace, simple et théoriquement fondée pour les algorithmes de bandits modernes comme LinUCB.