Decision Making under Imperfect Recall: Algorithms, Computational Complexity, and Benchmarks

In this talk, we investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. An example is the absentminded driver game, as well as team games in which the members have limited communication capabilities. Imperfect-recall decision problems are also prominent in modeling modern challenges in Trustworthy AI, such as privacy in systems that elicit sensitive information as well as AI safety via testing in simulation.

We investigate these settings theoretically by analyzing the computational complexity of finding various notions of equilibria in both single- and multiplayer games with imperfect recall. We further touch on the utility cost of losing memory, which we coin the "Value of Recall".

On the empirical front, we introduce the first benchmark suite for imperfect-recall decision problems, motivated by the applications in Trustworthy AI, on which we evaluate the performance of various solvers. In particular, we introduce the family of regret matching (RM) algorithms for decision making under imperfect recall, and nonlinear constrained optimization more generally. We find that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent. All in all, we establish that the RM family is a formidable approach to constrained optimization problems, in terms of large-scale practical solving as well as theoretical convergence guarantees.