Resumo Técnico: Revisão da Otimização de Política Regularizada para Aprendizado por Reforço Estável e Eficiente em Jogos de Dois Jogadores

Declaração do Problema

Jogos de soma zero com dois jogadores, particularmente jogos de tabuleiro, serviram como benchmarks tradicionais para aprendizado por reforço (RL). Embora métodos baseados em busca, como o AlphaZero (Silver et al., 2018), tenham alcançado desempenho superhumano ao combinar redes neurais profundas com busca de antecipação (por exemplo, Busca em Árvore Monte-Carlo, MCTS), eles incorrem em custos computacionais substanciais. O treinamento do AlphaZero, por exemplo, reportedly requer mais de 10 anos de GPU (Silver et al., 2018; Tian et al., 2019). Essa intensidade de recursos dificulta a reprodutibilidade e a aplicação prática em ambientes com recursos limitados (Zhao et al., 2022).

Embora estudos recentes tenham tentado reduzir o ônus computacional de métodos baseados em busca limitando a profundidade da árvore ou o número de simulações (Hessel et al., 2021; Danihelka et al., 2022), eles ainda dependem fundamentalmente da busca de antecipação. Por outro lado, métodos de RL sem modelo, que são eficientes em robótica e controle contínuo, não foram totalmente explorados em jogos de tabuleiro devido à instabilidade percebida em configurações de auto-jogo multiagente. A questão central abordada por este trabalho é: Um algoritmo puro de RL sem modelo pode alcançar aprendizado estável e competitivo em jogos de dois jogadores com significativamente menos recursos de treinamento do que contrapartes baseadas em busca?

Metodologia

Os autores propõem o KLENT (Otimização de Política Regularizada por KL e Entropia), um algoritmo de RL sem modelo que elimina a necessidade de MCTS durante o treinamento. A abordagem fundamenta-se na revisão da otimização de política regularizada com dois componentes específicos: regularização reversa de Kullback-Leibler (KL) e regularização de entropia.

1. Regra de Atualização da Política

O núcleo do KLENT é um problema de otimização de política regularizada definido como:
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
onde:

