随机纳什博弈中的近邻梯度响应与最佳响应方案研究

Research on Neighboring Gradient Response and Best-Response Schemes in Stochastic Nash Games

摘要: 本文研究了一个N人随机纳什博弈，其中第i个参与者最小化的目标函数为$f_i\left(x\right)+r_i\left(x_i\right)$ ，其中$f_i$ 是期望值，且$r_i$ 具有高效的近邻评估。在此背景下，本文做出以下结果：1) 在串联梯度映射的强单调性假设条件下，为所提出的可变样本规模近邻随机梯度响应方案推导出最优收敛速率以及神谕复杂度界；2) 在与近邻最佳响应映射相关的合适压缩性质下，设计了一个可变样本规模近邻最佳响应方案，其中近邻最佳响应是通过求解一个样本平均问题来计算的。如果用于计算样本平均的批量大小以合适的速率增加，可以证明所得迭代以线性速率收敛，并推导出神谕复杂度。

Abstract: This paper studies an N-player stochastic Nash game, where the objective function minimized by the i-th player is $f_i\left(x\right)+r_i\left(x_i\right)$ , where $f_i$ is the expected value and $r_i$ has an efficient proximal evaluation. In this context, this paper obtains the following results: 1) Under the strong monotonic assumption of the concatenated gradient mapping, the optimal convergence rate and the oracle complexity bound are derived for the proposed variable sample size stochastic gradient response scheme; 2) Under the appropriate contraction property related to the proximal best-response mapping, a variable sample size proximal best-response scheme is designed, where the proximal best-response is computed by solving a sample average problem. If the batch size used for computing the sample average increases at an appropriate rate, it can be shown that the resulting iterations converge at a linear rate, and the oracle complexity is derived.

1. 引言

非合作博弈论[1] [2]是博弈论的一个分支，它研究在给定对手策略的情况下，各个独立的参与者如何解决冲突以实现自身收益函数的最优化。纳什博弈是非合作博弈的一个重要子类，源于[3]的开创性工作。这类模型在众多工程系统中得到了广泛应用，例如电网、通信网络和传感器网络。在本文中，考虑一个有限参与者集合的纳什均衡问题，参与者用i表示，其中$i\in N\triangleq \left\{1,\cdots ,N\right\}$ 。对于任意的$i\in N$ ，第i个参与者由策略$x_i\in R^{n_i}$ 和收益函数$F_i\left(x_i,x_{-i}\right)$ 来刻画，该收益函数依赖于其自身的策略$x_i$ ，并以对手的策略$x_{-i}\triangleq {\left\{x_j\right\}}_{j\ne i}$ 为参数。若$n\triangleq {\displaystyle {\sum }_{i=1}^N{n}_i}$ ，且$x$ 表示策略组合定义为$x\triangleq \left(x_1,\cdots ,x_N\right)\in R^n$ 。本文考虑一个随机纳什博弈P，在该博弈中，给定对手的策略$x_{-i}$ ，参与者i的目标是求解如下的随机复合优化问题：

$\underset{x_i\in R^{n_i}}{\min }{F}_i\left(x_i,x_{-i}\right)\triangleq f_i\left(x_i,x_{-i}\right)+r_i\left(x_i\right).$

其中$f_i\left(x\right)\triangleq E\left[{\psi }_i\left(x;\xi \left(\omega \right)\right)\right]$ ，随机变量$\xi :\Omega \to R^d$ 定义在概率空间$\left(\Omega ,F,P\right)$ 上，${\psi }_i:R^n\times R^d\to R$ 是一个标量值函数，$E[\cdot ]$ 表示关于概率测度P的期望。本文关注的是非光滑凸纳什博弈，其中对于任意的$x_{-i}$ ，$f_i\left(x_i,x_{-i}\right)$ 被假设为关于$x_i$ 是光滑且凸的，而$r_i\left(x_i\right)$ 被假设为凸函数，但可能是非光滑的并且具有高效的近邻评估。在随机纳什博弈中，若第d i个参与者求解参数化问题$\left(P_i\left(x_{-i}\right)\right)$ ，则纳什均衡是一个元组$x^{*}={\left\{x_i^{*}\right\}}_{i=1}^N\in R^n$ ，使得对于每个参与者$i\in N$ ，都满足以下条件：

