Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

Resumo Técnico: Aprendizado por Reforço Esparso Não Convexo via Inclusões Não Monótonas

Definição do Problema
O aprendizado por reforço (RL) frequentemente enfrenta a "maldição da dimensionalidade" ao aproximar funções Q em espaços de estados de alta dimensão. Embora a aproximação linear seja um remédio padrão, ela introduz um compromisso entre precisão de aproximação e complexidade computacional. A seleção de características via modelagem esparsa é uma estratégia comum para mitigar isso, contudo, as abordagens convencionais que dependem da regularização de norma $\ell_1$ (ex: LARS-TD, LSTD com $\ell_1$) sofrem de viés de estimativa, subestimando sistematicamente componentes de grande amplitude. Além disso, em configurações de RL em lote (batch RL), onde os dados são fixos e potencialmente ruidosos, a robustez a características irrelevantes e outliers é crítica. Embora penalidades não convexas como a penalidade de Minimax Concave (MC) tenham sido propostas na regressão esparsa para reduzir o viés, sua aplicação ao RL permanece inexplorada devido à não convexidade resultante do problema de otimização, o que quebra as suposições de monotonicidade necessárias para garantias de convergência padrão em métodos de divisão de operadores (operator splitting).

Metodologia
O artigo propõe um novo algoritmo em lote para seleção de características em RL que integra a penalidade Projetiva Minimax Concave (PMC) na formulação de Mínimos Quadrados de Diferença Temporal (LSTD).

1. Reformulação do Problema: Os autores formulam o problema de avaliação de política como a busca por um ponto fixo de um mapeamento que minimiza um erro de diferença temporal de mínimos quadrados regularizado pela penalidade PMC. Diferente do LSTD padrão, este objetivo é não convexo.
2. Divisão de Operadores (Operator Splitting): Ao explorar a convexidade fraca da penalidade PMC, o problema de ponto fixo é reformulado como a busca pelo zero da soma de dois operadores: um operador Lipschitziano monótono e um operador hipomonotônico. Isso coloca o problema dentro da classe de inclusões não monótonas.
3. Solução Algorítmica: Os autores empregam o método de Divisão de Recuo-Direto-Inverso (FRBS - Forward-Reflected-Backward Splitting) para resolver este problema de inclusão. Uma contribuição técnica fundamental é a derivação de uma expressão de forma fechada para o resolvente da parte hipomonotônica (envolvendo o operador de soft-shrinkage), o que torna o algoritmo tratável sem variáveis auxiliares.
4. Ajuste de Hiperparâmetros: O método introduz um hiperparâmetro ajustável $q$ que controla o subespaço $M$ sobre o qual o efeito de redução de viés da penalidade PMC é confinado. Isso generaliza a definição original da PMC, permitindo a otimização do desempenho da penalidade mesmo quando a matriz de Gram de entrada possui autovalores positivos muito pequenos.

Principais Contribuições
O artigo apresenta quatro contribuições primárias:

• Algoritmo de RL: Introduz um método eficiente de seleção de características em lote para RL que incorpora a penalidade não convexa PMC ao LSTD. Isso aborda o viés de estimativa inerente aos métodos regularizados por norma $\ell_1$.
• Extensão Teórica: Estende a análise de convergência do método FRBS para uma classe mais ampla de problemas de inclusão não monótona. Especificamente, estabelece:
  • Estabilidade de Lyapunov: Sob condições suaves, mostra-se que as iterações são quase-Fejér monótonas, garantindo a existência de um ponto limite e estabilidade.
  • Convergência Exata: Sob a suposição de Desigualdade Variacional de Minty (MVI) fraca, prova-se que a sequência converge exatamente para uma solução.
• Penalidade PMC Generalizada: O artigo generaliza a penalidade PMC ao permitir que o subespaço $M$ seja controlado por um parâmetro ajustável $q$, em vez de ser fixo ao complemento ortogonal do núcleo (null space). Isso evita a degradação do desempenho em configurações mal condicionadas.
• Limites de Erro: Um limite de erro para políticas geradas pelo esquema de Iteração de Política Aproximada (API) proposto é fornecido, vinculando o erro de aproximação ao erro de estimativa da função Q.

Resultos
Testes numéricos foram conduzidos em três tarefas de benchmark de RL: o chain walk de 50 estados, o mountain car e o acrobot. O método proposto foi comparado contra métodos de estado da arte para seleção de características em lote, incluindo LSTD, LARS-TD e Basis Pursuit Denoising (BPDN).

• Desempenho: O método proposto superou substancialmente os concorrentes, particularmente em cenários com numerosas características ruidosas ou irrelevantes. Nas tarefas mountain car e acrobot, alcançou as maiores taxas de sucesso e o menor número médio de passos para atingir o objetivo.
• Mitigação de Viés: Os resultados demonstraram que o método proposto mitiga efetivamente o viés de estimativa associado à regularização de norma $\ell_1$, levando a estimativas de função Q mais precisas.
• Sensibilidade de Hiperparâmetros: Experimentos no chain walk de 50 estados mostraram que o hiperparâmetro $q$ influencia significamente o desempenho. Uma faixa moderada de $q$ resultou no menor Erro Quadrático Médio Normalizado (NMSE), enquanto valores extremos degradaram o desempenho ao falhar em reduzir o viés suficientemente ou ao forçar a penalidade a aproximar a norma $\ell_1$ enviesada.

Significância
O artigo afirma fornecer uma base teórica rigorosa para a aplicação de penalidades não convexas em RL, um domínio que anteriormente evitava tais métodos devido a preocupações de convergência. Ao estabelecer garantias de convergência para o FRBS em contextos não monótonos, o trabalho preenche a lacuna entre a teoria de modelagem esparsa não convexa e aplicações práticas de RL. Os autores afirmam que sua abordagem oferece uma alternativa robusta à regularização convexa, entregando seleção de características e desempenho de política superiores em ambientes de alta dimensão e ruidosos, sem sacrificar as garantias de convergência teórica. O trabalho estende uma versão preliminar de conferência ao fornecer provas completas de convergência sob suposições de MVI fraca e validação numérica extensiva.