[NIPS2017] A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning 笔记

admin管理员组

文章数量:1130349

文章目录

• 前言
• Background and Related Work
• • Neural Fictitious Self-Play
• Policy-Space Response Oracles
• • Meta-Strategy Solvers
  • Deep Cognitive Hierarchies
  • • Decoupled Meta-Strategy Solvers
• Experiments
• • Joint Policy Correlation in Independent Reinforcement Learning
  • Learning to Safely Exploit and Indirectly Model Opponents in Leduc Poker

前言

为了实现通用智能，agent需要学会在共享的环境中与彼此交互，这就是MARL的挑战。最简单的形式是independent reinforcement learning (InRL)，忽略其他agent，将交互当做（局部）环境的一部分，但在训练时往往会过拟合到其他人的策略，导致执行时不能有效泛化，观察越局部越严重。当然还包括局部环境非稳态和非马尔科夫性导致的难以保证收敛。作者引入了一个新的指标——joint-policy correlation（JPC），来量化这个影响。作者描述了一种针对一般MARL的算法——基于DRL产生的策略混合的近似最优反应，和为策略选择计算meta-strategies的经验博弈论分析——以及一种可扩展实现，使用解耦的meta-solvers来降低内存需求。CTDE的结构，主要是有集中的收益表。

https://arxiv/abs/1711.00832

Background and Related Work

一般式博弈是一个元组 ( Π , U , n ) (\Pi,U,n) (Π,U,n)，其中 n n n是玩家的数量， Π \Pi Π是策略集， U U U是效用的收益表。扩展式博弈将这种形式扩展到多步顺序情况。

玩家通过从 Π i \Pi_i Πi​中选择策略，或者根据分布 σ i \sigma_i σi​采样策略最大化期望效用。 σ i \sigma_i σi​的质量跟策略有关，因此不能被单独找到或评估。每个有限扩展式博弈都有等价的一般式博弈，但是指数级的更大，导致算法不得不直接解决序贯形式的。

有几种计算策略的算法。 在零和博弈中，可以使用例如 线性规划、fictitious play、replicator dynamics或悔恨最小化。其中一些技术已经扩展到扩展（顺序）形式，状态空间的大小呈指数增长。然而，这些扩展几乎只处理两人的情况，但有一些明显的例外。Fictitious play也收敛于包括合作（相同收益）游戏在内的潜在游戏。

double oracle (DO)算法解决一组两人、一般式的子博弈，在时间t由子集 Π t ⊂ Π \Pi_t\subset\Pi Πt​⊂Π得出。一个子博弈 G t G_t Gt​的收益矩阵只包含对应于 Π t \Pi_t Πt​中策略的项。在每个时间步 t t t，一个均衡 σ ∗ , t \sigma^{*,t} σ∗,t从子博弈 G t G_t Gt​中得到，并且为了得到 G t + 1 G_{t+1} Gt+1​，每个玩家添加一个来自完整空间 Π i \Pi_i Πi​的BR π i t + 1 \pi_i^{t+1} πit+1​，所以对于所有的玩家 i i i， Π i t + 1 = Π i t ∪ { π i t + 1 } \Pi_i^{t+1}=\Pi_i^t\cup\{\pi_i^{t+1}\} Πit+1​=Πit​∪{πit+1​}。在零和博弈中，需要 ∣ Π t ∣ |\Pi_t| ∣Πt​∣的多项式时间找到均衡，在一般和博弈中是PPAD-complete的（它们不是判定问题，纳什均衡点的存在性是有纳什定理直接保证的；它们也不是优化问题，因为没有一个优化的目标。从本质上讲，它们是一类不动点的计算问题，所以从传统的NP-Complete角度来研究他们的计算复杂度并不合适。但是否存在第二个均衡的问题是NP-Complete的）。

很明显，两人博弈中DO保证收到均衡，但是最差情况需要枚举整个策略空间，比如石头剪刀布。然而，有证据表明，许多博弈的支持大小会随着episode长度、隐藏信息揭示的多少和/或对收益的影响而缩小。已经开发了扩展式博弈的扩展，但由于维度灾难，大型状态空间仍然存在问题。

经验博弈论分析 (EGTA) 是对通过复杂博弈中的模拟获得的meta-strategies的研究。一个规模比完整博弈小得多的经验博弈是通过发现策略和对策略进行元推理以导航策略空间来构建的。当明确列举博弈策略的成本高得令人望而却步时，这是必要的。估计每个联合策略的期望效用并将其记录在经验收益表中。分析经验博弈，并继续模拟过程。EGTA 已被用于交易代理竞赛 (TAC) 和自动竞价拍卖。

作者的目标是通过学习发现新的策略，不是计算精确的BR，而是使用强化学习计算近似的BR，这在计算上更可行，fictitious play可以处理近似。考虑到有限理性的自然约束，它在生物学上也更合理。 在行为博弈论中，重点是预测人类采取的行动，并有意限制反应以提高预测能力。

