Computing Robust Counter-Strategies

Michael Johanson, Martin Zinkevich, and Michael Bowling. Computing Robust Counter-Strategies. In Advances in Neural Information Processing Systems 20 (NIPS), pp. 1128–1135, 2008. A longer version is available as a University of Alberta Technical Report, TR07-15.


[PDF] [gzipped postscript] 


Adaptation to other initially unknown agents often requires computing an effective counter-strategy. In the Bayesian paradigm, one must find a good counter-strategy to the inferred posterior of the other agents' behavior. In the experts paradigm, one may want to choose experts that are good counter-strategies to the other agents' expected behavior. In this paper we introduce a technique for computing robust counter-strategies for adaptation in multiagent scenarios under a variety of paradigms. The strategies can take advantage of a suspected tendency in the decisions of the other agents, while bounding the worst-case performance when the tendency is not observed. The technique involves solving a modified game, and therefore can make use of recently developed algorithms for solving very large extensive games. We demonstrate the effectiveness of the technique in two-player Texas Hold'em. We show that the computed poker strategies are substantially more robust than best response counter-strategies, while still exploiting a suspected tendency. We also compose the generated strategies in an experts algorithm showing a dramatic improvement in performance over using simple best responses.


  Title = "Computing Robust Counter-Strategies",
  Author = "Michael Johanson and Martin Zinkevich and Michael Bowling",
  Booktitle = "Advances in Neural Information Processing Systems 20 (NIPS)",
  Year = "2008",
  Pages = "1128--1135",
  Note = "A longer version is available as a University of Alberta Technical Report, TR07-15",
  AcceptRate = "22\%",
  AcceptNumbers = "217 of 975"

Generated by (written by Patrick Riley) on Fri Feb 13, 2015 15:54:28