$F_i\left(x_i^{*},x_{-i}^{*}\right)\le F_i\left(x_i,x_{-i}^{*}\right),\forall x_i\in R^{n_i}.$

换句话说，如果没有任何参与者可以通过单方面偏离策略$x_i^{*}$ 来提高自己的收益，那么$x^{*}$ 就是一个纳什均衡。

本文的研究重点为开发具有最优确定性收敛速率的可变样本规模近邻随机梯度响应方案和近邻最佳响应方案。前面的学者讨论了一些关于连续策略纳什博弈以及随机优化方差缩减的方案。例如在确定性纳什博弈中，早期研究聚焦于凸纳什博弈，其中串联梯度映射要么是强单调的[4]，要么仅仅是单调映射[5]。虽然上述方案采用了梯度响应技术，但在[6]中研究了依赖于最佳响应映射收缩特性的最佳响应方案。在随机纳什博弈中，针对单调随机纳什博弈，提出了正则化随机逼近方案[7]，并且后续研究对其进行了拓展，以应对模型误设以及缺乏利普希茨性质的情况。更近些时候，在[8]中开发了采样最佳响应方案，同时在[9]中为一类非精确随机最佳响应方案提供了收敛速率陈述和迭代复杂度界限。实际上，本文从前面学者的工作中获得灵感，进而推导出更优的收敛速率陈述。最后，在[10]中证明了随机纳什博弈中，由最佳响应方案产生的序列的几乎必然收敛性和均方收敛性。

本文的创新点有两个，第一提出了一个可变样本规模近邻梯度响应方案，在强单调性假设条件下，证明了可变样本规模近邻梯度响应方案具有均方误差的线性收敛速率(定理1)。而在定理2中确定了达到一个ε-纳什均衡(记为x，其中x满足$E\left[{\Vert x-x^{*}\Vert }^2\right]\le \epsilon$ )的迭代复杂度和神谕复杂度分别为$O\left(\ln \left(1/\epsilon \right)\right)$ 和$O\left(\ln {\left(1/\epsilon \right)}^{1+\delta }\right)$ ，其中$\delta \ge 0$ 。此外，在推论1中表明，通过选取特定的算法参数，获得一个ε-纳什均衡的迭代复杂度和神谕复杂度分别被界定为$O\left(k^2\ln \left(1/\epsilon \right)\right)$ 和$O\left(k^2/\epsilon \right)$ ，这里的k表示条件数。

第二开发了一种可变样本规模近邻最佳响应方案(见算法1)，用于求解一类具有压缩性质近邻最佳响应映射的随机纳什博弈。在该类博弈中，每个参与者每一步都要解决一个样本平均最佳响应问题。本文在定理3中证明，在合适的情景数量下，该方案所产生的迭代序列以线性速率收敛到纳什均衡。此外，还确定了达到ε-纳什均衡所需的迭代复杂度和神谕复杂度分别为$O\left(\ln \left(1/\epsilon \right)\right)$ 和$O\left(\ln {\left(1/\epsilon \right)}^{2\left(1+\delta \right)}\right)$ ，其中$\delta \ge 0$ 。

2. 可变样本规模近邻梯度响应方案

本节考虑针对一类与强单调串联梯度映射相关的强单调纳什博弈，设计一种可变样本规模的随机梯度响应方案。本文将证明该方案所产生的迭代序列以线性速率收敛至纳什均衡，并给出实现ε-纳什均衡所需的神谕复杂度。

2.1. 可变样本规模近邻梯度响应设计

本文针对随机纳什博弈P施加如下假设：

假设1：(1) 函数$r_i$ 是下半连续且凸的，其有效定义域记为$R_i\triangleq dom\left(r_i\right)$ 。假设$R\triangleq {\displaystyle {\prod }_{j=1}^N{R}_i}$ 且$R_{-i}\triangleq {\displaystyle {\prod }_{j\ne i}^{}{R}_j}$ 。

(2) 对于每个固定的$x_{-i}\in R_{-i}$ ，函数$f_i\left(x_i,x_{-i}\right)$ 在包含$R_i$ 的开集上关于$x_i$ 是$C^1$ 类且凸的。