Neural Fictitious Self-Play

许多现实应用可以看做大规模的非完美信息博弈，其是第一个不需要先验领域知识、端到端可扩展地学习近似纳什均衡的方法。虽然许多机器学习方法已经为经典的完美信息博弈实现了近乎最优的解决方案，但这些方法无法在不完美信息博弈中收敛。另一方面，许多用于寻找纳什均衡的博弈论方法缺乏学习抽象模式并使用它们来泛化到新情况的能力。

Neural Fictitious Self-Play (NFSP) 将 FSP 与神经网络函数逼近相结合。NFSP agent由两个神经网络组成。第一个网络是通过off-policy强化学习训练。该网络学习对其他agent的历史行为的近似最佳反应。第二个网络是通过从agent自身行为的记忆经验中进行监督学习来训练的。该网络学习了一个模型，对agent自己的历史策略进行了平均。agent根据其平均策略和最佳反应策略的混合来行动。

agent独立地同时在环境中行动， M R L M_{RL} MRL​中存transitions， M S L M_{SL} MSL​中存自己的最优反应行为。off-policy的RL算法，决定了近似最优反应策略 β \beta β。监督学习网络模仿自己过去的最优反应行为，多分类问题，得到平均策略 π = Π \pi=\Pi π=Π。根据两者的混合行动。

为了确保算法稳定和实现同时的self-play，作者有两个技术创新：首先，它使用蓄水池采样（只加入遵循最优反应的经验）来避免由于从有限记忆中采样而导致的窗口伪影。其次，它使用预期动态使每个agent都能够对自己的最优反应行为进行采样，并更有效地跟踪对手行为的变化。

NFSP agent定期训练其平均策略网络以匹配其存储在其监督学习记忆中的平均行为，例如通过优化过去采取的行动的log概率。

如果我们想要agent在交互的时候同时学习，会有一些两难。原则上每个agent可以执行平均策略 π \pi π，通过off-policy学习最优反应 β \beta β。然而这样agent就不能产生任何自己最优反应的经验，那就没法训练平均策略网络。

NFSP使用anticipatory dynamics的近似， β t + 1 i − π t i ≈ d d t π t i \beta_{t+1}^i-\pi_t^i\approx \frac{d}{dt}\pi_t^i βt+1i​−πti​≈dtd​πti​，梯度代表对未来的预测，用差来近似梯度。作者的混合策略是 σ = ( 1 − η ) π + η β \sigma=(1-\eta)\pi+\eta\beta σ=(1−η)π+ηβ，这样计算的就是对手预期平均策略 σ − i = π − i + η ( β − i − π − i ) \sigma^{-i}=\pi^{-i}+\eta(\beta^{-i}-\pi^{-i}) σ−i=π−i+η(β−i−π−i)的最优反应。此外，由于每个agent自己的最优反应策略现在按预期参数 η \eta η的比例进行采样，因此他们现在可以从该经验中训练他们的平均策略网络。

Policy-Space Response Oracles

PSRO是 Double Oracle 的自然泛化，其中元博弈的选择是策略而不是行动。它还概括了fictitious play。与以前的工作不同，可以插入任何meta-solver来计算新的meta-strategy。在实践中，参数化策略（函数逼近器）用于在不需要任何领域知识的情况下在状态空间中进行泛化。

元博弈被表示为经验博弈，从单个策略（均匀分布）开始，每个epoch通过增加新的策略（oracle）增长，策略是其余玩家的meta-strategy的近似最优反应。在情节式的局部可观察多智能体环境，当其他玩家固定了，环境就变成马尔科夫性了，计算一个最优反应变成求解某种形式的MDP，因此任意RL算法都能用。在每个episode，一个玩家被设为oracle（learning）模式训练策略 π i ′ \pi_i' πi′​，一个固定的策略从对手的meta-strategy中采样（ π − i ∼ σ − i \pi_{-i}\sim\sigma_{-i} π−i​∼σ−i​）。每个epoch的结尾，新的oracle被加入他们的策略集 Π i \Pi_i Πi​，新策略组合的期望效用通过仿真来计算，加入经验tensor U Π U^{\Pi} UΠ，时间复杂度 ∣ Π ∣ |\Pi| ∣Π∣的指数级。

定义 Π T = Π T − 1 ∪ π ′ \Pi^T=\Pi^{T-1}\cup\pi' ΠT=ΠT−1∪π′作为包含当前正在学习的oracle的策略空间，

• 迭代的最优反应是 σ − i = ( 0 , 0 , ⋯   , 1 , 0 ) \sigma_{-i}=(0,0,\cdots,1,0) σ−i​=(0,0,⋯,1,0)，
• InRL是 σ − i = ( 0 , 0 , ⋯   , 0 , 1 ) \sigma_{-i}=(0,0,\cdots,0,1) σ−i​=(0,0,⋯,0,1)，
• fictitious play是 σ − i = ( 1 / K , 1 / K , ⋯   , 1 / K , 0 ) \sigma_{-i}=(1/K,1/K,\cdots,1/K,0) σ−i​=(1/K,1/K,⋯,1/K,0)，
• DO是 n = 2 n=2 n=2， σ T \sigma^{T} σT是元博弈 ( Π T − 1 , U Π T − 1 ) (\Pi^{T-1},U^{\Pi^{T-1}}) (ΠT−1,UΠT−1)的纳什均衡

