Finding Equilibrium via Regularization

Finding Equilibrium via Regularization - 知乎 (zhihu.com)

[[R-NaD解读\] Finding Equilibrium via Regularization - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/665560516)

在日常生活中，我们经常遇到需要求解博弈的Nash均衡的问题，然而，使用简单的自博弈或其它方法，容易出现剪刀比布好，布比石头好，石头比剪刀好这样的结论，不一定能收敛到 $$(1/3,1/3,1/3)$$ 这样的均衡状态。本文研究了修改 `FoReL` 算法，通过增加正则项的方式，使得最后一轮的策略能收敛到Nash equilibrium。

文章研究的类型属于 **sequential imperfect information** 的 **monotone game** 。这是一类更广泛的game类型，常见的如零和博弈都能包括在其中。

**序列非完美信息博弈**

首先说 sequential imperfect information game 是什么，以打牌的游戏为例，非完美信息意味着不知道对手的手牌等信息，不过对手的目标是要打完最后一张牌这种是知道的。我作为player 1，当前看到的一个状态 $$x$$，表示我现在知道的所有信息。但是因为我不知道别的player的信息，所以可能会对应很多不同的其他人的（手牌）状态，别人打了一张大王，可能手里还有小王，可能没有小王。

形式化地定义，$$H=\bigcup_{i\in[1,..,N,c]} H_i$$ 是第 $$i$$ 个player的历史（包括chance player），还有我这一轮观测到的内容 $$X=\bigcup X_i$$ 作为信息集，有一个 $$Z=\bigcup Z_i$$ 表示游戏的终止状态，$$Z_i$$ 是 $$H_i$$ 的一个子集。我们定义 $$x(h)$$ 表示在历史 $$h$$ 的情况下的信息集。我们可以定义完美回忆（perfect recall，也就是我不会忘记之前看到的信息，比如别人打过的牌），我的理解是对于 $$i$$ 而言，如果现在的状态是 $$x$$，那么有唯一的一种可能的历史，但是别人可能有多个历史到达这个状态 $$x$$。我们还可以定义 $$\tau(h)\to i$$ 表示当前历史下，下一步做决策的是谁。

如果用 $$\rho^\pi(h)$$ 历史 $$h$$ 的到达概率，用 $$\rho^{\pi^i}(h)$$ 表示到达 $$h$$ 这个历史，并且只考虑 $$i$$ 的概率，有 $$\rho^\pi(h)=\rho^{\pi^{i}}(h)\times \rho^{\pi^{-i}}(h)$$，如果用 $$\rho^{\pi}(x)=\sum_{h \in x}\rho^{\pi}(h)$$ 那么前面说到的完美回忆意味着，对于player $$i$$ 观测到的信息 $$x \in X_i$$，有 $$\rho^{\pi}(x)=\rho^{\pi^i}(h)\times \rho^{\pi^{-i}}(x)$$。

在定义了游戏的属性之后（完美回忆，非完美信息，序列决策，扩展式博弈），我们就可以定义Value function和Q function，这里的定义方法和强化学习里的一样。
$$
V_\pi^i(h)=\mathbb E \sum_{n\ge 0} r_{\pi}^i(h_n,a_n)=\sum_a \pi(a\mid x(h))[r_\pi^i(h,a)+V_\pi^i(ha)]
$$
其中 $$h_0=h,h_{n+1}=h_na_n,a_n\sim \pi(x\mid x(h_n))$$。

很容易理解，就是所有可能的历史信息，玩家 $$i$$ 可能得到的奖励函数之和，注意我只关心玩家 $$i$$，所以不管某个步骤是谁在做决策，都可能产生玩家 $$i$$ 的收益 $$r_\pi^i(h',a')$$。nash均衡就是在初始历史信息下找一个稳定的 $$\pi^i,\pi^{-i}$$。

同样的定义 $$Q$$ 函数表示选择策略的优势
$$
Q_\pi^h(h,a)=r_\pi^i(h,a)+V_\pi^i(ha)
$$
这是在历史序列上定义的V函数和Q函数，定义在信息集上则是
$$
V_\pi^i(x)=\frac{\sum _{h \in x}\rho^\pi(h)V_\pi^i(h)}{\sum_{h\in x}\rho^\pi(x)}
$$
我们之所以要介绍完美回忆是因为完美回忆的情况下，$$\rho^{\pi^i}(x)=\rho^{\pi^i}(h)$$，所以可以提取出一个公因式 $$\rho^{\pi^i}(h)$$，变成
$$
V_\pi^i(x)=\frac{\sum _{h \in x}\rho^{\pi^{-i}}(h)V_\pi^{i}(h)}{\sum_{h\in x}\rho^{\pi^{-i}}(x)}
$$
我个人的理解是，在后面关于为什么算法能收敛的证明里，因为和 $$\pi^i$$ 的无关，可以忽略掉 $$\pi^i$$ 相关的 reward 的影响，那么我新增一个 $$\bar \pi^i$$ 就能把两个合起来变成一个 $$\pi'=(\bar \pi^i,\pi^{-i})$$，从而能运用上单调函数的性质。

照抄之前的定义我们也可以得到
$$
Q_\pi^i(x,a)=\frac{\sum_{h\in x}\rho^{\pi^{-i}}(h)Q_\pi^i(h,a)}{\sum_{h\in x}\rho^{\pi^{-i}}(h)}
$$
**单调博弈**

然后我们来给一个单调博弈的定义。他是说，如果对于所有策略 $$\pi\not =\mu$$
$$
\Omega^i(\pi, \mu) = V^i_{\pi^i, \pi^{-i}}(h_{init}) - V^i_{\mu^i, \pi^{-i}}(h_{init}) - V^i_{\pi^i, \mu^{-i}}(h_{init}) + V^i_{\mu^i, \mu^{-i}}(h_{init})
$$
满足
$$
\sum_{i \in \{1, \ldots, N\}} \Omega^i(\pi, \mu) \leq 0
$$
任何两个策略之间的变化都是负的，用来说明 $$V$$ 是一个单调

