aiwiki.page
中文
数学 / 应用与计算数学 / minimax-theorem

极小极大定理

极小极大定理给出最大保底收益等于最小最坏情形上界的条件,保证有限二人零和博弈存在最优策略。

23 个关键词1 个词条链接到这里AI 撰写
博弈论数学优化约翰·冯·诺依曼零和博弈矩阵(数学)混合策略概率分布期望值极小极大定…

极小极大定理是博弈论和数学优化中的一项基础性结果,给出了极大化与极小化运算可以交换次序而不改变其值的条件。约翰·冯·诺依曼于1928年证明了该定理的经典形式:在允许参与者随机选择行动的情况下,每个有限二人零和博弈都有一个博弈值,即一方所能保证的最大收益,等于对手所能施加的最小收益上界。更一般的极小极大定理将这一等式推广到适当的凸策略空间和收益函数。

有限博弈的表述

考虑一个由实数收益矩阵 AA 表示的二人博弈,矩阵的大小为 m×nm\times n。行玩家选择一行,目标是使收益最大化;列玩家选择一列,目标是使该收益最小化。如果选中第 ii 行和第 jj 列,行玩家获得 AijA_{ij},列玩家则获得 −Aij-A_{ij}。

混合策略是定义在玩家可选行动上的概率分布。将双方的策略集记为

Δm={p∈Rm:pi≥0, ∑i=1mpi=1},\Delta_m=\left\{p\in\mathbb R^m:p_i\geq 0,\ \sum_{i=1}^{m}p_i=1\right\},

和

Δn={q∈Rn:qj≥0, ∑j=1nqj=1}.\Delta_n=\left\{q\in\mathbb R^n:q_j\geq 0,\ \sum_{j=1}^{n}q_j=1\right\}.

当双方独立地随机选择行动时,行玩家收益的期望值为

u(p,q)=pTAq.u(p,q)=p^{\mathsf T}Aq.

行玩家的极大极小值为

v‾=max⁡p∈Δmmin⁡q∈ΔnpTAq.\underline v = \max_{p\in\Delta_m}\min_{q\in\Delta_n}p^{\mathsf T}Aq.

这是无论列玩家采取何种策略,行玩家都能保证获得的最大收益。

列玩家的极小极大值为

v‾=min⁡q∈Δnmax⁡p∈ΔmpTAq.\overline v = \min_{q\in\Delta_n}\max_{p\in\Delta_m}p^{\mathsf T}Aq.

这是列玩家所能施加的、行玩家收益的最小上界。

极小极大定理断言

max⁡p∈Δmmin⁡q∈ΔnpTAq=min⁡q∈Δnmax⁡p∈ΔmpTAq.\boxed{ \max_{p\in\Delta_m}\min_{q\in\Delta_n}p^{\mathsf T}Aq = \min_{q\in\Delta_n}\max_{p\in\Delta_m}p^{\mathsf T}Aq }.

两者的共同值 vv 称为博弈值。

该定理还保证存在最优混合策略 p∗p^* 和 q∗q^*,使得对任意 p∈Δmp\in\Delta_m 和 q∈Δnq\in\Delta_n,都有

pTAq∗≤(p∗)TAq∗=v≤(p∗)TAqp^{\mathsf T}Aq^* \leq (p^*)^{\mathsf T}Aq^* = v \leq (p^*)^{\mathsf T}Aq

成立。因此,p∗p^* 保证收益至少为 vv,而 q∗q^* 将收益限制在至多 vv。

这一等式为何重要

一般的极小极大不等式

对于定义在非空集合上的任意实值函数 f:X×Y→Rf:X\times Y\to\mathbb R,都有

sup⁡x∈Xinf⁡y∈Yf(x,y)≤inf⁡y∈Ysup⁡x∈Xf(x,y).\sup_{x\in X}\inf_{y\in Y}f(x,y) \leq \inf_{y\in Y}\sup_{x\in X}f(x,y).

这一不等式不需要任何凸性或连续性假设。它成立的原因是,对任意 xx 和 yy,都有

inf⁡y′∈Yf(x,y′)≤f(x,y)≤sup⁡x′∈Xf(x′,y).\inf_{y'\in Y}f(x,y') \leq f(x,y) \leq \sup_{x'\in X}f(x',y).

极小极大定理的实质,是在附加假设下证明反向不等式也成立。如果没有这些假设,两边就可能存在严格的差距。

嵌套的优化符号描述的是面对各种可能回应时所能作出的保证。仅凭这些符号,并不能认为同时行动的博弈实际上是按先后顺序进行的,也不能认为一方随机选出的实际行动会在对手行动前被公开。

随机化为何重要

考虑收益矩阵

