Efficient learning of multi-step best response

Bikramjit Banerjee, Jing Peng

Research output: Contribution to conferencePaper

5 Scopus citations

Abstract

We provide a uniform framework for learning against a recent history adversary in arbitrary repeated bimatrix games, by modeling such an agent as a Markov Decision Process. We focus on learning an optimal non-stationary policy in such an MDP over a finite horizon and adapt an existing efficient Monte Carlo based algorithm for learning optimal policies in such MDPs. We show that this new efficient algorithm can obtain higher average rewards than a previously known efficient algorithm against some opponents in the contract game. Though this improvement comes at the cost of increased domain knowledge, a simple experiment in the Prisoner's Dilemma game shows that even when no extra domain knowledge (besides that the opponent's memory size is known) is assumed, the error can still be small.

Original languageEnglish
Pages209-215
Number of pages7
Publication statusPublished - 1 Dec 2005
Event4th International Conference on Autonomous Agents and Multi agent Systems, AAMAS 05 - Utrecht, Netherlands
Duration: 25 Jul 200529 Jul 2005

Other

Other4th International Conference on Autonomous Agents and Multi agent Systems, AAMAS 05
CountryNetherlands
CityUtrecht
Period25/07/0529/07/05

    Fingerprint

Keywords

  • Efficient Learning
  • Game Theory
  • Multiagent Learning

Cite this

Banerjee, B., & Peng, J. (2005). Efficient learning of multi-step best response. 209-215. Paper presented at 4th International Conference on Autonomous Agents and Multi agent Systems, AAMAS 05, Utrecht, Netherlands.