Resumo Técnico: Q-Learning sob Critério de Custo Médio para MDPs Contínuos

1. Formulação do Problema

Este artigo aborda o desafio de resolver Processos de Decisão de Markov (MDPs) com espaços de estados e ações contínuos sob o critério de custo médio de horizonte infinito. O modelo é definido por uma tupla $(X, U, \mathcal{T}, c)$, onde $X$ e $U$ são espaços Borel padrão (espaços métricos completos e separáveis), $\mathcal{T}$ é o núcleo de transição e $c$ é a função de custo. O objetivo é encontrar uma política $\pi$ que minimize o custo médio de longo prazo:
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

Os autores destacam que, embora problemas de horizonte finito e de custo descontado para espaços contínuos sejam bem estudados usando propriedades de contração de operadores de Bellman, os problemas de custo médio apresentam dificuldades únicas. Especificamente, a ausência de um fator de desconto remove a contração imediata do mapeamento, exigindo suposições alternativas de estabilidade e ergodicidade. Além disso, a literatura existente sobre aprendizado por reforço (RL) de custo médio foca majoritariamente em espaços finitos ou impõe suposições estruturais restritivas (ex: dinâmica linear, políticas Lipschitz) que limitam a aplicabilidade a espaços contínuos gerais.

2. Metodologia

O artigo emprega uma abordagem de duas frentes: aproximação finita via quantização e algoritmos de aprendizado por reforço projetados para essas aproximações.

2.1 Discretização e Aproximação

A metodologia central envolve a construção de um MDP aproximado de estados e ações finitos através da quantização dos espaços contínuos.

• Quantização de Estado: O espaço de estados $X$ é particionado em compartimentos disjuntos $\{B_i\}_{i=1}^M$ com estados representativos $y_i$. Uma função de mapeamento $q: X \to Y$ (onde $Y$ é o conjunto finito de representantes) é definida.
• Quantização de Ação: O espaço de ações $U$ é aproximado por um conjunto finito $\Lambda$.
• Construção do Modelo Aproximado: O modelo aproximado $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ é definido usando uma medida de peso $\mu$ (frequentemente a medida invariante do processo de estado). O custo e os núcleos de transição aproximados são médias das funções originais sobre os compartimentos de quantização:
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• Condições de Continuidade Relaxadas: Uma mudança metodológica significativa é o relaxamento da condição de continuidade de Variação Total (TV), que é o padrão na literatura de aproximação anterior (ex: Saldi et al., 2018). Os autores estabelecem resultados de aproximação sob:
  1. Continuidade Fraca (Feller): Suficiente para a convergência assintótica de erros conforme os tamanhos da grade diminuem.
  2. Continuidade de Wasserstein: Suficiente para estabelecer taxas de convergência explícitas (limites de erro) conforme os tamanhos da grade diminuem.

2.2 Algoritmos de Aprendizado por Reforço

O artigo propõe algoritmos de Q-Learning Quantizado para aprender a política ótima para o modelo aproximado diretamente a partir dos dados.

• Algoritmo Síncrono (Algoritmo 1): Atualiza os valores de Q para todos os pares estado-ação na grade finita simultaneamente. Ele depende da amostragem de estados de cada compartimento de acordo com uma medida pré-determinada.
• Algoritmo Assíncrono (Algoritmo 2): Atualiza os valores de Q baseando-se em uma única trajetória do processo contínuo original. Isso é mais prático, mas introduz um termo de ruído não-markoviano porque o processo quantizado $q(X_t)$ não é uma cadeia de Markov (é um MDP Parcialmente Observável do ponto de vista do estado quantizado).
• Mecanismo de Convergência: Para lidar com o critério de custo médio e a falta de limitação nos iterados de Q (ao contrário dos casos descontados), os autores utilizam:
  • Semi-normas de Span para atualizações síncronas.
  • Suposições de Ergodicidade: A política de exploração deve induzir uma medida invariante única com suporte total sobre os compartimentos quantizados.
  • Atualizações Deslocadas: O algoritmo assíncrono subtrai um valor de referência (baseado em um compartimento específico) para estabilizar a iteração, tratando o processo quantizado como um POMDP.

3. Principais Contribuições