(3) 对于所有$x_{-i}\in R_{-i}$ 以及任意$\xi \in R^d$ ，函数${\psi }_i\left(x_i,x_{-i};\xi \right)$ 在包含$R_i$ 的开集上关于$x_i$ 是可微的，使得${\nabla }_{x_i}{f}_i\left(x_i,x_{-i}\right)=E\left[{\nabla }_{x_i}{\psi }_i\left(x_i,x_{-i};\xi \right)\right]$ 。

如果$G\left(x;\xi \right)\triangleq {\left({\nabla }_{x_i}{\psi }_i\left(x;\xi \right)\right)}_{i=1}^N$ 且$G\left(x\right)\triangleq E\left[G\left(x;\xi \right)\right]$ ，那么根据假设1(3)，$G\left(x\right)={\left({\nabla }_{x_i}{f}_i\left(x\right)\right)}_{i=1}^N$ 。以下引理表明，元组$x^{*}$ 是P的一个纳什均衡，当且仅当它是某个合适映射的不动点。

引理1纳什均衡与不动点的等价性

给定随机纳什博弈P，假设对于每个参与者$i\in N$ ，假设1都成立。定义$r\left(x\right)\triangleq {\left(r_i\left(x_i\right)\right)}_{i=1}^N$ 。那么$x^{*}\in X$ 是一个纳什均衡，当且仅当$x^{*}$ 是$pro{x}_{\alpha r}\left(x-\alpha G\left(x\right)\right)$ 的一个不动点，即

$x^{*}=pro{x}_{\alpha r}\left(x^{*}-\alpha G\left(x^{*}\right)\right),\forall \alpha >0.$

假设迭代步长用k表示，参与者i在时刻k的策略用$x_{i,k}\in R^{n_i}$ 表示，它是其均衡策略$x_i^{*}$ 的一个估计值。本文考虑标准近邻随机梯度法的一种可变样本规模的推广形式，在第k次迭代中使用$N_k$ 个采样梯度。给定随机向量$\xi$ 的$N_k$ 个实现值的样本${\xi }_k^1,\cdots ,{\xi }_k^{N_k}$ ，对于任意$i\in N$ ，给定$x_{i,0}\in R_i$ ，参与者i按如下方式更新$x_{i,k+1}$ ：

$x_{i,k+1}=pro{x}_{\alpha r_i}\left[x_{i,k}-\alpha \frac{{\displaystyle {\sum }_{p=1}^{N_k}{\nabla }_{x_i}{\psi }_i}\left(x_k;{\xi }_k^p\right)}{N_k}\right],$

其中$\alpha >0$ 是常数步长，${\nabla }_{x_i}{\psi }_i\left(x_k;{\xi }_k^p\right)$ ，$p=1,\cdots ,N_k$ 表示采样梯度。定义${\omega }_k^p\triangleq G\left(x_k;{\xi }_k^p\right)-G\left(x_k\right)$ ，且${\overline{\omega }}_{k,N_k}\triangleq \frac{1}{N_k}{\displaystyle {\sum }_{p=1}^{N_k}{\omega }_k^p}$ 。那么上述方案可表示为

$x_{k+1}=pro{x}_{\alpha r}\left[x_k-\alpha \left(G\left(x_k\right)+{\overline{\omega }}_{k,N_k}\right)\right].$

本文对梯度映射和噪声做出以下假设。

假设2：(1) 映射$G\left(x\right)$ 在集合R上是具有常数L的利普希茨连续的，即

$\Vert G\left(x\right)-G\left(y\right)\Vert \le L\Vert x-y\Vert \forall x,y\in R.$

(2) $G\left(x\right)$ 是具有参数$\eta$ 的强单调的，即

${\left(G\left(x\right)-G\left(y\right)\right)}^{\text{T}}\left(x-y\right)\ge \eta {\Vert x-y\Vert }^2\forall x,y\in R.$

(3) 存在一个常数$\nu$ ，使得对于任意$k\ge 0$ ，以下条件成立：$E\left[{\overline{\omega }}_{k,N_k}|F_k\right]=0$ ，$E\left[{\Vert {\overline{\omega }}_{k,N_k}\Vert }^2|F_k\right]\le {\nu }^2/N_k$ 几乎处处成立，其中$F_k\triangleq \sigma \left\{x_0,x_1,\cdots ,x_k\right\}$ 。

