Learning Payoff Functions in Infinite Games

Y Vorobeychik, MP Wellman, and S Singh

Machine Learning 67:145–168, 2007
Copyright (c) 2007, Springer.

Abstract

We consider a class of games with real-valued strategies and payoff information available only in the form of data from a given sample of strategy profiles. Solving such games with respect to the underlying strategy space requires generalizing from the data to a complete payoff-function representation. We address payoff-function learning as a standard regression problem, with provision for capturing known structure (e.g., symmetry) in the multiagent environment. To measure learning performance, we consider the relative utility of prescribed strategies, rather than the accuracy of payoff functions per se. We demonstrate our approach and evaluate its effectiveness on two examples: a two-player version of the first-price sealed-bid auction (with known analytical form), and a five-player market-based scheduling game (with no known solution). Additionally, we explore the efficacy of using relative utility of strategies as a target of supervised learning and as a learning model selector. Our experiments demonstrate its effectiveness in the former case, though not in the latter.

A previous version appeared in the Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, pages 977–982, 2005.

A preliminary version of this paper was presented at the AAAI Fall Symposium on Artificial Multi-Agent Learning, October 2004.

Downloads

• Full Paper