Resumo Técnico: Otimização de Política Primal-Dual para CMDPs Lineares com Perdas Adversariais

Configuração do Problema

Este artigo aborda o desafio da Aprendizagem por Reforço (RL) Segura em ambientes onde as restrições de segurança devem ser satisfeitas apesar de perturbações adversariais. Especificamente, os autores consideram Processos de Decisão de Markov (CMDPs) Lineares com Horizonte Finito e Perdas Adversariais.

A configuração é definida pela tupla $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, onde:

• Perdas Adversariais: As funções de perda $f^k = \{f^k_h\}$ são escolhidas arbitrariamente por um adversário no início de cada episódio $k$ (feedback de informação completa). Essas perdas não são extraídas de uma distribuição fixa.
• Custos Estocásticos: As funções de custo $g^k = \{g^k_h\}$ são amostradas i.i.d. de uma distribuição fixa $G$ (feedback de banda), representando restrições de segurança.
• Estrutura Linear: Os kernels de transição, as funções de perda e as funções de custo possuem uma estrutura linear em relação a um mapeamento de características conhecido $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Objetivo: O agente busca uma política que minimize a perda esperada cumulativa, garantindo que o custo esperado cumulativo não exceda um orçamento $b$.

O desempenho é medido pelo Arrependimento (diferença cumulativa de perda em comparação com a política ótima) e pela Violação de Restrição (custo excedente cumulativo sobre o orçamento). O objetivo é alcançar limites sublineares para ambas as métricas.

Metodologia

Os autores propõem um algoritmo de Otimização de Política Primal-Dual (Algoritmo 1) projetado para lidar com a interação entre perdas adversariais e restrições estocásticas em um cenário de aproximação de função linear. O algoritmo integra quatro componentes principais:

1. Inicialização de Época e Contração de Características:
   O algoritmo opera em épocas. Uma época começa quando o determinante da matriz de design $\Lambda^k_h$ aumenta por um fator multiplicativo. Na inicialização, a política é redefinida para uma política uniforme e a variável dual é redefinida para zero. Crucialmente, o algoritmo emprega contração de características, encolhendo a característica original $\phi$ usando uma função sigmoide para evitar que as estimativas da função Q se expandam incontrolavelmente. Esta técnica, adaptada de Cassel & Rosenberg (2024), simplifica a representação da política para argumentos de número de cobertura.

2. Execução da Política e Estimação:
   Em cada episódio, o agente executa ações com base na política atual, observa a perda adversarial e o custo estocástico, e atualiza a matriz de design. Em seguida, estima os parâmetros para as funções de perda e custo e computa estimativas da função Q ($\hat{Q}$) e estimativas da função valor ($\hat{V}$) usando as características contraídas e bônus otimistas.

3. Mistura Periódica de Políticas:
   Uma inovação central é a mistura periódica de políticas. Em vez de misturar a política (perturbando-a em direção a uma política uniforme) em cada episódio, o algoritmo aplica a mistura apenas uma vez a cada $K^B$ episódios (onde $B=3/4$).

   • Motivação: A mistura frequente é necessária para limitar a variável dual (via análise de deriva), mas aumenta a complexidade da classe de políticas (número de cobertura). A mistura periódica equilibra esses requisitos concorrentes.
   • Mecanismo: A cada $K^{3/4}$ episódios, a política atual $\hat{\pi}^k$ é misturada com a política uniforme $\pi_{unif}$ através de uma combinação convexa: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Atualização Dual Regularizada:
   A variável dual $Y^k$ (associada à restrição de custo) é atualizada usando um passo de ascensão de gradiente regularizada:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   Os termos de regularização ($-4\alpha\eta H^3 Y^k$ e constantes) são projetados para puxar a variável dual em direção a zero, permitindo uma análise de deriva de Lyapunov para limitar $Y^k$ sem depender das suposições de dualidade forte que falham em cenários adversariais.

