Information-Theoretic Generalization Bounds for Sequential Decision Making

Résumé technique : Bornes de généralisation informationnelles pour la prise de décision séquentielle

Énoncé du problème
Les bornes de généralisation informationnelles (IT), en particulier celles fondées sur l'information mutuelle conditionnelle (CMI) et les constructions de suréchantillons, sont devenues un outil standard pour l'analyse dépendante de l'algorithme dans le cadre par lots, indépendant et identiquement distribué (i.i.d.). Ces méthodes mesurent la force du couplage entre les données d'entraînement et la sortie d'un algorithme d'apprentissage en comparant des coordonnées d'entraînement sélectionnées à des coordonnées « fantômes » (non sélectionnées) au sein d'un suréchantillon apparié. Cependant, les cadres CMI existants reposent sur la symétrie des suréchantillons appariés i.i.d., une propriété qui ne s'étend pas directement aux problèmes de prise de décision séquentielle tels que l'apprentissage en ligne, l'apprentissage actif en flux et les bandits stochastiques. Dans ces environnements adaptatifs, les données sont révélées par le biais d'interactions dépendantes de l'historique, et l'apprenant évolue le long d'une trajectoire causale. Un terme CMI terminal mesurant la dépendance à l'égard de l'ensemble du vecteur sélecteur échoue à révéler comment l'information pénètre la trajectoire à des tours spécifiques, rendant difficile le contrôle de l'écart de généralisation dans des environnements adaptatifs.

Méthodologie : Le cadre de suréchantillon séquentiel
Pour remédier aux limites du CMI par lots dans les environnements adaptatifs, les auteurs proposent un cadre de suréchantillon séquentiel qui sépare la filtration de l'apprenant d'un agrandissement côté preuve.

