Optimal strategies in Markov decision processes with finitely additive evaluations

Este artigo demonstra que, em processos de decisão de Markov com horizonte infinito e avaliações finitamente aditivas, não é garantida a existência de uma estratégia ótima (nem pura nem aleatória) quando a medida de agregação não satisfaz o princípio do valor temporal do dinheiro, apresentando um contraexemplo que refuta essa possibilidade.

O essencial

O Dilema do Jogador Infinito: Por que às vezes não existe a "Estratégia Perfeita"

Imagine que você é o gerente de uma fábrica que nunca fecha. Todos os dias, você precisa tomar uma decisão: Trabalhar duro (ganha muito hoje, mas cansa amanhã) ou Descansar (ganha pouco hoje, mas está fresco amanhã). O jogo dura para sempre.

A pergunta clássica da economia e da matemática é: "Qual é a melhor estratégia para eu ganhar o máximo de dinheiro possível ao longo de toda a minha vida?"

Geralmente, a resposta é "sim, existe uma estratégia perfeita". Mas este artigo de 2026 (escrito por Flesch, Predtetchinski, Sudderth e Venel) descobriu algo surpreendente: em certas condições muito específicas, a resposta é "não". Às vezes, não existe uma estratégia perfeita, nem mesmo uma aleatória.

Vamos entender como isso funciona usando três conceitos-chave:

1. O Jogo Infinito (MDP)

Pense no "Processo de Decisão de Markov" (MDP) como um tabuleiro de jogo infinito.

• Você está em um estado (ex: na fábrica).
• Você escolhe uma ação (Trabalhar ou Descansar).
• Você ganha uma recompensa (dinheiro).
• O jogo avança para o próximo dia.

O objetivo é somar todas as recompensas futuras. Mas como somar algo que nunca acaba?

2. A "Lente" de Avaliação (A Carga Difusa)

Aqui está o truque. Para calcular o total, você precisa de uma "lente" ou um "filtro" para olhar para o futuro.

• Visão Padrão (Desconto): A maioria das pessoas diz: "Um real hoje vale mais que um real daqui a 100 anos". Isso é o "valor do dinheiro no tempo". Se você usa essa lógica, sempre existe uma estratégia perfeita.
• Visão Média (Frequência): Outra lente diz: "Não importa quando ganho, importa a média". Se eu ganho 1 real em dias ímpares e 0 em pares, minha média é 0,5.
• A Lente do Artigo (Carga Difusa): Os autores criaram uma lente matemática muito estranha e complexa. Ela é como um "olho de águia" que consegue ver padrões infinitos, mas não se importa com dias específicos. Ela é uma "média" que não dá peso a nenhum dia individual, mas olha para o infinito como um todo.

3. O Cenário "Par ou Ímpar" (O Exemplo do Artigo)

Os autores criaram um jogo de teste chamado "Par ou Ímpar":

• Dia 1 (Ímpar): Você escolhe entre ganhar 1 agora e 0 amanhã, OU ganhar 0 agora e 1 amanhã.
• Dia 2 (Par): O jogo volta ao início.
• Dia 3 (Ímpar): Você escolhe de novo. E assim por diante, para sempre.

A lógica parece simples: se você sempre escolhe "ganhar 1 agora", você ganha 1 em todos os dias ímpares. Se escolhe "ganhar 1 amanhã", você ganha 1 em todos os dias pares.

O Problema da Lente Estranha:
Os autores construíram uma "lente" (chamada de aggregation charge) que é uma mistura de duas visões opostas:

1. Visão A: Só se importa com os dias Ímpares.
2. Visão B: Só se importa com os dias Pares (mas de uma forma matemática muito sutil e complexa).

Para ganhar o máximo com a Visão A, você precisa escolher "ganhar 1 agora" o tempo todo.
Para ganhar o máximo com a Visão B, você precisa escolher "ganhar 1 amanhã" com certa frequência.

O Conflito:

• Se você foca na Visão A, você perde na Visão B.
• Se você foca na Visão B, você perde na Visão A.
• Se você tenta fazer um meio-termo (aleatoriamente), você não atinge o máximo de nenhuma das duas.

A descoberta matemática é que, com essa lente específica, é impossível atingir o valor máximo teórico (1). Você pode chegar muito perto (0,99999), mas nunca chegará a 1.

A Analogia do "Gato de Schrödinger" da Decisão

Imagine que você está tentando adivinhar se uma moeda vai dar "Cara" ou "Coroa" para sempre.

