Decision Making under Imperfect Recall: Algorithms and Benchmarks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910024486354944 |
|---|---|
| author | Tewolde, Emanuel Zhang, Brian Hu Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent |
| author_facet | Tewolde, Emanuel Zhang, Brian Hu Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent |
| contents | In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15252 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Decision Making under Imperfect Recall: Algorithms and Benchmarks Tewolde, Emanuel Zhang, Brian Hu Anagnostides, Ioannis Sandholm, Tuomas Conitzer, Vincent Computer Science and Game Theory Artificial Intelligence Machine Learning 68Q25, 68T01, 68T05, 68T42, 90C23, 90C26, 90C30, 91A14, 91A18, 91A26, 91A27, 91A35, 91A68 I.2; J.4; F.2 In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems. |
| title | Decision Making under Imperfect Recall: Algorithms and Benchmarks |
| topic | Computer Science and Game Theory Artificial Intelligence Machine Learning 68Q25, 68T01, 68T05, 68T42, 90C23, 90C26, 90C30, 91A14, 91A18, 91A26, 91A27, 91A35, 91A68 I.2; J.4; F.2 |
| url | https://arxiv.org/abs/2602.15252 |