Convergent learning algorithms for potential games with unknown noisy rewards

Archie C. Chapman, Nicholas R. Jennings, David S. Leslie and Alex Rogers

No 05/2011, Working Papers from University of Sydney Business School, Discipline of Business Analytics

Abstract: In this paper, we address the problem of convergence to Nash equilibria in games with rewards that are initially unknown and which must be estimated over time from noisy observations. These games arise in many real-world applications, whenever rewards for actions cannot be prespecified and must be learned on-line. Standard results in game theory, however, do not consider such settings. Specifically, using results from stochastic approximation and differential inclusions, we prove the convergence of variants of fictitious play and adaptive play to Nash equilibria in potential games and weakly acyclic games, respectively. These variants all use a multi-agent version of Q-learning to estimate the reward functions and a novel form of the e-greedy decision rule to select an action. Furthermore, we derive e-greedy decision rules that exploit the sparse interaction structure encoded in two compact graphical representations of games, known as graphical and hypergraphical normal form, to improve the convergence rate of the learning algorithms. The structure captured in these representations naturally occurs in many distributed optimisation and control applications. Finally, we demonstrate the efficacy of the algorithms in a simulated ad hoc wireless sensor network management problem.

Keywords: Game theory; distributed optimisation; learning in games (search for similar items in EconPapers)
Date: 2011-08
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/2123/8160

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:syb:wpbsba:2123/8160

Access Statistics for this paper

More papers in Working Papers from University of Sydney Business School, Discipline of Business Analytics Contact information at EDIRC.
Bibliographic data for series maintained by Artem Prokhorov ().