Poker-AI.org

Action Translation in Extensive-Form Games with Large Action Spaces: Axioms, Paradoxes, and the Pseudo-Harmonic Mapping
by: Sam Ganzfried and Tuomas Sandholm

Abstract
When solving extensive-form games with large action spaces, typically significant abstraction is needed to make the problem manageable from a modeling or computational perspective. When this occurs, a procedure is needed to interpret actions of the opponent that fall outside of our abstraction (by mapping them to actions in our abstraction). This is called an action translation mapping. Prior action translation mappings have been based on heuristics without theoretical justification. We show that the prior mappings are highly exploitable and that most of them violate certain natural desiderata. We present a new mapping that satisfies these desiderata and has significantly lower exploitability than the prior mappings. Furthermore, we observe that the cost of this worst-case performance benefit (low exploitability) is not high in practice; our mapping performs competitively with the prior mappings against no-limit Texas Hold’em agents submitted to the 2012 Annual Computer Poker Competition. We also observe several paradoxes that can arise when performing action abstraction and translation; for example, we show that it is possible to improve performance by including suboptimal actions in our abstraction and excluding optimal actions.

http://www.cs.cmu.edu/~sganzfri/Translation_IJCAI13.pdf

Did I miss the contribution of the paper? The action mapping they present was already published in a previous paper, and the evaluation was not showing something like "if you dont use this metric, you are screwed", but rather, it works great for toy games and is not bad in practice...

@p2bb:
Things like "Strictly use X instead of Y" usually are rare in AI world, because great advance in research of X (like "use CFRM instead of LP or you'll be doomed") doesn't happen too often. I prefer to think about this paper as another POV to this complicated problem. And it has some clear and nice propositions which give some food for thought (at least for me).

well, I don't expect to find a message like "Strictly use X instead of Y", but the action mapping they presented is not new, they already wrote in a previous paper about it. So the only new contribution is a bit more extensive evaluation, which doesn't look too convincing to me as it doesn't seem like a significant improvement in non-toy games.

Are they saying that by attaching some theory to the translation you can predict which buckets in the abstraction will give you less real game exploitability when using said translation method?

nope, they motivate their formular with the Clairvoyance Game and list some properties an action mapping should have - all of which has been done in the previous papers. Then they evaluate the exploitability in toy games (clairvoyance, kuhn and leduc) and in texas holdem - while it was better in the toy games (well, its derived from it), it did not perform as good in the holdem case. They argue its because the bots did not exploit action abstraction which is right, but I doubt the effect is too relevant in practice given we use a reasonable mapping...

What previous paper was the new mapping published in?

Only one of the prior mappings satisfies all the properties (Randomized Arithmetic), and that mapping is terrible, as shown by the example in 5.2 and the exploitabilities in all the toy games. No prior papers listed any properties. The new mapping is derived from the Clairvoyance game, but not from Kuhn/Leduc. It is intractable to compute exploitability in NLHE, so exploitabilities must be evaluated in smaller games. The new mapping did a lot better in TH than the randomized geometric ones, which are presumably the alternative one would use.

Interesting