Resumo Técnico: Limites PAC Minimax para Aprendizado em MDPs Contextuais Exógenos

1. Configuração do Problema

Este artigo investiga a complexidade de amostra para o aprendizado em Processos de Decisão de Markov (MDPs) tabulares descontados com contextos i.i.d. exógenos. O modelo é definido por uma tupla $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$, onde:

• $\mathcal{X}$ é um espaço de estados controlados finito.
• $\mathcal{A}$ é um espaço de ações finito.
• $\mathcal{Z}$ é um espaço de contextos finito.
• $\gamma \in [0, 1)$ é o fator de desconto.
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ é o núcleo de transição.
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ é a função de recompensa.
• $\mu$ é a distribuição desconhecida sobre os contextos.

Em cada passo de tempo $t$, um contexto $Z_t$ é extraído independentemente de $\mu$ e revelado ao agente antes da seleção da ação. O agente escolhe $A_t$, recebe a recompensa $r(X_t, A_t, Z_t)$ e transita para $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$. Crucialmente, o contexto $Z_{t+1}$ é independente das ações do agente e do estado atual, dependendo apenas de $\mu$.

Os objetivos de aprendizado são Avaliação de Política (PE), Estimativa de Melhor Valor (BVE) e Extração de Melhor Política (BPE). A complexidade de amostra é medida por um par $(n_{\text{learn}}, m_{\text{query}})$, representando o número de chamadas de oráculo feitas durante uma fase de aprendizado offline e o número de chamadas feitas durante a fase de decisão (consulta), respectivamente. O artigo considera dois regimes:

1. Dinâmica Conhecida: $P$ e $r$ são conhecidos; apenas $\mu$ é desconhecido.
2. Totalmente Desconhecido: Tanto $\mu$ quanto $P$ são desconhecidos.

2. Metodologia

2.1 Insight Central: Funções de Valor Médias

A principal contribuição metodológica é a redução do problema do espaço aumentado $\mathcal{X} \times \mathcal{Z}$ para o espaço de estados controlados $\mathcal{X}$. Os autores definem a função de valor média $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$.
Como o próximo contexto é extraído independentemente de $\mu$, a equação de Bellman de otimalidade para o valor médio $\bar{V}^\star$ depende apenas do núcleo de transição média sobre $\mu$:
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
Esta formulação permite que o aprendiz estime um vetor em $\mathbb{R}^{|\mathcal{X}|}$ em vez de $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$, desacoplando efetivamente a complexidade do tamanho do espaço de contexto $|\mathcal{Z}|$.

2.2 Estrutura Algorítmica: Redução de Variância por Metade (Halving)

O artigo emprega um esquema de iteração de valor com redução de variância (adaptado de Sidford et al., 2019) para estimar as funções de valor médias. O algoritmo opera em duas fases:

1. Fase Offline (Estimativa de Âncora): O algoritmo computa um limite inferior de alta probabilidade (âncora) para o operador de Bellman aplicado a uma estimativa de valor inicial. Isso requer um grande lote de amostras para controlar a variância da média empírica.
2. Fase Online/Iterativa (Atualizações com Redução de Variância): As iterações subsequentes estimam apenas a diferença entre o backup de Bellman atual e a âncora. Ao reutilizar as mesmas amostras para o termo de diferença, a variância é significativamente reduzida, permitindo tamanhos de amostra menores por iteração.

O algoritmo utiliza uma estratégia de "metade" (halving), chamando repetidamente uma sub-rotina (HALFERR) que reduz pela metade o limite de erro $u$ até que a precisão alvo $\epsilon$ seja alcançada.

2.3 Lidando com Dinâmicas Desconhecidas

No regime totalmente desconhecido, o algoritmo não pode computar o backup de Bellman exatamente mesmo com um contexto amostrado. Em vez disso, para cada contexto amostrado $Z$, o algoritmo extrai uma amostra de transição $X' \sim P(\cdot | x, \pi(x, Z), Z)$ para formar uma estimativa não viesada do backup. Isso introduz um termo de variância adicional relacionado ao núcleo de transição, que é rigorosamente limitado usando uma decomposição de martingala que considera tanto a aleatoriedade do contexto quanto a da transição.

