A Practical Use of Imperfect Recall

Abstract

Perfect recall is the common and natural assumption that an agent never forgets. As a consequence, the agent can always condition its choice of action on any prior observations. In this paper, we explore relaxing this assumption. We observe the negative impact this relaxation has on algorithms: some algorithms are no longer well-defined, while others lose their theoretical guarantees on the quality of a solution. Despite these disadvantages, we show that removing this restriction can provide considerable empirical advantages when model-ing extremely large extensive games. In particular, it allows fine granularity of the most relevant observations without re-quiring decisions to be contingent on all past observations. In the domain of poker, this improvement enables new types of information to be used in the abstraction. By making use of imperfect recall and new types of information, our poker pro-gram was able to win the limit equilibrium event as well as the no-limit event at the 2008 AAAI Computer Poker Com-petition. We show experimental results to verify that our pro-grams using imperfect recall are indeed stronger than their perfect recall counterparts.