在其它的地方也能看到另外的几种定义，比如 MD 里面说
$$
\sum_{i=1}^N \left< \nabla_{\pi_i} u_i(\pi_i, \pi_{-i}) - \nabla_{\pi_i} u_i(\mu_i, \mu_{-i})  , \pi_i - \mu_i \right> \leq 0
$$
虽然从形式上最后能理解这个公式在证明中的作用，但还是试着直观地感受一下。（这个V可以理解成和u的梯度同样阶的东西，所以这句话是说 $$\nabla u$$ 是单调的，上面那个是在说 $$V$$ 是一个单调的）

从感性上来说：

> 在经济和社会环境中，一个参与者的决策会影响其他人的福祉。当机构、组织或个人做出影响他人选择的决策时，最终结果往往复杂，并可能导致意想不到的后果。当决策受到其他决策者相互依赖行为和决策环境本身的特定方式影响时，会出现可预测的模式。问题是在哪些环境中，参与者有动机采取特定方向的决策，无论是与他人协调的决策，还是与他人对立的决策，或是两者的结合。
>
> 例如，如果越来越多的存款人一起挤兑银行，其他存款人也最好在资金耗尽前做同样的事情。如果两家公司生产相同的商品，公司2的产量上升，公司1的利润最大化选择可能是减少产量。在执法中，警察希望与罪犯在同一个地方（协调移动），但罪犯希望与警察在不同的地方（对立移动）。卡特尔有集体利益限制产量以增加他们的集体利润，但每个成员的个人利益是生产超过他们的配额。
>
> 这些例子展示了单调相互依赖激励在模拟各种现象方面的多功能性。这些是典型模型，它们的概括和修改被用于许多现实世界的应用中。