• Se você sempre aposta em Cara, você ganha em um universo paralelo.
• Se você sempre aposta em Coroa, você ganha em outro.
• Mas a "lente" do artigo é como um juiz que diz: "Eu vou te pagar o máximo possível, mas a minha regra de pagamento muda dependendo de como você joga, de uma forma que você nunca consegue acertar o padrão perfeito".

É como tentar encher um balde que tem um buraco no fundo que se move exatamente na velocidade em que você joga a água. Você pode chegar perto de encher, mas o balde nunca fica 100% cheio.

Por que isso importa?

1. Quebra de Intuição: A gente acha que, se o jogo é justo e as regras são claras, deve haver uma "melhor jogada". Este artigo diz: "Não necessariamente".
2. Limites da Matemática: Mostra que, quando lidamos com o infinito e com medidas matemáticas muito abstratas (que não contam dia por dia, mas olham o todo), a lógica de "otimização" pode falhar.
3. Aplicação Real: Embora pareça um quebra-cabeça teórico, isso afeta como modelamos sistemas complexos de longo prazo, como mudanças climáticas, economia global ou inteligência artificial que precisa planejar por séculos. Se a forma como "avaliamos" o futuro for muito complexa, pode não existir uma solução perfeita para o nosso problema.

Resumo Final

O artigo prova que, em um mundo infinito onde avaliamos o futuro com uma "lente" matemática muito peculiar e complexa, não existe uma estratégia vencedora perfeita. Você pode ficar cada vez melhor, mas nunca chegará ao topo. É a prova matemática de que, às vezes, o "melhor possível" é apenas um sonho inalcançável.

Resumo técnico

Resumo Técnico: Estratégias Ótimas em Processos de Decisão de Markov com Avaliações Aditivas Finitamente

1. Problema e Contexto

O artigo investiga Processos de Decisão de Markov (MDPs) com horizonte infinito, onde o conjunto de etapas é o conjunto dos números naturais $\mathbb{N} = \{1, 2, \dots\}$. A característica distintiva deste trabalho reside na forma como o tomador de decisão avalia as estratégias.

Diferente dos modelos clássicos que utilizam soma descontada ou média de longo prazo (que correspondem a medidas contavelmente aditivas ou frequências limites), este estudo considera que o tomador de decisão agrega o fluxo infinito de recompensas esperadas utilizando uma carga difusa (ou medida de probabilidade aditiva finitamente aditiva) definida sobre o conjunto de etapas.

• Carga Difusa ($\mu$): Uma medida aditiva finitamente aditiva $\mu: 2^{\mathbb{N}} \to [0, 1]$ tal que $\mu(\{n\}) = 0$ para todo $n \in \mathbb{N}$. Isso significa que nenhuma etapa individual tem peso positivo; a avaliação depende da estrutura global do fluxo de recompensas.
• Objetivo: Determinar se, para qualquer MDP com espaços de estados e ações finitos e qualquer carga de agregação $\mu$, existe sempre uma estratégia ótima (que maximiza o payoff esperado $\mu$-agregado), seja ela pura ou randomizada.

2. Metodologia e Ferramentas Teóricas

Os autores utilizam uma abordagem baseada em teoria da medida e topologia funcional:

1. Integração em Relação a Cargas: O payoff de uma estratégia $\sigma$ é definido como a integral das recompensas esperadas em relação à carga $\mu$:
   $$u_\mu(\sigma) = \int_{t \in \mathbb{N}} \mathbb{E}_\sigma[r_t] \, \mu(dt)$$
   Como as recompensas são limitadas, essa integral é bem definida para qualquer carga aditiva finitamente aditiva.

2. Princípio do Valor do Dinheiro no Tempo (TVM): O artigo revisa resultados anteriores de Neyman [2023], que mostram que, se a carga $\mu$ satisfaz o princípio do TVM (uma condição que implica que o tomador de decisão valoriza mais as recompensas imediatas ou respeita certas propriedades de dominância de soma parcial), então uma estratégia estacionária pura ótima sempre existe.

3. Topologia de Convergência Pontual: Para construir o contraexemplo, os autores utilizam a topologia de convergência pontual no espaço de todas as cargas $\Delta_f$. Eles exploram a compacidade deste espaço (Teorema de Tychonoff) para garantir a existência de pontos de acumulação de sequências de cargas.

4. Construção de Cargas Específicas: A metodologia central envolve a construção deliberada de uma carga de agregação "delicada" que combina componentes com comportamentos opostos, criando um conflito intratável para qualquer estratégia fixa.

3. Contribuições Principais e Resultados

A contribuição central do artigo é uma resposta negativa a uma questão aberta levantada por Neyman [2023]: A existência de uma estratégia ótima não é garantida em todos os MDPs com cargas difusas arbitrárias.

