Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games

一个以贝叶斯方式行事的参与者，在无限进行的多人博弈中，如果其先验信念对其他玩家的策略赋予了正的概率（或包含了一粒真理），那么他能够学会预测其他玩家的策略。Kalai 和 Lehrer 提出的经典“一粒真理”问题，是要找出一个相当大的策略类，使得相对于此类的贝叶斯最优策略都包含在其中，从而允许关于策略选择的相互一致的信念，并且这些信念遵循贝叶斯推理的规则。目前已知只有很小的策略类满足“一粒真理”的要求，文献中还存在多个相关的不可能性结果。本文中，我们给出了完整“一粒真理”问题的一个形式化且通用的解决方案：我们构造了一个足够广泛的策略类，它不仅包含了所有可计算的策略，还包含了针对该类中每一个合理先验的贝叶斯最优策略。当“环境”是一个已知的重复阶段博弈时，我们证明了以 [KL93a] 和 [KL93b] 中定义的方式收敛。当环境未知时，使用汤普森抽样（Thompson sampling）的智能体将在任意未知且可计算的多智能体环境中收敛于近似纳什均衡（$\varepsilon$-Nash equilibrium）。最后，我们还提供了一个在自我预测策略上的应用，这种策略可以避免复杂的规划。虽然这些结果仅将可计算性理论作为一种概念工具来解决经典的博弈论问题，但我们证明了我们的解决方案可以被任意逼近地进行计算近似。

这篇论文旨在解决经典的“grain of truth”问题，即在一个无限多玩家博弈中，如何构建一个足够广泛的策略类，使得贝叶斯最优策略能够在这个策略类中存在，并且不同玩家之间的信念能够相互一致地收敛。这个问题最早由Kalai和Lehrer提出，长期以来只有较小的策略类被证明满足grain of truth条件，而这篇论文试图构造一个足够大的策略类来解决这一问题。

论文的核心思想是构建一个包含所有可计算策略以及每个合理先验下的贝叶斯最优策略的策略类，并证明在已知重复博弈环境中，这种策略类可以实现信念收敛到Kalai-Lehrer意义下的均衡；而在未知环境中，使用Thompson抽样的智能体可以收敛到ε-纳什均衡。这一思路首次在理论上完整地解决了grain of truth问题，并将可计算性理论作为工具引入博弈论。

1. 提出了一种通用的策略类构造方法，适用于任意未知的可计算多智能体环境。 2. 在已知重复阶段博弈中，证明了信念收敛到Kalai-Lehrer意义下的均衡。 3. 在未知环境中，使用Thompson抽样策略能够收敛到ε-纳什均衡。 4. 引入了自预测策略（self-predictive policies），避免了复杂的规划过程。 5. 虽然依赖可计算性理论，但结果可以被任意逼近，具有潜在的实现可能性。

1. Kalai, E., & Lehrer, E. (1993). Rational learning leads to Nash equilibrium. 2. Hutter, M. (2005). Universal Artificial Intelligence. 3. Ortega, P. A., & Braun, D. A. (2010). A Bayesian rule for adaptive control based on causal interventions. 4. Leike, J., et al. (2016). Thompson Sampling is Asymptotically Optimal in General Environments. 5. Veness, J., et al. (2015). On the computability of AIXI.