2.2. 收敛速率分析

本文从一个关于样本规模$N_k$ 、步长$\alpha$ 和问题参数的条件均方差的简单递推关系开始。

引理2 考虑可变样本规模近邻梯度响应，并且假设1和假设2成立。定义$q\triangleq 1-2\alpha \eta +{\alpha }^2{L}^2$ 。那么对所有的$k\ge 0$ ，$E\left[{\Vert x_{k+1}-x^{*}\Vert }^2|F_k\right]\le q{\Vert x_k-x^{*}\Vert }^2+{\alpha }^2{\nu }^2/N_k$ ，几乎处处成立。

利用引理2，本文能够证明随机梯度响应的线性收敛速率。

定理1 可变样本规模近邻梯度响应的线性收敛速率：设将近邻梯度响应应用于P，其中对于某个$\rho \in \left(0,1\right)$ ，$N_k=\left[{\rho }^{-\left(k+1\right)}\right]$ ，并且对于某个常数$C>0$ ，有$E\left[{\Vert x_0-x^{*}\Vert }^2\right]\le C$ 。当假设1和假设2成立，且$\alpha <2\eta /L^2$ ，定义$q\triangleq 1-2\alpha \eta +{\alpha }^2{L}^2$ 。那么对任意的$k\ge 0$ ，以下结论成立：

(1) 若$\rho \ne q$ ，则$E\left[{\Vert x_k-x^{*}\Vert }^2\right]\le C\left(\rho ,q\right)\max {\left\{\rho ,q\right\}}^k$ ，其中

$C\left(\rho ,q\right)\triangleq C+\frac{{\alpha }^2{\nu }^2}{1-\min \left\{\rho /q,q/\rho \right\}}$ .

(2) 若$\rho =q$ ，则对任意的$\overline{\rho }\in \left(\rho ,1\right)$ ，$E\left[{\Vert x_k-x^{*}\Vert }^2\right]\le \overline{D}{\overline{\rho }}^k$ ，其中

$\overline{D}\triangleq C+\frac{{\alpha }^2{\nu }^2}{\ln \left({\left(\overline{\rho }/\rho \right)}^e\right)}$ .

2.3. 迭代与神谕复杂度

在本节中，本文考察此方案在计算ε-纳什均衡时的迭代次数(以近邻评估次数来衡量)和神谕复杂度，接下来将对ε-纳什均衡进行定义。回顾前文，若$E\left[{\Vert x-x^{*}\Vert }^2\right]\le \epsilon$ ，则随机策略配置$x:\Omega \to R^n$ 是一个ε-纳什均衡。

定理2 迭代与神谕复杂度：设将近邻梯度响应应用于$P$ ，其中对于某个$\rho \in \left(0,1\right)$ ，$N_k=\left[{\rho }^{-\left(k+1\right)}\right]$ ，且$E\left[{\Vert x_0-x^{*}\Vert }^2\right]\le C$ 。当假设1和假设2成立，定义$q\triangleq 1-2\alpha \eta +{\alpha }^2{L}^2$ 。设$\alpha <2\eta /L^2$ ，$\overline{\rho }\in \left(\rho ,1\right)$ ，$C\left(\overline{\rho },q\right)$ ，和$\overline{D}$ 如定理1中所定义。那么，获得一个ε-纳什均衡所需的近邻评估次数由$K\left(\epsilon \right)$ 界定，其定义如下：

