Resumo Técnico: Aprendizado por Reforço de Recompensa Média Robusto e Livre de Modelo com Análise de Complexidade de Amostragem

1. Formulação do Problema

O artigo aborda o desafio do Aprendizado por Reforço (RL) Robusto sob o critério de recompensa média. Embora o RL tenha alcançado sucesso em ambientes controlados, a implantação no mundo real frequentemente sofre com o hiato "Sim-to-Real" devido a desajustes de modelo, perturbações ambientais ou ataques adversários. O RL robusto mitiga isso ao otimizar para o desempenho de pior caso dentro de um conjunto de incerteza de dinâmicas de transição.

O foco específico é em MDPs de Recompensa Média Distribucionalmente Robustos (RAMDPs). Ao contrário dos cenários de recompensa descontada, o critério de recompensa média é essencial para o desempenho de estado estacionário de longo prazo em aplicações como controle de filas e otimização de portfólio. No entanto, o RL de recompensa média robusto é significativamente mais desafiador do que seu equivalente descontado devido a:

1. Operadores não-contrativos: O operador de Bellman robusto é geralmente não-expansivo em vez de contrativo, invalidando garantias de convergência iterativa padrão.
2. Incognitas duais: A equação de Bellman robusta envolve duas variáveis desconhecidas: a função de valor (ou viés) $Q$ e a recompensa média ótima $g^*_P$.
3. Não-linearidade: Estimar a expectativa de pior caso (função de suporte) a partir de amostras nominais introduz viés, particularmente em configurações livres de modelo (model-free).

A literatura existente baseia-se amplamente em garantias assintóticas, abordagens baseadas em modelos que exigem conhecimento prévio de parâmetros do problema (como o span de viés $H$), ou métodos de redução que sofrem de complexidade de amostragem subótima ou exigem suposições estruturais fortes (ex: irredutibilidade com coeficientes de contração específicos).

2. Metodologia: Iteração de Halpern Robusta (RHI)

Os autores propõem a Iteração de Halpern Robusta (RHI), um algoritmo livre de modelo projetado para resolver a equação de Bellman robusta sem exigir conhecimento prévio dos parâmetros do MDP.

2.1. Núcleo Algorítmico

O algoritmo RHI é inspirado na Iteração de Halpern da literatura de otimização, adaptada para lidar com os desafios específicos do RL de recompensa média robusto:

• Formulação de Espaço Quociente: Para abordar a "maldição das variáveis duais" (o $g^*_P$ desconhecido), os autores inserem o problema em um espaço quociente $\mathbb{R}^{SA} / \sim$, onde vetores que diferem apenas por um deslocamento constante são equivalentes. Isso permite que o algoritmo resolva a equação proximal $T_P(Q) - Q = ce$ sem conhecer explicitamente $g^*_P$.
• Atualização de Halpern: Em vez da iteração de valor padrão, a RHI utiliza uma combinação convexa da inicialização e da atualização do operador:
  $$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$$
  onde $\beta_k = k/(k+2)$. Esta abordagem fornece garantias de convergência para operadores não-expansivos sem depender de coeficientes de contração.

2.2. Oráculo de Amostragem Black-Box (R-SAMPLE)

Como o operador robusto $T_P$ é não-linear e envolve uma expectativa de pior caso, os autores introduzem um oráculo de amostragem black-box, o R-SAMPLE. Este oráculo estima a diferença entre as funções de suporte robustas em iterações consecutivas usando apenas amostras do núcleo nominal.

• O oráculo retorna um incremento aleatório $D_k$ tal que sua expectativa aproxima a diferença nos valores do operador de Bellman robusto.
• A complexidade de amostragem do algoritmo é derivada com base nas propriedades deste oráculo (constante de Lipschitz, viés e custo de amostragem).

2.3. Estimador de Monte Carlo de Níveis Múltiplos de Ordem K (K-Order MLMC)

Para implementar concretamente o oráculo R-SAMPLE com baixo viés, os autores propõem um estimador MLMC de ordem K.

