Solving Imperfect-Recall Games via Sum-of-Squares Optimization

Extensive-form games (EFGs) provide a powerful framework for modeling sequential decision making, capturing strategic interaction under imperfect information, chance events, and temporal structure. Most positive algorithmic and theoretical results for EFGs assume perfect recall, where players remember all past information and actions. We study the increasingly relevant setting of imperfect-recall EFGs (IREFGs), where players may forget parts of their history or previously acquired information, and where equilibrium computation is provably hard. We propose sum-of-squares (SOS) hierarchies for computing ex-ante optimal strategies in single-player IREFGs and Nash equilibria in multi-player IREFGs, working over behavioral strategies. Our theoretical results show that (i) these hierarchies converge asymptotically, (ii) under genericity assumptions, the convergence is finite, and (iii) in single-player non-absentminded IREFGs, convergence occurs at a finite level determined by the number of information sets. Finally, we introduce the new classes of (SOS)-concave and (SOS)-monotone IREFGs, and show that in the single-player setting the SOS hierarchy converges at the first level, enabling equilibrium computation with a single semidefinite program (SDP).

Many real-world decisions happen step by step, but people or AI systems may not remember everything that happened earlier. We study mathematical models for this situation, called imperfect-recall games, where an agent may forget past actions or information. However, finding good strategies in such games is usually very hard. We show that these games can be rewritten as polynomial optimization problems. This allows us to use sum-of-squares optimization, a mathematical method that can gradually approach the best possible solution. With this approach, we can compute good strategies for both single-agent and multi-agent decision problems. We also prove when the method is guaranteed to converge, and identify special cases where it becomes much simpler. These results provide a new mathematical foundation for reasoning about strategic decision making under limited memory. They may help future algorithms handle more realistic settings where agents cannot perfectly remember, store, or use all past information.