摘要

本文研究了具有恒定学习率的指数权重算法（Exponential Weights Algorithm）在离散时间重复交互中的最终迭代收敛性质。文章考虑了多个玩家独立使用指数权重算法的情况，并分析了混合策略轮廓（mixed action profile）pt在不同阶段的行为。文章证明了在存在严格纳什均衡（strict Nash equilibrium）的情况下，玩家在下一阶段选择严格纳什均衡的概率几乎必然收敛到0或1。此外，文章还证明了pt的极限，如果存在，属于“纳什均衡与等额支付”（Nash Equilibria with Equalizing Payoffs）集合。在强协调游戏中，玩家的支付在所有玩家选择相同行动时为正，否则为0，文章证明了pt几乎必然收敛到某个严格纳什均衡。文章最后提出了一些开放问题。

原理

指数权重算法的核心思想是，在每个阶段t ≥ 0，每个玩家i根据其混合策略pt i随机选择一个行动，然后观察其随机向量支付（每个可能行动对应一个坐标），这取决于其他玩家的实际行动。在下一阶段t + 1，玩家i选择每个行动的概率与该行动在过去所有阶段支付的指数和成正比，乘以一个学习率ηi。这种算法通过不断调整行动的概率分布，使得玩家能够逐步学习并收敛到最优策略。

流程

1. 初始化：每个玩家i选择一个初始混合策略p0 i。
2. 行动选择：在每个阶段t，玩家i根据当前的混合策略pt i随机选择一个行动。
3. 支付观察：玩家i观察到其支付向量，该向量取决于其他玩家的行动。
4. 策略更新：玩家i根据观察到的支付更新其混合策略pt+1 i，使得每个行动的概率与该行动过去支付的指数和成正比。
5. 重复步骤2-4，直到达到某个停止条件（如达到最大阶段数或策略收敛）。

应用

指数权重算法在计算几何、优化、运筹学、在线统计决策和机器学习等多个领域有广泛应用。特别是在多玩家交互和学习算法的研究中，该算法提供了一种有效的策略更新机制，有助于玩家在复杂环境中找到最优策略。未来，该算法可能在更广泛的博弈论和人工智能应用中发挥重要作用。