$K\left(\epsilon \right)\triangleq \{\begin{array}{l}\frac{1}{\ln \left(1/q\right)}\ln \left(\frac{C\left(\rho ,q\right)}{\epsilon }\right),若\rho <q<1\\ \frac{1}{\ln \left(1/\overline{\rho }\right)}\ln \left(\frac{\overline{D}}{\epsilon }\right),若q=\rho \\ \frac{1}{\ln \left(1/\rho \right)}\ln \left(\frac{C\left(\rho ,q\right)}{\epsilon }\right),若q<\rho <1\end{array}$ (2.1)

并且所需的采样梯度数量由$M\left(\epsilon \right)$ 界定，其定义如下：

$M\left(\epsilon \right)\triangleq \{\begin{array}{l}\frac{1}{\rho \ln \left(1/q\right)}{\left(\frac{C\left(\rho ,q\right)}{\epsilon }\right)}^{\frac{\ln \left(1/\rho \right)}{\ln \left(1/q\right)}}+K\left(\epsilon \right),若\rho <q<1\\ \frac{1}{\rho \ln \left(1/\overline{\rho }\right)}{\left(\frac{\overline{D}}{\epsilon }\right)}^{\frac{\ln \left(1/\rho \right)}{\ln \left(1/\overline{\rho }\right)}}+K\left(\epsilon \right),若q=\rho \\ \frac{1}{\rho \ln \left(1/\rho \right)}\left(\frac{C\left(\rho ,q\right)}{\epsilon }\right)+K\left(\epsilon \right),若q<\rho <1.\end{array}$ (2.2)

证明. 本文首先考虑$\rho \ne q$ 的情形。根据定理1 (1)，以下式子成立：

$E\left[{\Vert x_k-x^{*}\Vert }^2\right]\le \epsilon \Rightarrow k\ge K_1\left(\epsilon \right)\triangleq \frac{\ln \left(C\left(\rho ,q\right)/\epsilon \right)}{\ln \left(1/\max \left\{\rho ,q\right\}\right)}.$

然后，对于$\rho <q<1$ 和$q<\rho <1$ 的情况，本文得到了方程(2.1)中给出的界限。注意，对于$\lambda >1$ 以及任意正整数K，以下式子成立：

${\displaystyle \sum _{k=0}^K{\lambda }^k}\le {\displaystyle {\int }_0^{K+1}{\lambda }^x\text{d}x}\le \frac{{\lambda }^{K+1}}{\ln \left(\lambda \right)}.$

然后本文可以得到以下界限：

${\displaystyle \sum _{k=0}^{K_1\left(\epsilon \right)-1}{N}_k}\le {\displaystyle \sum _{k=0}^{K_1\left(\epsilon \right)-1}{\rho }^{-\left(k+1\right)}+K_1\left(\epsilon \right)}\le \frac{{\rho }^{-K_1\left(\epsilon \right)}}{\rho \ln \left(1/\rho \right)}+K_1\left(\epsilon \right).$

注意，对于任意$\epsilon >0,p<1,c_1>0$ ，以下式子成立：

${\rho }^{-\frac{\ln \left(c_1/\epsilon \right)}{\ln \left(1/p\right)}}={\left({\text{e}}^{\ln \left({\rho }^{\left(-1\right)}\right)}\right)}^{\frac{\ln \left(c_1/\epsilon \right)}{\ln \left(1/p\right)}}={\text{e}}^{\ln {\left(c_1/\epsilon \right)}^{\frac{\ln \left(c_1/\epsilon \right)}{\ln \left(1/p\right)}}}={\left(c_1/\epsilon \right)}^{\frac{\ln \left(c_1/\epsilon \right)}{\ln \left(1/p\right)}}.$

因此，获得一个ε-纳什均衡所需的采样梯度数量由以下式子界定：

$\frac{1}{\rho \ln \left(1/\rho \right)}{\left(\frac{C\left(\rho ,q\right)}{\epsilon }\right)}^{\frac{\ln \left(1/\rho \right)}{\ln \left(1/\max \left\{\rho ,q\right\}\right)}}+K_1\left(\epsilon \right).$

因此，对于$\rho <q<1$ 和$q<\rho <1$ 的情况，本文得到了方程(2.2)中给出的界限。$\rho =q$ 的情况可以类似的证明。

注：(1) 上述定理表明，达到ε-纳什均衡的迭代复杂度和神谕复杂度分别为$O\left(\ln \left(1/\epsilon \right)\right)$ 和$O\left(\ln {\left(1/\epsilon \right)}^{1+\delta }\right)$ 。其中，当$\rho \in \left(p,1\right)$ 时，$\delta =0$ ；当$\rho <q<1$ 时，$\delta =\frac{\ln \left(q/\rho \right)}{\ln \left(1/q\right)}$ ；当$q=\rho$ 时，$\delta =\frac{\ln \left(\overline{\rho }/\rho \right)}{\ln \left(1/\overline{\rho }\right)}$ 。(2) 假设本文使用另一种度量来描述ε-纳什均衡：若$E\left[\Vert x-x^{*}\Vert \right]\le \epsilon$ ，则随机策略配置$x:\Omega \to R^n$ 是一个ε-纳什均衡。然后，根据詹森不等式可知，ε²-纳什均衡也是ε-纳什均衡。因此，由定理2可得，达到ε-纳什均衡的迭代复杂度和神谕复杂度分别为$O\left(\ln \left(1/\epsilon \right)\right)$ 和$O\left(\ln {\left(1/\epsilon \right)}^{2\left(1+\delta \right)}\right)$ 。

推论：设将近邻梯度响应应用于P，其中对于某个常数$C>0$ ，有$E\left[{\Vert x_0-x^{*}\Vert }^2\right]\le C$ 。当假设1和假设2成立，定义条件数$k\triangleq \frac{L}{\eta }$ 。设$\alpha =\frac{\eta }{L^2}$ ，且对于$\rho =1-\frac{1}{2k^2}$ ，$N_k=\left[{\rho }^{-\left(k+\right)}\right]$ 。那么，获得一个ε-纳什均衡所需的近邻评估次数和采样次数分别由$O\left(k^2\ln \left(1/\epsilon \right)\right)$ 和$O\left(k^2/\epsilon \right)$ 界定。

3. 可变样本规模近邻最佳响应方案

在本节中，本文考虑一类随机纳什博弈，其中近邻最佳响应是压缩映射的。本文提出一种可变样本规模近邻最佳响应方案来计算均衡，并推导出收敛速率，建立迭代和神谕复杂度界限。

3.1. 近邻最佳响应映射的背景

对于任意的$i\in N$ 以及任意的元组$y\in R^n$ ，定义近邻最佳响应映射${\widehat{x}}_i\left(y\right)$ 为

${\widehat{x}}_i\left(y\right)\triangleq \arg {\min }_{x_i\in R^{n_i}}\left[E\left[{\psi }_i\left(x_i,y_{-i};\xi \right)\right]+r_i\left(x_i\right)+\frac{u}{2}{\Vert x_i-y_i\Vert }^2\right]$ 。对问题$\left(P_i\left(x_{-i}\right)\right)$ 施加如下假设。

假设3：(1) 对于每一个固定的$x_{-i}\in R_{-i}$ ，函数$f_i\left(x_i,x_{-i}\right)$ 是二次连续可微的，并且在包含$R_i$ 的开集上关于$x_i$ 是凸的。此外，假设${\nabla }_{x_i}{f}_i\left(x_i,x_{-i}\right)$ 关于$x_i$ 是利普希茨连续的，并且在$x_{-i}$ 上是一致有界的，其常数为$L_i$ ，即对任意的$x_i,{x^{\prime }}_i\in R_i$ ，有

$\Vert {\nabla }_{x_i}{f}_i\left(x_i,x_{-i}\right)-{\nabla }_{x_i}{f}_i\left({x^{\prime }}_i,x_{-i}\right)\Vert \le L_i\Vert x_i-{x^{\prime }}_i\Vert$ .

(2) 对于所有的$x_{-i}\in R_{-i}$ 以及任意的$\xi \in R^d$ ，函数${\psi }_i\left(x_i,x_{-i};\xi \right)$ 在包含$R_i$ 的开集上关于$x_i$ 是可微的。此外，对于任意的$i\in N$ 和所有的$x\in R$ ，存在$M_i>0$ ，使得$E\left[{\Vert {\nabla }_{x_i}{f}_i\left(x\right)-{\nabla }_{x_i}{\psi }_i\left(x_i,x_{-i};\xi \right)\Vert }^2\right]\le M_i^2$ 。

根据假设3，$\forall i\in N$ ，$f_i$ 在R上的二阶导数是有界的。类似于文献[11]中采用的方法，可以定义

$\Gamma \triangleq \left(\begin{array}{cccc}\frac{\mu }{\mu +{\zeta }_{1，\min }}& \frac{{\zeta }_{12,\max }}{\mu +{\zeta }_{1，\min }}& \cdots & \frac{{\zeta }_{1N,\max }}{\mu +{\zeta }_{1，\min }}\\ \frac{{\zeta }_{21,\max }}{\mu +{\zeta }_{2，\min }}& \frac{\mu }{\mu +{\zeta }_{2，\min }}& \cdots & \frac{{\zeta }_{2N,\max }}{\mu +{\zeta }_{2，\min }}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\zeta }_{N1,\max }}{\mu +{\zeta }_{N，\min }}& \frac{{\zeta }_{N2,\max }}{\mu +{\zeta }_{N，\min }}& \cdots & \frac{\mu }{\mu +{\zeta }_{N，\min }}\end{array}\right).$