我们定义凸函数是说
$$
\forall x\in \mathcal X,x'\in \mathcal X,z\in \partial f(x),z'\in \partial f(x')\\
\left<z-z',x-x'\right>\ge 0
$$
可以进一步泛化，假设有一个**映射**（map） $$F$$ 是 L-Lipschitz 的，满足
$$
\forall x\in \mathcal X,x'\in \mathcal X,z\in F(x),z'\in F(x')\\
\left<z-z',x-x'\right>\ge 0
$$
那么 $$F$$ 就是单调的。（如果Jacobian矩阵是半定的或者F是可微的那么就可以当单调的）

特别的，如果 $$F$$ 的环路积分是零，那么也就是积分与路径无关，那么这个函数是保守的。保守的单调函数是某个**凸函数**的次微分。

我们不考虑序列非完美信息的上下文的话，假设 $$f^i(x)$$ 表示第 $$i$$ 个玩家在 $$x\in \mathcal X$$ 下的成本函数。定义
$$
F=[z^1,z^2,..z^N]:\mathcal X\to R^n\mid z^i\in \partial x_i f^i
$$
也就是这些成本函数的任何一个次微分，如果 $$F$$ 是单调的，那么称游戏是单调的。

> Although the local stability of some equilibrium can be seen as a weak requirement for a game to possess reasonable equilibrium predictions, conditions under which such equilibria generally exist remain an open question, as we give examples of monotone games in which no stable equilibrium exists. 

这种定义和前面提到的某个形式是一样的。一个是说 $$V$$ 定义的 $$F$$ 是单调的，一个是说 $$du$$

---

**FTRL**

然后我们来看最原始的而这个算法，证明这个算法会出现庞加莱复现。

随着时间，其实是定义了一系列的策略 $$(\pi_s)_{s \ge 0}$$，对于每个 $$i$$ 和 $$x$$，算法是：
$$
y_t^i(x, a) = \int_0^t \rho_s^{\pi^{-i}}(x)Q_{\pi_s}^i(x, a)ds \\
 \pi_t^i(\cdot | x) = \arg \max_{p \in \Delta A} \Lambda^i(p, y_t^i(x, \cdot))
$$

> 这个是不是意思是其实有两个空间，然后这两个是共轭的？

这里的 $$Q$$是某些时候有机会得到的反馈，然后每次去求一个argmax，这里
$$
\Lambda^i(p,y)=\left<p,y\right> - \phi_i(p)
$$
是一个势函数，有点类似优化过程中有一个surrogate，假如收敛的话它并不影响收敛到的位置，但是影响迭代过程中的方式。一个很简单的想法是说我把 $$y$$ 看成是当前轮的梯度，那么变成一个
$$
x_{k+1}=\arg \max_{x} \left<\nabla F(x_k),x-x_k\right>+\phi(x)
$$
是不是就几乎完全就是带一个正则项的梯度下降了，直观上来看，后面这一项其实是取 $$D_\phi(x,x_k)=\phi(x)-\phi(x_k)-\left<\nabla \phi(x_k),x-x_k\right>$$ ，会改变中间步骤但是应该不影响收敛结果。（TODO）

上半部分是所有 $$Q$$ 的总和（或者说积分），确实唯一让人费解的地方在于这个求和，我们等下再考虑这件事。

我们想要证明，如果所有人都用这个算法，如果奖励函数是和策略无关的，那么这个算法在我们定义的单调博弈中并不收敛。具体而言证明了两件事，第一是说这个算法的动力学系统是无散度的，第二是说这个动力学系统是有界的，然后引用Poincare recurrent的方法说这个系统是会不断地复现重复。

##### **Poincare recurrent**

这一节的陈述我个人觉得是有必要的，他其实是引入了一个度量工具，这个工具在后续关于收敛性的证明中很有用，在这里也就用来说明无法收敛，而且论文的标题也是这么写的，所以还是试着也写一点。

> If a flow preserves volume (is Divergence free) and has only bounded orbits then for each open set here exist orbits that intersect the set infinitely often.

大家都把它当常识了，在维基百科上有完整的表述。[Poincaré recurrence theorem - Wikipedia](https://en.wikipedia.org/wiki/Poincaré_recurrence_theorem)。作者说，如果 $$w$$ 是发散的话可能确实会收敛到一个确定性的策略，但是如果nash均衡是full support的（这个概念是指$$\pi^*(a)>0\mid \forall a$$，也就是均衡在单纯形的内部），那一定不会成为动力系统的attractor。

散度$$\nabla \cdot F=\sum_{i=1}^n\frac{\partial F_i}{\partial x_i}$$ 是针对向量场在某一点处对各方向分量的求其对应坐标的偏导数的和。

条件是两个，第一个是说要有界，一个是无散度。这个证明的核心在于 如果奖励函数和 $$\pi^i$$ 无关，那么这里散度为零。

所以作者选择了一个新的动力系统
$$
\begin{align*}
&\dot w_t^i(x,a)= \rho^{\pi_t^{-i}}(x)\left[Q_{\pi_t^i}^i-Q_{\pi_t}^i(x,a_x)\right]\\
& \pi_t^i(\cdot | x) = \arg \max_{p \in \Delta A} \Lambda^i(p, w_t^i(x, \cdot)) \end{align*}
$$

1. 这里的 $$w_t$$ 演化有 $$\dot w_t=\xi(w_t)$$，演化只依赖于当前状态 $$w_t$$ 而不是显示地依赖时间 $$t$$。因为有了 $$w_t$$ 就有了 $$\pi_t$$ 就有了 $$\dot w_t$$ 。
2. 系统在某种意义上是守恒的，无散度的。
3. 这里的策略 $$\pi_t$$ 的动力学等价于之前定义的FTRL的动力学，这个很容易看出来，因为一个常量在argmax里可以省略。这个等价性其实很重要。

主要来说明这个无散度，如果写作 $$w_t=\xi(w_t)$$，

感受一下有一个 $$\R^3$$ 维的向量场，也就是 $$\xi(w)$$，在某一个维度上有一个强度 $$\xi(w)(i,x,a)$$，
$$
\xi(w)(i,x,a)=\rho^{\pi^{-i}}(x)\left[Q_{\pi}^i(x,a)-Q_{\pi}^i(x,a_x)\right]
$$
这里，向量场 $$\xi$$，状态向量 $$w$$，向量场的分量 $$\xi(w)(i,x,a)$$，注意到
$$
\rho^{\pi^{-i}}(x)Q_\pi^i(x,a)=\sum_{h\in x}\left[r^i(h,a)+V_\pi^i(ha)\right]
$$
**如果这里的奖励函数是和 $$\pi^i$$ 无关的**，然后 $$V_\pi^i$$ 也是和 $$\pi^i$$ 无关的，所以这里的 $$\xi(w)(i,x,a)$$ 只和 $$i,x,a,\pi^{-i}$$ 有关，也就是说和 $$w^i(x,a)=w(i,x,a)$$ 无关。那么就有
$$
\nabla \cdot \xi(w)=\sum_{i=1}^n\sum_{x\in \mathcal X}\sum_{a\in A}\frac{\partial \xi(w)(i,x,a)}{w^i(x,a)}=0
$$
也就得到了散度为零的性质。（但是如果奖励是和 $$\pi^i$$ 有关的就会有不一样的结论）

----

**Lyapunov函数**

除了散度为零，还要证明有界，能被bound住，这里用的方法是说定义了一个函数（这个函数并不是Lyapunov函数，因为可以是负数），并证明其梯度小于零。

在这里，这个函数的定义是这样的
$$
J(y) = \sum_{i=1}^{N} \sum_{x \in \mathcal{X}_i} \rho^{\pi^{*i}}(x) \left[ \phi_i^{*} \left( y^i(x, \cdot) \right) - \left\langle \pi^{*}(\cdot \mid x), y^i(x, \cdot) \right\rangle \right]
$$
这里的 $$\phi_i^*(y)=\max_p \Lambda ^i(p,y)$$ 表示对偶函数，根据Young不等式的取等条件我们还有这个argmax是一个满足次梯度的东西。
$$
\pi_t=\arg \max_{p\in \Delta A} \Lambda^i(p,y)=\nabla _y \phi_i^*(y)
$$
在其它的地方也有这样的函数的定义，用来衡量到均衡的举例，比如某篇文章用了
$$
\text{GAP}(\pi)=\max _{\bar \pi\in \mathcal X} \sum_{i=1}^N \left<\nabla _\pi v_i(\pi_i,\pi_{-i}),\bar \pi_i-\pi_i\right>
$$
注意看GAP这个函数相当于是在 $$v_i(\pi)$$ 处做了一个泰勒展开（在单调博弈的意义下，这玩意确实能衡量到均衡的距离）。回过头来看，这里定义的函数就是在其他文章里说到的 GAP 函数。GAP函数之所以这么衡量，一方面是符合直观，另一方面是通过一阶近似展开确实会方便计算。不过有不一样的地方，这里的 $$J$$ 是需要用上一个假定已知的均衡，而GAP函数似乎没有直接用到最终的那什均衡。

我们看上面这个函数，展开后其实是
$$
\max _{z} \left<z,y\right>-\phi(z)-\left<\pi,y\right>=\max_{z}\left<z-\pi,y\right>-\phi(z)
$$
直觉上看没有什么太大的差别，除了引入了 $$\phi$$ 这个函数，文章说这是用于构造下面这个 **Strong Lyapunov function**。我们会在证明策略相关的奖励函数的收敛性证明中用到这个函数。
$$
\Xi(\pi^*,\pi_t)=\sum_{i=1}^{N} \sum_{h \in H_i} \rho^{\pi^{*i}}(h) D_{\phi_i}(\pi^*(\cdot \mid x(h)), \pi_t(\cdot \mid x(h)))
$$
但本文是通过证明
$$
J(y)+\sum_{i=1}^N\sum_{x\in \mathcal X_i}\rho^{\pi^{*i}} \phi_i(\pi^*(.\mid x))=\Xi\left(\pi^*,\pi\right)
$$
（代入后发现可以写成 $$\phi(\pi^*)-\phi(\pi)+\left<\pi^*-\pi,y\right>$$，然后如果是内点的话有 $$y\in \nabla \phi(\nabla \phi^*(y))=\nabla \phi(\pi)$$ （这个也是Fenchel不等式），所以就可以把他写成

并且两者的梯度相同，我个人暂时还不清楚为什么要引入这样的函数，但至少这里 $$\frac{d}{dt}J(y)=\frac{d}{dt}\Xi(\pi^*,\pi)$$。这里是和 $$y$$ 相关的，而不是和 $$\pi$$ 相关的，虽然两者可以互相转化。

思考一下 $$J$$ 这里 $$i$$ 和 $$x$$ 出现的意义，或者说思考这个序列问题中，$$\Xi$$ 里 $$i$$ 和 $$h$$ 出现的意义

一个满足条件的问题需要满足两个性质，第一是除了均衡位置它都是大于等于零的，第二是说在均衡位置这个是等于零的，第三是说梯度是负定的。

我们来研究 $$\frac{d}{dt} J(y)$$.

**J 函数求导**

这个推导其实很容易，直接求导
$$
\begin{align*}
\frac{d}{dt}J(y)&=\sum_i\sum_x\rho^{\pi^{*i}}\left( (\frac{d \phi_i^*(y)}{dy}-\pi^*)\times \frac{dy}{dt} \right)\\
&=\sum_{i=1}^N\sum_{x\in \mathcal X_i}\rho^{\pi^{*i}}\rho^{\pi_t^{-i}}\left< \pi_t(.\mid x(h))-\pi^*(.\mid h(x)), Q_{\pi_t}^i(h,.) \right>\\
&= \sum_{i=1}^{N} \sum_{x \in \mathcal{X}_i} \rho^{\pi^{*i}}(x) \sum_{h \in x} \rho_t^{\pi^{-i}}(h) \langle \pi_t(\cdot | x(h)) - \pi^*(\cdot | x(h)), Q_{\pi_t}^{i}(h, \cdot) \rangle\\

&= \sum_{i=1}^{N} \sum_{x \in \mathcal{X}_i} \sum_{h \in x} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \langle \pi_t(\cdot | x(h)) - \pi^*(\cdot | x(h)), Q_{\pi_t}^{i}(h, \cdot) \rangle\\

&= \sum_{i=1}^{N} \sum_{h \in H_i} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \langle \pi_t(\cdot | x(h)) - \pi^*(\cdot | x(h)), Q_{\pi_t}^{i }(h, \cdot) \rangle

\end{align*}
$$
有一个不喜欢的地方，第一个是这里的 $$H_i$$ 是和 $$i$$ 强相关的，我们想把它去掉。这里，我们可以定义一个策略 $${^i\bar \pi_t}=(\pi^{*i},\pi_t^{-i})$$ ，那么上面这个概率就合成这个策略。

注意到对 $$h \in H^{i}$$，有 $$\pi^*(.\mid x(h))=^i\bar \pi_t(.\mid x(h))$$ 而对于 $$h\in H^{-i}$$，有 $$^i\bar \pi_t(.\mid x(h))=\pi_t(.\mid x(h))$$ ，也就是 $$\langle \pi_t(\cdot | x(h)) -  {}^i\bar \pi_t(\cdot | x(h)), Q_{\pi_t}^{i }(h, \cdot) \rangle=0$$，所以

我们得到：
$$
{% raw %}
\begin{align*}
\frac{d}{dt} J(y) &= \sum_{i=1}^{N} \sum_{h \in H} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \left< \pi_t(\cdot \mid x(h)) - \pi^{*}(\cdot \mid x(h)), Q_{\pi_t}^i(h, \cdot) \right> \\
&= \sum_{i=1}^{N} \left[ \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{{^i\bar \pi_t}}(h) \left( V_{\pi_t}^i(h) - \sum_{a \in A} \pi_t(a \mid x(h)) \left( r_{\pi_t}^i(h, a) + V_{\pi_t}^i(ha) \right) \right) + \sum_{h \in \mathcal{Z}} \rho^{{^i\bar \pi_t}}(h) V_{\pi_t}^i(h) \right] \\
&= \sum_{i=1}^{N} \left[ \sum_{h \in H} \rho^{{^i\bar \pi_t}}(h) V_{\pi_t}^i(h)-\sum_{h\in H\setminus h_{init}}\rho^{^i\bar \pi_t}(h) V_{\pi_t}^i(h) \right] - \left[ \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{{^i\bar \pi_t}}(h) \sum_{a \in A} \pi_t(a \mid x(h)) r_{\pi_t}^i(h, a) \right] \\

&= \sum_{i=1}^{N} V_{\pi_t}^i(h_{\text{init}}) - \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{{^i\bar \pi_t}}(h) \sum_{a \in A} {^i\bar \pi_t}(a \mid x(h)) r_{{^i\bar \pi_t}}^i(h, a) \\
&\quad + \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{\pi^{{^i\bar \pi_t}}}(h)  \sum_{a \in A} {^i\bar \pi_t}(a \mid x(h)) \left( r_{{^i\bar \pi_t}}^i(h, a) - r_{\pi_t}^i(h, a) \right) \\
&= \left[ \sum_{i=1}^{N} V_{\pi_t}^i(h_{\text{init}}) - V_{(\pi^{*i}, \pi_t^{-i})}^i(h_{\text{init}}) \right] + \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \mathbb{E}_{a \sim (\pi^{*i}, \pi_t^{-i})(\cdot \mid x(h))} \left[ r_{(\pi^{*i}, \pi_t^{-i})}^i(h, a) - r_{\pi_t}^i(h, a) \right] \\
&= \left[ \sum_{i=1}^{N} V^{i}_{\pi_{t}^{i}, \pi_{*}^{-i}}(h_{\text{init}}) - V^{i}_{\pi_{*}}(h_{\text{init}}) \right] + \left[ \sum_{i=1}^{N} V^{i}_{\pi_{t}}(h_{\text{init}}) - V^{i}_{\pi_{t}^{i}, \pi_{*}^{-i}}(h_{\text{init}}) - V^{i}_{\pi_{t}^{i}, \pi_{*}^{-i}}(h_{\text{init}}) + V^{i}_{\pi_{*}}(h_{\text{init}}) \right] 
 \\
&\quad + \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \mathbb{E}_{a \sim (\pi^{*i}, \pi_t^{-i})(\cdot \mid x(h))} \left[ r_{(\pi^{*i}, \pi_t^{-i})}^i(h, a) - r_{\pi_t}^i(h, a) \right]
\end{align*}
{% endraw %}
$$
注意看第二行我们用了一个高中数列学过的很知名的trick，类似于强化学习里把 $$Q$$ 按定义展开，然后裂项成两部分。

于是后面发现大部分都是按照 $${^i\bar \pi_t}$$ 在推，所以尝试把 $$r_{\pi_t}$$ 裂出一项 $$r_{^i\bar \pi_t}$$，好处是这样能把整个变成三部分。

第一部分是初始的 $$V$$，第二部分是按照策略 $${^i\bar \pi_t}$$ 得到的奖励函数，于是就得到了倒数第二行，比较有意思的是这里通过一个变换分离出了两项。

为什么要这么做，从直观上来看是为了凑出单调博弈，因为怎么看让当前player的策略用当前的，而对手策略用均衡都是一个很奇怪的。但anyway，至少能分成三项，第一项是负的（如果在内部的话，nash均衡每个玩家换最好的策略应该是恰好等于零），第二项因为单调博弈也是负的。

第一部分对于如果均衡策略是在内部的话，这个值应该是零。

第三项是个奇怪的值，但其实容易发现，**如果奖励和策略无关的话**，这个值一定是零。

于是我们有了推论是说，这个动力学系统是有界的，然后又因为无散度，所以结论是它能出现庞加莱复现。

---

**reward transformation**

上面我们已经得到了，如果奖励函数和 $$\pi$$ 无关，那么最终结论是无散度的，接下来我们会说明，通过 Lyapunov function 的方法，能够证明收敛性。

想要通过Lyapunov function证明某个常微分方程 $$\frac{d}{dt}y_t=\xi(y_t)$$
$$
\mathcal F(x )\ge 0,\mathcal F(x^*)=0\\
\forall y\not =y^*,\frac{d}{dt}\mathcal F(y_t)<0
$$
如果是strong，类比强凸函数，我们可以说
$$
\frac{d}{dt}\mathcal F(y_t) \le -\beta \mathcal F(t_y),\beta >0
$$
在上面的证明中，我们已经得到一个函数 $$\Xi$$，
$$
\Xi(\pi^*,\pi_t)=\sum_{i=1}^{N} \sum_{h \in H_i} \rho^{\pi^{*i}}(h) D_{\phi_i}(\pi^*(\cdot \mid x(h)), \pi_t(\cdot \mid x(h)))
$$
而且 $$\frac{d}{dt}\Xi=\frac{d}{dt}J$$ ，而
$$
\frac{d}{dt}J(y)\le \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \mathbb{E}_{a \sim (\pi^{*i}, \pi_t^{-i})(\cdot \mid x(h))} \left[ r_{(\pi^{*i}, \pi_t^{-i})}^i(h, a) - r_{\pi_t}^i(h, a) \right]
$$
所以，我们想把 $$J$$ 往 $$\Xi$$ 上凑一凑，尝试把 $$h\in H_i$$，也要尝试去掉 $$\rho_t^{\pi^{-i}}$$。
$$
r_\pi^i(h,a)=r^i(h,a) - \eta \frac{1_{i=\tau(h)}}{\rho^{\pi^{-i}}(h)} \log \frac{\pi(a\mid x(h))}{\mu(a\mid x(h))}
$$
就可以发现现在 $$J$$ 能完美符合我们的需求了，当然现在也是一个 KL，所以取 $$\phi(\pi)$$ 是一个熵的话，靠着这个，我们就有
$$
\frac{d}{dt}J(y)\le -\eta\sum_{i=1}^{N} \sum_{h \in H_i}(h) \rho^{\pi^{*i}}(h) KL(\pi^*(.\mid x(h)),\pi_t(.\mid x(h)))
$$

$$
\frac{d}{dt} \Xi(\pi^*,\pi_t)\le -\eta \Xi(\pi^*,\pi_t)
$$

也就意味着能有一个指数效率的收敛速度。

---

**another reward transformation** 

对于2p0s游戏可以尝试另一种定义方法，用
$$
r_\pi^i(h,a)=r^i(h,a)-1_{i=\tau(h)} \frac{\pi(a\mid x(h))}{\mu(a\mid x(h))}+1_{i\not=\tau(h)} \frac{\pi(a\mid x(h))}{\mu(a\mid x(h))}
$$
这是保持零和的方法，同时又不希望有$$1/\rho^{\pi^{-i}}(h)$$ 这个不容易sample的量，所以那么变成
$$
\frac{d}{dt}J(y)\le \sum_{i=1}^{N} \sum_{h \in H \setminus \mathcal{Z}} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) \mathbb{E}_{a \sim (\pi^{*i}, \pi_t^{-i})(\cdot \mid x(h))} \left[ r_{(\pi^{*i}, \pi_t^{-i})}^i(h, a) - r_{\pi_t}^i(h, a) \right]
$$
在 $$i\not=\tau(h)$$ 的时候，也就是 $$h\not \in H_i$$，两个 $$r$$ 相减等于零，在 $$i=\tau(h)$$ 的时候和上面一样，如果选 $$\phi$$ 为熵的话，能变成一个 KL 散度。
$$
\frac{d}{dt}J(y)\le -\eta\sum_{i=1}^{N} \sum_{h \in H_i} \rho_t^{\pi^{-i}}(h) \rho^{\pi^{*i}}(h) KL(\pi^*(.\mid x(h)),\pi_t(.\mid x(h)))
$$
设 $$\zeta=\min_{x}\min_{\pi=\arg\max_p \Lambda(p,y)\and J(y)\le J(y_0)}\sum _{h\in x}\rho^{\pi^{-i}}(h)$$ ，如果对一个 $$x$$ 从成立那么对 $$H_i$$ 里的和也成立，$$y_0$$ 是初始的那个 $$y$$。
$$
\frac{d}{dt} \Xi(\pi^*,\pi_t)\le -\eta\zeta \Xi(\pi^*,\pi_t)
$$
综上，我们证明了如果带有reward transformation是可以收敛的，而且可以收敛地比较快。

**origin equilibrium**

> 但是这个是真收敛，还是假装收敛，就很奇怪，因为argmax能不能恰好达到是不好说的东西

接下来，我们考虑如何收敛到原始的均衡，一种想法是每一次迭代都换reward，那么这样能不能收敛(LIC)呢？也就是取 $$\mu=\pi_{k-1}$$。

我们会证明（在熵的意义下）
$$
\Xi(\pi^*,\pi_k)-\Xi(\pi^*,\pi_{k-1}) = -\Xi(\pi_k,\pi_{k-1})+\frac{1}{\eta}\sum_{i=1}^N(m_k^i+\delta_k^i+\kappa_k^i)
$$
其中
$$
\begin{align*}
\kappa_{k}^{i} &= \sum_{x \in \mathcal{X}^{i}} \rho^{\pi^{*i}}(x) \rho^{\pi^{-i}}_{k}(x) \times \sum_{a \in A} \left[ \pi^{*i}(a \mid x(h)) - \pi_{k}(a \mid x(h)) \right]^{k} Q_{\pi_{k}}^{i}(x, a) 
\\
\delta_{k}^{i} &= V_{\pi_{k}, \pi^{-i}}^{i}(h_{init}) - V_{\pi_{*}}^{i}(h_{init})
\\
m_{k}^{i} &= V_{\pi_{k}}^{i}(h_{init}) - V_{\pi^{*i}, \pi_{k}^{-i}}^{i}(h_{init}) - V_{\pi_{k}, \pi_{*}^{-i}}^{i}(h_{init}) + V_{\pi_{*}}^{i}(h_{init})
\end{align*}
$$
原文的证明方法是通过下面的方式，我的理解是为了把各个距离给找出来，而为了得到从 $$\pi^*$$ 的展开，我们希望能有一项是 $$\pi^*()\log \frac{\pi_k}{\pi_{k-1}}$$
$$
\begin{align*}
&\underbrace{\sum_{h \in H} \rho^{\pi_k}(h) \sum_{a \in A} \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a)}_{(2)}= 

\underbrace{\sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a)}_{(3)} \\

