博弈论与强化学习の期中复习

, , Comments

对不起，学得很失败，基础知识没掌握，没有理解公式，没有掌握思想，没有深入内核。

博弈论Restart：

有一说一的感觉就是政管的那门通识课讲到的内容可能还是少了点，这门课我还是没咋听懂就是说，以前还退过一门算法博弈论，那门课根本不敢学笑死。

ok，假设大家已经被科普过了解了什么是博弈论，

彻底躺平的一学期与最后一周的博弈论 | emoairx

合作博弈、非合作博弈；完全信息、不完全信息；静态博弈、动态博弈

每个参与者对自己的行为，其它参与者的行为都是有预期的，根据预期做出合乎理性的行动。

我们还是从最简单的地方开始回顾。完全信息静态博弈，什么是完全呢。

完全信息：每一参与者的策略集和收益函数均为共同知识。

后面会说到完美信息并不是完全信息，完美信息大概是说历史上的事件都被记录了下来。

Nash equilibrium

根据定义，就是有一个策略组合，对于任何一个人要大于等于它改变的情况下收益函数。形式化为

这里可能要记一下下标 $-i$ 应该可以用来表示对手策略。

Support：因变量是一个策略，返回那些概率大于零的部分。

最佳应对引理的结论是，for any nash equilibrum，对于一个人来说，支撑集的每一个纯策略都是一个best response.

于是就引出一些求解方法

求解nash均衡

  1. 两人有限博弈的均衡计算 - 知乎 (zhihu.com)

  2. 支撑法求解，构造除所有混合策略的支撑之后根据best response来解方程。

    枚举支撑法的问题包括（解不存在，不满足非负性条件，存在支撑策略小于非支撑策略期望收益的情况）

  3. 规划求解法（比如双人博弈），有四个，一是在均衡下参与人1采用任何纯策略都不高于均衡收益；二是和为一；三是大于等于零；四是最大化收益减均衡收益。

Lemke-Howson
  • 把所有小于等于变成等于，利用松弛变量。
    • 如果一个action存在，即 $x^j>0$，那么一定有它是关于对手策略的 best response，也即 $r^j=0$。
  • 把原约束 $x^TB\le u\cdot 1,1^Tx=1$ 变成约束 $x^T\bar B \le 1$，通过某种矩阵的映射。
  • 于是说在这个约束可行解的多面体里，每个纯策略要么概率是零，要么就是对手策略的best response.
    • 那么对于每一个综合了双方的action，考虑它满足的条件的数量，就要尽可能满足所有这些条件都要满足。定义这些条件为标签，一个点 $x$ 满足的标签的集合为 $L(x)$
  • 于是转而得出，如果 $(x,y)$ 是一个Nash equilibrium，就有 $L(x)\cup L(y)=M+N$，定义这个性质叫做完备的。
    • 注意 $L(x)={i\mid x_i=0} \cup {j\mid (x^TB)_j=1}$
    • 所以两个图其实是相互的，有了 $y$ 才可能判断前 $n$ 个点是否满足要么是best response要么是等于零。
  • 定义一张图，图上两个点右边如果这两个点在符合条件的多面体上是相邻的。有一些点是完备的，零点和Nash均衡点。
  • 关于一个性质（标签）$k$，定义这张图的一个子图 $U_k$，那些要么只缺少标签 $k$，要么什么标签都不缺少。完备的点在这张图上的度为1，其余（可达）的点度为2。
    • lecture4.pdf (stanford.edu) 的 theorem4
    • 对于零这个点来说，只可能把标签换成选一个元素；对于nash均衡来说，也只可能舍弃掉 $k$ 这个位置。
    • 对于其它的一般的点，因为我们选的一定是顶点，所以总的可重集的大小是 $N+M$ 的，也就是说一定有一个重复的部分为 $l$。在两张图的地方分别舍弃 $l$ 就能到达两个地方。
  • 算法的过程是：不断地舍弃掉那些度为2的点，每次drop一个，pick一个。
    • Traversing the whole graph G to add missing labels and drop duplicate labels (i.e. pivoting) until we find one set of nodes that are fully labelled.
    • Guarantee to find one Nash, but not all of them! Determining whether all Nash are found is not even NP.
    • Exponential time complexity because G has the number of vertices that is exponential in $n,m$ (combinatorial many)
    • Because LCP has no objective, we cannot tell the progress before finding a solution.
    • Corollary: almost all games have an odd number of Nash equilibrium.
  • Algorithm：
    • Choose $k \in M \cup N$
    • Start with $(x,y) = (0,0) \in G$, Drop label $k$ from $(x,y)$.
    • Let $(x,y)$ be the current vertex. Let $l$ be the label that is picked up by dropping label $k$, just drop $l$ in other polytope and repeat until find the nash equilibirum.
