Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Resumo Técnico: Redistribuição de Recompensa para MDPs de CVaR usando um Operador de Bellman em L-infinity

Enunciado do Problema
Em aplicações críticas à segurança, otimizar o retorno esperado (neutro ao risco) é frequentemente insuficiente, pois pode permitir resultados raros, porém catastróficos. O Valor em Risco Condicional (CVaR) estático é uma medida de risco coerente usada para controlar a cauda inferior da distribuição de retorno. No entanto, diferentemente dos objetivos neutros ao risco, o CVaR estático de um retorno carece de separabilidade recursiva sobre o espaço de estados nominal, impedindo uma decomposição de Bellman Markoviana padrão.

Abordagens existentes, notadamente Bauerle & Ott (2011), tratam isso aumentando o espaço de estados com uma variável de "orçamento" contínua que rastreia as recompensas cumulativas. Embora teoricamente sólidas, essa formulação sofre de duas limitações práticas críticas:

1. Recompensas Esparsas: A informação relevante para o CVaR está concentrada inteiramente em um funcional terminal do estado aumentado. Isso resulta em recompensas por passo nulas no MDP aumentado, criando um feedback atrasado que exacerba os desafios de exploração e atribuição de crédito temporal, particularmente em configurações de horizonte infinito.
2. Convergência Restrita: O operador de Bellman associado à formulação de Bauerle & Ott é garantido como uma contração apenas em um conjunto altamente restrito de funções não limitadas. No espaço mais prático de funções limitadas ($L^\infty$), o operador admite um ponto fixo degenerado (a função zero), tornando a iteração de valor e o Q-learning padrão inaplicáveis sem restrições de inicialização cuidadosas e, muitas vezes, inviáveis.

Metodologia
Os autores propõem uma nova reformulação do objetivo de CVaR estático que resolve essas limitações através de uma transformação algébrica da função de valor.

1. MDP Aumentado Transformado: Construindo sobre o aumento de estado de Bauerle & Ott (2011), os autores definem uma nova função de valor $\bar{v}^*(s, z)$ que incorpora um termo de deslocamento $z^-$ (a parte negativa do orçamento). Esta transformação permite a derivação de um novo operador de Bellman, $\bar{T}$, definido no espaço de funções limitadas $\bar{T}$ em $L^\infty(\bar{S})$.
2. Redistribuição de Recompensa: A inovação principal é a definição de uma nova função de recompensa por passo $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$. Ao contrário da formulação anterior, que gerava recompensas intermediárias nulas, esta nova recompensa é densa e informativa em cada passo, efetivamente redistribuindo o sinal relevante do CVaR ao longo da trajetória.
3. Propriedades de Contração: Os autores provam que o novo operador $\bar{T}$ é uma $\gamma$-contração em relação à norma sup sobre o espaço total de funções limitadas. Isso garante que a iteração de valor converja para um ponto fixo único sem exigir as condições de inicialização restritivas do trabalho anterior.
4. Discretização e Aproximação: Como o estado aumentado $z$ é contínuo, os autores empregam um esquema de discretização uniforme. Eles definem operadores de limite inferior e superior ($\bar{T}^l$ e $\bar{T}^u$) usando funções de envelope para aproximar o operador real. Eles estabelecem limites teóricos mostrando que o erro entre o CVaR ótimo e a aproximação discretizada escala proporcionalmente com a granularidade da discretização e o fator de desconto.
5. Algoritmos: Com base neste framework, o artigo desenvolve:
   • Iteração de Valor de CVaR Estático: Um algoritmo baseado em modelo que computa a função Q ótima para todos os estados iniciais e níveis de orçamento simultaneamente.
   • Q-Learning de CVaR Estático: Um algoritmo livre de modelo que utiliza uma estratégia de atualização em bloco. Aproveitando a natureza determinística da transição de estado aumentado, o algoritmo re-rotula uma única trajetória para atualizar os valores de Q para múltiplas hipóteses de orçamento iniciais, melhorando a eficiência de dados. A convergência é provada sob as condições padrão de tamanho de passo de Robbins-Monro.

Principais Contribuições

• Novo Operador de Bellman: O artigo introduz um operador de Bellman para CVaR estático de horizonte infinito que opera em um espaço de estados aumentado, é exato em relação ao objetivo de controle, fornece recompensas por passo não esparsas e é uma aplicação de contração em funções limitadas.
• Garantias de Aproximação: Os autores fornecem limites rigorosos de erro de aproximação para o CVaR discretizado, quantificando a lacuna de desempenho como uma função da resolução da grade.
• Provas de Convergência: O artigo estabelece condições suficientes para a convergência do algoritmo de Q-learning proposto para a função de valor-ação ótima no espaço aumentado discretizado.
• Otimalidade Global: Os algoritmos produzem soluções globalmente ótimas para todos os níveis de risco (estados aumentados iniciais) em uma única execução, em vez de exigir treinamento separado para cada parâmetro de risco.

Resultados Empíricos
Os autores validam sua abordagem em um ambiente de gridworld estocástico ("Crater Walk") onde um agente deve navegar de um início a um objetivo enquanto evita uma cratera (penalidade alta) e minimiza o uso de combustível (penalidade de passo).

• Sensibilidade ao Risco: As políticas aprendidas ajustam o comportamento com sucesso com base no parâmetro de risco $\alpha$. À medida que $\alpha$ diminui (aumentando a aversão ao risco), a cauda inferior da distribuição de retorno encolhe, e o agente evita a cratera com mais frequência, mesmo que isso exija um caminho mais longo.
• Desempenho: Ambos os algoritmos de Iteração de Valor e Q-learning alcançam trade-offs eficazes entre desempenho e segurança. O algoritmo de Q-learning converge dentro de 50.000 iterações de treinamento.
• Precisão da Discretização: Experimentos variando a resolução da discretização (de 100 a 5000 bins) demonstram que as curvas de desempenho dos operadores de limite inferior e superior convergem para o valor ótimo real conforme a resolução aumenta, validando empiricamente os limites de erro teóricos.

Significância e Alegações
O artigo afirma que as limitações de recompensas esparsas e garantias de convergência restritas em MDPs de CVaR estático não são intrínsecas ao problema, mas sim artefatos de escolhas de modelagem específicas na literatura anterior. Ao propor uma reformulação exata que redistribui recompensas e opera em funções limitadas, os autores permitem a aplicação de técnicas padrão de programação dinâmica e aprendizado por reforço livre de modelo para problemas de risco estático sensíveis ao risco. Este trabalho lança as bases para algoritmos de RL escaláveis e avessos ao risco que não dependem de capping heurístico de recompensa ou currículos de risco especializados. Os autores observam que, embora sua análise empírica se concentre em configurações tabulares, o framework teórico suporta extensões futuras para aproximação de função (por exemplo, redes neurais profundas) para lidar com espaços de estados contínuos sem restrições de sinal de recompensa.