The goal of agents in multi-agent environments is to maximize total reward against the opposing agents that are encountered. Following a game-theoretic solution concept, such as Nash equilibrium, may obtain a strong performance in some settings; however, such approaches fail to capitalize on historical and observed data from repeated interactions against our opponents. Opponent modeling algorithms integrate machine learning techniques to exploit suboptimal opponents utilizing available data; however, the effectiveness of such approaches in imperfect-information games to date is quite limited. We show that existing opponent modeling approaches fail to satisfy a simple desirable property even against static opponents drawn from a known prior distribution; namely, they do not guarantee that the model approaches the opponent's true strategy even in the limit as the number of iterations approaches infinity. We develop a new algorithm that achieves this property given sufficiently informative observations and runs efficiently by solving a convex minimization problem based on the sequence-form game representation.
Figures & tables
Figure 1: Game tree for Kuhn poker.
∅
BK
ChK
ChKCaK
ChKFK
BQ
ChQ
ChQCaQ
ChQFQ
BJ
ChJ
ChJCaJ
ChJFJ
1
-1
1
1
-1
1
1
-1
1
1
-1
1
1
-1
1
1
Table 1: Matrix E for Kuhn poker.
∅
caQ
fQ
bQ
chQ
caJ
fJ
bJ
chJ
caK
fK
bK
chK
1
-1
1
1
-1
1
1
-1
1
1
-1
1
1
-1
1
1
Table 2: Matrix F for Kuhn poker.
∅
caQ
fQ
bQ
chQ
caJ
fJ
bJ
chJ
caK
fK
bK
chK
∅
BK
31
61
31
61
ChK
61
61
ChKCaK
31
31
ChKFK
−61
−61
BQ
31
61
−31
61
Table 3: Matrix A for Kuhn poker.
Leaf node ℓ
o1(ℓ)
o2(ℓ)
BKcaQ
{BKcaQ}
{BKcaQ}
BKfQ
{BKfQ,BKfJ}
{BKfQ,BJfQ}
ChKbQCaK
{ChKbQCaK}
{ChKbQCaK}
ChKbQFK
{ChKbQFK,ChKbJFK}
{ChKbQFK,ChJbQFJ}
ChKchQ
{ChKchQ}
{ChKchQ}
BKcaJ
{BKcaJ}
{BKcaJ}
Table 4: Observability functions o1 and o2 .
Figure 2: Expected payoff as a function of game iteration for several opponent modeling algorithms and benchmark strategies. The results are averaged over 100 opponents generated randomly from the prior distribution. The sampling algorithms all use 10 samples.