Reinforcement Learning Using known Invariances

1. Formulação do Problema

O Aprendizado por Reforço (RL) frequentemente luta com a eficiência de amostragem, particularmente em ambientes com espaços contínuos de estado-ação e aproximações de funções não lineares. Uma fonte significativa de ineficiência é a falha em explorar simetrias estruturais inerentes a problemas do mundo real (por exemplo, invariância rotacional em robótica, simetria de reflexão em jogos de tabuleiro ou invariância de permutação em sistemas multiagente).

Embora trabalhos anteriores tenham explorado simetria via aumento de dados ou redes neurais equivariantes, falta um quadro teórico rigoroso que quantifique os ganhos de complexidade de amostragem da incorporação de simetrias de grupo conhecidas diretamente em métodos de RL baseados em kernels não paramétricos. O artigo aborda a questão: Como as simetrias conhecidas do ambiente podem ser exploradas sistematicamente para melhorar a eficiência de amostragem e as garantias de arrependimento sob aproximação de função não linear?

2. Metodologia

Os autores propõem um algoritmo Symmetry-Aware Kernel-based Optimistic Least-Squares Value Iteration (KOVI) (Iteração de Valor de Mínimos Quadrados Ótima Baseada em Kernel Consciente de Simetria). A metodologia central envolve três componentes principais:

A. Kernels Invariantes e Espaço de Hilbert de Kernel Reprodutor (RKHS)

Em vez de aprender invariâncias a partir dos dados, os autores assumem que o grupo de simetria $G$ é conhecido a priori. Eles constroem um kernel totalmente invariante $k_G$ a partir de um kernel base $k$:
$$k_G(z, z') = \frac{1}{|G|} \sum_{g \in G} k(g(z), z')$$
Este kernel induz um Espaço de Hilbert de Kernel Reprodutor (RKHS) $\mathcal{H}_{k_G}$ consistindo apenas de funções que são invariantes sob a ação do grupo $G$. Ao restringir o espaço de hipóteses a este RKHS invariante, o algoritmo respeita inerentemente as simetrias das dinâmicas de recompensa e transição.

B. O Algoritmo (KOVI)

O algoritmo adapta a Iteração de Valor Ótima Baseada em Kernel padrão (Yang et al., 2020a):

1. LSVI Ótima: Em cada passo $h$ de um episódio, o agente estima a função Q ótima $\hat{Q}_h$ usando regressão de ridge de kernel nos dados observados.
2. Bônus de Confiança: Um limite superior de confiança (UCB) é adicionado para encorajar a exploração: $Q_h = \min(\hat{Q}_h + \beta b_h, H-h+1)$.
3. Integração de Simetria: A regressão é realizada usando o kernel invariante $k_G$, garantindo que as funções de valor estimadas e as políticas ganancias resultantes respeitem as simetrias do grupo.

C. Quadro Teórico

Os autores derivam novos limites teóricos para este cenário consciente de simetria:

• Ganho Máximo de Informação ($\Gamma(T)$): Eles estabelecem que, para kernels invariantes, o ganho máximo de informação escala como $O(T^{1/p} / |G|^{1/p})$, onde $|G|$ é o tamanho do grupo e $p$ relaciona-se ao decaimento do autovalor do kernel.
• Números de Cobertura: Eles derivam novos limites para o número de cobertura da classe de funções de funções Q invariantes, mostrando uma redução proporcional a $1/|G|$.
• Limites de Arrependimento: Combinando estes, eles provam que o arrependimento cumulativo $R(T)$ escala com um fator de $1/|G|$ em comparação com métodos baseados em kernel padrão. Especificamente, para dimensões grandes, o limite de arrependimento melhora significativamente, quantificando o ganho de eficiência de amostragem.

3. Contribuições Principais

1. Inovação Algorítmica: Introdução de uma variante consciente de simetria do LSVI ótima que incorpora invariâncias de grupo tanto nas dinâmicas de recompensa quanto de transição via kernels totalmente invariantes.
2. Avanço Teórico: A primeira análise teórica quantificando ganhos de complexidade de amostragem em RL devido à incorporação de simetria. Eles fornecem limites novos sobre o ganho máximo de informação e números de cobertura para RKHSs invariantes, mostrando explicitamente uma melhoria de $1/|G|$ nos limites de arrependimento.
3. Validação Empírica: Experimentos extensivos demonstrando que o RL consciente de simetria supera significativamente os equivalentes baseados em kernel padrão e até redes neurais profundas equvariantes em regimes específicos de baixos dados.

4. Resultados Experimentais

Os autores validaram sua abordagem em três configurações distintas:

• MDP Sintético: Uma configuração simplificada com $|G|=2$ (identidade e inversão). O KOVI com kernel invariante alcançou um arrependimento cumulativo significativamente menor em comparação com o KOVI com kernel RBF padrão.
• Frozen Lake (OpenAI Gym):
  • Layout Fixo: O ambiente é invariante sob o grupo de simetria $D_4$ (rotações e reflexões de um quadrado). O KOVI com kernels invariantes convergiu mais rápido e alcançou retornos mais altos do que o KOVI RBF padrão.
  • Layout Aleatório: Uma configuração mais desafiadora onde o layout muda a cada episódio, mas retém a simetria $D_4$. O kernel invariante consistentemente superou o kernel padrão, demonstrando generalização robusta.
  • Comparação com RL Profundo: O KOVI com kernels invariantes superou tanto o DQN padrão quanto o SymDQN (um DQN com camadas equvariantes) em termos de eficiência de amostragem, convergindo para retornos ótimos com menos passos de tempo.
• Problema de Posicionamento 2D (SynPl): Uma tarefa inspirada em design de chips envolvendo a colocação de 8 unidades em uma grade $8\times8$. Este problema envolve restrições geométricas complexas e espaços de estado de alta dimensão. A abordagem com kernel invariante produziu menor arrependimento e configurações de posicionamento melhores em comparação com a linha de base, destacando a utilidade da simetria em problemas de design estruturado.

5. Significado e Conclusão

• Eficiência de Amostragem: O artigo demonstra que codificar explicitamente priores estruturais conhecidos (simetrias) na classe de aproximação de função (via kernels invariantes) leva a reduções substanciais na complexidade de amostragem. Isso é crucial para aplicações do mundo real onde a coleta de dados é cara ou demorada.
• Rigor Teórico: Diferente do aumento de dados heurístico ou de redes equvariantes paramétricas, este trabalho fornece garantias formais de arrependimento e quantifica o benefício exato da simetria em termos do tamanho do grupo $|G|$.
• Vantagem Não Paramétrica: Os resultados sugerem que, em regimes de baixos dados, métodos de kernel não paramétricos com restrições de simetria podem superar abordagens de aprendizado profundo (mesmo aquelas projetadas com simetria), pois requerem menos dados para convergir para políticas ótimas.
• Limitações: Os autores reconhecem que a complexidade computacional dos métodos de kernel ($O(HT^4)$) pode ser proibitiva para conjuntos de dados muito grandes, embora sugiram otimizações como GPs esparsos ou atualizações de Cholesky para mitigar isso.

Em resumo, este trabalho preenche a lacuna entre a teoria de grupos teórica e o RL prático, fornecendo um quadro robusto para alavancar simetrias conhecidas para construir agentes de aprendizado mais eficientes e generalizáveis.