动机
双人零和博弈有极小极大值,而无遗憾策略可以逼近最优策略。在一般的多人博弈中,并不存在统一的共同值,也没有单一的对手。然而,只要每个参与者相对于任何固定行动的遗憾都很小,博弈过程的联合经验分布就满足一个有用的均衡条件。
由此得到的对象称为粗相关均衡。一位中介者抽取一个联合行动组合,并私下向每位参与者推荐一个行动。没有参与者能够通过事先承诺某个固定的替代行动而获得显著的好处。中介者可以在各参与者的推荐之间引入相关性;所得结果并不自动是纳什(Nash)均衡,也不自动抵御依赖于推荐内容的偏离。
定义与定理
定义 2.2.1
(粗相关均衡)
共有 位参与者。参与者 拥有非空有限行动集 ,并且对每个行动组合有收益 。若对每位参与者 以及每个固定的替代行动 ,联合分布 满足
则称 为 -粗相关均衡(-coarse correlated equilibrium)。
该替代行动可以依赖于已知的分布,但不能依赖于实际得到的推荐。这里 表示其余所有参与者的行动。
定理 2.2.2
(完全信息无遗憾构造)
对任意 ,下述同时进行的乘性权重过程能为每个收益在 内的有限博弈构造出一个 -粗相关均衡。它是 个乘积分布的均匀混合,其中
为正整数,对数取自然对数。若 ,则一轮即可。
定理 2.2.3
(完全信息遗憾界)
对 个行动、任意损失向量序列 以及 ,取 ,, 的指数权重算法对每个固定行动 满足
损失向量可以在看到当前分布之后才选定;序列一旦固定,该不等式是确定性的。我们假设指数权重与期望均采用精确实数运算。有限精度与抽样的保证需要另行分析。
证明遗憾界
证明
(单一势函数界住每个固定行动)
令 。对 与 ,初等不等式 给出
对 使用 并对各轮求和,得到
对任意固定行动 ,其最终权重为 ,因此 至少等于该值。由于 ,比较对数形式的下界与上界并整理,即证得所示遗憾不等式。证明中没有用到各轮之间的任何独立性。
证明透视
一个势函数控制所有固定偏离
总权重从上方控制学习者累积的期望损失,而任何单一行动的权重则从下方控制同一个总权重。比较这两个界便得到针对该固定行动的保证;这一代数推导对每个行动同时成立。
从无遗憾到联合分布
证明
(对各轮的乘积分布取平均)
在第 轮,每位参与者在 上有一个指数权重分布 。对每个可能的行动 ,通过对其他参与者当前的乘积分布取平均,定义其完全信息损失:
这些损失落在 内。每位参与者用自己的损失向量更新所有行动的权重。这是一个关于精确实数分布的确定性过程;定义更新时无需对行动进行抽样。令 为各轮联合乘积分布 的均匀混合。
对参与者 ,在第 轮乘积分布下实际承受的期望损失为 。对任意固定的 应用遗憾定理,并把损失换回收益,得到
取 以及整数 。这样两项都至多为 ,从而对每位参与者与每个固定偏离证明了粗相关不等式。当 时,任何参与者都没有替代行动,唯一的行动组合在一轮内即为精确均衡。
中介者揭示的信息
从 中抽样的方法是:先均匀地选取一个轮次指标,再从该轮的分布中独立地为每位参与者抽取行动。给每位参与者的推荐就是其抽到的行动。粗相关保证比较的是在收到推荐之前选定的固定替代行动;它并不保证参与者无法通过让偏离依赖于其推荐或隐藏的轮次指标而获益。
反例模式
乘积分布的混合不等于其边缘分布的乘积
以相等概率选取 或 。该分布是两个乘积分布的混合,但其两个边缘分布都是均匀分布,而它们的乘积还会给 与 赋予正概率。把联合混合替换为平均边缘分布的乘积会改变该分布,证明并不支持这样的替换。
的定义保持了各轮混合的完整性。尽管完整的联合表可能很大,它仍可由 个参与者分布列表紧凑地描述。若中介者公开轮次指标,参与者便可依据这一额外信息选择替代行动;上述固定行动的界并不自动涵盖这种更强的偏离。
例题详解
例题 2.2.4
(单一行动的博弈)
若每位参与者恰有一个行动,则唯一的联合组合没有任何不同的单边替代行动。其点质量分布是精确的粗相关均衡。特别处理 的情形,避免了对数界出现零轮的解释问题。
例题 2.2.5
(相关的协调结果)
两位参与者在其二元行动一致时获得收益一,否则为零。对 与 各赋予二分之一概率的分布使每位参与者的期望收益为一。没有任何固定偏离能超过一,因此它是精确的粗相关均衡。其推荐之间是相关的。
例题 2.2.6
(轮数预算)
设每位参与者至多有四个行动且 ,取 与 。由于 ,定理适用。显式遗憾界为每轮 。
例题 2.2.7
(固定的损失序列)
对两个行动与两轮,设第一轮损失为 ,第二轮损失为 。尽管最佳行动在两轮之间改变,遗憾界对任一固定行动仍然适用。它并不是把学习者与可在看到每个损失向量后自由切换的比较者相比。
常见错误
常见错误
(逐轮更换替代行动)
应用所示遗憾不等式时,每一轮必须使用同一个固定偏离。能看到抽到的轮次或推荐的参与者,可以在不同情形下选择不同的偏离;那是更强的基准。粗相关均衡的定义恰好与固定行动的比较相匹配。
单轮之内的乘积分布假设各参与者在给定该轮的条件下独立抽样。跨轮的混合可以产生相关性。先取乘积再平均,与先平均再取乘积,是不同的运算,如反例所示。
常见错误
(近似粗相关均衡不是纳什均衡)
该证明构造的是近似粗相关均衡,不一定是纳什均衡,也不一定是依赖于推荐的相关均衡。在双人零和博弈中,可通过额外的论证提取近似极小极大策略;任意的多人收益则需要各自的结论。
计算与表示
对于显式列出的标准型博弈,每一轮的损失向量可通过对收益表与当前乘积概率求和来计算。每轮所需的算术运算次数是该显式表规模的多项式,而所述轮数是 与最大行动数对数的多项式。若博弈仅由简洁电路或谕示给出,计算这些期望的代价可能不同。
定理假设指数与概率均采用精确实数运算。因此它给出的是算术运算次数与精确的数学分布,而不是经过认证的多项式比特时间实现。有限精度的实现必须界定累积误差及其对每个偏离不等式的影响。抽样版本的博弈还必须考虑抽样误差;这两个问题都没有被隐含在确定性的期望收益证明之中。
参与者人数可以任意,但显式收益表对每个联合行动组合与每位参与者各有一项。当每位参与者都有多个行动时,关于该表规模为多项式的运算次数,仍可能是参与者人数的指数。这是输入表示方式上的区别,并不与有限轮数的界相矛盾。
展开收益比较
对固定的参与者与轮次,把损失的定义代入学习者的期望损失。由于在给定该轮的条件下,参与者自身的混合行动与其他参与者相互独立,结果等于一减去完整乘积分布下的期望收益。固定替代行动的损失则是一减去仅替换该参与者分量后所得的期望收益。相减时两个一互相抵消。对所得不等式在各轮上取平均,恰好就是 下期望的定义。
同时更新并不产生循环选择。每一轮开始时,所有分布都由前几轮的权重所确定。该过程先由这些当前分布计算全部期望损失向量,再更新所有权重以进入下一轮。损失向量可能通过其他参与者的选择而依赖于该参与者当前的分布,但势函数的证明对每个一经给定的向量都成立。它不要求有独立的对手,也不要求各轮损失相互独立。
作为极限的精确存在性
有限轮数的构造同时给出精确粗相关均衡的存在性论证。取趋于零的序列 ,并对每个取值构造相应的分布 。所有联合分布都位于有限维概率单纯形中,该单纯形是紧致的,因此存在子列收敛到某个分布 。对每位参与者与每个固定的替代行动,粗相关不等式关于联合分布是线性且连续的。沿该子列取极限即消去了误差,表明 是精确的。
这一论证证明至少存在一个极限点满足要求。它并不说明整个分布序列收敛,也不提供有限时间内的精确有理表示。近似构造及其有限轮数预算仍是上文所建立的算法性结论。
小型博弈中的偏离检验
在二元协调的例子中,承诺永远出零的参与者,在对方推荐为零时获得收益一,在对方推荐为一时获得收益零。因此其偏离的期望收益为二分之一,而遵从推荐的收益为一。永远出一的情形计算相同。只需检验这两个固定行动即可,因为任何固定混合偏离的收益都是它们收益的凸组合。
最后这一观察可以推广:要验证一个粗相关均衡能抵御所有固定的混合偏离,只需检验每个固定纯行动。混合偏离的收益是相应纯偏离收益的加权平均,不可能超过其中最大的纯偏离收益。这一有限的不等式列表,正是遗憾界所控制的那一列。
概念视角几何
均衡构成一个多面体
固定一个博弈,并用 表示联合行动组合上的概率分布单纯形。每个纯替代行动 对 贡献一个线性不等式,即上述条件。因此 -粗相关均衡就是 与 个闭半空间的交集:一个凸多面体,而由上文的构造可知它非空。均衡的混合仍是均衡;在显式收益表上寻找一个均衡,就是一个线性可行性问题。
总结
指数权重法界定了每位参与者相对于每个固定行动的遗憾。把该界应用于期望的完全信息损失,并对各轮的乘积分布取平均,便得到一个近似粗相关均衡。中介者所掌握的信息、联合混合以及精确运算的假设,都是该保证的一部分。
练习
快速检查
(为什么遗憾定理允许损失向量依赖于当前的行动分布?)
看势函数证明在哪一步用到 。
解答 · 答案
势不等式对 中每个已实现的损失向量都成立,并不使用其与当前分布的独立性。对这些逐点不等式求和即得该界。
快速检查
(若所有参与者都只有一个行动,为什么一轮就能产生精确均衡?)
参与者还能考虑哪个替代行动?
解答 · 答案
不存在不同的单边行动,因此对唯一的组合,每个粗相关不等式都以等号成立。
快速检查
(在二元协调的例子中,对角混合下任一参与者的期望收益是多少?)
分别计算支撑集中两个行动组合的收益。
解答 · 答案
为一:支撑集中的两个组合行动均一致,收益均为一。
快速检查
(为什么固定偏离的保证并不自动涵盖依赖于抽到的推荐的偏离?)
比较事先固定的替代行动与看到建议后才选择的替代行动。
解答 · 答案
这样的偏离可以在不同的推荐情形下选择不同的替代行动。定理只与在所有轮次和推荐下都固定不变的单一行动作比较。