纳什均衡的深度Q学习：纳什DQN

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Deep Q-Learning for Nash Equilibria: Nash-DQN》
---
作者：
Philippe Casgrain, Brian Ning, Sebastian Jaimungal
---
最新提交年份：
2019
---
英文摘要：
  Model-free learning for multi-agent stochastic games is an active area of research. Existing reinforcement learning algorithms, however, are often restricted to zero-sum games, and are applicable only in small state-action spaces or other simplified settings. Here, we develop a new data efficient Deep-Q-learning methodology for model-free learning of Nash equilibria for general-sum stochastic games. The algorithm uses a local linear-quadratic expansion of the stochastic game, which leads to analytically solvable optimal actions. The expansion is parametrized by deep neural networks to give it sufficient flexibility to learn the environment without the need to experience all state-action pairs. We study symmetry properties of the algorithm stemming from label-invariant stochastic games and as a proof of concept, apply our algorithm to learning optimal trading strategies in competitive electronic markets.
---
中文摘要：
多智能体随机博弈的无模型学习是一个活跃的研究领域。然而，现有的强化学习算法通常局限于零和博弈，并且仅适用于小状态动作空间或其他简化设置。在这里，我们开发了一种新的数据高效的深度Q学习方法，用于一般和随机博弈的纳什均衡的无模型学习。该算法使用随机博弈的局部线性二次展开，从而得到解析可解的最优行为。扩展通过深度神经网络进行参数化，使其具有足够的灵活性来学习环境，而无需经历所有状态-动作对。我们研究了源于标签不变随机博弈的算法的对称性，并将我们的算法应用于竞争电子市场中的最优交易策略学习，作为概念证明。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
PDF下载：
--> Deep_Q-Learning_for_Nash_Equilibria:_Nash-DQN.pdf (820.04 KB)

2022-6-14 13:41:05 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：纳什均衡 Applications Coordination Environments Quantitative

Nash均衡的深度Q学习：Nash DQNPhilippe Casgrain：，Brian Ning；，和Sebastian Jaimungal§摘要。多智能体随机博弈的无模型学习是一个活跃的研究领域。然而，现有的强化学习算法通常局限于零和博弈，并且仅适用于小状态动作空间或其他简化设置。在这里，我们开发了一种新的数据效率deep-Q-learning方法，用于一般和随机博弈的纳什均衡的无模型学习。该算法使用随机博弈的局部线性二次展开，从而得到分析可解的最优行为。扩展通过深度神经网络进行参数化，使其能够灵活地学习环境，而无需经历所有状态-动作对。我们研究了源于标签不变随机博弈的算法的对称性，并作为概念证明，将我们的算法应用于竞争电子市场中的最优交易策略学习。1、简介。在自然科学和社会科学中，对相互作用主体系统平衡的研究是普遍存在的。研究这些平衡方程的经典方法是建立相互作用系统的模型，求解其平衡，然后研究其性质。然而，这种方法往往会遇到复杂的情况，因为必须在（i）模型可跟踪性和（ii）捕获其旨在表示的数据主要特征的能力之间取得平衡。与其采用基于模型的方法，不如推导出非参数强化学习（RL）方法来研究这些平衡。

这些方法背后的主要思想是直接从模拟或观测数据中近似平衡，为常规方法提供了一种强有力的替代方法。关于RL的大多数现有文献都致力于单人游戏。大多数现代方法要么遵循深度Q学习方法（如[16]），要么遵循策略梯度方法（如[18]），要么遵循它们的混合方法（如[7]）。RL方法也被开发用于多智能体博弈，但大部分局限于零和博弈的情况。有关详细信息，请参见[1]。最近有一些研究将RL扩展到一般和博弈，如[9]所述，或者如[14]所述，使用迭代定点方法。在（离散状态行动空间）平均场博弈的特定背景下，[6]提供了求解纳什均衡的Q学习算法。现有的许多算法要么是由于游戏的规模和复杂性增加时的计算困难性，要么是由于状态-动作空间变得连续，要么是由于能够模拟复杂的游戏行为。Hu和Wellman[8]介绍了一种基于Q学习的方法来获得一般和随机博弈中的纳什均衡。虽然他们证明了有限游戏和动作空间的游戏算法的收敛性，但他们的方法在计算上不可行，除了SJ想感谢加拿大自然科学和工程研究委员会（NSERC）的支持，[资金参考号RGPIN-2018-05705和RGPAS-2018-522715]：加拿大多伦多大学统计科学系（p。casgrain@utoronto.ca).;加拿大多伦多大学统计科学系（brian。ning@mail.utoronto.ca).§加拿大多伦多大学统计科学系（塞巴斯蒂安。jaimungal@utoronto.ca, http://sebastian.statistics.utoronto.ca.)最简单的例子。

