Experience generalization for multi-agent reinforcement learning

On-line learning methods have been applied successfully in multi-agent systems to achieve coordination among agents. Learning in multi-agent systems implies a non-stationary scenario perceived by the agents, since the behavior of other agents may change as they simultaneously learn how to improve their actions. Non-stationary scenarios can be modeled as Markov games, which can be solved using the Minimax-Q algorithm - a combination of Q-learning (a reinforcement learning (RL) algorithm which directly learns an optimal control policy) and the Minimax algorithm. However, finding optimal control policies using any RL algorithm (Q-learning and Minimax-Q included) can be very time consuming. In an attempt to improve the learning time of Q-learning, we considered the QS-algorithm, in which a single experience can update more than a single action value by using a spreading function. In this paper, we present a Minimax-QS algorithm which combines the Minimax-Q algorithm and QS-algorithm. We conduct a series of empirical evaluations of the algorithm in a simplified simulator of the soccer domain. We show that even when using a very simple domain-dependent spreading function, the performance of the learning algorithm can be improved