Résumé Technique : La Représentation Terminale en Apprentissage par Renforcement

Énoncé du Problème

Dans l'apprentissage par renforcement (RL), l'apprentissage de représentations est crucial pour l'abstraction spatio-temporelle. Deux approches établies sont la Représentation de Successeur (SR) et la Représentation par Défaut (DR). La SR encode les états en fonction des trajectoires de visites futures, capturant la dynamique des transitions indépendamment des récompenses. La DR étend cela en pondérant ces trajectoires par les récompenses, intégrant ainsi la structure d'attribution de crédit.

Cependant, les deux représentations font face à des limitations lorsqu'elles sont appliquées à des tâches en aval telles que la découverte d'options, le façonnage de récompense (reward shaping) et l'apprentissage par transfert :

1. Surcharge Computationnelle : L'utilisation de la DR ou de la SR pour ces tâches nécessite généralement une décomposition en valeurs propres (ou itération de puissance) pour extraire les vecteurs propres. Cela impose un coût de calcul de $O((S^+)^2)$ ou plus par requête et suppose des dynamiques de transition symétriques (réversibles), une condition souvent violée dans les environnements de RL pratiques où les politiques sont directionnelles.
2. Dimensionnalité : La SR et la DR sont définies sur l'espace d'états complet ($S^+ \times S^+$), ce qui peut être vaste et inefficace à stocker et à apprendre.
3. Connaissance Indirecte : Bien que la DR encode des trajectoires pondérées par les récompenses, elle n'isole pas explicitement l'accessibilité et la désirabilité des états terminaux dans un format directement utilisable sans analyse spectrale supplémentaire.

Méthodologie : La Représentation Terminale (TR)

Les auteurs proposent la Représentation Terminale (TR), une formulation structurellement distincte conçue pour encoder les trajectoires pondérées par les récompenses spécifiquement concernant les états terminaux.

Fondement Théorique

