不完全信息博弈中的后悔最小化

在多智能体决策环境中，扩展式博弈作为一种有效模型，尤其适合应对信息不完全的情形。近来，针对大规模扩展式博弈中纳什均衡的求解方法成为学术界关注的重点。本文提出了一种基于后悔最小化原理的创新性技术，旨在应对大规模博弈问题的挑战。

扩展式博弈的基本结构可以表示为一棵博弈树，其形式与完全信息博弈（如国际象棋或围棋）类似。在每一个非终止状态中，都会对应到某个玩家的行动选择；而在每一个终止状态中，则会关联到各参与者的具体收益值。其核心差异体现在信息集这一额外约束条件上——这些信息集代表了玩家无法区分的一组状态，因此在这些状态下所采取的行动必须遵循相同的概率分布。

以扑克游戏为例，在初始阶段进行行动的玩家无法获知其他玩家手中的牌面情况。因此，在发牌之后、该玩家所持有的相同牌型对应的所有博弈状态将被归入同一个信息集中。

扩展式博弈的形式化定义

具有不完全信息的有限扩展式博弈主要由以下几个部分构成：

有限的玩家集合 NN。

有限的序列集合 HH，用于表示可能发生的行动历史。其中空序列属于 HH，并且 HH 中任意一个序列的所有前缀也均包含在 HH 内。Z⊆HZ \subseteq H 表示终止历史，即那些不作为其他任何序列前缀存在的历史。对于非终止历史 h∈Hh \in H，A(h)={a:(h,a)∈H}A(h) = {a : (h,a) \in