From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

Résumé technique : Identifiabilité des noyaux de transition dans les MDP actualisés

Énoncé du problème
Cet article étudie le problème inverse consistant à récupérer les probabilités de transition d'un processus de décision markovien (MDP) fini et actualisé, en ne disposant que de l'ensemble des actions optimales pour chaque fonction de récompense appartenant à une classe spécifique. Bien que le modèle de transition dicte à la fois la politique optimale et la dynamique de l'environnement, deux noyaux de transition distincts peuvent recommander des actions optimales identiques. La question centrale est la suivante : sous quelles conditions deux noyaux $P$ et $Q$ deviennent-ils indiscernables sur la seule base des actions optimales qu'ils induisent ?

L'étude compare trois classes distinctes de récompenses, qui testent les dynamiques de différentes manières :

1. Récompenses d'état : $r(s)$, dépendant uniquement de l'état actuel.
2. Récompenses état-action : $r(s, a)$, dépendant de l'état actuel et de l'action.
3. Récompenses dépendantes de la transition : $r(s, a, s')$, dépendant de l'état, de l'action et de l'état suivant résultant.

L'article définit trois notions d'équivalence : $P \equiv_{tr} Q$ (indiscernables sous les récompenses de transition), $P \equiv_{sa} Q$ (indiscernables sous les récompenses état-action), et $P \equiv_{s} Q$ (indiscernables sous les récompenses d'état).

Méthodologie
L'analyse repose sur les propriétés structurelles des équations de Bellman pour l'optimalité et sur la relation entre les fonctions de valeur et les noyaux de transition.

• Récompenses état-action : L'auteur construit une famille spécifique de récompenses, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$, qui rendent chaque action optimale pour un vecteur de valeur $v$ donné. En comparant les équations d'évaluation de politique sous les noyaux $P$ et $Q$ pour ces récompenses, l'article dérive une condition nécessaire et suffisante d'équivalence. Cela implique l'identification d'une matrice inversible unique $L$ qui relie les fonctions de valeur des deux noyaux.
• Récompenses dépendantes de la transition : La méthodologie exploite la capacité d'isoler des lignes de transition spécifiques. Si un état possède plusieurs actions, une récompense dépendante de la transition peut être conçue pour avoir une espérance nulle sous une ligne de transition et non nulle sous une autre, distinguant ainsi les deux. Pour les états possédant une seule action, l'analyse repose sur la question de savoir si la ligne de transition spécifique affecte l'optimalité des actions ailleurs dans l'espace d'états.
• Récompenses d'état : L'analyse caractérise l'équivalence en examinant les « régions de politique » $R_P(\pi)$, définies comme l'ensemble des récompenses d'état pour lesquelles une politique déterministe $\pi$ est optimale. Deux noyaux sont équivalents si et seulement si leurs régions de politique sont identiques pour toutes les politiques déterministes.

Résultats clés

1. Équivalence état-action ($P \equiv_{sa} Q$) :
   Deux noyaux $P$ et $Q$ produisent les mêmes actions optimales pour toute récompense état-action si et seulement s'il existe une matrice inversible unique $L$ (satisfaisant $L\mathbf{1} = \mathbf{1}$) telle que :
   $$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$$
   Cela implique que l'avantage de toute action par rapport à une politique est préservé sous la transformation. Près d'un noyau ayant des entrées strictement positives, l'ensemble des noyaux indiscernables forme une variété lisse de dimension $n(n-1)$, où $n$ est le nombre d'états. Il s'agit d'un sous-ensemble strict de l'espace des noyaux ambiant, ce qui signifie que, bien que le noyau de transition ne soit pas déterminé de manière unique, l'ambiguïté est contrainte à une famille spécifique de dimension inférieure. Le résultat est valable même si les données sont restreintes aux récompenses présentant une action unique optimale à chaque état.

2. Équivalence dépendante de la transition ($P \equiv_{tr} Q$) :
   Les récompenses dépendantes de la transition fournissent nettement plus d'informations.

   • À n'importe quel état possédant au moins deux actions, la ligne de transition est identifiée de manière unique.
   • Aux états possédant une seule action, la ligne est identifiée, à moins que la ligne de transition spécifique n'influence jamais l'optimalité des actions dans d'autres états (une condition qui ne tient que pour un ensemble de mesure nulle de noyaux strictement positifs).
   • Par conséquent, si le MDP contient au moins un état avec un choix réel (plusieurs actions), presque tout noyau strictement positif est identifié de manière unique par les récompenses dépendantes de la transition.

3. Équivalence de récompense d'état ($P \equiv_{s} Q$) :
   Les récompenses d'état fournissent le moins d'informations. Deux noyaux sont équivalents si et seulement s'ils partagent le même ensemble de politiques déterministes optimales pour toute récompense d'état. Cette condition est équivalente à l'égalité des régions de politique $R_P(\pi) = R_Q(\pi)$ pour toute $\pi$. Cette équivalence est strictement plus faible que l'équivalence état-action ; des noyaux distincts peuvent être indiscernables sous les récompenses d'état tout en étant discernables sous les récompenses état-action.

4. Hiérarchie de l'identifiabilité :
   L'article établit une hiérarchie stricte d'équivalence :
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   Aucune des implications n'est réversible. Le fait de permettre à la récompense de dépendre de plus de composants de la transition (spécifiquement l'état suivant) augmente strictement la capacité de distinguer entre différents modèles de transition.

Signification et revendications
L'article prétend résoudre la question de savoir quelle part de la dynamique de transition peut être récupérée à partir du comportement optimal seul. Il démontre que :

• Les actions optimales sont insuffisantes pour une récupération complète : Même avec la connaissance des actions optimales pour toutes les récompenses, le noyau de transition n'est généralement pas déterminé de manière unique lorsque les récompenses dépendent uniquement des états ou des états-actions.
• Des contraintes structurelles existent : Pour les récompenses état-action, l'ambiguïté n'est pas arbitraire ; elle est précisément caractérisée par une transformation matricielle qui préserve les comparaisons d'actions (avantages) à travers toutes les politiques.
• La structure de la récompense dicte la récupérabilité : La forme de la récompense est critique. Les récompenses dépendantes de la transition peuvent récupérer le noyau presque entièrement, tandis que les récompenses d'état peuvent laisser subsister des différences structurelles importantes cachées.
• Distinction entre prise de décision et prédiction : Les résultats soulignent qu'un modèle peut être suffisant pour reproduire des décisions optimales (reproduction de politique) sans être suffisant pour prédire les transitions, simuler des contre-factuels ou transférer vers des classes de récompenses non vues.

Le travail étend la littérature existante (ex. Letcher et al.) en déplaçant l'accent de la récupération des noyaux à partir des valeurs Q numériques vers la récupération à partir de l'ensemble discret des actions optimales, tout en élargissant la portée de la classe de récompenses considérée. L'article conclut que, bien que les actions optimales révèlent une structure significative de la dynamique, elles ne révèlent généralement pas la dynamique elle-même, à moins que la fonction de récompense ne soit suffisamment riche (c'est-à-dire qu'elle dépende de l'état suivant).