[论文学习]Adaptively Perturbed Mirror Descent for Learning in Games

前言

文章链接

我们称集合是紧的，则集合满足：1.闭集 2.有界集。在一个紧凑的策略空间中，连续函数总是可以达到其最大值和最小值，这对于证明纳什均衡的存在性是非常有用的。

博弈的单调性（Monotonicity）：单调性通常指的是博弈的雅可比矩阵（Jacobian matrix）是正定的或半正定的。这意味着当一个玩家增加其策略值时，其他玩家的最优反应不会减少。这种性质确保了博弈的稳定性和解的唯一性。大概意味着，一个玩家的策略调整一定与收益变化的方向一致，即不会出现策略改变导致出现非预期收益。

博弈的平滑性（Smoothness）：平滑性通常意味着每个玩家的收益函数是可微的，并且其导数是连续的。这种性质允许使用微分工具来分析博弈的动态特性和均衡解。

L-Lipschitz条件。$||f(x)-f(y)||\le L||x-y||$。该条件能保证算法的收敛性。其本身可以控制函数的变化速率。

弱单调性：

Gap Function

概述

本文提出了一种作用于Mirror Descent（MD）算法的收益扰动的方式。需要说明的是，MD算法的收益函数是单调的，并可能包含噪声。通过采用这种算法，MD成功在没有噪声的场景中达到了最后一次迭代收敛到Nash均衡。目前的研究显示，基于距离anchoring函数或slingshot函数的距离设置扰动，强调了扰动对MD的作用。

因此，我们提出了APMD算法，通过根据预先设定的间隔，不断更新slingshot函数，从而不断调整扰动的大小。并最终加速了收敛的速度。

文章的整体思维链为：

1. 过去的研究从最初的设置强大的凸的惩罚函数->仔细调整优化的learning rate（调整惩罚的大小）
2. 本文不调整惩罚强度参数，而是以固定频率更新slingshot函数，从而带动扰动强度的修改。
3. 提出算法，并给出相关的收敛速度的证明。

前置知识和问题约定

单调博弈（monotone game）

定义：$G=\{[N],({\mathcal{X}}_i{)}_{i\in [N]},(v_i{)}_{i\in [N]}\}$
其中 [ N ] = { 1 , 2 , . . . , N } [N] = \{1, 2, ..., N\} [N]={1,2,...,N}表示有N个玩家，${\mathcal{X}}_i\in R^{d_i}$表示玩家$i$的$d_i$维的紧的策略空间，为便于以后的表示，我们设所有玩家的策略空间的拼接为$\mathcal{X}={\Pi }_{i\in [N]}{\mathcal{X}}_i$，每个玩家选择其策略${\pi }_i$的目的是最大化其可微分的价值函数$v_i:\mathcal{X}\to \mathbb{R}$。我们定义${\pi }_{-i}\in {\Pi }_{j\ne i}{\mathcal{X}}_j$表示除了玩家$i$，其它玩家的策略。并定义所有玩家的策略组合$\pi =({\pi }_i{)}_{i\in [N]}\in \mathcal{X}$。本文主要考虑平滑的单调博弈，即收益函数的导数是单调的。
文中给出的单调博弈满足以下两个公式：
$$\sum _{i=1}^N⟨{\nabla }_{{\pi }_i}{u}_i({\pi }_i,{\pi }_{-i})-{\nabla }_{{\pi }_i}{u}_i({\pi }_i^{\prime },{\pi }_{-i}^{\prime }),{\pi }_i-{\pi }_i^{\prime }⟩\le 0\forall \pi ,{\pi }^{\prime }\in \mathcal{X}\text{\hspace{1em}(1)}$$
$$\sum _{i=1}^N||⟨{\nabla }_{{\pi }_i}{u}_i({\pi }_i,{\pi }_{-i})-{\nabla }_{{\pi }_i}{u}_i({\pi }_i^{\prime },{\pi }_{-i}^{\prime })|{|}^2\le L^2||\pi -{\pi }^{\prime }|{|}^2\text{\hspace{1em}(2)}$$
上述公式实际上规定了两点，公式（1）规定该价值函数的变化趋势是与策略的变化趋势相反的（是一种弱单调性递减，可以认为其二阶导数矩阵是负定的）。

公式（2）则规定了其价值函数变化趋势的变化程度不大。即不会出现突变之类的的情况。

此外文中提到了两个博弈：最大最小博弈、零和高维矩阵博弈。并认为两者都是单调博弈。
对于其证明，这里可以简要叙述：

• 关于Example1:根据定义$u_1=-u_2$，因此其上述的梯度差实际上就是相反数的关系，其和永远是0，因此可以认为是单调的。
• 关于Example2:证明见上文。

Nash均衡和Gap函数

文章中满足Nash均衡的解集写作${\Pi }^{\ast }$， 并指出，对于一个平滑的单调博弈，Nash均衡解永远存在。论文用Gap函数作为衡量一个策略与Nash均衡之间的距离。
$$GAP(\pi )=ma{x}_{\tilde{\pi }\in \mathcal{X}}(\sum _{i=1}^N⟨{\nabla }_{{\pi }_i}{u}_i({\pi }_i,{\pi }_{-i}),{\tilde{\pi }}_i-{\pi }_i⟩)\text{\hspace{1em}(3)}$$
这个公式之所以能衡量，可以简单理解为，假如对于一个二维函数而言比如$y=x^2$，在一个给定的策略点$x_0$，现在需要在所有合法策略里找一个点$x_1$，使得在当前点的梯度之下，到$x_1$使得价值增长的最多。

这个GAP值之所以大于等于0，是因为如果某一个策略的所有梯度都小于0（说明无论怎么变动这个策略，该策略附近都不会有更好的价值了），则最大就是0，也就是说其本身。

此外需要说明的是，某些博弈可能存在多个Nash均衡点，可以理解为存在多个局部最小值，因此这里GAP=0不意味着这就是全局最优，仅能认为已经到了某个Nash均衡点（局部最优）。

文章问题定义

本文所讨论的博弈过程定义为，每个参与者$i$根据其之前所获得的信息作决策，并在决策结束后下一轮收到价值函数的梯度作为反馈。本论文主要讨论两种反馈模型：全量反馈(Full Feedback)与噪声反馈(Noisy Feedback)。

• 全量反馈：${\hat{\nabla }}_{{\pi }_i}u({\pi }_i^t,{\pi }_{-i}^t)={\nabla }_{{\pi }_i}u({\pi }_i^t,{\pi }_{-i}^t)$，即反馈的梯度完全等于该点真实的梯度。
• 噪声反馈：${\hat{\nabla }}_{{\pi }_i}u({\pi }_i^t,{\pi }_{-i}^t)={\nabla }_{{\pi }_i}u({\pi }_i^t,{\pi }_{-i}^t)+{\xi }_i^t$，其中${\xi }_i^t$是噪音向量，在后续的讨论过程中，认为其均值为0，方差有界。

Mirror Descent

方法

论文后面有大量的数学证明用于证明该算法的收敛性。这里暂时偷懒了，以后再写。

评价

1. 本文解决了在有噪声的反馈中，最终会围绕Nash均衡转圈，而无法收敛到Nash均衡的情况。
2. 本文是更多是一个理论上推导。十分严谨。
3. 不同的散度函数会对收敛结果有影响吗？不同的映射函数会对Mirror Descent有影响吗？