O artigo apresenta três contribuições primárias, avançando o estado da arte no controle de custo médio para espaços contínuos:

1. Teoria de Aproximação com Condições Mais Fracas:

   • Os autores fornecem limites de erro para aproximações finitas sob continuidade fraca e continuidade de Wasserstein, relaxando a estrita continuidade de Variação Total exigida por trabalhos anteriores (ex: Saldi et al., 2018).
   • Eles estabelecem que, sob continuidade de Wasserstein (com uma constante de contração $K_T < 1$), o erro no custo médio ótimo decai a uma taxa proporcional ao erro de quantização (especificamente $L_X^\delta$).
   • Sob apenas continuidade fraca, eles provam a convergência assintótica do custo da política aproximada para o custo ótimo conforme a discretização se torna mais fina.

2. Convergência de Q-Learning Quantizado:

   • O artigo estabelece a convergência quase certa de algoritmos de Q-learning síncronos e assíncronos para espaços contínuos.
   • Crucialmente, prova-se que esses algoritmos convergem para os valores de Q ótimos do modelo aproximado finito construído, e não apenas para o modelo contínuo original. Essa distinção é vital porque o processo quantizado não é estritamente Markoviano.
   • A análise generaliza resultados anteriores (ex: Kara e Yüksel, 2023) de custos descontados para o mais desafiador critério de custo médio, exigindo nova análise técnica para lidar com iterados de Q não limitados.

3. Garantias de Quase-Otimalidade:

   • Ao combinar os limites de erro de aproximação com a convergência dos algoritmos de aprendizado, o artigo demonstra que as políticas aprendidas via Q-learning quantizado são quase-ótimas para o MDP contínuo original.
   • A perda de desempenho é explicitamente limitada em termos da resolução da quantização e das constantes de Lipschitz das funções de custo e núcleos de transição.

4. Principais Resultados e Teoremas

• Teorema 1 & 2 (Limites de Aproximação): Estabelecem limites superiores para a diferença entre o custo médio ótimo do modelo original ($\rho$) e o modelo aproximado ($\hat{\rho}$).
  • Sob continuidade de Wasserstein: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, onde $L_X$ é o erro de quantização.
  • Sob continuidade fraca: $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• Teorema 5 & 6 (Convergência do Algoritmo): Provam que as iterações de Q-learning síncronas e assíncronas convergem para os valores de Q ótimos do modelo aproximado finito. A convergência assíncrona depende da ergodicidade do processo de estado sob a política de exploração.
• Corolário 1: Combina os resultados de aproximação e aprendizado para mostrar que a política aprendida $\hat{\pi}$ satisfaz $\rho(\hat{\pi}) - \rho \leq \epsilon$, onde $\epsilon$ desaparece conforme o tamanho da grade de discretização se aproxima de zero.

5. Significância e Alegações

Os autores posicionam este trabalho como uma solução para problemas abertos na literatura de aprendizado por reforço para MDPs de custo médio com espaços contínuos.

• Relaxamento de Suposições: O artigo alega um avanço teórico significativo ao afastar-se da continuidade de Variação Total, que é frequentemente muito restritiva para modelos práticos, movendo-se para a continuidade Fraca e de Wasserstein. Isso amplia a classe de sistemas (ex: aqueles com ruído aditivo ou dinâmicas específicas) para os quais garantias teóricas podem ser fornecidas.
• Ponte entre Teoria e Prática: Ao provar que o Q-learning converge para a solução de uma aproximação finita bem definida, o artigo fornece uma justificativa rigorosa para o uso de aprendizado por reforço baseado em discretização em configurações de custo médio contínuo. Esclarece que a "quase-otimalidade" é uma consequência direta da qualidade da aproximação, não um artefato do algoritmo de aprendizado.
• Tratamento da Quantização Não-Markoviana: O artigo aborda explicitamente a dificuldade técnica de que o processo de estado quantizado é um POMDP, não um MDP, e fornece uma prova de convergência para o aprendizado assíncrono neste cenário sob o critério de custo médio, uma lacuna anteriormente observada na literatura (ex: Wan et al., 2021).

O artigo conclui com um estudo de caso numérico em um problema de controle contínuo, demonstrando a convergência das funções de valor e a redução do regret conforme a taxa de quantização aumenta, validando os limites teóricos.