Resumo Técnico: Método de Lagrangiano Aumentado para Convergência na Última Iteração em MDPs Constrained

Formulação do Problema

O artigo aborda o problema de otimização de políticas para Processos de Decisão de Markov (MDPs) Constrained com horizonte infinito e desconto. Neste cenário, um agente deve maximizar uma recompensa cumulativa $V^\pi_r(\rho)$, garantindo ao mesmo tempo que as recompensas cumulativas de restrição $V^\pi_{c_i}(\rho)$ satisfaçam os limites prescritos $b_i$ para $m$ restrições. Diferentemente dos MDPs padrão, onde as políticas ótimas são determinísticas, as políticas ótimas para MDPs Constrained são geralmente estocásticas.

Um desafio prático significativo surge das limitações dos métodos Primal-Dual (PD) existentes. Embora existam garantias teóricas para métodos PD, elas tipicamente se aplicam apenas a uma política de mistura (uma média uniforme de todas as políticas intermediárias geradas durante o treinamento). Implantar tal mistura é computacionalmente e em termos de memória intensivo, pois requer o armazenamento de todas as políticas intermediárias. Além disso, em aplicações críticas para a segurança, confiar em uma mistura é arriscado, pois uma política amostrada aleatoriamente da mistura pode violar as restrições significativamente, mesmo que a mistura satisfaça-as em expectativa. Consequentemente, os praticantes frequentemente implantam a política da última iteração (a política final gerada), mas os métodos PD padrão carecem de garantias teóricas para esta política específica, exibindo frequentemente comportamento oscilatório e falhando em convergir para uma solução viável.

Trabalhos recentes que tentam provar convergência na última iteração foram amplamente limitados a configurações tabulares ou dependem de variantes algorítmicas (por exemplo, regularização pesada) que são difíceis de implementar ou impraticáveis para problemas em grande escala.

Metodologia

Os autores propõem um quadro geral baseado no método de Lagrangiano Aumentado (AL), uma abordagem clássica em otimização com restrições, para alcançar convergência provável na última iteração para MDPs Constrained.

1. O Quadro do Lagrangiano Aumentado

Em vez do Lagrangiano padrão usado em métodos PD, o quadro otimiza a função Lagrangiano Aumentado $L_\beta(\pi, \lambda)$:
$$L_\beta(\pi, \lambda) := V^\pi_r(\rho) + \frac{\beta}{2} \sum_{i=1}^m \left( -\min\left\{ V^\pi_{c_i}(\rho) - b_i - \frac{\lambda_i}{\beta}, 0 \right\}^2 + \frac{\lambda_i^2}{\beta^2} \right)$$
onde $\beta > 0$ é um parâmetro de penalidade e $\lambda$ são multiplicadores de Lagrange. O termo de penalidade quadrática desencoraja violações de restrição. O algoritmo atualiza iterativamente a política (variável primal) para maximizar aproximadamente esta função e atualiza as variáveis duais (multiplicadores de Lagrange) com base nas violações de restrição.

2. Resolução do Subproblema AL

O desafio central é que $L_\beta(\pi, \lambda)$ é não côncava em relação à política $\pi$, tornando o subproblema difícil de resolver. Os autores decompõem a solução em dois cenários:

• Configuração Tabular: Os autores propõem resolver o subproblema AL usando Ascensão Q Projetada (PQA). Eles derivam o gradiente da política para o subproblema AL, que envolve uma recompensa pseudo não estacionária $\Gamma(\pi)$ que depende do nível de satisfação de restrição da política atual. Ao usar PQA, eles estabelecem garantias de convergência global na última iteração para o subproblema.
• Aproximação de Função (Políticas Log-Lineares): Para lidar com grandes espaços de estado-ação, o quadro é estendido para políticas paramétricas (especificamente políticas log-lineares). Os autores derivam um gradiente de política AL que se decompõe linearmente nos componentes de recompensa e restrição originais, permitindo o uso de ferramentas de estimação padrão (como as usadas em PPO ou SPMA). Eles introduzem uma atualização PQA Projetada (PPQA), que envolve:
  1. Computar uma atualização de política idealizada (etapa PQA).
  2. Projetar esta atualização na classe de políticas viáveis usando a divergência KL direta, formulada como um problema de otimização substituto (regressão logística multiclasse com rótulos suaves).

3. Análise de Convergência

Os autores fornecem uma análise modular:

1. Eles primeiro provam que o método AL inexato converge para uma solução $\epsilon$-ótima para o MDP Constrained se o solver do subproblema atingir uma precisão específica ($O(1/\epsilon^2)$ iterações para o loop externo).
2. Eles analisam então os solvers específicos (PQA e PPQA) para mostrar que podem atingir a precisão necessária para o subproblema.
3. Combinando esses resultados, eles provam que o algoritmo geral alcança convergência global na última iteração com uma complexidade de amostragem de $O(1/\epsilon^6)$ avaliações de gradiente para ambos os cenários tabular e log-linear.

Contribuições Principais

1. Quadro Genérico de AL Inexato: O artigo introduz um quadro modular para resolver MDPs Constrained usando o método AL inexato. Ele separa a análise das iterações AL da escolha do solver do subproblema, provando que $O(1/\epsilon^2)$ iterações externas são suficientes para encontrar uma política $\epsilon$-ótima, desde que o subproblema seja resolvido com precisão suficiente.
2. Convergência na Última Iteração em Configuração Tabular: Ao instanciar o quadro com Ascensão Q Projetada (PQA) para a configuração tabular, os autores estabelecem convergência global na última iteração com complexidade de $O(1/\epsilon^6)$. Isso aborda a não estacionariedade da recompensa pseudo no subproblema AL.
3. Extensão para Aproximação de Função: O quadro é generalizado para políticas log-lineares. Os autores derivam o gradiente de política AL e propõem uma variante projetada (PPQA) que alcança garantias de convergência comparáveis de $O(1/\epsilon^6)$. Diferentemente de trabalhos anteriores, este método não requer modificações algorítmicas não padrão (como projetar em simplex restritos) ou suposições estruturais restritivas (como aproximação de função compatível) e suporta múltiplas restrições.
4. Validação Empírica: O quadro é instanciado usando PPO e SPMA (um algoritmo recente de otimização de políticas) e avaliado em tarefas de controle contínuo em grande escala do Safety-Gymnasium. Os resultados demonstram que a abordagem proposta desempenha de forma comparável a bases altamente engenhosas como PPO-Lag e CPO, enquanto oferece garantias teóricas para a política final.

Resultados

• Teórico: O artigo prova que o algoritmo proposto retorna uma política estocástica que é uma solução $\epsilon$-aproximada para o problema de MDP Constrained após $O(1/\epsilon^6)$ avaliações de gradiente. Isso vale para ambas as classes de políticas tabular e log-linear.
• Empírico (Tabular): Em ambientes tabulares (Constrained Cliff World, Constrained Deep Sea Treasure), os métodos propostos PQA-ALM e PPQA-ALM convergem suavemente para a política ótima com oscilação mínima, superando ou igualando outros métodos de última iteração como RPG-PD e ReLOAD.
• Empírico (Controle Contínuo): Em tarefas do Safety-Gymnasium (SafetyAntVelocity, SafetyHalfCheetahVelocity, SafetyHopperVelocity), as variantes SPMA-ALM e PPO-ALM alcançam retornos e violações de restrição comparáveis ao PPO-Lag e CPO. Notavelmente, os métodos baseados em AL exibem menos comportamento oscilatório e satisfação de restrição mais consistente (menores violações médias e de cauda) em comparação com as bases.

Significado e Alegações

O artigo afirma preencher a lacuna entre garantias teóricas e implantação prática em aprendizado por reforço com restrições.

• Praticidade: Diferentemente de trabalhos anteriores de convergência na última iteração que são limitados a configurações tabulares ou dependem de regularizações impraticáveis, este quadro é projetado para ser eficiente e escalável para grandes problemas usando aproximação de função padrão.
• Segurança: Ao garantir convergência para a política da última iteração em vez de uma mistura, o método assegura que a política implantada em si satisfaça as restrições, o que é crítico para aplicações críticas para a segurança onde a amostragem aleatória de uma mistura é inaceitável.
• Abordagem Principiada: O método baseia-se no clássico método de Lagrangiano Aumentado, fornecendo uma base teórica clara sem a necessidade de heurísticas ad hoc frequentemente encontradas em implementações práticas de RL com restrições (por exemplo, escalonar objetivos por multiplicadores).

Os autores reconhecem limitações, especificamente a forte dependência da probabilidade mínima de visitação de estado ($\rho_{min}$) na configuração tabular e o termo de viés ($\epsilon_{bias}$) para políticas log-lineares, sugerindo estas como direções para trabalho futuro. Eles também notam que direções futuras incluem incorporar métodos ator-crítico ou off-policy no quadro teórico.