&+ \underbrace{\sum_{h \in H} \rho^{\pi_k}(h) \sum_{a \in A} \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a) - \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a)}_{(1)}
\end{align*}
$$
这里有记号
$$
{{}^kr_\pi^i(h,a)}=r^i(h,a)-\eta\frac{\bold{1}_{i=\tau(h)}}{\rho^{\pi^{-i}}(h)} \log \frac{\pi(a\mid x(h))}{\pi_{k-1}(a\mid x(h))}
$$

$$
{^i\bar \pi_t}=(\pi^{*i},\pi_t^{-i})
$$

直觉上来看就是多了一步，一个是 $$\pi_k$$ 的收益，一个是 $${^i\bar \pi_k}$$ 的收益，还有一个是差。

我们看第二项和第三项，本质是展开奖励项和策略

第二项直接展开，会发现只有 $$\pi_k^i$$ 项是有值的。
$$
\begin{align*}
(2) &= \sum_{h \in H} \rho^{\pi_k}(h)\sum_{a \in A} \pi_k(a \mid x(h)) r^i(h, a) 
\\&\quad \quad \quad - \eta \sum_{h \in H^i} \rho^{\pi_k^i}(h) \sum_{a \in A} \pi_k^i(a \mid x(h)) \log \frac{\pi_k^i(a \mid x(h))}{\pi_{k-1}^i(a \mid x(h))}
\\
&=V_{\pi_k}^i(h_{init})-\eta\sum_{h\in H_i} \rho^{\pi_k^i}(h) KL(\pi_k^i(.\mid x(h)),\pi_{k-1}^i(.\mid x(h)))
\end{align*}
$$
第三项展开，但是奖励并不是完全的
$$
\begin{align*}
(3) &= \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h)\sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) r^i(h, a) 
\\&\quad \quad \quad - \eta \sum_{h \in H^i} \rho^{\pi_k^i}(h) \sum_{a \in A} \pi^{*i}(a \mid x(h)) \log \frac{\pi_k(a \mid x(h))}{\pi_{k-1}(a \mid x(h))}
\\
&=V_{\pi_k}^i(h_{init})-\eta\sum_{h\in H_i} \rho^{\pi^{*i}}(h) (
KL(\pi^{*i}(.\mid x(h)),\pi_{k-1}(.\mid x(h)))\\&\quad \quad \quad -KL(\pi^{*i}(.\mid x(h)),\pi_{k}(.\mid x(h)) )
)
\end{align*}
$$
这里用到的就是说可以把 $$p \log \frac{a}{b}=p\log\frac{p}{b}-p\log \frac{p}{a}$$