零和博弈

  • 定义博弈的值是一个常数 $v$，在参与人1在均衡中得到的期望收益。

  • 如果博弈的值大于零，那么纳什均衡就是一个对偶线性规划的解：

  • 其中 $v=\frac{1}{\sum_{}p_i}$，这个问题的对偶问题就是一个对手（玩家2）要最大化收益。其中最终的概率是归一化后的这个。

对于nash均衡的求解，当参与人数大于2时，没有得到很好的解决，很多都是非线性的。

nash均衡存在性

  • 其实可以参考 纳什均衡的存在性证明 - 知乎 (zhihu.com)

  • Sperner’s Lemma ：按照某种情况染色，只可能有奇数个顶点颜色不同的三角形。

    • 其实比较好理解，就是每个点都染色之后，只能走红黄的边。那么除了最最下角的起点以外，它能恰好走到一个三个点不同色的三角形，其它都是一系列的三角形走到三角形。

  • 然后是关于推广的，Brouwer’s lemma：对于 $X \to X$ 的连续函数存在不动点。107

    • https://www.bilibili.com/video/BV1Ap4y1D71s
    • 具体方法是，首先构造一个平面，然后对于 $R^3$ 中的点，设 $f(x)=y$
    • 那么根据 $\min_i y_i<x_i$ 的那个 $i$ 来给点染色，从而出现三种颜色。（其实依然不是很理解）。也就是其实在这个定义域（一个单纯性）内，我是能找到一个不动点的。然后后来我们又把结论扩展了。

  • 然后用这个lemma来证明nash均衡的存在性，其实就是考虑怎么构造出这样一个函数，这个函数是一个映射。直观地理解是这个函数应该是一个best response相关的，因为nash均衡具有best response不变性。

  • 所以我们考虑所有策略 $k$，定义参与人改变策略的倾向为

    具体而言是如果参与人 $i$ 采取了纯策略 $s_{ik}$ 后的收益比现在的策略大多少。

    $f(\sigma)=\sigma’$，其中

    直观地理解，方法就是当前策略为 $\sigma$，那么我对这个点我可以得到一个各个方向的best response的归一化。总之存在一个 $f$ 不变的地方。也就是基本上都有奇数个nash均衡。

Nash逼近

  • 但注意到我们只是说明了存在性。所以其实要求解这个逼近有两种方法
  • 一种是weak的，具体是 $||F(x’)-x’|| < \epsilon$，一种是strong的，为 $||x’-x^*|| < \epsilon$

后面引出了一个复杂度类称之为PPAD，关于二人博弈，四人以上博弈，多人一般和随机博弈，nash均衡的计算式PPAD-Complete的。

PPAD

  • polynomial parity arguments on directed graphs，有向图的多项式校验参数

  • 计算纳什均衡本质是一个搜索的问题，需要新的复杂度理论来 刻画，也就是FNP类

    TFNP是FNP的子类，表示问题一定有解。PPA是TFNP的子类， 表示无向图问题，+d表示有向图，就是PPAD。

    Nash → Brouwer → Sperner → End of Line → Nash 可以规约

  • 一类PPAD完全的问题是：End of The Line，大概是每个点都有一个唯一的出度，但是要从起始点开始找到一个结束的无出度的点。不过没搞懂这里的问题规模是什么。