他们方法中的主要计算瓶颈是需要重复计算状态上的局部纳什均衡，这在一般情况下是一个NP难操作。此外，在[8]中提出的方法不适用于代理选择连续值控制的游戏，也不适用于具有高维游戏状态表示或具有大量玩家的游戏。相反，我们将[19，5]的iLQG框架和[8]的纳什Q-学习算法结合起来，生成了一种可以在这些更复杂和实际相关的环境中学习纳什均衡的算法。特别地，我们将状态动作值（Q）-函数分解为值函数和优势函数之和。我们使用神经网络近似值函数，并且我们局部地将代理行为中的优势函数近似为线性二次函数，系数是神经网络给出的特征的非线性函数。这使我们能够根据网络参数在特征空间中的每个点（即所有代理的最优操作）解析地计算纳什均衡。利用这种封闭形式的局部纳什均衡，我们导出了一种迭代的行动者-批评家算法来学习网络参数。原则上，我们的方法允许我们处理具有大量相同状态特征和较大动作空间的随机博弈。此外，我们的方法可以很容易地适用于平均场博弈（MFG）问题，这是由于某些随机博弈的有限人口限制（见[11、15、2]），如在[3、4]中开发的博弈，或主要次要代理FGS，如在[10、17、12]中研究的博弈。我们提出的方法的一个缺点是对所提出的Q函数逼近器的局部结构的限制。

然而，我们发现，所提出的近似值在大多数情况下都有很好的表达能力，并且在本文中的数值例子中表现良好。本文的其余部分结构如下。第二节介绍了一般和随机对策的一般马尔可夫模型。在第3节中，我们给出了随机博弈的最优性条件，并激励我们的Q-学习方法来寻找纳什均衡。4介绍了Q函数的局部线性二次近似和结果学习算法。我们还提供了一些标签不变博弈中出现的简化。第5节介绍了实现细节，第6节给出了一些示例。2、模型设置。我们考虑一个具有代理i P N的随机博弈：“t1，2，…，Nu都在一起竞争。我们假设博弈的状态通过随机过程txttpnso表示，对于每个时间t，xtP X，对于一些可分离的Banach空间X。在每个时间t，代理i选择一个动作ui，tP ui，其中ui被假定为可分离的Banach空间。在续集中，我们使用符号u\'i，t“puj，tqjPN{tiuto表示时间t时除agent-i以外的所有agent的动作向量，而符号ut“puj，tqjpn表示所有agent的动作向量。我们假设博弈是一个具有完全可见博弈状态的马尔可夫决策过程（MDP）。MDP假设等价于假设联合状态动作过程pxt，utqt“1是马尔可夫，其状态转移概率由平稳马尔可夫转移核ppxt ` 1 | xt、utq和初始状态分布ppxq定义。在游戏的每个步骤中，代理收到的奖励根据游戏的当前状态、他们自己选择的动作和所有其他代理的动作而变化。

