TY - JOUR
AU - Davis, Trevor
AU - Burch, Neil
AU - Bowling, Michael
PY - 2014/06/21
Y2 - 2024/08/15
TI - Using Response Functions to Measure Strategy Strength
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 28
IS - 1
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v28i1.8830
UR - https://ojs.aaai.org/index.php/AAAI/article/view/8830
SP -
AB - <p> Extensive-form games are a powerful tool for representing complex multi-agent interactions. Nash equilibrium strategies are commonly used as a solution concept for extensive-form games, but many games are too large for the computation of Nash equilibria to be tractable. In these large games, exploitability has traditionally been used to measure deviation from Nash equilibrium, and thus strategies are aimed to achieve minimal exploitability. However, while exploitability measures a strategy's worst-case performance, it fails to capture how likely that worst-case is to be observed in practice. In fact, empirical evidence has shown that a less exploitable strategy can perform worse than a more exploitable strategy in one-on-one play against a variety of opponents. In this work, we propose a class of response functions that can be used to measure the strength of a strategy. We prove that standard no-regret algorithms can be used to learn optimal strategies for a scenario where the opponent uses one of these response functions. We demonstrate the effectiveness of this technique in Leduc Hold'em against opponents that use the UCT Monte Carlo tree search algorithm. </p>
ER -