Best Agent Identification for General Game Playing

1. O Problema

O campo do Jogo Geral (General Game Playing - GGP) foca no desenvolvimento de agentes de IA capazes de jogar uma vasta variedade de jogos. Um desafio central neste domínio é a avaliação eficiente de agentes. À medida que o número de jogos e agentes cresce, o tempo necessário para avaliar o desempenho de cada agente em todos os jogos torna-se proibitivo, especialmente porque muitos agentes não jogam de forma determinística, exigindo múltiplas execuções (tentativas) para obter estimativas precisas.

O objetivo do artigo não é avaliar o desempenho geral de um agente em todos os jogos, mas sim identificar o melhor (ou quase melhor) agente para cada jogo individual dentro de um conjunto definido, utilizando um número limitado de tentativas. Este problema é formalizado como um problema de Identificação do Melhor Braço (Best Arm Identification - BAI) em um ambiente de Múltiplos Bandits (Multi-Bandit):

• Cada bandit representa um jogo específico.
• Cada braço representa um agente disponível para jogar aquele jogo.
• O objetivo é selecionar um único agente para cada jogo de modo a maximizar a recompensa total (número de vitórias) ao final do período de exploração.

2. Metodologia: O Algoritmo RCP

Os autores propõem um novo algoritmo chamado RCP (Regret Change Potential - Potencial de Mudança de Arrependimento). Diferente de abordagens anteriores que focam em minimizar a probabilidade de erro ou em explorar uniformemente, o RCP adota uma filosofia de "otimismo frente à incerteza" para minimizar o arrependimento simples médio (average simple regret).

Principais Características do RCP:

• Mecanismo de Seleção: O algoritmo calcula o "potencial de mudança de arrependimento" ($\Delta_{mk}$) para cada par (jogo, agente). Isso é feito comparando os limites de confiança (superior e inferior) da recompensa estimada de um braço com a recompensa esperada do melhor braço atual naquele bandit.
  • Para braços que não são os melhores atuais, assume-se uma perspectiva otimista (usa-se o limite superior de confiança).
  • Para o braço que é o melhor atual, assume-se uma perspectiva pessimista (usa-se o limite inferior de confiança).
• Intervalos de Confiança: O RCP é flexível quanto ao intervalo de confiança utilizado. Os autores testaram várias estimativas binomiais (Wilson Score, Jeffreys, Clopper-Pearson, Agresti-Coull) e não-binomiais (KL-UCB, PAC). O Wilson Score demonstrou ser particularmente eficaz.
• Flexibilidade Operacional:
  • Parada a qualquer momento (Stop Anytime): O algoritmo pode retornar o melhor agente identificado em qualquer rodada, sem perda de desempenho, ao contrário de algoritmos que exigem um número fixo de rodadas pré-definido.
  • Adaptabilidade: Suporta a adição dinâmica de novos jogos ou agentes durante a execução.
  • Assimetria de Braços: Lida naturalmente com jogos que têm diferentes números de agentes disponíveis.

3. Contribuições Principais

1. Novo Algoritmo (RCP): Introdução de uma abordagem baseada no potencial de mudança de arrependimento, que prioriza a redução do arrependimento simples global em vez de apenas tentar encontrar o "único" melhor braço com certeza absoluta.
2. Aplicação ao Domínio de Jogos Gerais: Formalização do problema de seleção de agentes para GGP como um problema de Multi-Bandit BAI, considerando restrições específicas do domínio (limites de recompensa [0,1], variabilidade de resultados, e presença de empates).
3. Análise Comparativa Abrangente: Avaliação extensiva contra algoritmos state-of-the-art (GapE, GapE-V, UCB-E, Successive Rejects, Sequential Halving) em dois dos maiores conjuntos de dados de GGP: GVGAI (Video Games) e Ludii (Jogos de Tabuleiro).

4. Resultados Experimentais

Os experimentos foram realizados em dois conjuntos de dados reais:

• GVGAI: 108 jogos, 27 agentes, ~4 milhões de tentativas.
• Ludii: 1085 jogos, 29 variantes de agentes, ~3,4 milhões de tentativas.

Desempenho:

• Redução de Arrependimento Simples: O RCP superou consistentemente todas as outras abordagens.
  • No GVGAI, o arrependimento simples do RCP foi 35,7% menor que o segundo melhor (UCB-E) e 64,5% menor que a amostragem uniforme.
  • No Ludii, a melhoria foi de 35,5% em relação ao UCB-E.
• Probabilidade de Erro (APE): Embora o foco fosse o arrependimento, o RCP também reduziu a probabilidade de erro, embora com margens menores (ex: 10,4% a 20,2% de melhoria) em comparação com a redução no arrependimento.
• Eficiência de Amostragem: O RCP demonstrou ser superior na distribuição dinâmica de tentativas, focando recursos nos jogos onde a incerteza sobre o melhor agente era maior, ao contrário de métodos que distribuem tentativas uniformemente ou exigem rodadas fixas (como Successive Rejects), que falharam em cenários com muitos jogos e poucas tentativas por jogo.

5. Significado e Impacto

O trabalho demonstra que a otimização direta do arrependimento simples é uma estratégia mais eficaz para a avaliação de agentes em jogos gerais do que a otimização da probabilidade de erro ou a exploração uniforme.

• Aplicabilidade Prática: O RCP permite que pesquisadores e desenvolvedores identifiquem rapidamente o melhor agente para um jogo específico com muito menos tempo de computação, acelerando o ciclo de desenvolvimento de agentes de IA.
• Melhoria de Agentes de Portfólio: A técnica pode ser usada para treinar modelos de previsão (agentes de portfólio) que selecionam o melhor agente para um jogo desconhecido, utilizando dados de treinamento gerados de forma mais eficiente pelo RCP.
• Generalização: A abordagem é agnóstica ao domínio e pode ser aplicada a qualquer problema multi-tarefa onde as recompensas estão limitadas entre 0 e 1 e o custo de avaliação é alto.

Em resumo, o artigo apresenta uma solução robusta e eficiente para o gargalo de avaliação em sistemas de jogos gerais, oferecendo uma melhoria substancial na precisão e velocidade de identificação dos melhores agentes.