Résumé technique : Une définition information-théorique de l'apprentissage à ouverture infinie (Open-Ended Learning)

Énoncé du problème

L'article traite de l'absence d'une définition théorique cohérente de l'ouverture infinie (open-endedness) pour les systèmes d'IA. Bien que la littérature existante caractérise les environnements à ouverture infinie comme ceux présentant des tâches de plus en plus nouvelles et complexes, ou les définit via la nouveauté et la capacité d'apprentissage des artefacts produits par l'agent, ces définitions ne parviennent pas à capturer si un agent peut améliorer durablement ses capacités par l'interaction. Générer des politiques nouvelles n'implique pas nécessairement l'acquisition d'informations permettant une amélioration des performances.

Les auteurs proposent de formaliser l'ouverture infinie en étudiant la relation entre l'espérance de la récompense et l'information requise pour atteindre cette récompense. La question centrale est la suivante : un environnement permet-il une amélioration soutenue de la récompense qui nécessite l'acquisition continue d'informations utiles à un taux non nul ?

Méthodologie et définitions

L'équivalent en bits

La contribution méthodologique centrale est l'introduction de l'équivalent en bits ($B_\rho$). Ce concept quantifie la quantité minimale d'information (mesurée en nats) concernant le paramètre de l'environnement $\theta$ requise pour sélectionner une action qui produit une espérance de récompense d'au moins $\rho$.

Formellement, pour un niveau d'espérance de récompense $\rho$ :
$$B_\rho = \inf_{A: \mathbb{E}[r_\theta(A)] \geq \rho} I(\theta; A)$$
où $I(\theta; A)$ est l'information mutuelle entre le paramètre de l'environnement et l'action.

Équivalent en bits moyen et ouverture infinie

La performance d'un agent $\pi$ sur un temps $T$ est caractérisée par l'équivalent en bits moyen ($B_T(\pi)$), défini comme la moyenne temporelle des équivalents en bits des récompenses obtenues :
$$B_T(\pi) = \frac{1}{T} \sum_{t=0}^{T-1} B_{\mathbb{E}_\pi[R_{t+1}]}$$

Définition de l'ouverture infinie : Un environnement est défini comme étant à ouverture infinie s'il existe un agent $\pi$ tel que l'équivalent en bits moyen croît linéairement avec le temps :
$$B_T(\pi) = \Omega(T)$$
Un agent réalise un apprentissage à ouverture infinie s'il atteint ce taux de croissance linéaire.

Cadre analytique

Les auteurs analysent cette définition dans le contexte des environnements de bandits. Ils distinguent :

1. Le gain d'information ($\gamma_T$) : L'information mutuelle totale $I(\theta; H_T)$ contenue dans l'historique.
2. La croissance de l'équivalent en bits : L'information spécifique requise pour l'amélioration des récompenses.

L'article établit que si un gain d'information sous-linéaire implique une absence d'ouverture infinie, un gain d'information linéaire n'est pas suffisant pour l'ouverture infinie. Un environnement peut permettre une acquisition d'information linéaire, mais si cette information ne se traduit pas par une croissance soutenue de l'équivalent en bits pertinent pour la récompense, l'environnement n'est pas à ouverture infinie.

Contributions clés et résultats

1. Résultats négatifs : Les environnements classiques ne sont pas à ouverture infinie

L'article prouve que plusieurs environnements de bandits standards ne répondent pas au critère d'ouverture infinie :

• Bandits à bras finis : Même avec un bruit non gaussien permettant un gain d'information infini, l'ensemble d'actions fini limite l'équivalent en bits par $\log |A|$. Ainsi, $B_T(\pi) \leq \log |A|$, ce qui n'est pas $\Omega(T)$.
• Bandits linéaires à dimensions finies (Gaussiens) : Le gain d'information croît comme $O(d \log T)$, ce qui est sous-linéaire ($o(T)$).
• Bandits à processus gaussiens (GP) : Sous les hypothèses standards de noyaux (ex: Matérn, exponentiel carré), la décroissance spectrale des valeurs propres du noyau garantit que le gain d'information est sous-linéaire.
• Bandits à bras infinis (moyennes i.i.d.) : Malgré un gain d'information potentiellement non borné, l'équivalent en bits moyen croît au plus logarithmiquement ($O(\log T)$) car le faible couplage entre les bras indépendants empêche une croissance linéaire de l'information utile.

2. Résultat positif : Le « Bandit Linéaire Insatiable »

Les auteurs construisent un environnement spécifique, le bandit linéaire insatiable, qui est à ouverture infinie.