nash均衡的多重性

  • 有时候有多个nash均衡的解，比如多个纯均衡的解。一般的解决思路有两种

    • 均衡精炼：剔除不合理的均衡，如子博弈精炼那什均衡，精炼贝叶斯nash均衡等
    • 非规范式方法：焦点效应、廉价磋商、相关均衡。

  • 焦点效应：考虑一些被模型所抽象掉的信息

    • 廉价磋商的一种定义可能是，根据对手提出的建议选择接受或者不接受，并在这种setting下找到新的nash均衡。带有沟通过程

  • 相关均衡：

    • 再引入一个随机变量，假设有 $m$ 种取值，双方对该随机变量不同取值下的反应不同，最终得到一个相关的矩阵，如果是两个人的话，这个矩阵是三维的，这里双方的策略有 $k^m$ 种，长度为 $m$。
    • 所谓的相关均衡，就是在各种概率的取值的情况下，期望上的收益最终能达到的nash均衡。双方收到的信号可以相关但是不同。

扩展式博弈

  • 大概就是引入了一个信息集的概念，一个人是否知道在哪个节点上，于是所有参与者在每个信息集上的行动 $A_i(I_i)$ 的笛卡尔积 $S_i$ 表示 参与人的策略集。静态博弈也可以扩展式表示。

  • 在之前的通识课里我们已经知道了子博弈精炼纳什均衡（剔除一些不合理的nash均衡）及其求解（和动态规划差不多），我们这里重点关注子博弈精炼纳什均衡的合理性与唯一性。

  • Kuhn定理：在perfect recall的前提下，每一个混合策略都有一个行为策略和他等价。

  • 不仅要求在博弈达到的路径上参与人的选择最优，而且要求在博弈没有达到的路径上参与人的选择也要最优。

  • 关于合理性，虽然逆向归纳法在逻辑上是合理的，但是在蜈蚣博弈等情形下往往与常识相违背。

  • 关于唯一性，如果不存在一个人在某个决策节点时其不同选择对自己的收益是无差异的，那么就是唯一的子博弈精炼nash均衡。

贝叶斯博弈
  • 贝叶斯的意思我理解成就是根据观测和先验概率，得到后验概率。
  • 对于存在非完全信息的情况，设置一个自然的存在（海萨尼转换），所有参与者关于自然的行动的信念是相同的，且为共同知识。
  • 在这个转换中有一个很有意思的点：参与人对包括自己在内的所有参与人的类型的联合概率推断(分布)都是一样的，但由于参与人掌握的私人信息不同，使得各自对其他参与人的类型的概率分布的推断不同。从贝叶斯公式可以看出来是这样的。
  • 那么贝叶斯博弈要求最关键的要素是：
    • 参与人的集合
    • 参与人的类型集
    • 参与人关于其它参与人的类型的推断
    • 参与人类型集相应的行动集
    • 参与人类型集相应的收益函数
  • 通过海萨尼转换后，得到了一个信息完全但非完美的动态博弈问题，则由于对自然的概率有一致的判断，则根据这个概率能得到均衡。
贝叶斯博弈

这里我没看懂

合作博弈

  • 合作博弈就是说可以有一些人一起合作然后分钱，主要考虑参与人之间能达成的可实施(enforceable)的协议。强调集体理性。在这种情况下，合作是博弈规则的一部分，而非博弈的结果。
  • 因为可实施，合作后收益增加的部分叫做合作剩余(cooperative surplus)
  • 特征函数：$V:2^N \to R$，通过合作取得的联盟总体收益水平。
    • 超加性：对于任意独立的 $S,T$ , $V(S\cup T) \ge V(S)+V(T)$（否则联盟会解散）
    • 单调性：联盟越大，合作所获越大；$V(S)\le V(T)$ 如果 $S \subseteq T$
  • 合作博弈是本质(essential)的如果存在有净增收益的联盟。
  • 构建联盟通过核，分配利益可以用夏普利值。