5. Políticas Softmax LogSumExp Ponderadas:
   A classe de políticas resultante é um softmax LogSumExp ponderado. Devido à mistura periódica, a política não é uma exponencial simples da soma das funções Q, mas uma soma ponderada de exponenciais de somas parciais de estimativas da função Q. Esta estrutura permite que a política se adapte a perdas escolhidas adversarialmente, mantendo um número de cobertura tratável.

Principais Contribuições

1. Primeiros Limites Sublineares para CMDPs Lineares Adversariais:
   O artigo apresenta o primeiro algoritmo a alcançar limites sublineares de arrependimento e violação de restrição no cenário de CMDPs lineares com perdas adversariais e custos estocásticos. Os limites são $\tilde{O}(K^{3/4})$, onde $K$ é o número de episódios.

2. Novo Argumento de Número de Cobertura:
   Os autores estabelecem um novo argumento de número de cobertura para as políticas softmax LogSumExp ponderadas. Diferentemente das políticas softmax padrão onde os pesos são uniformes, o processo de mistura introduz parâmetros de peso variáveis $\zeta_i$. Os autores provam que o logaritmo do número de cobertura para esta classe cresce como $\tilde{O}(n^2 d^2)$, onde $n$ é o número de etapas de mistura e $d$ é a dimensão da característica. Este resultado é não trivial porque os parâmetros de peso dependem tanto do parâmetro de mistura quanto das estimativas da função Q.

3. Componentes Algorítmicos para Controle:
   O artigo introduz dois componentes novos para controlar conjuntamente o número de cobertura e a variável dual:

   • Mistura Periódica de Políticas: Regula a frequência da mistura para impedir que o número de cobertura cresça excessivamente (o que aconteceria com $O(K)$ etapas de mistura), enquanto ainda ocorre com frequência suficiente para limitar a variável dual.
   • Atualização Dual Regularizada: Uma nova regra de atualização que incorpora um termo de regularização para facilitar a análise baseada em deriva, permitindo o limite da variável dual na ausência de dualidade forte.

Resultados

Garantias Teóricas:
Sob a condição de Slater (Suposição 1) e assumindo $H^2 \leq K$, com probabilidade de pelo menos $1-\delta$, o algoritmo alcança:

• Arrependimento: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Violação de Restrição: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Ambas as métricas escalonam sublinearmente com $K$ (especificamente $K^{3/4}$), indicando que o arrependimento médio e a violação média de restrição convergem para zero à medida que o número de episódios aumenta.

Experimentos Numéricos:
O algoritmo foi avaliado em um CMDP de agendamento de tarefas modificado com perdas adversariais. Ao longo de $100.000$ episódios:

• Arrependimento: Cresceu sublinearmente, confirmando o limite teórico.
• Violação de Restrição: Inicialmente cresceu rapidamente, mas convergiu para zero após aproximadamente 45.000 episódios, validando a capacidade do algoritmo de satisfazer restrições de segurança a longo prazo.

Significado e Alegações

O artigo alega ser o primeiro algoritmo comprovadamente eficiente para RL segura com aproximação de função linear em cenários adversariais. Seu significado reside em preencher a lacuna entre:

1. CMDPs Adversariais Tabulares: Trabalhos anteriores (e.g., Qiu et al., 2020) lidaram com cenários adversariais, mas foram limitados a espaços de estados pequenos e finitos.
2. CMDPs Lineares Estocásticos: Trabalhos anteriores (e.g., Ghosh et al., 2022) lidaram com grandes espaços de estados, mas assumiram ambientes estacionários (estocásticos).

Ao introduzir a política softmax LogSumExp ponderada e a estratégia de mistura periódica, os autores demonstram que é possível lidar com grandes espaços de estados (via aproximação linear) e perdas adversariais simultaneamente. O artigo nota modestamente que, embora $\tilde{O}(K^{3/4})$ seja alcançado, o limite ótimo $\tilde{O}(\sqrt{K})$ permanece uma questão em aberto para este cenário específico, particularmente em relação ao trade-off entre etapas de mistura e números de cobertura. O trabalho também destaca a dificuldade de estender atualizações duais baseadas em medidas de ocupação para métodos baseados em política em CMDPs lineares adversariais, justificando a abordagem proposta de otimização de política primal-dual.