A flexible approach for optimal rewards in multi-agent reinforcement learning problems

Abstract

Defining a reward function that, when optimized, results in rapid acquisition of an optimal policy, is one of the most challenging tasks involved in applying reinforcement learning algorithms. The behavior learned by agents is directly related to the reward function they are using. Existing work on the Optimal Reward Problem (ORP) propose mechanisms to design reward functions. However, their application is limited to specific sub-classes of single or multi-agent reinforcement learning problems. Moreover, these methods identify which rewards should be given in which situation, but not which aspects of the state or environment should be used when defining the reward function. This thesis proposes an extended version of the optimal reward problem (EORP) that: i) can identify both features and reward signals that should compose the reward function; ii) is general enough to deal with single and multi-agent reinforcement learning problems; iii) is scalable to problems with large number of agents learning simultaneously; iv) incorporates a learning effort metric in the evaluation of reward functions, allowing the discovery of reward functions that result in faster learning. The method is evaluated on gridworld and traffic assignment problems to demonstrate its efficacy in designing effective reward functions. The results obtained by the proposed approach are compared to reward functions designed by a domain specialist and to a wellknown new design technique for multi-agent rewards called difference rewards. Results show that EORP can identify reward functions that outperform these two types of reward functions in the evaluated problems.

Definir uma função de recompensa que, quando otimizada, resulta em uma rápida aquisição de política ótima é uma das tarefas mais desafiadoras envolvendo o uso de algoritmos de aprendizado por reforço. O comportamento aprendido pelos agentes está diretamente relacionado à função de recompensa que eles estão utilizando. Trabalhos existentes sobre o Optimal Reward Problem (ORP) propõem mecanismos para projetar funções de recompensa. Entretanto, a aplicação de tais métodos é limitada à algumas subclasses específicas de problemas de aprendizado por reforço mono ou multiagente. Além do mais, os métodos em questão apenas identificam “o quanto” que um agente deve ser recompensado em cada situação, mas não “quais os” aspectos do estado ou ambiente que devem ser utilizados na estrutura da função de recompensa. Nesta tese, nós propomos melhorias no ORP tradicional, definindo uma versão estendida do optimal reward problem (EORP) que: i) pode identificar tanto as características do estado/ambiente quanto os sinais de recompensa que compõem a função de recompensa; ii) é geral o suficiente para lidar com problemas de aprendizado por reforço mono e multiagente; iii) é escalável para problemas onde existem grandes quantidades de agentes aprendendo simultaneamente; iv) incorpora uma métrica de esforço de aprendizagem na avaliação das funções de recompensa, permitindo a descoberta de funções de recompensa que resultam em um aprendizado mais rápido. Para demonstrar a eficácia do nosso método em projetar funções de recompensa efetivas, nós o avaliamos em dois cenários, onde os resultados são comparados com outras duas funções de recompensa: uma definida manualmente por um especialista de domínio e uma função do tipo difference rewards. Os resultados mostram que a nossa abordagem consegue identificar funções de recompensa que aprendem políticas de maior performance e que resultam em menor tempo de aprendizagem.