然后我们展开(1)，我们期待能把他放缩掉。因为有一个作差，而他们除了第一步其实是一样的，我们希望把第一步展开，但是直接展开会发现两项还是不一样，主要是 $$\rho$$ 造成的，但仔细一想，(1)的一部分不就只和初始状态有关吗，所以是可以做差的。

我们定义
$$
^{k}V_{\pi_k}^i(h)=\sum_a \pi_k(a\mid x(h))\left[{}^kr_{\pi_k}^i(h,a)+{}^kV_{\pi_k}^i(ha)\right]
$$
可以发现
$$
\begin{align*}
(1)&=\sum_{h \in H} \rho^{\pi_k}(h) \sum_{a \in A} \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a) - \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a)\\
&= {}^k V_{\pi_k}^i(h_{\text{init}}) - \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a)
\\
&= \sum_{h \in H} \underbrace{\rho^{{}^i\bar \pi_k}(h)}_{\text{not }\pi_k} {}^k V_{\pi_k}^i(h) - \sum_{h \in H \setminus \{h_{\text{init}}\}} \rho^{{}^i\bar \pi_k}(h) {}^k V_{\pi_k}^i(h) - \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^{i}(h, a) \\

&= \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \left[ {}^k V_{\pi_k}^i(h) - \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k V_{\pi_k}^i(ha) \right] - \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) {}^k r_{\pi_k}^i(h, a)\\

