Heavy-Ball Q-Learning with Residual Weighting Correction

Resumo Técnico: Q-Learning com Heavy-Ball com Correção de Pesagem Residual

Definição do Problema
O Q-learning é um método fundamental em aprendizado por reforço (RL) para aprender funções Q ótimas sem um modelo de transição explícito. Embora o Q-learning padrão converja com base na propriedade de contração do operador de otimalidade de Bellman, essa contração pode ser fraca quando o fator de desconto $\gamma$ está próximo de um, levando a uma convergência lenta. Métodos de aceleração existentes, como atualizações baseadas em momentum, iterações do tipo PID e correções de rank-um, frequentemente carecem de garantias teóricas rigorosas de que superam o Q-learning padrão, particularmente em configurações de controle onde a política gulosa ativa muda dinamicamente. Um desafio específico surge ao aplicar o momentum heavy-ball ao Q-learning com pesos de amostragem não uniformes: a matriz de pesagem padrão destrói a propriedade de "autovetor comum" (especificamente o vetor de todos os uns) necessária para certas análises espectrais, tornando difícil certificar a aceleração teoricamente.

Metodologia
O artigo propõe um método de Q-Learning Heavy-Ball Corrigido (HBCQL) e estabelece suas propriedades de convergência e aceleração usando um framework de Sistema Linear Alternado (SLS).

1. Correção de Pesagem Residual (CQL):
   Os autores introduzem primeiro uma atualização de Q-learning "corrigida" (Algoritmo 2) para abordar a perda do autovetor comum no Q-learning com pesagem padrão. Eles substituem a matriz de amostragem diagonal padrão $D$ por uma matriz de correção $H = \delta \Pi_d + D(I - \Pi_d)$, onde $\Pi_d = \mathbf{1}d^\top$. Esta matriz $H$ é projetada de tal forma que mapeia o vetor constante $\mathbf{1}$ para um múltiplo escalar de si mesmo ($H\mathbf{1} = \delta\mathbf{1}$), restaurando assim um autovetor comum para a dinâmica média do algoritmo. Esta correção preserva o ponto fixo $Q^\star$ enquanto permite uma decomposição estrutural específica.

2. Momentum Heavy-Ball:
   O método estende o Q-learning corrigido adicionando um termo de momentum heavy-ball $\eta(Q_k - Q_{k-1})$ (Algoritmo 3). Isso transforma a recursão de primeira ordem em um sistema de segunda ordem.

3. Análise de SLS e Raio Espectral Conjunto (JSR):
   A ferramenta analítica central é a representação da dinâmica de erro do Q-learning como um Sistema Linear Alternado. O sinal de alternância é determinado pela seleção de ação gulosa no operador de Bellman. A taxa de convergência é caracterizada pelo Raio Espectral Conjunto (JSR) da família de matrizes de alternância associadas.

   • Decomposição: Os autores decompõem o espaço de estados no subespaço gerado pelo autovetor comum (ou subespaço invariante no caso do heavy-ball) e seu complemento ortogonal.
   • Mecanismo de Aceleração: A análise mostra que o JSR do sistema completo é o máximo do JSR do sistema projetado (ortogonal à direção comum) e do raio espectral da dinâmica ao longo da direção comum. A matriz de correção $H$ permite que a dinâmica ao longo da direção comum seja ajustada independentemente via o parâmetro $\delta$. O termo heavy-ball $\eta$ é então mostrado para acelerar a convergência ao longo desta direção específica sem impactar negativamente as dinâmicas projetadas, desde que $\eta$ seja suficientemente pequeno.

4. Extensão para Aproximação de Função Linear:
   O framework é estendido para aproximação de função linear (LQL). Uma matriz de correção $G$ semelhante é construída no espaço de características para garantir a existência de uma direção de autovetor comum (gerada por um vetor $c$ tal que $\Phi c = \mathbf{1}$). A mesma análise de SLS e JSR produz resultados de convergência e aceleração análogos.

Principais Contribuições

• Q-Learning Corrigido (CQL): A proposta de uma correção estrutural para a atualização do Q-learning que restaura a propriedade do autovetor comum para amostragem não uniforme, permitindo uma análise espectral rigorosa.
• Garantia Teórica de Aceleração: A derivação de condições suficientes (Suposições 4.1, 4.2 e 5.1) sob as quais o método HBCQL possui um JSR estritamente menor que tanto o Q-learning padrão quanto o Q-learning corrigido (sem momentum). Isso fornece uma "taxa certificada" de aceleração em uma direção especificamente identificável analiticamente.
• Framework SLS/JSR: A aplicação de Sistemas Lineares Alternados e análise de Raio Espectral Conjunto ao Q-learning, oferecendo uma perspectiva complementar aos argumentos de contração padrão. Esta abordagem lida explicitamente com a natureza de alternância da política gulosa.
• Extensão para Aproximação de Função: Generalização da correção e da teoria de aceleração para configurações de aproximação de função linear.

Resultados

• Convergência: O artigo prova que, sob as suposições declaradas, a recursão de erro converge uniformemente de forma exponencial para zero (ou para uma vizinhança de ruído no caso estocástico) com uma taxa limitada pelo JSR.
• Aceleração: A análise teórica (Teoremas 5.1 e 10.1) demonstra que, para pequenos parâmetros de momentum $\eta$, o JSR do sistema corrigido heavy-ball é estritamente menor que o do baseline padrão ou corrigido.
• Ilustrações Numéricas:
  • Em um cenário tabular determinístico, o HBCQL atingiu um limiar de erro relativo significativamente mais rápido que o CQL.
  • Em um cenário tabular estocástico, o HBCQL reduziu o tempo mediano para atingir um limiar de erro específico comparado ao Q-learning padrão e ao CQL.
  • Em configurações de aproximação de função linear (tanto determinísticas quanto estocásticas), o método corrigido heavy-ball (HBCLQL) superou consistentemente os métodos de Q-learning linear padrão e corrigido em termos de velocidade de convergência.

Significância e Alegações
O artigo afirma fornecer um certificado preciso de aceleração em uma direção identificável analiticamente, em vez de um teorema de aceleração para todas as direções. Os autores enfatizam que a contribuição é uma garantia teórica para uma direção geométrica específica, o que oferece novos insights sobre a geometria do Q-learning heavy-ball.

O trabalho distingue-se da literatura existente de momentum por:

1. Focar no cenário de controle (onde a política muda) em vez de apenas na avaliação de política;
2. Usar SLS e JSR em vez de argumentos de política fixa ou apenas limites de aproximação estocástica;
3. Fornecer uma correção estrutural que torna a análise de aceleração tratável para amostragem não uniforme, um cenário onde o Q-learning heavy-ball padrão carece de um autovetor comum.

Os autores observam que a garantia de aceleração é condicional à suposição do "gap projetado" (que as dinâmicas projetadas são mais rápidas que as dinâmicas da direção comum) e a parâmetros de momentum pequenos. Eles não alegam aceleração universal para todas as escolhas de parâmetros ou todos os MDPs, mas sim identificam um regime onde o método é teoricamente garantido para ser mais rápido. A análise é realizada principalmente em dinâmicas médias determinísticas, com extensões para cenários estocásticos via argumentos padrão de média condicional.