多智能体学习中的探索性开发:突变理论与博弈论的结合

1 文章信息

Exploration-Exploitationin Multi-Agent Learning: Catastrophe Theory Meets Game Theory 这是新加坡设计大学发表在计算机顶级会议AAAI2021上的一篇文章。

2 摘要

探索和开发是多智能体学习（MAL）中一个有力实用的工具，为理解其效果，作者探究了一种Q-learning的平滑模拟。作者首先表明，其学习模型作为研究探索-开发的最佳模型有很强的理论合理性。具体来说，作者证明了平滑的Q-learning 在任意博弈中对于明确地捕捉到的博弈成本和探索成本之间的平衡的成本模型存在约束，并且在异质学习智能体的加权潜在博弈中总能收敛到量化响应均衡（QRE）。作者接着转向测量探索对集体系统性能的影响，描述了低维MAL系统中QRE面的几何特征，并将其发现与灾难（分叉）理论联系起来。特别是，随着探索超参数随时间的演变，系统经历了阶段转换，在这种情况下，给定探索参数的无限小变化，平衡的数量和稳定性可以发生根本性变化。在此基础上，作者提供了一个形式化的理论处理方法，以证明调整探索参数可以达到平衡选择，同时对系统性能产生积极以及消极（和潜在的无限制）的影响。

3 动机

尽管在行为建模和人工智能方面都取得了显著的进展，但是即使在简单的设置中，MAS的理论学习仍然存在很大的不完整性。虽然还没有理论来证实的解释MAL算法的性能，特别是在“the effects ofexploration in MAS”， 但现有的研究表明，在无状态矩阵博弈中已经出现了许多探索的病态，在这些博弈中，自然出现的集体学习动态表现出不同的结果。缺少正式理论的原因是多方面的，首先即使没有探索，博弈中MAL也会产生难以分析的复杂行为。一旦强制进行探索，在线学习的行为变得更加难以解决，因为纳什均衡不在是智能体长久固定的目标。最后如果参数改变得足够多，那么我们就会得到分叉现象和可能的混乱。

4 模型构建

作者研究了无状态Q-learning 的平滑变体通过softmax或者Boltzmann探索，成为Boltzmann Q-learning 或 平滑Q-learning（SQL）,每个智能体通过以下规则更新选择的分布

 （1）

• 定义1. 动力学方程：

  
  （2）
  
  （3）

• 定义2. Bounded regret：为了衡量(1)中SQL动态的性能，我们将使用累计的标准概念。

  
  是agent k在SQL动态生成的游戏序列与事后看来直到时间T的最佳可能选择之间的不同奖励,如果满足当T区域无穷时
  
  ，则agent具有Bounded regret.
  

• 定义3. 考虑改变后的设置

  
  ，然后每一个智能体根据动力学方程更新其选择分布的有Bounded regret.

• 定义4. 在异质智能体的加权势博弈中收敛到QRE. 如果存在一个函数

  
  和一个正权重的向量
  
  ，则Γ被称为加权势游戏

• 定义5. 如果

  
  承认潜力函数
  
  ，那么(1)中SQL动态生成的序列就会收敛到一个紧凑连接的Γ的QRE。

• 定义6. 使

  
  定义为
  
  的潜在函数，并且考虑
  
  ，则
  
  是改变后后博弈的潜在函数。

5 实验结果

实验设置

作者从2×2的协调游戏开始，然后进行具有任意大小的行动空间的潜在游戏。在所有情况下，作者考虑两种具有代表性的探索-开发政策：一种是探索-然后-开发（ETE）策略，从（相对）高探索开始，线性地减少到零；另一种是一个周期的循环学习率（CLR-1）策略，从低探索开始，在周期中间增加到高探索，并衰减到（最终）零探索（即纯开发）。分别进行帕累托实验和猎鹿实验。

实验结果

7 创新点

研究了无状态Q-learning的平滑变体使用softmax或Boltzmann探索称为Boltzmann Q-learning或平滑Q-learning（SQL）                 

1. 证明了平滑的Q-learning在任意博弈中对于明确地捕捉到的博弈成本和探索成本之间的平衡的成本模型句存在约束

2. 描述了低维MAL系统中QRE面的几何特征，并将其发现与灾难（分叉）理论联系起来

3. 提供了一个形式化的理论处理方法，以证明调整探索参数可以达到平衡选择，同时对系统性能产生积极以及消极（和潜在的无限制）的影响

8 参考文献

S. Leonardos, and P. Georgios,'Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory MeetsGame Theory.' (2020).

Attention

如果你和我一样是轨道交通、交通运输、城市规划相关领域的，也愿意分享自己的科研生活，请加微信：Dr_JinleiZhang，备注“进群”，我会拉你进交通大数据分享群！希望我们共同进步！