Aprendizado por Reforço com Valores deInfluência em Sistemas Multi-Agente

We propose a new paradigm for collective learning in multi-agent systems (MAS) as a solution to the problem in which several agents acting over the same environment must learn how to perform tasks, simultaneously, based on feedbacks given by each one of the other agents. We introduce the proposed paradigm in the form of a reinforcement learning algorithm, nominating it as reinforcement learning with influence values. While learning by rewards, each agent evaluates the relation between the current state and/or action executed at this state (actual believe) together with the reward obtained after all agents that are interacting perform their actions. The reward is a result of the interference of others. The agent considers the opinions of all its colleagues in order to attempt to change the values of its states and/or actions. The idea is that the system, as a whole, must reach an equilibrium, where all agents get satisfied with the obtained results. This means that the values of the state/actions pairs match the reward obtained by each agent. This dynamical way of setting the values for states and/or actions makes this new reinforcement learning paradigm the first to include, naturally, the fact that the presence of other agents in the environment turns it a dynamical model. As a direct result, we implicitly include the internal state, the actions and the rewards obtained by all the other agents in the internal state of each agent. This makes our proposal the first complete solution to the conceptual problem that rises when applying reinforcement learning in multi-agent systems, which is caused by the difference existent between the environment and agent models. With basis on the proposed model, we create the IVQ-learning algorithm that is exhaustive tested in repetitive games with two, three and four agents and in stochastic games that need cooperation and in games that need collaboration. This algorithm shows to be a good option for obtaining solutions that guarantee convergence to the Nash optimum equilibrium in cooperative problems. Experiments performed clear shows that the proposed paradigm is theoretical and experimentally superior to the traditional approaches. Yet, with the creation of this new paradigm the set of reinforcement learning applications in MAS grows up. That is, besides the possibility of applying the algorithm in traditional learning problems in MAS, as for example coordination of tasks in multi-robot systems, it is possible to apply reinforcement learning in problems that are essentially collaborative

Conselho Nacional de Desenvolvimento Científico e Tecnológico

Propomos um novo paradigma de aprendizado coletivo em sistemas multi-agentes (SMA) como uma solução para o problema em que vários agentes devem aprender como realizar tarefas agindo sobre um mesmo ambiente, simultaneamente, baseando-se em retornos fornecidos por cada um dos outros agentes. Introduzimos o paradigma proposto na forma do algoritmo de aprendizado por reforço, denominando-o de aprendizado por reforço com valores de influência. Cada agente aprendendo por reforço avalia a relação existente entre o valor do seu estado atual e/ou a ação executada no estado (crenças atuais) junto com a recompensa obtida após todos os agentes que estão interagindo executarem suas ações (resultado da interferência dos outros). O agente pondera as opiniões de todos os seus colegas na tentativa de mudar os valores dos seus estados e/ou ações. A idéia é que o sistema como um todo deve chegar a um equilíbrio, onde todos os agentes se sentem satisfeitos com os resultados obtidos, significando que os valores dos estados ou pares estado/ação casam-se com a recompensa obtida por cada agente. Esta forma dinâmica de atualizar o valor dos estados e/ou ações faz deste novo paradigma de aprendizado por reforço o primeiro a incluir, naturalmente, o fato de que a presença de outros agentes no ambiente o torna dinâmico. Como resultado direto, incluímos implicitamente o estado interno, as ações e a recompensa obtida por todos os outros agentes dentro do estado interno de cada agente. Isso faz de nossa proposta a primeira solução completa para o problema conceitual que surge ao aplicar aprendizado por reforço em sistemas multi-agente, causado pela diferença existente entre o modelo do ambiente e o modelo do agente. Com base no modelo proposto, criamos o algoritmo IVQ-Learning, testado exaustivamente em jogos repetitivos com dois, três e quatro agentes e em jogos estocásticos que exijam cooperação e em jogos que exijam colaboração. Este algoritmo mostra-se como uma boa opção na tentativa de obter soluções que garantam a convergência para o equilíbrio de Nash ótimo em problemas cooperativos. Os experimentos realizados deixam claro que o paradigma proposto é teórica e experimentalmente superior aos paradigmas tradicionais. Ainda, com a criação deste novo paradigma, o conjunto de aplicações de aprendizado por reforço em SMA foi ampliado. Ou seja, além da possibilidade de aplicar os algoritmos nos problemas tradicionais de aprendizado em SMA, como por exemplo coordenação de tarefas em sistemas multi-robô, é possível aplicar aprendizado por reforço nos problemas essencialmente colaborativos