• $\pi'$ é a nova política e $\pi$ é a política anterior.
• $D_{KL}(\pi' \parallel \pi)$ é a divergência KL reversa, promovendo atualizações graduais da política para lidar com a não estacionariedade no auto-jogo.
• $H(\pi')$ é a entropia, incentivando exploração sustentada para evitar o sobreajuste à própria política do agente.
• $\alpha$ e $\beta$ são hiperparâmetros não negativos.

Dado o espaço de ações finito dos jogos de tabuleiro, a política ótima $\pi'$ admite uma solução analítica de forma fechada:
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
No KLENT, uma rede neural $\pi_\theta$ é treinada para minimizar a entropia cruzada entre sua saída e esse alvo $\pi'$ derivado analiticamente.

2. Aprendizado da Função Valor

Diferentemente de métodos baseados em busca que estimam valores de ação via backups de MCTS, o KLENT parametriza diretamente a função valor-ação $Q^\pi(s, a)$ usando uma rede neural. Para estabilizar o aprendizado e gerenciar o compromisso viés-variância, o algoritmo utiliza retornos $\lambda$ ($G^\lambda$) como alvo de aprendizado para a função valor, em vez dos retornos Monte Carlo padrão ($\lambda=1$). Experimentos preliminares indicaram que um $\lambda$ intermediário $\in (0, 1)$ minimiza a soma do viés quadrático e da variância melhor do que $\lambda=1$.

3. Estrutura do Algoritmo

O KLENT alterna entre uma fase de auto-jogo (coleta de dados on-policy) e uma fase de ajuste (atualização dos parâmetros da rede). A função de perda otimiza simultaneamente as redes de política e valor-ação:
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
Crucialmente, o KLENT não requer busca em árvore durante o treinamento, confiando apenas nas previsões da rede neural e na atualização analítica da política.

Principais Contribuições

O artigo faz três contribuições primárias, focando na caracterização teórica e empírica dessa combinação específica de regularização, em vez de propor ingredientes algorítmicos inteiramente novos:

1. Formulação Algorítmica: Os autores derivam um algoritmo prático de RL sem modelo (KLENT) baseado na combinação de regularização reversa-KL e regularização de entropia, fornecendo uma regra de atualização de política de forma fechada.
2. Garantias Teóricas: Novas garantias de convergência são fornecidas para a regra de atualização da política em dois cenários:
   • Jogos de Forma Normal: O artigo prova a convergência linear local para um ponto fixo único sob a condição $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$. Esta condição abrange uma faixa mais ampla de coeficientes de regularização do que resultados anteriores (por exemplo, Sokota et al., 2022).
   • Jogos de Comprimento Finito: Os autores provam que a política KLENT converge para uma política ótima regularizada por entropia (Equilíbrio de Resposta Quantal) via indução reversa, assumindo um horizonte de jogo finito.
3. Validação Empírica: Experimentos abrangentes em cinco jogos de tabuleiro (Shogi Animal, Xadrez Gardner, Go 9x9, Hex e Othello) demonstram que o KLENT alcança eficiência de treinamento significativamente maior do que bases de referência existentes baseadas em busca e sem modelo.

Resultados

Eficiência de Treinamento

Experimentos mostram que o KLENT aprende com mais eficiência do que métodos existentes em todos os ambientes testados.

• Ganho de Desempenho: Em média, o KLENT alcançou até 4x maior eficiência de treinamento em comparação com o Gumbel AlphaZero (a base de referência baseada em busca mais forte do estudo). Por exemplo, o Gumbel AlphaZero exigiu 300 milhões de avaliações de simulador para atingir uma taxa de vitória de 50%, enquanto o KLENT exigiu apenas 75 milhões.
• Escalabilidade: A lacuna de eficiência amplia-se em jogos com fatores de ramificação mais altos (por exemplo, Go 9x9, Hex), onde métodos baseados em busca exigem orçamentos substanciais de simulador. A vantagem do KLENT é atribuída à evitação da busca de antecipação e ao uso de retornos $\lambda$ estáveis.
• Desempenho em Grande Escala: No Go 19x19, o KLENT manteve eficiência de aprendizado competitiva em comparação com o AlphaZero, apesar do aumento da complexidade.

Estudos de Ablação

O estudo valida a necessidade de três técnicas-chave:

• Regularização Reversa-KL: Remover isso (definindo $\beta=0$) leva a atualizações abruptas da política e desempenho degradado, particularmente no Go 9x9.
• Regularização de Entropia: Remover isso (definindo $\alpha=0$) faz com que a política se torne excessivamente determinística (a entropia cai para perto de zero), levando a aprendizado instável e colapso de desempenho.
• Retornos $\lambda$: Substituir retornos $\lambda$ por backups de 1 passo ou retornos Monte Carlo resultou em quedas de desempenho, confirmando a importância de equilibrar viés e variância.

Desempenho no Tempo de Teste

Quando equipado com MCTS no tempo de teste (800 simulações), os agentes KLENT alcançaram altas taxas de vitória contra bases de referência, superando o AlphaZero e o Gumbel AlphaZero em confrontos diretos no Go 9x9 e Go 19x19.

Significado e Alegações

Os autores posicionam este trabalho como uma demonstração de que revisar adequadamente técnicas de regularização existentes pode levar a aprendizado estável e eficiente em domínios há muito dominados por métodos baseados em busca.

• Alegações Modestas: O artigo afirma explicitamente que sua principal contribuição não é um ingrediente algorítmico novo, mas uma nova caracterização teórica e empírica da otimização de política regularizada em jogos de dois jogadores.
• Limitações: Os autores reconhecem que, embora o KLENT alcance alta eficiência, ele não garante necessariamente desempenho assintótico superior quando recursos computacionais ilimitados estão disponíveis. Eles não excluem a eficácia de abordagens baseadas em busca como o AlphaZero quando recursos massivos (por exemplo, milhares de GPUs) estão acessíveis.
• Impacto Mais Amplo: Os autores sugerem que a premissa subjacente (MDP de ação finita) aplica-se a problemas do mundo real, como otimização discreta, descoberta algorítmica e prova matemática, onde métodos baseados em busca são atualmente prevalentes. Eles esperam que este trabalho incentive a extensão de tais abordagens eficientes e sem modelo para outros campos.

Em resumo, o KLENT oferece uma alternativa computacionalmente eficiente ao RL baseado em busca para jogos de tabuleiro, alcançando desempenho competitivo com uma fração dos recursos de treinamento, aproveitando a estabilidade da regularização reversa-KL e de entropia.