Strategic best-response learning in multiagent systems

Bikramjit Banerjee, Jing Peng

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

We present a novel and uniform formulation of the problem of reinforcement learning against bounded memory adaptive adversaries in repeated games, and the methodologies to accomplish learning in this novel framework. First we delineate a novel strategic definition of best response that optimises rewards over multiple steps, as opposed to the notion of tactical best response in game theory. We show that the problem of learning a strategic best response reduces to that of learning an optimal policy in a Markov Decision Process (MDP). We deal with both finite and infinite horizon versions of this problem. We adapt an existing Monte Carlo based algorithm for learning optimal policies in such MDPs over finite horizon, in polynomial time. 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, simple experiments in the Prisoner's Dilemma, and coordination games show that even when no extra domain knowledge (besides that an upper bound on the opponent's memory size is known) is assumed, the error can still be small. We also experiment with a general infinite-horizon learner (using function-approximation to tackle the complexity of history space) against a greedy bounded memory opponent and show that while it can create and exploit opportunities of mutual cooperation in the Prisoner's Dilemma game, it is cautious enough to ensure minimax payoffs in the Rock-Scissors-Paper game.

Original languageEnglish
Pages (from-to)139-160
Number of pages22
JournalJournal of Experimental and Theoretical Artificial Intelligence
Volume24
Issue number2
DOIs
StatePublished - 1 Jun 2012

Keywords

  • game theory
  • multiagent learning
  • reinforcement learning

Fingerprint Dive into the research topics of 'Strategic best-response learning in multiagent systems'. Together they form a unique fingerprint.

  • Cite this