Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Resumo Técnico: Processos de Decisão de Markov de Recompensa Média Robustos

Formulação do Problema
Este trabalho investiga a complexidade estatística de aprender uma política $\epsilon$-ótima para Processos de Decisão de Markov de Recompensa Média (AMDPs) com Robustez Distribucional sob um modelo generativo. O agente opera dentro de um ambiente nominal definido por um núcleo de transição $P^0$ e uma função de recompensa $r$. No entanto, a dinâmica do ambiente real é incerta e pode residir dentro de um conjunto de incerteza prescrito $\mathcal{P}$ centrado em $P^0$. Especificamente, o artigo considera conjuntos de incerteza de variação total (TV) $(s, a)$-retangulares com um raio de no máximo $\sigma$.

O objetivo é maximizar a recompensa média robusta, definida como a pior recompensa média de longo prazo sobre todos os núcleos de transição em $\mathcal{P}$:
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
O objetivo de aprendizado é computar uma política $\hat{\pi}$ usando $N$ amostras por par estado-ação tal que $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$, onde $\rho^{\star, \sigma}$ é a recompensa média robusta ótima.

Parâmetros Chave e Suposições Estruturais
A análise baseia-se em dois parâmetros estruturais críticos:

1. Amplitude do Viés Ótimo Nominal ($H_0$): A amplitude da função de viés que satisfaz a equação de Bellman de otimalidade nominal.
2. Amplitude do Viés Ótimo Robusto ($H_\sigma$): A amplitude da função de viés que satisfaz a equação de Bellman de otimalidade robusta.

O artigo estabelece que $H_0$ e $H_\sigma$ são geralmente independentes; um não controla o outro. Uma escala de perturbação crucial é identificada como $\sigma H_0$, que separa o problema de aprendizado em dois regimes distintos:

• Regime de Alta Tolerância ($\epsilon \gtrsim \sigma H_0$): A perturbação causada pela incerteza é pequena em relação à precisão pretendida.
• Regime de Baixa Tolerância ($\epsilon \lesssim \sigma H_0$): A perturbação é significativa, e a otimização nominal isolada é insuficiente para garantir a otimalidade robusta.

Metodologia: Procedimentos de Plug-in Baseados em Redução
A principal contribuição metodológica é um framework de redução que transforma o difícil problema de recompensa média robusta em um problema de MDP descontado robusto (DMDP) mais tratável. Os autores propõem dois algoritmos baseados nesta redução:

1. Procedimento Informado pela Amplitude (Algoritmo 1): Assume que $H_0$ e $H_\sigma$ são conhecidos. Ele seleciona adaptativamente entre uma redução nominal (resolvendo um DMDP padrão com o núcleo empírico) e uma redução robusta (resolvendo um DMDP sobre o conjunto de incerteza). A escolha depende da ordenação de $H_0$ e $H_\sigma$ e do regime de tolerância. O fator de desconto $\gamma$ é calibrado com base no parâmetro de amplitude relevante (ex: $\gamma = 1 - \epsilon/(3H_\sigma)$).
2. Procedimento Agnóstico à Amplitude (Algoritmo 2): Opera sem o conhecimento de $H_0$ ou $H_\sigma$. Ele constrói um conjunto de políticas candidatas a partir de ambas as reduções (nominal e robusta) através de uma grade dicotômica de fatores de desconto. Em seguida, seleciona a melhor política usando um limite inferior de confiança (LCB) na recompensa média robusta, derivado de um "certificado de âncora" computado de um lote de dados separado. Isso permite que o algoritmo escolha adaptativamente a redução e o fator de desconto corretos com base nos dados.

A análise aproveita três refinamentos técnicos fundamentais para alcançar limites estreitos:

• Comparar o problema descontado robusto com uma solução de referência nominal (âncora) para estreitar os termos de variância.
• Controlar funções de valor descontadas através de suas amplitudes ($H_\sigma$) em vez do horizonte efetivo.
• Usar limites de concentração localizados governados por essas amplitudes.

Principais Resultados: Complexidade de Amostra Minimax
O artigo fornece limites superior e inferior correspondentes para a complexidade de amostra minimax $N_{SA}$ (amostras por par estado-ação), até fatores logarítmicos. A complexidade é caracterizada por um resumo de quatro regimes baseado na ordenação de $H_0$ e $H_\sigma$ e no regime de tolerância:

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{se } \epsilon \gtrsim \sigma H_0 \quad (\text{Alta Tolerância}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{se } \epsilon \lesssim \sigma H_0 \quad (\text{Baixa Tolerância}) \end{cases}$$

• Regime de Alta Tolerância: A complexidade é dominada pelo termo de amplitude linear $\min\{H_0, H_\sigma\}$. Se $H_\sigma \leq H_0$, a redução robusta produz um limite mais estreito que a nominal.
• Regime de Baixa Tolerância: Um termo adicional "específico de robustez" $\sigma H_\sigma^2$ aparece, representando o custo de lidar com a incerteza distribucional quando alta precisão é exigida.
• Limite Inferior: Os autores provam um limite inferior minimax que coincide com o limite superior, estabelecendo que o termo $\sigma H_\sigma^2$ é fundamental e não pode ser evitado no regime de baixa tolerância. Este é o primeiro limite inferior caracterizando os limites estatísticos de AMDPs com distribuição robusta.

Significância e Alegações
O artigo afirma fornecer a primeira caracterização minimax-ótima da complexidade de amostra para AMDPs de distribuição robusta. As principais contribuições incluem:

• Resolução da Lacuna de Complexidade de Amostra: Limites superiores robustos anteriores (ex: Roch et al., 2025, 2026) dependiam quadraticamente de parâmetros de amplitude robusta ($H_{Roch}^2$ ou $H_{RHI}^2$) sem distinguir entre alta e baixa tolerância. Este trabalho refina a dependência para $\min\{H_0, H_\sigma\}$ no regime de alta tolerância e identifica o custo preciso de $\sigma H_\sigma^2$ no regime de baixa tolerância.
• Algoritmos Adaptativos: O procedimento agnóstico à amplitude (Algoritmo 2) alcança essas taxas ótimas sem conhecimento prévio dos parâmetros de amplitude, adaptando-se automaticamente ao regime e às magnitudes relativas de $H_0$ e $H_\sigma$.
• Generalidade: Os resultados mantêm-se mesmo se apenas a amplitude robusta $H_\sigma$ for assumida como limitada, resultando em uma complexidade de $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$.

Resultados experimentais em simulações controladas verificam a dependência linear prevista de $\min\{H_0, H_\sigma\}$ e a dependência quadrática de $\sigma H_\sigma^2$ no regime de baixa tolerância, bem como a adaptabilidade do algoritmo agnóstico à amplitude. Os autores observam que trabalhos futuros poderiam explorar estruturas de incerteza acopladas e configurações online (baseadas em regret), mas o presente trabalho foca estritamente no cenário de modelo generativo.