Convergent Learning Algorithms for Unknown Reward Games

• Published in: SIAM journal on control and optimization 2013-01, Vol.51 (4), p.3154-3180
• Main Authors: Chapman, Archie C, Leslie, David S, Rogers, Alex, Jennings, Nicholas R
• Format: Article
• Language: English
• Subjects: Algorithms; Control algorithms; Convergence; Design; Effectiveness; Equilibrium; Estimates; Game theory; Games; Learning; On-line systems; Optimization; Stochasticity; Wireless networks
• ISSN: 0363-0129; 1095-7138
• DOI: 10.1137/120893501

In this paper, we address the problem of convergence to Nash equilibria in games with rewards that are initially unknown and 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 online, but standard results in game theory do not consider such settings. For this problem, we derive a multiagent version of $\mathcal{Q}$-learning to estimate the reward functions using novel forms of the $\epsilon$-greedy learning policy. Using these $\mathcal{Q}$-learning schemes to estimate reward functions, we then provide conditions guaranteeing the convergence of adaptive play and the better-reply processes to Nash equilibria in potential games and games with more general forms of acyclicity, and of regret matching to the set of correlated equilibria in generic games. A secondary result is that we prove the strong ergoditicity of stochastic adaptive play and stochastic better-reply processes in the case of vanishing perturbations. Finally, we illustrate the efficacy of the algorithms in a set of randomly generated three-player coordination games and show the practical necessity of our results by demonstrating that violations to the derived learning parameter conditions can cause the algorithms to fail to converge. [PUBLICATION ABSTRACT]