Teorema Principal (Teorema 3)

Os autores provam que existe um MDP com espaços de estados e ações finitos e uma carga difusa $\mu$ tal que não existe nenhuma estratégia ótima (nem pura, nem randomizada).

O Contraexemplo: "Even-or-Odd MDP"

O exemplo construído possui as seguintes características:

• Estrutura: 3 estados. No estado 1, o agente escolhe entre Ações T (Top) e B (Bottom).
  • Ação T: Recompensa 1 no estado atual, transição para estado 2 (recompensa 0).
  • Ação B: Recompensa 0 no estado atual, transição para estado 3 (recompensa 1).
  • Estados 2 e 3 retornam deterministicamente ao estado 1.
• Dinâmica: O agente enfrenta um dilema a cada par de etapas (ímpar-par). Escolher T dá 1 agora e 0 depois; escolher B dá 0 agora e 1 depois.
• A Carga de Agregação ($\mu$): A carga é definida como $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
  • $\mu_0$: Concentrada nos estágios ímpares (baseada em uma carga de frequência).
  • $\mu^*$: Um ponto de acumulação de uma sequência de cargas $\mu_n$ que, embora definidas sobre conjuntos de múltiplos de potências de 2, convergem para uma carga que dá peso 1 a conjuntos específicos de estágios pares.

Análise do Resultado

1. Valor do Jogo ($v_\mu$): O valor supremo do payoff é 1. Isso é alcançável arbitrariamente próximo por estratégias que alternam ações de forma inteligente dependendo do "bloco" de tempo considerado (estratégias $\sigma_n$ que jogam B em certos conjuntos esparsos e T no resto).
2. Não Existência de Ótimo:
   • Para obter payoff 1, a estratégia deve jogar T com frequência quase 1 para satisfazer $\mu_0$, mas também deve jogar B com frequência positiva (em conjuntos específicos) para satisfazer $\mu^*$.
   • Qualquer estratégia fixa (pura ou randomizada) falha em maximizar simultaneamente os dois componentes da carga. Se a estratégia favorece T para agradar $\mu_0$, ela perde valor em $\mu^*$, e vice-versa.
   • O artigo demonstra formalmente que para qualquer estratégia $\sigma$, $u_\mu(\sigma) < 1$. Portanto, o supremo não é atingido.

Outros Resultados Relevantes

• Exemplo 4 (Não existência de estratégias estacionárias ótimas): Mesmo quando uma estratégia ótima pura existe (mas não é estacionária), pode não haver nenhuma estratégia estacionária que seja ótima. Isso contrasta com o caso do TVM, onde estratégias estacionárias puras são suficientes.
• Exemplo 5 (Cargas não-difusas): O artigo discute que se a carga não for difusa (ou seja, tiver uma parte contavelmente aditiva positiva), a existência de estratégia ótima pode falhar em cenários que misturam soma descontada e média de longo prazo, um fenômeno conhecido na literatura, mas aqui formalizado no contexto de cargas gerais.

4. Significado e Implicações

1. Limites da Teoria de Decisão Dinâmica: O trabalho estabelece um limite fundamental para a teoria de MDPs. Mostra que a garantia de existência de estratégias ótimas, que é robusta em modelos descontados ou de média de longo prazo, se quebra quando se permite avaliações via cargas aditivas finitamente aditivas arbitrárias.
2. Importância da Estrutura da Carga: A existência de uma estratégia ótima depende criticamente das propriedades da carga de agregação. O princípio do TVM (satisfeito por Neyman) é uma condição suficiente, mas não necessária para a existência de estratégias puras; contudo, sem condições adicionais, a existência de qualquer estratégia ótima não é garantida.
3. Complexidade de Estratégias: O resultado sugere que, em ambientes com avaliações "patológicas" (como a carga construída), o tomador de decisão pode não ter uma melhor resposta estável, indicando que o problema de otimização pode não ter solução no espaço de estratégias padrão.
4. Aplicação em Economia e Teoria dos Jogos: A análise de cargas finitamente aditivas é relevante para modelar agentes com preferências de longo prazo que não são capturadas por descontos exponenciais, ou para analisar equilíbrios em jogos com horizonte infinito onde a convergência de médias é problemática.

Em resumo, o artigo demonstra que a generalização de MDPs para avaliações por cargas difusas introduz uma complexidade matemática onde a otimalidade pode ser inatingível, desafiando a intuição de que sempre é possível encontrar a melhor política de decisão em sistemas dinâmicos finitos.