优超
  • 有两个联盟 $N,S$，两个条件，第一个是 $S$ 这个联盟内的成员觉得他们一起搞，$x$ 这个分配效果会比 $y$ 这个分配好，第二条条件是 $S$ 这个联盟的总收益比他们原来在 $N$ 这个联盟的分配收益更高（那么他们就有可信的威胁来不达成联盟）
  • 换言之，对于可转移效用情形的合作博弈，一种分配被优超就是联盟的子联盟的收益总和大于分配给他们的总收益。定义 核 为所有不被优超的分配构成的集合。

  • 核是一个闭凸集，满足以下两个条件

    • $\sum x_i=V(N)$
    • $\sum _{i \in S} x_i \ge V(S);\forall S$

  • 常和合作博弈的核是空的。

  • 在简单博弈中(01)，核非空的充分必要条件是存在否决权的人.

核关注的是分配的稳定性（而且要求太高，很多博弈没有核解），公平性用夏普利值

参与人恰好排在第 $t$ 个位置的期望收益。

随机博弈

带有随机性的博弈，就好比RL里出现了一点环境的随机性。

这部分有点复杂，这里写得很简略

Fictitious Play
  • 根据对方的历史策略出的比例当成对方的概率。
  • 玩家的策略最终收敛到一个稳定状态，这个稳定状态不一定是一个混合策略均衡。在实际游戏中，玩家可能不会完美地执行混合策略，或者他们可能会由于某些原因（如误解对手的意图或对自己的策略过于自信）而偏离理想的混合策略。
Stochastic Games
  • 定义在马尔可夫序列上的一个游戏，每个状态 $S$ 下有一个动作空间 $A$
  • n个人的话，$\mathcal A = A^1\times A^2 \times A^3 … \times A^n$
  • 关于矩阵游戏与强化学习：矩阵游戏和纳什均衡学习者更侧重于找到或收敛到一个策略，使得没有玩家有动力单方面改变策略。而强化学习和最佳响应学习者则更关注于通过不断的学习和调整策略来最大化个体收益，不一定追求均衡状态。

为此关于Equilibrium Learners我们介绍三种算法

Nash-Q

minimax-Q

Friend-or-Foe-Q

强化学习基础

关于MDP等基础此处不提，值得关注的是为什么MDP是对的，也就是为什么可以可以给出马尔可夫的假设。

这里面需要用到两个概念，第一个叫做占用度量。

具体而言，我们得到的是

我们假设策略是平稳策略，不依赖于时间，不依赖于历史的，但是我们好像没有仔细思考过为什么可以这么假设。

如果有了占用度量，那么我们应该是和时间无关的。

此处未严格考量

分割线

强化学习算法大致分成两类，值迭代和策略迭代，现代强化学习会把两者都结合起来，最早发展的是值迭代，一般认为基于bellman迭代式，方差较小，而reinforce算法是一种最基础的策略迭代……这应该没人不会了

时序差分

最简单的是 TD 学习方法

累计奖励（一般用于蒙特卡洛）$Gt=R{t+1}+\gamma R_{t+2}+…+\gamma^{T-1}R_T$ 是 $V^\pi(S_t)$ 的无偏估计

时序差分的真实目标 $R{t+1}+V^\pi(S{t+1})$ 是无偏估计。

时序差分的目标 $R{t+1}+V(S{t+1})$ 则是有偏估计。（但是它方差小啊）

MC TD DP
无偏估计，高方差 低方差，有偏差 你不知道未来
良好的收敛性质 • 使用函数近似时依然如此 时序差分最终收敛到但使用函数近似并不总是如此 你不知道未来
对初始值不敏感 比蒙特卡洛对初始值更加敏感 你不知道未来