agenti的奖励由函数px、ui、u'iqThniripx表示；ui，u'iq P R，以便在每个时间t，agent-i累积奖励ripxt；ui、t、u’i、tq。我们假设每个函数Ri在Ui中是连续可微且凹的，并且在x和u’i中是连续的。在每个时间t，agent-i可以观察其他agent的动作u’i，t，以及博弈xt的状态。此外，每个agent-i根据确定性Markovpolicy X Q XTh~nπipxq P Ui选择其动作。agent-i的目标是选择能够最大化目标函数Ri的政策π，该函数代表了他们在游戏剩余过程中的个人预期折扣未来回报，给定了他们自己的固定政策πIf和所有其他玩家的固定政策πIf。agent-i的目标函数为（2.1）Ripx；πi，π'iq“E<<"yt”0γ'tiripxt，πi，t，π'i，tq ff，其中期望值超过过程pxtqtPN，x“x”，其中我们假设γiP p0，1qis是表示贴现率的固定常数。在方程（2.1）中，我们使用压缩旋转πi，t：“πipxtq”和π'i，t：“π'ipxtq”。代理的目标函数（2.1）明确依赖于所有代理的策略选择。然而，每个代理只能控制自己的策略，并且必须在限制所有其他参与者行为的同时选择自己的行为。因此，Agent-i寻求一种优化其目标函数的策略，但对其他人的行为保持鲁棒性。最后代理人的政策形成纳什均衡——一组政策πpxq“tπipxquipn，这样单个代理人单方面偏离该均衡将导致该代理人的目标函数值下降。正式地说，如果（2.2），我们认为一组政策π形成纳什均衡Ri\'x；πi，πiRi\'x；πi，πi适用于所有可接受的保单πi，适用于所有保单N。

非正式地说，我们可以将纳什均衡解释为每个代理同时最大化自己的目标函数，同时又以其他代理的行动为条件的策略。3、最优性条件。我们的最终目标是获得一种算法，该算法可以在不事先了解其动力学的情况下实现博弈的纳什均衡。为了做到这一点，我们首先确定比上述aNash平衡的正式定义更容易验证的条件。我们继续扩展著名的纳什均衡Bellman方程。在去掉π'i fix的同时，我们可以将动态规划原理应用于代理——i rewardRipx；πi，πiq导致（3.1）Ripx；πi，πiq“maxuPUi”ripx，u，πipxqq`γiEx"pp | x，uq“ripx；πi，1，πi，1q‰*。在纳什均衡下，方程（3.1）同时满足所有i P N。为了更简洁地表达这一点，我们引入了向量表示法。首先定义向量值函数Rpx；πq“pRipx；πi，π'iqqiPN，由目标函数的叠加向量组成。我们将在纳什均衡点评估的叠加目标函数称为附加值函数，我们将其写为V pxq：“pVipxqqiN”Rpx；πq。接下来，我们定义纳什状态作用值函数，也称为q函数，其中表示Qpx；uq：“pQipx；ui，u'iqqiPN，其中（3.2）Qpx；uq“rpx；uq`γiEx"pp | x，uq”V pxq‰，其中我们表示rpx，uq：“pripx，ui，u'iqqipn，表示向量化的奖励函数。Q的每个元素都可以解释为其目标函数可能采取的预期最大值，给定固定的当前状态x和所有代理都可以执行的固定（任意）即时操作。接下来，我们定义Nash运算符如下。定义3.1（纳什算子）。考虑N个凹实值函数的集合，fpuq“pfipui，u'iqipn，其中fi:Ui'Su'i尼R。

