When Is a Game a Markov Decision Process? Correspondences Between Game Theory and Reinforcement Learning

📄 arXiv: 2610.41962v1 📥 PDF

作者: Eduardo C. Garrido-Merchán

分类: cs.GT, cs.LG

发布日期: 2026-10-30

💡 一句话要点

提出游戏理论与强化学习之间的定理对应关系

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 博弈论 强化学习 马尔可夫决策过程 纳什均衡 多智能体系统 策略优化 决策理论

📋 核心要点

  1. 现有的博弈论与强化学习文献在术语上存在分歧，导致理论之间的桥梁缺乏严谨性。
  2. 本文通过提供定理，明确了游戏与马尔可夫决策过程之间的三种对应关系，填补了理论空白。
  3. 对多种游戏类型及解概念的分析，揭示了强化学习与博弈论之间的深层联系，推动了两者的融合。

📝 摘要（中文）

强化学习与博弈论从不同角度描述相同的对象。博弈论关注战略互动的理性结果，而强化学习则关注代理如何通过经验达到这些结果。尽管两者在结构上相同，但使用的术语却各不相同。本文提供了定理，明确了游戏在三个不同意义上是马尔可夫决策过程，并对每种游戏类型进行了分析，识别出与强化学习相关的决策理论模型。此外，本文还探讨了不同解概念之间的对应关系，并记录了不成立的对应关系。

🔬 方法详解

问题定义：本文旨在解决博弈论与强化学习之间的术语不一致及理论桥梁缺乏的问题，现有方法多为类比而非定理。

核心思路：通过提供明确的定理，阐明游戏在不同意义上是马尔可夫决策过程，建立起博弈论与强化学习之间的严谨对应关系。

技术框架：研究涵盖了从标准形式游戏到重复博弈、随机博弈、部分可观察博弈等多种类型，并对每种类型的决策理论模型进行了识别与映射。

关键创新：提出了游戏与马尔可夫决策过程之间的三种对应关系，包括定义性身份、精确约简和结构类比，突破了以往的类比方法。

关键设计：对解概念如纳什均衡、贝尔曼最优性算子等进行了详细分析，记录了相应的训练程序及复杂性，确保理论与实践的紧密结合。

📊 实验亮点

通过对多种游戏类型的分析，本文揭示了强化学习与博弈论之间的深层联系，提供了新的理论视角，推动了两者的融合，具有重要的学术价值和实际应用潜力。

🎯 应用场景

该研究为博弈论与强化学习的结合提供了理论基础，潜在应用于多智能体系统、经济学模型及策略优化等领域，推动相关领域的研究与应用发展。

📄 摘要（原文）

Reinforcement learning and game theory describe the same object from two sides. Game theory says what a rational outcome of a strategic interaction is; reinforcement learning says how an agent could reach one through experience. The two literatures nevertheless keep separate vocabularies for identical structures, and the treatments that bridge them present the correspondence as analogy rather than theorem. This monograph supplies the theorems. A game is a Markov decision process in three distinct senses, and every table entry is labelled with the one that applies: a definitional identity, an exact reduction carried by a value- and solution-preserving map, or a structural analogy that fails under identifiable conditions. We take every standard class of game, from normal-form through repeated, stochastic, partially observable, extensive-form with imperfect information, Bayesian, graphical, Stackelberg, potential, coalitional, mean-field and evolutionary games, and identify for each the decision-theoretic model that reinforcement learning already studies under another name. The same treatment is applied to solution concepts: Nash equilibrium and the fixed point of the Bellman optimality operator, quantal response equilibrium and the soft Bellman operator, the Shapley value and credit assignment, Blackwell approachability and no-regret learning. We map each model class onto the training procedures sound for it and record the complexity of the associated solution problems. A final part collects the correspondences that do not hold: the non-stationarity that invalidates the independent-learner reduction, the impossibility results that forbid uncoupled convergence to Nash equilibrium, and the gap between the coarse correlated equilibria that no-regret self-play reaches and the correlated equilibria it is credited with.