study
PSRO: Policy-space response oracles博弈论与 RL 算法结合
智能体间复杂的关系和智能体之间的影响让 MARL 变得极其复杂。这个时候，博弈论的引入就会让建模变得轻松很多，博弈论的引入让智能体在过去与环境打交道的基础上又学会了如何与其他智能体打交道。纳什均衡（Nash Equilibrium, NE）是指的游戏中的一个状态，在这个状态下，在其他玩家决策不变的情况下，如果任何一个玩家改变当下的决策，都无法得到更多的好处。如果所有人都把自己的决策告诉其他玩家，其他玩家都不会变更自己的方案，这时候就达到了 NE。它是在多个智能体中达成的一个不动点，对于其中任意一个智能体来说，无法通过采取其他的策略来获得更高的累积回报。纳什均衡不一定是全局最优，但它是在概率上最容易产生的结果，是在学习时较容易收敛到的状态，特别是如果当前智能体无法知道其他智能体将会采取怎样的策略。
多人一般和博弈，此时 minimax Q-learning 方法可扩展为 Nash Q-learning 方法。当每个智能体采用普通的 Q 学习方法，并且都采取贪心的方式、即最大化各自的 Q 值时，这样的方法容易收敛到纳什均衡策略。Nash Q-learning 方法可用于处理以纳什均衡为解的多智能体学习问题。它的目标是通过寻找每一个状态的纳什均衡点，从而在学习过程中基于纳什均衡策略来更新 Q 值。
Double Oracle Algorithm（DO Algo），这个算法将目标定为寻找当下阶段博弈的 NE。它使用深度神经网络进行函数逼近，迭代计算子游戏（阶段博弈）的收益矩阵（Gt）。在每个时间 t 处（每个阶段博弈），都会计算出符合 NE 的回应（c），并得到最优策略（π），然后添加新的策略来扩展 Gt 为 Gt + 1，继续重复上述过程。 在其他人选择的策略不变的情况下，能够最大化player i的payoff的策略，称之为best response
PSRO对 DO Algo 进行了泛化，策略将不再只能是单个动作，也可以是战术或者其它的 meta-solver。该算法首先抽样一个初始策略并计算效用函数，并初始化元策略（记录策略分布的函数），元游戏开始于一个单一的策略，并在每个 epoch 中添加策略（Oracle），这些策略将尽可能地响应其他玩家的元策略。对于每个 epoch、每个 player 和 episode，都需要基于每个 player 计算新的策略π和元策略，计算量大。 一个标准的游戏是一个元组(Π，U， n)其中n是玩家的数量，Π=(Π1 , · · · , Πn)是策略，U是所有参与人采取的每个联合策略的效用的收益表。