&= \sum_{h \in H} \rho^{{}^i\bar \pi_k}(h) \left[ {}^k V_{\pi_k}^i(h) - \sum_{a \in A} {}^i\bar \pi_k(a \mid x(h)) \left[ {}^k r_{\pi_k}^i(h, a) + {}^k V_{\pi_k}^i(ha) \right] \right]\\
&= \sum_{h\in H} \rho^{^{i}\bar \pi_k}(h) \sum_{a \in A} \left[ \pi_k(a \mid x(h)) - \pi^{*i}(a \mid x(h)) \right] {}^k Q_{\pi_k}^i(h, a)\\

&= \sum_{x \in \mathcal{X}^i} \sum_{h \in x} \rho^{\pi^{*i}}(h) \rho^{\pi^{-i}_k}(h) \sum_{a \in A} \left[ \pi_k(a \mid x(h)) - \pi^{*i}(a \mid x(h)) \right] {}^k Q_{\pi_k}^i(h, a)\\

&= \sum_{x \in \mathcal{X}^i} \rho^{\pi^{*i}}(x) \left[\sum_{h \in x} \rho^{\pi^{-i}_k}(h)\right] \sum_{h\in x}\sum_{a \in A} \left[ \pi_k(a \mid x(h)) - \pi^{*i}(a \mid x(h)) \right] {}^k Q_{\pi_k}^i(h, a)\\

