提出首个不完全记忆决策问题基准，发现后悔匹配算法远超传统优化方法。
Decision Making under Imperfect Recall: Algorithms and Benchmarks
- 构建61个不完全记忆问题的基准，涵盖隐私与AI安全场景。
- 后悔匹配算法在61个实例中普遍优于投影梯度下降，性能提升数个数量级。
- 首次证明后悔匹配适用于大规模约束优化，适合强化学习与安全测试场景。
在博弈论中，不完全记忆决策问题模拟了代理遗忘过往信息的情形，涵盖如“失忆司机”和通信受限的团队博弈等场景。本文首次提出不完全记忆决策问题的基准套件，涵盖多种问题类型，包括涉及人工智能系统敏感信息获取的隐私问题，以及通过仿真测试实现的人工智能安全评估。我们基于该套件生成了61个问题实例，评估了不同算法在寻找一阶最优策略方面的表现。特别地，我们引入了一类用于非线性约束优化的后悔匹配（Regret Matching, RM）算法。这类无参数算法在求解大型双人零和博弈中已取得巨大成功，但此前在该领域之外研究甚少。关键发现是：RM算法在多数情况下显著优于常见的首阶优化器（如投影梯度下降），性能差距可达数个数量级。这首次确立了RM家族作为大规模约束优化的强大解决方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。