• Motivação: Estimadores plug-in padrão e estimadores MLMC comuns para funções de suporte robustas sofrem de um viés de $O(1/N)$, levando a uma complexidade de amostragem de $\tilde{O}(\epsilon^{-3})$.
• Mecanismo: O estimador de ordem K constrói uma combinação linear de estimadores de nível único em diferentes tamanhos de amostra ($N_\ell = 2^\ell N_0$). Ao escolher cuidadosamente os pesos $w^{(K)}_\ell$, o estimador cancela os primeiros $K$ termos da expansão do viés.
• Resultado: Isso reduz o viés para $\tilde{O}(N_0^{-(K+1)})$, permitindo uma complexidade de amostragem global muito mais estreita.

3. Principais Contribuições

1. Um Algoritmo Universal Livre de Modelo: A RHI é o primeiro algoritmo livre de modelo para RL de recompensa média robusto que não requer conhecimento prévio do span ótimo robusto $H$ ou do tempo de mistura, contornando as limitações das abordagens baseadas em redução.
2. Estimador MLMC de Ordem K: Os autores projetam um novo estimador que reduz significativamente o viés em comparação com métodos MLMC anteriores. Isso é crucial para alcançar uma complexidade de amostragem próxima da ótima na presença de funções de suporte robustas não-lineares.
3. Análise de Complexidade de Amostragem Finita: O artigo fornece uma análise rigorosa de amostra finita para a RHI sob um cenário de modelo generativo.
   • Para conjuntos de incerteza de divergência KL e $\chi^2$, a complexidade de amostragem para encontrar uma política $\epsilon$-ótima é $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$.
   • Para conjuntos de norma-$\ell_p$ e contaminação, a complexidade é $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$.
   • Aqui, $S$ e $A$ são o número de estados e ações, e $H$ é o span de viés ótimo robusto.
4. Variante Sem Parâmetros (PF-RHI): Os autores propõem uma variante da RHI que utiliza um truque de duplicação (doubling trick) para determinar o número de iterações dinamicamente, removendo a necessidade de pré-especificar o horizonte baseado no parâmetro desconhecido $H$, mantendo a mesma complexidade de amostragem.

4. Resultados e Garantias Teóricas

• Convergência: É provado que o algoritmo RHI exato converge assintoticamente, com o span do resíduo de Bellman e o gap de subotimalidade desaparecendo conforme as iterações aumentam.
• Complexidade de Amostragem: A complexidade de amostragem derivada para conjuntos KL e $\chi^2$ coincide assintoticamente com os melhores limites conhecidos para abordagens baseadas em modelos (ex: Roch et al., 2025; Chen et al., 2025). O termo $o(1)$ no expoente representa uma penalidade sub-polinomial que desaparece conforme $\epsilon \to 0$, distinguindo-se da complexidade $\epsilon^{-3}$ de métodos que usam MLMC padrão.
• Validação Experimental: Experimentos numéricos no problema Garnet e vários conjuntos de incerteza (contaminação, $\ell_\infty$, $\ell_2$) demonstram que a RHI converge para a recompensa média robusta ótima e que o estimador MLMC de ordem K reduz efetivamente o viés em comparação com métodos padrão.

5. Significância e Alegações

O artigo afirma estabelecer a RHI como o algoritmo estado-da-arte livre de modelo para RL de recompensa média robusto. Sua significância reside em:

• Preenchimento do Hiato: Ele fecha o hiato entre garantias assintóticas e análise de amostra finita em RL de recompensa média robusto.
• Praticidade: Por ser livre de modelo e não exigir conhecimento prévio de $H$, o algoritmo é mais prático para implantação no mundo real, onde tais parâmetros são desconhecidos.
• Otimalidade: A complexidade de amostragem coincide assintoticamente com os limites mais estreitos conhecidos para métodos baseados em modelos, demonstrando que abordagens livres de modelo podem alcançar eficiência semelhante sem o custo de construção do modelo.
• Redução de Viés: O design MLMC de ordem K oferece uma melhoria fundamental sobre estimadores de RL robusto anteriores, resolvendo o problema da alta complexidade de amostragem causada pelo viés não mitigado na estimativa de funções não-lineares.

Os autores observam que sua análise assume um modelo generativo (acesso a um simulador) para isolar a complexidade estatística. Extensões para cenários de exploração-explotação (online) ou baseados em dados (offline) são identificadas como trabalhos futuros. Adicionalmente, o gap sub-polinomial na complexidade de amostragem para conjuntos KL/$\chi^2$ é atribuído ao trade-off inerente entre viés e variância na estimativa de funcionais não-lineares, o que permanece um desafio aberto para eliminar totalmente em configurações livres de modelo.