&= \sum_{x \in \mathcal{X}^i} \rho^{\pi^{*i}}(x) \rho^{\pi_k^{-i}}(x) \sum_{h\in x}\sum_{a \in A} \left[ \pi_k(a \mid x(h)) - \pi^{*i}(a \mid x(h)) \right] \frac{\sum_{h \in x} \rho^{\pi^{-i}_k}(h) \, {}^k Q_{\pi_k}^i(h, a)}{\sum_{h \in x} \rho^{\pi^{-i}_k}(h)}
\\
&= \sum_{x \in \mathcal{X}^i} \rho^{\pi^{*i}}(x) \rho^{\pi_k^{-i}}(x) \sum_{a \in A} \left[ \pi_k(a \mid x(h)) - \pi^{*i}(a \mid x(h)) \right] {}^k Q_{\pi_k}^i(x, a)
\\
&=-\kappa_{k}^{i} \ge 0
\end{align*}
$$
通过一通推导，作者说 $$\pi_k$$ 是 $$^kr_{\pi_k}^i$$ 这个游戏的nash均衡，所以整个的价值就是非负的。

这里第四行有一些很有意思的推导，通过一些努力我们可以把原本应该是一个策略的路径概率换成另一个策略的，从而统一作差的时候的公因式。

合并
$$
\begin{aligned}
&\eta \sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_k(\cdot \mid x(h)) \right) - \eta \sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_{k-1}(\cdot \mid x(h)) \right) \\
&= V_{\pi_k}^i(h_{\text{init}}) - V_{\pi^{*i}, \pi_k^{-i}}^i(h_{\text{init}}) + \kappa_k^i - \eta \sum_{h \in H^i} \rho^{\pi_k^i}(h) KL \left( \pi_k^i(\cdot \mid x(h)), \pi_{k-1}^i(\cdot \mid x(h)) \right) \\
&= V_{\pi_k}^i(h_{\text{init}}) - V_{\pi^{*i}, \pi_k^{-i}}^i(h_{\text{init}}) - V_{\pi_k^{i}, \pi_{k-1}^{-i}}^i(h_{\text{init}}) + V_{\pi_k^{i}, \pi_{k-1}^{-i}}^i(h_{\text{init}}) + V_{\pi_k^{i}, \pi_{k-1}^{-i}}^i(h_{\text{init}}) - V_{\pi^{*}, \pi_{k-1}^{-i}}^i(h_{\text{init}}) + \kappa_k^i \\
&= m_k^i - \eta \sum_{h \in H^i} \rho^{\pi_k^i}(h) KL \left( \pi_k^i(\cdot \mid x(h)), \pi_{k-1}^i(\cdot \mid x(h)) \right)
\end{aligned}
$$
也就是得到
$$
\sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_k(\cdot \mid x(h)) \right) - \sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_{k-1}(\cdot \mid x(h)) \right)\\
= \frac{1}{\eta} m_k^i + \frac{1}{\eta} \delta_k^i + \frac{1}{\eta} \kappa_k^i - \sum_{h \in H^i} \rho^{\pi_k^i}(h) KL \left( \pi_k^i(\cdot \mid x(h)), \pi_{k-1}^i(\cdot \mid x(h)) \right)
$$
求和得到
$$
\sum_{i=1}^{N} \sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_k(\cdot \mid x(h)) \right) - \sum_{i=1}^{N} \sum_{h \in H^i} \rho^{\pi^{*i}}(h) KL \left( \pi^{*i}(\cdot \mid x(h)), \pi_{k-1}(\cdot \mid x(h)) \right)\\
= \frac{1}{\eta} \sum_{i=1}^{N} m_k^i + \frac{1}{\eta} \sum_{i=1}^{N} \delta_k^i + \frac{1}{\eta} \sum_{i=1}^{N} \kappa_k^i - \sum_{i=1}^{N} \sum_{h \in H^i} \rho^{\pi_k^i}(h) KL \left( \pi_k^i(\cdot \mid x(h)), \pi_{k-1}^i(\cdot \mid x(h)) \right)
$$
$$m$$ 因为单调博弈所以是非正的，$$\kappa$$ 因为中间某个游戏的均衡是 $$\pi_k$$ 所以是非正的，$$\delta_k$$ 因为不是均衡所以也是非正的。

也就总而言之得到了一个
$$
\Xi(\pi^*,\pi_k)-\Xi(\pi^*,\pi_{k-1}) = -\Xi(\pi_k,\pi_{k-1})+\frac{1}{\eta}\sum_{i=1}^N(m_k^i+\delta_k^i+\kappa_k^i)
$$
这样的结论。

---

还是和刚才一样，我们遵循几乎一样的原则，构造一个strict Lyapunov functions。（但是离散版本）就是要有一个map $$F$$，每一步是说，$$\pi_k=F^k(\pi_0)$$ 收敛到 $$\pi^*$$。我们需要 $$F$$ 连续，也就是尝试求导之后，证明能L-Lipschitz连续。

我们来看下面这个东西
$$
\min_{\pi^*\in \Pi^*} \Xi(\pi^*,F(\mu))-\min_{\pi^*\in \Pi^*} \Xi(\pi^*,\mu) < 0
$$
这对于所有外面的来说，这都是能严格下降，就是收敛，而之后会证明这个收敛只能收敛到零。我们先来看这个小于零的断言，首先证明如果 $$\Xi(F(\mu),\mu)=0$$，那么 $$F(\mu),\mu \in \Pi^*$$ .