1. Construction causale : Le cadre introduit une construction tour par tour où, à chaque instant $t$, l'environnement génère une paire latente $\tilde{Z}_t = (Z_{t,0}, Z_{t,1})$. Un sélecteur équitable $U_t \in \{0, 1\}$ choisit une coordonnée ($Z_t = Z_{t, U_t}$) que l'apprenant observe et sur laquelle il met à jour. La coordonnée non sélectionnée ($Z'_{t} = Z_{t, 1-U_t}$) reste inobservée par l'apprenant mais est conservée pour l'analyse côté preuve en tant que coordonnée « fantôme ».
2. Séparation de la filtration :
   • Historique de l'apprenant ($H_t$) : Contient uniquement les informations conservées le long du chemin sélectionné (observations passées, états et actions sélectionnées).
   • Agrandissement côté preuve ($G_{t-1}$) : Un champ sigma local défini comme $G_{t-1} = H_{t-1} \vee \sigma(\tilde{Z}_t)$. Ce champ expose la paire complète actuelle $(Z_{t,0}, Z_{t,1})$ uniquement aux fins de la preuve, permettant une comparaison entre les coordonnées sélectionnées et fantômes tout en maintenant que l'état de l'apprenant $W_t$ est généré exclusivement à partir de la coordonnée sélectionnée.
3. CMI séquentielle (SCMI) : Les auteurs définissent la SCMI comme l'information mutuelle entre la perte (ou l'état) induite par l'apprenant et le sélecteur courant, conditionnée par l'agrandissement côté preuve : $I(L^+_t; U_t \mid G_{t-1})$. Cela mesure l'information concernant le sélecteur courant révélée au tour spécifique où la comparaison a lieu, plutôt que d'agréger l'information au temps terminal.
4. Hypothèses : Le cadre repose sur une condition de mise à jour par coordonnée sélectionnée (l'apprenant met à jour uniquement en utilisant la coordonnée sélectionnée) et sur l'échangeabilité ligne par ligne (la distribution conjointe de la paire $(Z_{t,0}, Z_{t,1})$ est invariante par échange, conditionnellement au passé).

Contributions et résultats clés

1. Bornes SCMI générales (Théorème 2) :
   Les auteurs établissent que l'écart de généralisation séquentielle (différence entraînement-holdout) est borné par la somme des termes SCMI tour par tour. Plus précisément, l'écart est contrôlé par la racine carrée de la somme de $I(L^+_t; U_t \mid G_{t-1})$. Ce résultat généralise l'identité CMI par lots aux cadres séquentiels, décomposant l'erreur de généralisation en accroissements causaux d'information du sélecteur.

2. Raffinement de type Bernstein (Théorème 3) :
   Sous une condition de Bernstein (une borne sur le moment conditionnel d'ordre deux de la perte excédentaire), les auteurs dérivent une borne de « taux rapide » où le terme informationnel intervient de manière linéaire plutôt que via une racine carrée. Cela produit des bornes plus serrées lorsque la variance de la perte est faible.

3. Applications à des problèmes séquentiels spécifiques :

   • Apprentissage en ligne (Section 3.3) : Le cadre est appliqué à l'apprentissage en ligne, reliant la SCMI à la complexité de Rademacher séquentielle et à la dimension de Littlestone. Sous la réalisabilité au sens des trajectoires, la somme SCMI est bornée par le logarithme de la croissance des motifs séquentiels, offrant une interprétation combinatoire de la borne informationnelle.
   • Apprentissage actif en flux (Section 4) : Le cadre gère l'apprentissage actif pondéré par l'importance où les décisions de requête sont adaptatives. L'agrandissement côté preuve inclut les pièces de requête et les masques d'étiquettes. Les auteurs dérivent une borne pour le risque de population du prédicteur terminal, montrant que l'écart de généralisation est contrôlé par la SCMI des pertes pondérées par l'importance.
   • Bandits multi-bras stochastiques (Section 5) : Les auteurs appliquent le cadre aux bandits avec lissage (poids exponentiels). Une contribution technique clé ici est une correction de comparaison de sélecteur (Lemme 12) requise car la posteriorité terminale dépend de toute la trajectoire sélectionnée. En utilisant un contexte de preuve conservant le passé et un calcul de variance spécifique à l'écart des bandits, ils dérivent une borne de regret avec une dépendance à l'horizon de $\sqrt{KT}$ (jusqu'à des facteurs logarithmiques et dépendants de l'écart). Cela améliore les bornes existantes de type PAC-Bayes pour les bandits, qui exhibent généralement une dépendance en $O(K^{1/3}T^{2/3})$.

Signification et affirmations
L'article affirme que la contribution principale est le développement d'un cadre de suréchantillon causal qui transforme l'analyse CMI par lots en une somme d'accroissements d'information du sélecteur tour par tour. Cette approche :

• Préserve la comparaison « échantillon fantôme » essentielle aux bornes CMI tout en respectant la causalité de la prise de décision séquentielle.
• Fournit un modèle unifié pour l'analyse de la généralisation dans l'apprentissage en ligne, l'apprentissage actif et les bandits.
• Démontre que la SCMI sert d'analogue séquentiel au CMI par lots, maintenant le lien avec des mesures de complexité combinatoire comme la dimension de Littlestone.
• Offre une dépendance améliorée à l'horizon dans les environnements de bandits grâce à l'intégration de la SCMI avec des bornes de Bernstein sensibles à la variance et une nouvelle correction de comparaison de sélecteur.

Les auteurs notent que leurs bornes sont actuellement des bornes d'espérance pour des pertes bornées. Ils identifient les garanties à haute probabilité, les pertes à queue lourde, le regret dynamique, ainsi que les extensions aux bandits contextuels et à l'apprentissage par renforcement comme des pistes ouvertes pour les travaux futurs. Le cadre est présenté comme un outil pour l'analyse dépendante de l'algorithme, comblant le fossé entre les mesures informationnelles et la structure causale des processus d'apprentissage adaptatif.