一个令人兴奋的问题是在这个已知空间之外的（非固定的）元求解器会发生什么？fictitious play与其所响应的策略无关；因此，它只能通过重复生成相同的最佳响应来锐化meta-strategy分布。另一方面，对由 Double Oracle 计算的均衡策略的响应将 (i) 在 n 玩家或一般和情况下过拟合特定均衡，以及 (ii) 无法推广到任何零和情况下的均衡策略未达到的空间部分。在计算在任何情况下都应该运行良好的一般策略时，这两种方法都是不可取的。作者试图通过折衷来平衡这些过拟合的问题：完全支持的meta-strategy，强制（mix in）策略选择的 γ \gamma γ探索。

Meta-Strategy Solvers

其输入经验博弈 ( Π , U Π ) (\Pi,U^{\Pi}) (Π,UΠ)，输出每个玩家 i i i的meta-strategy σ i \sigma_i σi​。作者尝试了三种：regret-matching, Hedge, 和 projected replicator dynamics。这些特定的元求解器为每个策略（“arm”）累积值，和一个根据所有玩家的meta-strategy的合计值。 u i ( σ ) u_i (\sigma) ui​(σ)是给定所有玩家meta-strategy的玩家 i i i的期望值， U Π U^{\Pi} UΠ是当前经验收益tensor（通过多个tensor点积计算）， u i ( π i , k , σ − i ) u_i(\pi_{i,k},\sigma_{-i}) ui​(πi,k​,σ−i​)是玩家 i i i执行kth策略其他玩家执行meta-strategy的期望效用。使用探索参数 γ \gamma γ，导致下界为 γ K + 1 \frac{\gamma}{K+1} K+1γ​的选择任意 π i , k \pi_{i,k} πi,k​的概率。类似bandit算法，下面会提到。

具体的内容这里不做讨论，可以参考附录A。

Deep Cognitive Hierarchies

虽然 PSRO 的泛化性明显且有吸引力，但 RL 步骤可能需要很长时间才能收敛到良好的反应。在复杂的环境中，很多在一个 epoch 中学到的基本行为在从头开始时可能需要重新学习；此外，可能需要运行多个 epoch 以获得可以通过更深层次的突发事件进行递归推理的 oracle 策略（it may be desirable to run many epochs to get oracle policies that can recursively reason through deeper levels of contingencies）。