1. recall一下之前 (1) 那个的推导，我们已经有（LemmaH1）：
   $$
   \begin{equation}
   V_{\pi^*}^i(h_{init})-V_{\pi^i,\pi^{*-i}}^i(h_{init})=\\\sum_{x\in \mathcal X_i}\rho^{\pi^i}(x)\rho^{\pi^{*-i}}(x)\sum_{a}\left( \pi^i(a\mid x) -\pi^{*i}(a\mid x)\right)Q_{\pi^*}^i(x,a)
   
   \end{equation}
   $$
   这个结论其实也可以比较直观地理解，就是枚举第一个出现差别的位置，然后前面用 $$\pi^i$$ 来走（$$\rho$$），后面用 $$\pi^{*i}$$ 来走 （$$Q$$），这一步的差别是两者的差，然后因为路径是乘积的所以我需要做一个累和，大概是
   $$
   x_1x_2x_3-y_1y_2y_3=\\x_1x_2(x_3-y_3)+x_1(x_2-y_2)y_3+(x_1-y_1)y_2y_3
   $$

2. 我们断言如果对于所有 $$\hat \pi$$ 和所有 $$i$$ 满足 $$\sum_a(\pi^*(a\mid x)-\hat \pi(a\mid x))Q_{\pi^*}^i(x,a)\ge 0$$，那么 $$\pi^*$$ 一定是一个均衡。 

这个证明是说，如果 $$\pi^*$$ 满足这个条件，就一定有它的value对于换一个 $$\pi^i$$ 的value相比，代入LemmaH1，大于等于零。

3. 我们得到推论，如果不是nash均衡，那么存在 $$i,\hat \pi$$，使得这个量小于零。
4. 我们证明如果 $$\pi_\mu^*=F(\mu)=\mu$$，那么 $$\mu$$ 就是 $$r^i(h,a)$$ 游戏的nash均衡，否则存在 $$i,\hat \pi,\tilde x$$ 满足 $$\sum_{a}(\pi_\mu^*(a\mid \tilde x)-\hat \pi(a\mid \tilde x))Q_{\pi_\mu^*}^i(\tilde x,a)<0$$

于是我们记  $$\hat \pi_{\alpha}$$ 只在状态 $$\tilde x$$ 上使得 $$(1-\alpha) \pi_\mu^*+\alpha \hat \pi$$，其它地方都是 $$\pi_\mu^*$$ ，原文接下来就是证明了
$$
V_{\mu,\pi_\mu^*}^i(h_{init})-V_{\mu,\hat \pi_\alpha}^i(h_{init})\le \underbrace{c \alpha^2+d \alpha}_{c>0,d<0}<0
$$
也就是说，$$\pi_{\mu}^*$$ 不是 $$r^i(h,a)$$ 的均衡会推出 $$\pi_{\mu}^*$$ 不是 $$r_{\mu,\pi}^i(h,a)$$ 的均衡，而后者是矛盾的。证明的展开的方法是前面类似trick的延续。

> 但这里high level的idea是什么呢？微调策略以观察其对收益的影响？不是很好理解。

---

最后把上面的结论总和起来，假设策略 $$\pi^*$$ 在内部的话，

1. **前提和性质**：
   - $$F(\cdot)$$ 是一个在单纯形内部的连续映射。
   - 对于所有 $$\mu \notin \Pi^*$$，有一个不等式，表示偏离最优策略的价值函数 $$\Xi$$ 在策略 $$\mu$$ 下的值总是低于在 $$F(\mu)$$ 下的值。
   - $$\mu \to \min_{\pi^* \in \Pi^*} \Xi(\pi^*, F(\mu))$$ 是一个在单纯形边界上无穷大的正函数，并且在 $$\mu$$ 上连续。
   - 定义 $$\mu\to \Delta V(\mu)=\min_{\pi^* \in \Pi^*} \Xi(\pi^*, F(\mu))-\min_{\pi^* \in \Pi^*} \Xi(\pi^*, \mu)$$.
   - 定义 $$\bar \Omega_c=\{\mu\mid \min_{\pi^*\in \Pi^*} \Xi(\pi^*,\mu)\le c\}$$ 且 $$\Omega_c=\{\mu\mid \min_{\pi^*\in \Pi^*} \Xi(\pi^*,\mu)< c\}$$，这两个集合有界且闭，都是紧集。（原始论文这里应该有一点小错误？可能是这么修正的吧，望大佬指清）
2. **收敛性**：
   - 假设 $$C = \min_{\pi^* \in \Pi^*} \Xi(\pi^*, \pi_0)$$，并且由于 $$\Delta V(\mu) < 0$$，序列 $$\min_{\pi^* \in \Pi^*} \Xi(\pi^*, \pi_k)$$ 收敛于 $$c$$。
3. **c=0**：
   - 假设 $$c > 0$$，那么所有 $$\pi_k $$ 都在闭集 $$\Omega_{C,c} = \bar{\Omega}_C \setminus \Omega_c$$ 中。
   - $$\Omega_{C,c}$$ 是紧集，$$\Delta V(\cdot)$$ 的像也是紧集 $$K$$，且 $$k_{\max} = \sup_{x \in K} < 0$$。
   - 这意味着对于所有 $$k$$，$$\Delta V(\pi_k) \leq k_{\max}$$
   - $$\min_{\pi^*\in \Pi^*} \Xi(\pi^*,\pi_k) \le \min_{\pi^*\in \Pi^*} \Xi(\pi^*,\pi_0)+\sum_{i=0}^{k-1}\Delta V(\pi_i)\le C+k\times k_{max}<c$$。对于某个 $$k$$ 是能成立的，这和 $$c$$ 是最小值是矛盾的。
   - 所以只能 $$c=0$$

因此，通过以上分析，策略序列 $$\pi_k$$ 收敛到一个纳什均衡。

---





碎碎念：

为什么 $$\pi,Q$$ 并不完全是对偶的。







> Piliouras, G. and Shamma, J. S. Optimization despite chaos: Convex relaxations to complex limit sets via Poincar´e recurrence. In ACM-SIAM Symposium on Discrete Algo rithms (SODA), 2014.

> Doubly Optimal No-Regret Learning in Monotone Games

>Monotone Games - A Unified Approach to Games with Strategic Complements and Substitutes
>
>online monotone Games