3. Resultados Principais

3.1 Dinâmica Conhecida, Distribuição de Contexto Desconhecida ($P, r$ conhecidos, $\mu$ desconhecido)

Quando o núcleo de transição e as recompensas são conhecidos, o artigo estabelece que a complexidade de amostra é independente do tamanho do espaço de contexto $|\mathcal{Z}|$.

• Complexidade: O algoritmo atinge os objetivos com $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$, onde $\beta = (1-\gamma)^{-1}$.
• Otimalidade: Um limite inferior minimax de $\Omega(\beta^3/\epsilon^2)$ é provado, mostrando que o limite superior é apertado até fatores logarítmicos.
• Implicação: O aprendiz não precisa estimar valores para cada par $(x, z)$; estimar o valor médio $\bar{V}$ é suficiente. A fase de consulta não requer amostras adicionais ($m_{\text{query}}=0$) porque a elevação (lift) de $\bar{V}$ para $V(x, z)$ é um backup de Bellman determinístico usando $P$ e $r$ conhecidos.

3.2 Aplicação ao Lookahead de Passo Único Perfeito

A estrutura é aplicada ao cenário de lookahead de transição de passo único perfeito (onde o agente observa todos os próximos estados possíveis para todas as ações antes de agir).

• Este cenário é mostrado como um caso especial do MDP contextual exógeno onde o espaço de contexto é o conjunto de todos os tensores de transição possíveis.
• O resultado produz uma complexidade de amostra de $\tilde{O}(\beta^3/\epsilon^2)$ amostras de lookahead.
• Em termos de transições tabulares individuais, isso corresponde a $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$, melhorando o limite anterior de Lu et al. (2025) por um fator de $\beta$.

3.3 Regime Totalmente Desconhecido ($P$ e $\mu$ desconhecidos)

Quando tanto a dinâmica quanto a distribuição de contexto são desconhecidas, o artigo foca na Avaliação de Política (PE).

• Complexidade: O algoritmo atinge $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$.
• Trade-off: A fase offline aprende o valor médio $\bar{V}^\pi$ (custando $|\mathcal{X}|$ transições por amostra de contexto). A fase de consulta estima a expectativa de transição de um passo final no $(x, z)$ realizado usando amostras novas.
• Limites Inferiores: O artigo prova limites inferiores correspondentes, demonstrando que:
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ é necessário para a precisão no tempo de decisão.
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ é necessário para o aprendizado offline.
• Significância: Mesmo no regime totalmente desconhecido, a complexidade permanece independente de $|\mathcal{Z}|$. As dinâmicas desconhecidas não forçam a estimativa no espaço aumentado; elas apenas introduzem estocasticidade na "elevação" de decisão de $\bar{V}$ para $V(x, z)$.

4. Significância e Alegações

O artigo afirma fornecer os primeiros limites PAC minimax-ótimos para aprendizado em MDPs contextuais exógenos. Suas principais contribuições são:

1. Desacoplamento do Tamanho do Contexto: Demonstra que o preço estatístico de espaços de contexto grandes é evitável. A complexidade de amostra depende do espaço de estados controlados $|\mathcal{{X}}|$, mas não do espaço de contexto $|\mathcal{Z}|$.
2. Taxas Ótimas: As taxas derivadas ($\tilde{O}(\beta^3/\epsilon^2)$ para dinâmica conhecida e $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$ para totalmente desconhecido) são mostradas como minimax-ótimas até fatores logarítmicos.
3. Estrutura Unificada: A estrutura engloba e melhora resultados existentes para lookahead de passo único perfeito e fornece uma análise rigorosa do trade-off de amostra offline/online.

Os autores observam que, embora o limite inferior seja apertado no ponto puramente online ($n_{\text{learn}}=0$) e no ponto do oráculo reutilizável (seu algoritmo proposto), a consistência do limite para trade-offs intermediários permanece uma questão aberta. Além disso, a extensão desses resultados para a Extração de Melhor Política (BPE) no regime totalmente desconhecido é deixada como trabalho futuro devido à dificuldade de lidar com o viés de seleção ao estimar o máximo sobre as ações a partir de amostras de transição.