为了克服这些问题，作者引入了一种实用的并行形式的 PSRO。作者提前选择了固定数量的levels，而不是无限数量的 epoch。然后，对于 n 人游戏，并行启动 nK 个进程（level 0 agent是均匀随机的）：每个为玩家 i i i和level k k k训练一个单独的oracle策略 π i , k \pi_{i,k} πi,k​，并更新自己的meta-strategy σ i , k \sigma_{i,k} σi,k​，定期将每个保存到中央磁盘。每个进程还维护当前和更低级别的所有其他oracle策略 π j , k ′ ≤ k \pi_{j,k'\le k} πj,k′≤k​的副本，以及当前级别的meta-strategy σ − i , k \sigma_{-i,k} σ−i,k​的副本，这些副本从中央磁盘定期刷新。我们通过在线更新meta-strategy来规避显式存储 U Π U^{\Pi} UΠ。作者将其称为深度认知层次结构 (DCH)，参考了 Camerer、Ho 和 Chong 用深度强化学习增强的模型。


由于每个进程使用稍微过时的其他进程的策略和meta-strategy，DCH近似PSRO。具体来说，它牺牲了与 PSRO 对应的准确性，以换取实际效率，尤其是可扩展性。DCH 的另一个好处是总空间复杂度的渐近减少。PSRO中，n个玩家K个策略需要存储经验收益tensor K n K^n Kn，DCH中的每个进程存储 n K nK nK个策略，n个meta-strategy，所以是 O ( n K ( n K + n K ) ) = O ( n 2 K 2 ) O(nK(nK+nK))=O(n^2K^2) O(nK(nK+nK))=O(n2K2)。或许是由于使用了解耦的meta-solver，在线计算策略，不需要收益tensor。

Decoupled Meta-Strategy Solvers

在在线学习领域，专家算法（“完全信息”条件）在每一轮都会收到有关每个arm的信息。在bandit（“部分信息”）情况下，仅对被拉动的arm给出反馈。解耦的元求解器本质上是应用于博弈的基于样本的对抗性bandit。由于folk定理，经验strategy在某些类型的博弈（即零和、potential博弈）中收敛到纳什均衡。

作者尝试了三种：解耦regret-matching、Exp3 (decoupled Hedge)和解耦 PRD。 γ \gamma γ概率混入均匀strategy，这个探索对于确保估计无偏是必要的。对于解耦 PRD，为整体平均值维护移动平均值作为每个arm（策略）的值（we maintain running averages for the overall average value an value of each arm (policy)）。与 PSRO 不同的是，在 DCH 的情况下，一次获取一个样本，并根据在线估计定期更新元策略。

Experiments

作者的oracle使用Reactor来学习，具体细节参考附录C，不是为了复现的话不太需要看。

Joint Policy Correlation in Independent Reinforcement Learning

首先介绍两人对称非负奖赏的博弈情况下，JPC矩阵。

值通过 D D D 个相同实验不同随机数种子的实例获得，经过很多episode后，每个实验 d d d产生策略 ( π 1 d , π 2 d ) (\pi_1^d,\pi_2^d) (π1d​,π2d​)。每个 D × D D\times D D×D矩阵的每一项是 T = 100 T=100 T=100个episode的均值 ∑ t = 1 T 1 T ( R 1 t + R 2 t ) \sum_{t=1}^T\frac{1}{T}(R_1^t+R_2^t) ∑t=1T​T1​(R1t​+R2t​)，因此对角线上的就是两个一起学习的策略的return，即相同的实例。对角线之外的是不同实例的策略的return。

令 D ˉ \bar{D} Dˉ是对角线的均值， O ˉ \bar{O} Oˉ是非对角线的均值，奖赏的average proportional loss为 R _ = ( D ˉ − O ˉ ) / D ˉ R_\_=(\bar{D}-\bar{O})/\bar{D} R_​=(Dˉ−Oˉ)/Dˉ。例如，上图左边的是 R _ = ( 30.44 − 20.03 ) / 30.44 = 0.342 R_\_=(30.44-20.03)/30.44=0.342 R_​=(30.44−20.03)/30.44=0.342。

对于任意奖赏的有限n player博弈，每个玩家 i i i有自己的效用 U i U_i Ui​，存在 d d d个独立的学习实例，那么 U i U_i Ui​就有 d n d^n dn维，每一项代表给定每个玩家每个实例后 i i i的期望效用。

对于4玩家5实例的博弈， U 4 [ 0 ] [ 3 ] [ 2 ] [ 2 ] U_4[0][3][2][2] U4​[0][3][2][2]代表玩家4给定玩家1、2、3、4分别使用实例0、3、2、2的效用。所以 D ˉ i \bar{D}_i Dˉi​就是 d d d个值的平均， O ˉ i \bar{O}_i Oˉi​是 d n − d d^n-d dn−d个值的平均。当n很大时，可以采样 O ( d ) O(d) O(d)项估计 O ˉ i \bar{O}_i Oˉi​。在非对称博弈中，JPC问题在玩家间不同，需要分别看每个玩家是怎么被影响的。

即使在具有几乎完全可观察性（small2）的简单领域中，尽管在相同的环境下训练，独立学习的策略在与另一个独立学习的策略一起玩时也可能会损失 34.2% 的奖励！在其他变体（收集和寻路）中没有观察到 JPC 问题，大概是因为不需要协作并且策略是独立的。当使用 DQN 作为 oracle 训练算法时，也存在类似的效果。

我们注意到一个（level 10）DCH agent 显著缓解了JPC问题。JPC问题随着地图变大和更局部可观察变大。

Is the Meta-Strategy Necessary During Execution? YES！

How Many Levels? 在small4，level 5的效果与10相似，3变差。

Learning to Safely Exploit and Indirectly Model Opponents in Leduc Poker

DCH（和 PSRO）在训练开始时比NFSP收敛得更快，这可能是由于比fictitious play中使用的均匀随机策略更好的meta-strategy。收敛曲线最终趋于平稳：双人博弈中 DCH 受到的影响最大，可能是由于更新的异步性质，而 NFSP 在后面的episode中收敛到较低的可利用性。作者认为这是因为 NFSP 能够在树的最下方状态学习更准确的混合平均策略，这在扑克中尤为重要，而 DCH 和 PSRO 在完整策略的顶部混合。

另一方面，我们看到 PSRO/DCH 能够在对抗固定玩家时获得更高的表现。 据推测，这是因为 PSRO/DCH 制定的策略能够更好地识别较弱对手策略中的缺陷，因为oracle是为此专门训练的，并动态适应episode中的利用性反应。因此，NFSP 在计算一个稳妥均衡，而 PSRO/DCH 可能在权衡收敛精度以获得适应训练期间观察到的一系列不同玩法的能力，在这种情况下计算一个鲁棒的反策略。

PSRO/DCH 提供的泛化性可以看作是“对手/队友正则化”的一种形式，最近在实践中也观察到了。作者强调这些技术的博弈论基础，希望这将激发对多智能体强化学习算法开发的进一步研究。

文章目录

• 前言
• Background and Related Work
• • Neural Fictitious Self-Play
• Policy-Space Response Oracles
• • Meta-Strategy Solvers
  • Deep Cognitive Hierarchies
  • • Decoupled Meta-Strategy Solvers
• Experiments
• • Joint Policy Correlation in Independent Reinforcement Learning
  • Learning to Safely Exploit and Indirectly Model Opponents in Leduc Poker

前言

为了实现通用智能，agent需要学会在共享的环境中与彼此交互，这就是MARL的挑战。最简单的形式是independent reinforcement learning (InRL)，忽略其他agent，将交互当做（局部）环境的一部分，但在训练时往往会过拟合到其他人的策略，导致执行时不能有效泛化，观察越局部越严重。当然还包括局部环境非稳态和非马尔科夫性导致的难以保证收敛。作者引入了一个新的指标——joint-policy correlation（JPC），来量化这个影响。作者描述了一种针对一般MARL的算法——基于DRL产生的策略混合的近似最优反应，和为策略选择计算meta-strategies的经验博弈论分析——以及一种可扩展实现，使用解耦的meta-solvers来降低内存需求。CTDE的结构，主要是有集中的收益表。

https://arxiv/abs/1711.00832

Background and Related Work

一般式博弈是一个元组 ( Π , U , n ) (\Pi,U,n) (Π,U,n)，其中 n n n是玩家的数量， Π \Pi Π是策略集， U U U是效用的收益表。扩展式博弈将这种形式扩展到多步顺序情况。

玩家通过从 Π i \Pi_i Πi​中选择策略，或者根据分布 σ i \sigma_i σi​采样策略最大化期望效用。 σ i \sigma_i σi​的质量跟策略有关，因此不能被单独找到或评估。每个有限扩展式博弈都有等价的一般式博弈，但是指数级的更大，导致算法不得不直接解决序贯形式的。

有几种计算策略的算法。 在零和博弈中，可以使用例如 线性规划、fictitious play、replicator dynamics或悔恨最小化。其中一些技术已经扩展到扩展（顺序）形式，状态空间的大小呈指数增长。然而，这些扩展几乎只处理两人的情况，但有一些明显的例外。Fictitious play也收敛于包括合作（相同收益）游戏在内的潜在游戏。

double oracle (DO)算法解决一组两人、一般式的子博弈，在时间t由子集 Π t ⊂ Π \Pi_t\subset\Pi Πt​⊂Π得出。一个子博弈 G t G_t Gt​的收益矩阵只包含对应于 Π t \Pi_t Πt​中策略的项。在每个时间步 t t t，一个均衡 σ ∗ , t \sigma^{*,t} σ∗,t从子博弈 G t G_t Gt​中得到，并且为了得到 G t + 1 G_{t+1} Gt+1​，每个玩家添加一个来自完整空间 Π i \Pi_i Πi​的BR π i t + 1 \pi_i^{t+1} πit+1​，所以对于所有的玩家 i i i， Π i t + 1 = Π i t ∪ { π i t + 1 } \Pi_i^{t+1}=\Pi_i^t\cup\{\pi_i^{t+1}\} Πit+1​=Πit​∪{πit+1​}。在零和博弈中，需要 ∣ Π t ∣ |\Pi_t| ∣Πt​∣的多项式时间找到均衡，在一般和博弈中是PPAD-complete的（它们不是判定问题，纳什均衡点的存在性是有纳什定理直接保证的；它们也不是优化问题，因为没有一个优化的目标。从本质上讲，它们是一类不动点的计算问题，所以从传统的NP-Complete角度来研究他们的计算复杂度并不合适。但是否存在第二个均衡的问题是NP-Complete的）。

很明显，两人博弈中DO保证收到均衡，但是最差情况需要枚举整个策略空间，比如石头剪刀布。然而，有证据表明，许多博弈的支持大小会随着episode长度、隐藏信息揭示的多少和/或对收益的影响而缩小。已经开发了扩展式博弈的扩展，但由于维度灾难，大型状态空间仍然存在问题。

经验博弈论分析 (EGTA) 是对通过复杂博弈中的模拟获得的meta-strategies的研究。一个规模比完整博弈小得多的经验博弈是通过发现策略和对策略进行元推理以导航策略空间来构建的。当明确列举博弈策略的成本高得令人望而却步时，这是必要的。估计每个联合策略的期望效用并将其记录在经验收益表中。分析经验博弈，并继续模拟过程。EGTA 已被用于交易代理竞赛 (TAC) 和自动竞价拍卖。

作者的目标是通过学习发现新的策略，不是计算精确的BR，而是使用强化学习计算近似的BR，这在计算上更可行，fictitious play可以处理近似。考虑到有限理性的自然约束，它在生物学上也更合理。 在行为博弈论中，重点是预测人类采取的行动，并有意限制反应以提高预测能力。

Neural Fictitious Self-Play

许多现实应用可以看做大规模的非完美信息博弈，其是第一个不需要先验领域知识、端到端可扩展地学习近似纳什均衡的方法。虽然许多机器学习方法已经为经典的完美信息博弈实现了近乎最优的解决方案，但这些方法无法在不完美信息博弈中收敛。另一方面，许多用于寻找纳什均衡的博弈论方法缺乏学习抽象模式并使用它们来泛化到新情况的能力。

Neural Fictitious Self-Play (NFSP) 将 FSP 与神经网络函数逼近相结合。NFSP agent由两个神经网络组成。第一个网络是通过off-policy强化学习训练。该网络学习对其他agent的历史行为的近似最佳反应。第二个网络是通过从agent自身行为的记忆经验中进行监督学习来训练的。该网络学习了一个模型，对agent自己的历史策略进行了平均。agent根据其平均策略和最佳反应策略的混合来行动。

agent独立地同时在环境中行动， M R L M_{RL} MRL​中存transitions， M S L M_{SL} MSL​中存自己的最优反应行为。off-policy的RL算法，决定了近似最优反应策略 β \beta β。监督学习网络模仿自己过去的最优反应行为，多分类问题，得到平均策略 π = Π \pi=\Pi π=Π。根据两者的混合行动。

为了确保算法稳定和实现同时的self-play，作者有两个技术创新：首先，它使用蓄水池采样（只加入遵循最优反应的经验）来避免由于从有限记忆中采样而导致的窗口伪影。其次，它使用预期动态使每个agent都能够对自己的最优反应行为进行采样，并更有效地跟踪对手行为的变化。

NFSP agent定期训练其平均策略网络以匹配其存储在其监督学习记忆中的平均行为，例如通过优化过去采取的行动的log概率。

如果我们想要agent在交互的时候同时学习，会有一些两难。原则上每个agent可以执行平均策略 π \pi π，通过off-policy学习最优反应 β \beta β。然而这样agent就不能产生任何自己最优反应的经验，那就没法训练平均策略网络。

NFSP使用anticipatory dynamics的近似， β t + 1 i − π t i ≈ d d t π t i \beta_{t+1}^i-\pi_t^i\approx \frac{d}{dt}\pi_t^i βt+1i​−πti​≈dtd​πti​，梯度代表对未来的预测，用差来近似梯度。作者的混合策略是 σ = ( 1 − η ) π + η β \sigma=(1-\eta)\pi+\eta\beta σ=(1−η)π+ηβ，这样计算的就是对手预期平均策略 σ − i = π − i + η ( β − i − π − i ) \sigma^{-i}=\pi^{-i}+\eta(\beta^{-i}-\pi^{-i}) σ−i=π−i+η(β−i−π−i)的最优反应。此外，由于每个agent自己的最优反应策略现在按预期参数 η \eta η的比例进行采样，因此他们现在可以从该经验中训练他们的平均策略网络。

Policy-Space Response Oracles

PSRO是 Double Oracle 的自然泛化，其中元博弈的选择是策略而不是行动。它还概括了fictitious play。与以前的工作不同，可以插入任何meta-solver来计算新的meta-strategy。在实践中，参数化策略（函数逼近器）用于在不需要任何领域知识的情况下在状态空间中进行泛化。

元博弈被表示为经验博弈，从单个策略（均匀分布）开始，每个epoch通过增加新的策略（oracle）增长，策略是其余玩家的meta-strategy的近似最优反应。在情节式的局部可观察多智能体环境，当其他玩家固定了，环境就变成马尔科夫性了，计算一个最优反应变成求解某种形式的MDP，因此任意RL算法都能用。在每个episode，一个玩家被设为oracle（learning）模式训练策略 π i ′ \pi_i' πi′​，一个固定的策略从对手的meta-strategy中采样（ π − i ∼ σ − i \pi_{-i}\sim\sigma_{-i} π−i​∼σ−i​）。每个epoch的结尾，新的oracle被加入他们的策略集 Π i \Pi_i Πi​，新策略组合的期望效用通过仿真来计算，加入经验tensor U Π U^{\Pi} UΠ，时间复杂度 ∣ Π ∣ |\Pi| ∣Π∣的指数级。

定义 Π T = Π T − 1 ∪ π ′ \Pi^T=\Pi^{T-1}\cup\pi' ΠT=ΠT−1∪π′作为包含当前正在学习的oracle的策略空间，

• 迭代的最优反应是 σ − i = ( 0 , 0 , ⋯   , 1 , 0 ) \sigma_{-i}=(0,0,\cdots,1,0) σ−i​=(0,0,⋯,1,0)，
• InRL是 σ − i = ( 0 , 0 , ⋯   , 0 , 1 ) \sigma_{-i}=(0,0,\cdots,0,1) σ−i​=(0,0,⋯,0,1)，
• fictitious play是 σ − i = ( 1 / K , 1 / K , ⋯   , 1 / K , 0 ) \sigma_{-i}=(1/K,1/K,\cdots,1/K,0) σ−i​=(1/K,1/K,⋯,1/K,0)，
• DO是 n = 2 n=2 n=2， σ T \sigma^{T} σT是元博弈 ( Π T − 1 , U Π T − 1 ) (\Pi^{T-1},U^{\Pi^{T-1}}) (ΠT−1,UΠT−1)的纳什均衡

一个令人兴奋的问题是在这个已知空间之外的（非固定的）元求解器会发生什么？fictitious play与其所响应的策略无关；因此，它只能通过重复生成相同的最佳响应来锐化meta-strategy分布。另一方面，对由 Double Oracle 计算的均衡策略的响应将 (i) 在 n 玩家或一般和情况下过拟合特定均衡，以及 (ii) 无法推广到任何零和情况下的均衡策略未达到的空间部分。在计算在任何情况下都应该运行良好的一般策略时，这两种方法都是不可取的。作者试图通过折衷来平衡这些过拟合的问题：完全支持的meta-strategy，强制（mix in）策略选择的 γ \gamma γ探索。

Meta-Strategy Solvers

其输入经验博弈 ( Π , U Π ) (\Pi,U^{\Pi}) (Π,UΠ)，输出每个玩家 i i i的meta-strategy σ i \sigma_i σi​。作者尝试了三种：regret-matching, Hedge, 和 projected replicator dynamics。这些特定的元求解器为每个策略（“arm”）累积值，和一个根据所有玩家的meta-strategy的合计值。 u i ( σ ) u_i (\sigma) ui​(σ)是给定所有玩家meta-strategy的玩家 i i i的期望值， U Π U^{\Pi} UΠ是当前经验收益tensor（通过多个tensor点积计算）， u i ( π i , k , σ − i ) u_i(\pi_{i,k},\sigma_{-i}) ui​(πi,k​,σ−i​)是玩家 i i i执行kth策略其他玩家执行meta-strategy的期望效用。使用探索参数 γ \gamma γ，导致下界为 γ K + 1 \frac{\gamma}{K+1} K+1γ​的选择任意 π i , k \pi_{i,k} πi,k​的概率。类似bandit算法，下面会提到。

具体的内容这里不做讨论，可以参考附录A。

Deep Cognitive Hierarchies

虽然 PSRO 的泛化性明显且有吸引力，但 RL 步骤可能需要很长时间才能收敛到良好的反应。在复杂的环境中，很多在一个 epoch 中学到的基本行为在从头开始时可能需要重新学习；此外，可能需要运行多个 epoch 以获得可以通过更深层次的突发事件进行递归推理的 oracle 策略（it may be desirable to run many epochs to get oracle policies that can recursively reason through deeper levels of contingencies）。

为了克服这些问题，作者引入了一种实用的并行形式的 PSRO。作者提前选择了固定数量的levels，而不是无限数量的 epoch。然后，对于 n 人游戏，并行启动 nK 个进程（level 0 agent是均匀随机的）：每个为玩家 i i i和level k k k训练一个单独的oracle策略 π i , k \pi_{i,k} πi,k​，并更新自己的meta-strategy σ i , k \sigma_{i,k} σi,k​，定期将每个保存到中央磁盘。每个进程还维护当前和更低级别的所有其他oracle策略 π j , k ′ ≤ k \pi_{j,k'\le k} πj,k′≤k​的副本，以及当前级别的meta-strategy σ − i , k \sigma_{-i,k} σ−i,k​的副本，这些副本从中央磁盘定期刷新。我们通过在线更新meta-strategy来规避显式存储 U Π U^{\Pi} UΠ。作者将其称为深度认知层次结构 (DCH)，参考了 Camerer、Ho 和 Chong 用深度强化学习增强的模型。


由于每个进程使用稍微过时的其他进程的策略和meta-strategy，DCH近似PSRO。具体来说，它牺牲了与 PSRO 对应的准确性，以换取实际效率，尤其是可扩展性。DCH 的另一个好处是总空间复杂度的渐近减少。PSRO中，n个玩家K个策略需要存储经验收益tensor K n K^n Kn，DCH中的每个进程存储 n K nK nK个策略，n个meta-strategy，所以是 O ( n K ( n K + n K ) ) = O ( n 2 K 2 ) O(nK(nK+nK))=O(n^2K^2) O(nK(nK+nK))=O(n2K2)。或许是由于使用了解耦的meta-solver，在线计算策略，不需要收益tensor。

Decoupled Meta-Strategy Solvers

在在线学习领域，专家算法（“完全信息”条件）在每一轮都会收到有关每个arm的信息。在bandit（“部分信息”）情况下，仅对被拉动的arm给出反馈。解耦的元求解器本质上是应用于博弈的基于样本的对抗性bandit。由于folk定理，经验strategy在某些类型的博弈（即零和、potential博弈）中收敛到纳什均衡。

作者尝试了三种：解耦regret-matching、Exp3 (decoupled Hedge)和解耦 PRD。 γ \gamma γ概率混入均匀strategy，这个探索对于确保估计无偏是必要的。对于解耦 PRD，为整体平均值维护移动平均值作为每个arm（策略）的值（we maintain running averages for the overall average value an value of each arm (policy)）。与 PSRO 不同的是，在 DCH 的情况下，一次获取一个样本，并根据在线估计定期更新元策略。

Experiments

作者的oracle使用Reactor来学习，具体细节参考附录C，不是为了复现的话不太需要看。

Joint Policy Correlation in Independent Reinforcement Learning

首先介绍两人对称非负奖赏的博弈情况下，JPC矩阵。

值通过 D D D 个相同实验不同随机数种子的实例获得，经过很多episode后，每个实验 d d d产生策略 ( π 1 d , π 2 d ) (\pi_1^d,\pi_2^d) (π1d​,π2d​)。每个 D × D D\times D D×D矩阵的每一项是 T = 100 T=100 T=100个episode的均值 ∑ t = 1 T 1 T ( R 1 t + R 2 t ) \sum_{t=1}^T\frac{1}{T}(R_1^t+R_2^t) ∑t=1T​T1​(R1t​+R2t​)，因此对角线上的就是两个一起学习的策略的return，即相同的实例。对角线之外的是不同实例的策略的return。

令 D ˉ \bar{D} Dˉ是对角线的均值， O ˉ \bar{O} Oˉ是非对角线的均值，奖赏的average proportional loss为 R _ = ( D ˉ − O ˉ ) / D ˉ R_\_=(\bar{D}-\bar{O})/\bar{D} R_​=(Dˉ−Oˉ)/Dˉ。例如，上图左边的是 R _ = ( 30.44 − 20.03 ) / 30.44 = 0.342 R_\_=(30.44-20.03)/30.44=0.342 R_​=(30.44−20.03)/30.44=0.342。

对于任意奖赏的有限n player博弈，每个玩家 i i i有自己的效用 U i U_i Ui​，存在 d d d个独立的学习实例，那么 U i U_i Ui​就有 d n d^n dn维，每一项代表给定每个玩家每个实例后 i i i的期望效用。

对于4玩家5实例的博弈， U 4 [ 0 ] [ 3 ] [ 2 ] [ 2 ] U_4[0][3][2][2] U4​[0][3][2][2]代表玩家4给定玩家1、2、3、4分别使用实例0、3、2、2的效用。所以 D ˉ i \bar{D}_i Dˉi​就是 d d d个值的平均， O ˉ i \bar{O}_i Oˉi​是 d n − d d^n-d dn−d个值的平均。当n很大时，可以采样 O ( d ) O(d) O(d)项估计 O ˉ i \bar{O}_i Oˉi​。在非对称博弈中，JPC问题在玩家间不同，需要分别看每个玩家是怎么被影响的。

即使在具有几乎完全可观察性（small2）的简单领域中，尽管在相同的环境下训练，独立学习的策略在与另一个独立学习的策略一起玩时也可能会损失 34.2% 的奖励！在其他变体（收集和寻路）中没有观察到 JPC 问题，大概是因为不需要协作并且策略是独立的。当使用 DQN 作为 oracle 训练算法时，也存在类似的效果。

我们注意到一个（level 10）DCH agent 显著缓解了JPC问题。JPC问题随着地图变大和更局部可观察变大。

Is the Meta-Strategy Necessary During Execution? YES！

How Many Levels? 在small4，level 5的效果与10相似，3变差。

Learning to Safely Exploit and Indirectly Model Opponents in Leduc Poker

DCH（和 PSRO）在训练开始时比NFSP收敛得更快，这可能是由于比fictitious play中使用的均匀随机策略更好的meta-strategy。收敛曲线最终趋于平稳：双人博弈中 DCH 受到的影响最大，可能是由于更新的异步性质，而 NFSP 在后面的episode中收敛到较低的可利用性。作者认为这是因为 NFSP 能够在树的最下方状态学习更准确的混合平均策略，这在扑克中尤为重要，而 DCH 和 PSRO 在完整策略的顶部混合。

另一方面，我们看到 PSRO/DCH 能够在对抗固定玩家时获得更高的表现。 据推测，这是因为 PSRO/DCH 制定的策略能够更好地识别较弱对手策略中的缺陷，因为oracle是为此专门训练的，并动态适应episode中的利用性反应。因此，NFSP 在计算一个稳妥均衡，而 PSRO/DCH 可能在权衡收敛精度以获得适应训练期间观察到的一系列不同玩法的能力，在这种情况下计算一个鲁棒的反策略。

PSRO/DCH 提供的泛化性可以看作是“对手/队友正则化”的一种形式，最近在实践中也观察到了。作者强调这些技术的博弈论基础，希望这将激发对多智能体强化学习算法开发的进一步研究。

本文标签： 笔记GAMETheoreticUnifiedReinforcement