其中${\zeta }_{i,\min }\triangleq {\inf }_{x\in X}{\lambda }_{\min }\left({\nabla }_{x_i}^2{f}_i\left(x\right)\right)$ ，以及$\forall j\ne i$ ，有${\zeta }_{ij,\max }\triangleq {\sup }_{x\in X}\Vert {\nabla }_{x_i{x}_j}^2{f}_i\left(x\right)\Vert$ 。那么根据文献[11]中的定理4，可得：$\left[\begin{array}{c}\Vert {\widehat{x}}_1\left(y^{\prime }\right)-{\widehat{x}}_1\left(y\right)\Vert \\ ⋮\\ \Vert {\widehat{x}}_N\left(y^{\prime }\right)-{\widehat{x}}_N\left(y\right)\Vert \end{array}\right]\le \Gamma \left[\begin{array}{c}\Vert {y^{\prime }}_1-y_1\Vert \\ ⋮\\ \Vert {y^{\prime }}_N-y_N\Vert \end{array}\right]$ 。若该雅可比矩阵的谱半径$\rho \left(\Gamma \right)<1$ ，则近邻最佳响应映射关于某个单调范数是压缩映射的。关于最佳响应映射$\widehat{x}(\cdot )$ 的压缩性质的充分条件，可见参考文献[11]。

