  Two fundamental problems in computational game theory are computing a Nash
equilibrium and learning to exploit opponents given observations of their play
(opponent exploitation). The latter is perhaps even more important than the
former: Nash equilibrium does not have a compelling theoretical justification
in game classes other than two-player zero-sum, and for all games one can
potentially do better by exploiting perceived weaknesses of the opponent than
by following a static equilibrium strategy throughout the match. The natural
setting for opponent exploitation is the Bayesian setting where we have a prior
model that is integrated with observations to create a posterior opponent model
that we respond to. The most natural, and a well-studied prior distribution is
the Dirichlet distribution. An exact polynomial-time algorithm is known for
best-responding to the posterior distribution for an opponent assuming a
Dirichlet prior with multinomial sampling in normal-form games; however, for
imperfect-information games the best known algorithm is based on approximating
an infinite integral without theoretical guarantees. We present the first exact
algorithm for a natural class of imperfect-information games. We demonstrate
that our algorithm runs quickly in practice and outperforms the best prior
approaches. We also present an algorithm for the uniform prior setting.
