【论文笔记】policy-space response oracles (PSRO)

论文介绍

policy-space response oracles (PSRO)，论文链接：https://arxiv.org/pdf/1711.00832.pdf

这是一篇2017年发表的论文，属于多智能体强化学习领域和博弈论的交叉。
在了解这篇文章之前，需要先弄清楚NFSP这类自博弈的概念。这方面优质的文章不是很多，我的内容部分参考了：
https://zhuanlan.zhihu.com/p/521429175
https://zhuanlan.zhihu.com/p/500746290

之前读这篇论文一直感觉有些看不懂，误以为PSRO和NFSP那一系列非常不一样，是自己不太能学会的新方向。
在自己用类似RL+三脚猫self-play做了一个扑克AI算法后，再来重读文章就发现，其实很多地方的思想都是很朴素的，理解起来障碍也少了很多。

PSRO的主要贡献在于统一了自博弈、虚拟自博弈以及其他一些结合经验博弈的population-based方法的算法流程，并将这类算法从结构上划分成了元博弈求解、BR求解和策略池扩张这三个模块。

吐槽一句，InRL会对对手的策略过拟合，自己动手做了才深有感触。

PSRO

论文贴出的伪代码。Algorithm 1 维护了一个所有玩家策略的策略池。然后循环地选定玩家，然后从他的策略集中选择出一个策略，固定其它所有玩家此时的策略，然后不断地训练这个策略使得该策略成为一个在别的玩家策略不变的情况下、近似的best respond。然后将其加入策略集合中。

DO算法

Double Oracle算法目标在于解决一系列双人博弈，分别维护双方的策略池，并对对方的策略池中的所有策略做出最佳响应，加入新的算法池中。大致的算法框架如图。

这张动图很好的诠释了DO算法：

DO的执行流程和PSRO相比并无差异，只不过DO中所指最佳响应（BR）从动作变成了PSRO中的策略，我们完全可以认为DO算法即是PSRO算法的表格形式（tabular-form algorithm）。

DO算法在双人游戏中可以保证最终收敛到纳什均衡，但最坏的情况下需要遍历整个策略空间，无法处理复杂的非完美信息游戏。

PSRO文章定理A.1指出，在理想情况下，PSRO总能找到一个不存在于目前策略池中的新策略用于扩张策略池。也就是说，新的策略总是可以被扩展的，这保证了PSRO算法能够确保agent在不断地学习更优质的新策略。

Meta-Strategy Solvers

论文提出了一种新的策略求解器，projected replicator dynamics (PRD)，具体内容可以在附录A中看到。它可以被理解为一种指导策略探索的算法，个人理解起来，有点类似RD算法及神经网络梯度下降算法，用拟合的方式逼近meta-strategy的best response。

在这种策略选择方式下，league中的每一个policy都有相等的概率被选中。

另外，在生成NE策略的方法上，像FSP等方法，都是可行的。这也给之后的论文留下了很大的空间。

DCH

并行计算加速。感觉不是这篇文章的主要贡献。


在n个player的游戏中，使用并行的nK个进程，也就是说，每个进程独立地为n个玩家训练训练K种不同的策略（第0种策略可以认为是random策略）。在每个玩家训练第i层策略时（i<=K）,用到了所有其他玩家小于等于i层的策略。

所有策略更新后，统一保存。每次策略开始时，更新其它玩家的策略。因此可以计算得到，需求的总空间量级是固定的，为 O(n²K²)

joint-policy correlation

衡量过拟合的指标。感觉不是这篇文章的主要贡献。

算法本质上属于 InRL，容易出现某一个agent对另一个agent的策略过度适应的问题 (overfit)。为了量化这个问题，作者提出了JPC这一指标。

对于 symmetric two-player game，将之重复训练五次（随机初始化），最后能得到五组agent1和agent2的策略。将他们两两对打，最终能得到如下JPC矩阵，数值代表平均回报。

结论

实验说明：

• 在非完美信息游戏中，相比NFSP，PSRO、DCH可以减少策略生成的JPC，也就是meta-strategy能够大幅减少过拟合。
• 训练的代数越多，过拟合程度越高。
• 越是部分可观测的游戏、缺失的信息越多，就越容易过拟合。

总结

PSRO/DCH提供的普遍性可以被视为一种“对手/队友正则化”的形式。最初始的矩阵博弈是列举出双方所有能使用的纯策略，然后求解均衡点。而对于复杂的博弈，列举所有的策略显然不现实，那我们可以通过实验的方式不断生成新的策略，每生成一个新的策略就建模一个meta-game，在其中求解均衡点。

按照我现在的理解，PSRO主要是有三个比较重要的步骤：

1. 维护一个历史的策略池
2. meta-solver: 基于历史策略池，求解一个混合的历史策略，作为受限游戏的NE策略
3. BR: 学习一个新的针对NE策略的最佳回应，并加入历史策略池中

在PSRO之后，还有很多相关的论文在这个领域进行了进一步的改良，这部分论文就是接下来要阅读的目标了。

————————
2022-9-15 读了一些论文之后，回来补充：
PSRO 相关发展整理。部分参考：https://zhuanlan.zhihu.com/p/397611232。
补充了2019年后PSRO相关的重要工作。

• 博弈论基本框架：

  • NE：纳什均衡，博弈求解的目标。（1944）
  • FP：基于对手历史行为做BR就可以逐步达到NE。（1951）
  • WFP: 弱化版ε-BR，可以比BR差一点，要求ε随着时间趋于0。给神经网络、强化学习提供了支撑。（2000）
  • FSP：从normal form game 推广到了 extensive form game 中。（2015）
  • NFSP：开始使用深度神经网络框架。（2016）

• PSRO基本框架：

  • DO：为了提高自博弈计算效率的一种算法。（2003）
  • PSRO： 整合了DO和FSP的算法框架。（2017）
  • PSRO-rN：探索时使用种群。只和打得过的对手打。（2019）
  • Alpha-PSRO： Alpha rank + PSRO。（2019）

• Self-play 相关实践：

  • AlphaGo
  • 启发式 self-play
  • δFSP
  • PFSP: Prioritized FSP

PSRO最新进展