La TR est dérivée dans le cadre des Processus de Décision de Markov Linéairement Résolubles (LMDP). Dans un LMDP, la fonction de valeur optimale $v(s)$ peut être transformée en une valeur exponentielle $z(s) = e^{v(s)/\lambda}$, satisfaisant l'équation linéaire :
$$z(s) = e^{R(s)/\lambda} \sum_{s'} P_\mu(s'|s)z(s')$$
où $P_\mu$ est une politique par défaut et $\lambda$ est un paramètre de température.

En décomposant l'espace d'états en états non-terminaux ($S$) et états terminaux ($T$), les auteurs dérivent la matrice TR $M$ comme suit :
$$M = (I_S - D_S)^{-1} D_T$$
où $D_S = R_S P_S$ représente la dynamique non-terminale et $D_T = R_S P_T$ représente les transitions de l'état non-terminal vers l'état terminal. Ici, $R_S$ et $R_T$ sont des matrices diagonales de récompenses exponentiées.

La TR permet une récupération zero-shot des valeurs exponentielles optimales $z$ pour toute configuration de récompenses terminales $y$ (où $y(\tau) = e^{R(\tau)/\lambda}$) via la relation linéaire :
$$z = M y$$

Algorithmes d'Apprentissage

L'article établit la convergence de deux algorithmes d'apprentissage pour $M$ :

1. Programmation Dynamique (Model-Based) : Une règle de mise à jour itérative $M_{k+1} = D_T + D_S M_k$ est prouvée comme convergeant vers la véritable TR.
2. Basé sur l'Échantillonnage (Model-Free) : Une règle de mise à jour de type différence temporelle (TD) est dérivée pour l'apprentissage en ligne :
   $$\hat{M}(s_t) \leftarrow (1 - \alpha_t)\hat{M}(s_t) + \alpha_t e^{r_t/\lambda} \hat{M}^+(s_{t+1})$$
   où $\hat{M}^+$ est une application étendue qui gère les transitions vers les états terminaux. Le Théorème 4.2 prouve que cela converge vers $M$ sous des conditions standards d'approximation stochastique.

Propriétés Théoriques Clés

• Dimensionnalité : La TR est une matrice $S \times T$. Puisque le nombre d'états terminaux $T$ est souvent bien inférieur à l'espace d'états total $S^+$, la TR est significativement plus compacte que la DR $S^+ \times S^+$.
• Utilisabilité Directe (Sans Décomposition en Valeurs Propres) : Les colonnes de la TR correspondent directement aux informations typiquement extraites via les vecteurs propres de la DR. Le Théorème 7.1 démontre que le vecteur propre supérieur de la DR est structurellement composé d'une colonne de la TR (spécifiquement la colonne correspondant au terminal le plus désirable) et d'une série géométrique. Ainsi, la TR capture la même connaissance structurelle sous-jacente sans nécessiter de décomposition en valeurs propres.
• Gestion de l'Asymétrie : Contrairement aux approches par vecteurs propres qui reposent sur la réversibilité des dynamiques de transition (symétrie) pour garantir des valeurs propres réelles, la TR est intrinsèquement asymétrique et bien définie sous des dynamiques arbitraires et non réversibles.
• Compositionnalité : La TR supporte la compositionnalité zero-shot. Si une nouvelle tâche est une combinaison linéaire de tâches de base avec différentes récompenses terminales, la fonction de valeur optimale peut être récupérée en combinant linéairement les colonnes correspondantes de la TR, évitant ainsi de réapprendre les fonctions de valeur de base.
• Équivalence de Récompense : Les auteurs prouvent que les LMDP avec des récompenses dépendantes des transitions ou des actions peuvent être mappés vers des LMDP équivalents avec des récompenses dépendantes des états, garantissant que la théorie de la TR s'applique largement à différentes formulations de récompenses.

Résultats Expérimentaux

Les auteurs évaluent la TR par rapport à la SR et la DR à travers quatre applications en aval dans des environnements de type grid-world (Four Rooms, RiverSwim, SixArms) :

1. Découverte d'Options : Dans la tâche "covering eigenoptions", la TR est utilisée pour générer des options en extrayant directement les colonnes (évitant le calcul de vecteurs propres). Des variantes utilisant la colonne du terminal à plus haute récompense ou toutes les colonnes ont obtenu des performances compétitives avec les méthodes RACE (basée sur la DR) et CEO (basée sur la SR), atteignant souvent des récompenses moyennes plus élevées en poussant les agents directement vers les objectifs désirables.
2. Façonnage de Récompense (Reward Shaping) : L'utilisation de la TR pour construire des récompenses de potentiel basées sur le potentiel ($\hat{r}_t = 1 - M(s_{t+1}, \tau)$) a produit des performances identiques à la DR et supérieures à la SR. Cela confirme la capacité de la TR à capturer l'information structurelle nécessaire pour une navigation efficace sans décomposition en valeurs propres.
3. Exploration Basée sur le Comptage : L'utilisation de la norme de la TR comme bonus d'exploration dans les environnements RiverSwim et SixArms a donné des performances presque identiques à la DR et nettement meilleures que la SR.
4. Apprentissage par Transfert : Lorsque les récompenses terminales changeaient entre les tâches, la TR était utilisée pour transférer la connaissance. Elle a performé similairement aux Caractéristiques par Défaut (DF) (la variante de la DR indépendante de la politique) et a surpassé les Caractéristiques de Successeur (SF) à travers diverses configurations de politiques de base, et ce, sans étape explicite d'apprentissage de caractéristiques.

Signification et Revendications

L'article affirme que la Représentation Terminale offre une alternative viable et efficace sur le plan computationnel à la SR et la DR. Sa principale importance réside dans :

• Efficacité : Elle réduit la dimensionnalité de la représentation et élimine le besoin de décomposition coûteuse en valeurs propres, réduisant la complexité de requête de $O((S^+)^2)$ à $O(1)$ pour l'extraction de colonnes.
• Robustesse : Elle fonctionne correctement sous des dynamiques de transition non symétriques (non réversibles), un scénario courant en RL où les méthodes de vecteurs propres peuvent échouer ou produire des valeurs propres complexes.
• Applicabilité Directe : Elle encode explicitement la connaissance des états terminaux, permettant une utilisation directe dans le façonnage de récompense, la découverte d'options et l'apprentissage par transfert sans analyse spectrale intermédiaire.

Les auteurs maintiennent une position modeste, notant que bien que la TR soit compétitive avec la DR, elle n'est pas fondamentalement supérieure dans tous les aspects sémantiques ; elle fournit plutôt un mécanisme plus compact et plus traitable par le calcul pour accéder à la même connaissance structurelle sous-jacente concernant les états terminaux. Des travaux futurs sont suggérés pour étendre la TR aux environnements de haute dimension via l'approximation de fonction et pour gérer les contextes sans états terminaux explicitement définis.