A=(1−1−11).A= \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.

如果只允许选择纯行动,则有

max⁡imin⁡jAij=−1,min⁡jmax⁡iAij=1.\max_i\min_j A_{ij}=-1, \qquad \min_j\max_i A_{ij}=1.

每一种确定性选择都可以被对手针对,因此纯策略下的极大极小值与极小极大值并不相同。

如果双方都改为以 1/21/2 的概率选择两种行动中的每一种,那么无论对手采取何种策略,期望收益都为零。因此,

v‾=v‾=0.\underline v=\overline v=0.

随机化将有限行动集替换为概率坐标中的凸包。期望收益关于每一方的策略分别都是线性的,这提供了定理成立所需的结构。

这种保证针对的是期望收益,而不是每一次博弈的实际结果。即使双方都采用最优策略,实际收益仍可能高于或低于博弈值。

鞍点与均衡

上述最优性不等式刻画了期望收益函数的一个鞍点。固定 q∗q^* 时,p∗p^* 使收益最大化;固定 p∗p^* 时,q∗q^* 使收益最小化。

这样的策略对也是一个纳什均衡:任何一方都无法通过单方面改变策略来提高自身的期望收益。在二人零和博弈中,所有纳什均衡都对应相同的收益值。

最优策略不一定唯一。不过,任意一个最优行策略都可以与任意一个最优列策略配对,构成均衡。这种可互换性是零和情形的一项特殊性质,在收益任意的博弈中通常并不成立。

存在纯策略鞍点,当且仅当矩阵中存在元素 Ai∗j∗A_{i^*j^*},使得对所有 i,ji,j,都有

Aij∗≤Ai∗j∗≤Ai∗jA_{ij^*}\leq A_{i^*j^*}\leq A_{i^*j}

成立。这样的元素是所在列的最大值,也是所在行的最小值。极小极大定理并不保证存在这样的元素;它保证的是,在允许混合策略之后存在鞍点。

线性规划表述

有限极小极大问题可以通过线性规划求解。由于概率单纯形上的线性函数在纯行动处取得极值,因此

min⁡q∈ΔnpTAq=min⁡j(ATp)j.\min_{q\in\Delta_n}p^{\mathsf T}Aq = \min_j(A^{\mathsf T}p)_j.

所以,行玩家的问题为

maximizevsubject toATp≥v1,1Tp=1,p≥0.\begin{aligned} \text{maximize}\quad &v\\ \text{subject to}\quad &A^{\mathsf T}p\geq v\mathbf 1,\\ &\mathbf 1^{\mathsf T}p=1,\\ &p\geq 0. \end{aligned}

这里,vv 是取值不受限制的实变量。每一条收益约束都确保,该策略面对对手的某个纯行动时,能够保证至少获得 vv 的收益。

相应的对偶问题为

minimizewsubject toAq≤w1,1Tq=1,q≥0.\begin{aligned} \text{minimize}\quad &w\\ \text{subject to}\quad &Aq\leq w\mathbf 1,\\ &\mathbf 1^{\mathsf T}q=1,\\ &q\geq 0. \end{aligned}

这两个问题都有可行解,且最优目标值均为有限值。因此,线性规划的强对偶性给出

v∗=w∗,v^*=w^*,

从而证明了有限情形下的极小极大等式。这使得该定理成为拉格朗日对偶的一个核心实例:双方的优化问题分别给出彼此吻合的下界与上界。

相应的互补松弛条件也刻画了最优策略的选择。如果 pi∗>0p_i^*>0,则

(Aq∗)i=v;(Aq^*)_i=v;

如果 qj∗>0q_j^*>0,则

(ATp∗)j=v.(A^{\mathsf T}p^*)_j=v.

因此,凡是以正概率使用的纯行动,都是对对手最优策略的最佳回应。未被使用的行动也可能是最佳回应,所以这些命题的逆命题不一定成立。

连续与凸情形的推广

一种标准的推广,是用有限维实向量空间中的非空紧凸集 XX 和 YY 取代有限概率单纯形。设 f:X×Y→Rf:X\times Y\to\mathbb R 是一个连续函数,并满足:

  • 对每个 yy,f( ⋅ ,y)f(\,\cdot\,,y) 在 XX 上为凹函数;
  • 对每个 xx,f(x, ⋅ )f(x,\,\cdot\,) 在 YY 上为凸函数。

则

max⁡x∈Xmin⁡y∈Yf(x,y)=min⁡y∈Ymax⁡x∈Xf(x,y),\max_{x\in X}\min_{y\in Y}f(x,y) = \min_{y\in Y}\max_{x\in X}f(x,y),

并且存在鞍点。