value->policy：在上面这个迭代方法中，我们能得到value，只需要再加上小小的一点点就能得到policy，即argmax.

所以学Q也是可以的，Q就是多了一步

一个叫SARSA的算法的Q公式是这样的：

SARSA是在线的，因为在这之后它就需要根据Q继续采样，它的采样策略称为 $\epsilon$-greedy，一定概率随机探索，一定概率取best action

如果考虑离线的学习方法，可以把SARSA改一改，就是在update的时候取的 $a’$ 因为不能探索所以只是通过argmax得到，这就是我们熟知的Q-learning。

TD(λ)：很显然我们只通过一步迭代可能会有点方差还是大了一点，在实践中往往用多步时序差分，定义

就是用平均 $n$ 步累计奖励来做，TD(λ)可以用类似dp的方法倒推求，后面写GAE的时候再补充这里，为什么要求均值，因为方差会减小。

所以TD lambda这里就是利用 $G_{t}^\lambda$ 来更新其值函数。下面有一些新的概念

【Typical RL 13】GAE - 知乎 (zhihu.com)

定义 $\lambda $ Return就是 $G_t^{\lambda}-V(S_t)$，经过一些推导可以发现

其中

回到这里，我们思考一下会发现 $\lambda$ 越大，就越像TD，越小就越像MC。

回到上文，这里引出一个概念就是 $A(s,t)=Q(s,t)-V(s)$，对于策略梯度来说 $A$ 是无偏估计，因为 $V$ 与 $\pi$ 无关，求导后是零。

可以用TD-error作为Advantage函数的估计量。

人们后来又发现 GAE 也可以就是 $\lambda$ Return的方法加权求和，所以用 GAE 来估计 advantage function是很恰当的事情。

ray.rllib.evaluation.postprocessing — Ray v0.9.0.dev0 (anyscale-ray-doc-assets.s3-us-west-2.amazonaws.com)

关于怎么求GAE，Eligibility Traces可以用，直接看代码很好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def compute_advantages(rewards, next_done, dones, values, last_value, args):
    advantages = torch.zeros_like(rewards).to(args.device)
    lastgaelam = 0
    for t in reversed(range(args.num_steps)):
        if t == args.num_steps - 1:
            nextnonterminal = 1.0 - next_done
            nextvalues = last_value
        else:
            nextnonterminal = 1.0 - dones[t + 1]
            nextvalues = values[t + 1]
        delta = rewards[t] + args.gamma * nextvalues * nextnonterminal - values[t]
        advantages[t] = lastgaelam = delta + args.gamma * args.gae_lambda * nextnonterminal * lastgaelam
    return advantages

第一行就是初始化一个gae，然后根据step倒着来，中间大概是说如果是路径结束可以是得到的准确值，否则就是V这个估计值。

注意看先求出了delta，然后计算了advantage的衰减，至于我这里其实计算了好多组advantage，是不同起点出发的路径。

同样的，我们可以用 神经网络 来充当这个Q，以及policy的近似器。

回到 DQN，很明显需要两个网络，一个是目标的Q，一个是目前在学的预测的Q。

所谓的 DoubleQ，就是我在选取action用一个Q网络，选完action后估计它的值用另一个Q网络（target）。【更新q_target】

doubleDQN中有重要性采样，但是这一步我没看懂为什么要用重要性采样，似乎是为了把在线变离线？

策略梯度法

策略梯度定理

这里就放一个结论：https://zhuanlan.zhihu.com/p/491647161

这里 $d^{\pi}(s)$ 意思是状态 $s$ 在 $s_0$ 出发的轨迹中出现的期望次数，如果带discont严格意义上是有偏估计。

策略梯度的另一个思考方法假设有N条路径，是直接对 $\tau$ 的期望来求导，可以得到的大约是

至于为什么这个理解下这两个是分开的，我还没搞明白

如果使用softmax的随机策略，也即