3.2. 可变样本规模近邻最佳响应方案

在迭代步长为k下，获取随机向量$\xi$ 的$N_k$ 个独立样本${\xi }_k^1,\cdots ,{\xi }_k^{N_k}$ ，对于任意的$x_i\in X_i$ ，本文通过样本均值$\frac{1}{N_k}{\displaystyle {\sum }_{p=1}^{N_k}{\psi }_i}\left(x_i,y_{-i,k};{\xi }_k^p\right)$ 近似函数$f_i\left(x_i,y_{-i,k}\right)$ 来求解样本均值下的最佳响应问题，得到可变样本规模近邻最佳响应算法，见表1。

Table 1. Variable sample size proximal best-response algorithm

表1. 可变样本规模近邻最佳响应算法

算法 可变样本规模近邻最佳响应算法

设$k:=0.$ 初始策略为：$y_{i,0}=x_{i,0}\in X_i$ ，对每个参与者$i=1,\cdots ,N$ ，给定一个确定性序列${\left\{{\gamma }_{i,k}\right\}}_{k\ge 0}$ 。

(1) 对于$i=1,\cdots ,N$ ，参与者i更新其估计值$x_{i,k+1}$ 为 $x_{i,k+1}=\underset{x_i\in R^{n_i}}{\arg \min }\left[\frac{1}{N_k}{\displaystyle \sum _{p=1}^{N_k}{\psi }_i\left(x_i,y_{-i,k};{\xi }_k^p\right)+r_i\left(x_i\right)+\frac{\mu }{2}{\Vert x_i-y_{i,k}\Vert }^2}\right].$

(2) 对于$i=1,\cdots ,N$ ，有$y_{i,k+1}:=x_{i,k+1}$ ； (3) 令$k:=k+1$ ，然后重复步骤(1)。

3.3. 神谕与迭代复杂度

定义${\epsilon }_{i,k+1}\triangleq x_{i,k+1}-{\widehat{x}}_i\left(y_k\right)$ 。本节可以得到如下引理，该引理为关于$E\left[{\Vert {\epsilon }_{i,k+1}\Vert }^2\right]$ 的一个界定。

引理3：若假设3成立，考虑上面算法，则有$E\left[{\Vert {\epsilon }_{i,k+1}\Vert }^2\right]\le \frac{M_i^2{C}_r^2}{N_k}$ ，其中$C_r\triangleq \frac{\mu }{{\mu }^2+L^2}{\left(1-\frac{L}{\sqrt{{\mu }^2+L^2}}\right)}^{-1}$ ，$L\triangleq {\max }_i{L}_i$ 。