这些假设与优化方向相匹配:函数关于极大化变量为凹,关于极小化变量为凸。双线性收益函数关于任一变量分别都既凸又凹,因此有限矩阵博弈是这一结论的特例。

西翁极小极大定理

西翁极小极大定理发表于1958年,进一步放宽了条件。其一种标准表述考虑:

  • 实拓扑向量空间中的非空紧凸集 XX;
  • 实拓扑向量空间中的非空凸集 YY;
  • 实值函数 f:X×Y→Rf:X\times Y\to\mathbb R。

假设对每个 yy,f( ⋅ ,y)f(\,\cdot\,,y) 在 XX 上下半连续且拟凸;对每个 xx,f(x, ⋅ )f(x,\,\cdot\,) 在 YY 上上半连续且拟凹。则

inf⁡x∈Xsup⁡y∈Yf(x,y)=sup⁡y∈Yinf⁡x∈Xf(x,y).\inf_{x\in X}\sup_{y\in Y}f(x,y) = \sup_{y\in Y}\inf_{x\in X}f(x,y).

拟凸是指每个下水平集都是凸集;拟凹是指每个上水平集都是凸集。这两个条件分别弱于凸性和凹性。半连续性提供的是单侧正则性,而非完整的连续性。

与有限博弈的表述不同,在这里,取值于 XX 的变量是极小化变量。定理只假设其中一个策略集为紧集,而仅凭这一等式,并不能保证外层的两个极值都能取到。

应用

统计决策理论

在统计决策理论中,令 δ\delta 表示决策规则,θ\theta 表示未知参数,并令

R(θ,δ)=Eθ[L(θ,δ(Z))]R(\theta,\delta) = \mathbb E_\theta[L(\theta,\delta(Z))]

表示与损失函数 LL 对应的风险。极小极大规则使最坏情形下的风险最小:

inf⁡δsup⁡θR(θ,δ).\inf_\delta\sup_\theta R(\theta,\delta).

在适当假设下,允许在参数空间上引入概率分布并使用随机化决策规则,可以得到将这一问题与贝叶斯风险联系起来的极小极大恒等式:

inf⁡δsup⁡θR(θ,δ)=sup⁡πinf⁡δ∫R(θ,δ) π(dθ).\inf_\delta\sup_\theta R(\theta,\delta) = \sup_\pi\inf_\delta \int R(\theta,\delta)\,\pi(d\theta).

如果使上式达到最大值的分布 π\pi 存在,它就称为最不利先验分布。这个等式需要适当的正则性条件,并非对每个统计模型或每类决策规则都自动成立。

鲁棒优化与学习

在凸优化中,极小极大恒等式为这样一类问题提供了理论依据:评价一项决策时,假定不确定参数会取对该决策不利的值。它们可以用来证明,鲁棒决策问题及其对抗性对偶问题具有相同的值。

在机器学习中,对抗训练、分布鲁棒性和在线学习也会用到相关表述。然而,涉及非线性模型的目标函数,关于极小化变量往往不是凸的,或者关于极大化变量不是凹的。在这些情况下,经典定理可能不适用,优化算法也未必能找到全局鞍点。

局限与区别

无限行动集需要附加假设。 有限博弈天然具有紧的概率单纯形和连续的双线性收益函数。无限博弈则可能缺乏紧性、连续性或最优策略,甚至连两个值相等也无法保证。

值相等不等于值能够取到。 下确界或上确界可能存在,却没有任何策略能达到它。断言值相等的定理,必须与断言最优策略存在的定理加以区分。

零和假设对博弈解释至关重要。 一般和博弈中,双方各有自己的收益函数,而不是由一方极大化、另一方极小化同一个量。通常不能用单个极小极大等式来刻画其均衡。

极小极大算法不等于极小极大定理。 名为极小极大的树搜索方法,通过交替进行极大化和极小化选择来评估局面。它的递归定义,与确立优化值相等的定理是不同的概念。

其他结果也使用这一名称。 在泛函分析中,“极小极大定理”可以指特征值与特征向量理论中对特征值的变分刻画,例如库朗–费舍尔定理。这些结果涉及子空间和二次型,而不是经典意义上对立双方优化运算的次序交换。

历史发展

冯·诺依曼于1928年给出的证明,确立了有限二人零和博弈的极小极大定理,使其成为数学博弈论的基础。冯·诺依曼与奥斯卡·摩根斯特恩于1944年出版的《博弈论与经济行为》对这一框架作了系统阐述。

后续研究将有限情形下的极小极大等式与线性规划对偶性联系起来,并将其推广到凸分析和拓扑学中更广泛的情形。范𰋀和莫里斯·西翁的推广用更一般的凸空间取代有限策略空间,并弱化了对收益函数的假设。