Computing Robust Counter-Strategies
- Michael Johanson, University of Alberta
- Martin Zinkevich
- Michael Bowling, University of Alberta
Adaptation to other initially unknown agents often requires computing an effective counter-strategy. In the Bayesian paradigm, one must ï¬nd 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 modiï¬ed 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.
Citation
M. Johanson, M. Zinkevich, M. Bowling. "Computing Robust Counter-Strategies". Neural Information Processing Systems (NIPS), (ed: J.C. Platt, D. Koller, Y. Singer, S. Roweis), pp 721--728, December 2007.Keywords: | game theory |
Category: | In Conference |
BibTeX
@incollection{Johanson+al:NIPS07, author = {Michael Johanson and Martin Zinkevich and Michael Bowling}, title = {Computing Robust Counter-Strategies}, Editor = {J.C. Platt, D. Koller, Y. Singer, S. Roweis}, Pages = {721--728}, booktitle = {Neural Information Processing Systems (NIPS)}, year = 2007, }Last Updated: August 19, 2009
Submitted by Michael Johanson