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

Resumen Técnico: Identificabilidad de los Núcleos de Transición en MDPs Descontados

Planteamiento del Problema
Este artículo investiga el problema inverso de recuperar las probabilidades de transición de un Proceso de Decisión de Markov (MDP) finito y descontado, dado únicamente el conjunto de acciones óptimas para cada función de recompensa dentro de una clase específica. Si bien el modelo de transición dicta tanto la política óptima como la dinámica del entorno, dos núcleos de transición distintos pueden recomendar acciones óptimas idénticas. La cuestión central es: ¿bajo qué condiciones dos núcleos $P$ y $Q$ se vuelven indistinguibles basándose únicamente en las acciones óptimas que inducen?

El estudio compara tres clases distintas de recompensas, que prueban la dinámica de diferentes maneras:

1. Recompensas de estado: $r(s)$, que dependen únicamente del estado actual.
2. Recompensas de estado-acción: $r(s, a)$, que dependen del estado actual y la acción.
3. Recompensas dependientes de la transición: $r(s, a, s')$, que dependen del estado, la acción y el estado siguiente resultante.

El artículo define tres nociones de equivalencia: $P \equiv_{tr} Q$ (indistinguibles bajo recompensas de transición), $P \equiv_{sa} Q$ (indistinguibles bajo recompensas de estado-acción) y $P \equiv_{s} Q$ (indistinguibles bajo recompensas de estado).

Metodología
El análisis se basa en las propiedades estructurales de las ecuaciones de optimalidad de Bellman y la relación entre las funciones de valor y los núcleos de transición.

• Recompensas de Estado-Acción: El autor construye una familia específica de recompensas, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$, que hacen que cada acción sea óptima para un vector de valor $v$ dado. Al comparar las ecuaciones de evaluación de la política bajo los núcleos $P$ y $Q$ para estas recompensas, el artículo deriva una condición necesaria y suficiente para la equivalencia. Esto implica identificar una matriz invertible única $L$ que relaciona las funciones de valor de los dos núcleos.
• Recompensas Dependientes de la Transición: La metodología explota la capacidad de aislar filas de transición específicas. Si un estado tiene múltiples acciones, se puede diseñar una recompensa dependiente de la transición para que tenga un valor esperado de cero bajo una fila de transición y no nulo bajo otra, distinguiéndolas efectivamente. Para estados con una sola acción, el análisis depende de si la fila de transición específica afecta la optimalidad de las acciones en otros estados del espacio.
• Recompensas de Estado: El análisis caracteriza la equivalencia examinando las "regiones de política" $R_P(\pi)$, definidas como el conjunto de recompensas de estado para las cuales una política determinista $\pi$ es óptima. Dos núcleos son equivalentes si y solo si sus regiones de política son idénticas para todas las políticas deterministas.

Resultados Clave

1. Equivalencia de Estado-Acción ($P \equiv_{sa} Q$):
   Dos núcleos $P$ y $Q$ producen las mismas acciones óptimas para cada recompensa de estado-acción si y solo si existe una matriz invertible única $L$ (que cumple $L\mathbf{1} = \mathbf{1}$) tal que:
   $$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$$
   Esto implica que la ventaja de cualquier acción relativa a una política se preserva bajo la transformación. Cerca de un núcleo con entradas estrictamente positivas, el conjunto de núcleos indistinguibles forma una variedad suave de dimensión $n(n-1)$, donde $n$ es el número de estados. Esto es un subconjunto estricto del espacio de núcleos ambiente, lo que significa que, si bien el núcleo de transición no está determinado de forma única, la ambigüedad está restringida a una familia específica de menor dimensión. El resultado se mantiene incluso si los datos se restringen a recompensas con una acción única óptima en cada estado.

2. Equivalencia Dependiente de la Transición ($P \equiv_{tr} Q$):
   Las recompensas dependientes de la transición proporcionan significativamente más información.

   • En cualquier estado con al menos dos acciones, la fila de transición se identifica de forma única.
   • En estados con una sola acción, la fila se identifica a menos que las probabilidades de transición específicas nunca influyan en la optimalidad de las acciones en otros estados (una condición que solo se cumple para un conjunto de medida cero de núcleos estrictamente positivos).
   • En consecuencia, si el MDP contiene al menos un estado con una elección genuina (múltiples acciones), casi todos los núcleos estrictamente positivos son identificados de forma única por las recompensas dependientes de la transición.

3. Equivalencia de Recompensa de Estado ($P \equiv_{s} Q$):
   Las recompensas de estado proporcionan la menor cantidad de información. Dos núcleos son equivalentes si y solo si comparten el mismo conjunto de políticas deterministas óptimas para cada recompensa de estado. Esta condición es equivalente a la igualdad de las regiones de política $R_P(\pi) = R_Q(\pi)$ para todo $\pi$. Esta equivalencia es estrictamente más débil que la equivalencia de estado-acción; núcleos distintos pueden ser indistinguibles bajo recompensas de estado mientras que son distinguibles bajo recompensas de estado-acción.

4. Jerarquía de Identificabilidad:
   El artículo establece una jerarquía estricta de equivalencia:
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   Ninguna de las implicaciones es reversible. Permitir que la recompensa dependa de más componentes de la transición (específicamente del siguiente estado) aumenta estrictamente la capacidad de distinguir entre diferentes modelos de transición.

Significado y Pretensiones
El artículo pretende resolver la pregunta de cuánto de la dinámica de transición puede recuperarse únicamente a partir del comportamiento óptimo. Demuestra que:

• Las acciones óptimas son insuficientes para la recuperación total: Incluso con conocimiento de las acciones óptimas para todas las recompensas, el núcleo de transición generalmente no está determinado de forma única cuando las recompensas dependen solo de los estados o de los estados-acciones.
• Existen restricciones estructurales: Para las recompensas de estado-acción, la ambigüedad no es arbitraria; está caracterizada precisamente por una transformación de matriz que preserva las comparaciones de ventajas entre acciones para todas las políticas.
• La estructura de la recompensa dicta la recuperabilidad: La forma de la recompensa es crítica. Las recompensas dependientes de la transición pueden recuperar el núcleo casi por completo, mientras que las recompensas de estado pueden dejar ocultadas diferencias estructurales sustanciales.
• Distinción entre la toma de decisiones y la predicción: Los resultados resaltan que un modelo puede ser suficiente para reproducir decisiones óptimas (reproducción de política) sin ser suficiente para predecir transiciones, simular contrafácticos o transferirse a clases de recompensa no vistas.

El trabajo extiende la literatura previa (por ejemplo, Letcher et al.) al desplazar el enfoque de la recuperación de núcleos a partir de valores Q numéricos hacia la recuperación de núcleos a partir del conjunto discreto de acciones óptimas, mientras expande simultáneamente el alcance de la clase de recompensa considerada. El artículo concluye que, si bien las acciones óptimas revelan una estructura significativa sobre la dinámica, no revelan generalmente la dinámica misma a menos que la función de recompensa sea suficientemente rica (es decir, que dependa del siguiente estado).