• Configuration : L'ensemble d'actions $A$ consiste en des vecteurs binaires à dimensions infinies avec support fini ($a \in \{0,1\}^\mathbb{N}, \|a\|_1 < \infty$). Le paramètre $\theta \in \mathbb{R}^\mathbb{N}$ possède des composantes indépendantes $\theta_i \sim \mathcal{N}(-1, 1)$. La récompense est $r_\theta(a) = \langle \theta, a \rangle + \text{bruit}$.
• Propriété clé : Contrairement aux bandits GP, les valeurs propres du noyau dans la base de coordonnées ne sont pas sommables, violant les conditions de queue spectrale qui limitent le gain d'information.
• Résultat : Les auteurs prouvent que $B_T(\pi) = \Omega(T)$ pour cet environnement, satisfaisant la définition de l'ouverture infinie.

3. Échec et succès algorithmiques

L'article analyse pourquoi les algorithmes classiques échouent dans le bandit linéaire insatiable et propose une alternative réussie :

• Échec de l'échantillonnage de Thompson (TS) : Le TS standard tente d'optimiser sur le postérieur complet à dimensions infinies. Comme l'échantillon du postérieur $\theta^{(t)}$ possède une infinité de coordonnées positives avec une probabilité 1, le supremum de la récompense est inatteignable au sein de l'ensemble d'actions valide $A$. Même avec une troncature finie, l'espérance de la récompense du maximisateur diverge vers $-\infty$ à mesure que la taille de la troncature augmente.
• Échec de la troncature fixe (FT) : Fixer une dimension finie $M$ limite l'acquisition d'information à $O(M \log 2)$, empêchant la croissance linéaire.
• Succès de l'échantillonnage de Thompson tronqué (TTS) : Les auteurs introduisent le TTS, qui utilise une séquence de cibles d'apprentissage. Au lieu d'apprendre l'intégralité de $\theta$ ou d'utiliser une approximation statique, l'agent augmente dynamiquement le niveau de troncature $m_t$ au fil du temps.
  • Mécanisme : L'agent choisit un niveau de troncature $m_t$ basé sur l'historique, échantillonne le postérieur pour les $m_t$ premières coordonnées, et agit de manière optimale pour ce paramètre tronqué.
  • Garantie théorique : En planifiant soigneusement la croissance de $m_t$ (équilibrant l'exploration de nouvelles coordonnées et l'exploitation des anciennes), le TTS atteint une récompense cumulative de $\Omega(T^2)$. Puisque la croissance de la récompense implique une croissance de l'équivalent en bits dans ce contexte, le TTS atteint $B_T(\pi) = \Omega(T)$, prouvant ainsi un apprentissage à ouverture infinie.

Signification et limites

Signification

L'article fournit la première définition quantitative et information-théorique de l'ouverture infinie qui lie directement l'amélioration des performances à l'acquisition d'informations utiles. Il démontre que :

1. La récompense seule est insuffisante : Des récompenses élevées ou non bornées ne garantissent pas l'ouverture infinie ; le coût informationnel pour atteindre ces récompenses est la métrique critique.
2. Les hypothèses classiques sont insuffisantes : Des récompenses non bornées et des ensembles d'actions infinis (souvent supposés permettre l'ouverture infinie) ne sont pas des conditions suffisantes.
3. Les cibles d'apprentissage comptent : Réaliser l'ouverture infinie nécessite qu'un agent adapte ses cibles d'apprentissage (ex: via le TTS) plutôt que de tenter d'apprendre l'état complet de l'environnement ou d'utiliser une approximation statique.

Limites

Les auteurs notent explicitement deux limites principales :

1. Cadre de bandit : La définition et l'analyse sont actuellement restreintes aux environnements de type bandit (sans état). Étendre ce cadre à des environnements d'apprentissage par renforcement (RL) avec état, non stationnaires ou complets est une étape nécessaire.
2. Dépendance aux hyperparamètres : L'algorithme TTS proposé nécessite une séquence prédéfinie de cibles d'apprentissage (niveaux de troncature). Les auteurs reconnaissent que concevoir des agents capables de déterminer de manière autonome ces cibles sans choix délibérés d'hyperparamètres reste un défi ouvert.

L'article conclut que si l'agent TTS sert de « test de cohérence » pour l'intuition selon laquelle les agents doivent continuellement élargir leurs cibles d'apprentissage, le cadre offre une base rigoureuse pour de futures analyses théoriques et des principes de conception d'agents.