我们将纳什算子NuPUfpuqTh~nfpuq定义为从函数集合到纳什均衡值uP RN的映射，其中，u“arg NuPUfpuq是唯一满足的点，fi`ωi，uifi` ui，ui，@ωiP ui，和@i P N.（3.3），对于函数f的高效正则集合，纳什算子对应于同时最大化其第一个参数ui中的每个fi。该定义为我们提供了值函数和代理的Qfunction之间的关系，如V pxq“NuPUQpx；uq。使用纳什算子，我们可以将Bellman方程（3.1）以简洁的形式表示为V pxq”NuPUQpx；uq“NuPU”rpx；uq`γiEx"pp¨x，uq“V pxq‰*，（3.4），我们在本文的其余部分将其称为Nash Bellman方程。值函数方程（3.4）的定义意味着π“NuPUQpx；uq。因此，为了确定纳什均衡π，有必要获得Q函数并对其应用纳什算子。这一原则将为我们在本文其余部分所采取的方法提供信息：与其通过方程（2.1）和（2.2）直接搜索纳什均衡的政策集合空间，我们可以依赖于确定满足纳什均衡的函数Q(3.4),计算π后“NuPUQpx；uq.4.局部线性二次Nash Q-学习。在本节中，我们制定了一种算法，用于学习前一节中描述的随机博弈的Nash均衡。我们采取的方法背后的主要思想是构造agent-i的Q-函数的参数估计量^Qθ，在这里我们搜索参数集θPΘ，从而得到估计量^Qθ近似满足纳什-贝尔曼方程（3.4）。因此，我们的目标是将数量（4.1）最小化，例如ρx、pp | x、uq<<>>>>Qθpx；uq'rpx；uq′γiNuPU^Qθpx；uq>>>>fff，在所有u中，我们将ρ定义为对游戏状态x的无条件可预测性度量。

方程式（4.1）设计用于测量方程式（3.4）左右两侧之间的间隙。我们也可以将其解释为^Qθ和Q的真实值之间的距离。表达式（4.1）很难理解，因为我们不知道ρ或pp¨x，uq a-priori，并且我们希望对系统动力学几乎没有假设。因此，我们采用基于模拟的方法，用（4.2）Lpθq“MM"ym”1近似（4.1^Qθpxm；umq'rpxm；umq'γiNumPU^Qθpxm；umq公司,其中，对于每个m“1，2，…，m，pxm，um；xmq表示从游戏中观察到的过渡三元组。然后，我们搜索使Lpθq最小化的θPΘ，以近似于^q。我们的方法是由Hu和Wellman【8】以及Todorov和Li【19】【8】提出的提出了一种Q-学习算法，其中可以通过依赖于Nashoperator NuPU^Qθ重复计算的更新规则来估计^Q，而^Q假设只取很多值。由于NuPU^Qθ的计算通常是NP困难的，因此这种方法证明除了平凡的例子之外，在计算上是难以处理的。为了避免这个问题并使用更具表现力的参数化模型，我们对Gu等人的技术进行了概括和调整。[5] 在多智能体博弈设置中，开发一种计算和数据高效的算法来近似纳什均衡。在我们的算法中，我们额外假设博弈状态x P x和actionsuiP ui是实值的。具体地说，我们假设每个i P N的X“rdxf或某个正整数dxandUi”rdi，其中d，…dn都是正整数。为了便于注释，我们定义d'i：“rjPN{tiudj。我们现在定义了一个用于收集近似Q函数的特定模型^Qθpx；uq”P^Qθipx；uqqiPN。

对于每个θPΘ，我们都有^Qθ：X'SU~nr，并将Q函数分解为两个分量：（4.3）^Qθpx；uq“^Vθpxq ` pAθpx；uq，其中^Vθpxq”p^Vθipxqqipn是一个值函数集合的模型，因此^Vθ：X~nRNand where pAθpx；uq“ppAθipx；uqqipn是我们所称的优势函数集合。优势函数代表了^Q和^V之间的最优差距。我们进一步假设，对于每个i p N，pAθih是线性二次型（4.4）pAθipx；uqqipn uq公司“\'^ui'uθipxqu'i'uθ'ipxq'124; Pθipxq'ui'uθipxqu'i'uθ'ipxq'729; `'u'i'uθ'ipxq'i'θipxq'i'ipxq'i'ipxq'i'ipxq'i'θipxq'i'ipxq''i'ipxq'i'θipxq'i 9；，uθipxq:X~nRdiwithuθ'ipxq“PuθipxqqiPN，ψi:X~nRd'i.In（4.5），Pθ11，i:XИRdi^di，Pθ12，i:XИRdi^d'i，Pθ21，i:XИRd'i^dian和Pθ22，i:XИRd'i^d'iare矩阵值函数，对于每个i P N，我们要求Pθ11，ipxq对于所有X P X为正定义，在不丧失一般性的情况下，我们可以选择P12，ipxq“pP21，ipxqq |，因为优势函数仅取决于P12，i和P21，i的对称组合。我们的方法可以很容易地扩展到控制限于Rdi的凸子集的情况。因此，我们不是建模^Qθpx；uq，而是将函数^Vθ，uθ和tpθi，ψθi分别建模为状态空间X的函数。这些函数中的每一个都可以由univ其他函数逼近器，如神经网络。唯一的主要限制是，Pθ11，ipxq必须保持x的正定义函数。通过使用Cholesky分解Pθ11，ipxq，可以很容易地实现这一限制，因此我们将θ11，ipxq“Lθ11，ipxqpLθ11，ipxqq |并对下三角矩阵Lθ11，iP Rdi^di进行建模。在（4.4）中的模型假设隐含地假设agent-i的Q函数可以近似地写成每个agent动作的线性二次函数。