证明：定义${\overline{\omega }}_{i,k}\left(x_i\right)\triangleq \frac{1}{N_k}{\displaystyle {\sum }_{p=1}^{N_k}{\nabla }_{x_i}}{\psi }_i\left(x_i,y_{-i,k};{\xi }_k^p\right)-{\nabla }_{x_i}{f}_i\left(x_i,y_{-i,k}\right)$ 。由最优性条件可知，对于任意的$\alpha >0$ ，$x_{i,k+1}$ 和${\widehat{x}}_i\left(y_k\right)$ 分别是以下两个映射的不动点

$pro{x}_{\alpha r_i}\left[x_i-\alpha \left({\nabla }_{x_i}{\tilde{f}}_i\left(x_i,y_k\right)+{\overline{\omega }}_{i,k}\left(x_i\right)\right)\right]$ 和$pro{x}_{\alpha r_i}\left[x_i-\alpha {\tilde{f}}_i\left(x_i,y_k\right)\right]$ .

由近邻算子的非扩张性，对于任意的$\alpha >0$ ，以下结论成立：

$\begin{array}{l}\Vert {\epsilon }_{i,k+1}\Vert \le \alpha \Vert {\overline{\omega }}_{i,k}\left(x_{i,k+1}\right)\Vert +\Vert x_{i,k+1}-{\widehat{x}}_i\left(y_k\right)-\alpha \left({\tilde{f}}_i\left(x_{i,k+1},y_k\right)-{\tilde{f}}_i\left({\widehat{x}}_i\left(y_k\right),y_k\right)\right)\Vert \\ \le \sqrt{{\left(1-\alpha \mu \right)}^2+{\alpha }^2{L}^2}\Vert {\epsilon }_{i,k+1}\Vert +\alpha \Vert {\overline{\omega }}_{i,k}\left(x_{i,k+1}\right)\Vert .\end{array}$

在上述不等式中，令$\alpha =\frac{\mu }{{\mu }^2+L^2}$ ，可以得到$\Vert {\epsilon }_{i,k+1}\Vert \le C_r\Vert {\overline{\omega }}_{i,k}\left(x_{i,k+1}\right)\Vert$ 。其中$C_r$ 是一个与算法相关的常数。再结合假设3，引理得证。

类似于文献[11]中的命题4，可以证明该算法具有线性收敛速率。随后，本文建立了获得一个近邻纳什均衡所需的迭代复杂度和神谕复杂度，其中近邻纳什均衡定义为满足$E\left[\Vert x-\tilde{x}\Vert \right]$ 条件的随机策略组合$x:\Omega \to R^n$ 。

定理3：若假设3成立，且$\alpha \triangleq \Vert \Gamma \Vert <1$ 。将上述算法应用于随机纳什博弈$\left(P_i\left(x_{-i}\right)\right)$ ，其中$E\left[\Vert x_{i,0}-x_i^{*}\Vert \right]\le C$ ，且对某个$\eta \in \left(0,1\right)$ 有$N_k=\frac{{\max }_i{M}_i^2{C}_r^2}{{\eta }^{2k}}$ 。定义$c\triangleq \max \left\{\alpha ,\eta \right\}$ ，令$\tilde{\eta }\in \left(c,1\right)$ ，并设$D=\frac{1}{\ln \left({\left(\tilde{\eta }/c\right)}^e\right)}$ 。那么，为获得ε-纳什均衡，参与者i需要求解的确定性优化问题的数量和所需的样本数分别为：$O\left(\ln \left(\sqrt{N}/\epsilon \right)\right)$ 和$O\left({\left(\sqrt{N}/\epsilon \right)}^{\frac{2\ln \left(1/\eta \right)}{\ln \left(1/\tilde{\eta }\right)}}\right)$ 。

4. 结论

本文研究了一类随机纳什博弈，其中每个参与者的目标函数由一个期望值形式的光滑函数和一个凸非光滑函数之和构成。基于此，本文提出了两种算法方案：

(1) 可变样本规模近邻梯度响应方案，适用于强单调随机纳什博弈；(2) 可变样本规模近邻最佳响应方案，适用于具有压缩最佳响应映射的随机纳什博弈。在适当的假设条件下，本文证明了两种方案均能生成以最佳线性收敛的序列，并推导了其计算复杂度以及神谕复杂度。