那么求对数之后求导就是 $f$ 的导数减去 $f$ 的导数关于 $a’$ 的期望。

于是我们引出了 Reinforce 算法，这是一个MC的算法，方差很大，所以我们想能不能引入TD的方法：那么引入 $\pi $ 和 $Q$ 两个网络就是一个新的算法。如果想用上文提到的Advantage来更新critic网络也是可以的，值得注意的是Advantage Function可以直接取代Q作为policy gradient的参数，依然是无偏估计而且能降低方差。

关于引入深度学习，在形式上深度强化学习和强化学习没有差别，只是一个参数 $\theta$。算法 A3C 是算法 A2C 的异步形式，异步地积累梯度，然后定时同步。

这里跳过了一些Actor-Critic的介绍，如果读者不是很熟悉，强烈推荐这个： https://spinningup.openai.com/en/latest。

确定性策略梯度算法

引入一个算法叫DPG（ICML2014），深度网络版本叫DDPG。

Deep Deterministic Policy Gradient — Spinning Up documentation (openai.com)

其实算法是一样的，但是连续动作所以不是采样，而是直接 $a=\pi_\theta(s)$，直接导致这个 $a$ 是可微的，也就可以从后一个状态梯度反传到前一个状态。

也就是说，直接通过链式法则得出：

虽然在严谨的推导过程中它其实是丢掉了一项，只不过在策略更新小的情况下那一项被扔掉是可以接受的。

但是它只能是offline版本，因为引入噪声才行。

DDPG的tricks包括：经验回放（离线策略），目标网络，在动作输入前批标准化Q网络，添加连续噪声，最后终于把它搞work了。——广泛应用于机器人控制领域。

接下来我们考虑 off-policy 的策略梯度，因为学习的和采样的是不同的策略，所以就需要用到重要性采样了。

TD3算法，Twin Delayed DDPG，是用了三个trick，两个Q函数，不同的policy和Q的更新速度，目标函数增加高斯噪声。

Stochastic Value gradient

Deep RL Bootcamp 2017, Lecture 7

Learning Continuous control policies by stochastic value gradients. NIPS 2015

这里也先跳过吧，有点难。

natural policy gradient

Natural Actor-Critic, Jan Peters

covariant view：我们希望梯度是放射变化无关的，于是需要给梯度乘上一个系数，使得原来关于参数 $\theta$ 的梯度方向乘上系数和关于变换后的 $h$ 参数的梯度（关于 $\theta$ 的情况）一样。

理论上来说 $\nabla h J(h)=\nabla _h\theta \nabla \theta J(\theta)$。现在我们考察Fisher Information Matrix，我们定义了从参数 $\theta$ 变成参数 $h$ 的一个变换，这个Fisher Information Matrix满足性质是：

这个Fisher Information Matrix有点类似于Hessian，但是score function，就是先对策略 $\pi$ 取了一个对数，然后最后求期望。总之，假设存在这样一个函数 $F$ 满足上面的变换性质，我们就有

注意看这个形式和之前直接链式法则还是不太一样的，这个能让我们导出

也就是虽然在 $h$ 下做这个参数 $\alpha$ 的梯度，在 $\theta$ 下也是这个梯度。

Optimisation View：注意牛顿法每次找二次拟合曲线的最低点，牛顿法是仿射不变的。

Compatible point of view：

如果存在一个 $Q$，作为近似

满足两个条件：

然后最小化这个 $\epsilon$，这样的情况下estimator是无偏的。

可以看 Compatible Function Approximator Theorem，PolicyGradient.pdf (stanford.edu)后面有证明。个人认为理解这里的Q可以用soft max的想法。

这时候

可以直接展开。

TRPO

务必掌握每个公式！

这个意思是Total Variation可以被KL给bound住。

我要找到最小的地方：

然后期中复习到这里，下面这个考了这个推导我没整出来，感觉自己好菜。

emoairxPKU,EECS

春天来了，冬天还会远吗~