Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Doutor em Ciências (D.Sc.)
Uma Abordagem via Funções de Liapunov com Controle à Dinâmica de Aprendizado em Jogos de Dois Jogadores
Rodrigo Brandolt Sodré de Macedo
Dezembro/2010
| Programa: |
Engenharia Elétrica |
Esta tese foca na dinâmica de aprendizado de jogos, especificamente nas várias propostas recentes da literatura em jogos de duas ações, dois jogadores. Essas propostas, conhecidas por gradiente ascendente incremental (IGA) e "vença ou aprenda rápido" (WoLF-IGA), utilizam uma forma de gradiente ascendente ao longo de uma função de valor, chamada também de função recompensa, junto com algumas leis de chaveamento heurísticas. A tese propõe o uso de função de Liapunov de controle (FLC) para desenvolver projetos de aprendizado envolvendo chaveamento, que é típico quando FLC são usadas em sistemas não lineares, permitindo a unificação de todas as propostas recentes na área de aprendizado por gradiente ascendente em jogos, também provendo provas rigorosas, inexistentes em muitas dessas propostas, de convergência ao equilíbrio misto. Ademais, a perspectiva de controle também conduz a generalizações dessas propostas, primeiro propondo novas leis de chaveamento que podem levar a melhoria de desempenho. E mais, com exceção de uma das propostas existentes, chamada de heurística de aprendizado de política ponderada (WPL), todas as propostas anteriores assumem que o jogo subjacente, isto é, ambas matrizes de recompensa, são conhecidas de ambos jogadores. Nesse respeito, a tese examina WPL e mostra que, pela introdução do conceito de equilíbrio virtual, essa política também pode ser considerada como um projeto de controle chaveado usando FLC, chegando-se a uma prova rigorosa. Além disso, a técnica de estimação de mínimos quadrados é introduzida de modo a estimar a combinação requerida de parâmetros de matrizes de recompensa que surgem em outra proposta recente, chamada aprendizado probabilístico de Boltzmann, que mostra que uma FLC adequada permite o projeto de estratégias que convergem ao equilíbrio de Nash misto desejado, em jogos padrão tal como o jogo casar moedas.
