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

Resumo Técnico: Identificabilidade de Núcleos de Transição em MDPs Descontados

Enunciado do Problema
Este artigo investiga o problema inverso de recuperar as probabilidades de transição de um Processo de Decisão de Markov (MDP) finito e descontado, dado apenas o conjunto de ações ótimas para toda função de recompensa dentro de uma classe específica. Embora o modelo de transição dite tanto a política ótima quanto a dinâmica do ambiente, dois núcleos de transição distintos podem recomendar ações ótimas idênticas. A questão central é: sob quais condições dois núcleos $P$ e $Q$ tornam-se indistinguíveis baseando-se apenas nas ações ótimas que eles induzem?

O estudo compara três classes distintas de recompensas, que testam a dinâmica de maneiras diferentes:

1. Recompensas de estado: $r(s)$, dependendo apenas do estado atual.
2. Recompensas de estado-ação: $r(s, a)$, dependendo do estado atual e da ação.
3. Recompensas dependentes de transição: $r(s, a, s')$, dependendo do estado, da ação e do próximo estado resultante.

O artigo define três noções de equivalência: $P \equiv_{tr} Q$ (indistinguíveis sob recompensas de transição), $P \equiv_{sa} Q$ (indistinguíveis sob recompensas de estado-ação) e $P \equiv_{s} Q$ (indistinguíveis sob recompensas de estado).

Metodologia
A análise baseia-se nas propriedades estruturais das equações de otimalidade de Bellman e na relação entre funções de valor e núcleos de transição.

• Recompensas de Estado-Ação: O autor constrói uma família específica de recompensas, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$, que torna cada ação ótima para um dado vetor de valor $v$. Ao comparar as equações de avaliação de política sob os núcleos $P$ e $Q$ para essas recompensas, o artigo deriva uma condição necessária e suficiente para a equivalência. Isso envolve a identificação de uma matriz invertível única $L$ que relaciona as funções de valor dos dois núcleos.
• Recompensas Dependentes de Transição: A metodologia explora a capacidade de isolar linhas de transição específicas. Se um estado possui múltiplas ações, uma recompensa dependente de transição pode ser projetada para ter valor esperado zero sob uma linha de transição e não nulo sob outra, efetivamente distinguindo-as. Para estados com uma única ação, a análise depende de se a linha de transição específica afeta a otimalidade das ações em outros estados do espaço de estados.
• Recompensas de Estado: A análise caracteriza a equivalência examinando as "regiões de política" $R_P(\pi)$, definidas como o conjunto de recompensas de estado para as quais uma política determinística $\pi$ é ótima. Dois núcleos são equivalentes se, e somente se, suas regiões de política são idênticas para todas as políticas determinísticas.

Principais Resultados

1. Equivalência de Estado-Ação ($P \equiv_{sa} Q$):
   Dois núcleos $P$ e $Q$ produzem as mesmas ações ótimas para toda recompensa de estado-ação se, e somente se, existe uma matriz invertível única $L$ (satisfazendo $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}$$
   Isso implica que a vantagem de qualquer ação relativa a uma política é preservada sob a transformação. Próximo a um núcleo com entradas estritamente positivas, o conjunto de núcleos indistinguíveis forma uma variedade suave de dimensão $n(n-1)$, onde $n$ é o número de estados. Isso é um subconjunto estrito do espaço de núcleos ambiente, o que significa que, embora o núcleo de transição não seja unicamente determinado, a ambiguidade é restrita a uma família específica de dimensão inferior. O resultado mantém-se mesmo se os dados forem restritos a recompensas com uma ação única e ótima em cada estado.

2. Equivalência de Dependência de Transição ($P \equiv_{tr} Q$):
   Recompensas dependentes de transição fornecem significativamente mais informação.

   • Em qualquer estado com pelo menos duas ações, a linha de transição é unicamente identificada.
   • Em estados com uma única ação, a linha é identificada, a menos que a linha de transição específica nunca influencie a otimalidade das ações em outros estados (uma condição que ocorre apenas em um conjunto de medida zero de núcleos estritamente positivos).
   • Consequentemente, se o MDP contiver pelo menos um estado com uma escolha genuína (múltiplas ações), quase todo núcleo estritamente positivo é unicamente identificado por recompensas dependentes de transição.

3. Equivalência de Recompensa de Estado ($P \equiv_{s} Q$):
   Recompensas de estado fornecem a menor quantidade de informação. Dois núcleos são equivalentes se, e somente se, compartilham o mesmo conjunto de políticas determinísticas ótimas para toda recompensa de estado. Esta condição é equivalente à igualdade das regiões de política $R_P(\pi) = R_Q(\pi)$ para todo $\pi$. Esta equivalência é estritamente mais fraca que a equivalência de estado-ação; núcleos distintos podem ser indistinguíveis sob recompensas de estado enquanto são distinguíveis sob recompensas de estado-ação.

4. Hierarquia de Identificabilidade:
   O artigo estabelece uma hierarquia estrita de equivalência:
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   Nenhuma das implicações é reversível. Permitir que a recompensa dependa de mais componentes da transição (especificamente do próximo estado) aumenta estritamente a capacidade de distinguir entre diferentes modelos de transição.

Significância e Alegações
O artigo afirma resolver a questão de quanto da dinâmica de transição pode ser recuperada apenas a partir do comportamento ótimo. Ele demonstra que:

• Ações ótimas são insuficientes para a recuperação total: Mesmo com o conhecimento das ações ótimas para todas as recompensas, o núcleo de transição geralmente não é unicamente determinado quando as recompensas dependem apenas de estados ou estado-ações.
• Existem restrições estruturais: Para recompensas de estado-ação, a ambiguidade não é arbitrária; ela é precisamente caracterizada por uma transformação de matriz que preserva as comparações de ações (vantagens) através de todas as políticas.
• A estrutura da recompensa dita a recuperabilidade: A forma da recompensa é crítica. Recompensas dependentes de transição podem recuperar o núcleo quase inteiramente, enquanto recompensas de estado podem deixar diferenças estruturais substanciais ocultas.
• Distinção entre tomada de decisão e predição: Os resultados destacam que um modelo pode ser suficiente para reproduzir decisões ótimas (reprodução de política) sem ser suficiente para prever transições, simular contrafatuais ou transferir para classes de recompensas não vistas.

O trabalho expande a literatura anterior (ex: Letcher et al.) ao mudar o foco da recuperação de núcleos a partir de valores numéricos de Q para a recuperação a partir do conjunto discreto de ações ótimas, enquanto simultaneamente amplia o escopo da classe de recompensa considerada. O artigo conclui que, embora as ações ótimas revelem uma estrutura significativa sobre a dinâmica, elas não revelam genericamente a dinâmica em si, a menos que a função de recompensa seja suficientemente rica (ou seja, dependa do próximo estado).