| Recent years have seen a rapidly growing interest in multi-agent systems, and in particular in learning algorithms for such systems. The problem of learning in a multi-agent system is qualitatively more difficult than the single agent learning situation. The optimal policy is now fundamentally dependent on the strategies employed by the other agents and the environment is dynamic, changing character over time as the agents adapt to one another's behavior.; There are a number of different research agendas one could pursue under the name of learning in multi-agent systems. I will focus on an agent-centric agenda, in which one asks how an agent should act in order to maximize its rewards in the presence of other agents who may also be learning (using the same or other learning algorithms). After discussing existing work from both artificial intelligence and game theory, I define a new formal criterion to guide the development of algorithms in this setting. This new criterion takes in as a parameter a class of opponents and requires the agent to learn to behave optimally against members of that class while providing a security value guarantee against all opponents and yielding high reward when paired with other identical algorithms.; Using this criterion as a guideline, I'll describe a modular approach for achieving effective agent-centric learning. I demonstrate the power of this approach in the environment of general-sum known repeated games by providing several specific instantiations for both stationary opponents and opponents with bounded recall. These algorithms are shown both to satisfy the formal criterion and to achieve superior experimental results when compared with existing algorithms in comprehensive computer testing. I then discuss possible extensions to these algorithms for situations in which the agent has limited access to the payoff structure for the game. These extensions include a novel algorithm that is applicable over a wide variety of informational assumptions and shows significant improvements over existing approaches from the literature. I conclude with an analysis of the value of teaching in achieving high empirical payoffs and some suggestions for future work. |
