MARL综述阅读
多智能体强化学习:理论与算法选讲
这篇是Arxiv上的一篇综述论文,主要介绍了多智能体强化学习的理论与算法,因为在看了几篇MARL新的文章之后发现根基不稳,需要补一些理论基础和其他算法的知识,所以挑了一篇比较经典的。看着挺难读,正文就有47页,引用文献数量达383,写的很不错可惜有点早了2021年的。 注意部分内容是我补充上去的,部分内容也有所修改,虽然严谨性可能大打折扣,但是至少比原文好读,方便自己之后查阅。 论文地址: https://arxiv.org/abs/1911.10635 这里贴上作者的github页面,确实是行业内的专家,譬如这篇论文被引就达2k https://kzhang66.github.io/ 有一点很重要,笔记的定义为是半翻译半讲述,其中有相关专业术语翻译不一定准确的会标出英文原文。 对于 distributed 翻译为分布式,decentralized 翻译为去中心,fully decentralized 翻译为分散式
摘要
MARL 的理论在上世纪就提出来了,但是直到单智能体有所突破才重新焕发生机,现在的 MARL 虽然验证效果不错,但是理论相对薄弱,作者强调他们只是选择性讲了一些理论:重点聚焦有理论支撑的算法体系。把任务分为三类,分别是完全合作任务、完全竞争任务和混合任务。问题建模框架主要选择讲马尔可夫/随机博弈和扩展形式博弈(Extensive-Form Games)。涉及一些新颖的视角和分类体系例如:扩展式博弈中的学习、网络化智能体的去中心(Decentralized)学习、平均场(Mean Field)框架下的多智能体学习、博弈学习中策略梯度方法。
介绍
MARL 致力于解决多个自主智能体在共同环境中的序贯决策(Sequential Decision-Making)问题——每个智能体都通过与环境及其他智能体的交互,来优化自身长期回报。 总得来说,MARL 根据应用场景分为三类:完全合作任务——智能体协作优化共同的长期回报;竞争场景——智能体的回报通常为零和或常和;混合任务——智能体的回报通常为一般和(就是除去前两种和的类型之外的最一般的回报类型),对 MARL 问题建模需要 “优化理论,动态规划,博弈论,去中心控制” 等多种理论工具,但是不同理论在建模中遇到的问题是有共性的,譬如:学习目标多维,即不同智能体间目标不一定一致,很难处理均衡点(是指均衡点的多重性等问题);优化结果外的其他性能也不好衡量,例如通信效率或者说协调效率,对潜在的对抗性智能体的鲁棒性;由于每个智能体都根据自身利益同步优化策略,导致对于单个智能体而言环境呈现非平稳性,(平稳性和非平稳性简单地可以理解为,如果时序数据,其主要统计量与时间无关即为平稳的,若与时间有关则为非平稳的)这打破了单智能体的理论框架;联合动作空间会随智能体数量增加呈现指数级增长,可能引发扩展性问题,称为 MARL 的组合复杂性;MARL中的信息结构(即智能体间的信息分布)更为复杂,由于每个智能体对其他智能体观测信息的获取受限,可能导致局部决策规则陷入次优困境。 研究者们致力于解决上述挑战,结合深度学习、运筹学和多智能体系统等领域的最新进展,涌现出诸多创新性研究成果。然而,这些成果普遍缺乏坚实的理论基础——单智能体深度强化学习的理论体系尚未成熟,多智能体场景的复杂性又进一步加剧了理论分析的难度。为此,作者系统梳理了具有理论保证的 MARL 算法,撰写此综述以明确当前研究的边界,并为该领域的未来发展提供方向性指引。 作者选择重点阐述离散时间框架下的两类代表性建模范式:扩展形式博弈和马尔科夫或者说随机博弈。也总结到现有的新视角与新的分类体系:基于作者的早期研究的智能体网络化分布式 MARL ;引入均值场博弈体系作为超大规模智能体群体的解决方案;优化理论新突破对策略梯度类方法收敛性(特别是零和博弈场景)的理论启示。作者甚至评述了部分观测场景下的 MARL 研究(未采用深度强化学习作为启发式解决方案)。
背景
单智能体
RL 中,智能体通过与环境交互进行序贯决策,环境通常被建模为无限时域折扣马尔可夫决策过程。 定义: 马尔可夫决策过程(MDP)由一个五元组 \((\mathcal{S}, \mathcal{A}, P, R, \gamma)\) 定义,其中 \(\mathcal{S}\) 与 \(\mathcal{A}\) 分别表示状态空间与动作空间;\(P: \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})\) 表示在动作 \(a \in \mathcal{A}\) 作用下,从任意状态 \(s \in \mathcal{S}\) 转移到任意状态 \(s' \in \mathcal{S}\) 的转移概率;\(R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}\) 为奖励函数,决定智能体在从 \((s, a)\) 转移到 \(s'\) 时获得的即时奖励;\(\gamma \in [0, 1)\) 为折扣因子,用于权衡即时与未来奖励。 作为标准模型,MDP 被广泛用于刻画在完全可观测系统状态 \(s\) 下的单智能体决策过程。每个时刻 \(t\),智能体面对系统状态 \(s_t\) 选择动作 \(a_t\),使系统转移到 \(s_{t+1} \sim P(\cdot \mid s_t, a_t)\),同时获得即时奖励 \(R(s_t, a_t, s_{t+1})\)。求解 MDP 的目标是找到一个策略 \(\pi: \mathcal{S} \to \Delta(\mathcal{A})\),即将状态空间映射到动作空间的分布,使得 \(a_t \sim \pi(\cdot \mid s_t)\),并最大化如下折扣累计奖励:
$$ \mathbb{E}\!\left[ \sum_{t \ge 0} \gamma^{t} R(s_t, a_t, s_{t+1}) \,\middle|\, a_t \sim \pi(\cdot \mid s_t),\, s_0 \right]. $$因此,可定义策略 \( \pi \) 下的动作价值函数( Q 函数)与状态价值函数( V 函数)为
$$ Q_\pi(s, a) = \mathbb{E}\!\left[ \sum_{t \ge 0} \gamma^{t} R(s_t, a_t, s_{t+1}) \,\middle|\, a_t \sim \pi(\cdot \mid s_t), a_t = a, s_0 = s \right], $$$$ V_\pi(s) = \mathbb{E}\!\left[ \sum_{t \ge 0} \gamma^{t} R(s_t, a_t, s_{t+1}) \,\middle|\, a_t \sim \pi(\cdot \mid s_t), s_0 = s \right]. $$对任意 \(s \in \mathcal{S}\) 与 \(a \in \mathcal{A}\),上述两个量分别表示从 \((s_0, a_0) = (s, a)\) 与 \(s_0 = s\) 出发的折扣累计回报(从当前状态 \( s \) ,采取动作 \( a \) 之后的折扣累计回报是 Q 函数,衡量状态动作对的预期回报,从当前状态 \( s \) 之后的折扣累计回报是 V 函数,衡量状态的预期回报,两者均由贝尔曼方程导出)。对应于最优策略 \(\pi^*\) 的两者通常分别称为最优动作价值函数与最优状态价值函数。 利用马尔可夫性质,最优策略可以通过动态规划或者说向后归纳的方法,例如价值迭代与策略迭代算法,获得。这类方法需要已知模型信息,即转移概率以及奖励函数的形式。而强化学习旨在在未知模型的条件下找到这样的最优策略,智能体可以通过与环境交互收集的经验来学习策略。 总的来说,RL 算法大致可以分为两大类:基于价值的方法与基于策略的方法。
基于价值的方法
基于价值的强化学习方法旨在求得状态动作价值函数的良好估计,即最优 \(Q\) 函数 \(Q_{\pi^*}\)。随后可以通过对该 \(Q\) 函数估计采取贪心动作来提取(近似)最优策略。 最常见的价值类算法是 Q-learning ,其中智能体维护对 \(Q\) 值函数的一个估计 \(\hat Q(s, a)\)。当从状态-动作对 \((s, a)\) 转移到下一状态 \(s'\) 时,智能体获得回报 \(r\),并按如下规则更新 Q 函数:
$$ \hat Q(s, a) \leftarrow (1 - \alpha)\hat Q(s, a) + \alpha\big[r + \gamma \max_{a'} \hat Q(s', a')\big], $$基于最优贝尔曼方程。其中 \(\alpha > 0\) 是步长或称学习率,\( \gamma \) 乘的是下一状态所有可能动作中 \(Q\) 值最大的动作(对应“最优动作”假设)。在满足 Robbins–Monro 步长条件、每个状态-动作对被无限访问、回报有界且 \(\gamma < 1\) 的前提下,Q-learning 在有限状态与动作空间中几乎必然收敛到最优 \(Q\) 值函数。因此与深度神经网络结合就有了 DQN、DDQN、Dueling DQN、Rainbow DQN,在雅达利游戏中的测试表现良好。 还有 SARSA ,与 Q-learning 更新方式略有不同:
$$ \hat Q(s, a) \leftarrow (1 - \alpha)\hat Q(s, a) + \alpha\big[r + \gamma \hat Q(s', a')\big], $$基于策略贝尔曼方程,优化当前策略 \(\pi\) 下的动作价值函数 \(Q_\pi(s, a)\),其中 Q-learning 的最大化项被换成下一个状态和动作的 \(Q\) 值(\(a'\) 由当前策略选出)。其收敛性通常要求 GLIE(Greedy in the Limit with Infinite Exploration):在保证每个状态-动作对被无限访问的同时,探索强度随时间递减并最终趋于贪心;再配合 Robbins–Monro 步长条件与有界回报,即可在有限空间下收敛。SARSA 相比 DQN 系列更稳健,因为它为同策略学习,不使用“最乐观”的最大化估计,降低了过估计风险。 还有 MCTS(蒙特卡洛树搜索),通过蒙特卡洛模拟构建搜索树来进行近似规划;树策略用于在搜索中平衡探索与利用。常见做法是将 UCB1 应用于树的每个节点(UCT),或采用带先验的 PUCT。MCTS 本身不必使用 DNN,但在 AlphaGo/AlphaZero 等方法中,MCTS 与策略和价值网络结合以提升搜索质量。 强化学习中与 \(Q\) 函数相关的还有策略评估任务:给定策略 \(\pi\),评估其好坏,本质上是估计其值函数(\(V_\pi(s)\) 或 \(Q_\pi(s, a)\))。可以使用 TD 学习(例如 TD(0)):
$$ V(s) \leftarrow V(s) + \alpha\big[r + \gamma V(s') - V(s)\big], $$对于表格或线性函数的值函数,满足适当的步长条件与平稳马尔可夫过程假设时,TD(0) 收敛到投影贝尔曼固定点;但在非线性函数逼近下一般不保证收敛,因此需额外的正则化或算法设计(如目标网络、经验回放等)。
基于策略的方法
另一类强化学习算法直接在策略空间上进行搜索,策略通常由参数化的函数逼近器(如神经网络)估计,逼近器目标是近似 \(\pi(\cdot \mid s) \approx \pi_\theta(\cdot \mid s)\)。因此,最直接的思路是沿长期回报的梯度方向更新参数,这一思想由策略梯度(PG)方法实现。其关键前提是 PG 的闭式表达式:
$$ \nabla J(\theta) = \mathbb{E}_{\,a\sim \pi_\theta(\cdot \mid s),\, s \sim \eta_{\pi_\theta}} \big[\, Q_{\pi_\theta}(s, a)\, \nabla \log \pi_\theta(a \mid s) \,\big], $$其中 \(J(\theta)\) 与 \(Q_{\pi_\theta}\) 分别是策略 \(\pi_\theta\) 下的期望回报与 \(Q\) 函数;\(\nabla \log \pi_\theta(a \mid s)\) 是策略的得分函数(对数概率的梯度),即把“在状态 \(s\) 选择动作 \(a\)”这件事的概率往更大/更小推的方向;\(\eta_{\pi_\theta}\) 是策略 \(\pi_\theta\) 下的状态占用测度,可以认为是状态在策略下的概率分布,区别在于如果状态占用测度没有折扣,那么它就是状态在策略下出现的概率分布,与初始状态无关,只考虑长期来看,每个状态在策略下出现的概率分布,如果状态占用测度是折扣形式,那么它会和初始状态相关,并且其概率会随乘时间步的折扣,这会使概率分布具有时间偏见性。 有策略参数的更新规则:
$$ \theta \leftarrow \theta + \alpha \nabla J(\theta), $$其中 \(\alpha > 0\) 是步长/学习率。 根据 PG 的计算方式不同可划分为两类:随机 PG 与确定 PG。 对于随机 PG:REINFORCE 用蒙特卡洛的似然比或者得分函数来估计梯度,常配合基线降低方差;GAE 从 GPOMDP 获得灵感通过 \(\lambda\) 加权的优势时序差分在偏差和方差间折中;Actor–Critic 由 Critic 估值 \(V\) 或者 \(Q\),Actor 按优势 \(A\) 更新,依靠 TD bootstrap 做到低方差的在线训练;TRPO 以 KL 约束的置信域更新保证步长稳定、近似单调改进;PPO 用剪裁的替代目标近似 TRPO,同时引入GAE,结构更简洁、效果稳健。SAC 基于最大熵强化学习框架,将策略熵 \(\mathcal{H}(\pi(\cdot\mid s))\) 纳入目标函数(鼓励策略输出的多样化),采用重参数化技巧实现随机策略的稳定更新(将动作表示为状态和独立噪声的确定性函数:\(a_t = f_\phi(\epsilon_t; s_t)\),其中 \(\epsilon_t \sim \mathcal{N}(0, I)\),使得梯度可以通过整个计算图反向传播,显著降低策略梯度的方差),配合"双重 \(Q\) 网络"(同时学两个独立的 Q 网络,取最小值以减少过估计)与 \(\alpha\) 自动调节机制,表现稳定、样本效率好。 对于确定 PG,动作不再是概率分布,而是确定动作,其 PG 形式为:
$$ \nabla J(\theta) = \mathbb{E}_{\,s \sim \eta_{\pi_\theta}} \Big[\, \nabla_\theta \pi_\theta(s)\; \nabla_a Q_{\pi_\theta}(s, a)\Big|_{a=\pi_\theta(s)} \,\Big]. $$这表示:用链式法则将”动作对参数的敏感度”与”价值对动作的敏感度”相乘,并在 \(a=\pi_\theta(s)\) 处取值;不再出现 \(\nabla \log \pi_\theta(a\mid s)\) 的得分函数项(那是随机策略的形式)。 确定 PG 的开山之作为 DPG:首次提出了确定性策略梯度原理,方差更低且支持 off-policy;DDPG 把 DPG 做成 Actor–Critic,用 DNN 逼近策略和价值,并借助经验回放、目标网络与 OU 噪声提升稳定性与探索;TD3 针对 DDPG 的过估计问题,引入三个关键改进:双重 Critic 网络(取两个 \(Q\) 网络的最小值以减少过估计)、延迟策略更新(Actor 更新频率低于 Critic,增强稳定性)和目标策略平滑化(在目标动作上添加噪声以提高鲁棒性)。
多智能体
多智能体与单智能体相比,首先是系统状态的演变过程受到所有智能体联合行动的影响;最重要的问题是,每个智能体所要优化的自己的长期奖励函数也会收到所有其他智能体策略的影响。 MARL 可以由两种不同的框架建模,马尔可夫/随机博弈和扩展形式博弈,(虽然不能用来建模,但是认知科学和神经科学的研究也对MARL有重要影响)
马尔可夫/随机博弈
在多智能体交互设定下,直接的思路是,把马尔可夫决策过程推广为马尔可夫博弈,或称随机博弈(应该说随机博弈定义更加宽泛,马尔可夫博弈要求随机博弈必须满足马尔可夫性质,但是实际建模中随机博弈通常被建模为马尔可夫博弈)。 马尔可夫博弈定义:马尔可夫博弈由一个元组 \((N, S, \{A_i\}_{i\in N}, P, \{R_i\}_{i\in N}, \gamma)\) 所定义。其中,\(N = \{1, \cdots, N\}\) 表示 \(N > 1\) 个智能体的集合;\(S\) 为所有智能体共同观察到的状态空间;\(A_i\) 为第 \(i\) 个智能体的动作空间。令 \(A := A_1 \times \cdots \times A_N\),则 \(P: S \times A \to \Delta(S)\) 表示在任一联合动作 \(a \in A\) 下,从任一状态 \(s \in S\) 转移到任一状态 \(s' \in S\) 的转移概率;\(R_i: S \times A \times S \to \mathbb{R}\) 为奖励函数,决定了从 \((s, a)\) 转移到 \(s'\) 时智能体 \(i\) 获得的即时奖励;\(\gamma \in [0, 1)\) 为折扣因子。 在时间 \(t\),每个智能体 \(i \in N\) 会根据系统状态 \(s_t\) 执行动作 \(a_i^t\)(所有智能体同时执行动作)。随后系统转移到状态 \(s_{t+1}\),并依据 \(R_i(s_t, a_t, s_{t+1})\) 对每个智能体 \(i\) 给予奖励,其中联合动作 \(a_t \in A\)。智能体 \(i\) 的目标是寻找策略 \(\pi_i: S \to \Delta(A_i)\) 且 \(a_i^t \sim \pi_i(\cdot \mid s_t)\),使自身的长期回报最大,\( \Delta \) 表示概率单纯形即所有状态上动作的概率分布的集合。 此时,智能体 \(i\) 的状态价值函数 \(V_i: S \to \mathbb{R}\) 成为联合策略的函数。假设每个智能体在动作选择上是独立的,即智能体间策略是独立的,联合策略 \(\pi: S \to \Delta(A)\) 定义为
$$ \pi(a \mid s) := \prod_{i\in N} \pi_i(a_i \mid s). $$特别地,对于任一联合策略 \(\pi\) 与状态 \(s \in S\),定义智能体 \(i\) 在状态 \(s\) 下的状态价值函数为:
$$ V_i^{\pi_i,\pi_{-i}}(s) := \mathbb{E}\Big[ \sum_{t \ge 0} \gamma^t\, R_i(s_t, a_t, s_{t+1}) \,\Big|\, a_i^t \sim \pi_i(\cdot \mid s_t),\; s_0 = s \Big], $$其中 \(-i\) 表示除智能体 \(i\) 外的所有智能体的索引集合,该公式定义了当智能体 \(i\) 在状态 \(s\) 下遵循策略 \(\pi_i\),而其他智能体(用下标 \(-i\) 表示)遵循策略 \(\pi_{-i}\) 时,智能体 \(i\) 的期望累计折扣回报。 由此可见,马尔可夫博弈的解概念有别于马尔可夫决策过程:某个智能体的最优表现不仅受其自身策略影响,也受到其他玩家选择的共同作用。最常见的解概念是纳什均衡简称 NE ,其定义如下: 纳什均衡定义:对于马尔可夫博弈 \((N, S, \{A_i\}_{i\in N}, P, \{R_i\}_{i\in N}, \gamma)\),一个联合策略 \(\pi^* = (\pi_1^*, \cdots, \pi_N^*)\) 若满足对任意 \(s \in S\) 与任意 \(i \in N\),
$$ V_i^{\pi_i^*,\,\pi_{-i}^*}(s) \;\ge\; V_i^{\pi_i,\,\pi_{-i}^*}(s), \quad \forall\, \pi_i, $$则称 \(\pi^*\) 为该博弈的纳什均衡。纳什均衡刻画了一个无人有激励单边偏离的平衡点:对任意智能体 \(i \in N\),\(\pi_i^*\) 是对 \(\pi_{-i}^*\) 的最优响应(任何智能体都无法只改变自己的策略获得更优的利益,所有智能体都没有动机改变自己的策略)。作为 MARL 的标准学习目标,NE 在有限状态/动作空间、无限时域且折扣的 MG 中总是存在,但一般不保证唯一。大多数 MARL 算法的目标是当 NE 存在时收敛到这样的平衡点。马尔可夫博弈框架足够通用,可以统一覆盖多种 MARL 设定。
完全合作设定下:
在完全合作的设定下,所有智能体通常共享同一个奖励函数,即 \(R_1 = R_2 = \cdots = R_N = R\)。该模型在 AI 社区被称为多智能体 MDP(MMDPs),在控制或者博弈论社区则被称为马尔可夫团队或者马尔可夫团队博弈( Markov teams/team Markov games)。此外,从博弈论视角看,这一合作设定也可视为马尔可夫势博弈( Markov potential games )的特殊情形,其中势函数为共享的累计回报。 在此设定下,各智能体的 \( V \) 函数与 \(Q\) 函数相同;若所有智能体能够被协调为“单一决策者”,则可直接应用单智能体强化学习算法。合作设定的全局最优解是马尔可夫博弈的一个纳什均衡。 除共享奖励模型外,另一类更一般的合作 MARL 模型则考虑团队平均奖励,智能体可以拥有不同(且可保持私有)的奖励函数,而合作的目标是优化与平均奖励对应的长期回报,其中平均奖励定义为
$$ \bar{R}(s,a,s') := \frac{1}{N}\sum_{i\in N} R_i(s,a,s'), \quad (s,a,s') \in S \times A \times S. $$平均奖励模型不仅支持更强的智能体异构性,还能保护智能体间的隐私,促进了去中心化MARL算法的发展。这种异构性特征进一步强化了将通信协议整合到多智能体强化学习中的必要性,推动了通信高效MARL算法的研究。
完全竞争设定下:
在完全竞争设定下,MARL 通常建模为零和马尔可夫博弈,即对任意 \((s,a,s')\),都有 \(\sum_{i\in N} R_i(s,a,s') = 0\)。为便于算法分析与计算可行性,大多数文献聚焦于两个相互对抗的智能体,此时一方的奖励即为另一方的损失。除了直接用于博弈类应用外,零和博弈亦常用作鲁棒学习的模型:学习中的不确定性可视作始终与智能体对立的“虚拟对手”,此时,纳什均衡对应的策略在最坏情形的长期回报意义下是鲁棒的,即假设对手(即环境)总是会以最凶险的方式对付你的前提下,所能保证的最坏设定下的最好结果。
混合合作竞争设定下:
混合设定亦称一般和(general-sum)博弈,对智能体的目标与关系不作限制。每个智能体是自利的,其奖励可能与他者冲突。博弈论中的均衡解概念(如纳什均衡)对该设定下算法的发展影响最为显著。此外,同时包含完全合作与完全竞争的设定——例如两个零和竞争团队,且每个团队内智能体合作——也可视为混合设定的实例。
扩展形式博弈(Extensive-Form Games)
尽管马尔可夫博弈是 MARL 的经典形式,但它只能处理完全可观测情形,即智能体在时刻 \(t\) 对系统状态 \(s_t\) 与已执行的联合动作 \(a_t\) 拥有完备信息。与此同时,诸多 MARL 应用涉及仅部分可观测的智能体,即不完备信息的博弈。虽然将马尔可夫博弈扩展到部分可观测情形(Dec-POMDP)但即使是在完全合作的情况下求解难度也极大。 相较而言,扩展形式博弈能够更自然地刻画不完备信息的多智能体决策;该框架源于计算博弈论,并在温和条件(某些不是很严格的条件下)下可用多项式时间(时间复杂度是多项式)算法求解。 扩展形式博弈定义:一个扩展形式博弈由 \((N \cup \{c\}, H, Z, A, \{R_i\}_{i\in N}, \tau, \pi_c, S)\) 定义,其中 \(N = \{1, \ldots, N\}\) 表示 \(N>1\) 个智能体的集合,\(c\) 是称为“机会/自然”的特殊智能体,其固定的随机策略 \(\pi_c\) 代表环境中的随机性。\(A\) 是所有可能动作的集合,\(H\) 是所有可能的历史集合,每个历史是自博弈开始以来的动作序列。记 \(A(h) = \{\, a \mid ha \in H \,\}\) 为非终止历史 \(h\) 之后可用的动作集合。若一个智能体在历史 \(h \in H\) 下采取动作 \(a \in A(h)\),则到达新历史 \(ha \in H\)。在所有历史中,\(Z \subseteq H\) 是终止历史的子集,表示博弈结束;每个智能体 \(i \in N\) 在终止历史上的回报由 \(R_i: Z \to \mathbb{R}\) 给出(注意扩展博弈没有单步回报,其效用只在终止历史上给定)。并且 \(\tau: H \to N \cup \{c\}\) 是识别函数,指定每个历史上由谁执行动作:若 \(\tau(h) = c\),则机会智能体按其策略选择 \(a \sim \pi_c(\cdot \mid h)\)。此外,\(S\) 将 \(H\) 划分为不相交的子集,使得对任意 \(s \in S\) 以及其中任意 \(h, h' \in s\),都有 \(\tau(h) = \tau(h')\) 且 \(A(h) = A(h')\)。换言之,属于同一分区的历史对即将行动的智能体而言不可区分(扑克牌,出牌者手里的牌一致的设定下,对方的牌可能是任何一种设定,这表明历史不同,但是对于出牌者而言,不知道对手的牌具体是哪种设定);\(S\) 的元素 \( s \) 称为信息状态。 直观地说,不完备信息体现在智能体无法区分同一信息状态中的不同历史。为简化记号,对任意 \(s \in S\) 与其中任意 \(h \in s\)(任意一个分区的任意一段历史),记 \(A(s) := A(h)\)、\(\tau(s) := \tau(h)\)(智能体无法判定自己处于哪段历史,只能判定自己处于哪个信息状态,所以它对于一个历史的动作可以认为是对这个信息状态的动作,对于该由谁行动也可以基于信息状态判定),并定义映射 \(I: H \to S\),满足当且仅当 \(h \in s\) 时 \(I(h) = s\)。仅考虑 \(H\) 与 \(A\) 为有限集的情形。对任意两个历史 \(h, h' \in H\),若从 \(h\) 经过一串动作可到达 \(h'\),则称 \(h\) 是 \(h'\) 的前缀,记为 \(h \sqsubseteq h'\);同时称 \(h'\) 是 \(h\) 的后缀。另外假设博弈满足完美回忆,即每个智能体记得导致其当前信息状态的历史中的信息状态-动作序列。由著名的 Kuhn 定理(在满足 “完美回忆” 的有限扩展形式博弈中,对于任何一个智能体,其任何混合策略都存在一个收益等价(即对所有其他智能体都产生相同期望回报)的行为策略)可知,在完美回忆下,只需在行为策略中寻找纳什均衡;行为策略把每个信息状态 \(s \in S\) 映射为其可行动作集合上的概率分布(意思是只需要按照当前的信息状态执行策略就可以囊括所有可能的复杂策略,大大减少了策略的搜索范围)。 对任意 \(i \in N\),令 \(S_i := \{\, s \in S : \tau(s) = i \,\}\) 为智能体 \(i\) 的信息状态集合。联合策略记为 \(\pi = (\pi_1, \ldots, \pi_N)\),其中 \(\pi_i : S_i \to \Delta(A(s))\) 是智能体 \(i\) 的策略。对任意历史 \(h\) 及联合策略 \(\pi\),定义在 \(\pi\) 下到达历史 \(h\) 的到达概率为
$$ \eta_\pi(h) = \prod_{\,h':\, h'a \sqsubseteq h} \pi^{\tau(h')}\!\big(a \,\big|\, I(h')\big) = \prod_{\,i \in N \cup \{c\}} \;\prod_{\substack{h':\, h'a \sqsubseteq h \\ \tau(h') = i}} \pi^i\!\big(a \,\big|\, I(h')\big) $$它刻画在所有智能体遵循 \(\pi\) 时生成历史 \(h\) 的概率。类似地,信息状态 \(s\) 的到达概率记为 \(\eta_\pi(s) = \sum_{h \in s} \eta_\pi(h)\)。智能体 \(i\) 的期望回报为
$$ R_i(\pi) = \sum_{z \in Z} \eta_\pi(z) \cdot R_i(z). $$现在给出扩展形式博弈的解概念,即 \(\varepsilon\)-纳什均衡: \(\varepsilon\)-纳什均衡定义:对于由 \((N \cup \{c\}, H, Z, A, \{R_i\}_{i\in N}, \tau, \pi_c, S)\) 表示的扩展形式博弈,若存在联合策略 \(\pi^* = (\pi_1^*, \cdots, \pi_N^*)\),使得对任意 \(i \in N\) 与任意策略 \(\pi_i\),
$$ R_i(\pi_i^*, \pi_{-i}^*) \;\ge\; R_i(\pi_i, \pi_{-i}^*) - \varepsilon, $$则称 \(\pi^*\) 为一个 \(\varepsilon\)-纳什均衡。这里 \(\pi_{-i}\) 表示集合 \(N\setminus \{i\}\) 中各智能体的联合策略(其中 \(j \in N\setminus\{i\}\) 的策略为 \(\pi_j\))。若 \(\varepsilon = 0\),则 \(\pi^*\) 构成一个纳什均衡。由于 \(\varepsilon\)-纳什均衡相对纳什均衡更加宽松,因此,\(\varepsilon\)-纳什均衡通常被视为一种解概念。 多种设定: 扩展形式博弈通常用于刻画非合作设定。具体地,若效用满足零和或者常和,即 \(\sum_{i\in N} R_i = k\)(其中 \(k\) 为常数),则对应完全竞争设定;一般和的效用则对应混合设定。主要是,不同的信息结构都可以可用扩展形式博弈来描述:完备信息博弈指每个信息集都是单点集,即对任意 \(s \in S\),\(|s| = 1\);不完备信息博弈指存在 \(s \in S\) 使得 \(|s| > 1\)。换言之,在不完备信息下,用于决策的信息状态 \(s\) 代表多个可能的历史,智能体无法区分它们。众多设定中,零和的不完备信息设定一直是连接 MARL 与广义形式博弈的理论研究重点,并催生了颠覆性的竞争场景算法,如 Poker AI 打德扑的 AI 好像挺强的,也挺吃算力的。 与马尔可夫博弈的联系: 更直观地说,扩展形式博弈与马尔可夫博弈在“到达概率”的建模上是可以互相映射的:在“同时行动”的马尔可夫博弈里,某个智能体在该时间步看不到其他智能体到底选了什么动作,因此对它而言,同一时刻可能发生的多种联合动作序列其实是“不可区分”的,这些不同的历史会被合并为同一个信息状态 \(s\)。在这种视角下,历史就是从起点到当前的一串联合动作,而“到达概率”就是“所有参与者按各自策略一路走到某个历史/信息状态的概率”(分别记为 \(\eta_\pi(h)\) 和 \(\eta_\pi(s)\))。反过来,如果在某个信息状态 \(s\) 上只允许当前行动者选择动作,把其他参与者的动作集置空(对所有 \(j \neq \tau(s)\) 设 \(A_j = \varnothing\)),那么这个扩展形式博弈就会退化为一个具有随状态变化的动作空间的马尔可夫博弈。简言之:扩展形式用信息集 \(s\) 表达“在该时间步对他人动作的不完全信息”,而马尔可夫博弈用联合动作与折扣累计回报刻画序列决策;两者以不同层次描述同一条轨迹的概率。
其他 MARL 框架
还存在其他 MARL 的理论框架,例如规范形博弈或者说重复博弈,以及部分可观测马尔可夫博弈。前者可视为马尔可夫的一个特例(状态为单点集,即只有一种状态,状态只会转移回这个状态),局限于小规模问题;部分可观测马尔可夫博弈由于更具挑战性,因此相关理论相对稀缺。
MARL 理论的挑战
非唯一学习目标
与单智能体强化学习中智能体以高效最大化长期回报为目标不同,多智能体强化学习的学习目标更为复杂且常常不唯一。早期 MARL 的一个主要缺陷在于研究目标界定不清。 在 MARL 算法设计与分析中,最常见的目标是收敛到纳什均衡。纳什均衡的含义是:一旦达到该均衡点,任何智能体都没有动机单方面偏离。该目标依赖严格的理想化假设:智能体完全理性、具备完全推理能力、并拥有无限的相互建模能力。在此假设下,纳什均衡是一个合理的解概念。 然而,纳什均衡作为学习目标存在明显局限:它可能全局次优、计算代价高昂,且现实中智能体只能进行有限次的相互建模。因此,单纯追求纳什均衡收敛的学习方法在实际 MARL 中往往缺乏合理性。 基于上述反思,研究者提出了两类目标框架: 均衡议程(equilibrium agenda):继续以某种均衡概念为收敛目标,强调系统层面的稳定性。 人工智能议程(AI agenda):在其他智能体属于固定类别(其策略集合有限,可视作环境的一部分)的前提下,为给定智能体设计最优学习策略,强调个体性能优化。 与此同时,将“收敛至均衡点”作为主要评估标准也引发争议。有研究指出,在一般和(general-sum)马尔可夫博弈中,部分基于值的 MARL 算法可能无法保证收敛到静态纳什均衡,这促生了“循环均衡”的新概念:智能体在一组静态策略之间呈现严格的周期性切换,而非收敛到任何纳什策略。 另一条评估思路将学习目标拆分为“稳定性”与“理性”:稳定性指在预定义的对手算法类别下算法的收敛性;理性则要求当其他智能体策略保持不变时,算法能收敛到最优反应。若所有智能体兼具稳定性与理性,则在该框架下系统自然收敛至纳什均衡。此外,遗憾值也为刻画智能体理性提供了另一视角:它衡量算法相对“事后可知的最佳静态策略”的性能差异。当平均遗憾渐近为零 \( \lim_{T \to \infty} \frac{1}{T}\sum_{t=1}^{T} \mathrm{regret}_t = 0 \),无遗憾学习在一定监控或者说信息反馈条件下可保证收敛至特定博弈的相关均衡;其本质是确保长期来看智能体不被他人策略所利用(即长期来看无论其他智能体行为如何智能体的策略总不会差于事后可知的最佳静态策略)。 除了优化回报的目标外,多智能体系统特有的其他目标也日益受到关注。例如,通信学习以便智能体更好地协调,这种对通信协议的关注自然推动了通信高效的 MARL 研究。其他重要目标包括如何学习而不过度拟合特定智能体,以及如何在存在恶意、对抗性或失效或失调的学习智能体的设定下进行鲁棒学习。
非平稳性
另一个关键挑战在于多智能体通常同时学习,导致每个个体面对的环境是非平稳的。具体而言,一个智能体的动作会影响其他对手的奖励与系统状态的演化;因此,学习者必须考虑其他智能体的行为,并据此适应联合行为。这直接破坏了单智能体RL建立收敛性的平稳性假设(环境满足平稳的马尔可夫性质,即个体奖励与当前状态仅依赖于前一状态和所采取的动作)。由此也就无法直接套用单智能体RL的数学分析工具到 MARL 上。理论上,如果智能体忽略这一问题并在假定环境平稳的前提下优化自身策略(通常称为独立学习者-IRL),算法可能出现不收敛的情况,除非在若干特殊设定下(例如智能体共享一个团队回报函数,智能体局部行动但是有全局观测)。而在经验上, IRL 有时也能取得尚可的表现(例如IPPO)。作为MARL中最为人熟知的问题之一,非平稳性在文献中早已被广泛讨论;可以参见这篇综述,https://arxiv.org/abs/1906.04737
可拓展性问题
为应对非平稳性,个体智能体通常需要考虑联合动作空间,而其维度会随智能体数量指数级增长,这也被称为 MARL 的组合爆炸特性。大量智能体的存在显著增加了理论分析的复杂度,尤其是收敛性分析;这也从侧面反映在现有理论进展上:关于二人零和的MARL理论明显更为完备,而对于多于两人的一般和的设定则相对落后。一种可能的缓解思路是进一步假设价值函数或奖励函数在动作依赖上的分解(因子化)结构:例如 VDN ,QMIX 这类算法(虽然他们的理论证明薄弱)。严格理论分析参见 https://ieeexplore.ieee.org/document/9029635 :在一种特殊的依赖结构下,提出了可证明收敛的基于模型的算法。与此同时,还有一类与可扩展性相互独立但被其进一步加剧的理论挑战:建立“深度”多智能体强化学习(deep MARL)的系统理论。由于可扩展性,MARL 往往需要使用函数逼近,尤其是深度神经网络;尽管在经验上颇为成功,但深度 MARL 的理论分析几乎仍是一片空白,因为当前对深度学习理论的理解尚且有限,更遑论深度 RL 理论。这也是未来的研究方向之一。
多样的信息结构
与单智能体相比,MARL 的信息结构(即在训练与执行阶段“谁知道什么”)更为复杂。以马尔可夫博弈为例,只需观测瞬时状态 \(s_t\) 即可使每个智能体作出决策,因为局部策略 \(\pi_i: S \to \Delta(A_i)\) 能表达均衡策略。而在扩展形式博弈中,在常见的“完美回忆”假设下,每个智能体可能需要回忆过去的决策历史。 此外,作为自利的智能体,每个智能体通常难以直接获取对手的策略或奖励,最多只能观测其采取的动作。这种部分信息会加剧非平稳性问题:样本难以准确恢复对手策略的真实行为,从而增加个体智能体所感知的非平稳性。其极端情形是前述的 IRL ,它仅假设可观测本地动作与奖励,通常不收敛。 不同信息结构下的学习方案会带来不同层次的理论分析难度。为缓解上述部分信息问题,许多工作假设存在一个中央控制器,能够收集联合动作、联合奖励与联合观测,甚至为所有智能体设计策略。这一结构催生了“集中式训练—分散式执行”(CTDE)的流行范式,其源自对部分可观测设定的规划研究,即 Dec-POMDPs,并被近年来的深度 MARL 工作广泛采用。在合作设定中,这一范式能显著简化分析,可以借用单智能体 RL 的工具;但在非合作且异构智能体的设定中,由于各方学习目标不一致,该范式并不能简化问题。 需要指出的是,在许多应用中通常并不存在这样的中央控制器,除非能方便地访问仿真环境(如电子游戏、机器人)。因此,往往更偏好分散式(fully decentralized)的学习方案,其中 IRL 是一个特例。为缓解 IRL 的不收敛问题,智能体通常允许通过通信网络与邻居交换或共享本地信息;我们将这种设定称为“带网络的去中心结构”。在该设定下,可以开展收敛性的理论分析,其难度介于单智能体 RL 与一般 MARL 算法之间。
具备理论支撑的 MARL 算法
完全合作设定
具有理论支撑的合作型 MARL 主要针对以下情境设计:
同构智能体
所有智能体共享相同的奖励函数(在这种设定下,NE 变为团队均衡,在满足 NE 的一般特性上还满足全局最优的特性),该奖励函数能协调所有智能体的利益,在智能体数量极大的设定下,同构性智能体意味着智能体在系统演化中可互换,难以区分(即智能体之间没有区别)。
MAMDP 和 马尔可夫团队
考虑马尔可夫博弈,当满足 \(R_1 = R_2 = \cdots = R_N = R\),其中奖励函数 \(R: S \times A \times S \to \mathbb{R}\) 受联合动作 \(A = A_1 \times \cdots \times A_N\) 的影响,此时,各智能体的 \(Q\) 函数相同。一个直接的算法是在每个智能体处执行标准的 Q-learning 更新,但在目标项中对联合动作空间的后继动作 \(a' \in A\) 取最大值(即将标准Q-learning 更新中对于单智能体动作空间的后继动作取最大值,替换为联合动作空间的后继动作取最大值)。在状态与动作空间均有限时,有论文论证了最优或者说均衡 \(Q\) 函数的收敛性。 然而,\(Q\) 函数的收敛并不必然意味着马尔可夫团队的均衡策略(可能是任何一种均衡,此处可能指 NE )收敛:当均衡策略不唯一且智能体无法协调选择时,逐个智能体提取的均衡策略的任意组合可能并不构成一个团队均衡(每个智能体都找到了奖励相同的团队均衡点,但是他们选的不是同一个团队均衡点,导致联合策略不能达到一个团队均衡点)。因而,收敛到 NE 策略仅在以下两种设定下得到保证:要么假设均衡唯一,要么智能体在均衡选择上达成协调。后一思路在合作重复博弈中得到验证——这是一种具有单一状态的马尔可夫团队,其中智能体作为联合动作学习者维护联合动作的 \(Q\) 值,并学习他人的经验模型;对于一般设定还没有理论证明收敛。 在真实的马尔可夫团队设定下,有研究利用了这种协调思想并提出了“最优自适应学习”(OAL),这是首个对均衡策略收敛具有证明保证的 MARL 算法。最优自适应学习(OAL)的运作机制如下:它首先通过交互经验来估计博弈模型。随后,在每一个决策点,它都会构建一个内部的“虚拟博弈”。这个虚拟博弈是经过设计的,它围绕一个核心的策略候选集合(偏置集合,基于对历史的分析所确定的),并确保智能体在这些策略上的互动能够避免循环、趋向稳定(此性质被称为弱非循环)。接着,OAL 引入一种能够适应不同策略情境的学习算法,作用于这些虚拟博弈之上。正是通过这一系列精巧的设计,理论上证明了OAL的行为最终能够收敛至 NE。 除均衡选择的问题外,马尔可夫团队相较单智能体 RL 还需处理可扩展性问题。由于独立 Q-learning 可能不收敛,面向 MMDPs 的可扩展且收敛的早期尝试是:提出一种分布式 Q-learning 算法,可在确定性、有限的 MMDPs 上收敛。每个智能体仅维护关于状态 \(s\) 与本地动作 \(a_i\) 的 \(Q\) 表,并在更新中依次对联合动作 \(a'\) 做最大化;各个体无法获取他人的动作及其历史。 为缓解可扩展性,业界提出了若干启发式(缺乏理论支撑)的奖励或价值函数因子化方法如 VDN、QMIX、QTRAN 。其中 QTRAN 对“价值因子化”给出了严格的条件刻画;另一项理论工作假设一种单向树形依赖结构,使得整体 MMDPs 的最优策略可被局部策略在理论上良好逼近;也有人研究了共同利益博弈(包含马尔可夫团队),提出一种仅依赖状态、局部动作与奖励的分散式 RL 算法。在与独立 Q-learning 相同的信息结构下,该算法保证收敛到“团队最优均衡策略”(而不仅仅是任意均衡策略)。这点尤为重要,因为一般而言,次优均衡的性能可能与最优均衡相差悬殊。 对于基于策略的方法,据作者所知只有“两时间尺度”的 Actor-Critic 拟似博弈(fictitious play)算法有理论论证,其内容为:慢时间尺度上,Actor 在当前策略与相对于本地 \(Q\) 估计的最优反应之间做混合(相当于平滑更新);快时间尺度上,Critic 进行策略评估,仿佛所有智能体的策略是静态的(确保准确估计Q值)。其收敛性已在“同时行动的多阶段博弈、具有共同奖励”这一马尔可夫团队特例下证明:该特例从初始状态出发,经吸收态终止(确保了有限时间范围,使值函数有界),且每个状态仅被访问一次(没有重复访问和优化,不会因为重复访问产生依赖循环)。
马尔可夫势博弈
从博弈论视角,更一般地能包括合作设定的框架是势博弈:存在一个所有智能体共享的势函数,使得任一智能体单方面改变策略时,其奖励的变化等于或正比于该势函数的变化。尽管多数势博弈是无状态的,但马尔可夫势博弈(MPGs)这种扩展框架因能建模序列决策问题而日益受到关注;其中状态满足马尔可夫性且其演化受联合动作影响。实际上,马尔可夫团队是 MPGs 的一个特例,其势函数即公共奖励;这类动态博弈在策略上等价于马尔可夫团队。在这一模型下,有文献给出了可验证条件以判定一个马尔可夫博弈是不是马尔可夫势博弈,并证明了在马尔可夫势博弈中寻找闭环纳什均衡与求解单智能体最优控制问题等价;因此,可直接借助单智能体强化学习算法来求解此类 MARL 问题。
均值场
针对可扩展性问题的另一解决思路是将环境建模为均值场,其中包括大量同构的智能体。此时,每个体对整体系统的影响趋于无穷小,智能体间因此可互换或者说不可区分;与他人的交互可由某个均值场量简洁刻画,例如平均状态或状态的经验分布。每个体只需对均值场求最优响应,显著简化了分析的复杂度。这种多智能体系统的均值场视角已通过以下模型实现:均值场博弈模型、具有均值场共享的团队模型、具有均值场行为的博弈模型。注意均值场团队和均值场博弈的区别在于求解的目标不同,均值场团队求解最优解,均值场博弈求解均衡解。 直到最近(2021年的最近),基于这些模型的MARL算法才开始探索,多集中于均值场中的非合作设定。对于合作设定,有文献研究了具有均值场共享的马尔可夫团队的强化学习:与均值场博弈相比,该模型假设智能体共享一个仅依赖本地状态与均值场的公共奖励函数,从而鼓励合作;同时,“均值场”在此指有限群体的状态经验平均(当智能体数量有限时使用智能体的状态的经验分布近似均值场(均值场一半要求智能体趋于无穷)的智能体状态概率分布),区别于 MFGs 中无限群体的期望或概率分布。基于该模型的动态规划分解(基本上是说贝尔曼方程了),若干常见的 RL 算法可直接迁移到此种模型下。有文献采用均值场控制(MFC)来刻画大规模合作决策者:策略梯度方法被证明在线性二次 MFC 上收敛;也有人证明了均值场 Q-learning 在一般 MFC 上的收敛性。 注:均值场团队与均值场博弈的区别主要在解概念——“最优”与“均衡”,分别对应一般动态团队理论与博弈论。尽管前者可视为后者的特例,但相关研究通常分开回顾。
网络化智能体的去中心范式
在实际多智能体系统中,协作智能体并非总是同构的。智能体可能具有不同的偏好,即奖励函数,但它们仍然组成团队以最大化团队平均奖励 \(\bar{R}\) 的回报,其中 \(\bar{R}(s, a, s') = \frac{1}{N} \cdot \sum_{i \in N} R_i(s, a, s')\)。主要是,奖励函数有时无法与其他智能体共享,因为偏好对每个智能体来说是私有的。这种设定在传感器网络、智能电网、智能交通系统和机器人学等工程系统中有着广泛的应用。 网络化智能体的去中心范式可以将同构智能体视为一种特例,但是这种网络化的智能体显然需要更多的协调机制,例如,在不知道其他智能体奖励函数的设定下,全局价值函数无法在本地估计。在有中央控制器的设定下,同构智能体设定中的大多数 MARL 算法可以直接应用,因为控制器可以收集和平均奖励,并将信息分发给所有智能体。然而,由于成本、可扩展性或鲁棒性考虑,这样的控制器在前面提到的大多数应用中可能不存在。取代这种方法的是,智能体或许能够通过可能时变且稀疏的通信网络与其邻居共享/交换信息。尽管这种去中心或者分布式范式的 MARL 显然具有很大的发展潜力,但与解决静态或单阶段优化问题的分布式或一致性算法(指分布式静态优化领域的算法)的广泛研究结果相比,它的研究相对较少,分布式静态优化领域的算法与 MARL 不同,不涉及系统动态,也不最大化序贯决策问题的长期目标。
学习最优策略
最重要的目标是学习最优联合策略,与此同时每个智能体只能访问本地和网络上的邻居信息。网络化智能体的 MARL 思想可以追溯到09年的文献 Efficient distributed reinforcement learning through agreement 。据作者所知,在这种设定下第一个可证明收敛的 MARL 算法来自 A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations,该算法将”一致性和创新”的思想融入到标准 Q-learning 算法中,产生了 QD-learning 算法,其更新规则如下:
$$ Q_t^{i+1}(s, a) \leftarrow Q_t^i(s, a) + \alpha_{t,s,a} \left[ R_i(s, a) + \gamma \max_{a' \in A} Q_t^i(s', a') - Q_t^i(s, a) \right] - \beta_{t,s,a} \sum_{j \in \mathcal{N}_t^i} \left[Q_t^i(s, a) - Q_t^j(s, a)\right] $$其中 \(\alpha_{t,s,a}, \beta_{t,s,a} > 0\) 是步长,\(\mathcal{N}_t^i\) 表示智能体 \(i\) 在时间 \(t\) 的邻居智能体集合。与 Q-learning 更新相比,QD-learning 附加了一个创新项,该项捕获了与其邻居的 Q 值估计的差异。在步长的某些条件下,该算法保证在表格设定(Q-table 专门存储精确 Q 值的表格)下收敛到最优 Q 函数。 由于可扩展性问题,函数逼近在 MARL 中至关重要,这需要开发基于策略的算法。作者之前的工作,为这种设定提出了分散式 Actor-Critic 算法。特别地,每个智能体通过某个参数 \(\theta_i \in \mathbb{R}^{m_i}\) 参数化其自己的策略 \(\pi_\theta^i : S \to \Delta(A_i)\),回报的策略梯度首先推导为:
$$ \nabla_{\theta^i} J(\theta) = \mathbb{E}[\nabla_{\theta^i} \log \pi_{\theta^i}^i(s, a^i) \cdot Q_\theta(s, a)] \quad $$其中 \(Q_\theta\) 是在联合策略 \(\pi_\theta\) 下对应于 \(\bar{R}\)(这是团队平均奖励) 的全局价值函数(注意此处的全局价值函数是对于团队平均奖励而言的,而非对于一个额外定义的全局奖励),定义为 \(\pi_\theta(a \mid s) := \prod_{i \in \mathcal{N}} \pi_{\theta^i}^i(a^i | s)\)。与标准 Q-learning 中的策略梯度相比,此处涉及本地得分函数 \(\nabla_{\theta^i} \log \pi_{\theta^i}^i(s, a^i)\) 和全局 Q 函数 \(Q^\theta\) 乘积的期望。然而,全局 Q 函数无法在每个智能体处单独估计。因此,通过将 \(Q^\theta(\cdot, \cdot)\) 的每个本地副本(全局 Q 函数在每个本地智能体上的部分)参数化为智能体 \(i\) 的 \(Q^\theta(\cdot, \cdot; \omega_i)\)(使用神经网络从本地对全局 Q 函数估计),我们提出以下基于一致性的 TD 学习用于 Critic 步骤,即估计 \(Q^\theta(\cdot, \cdot)\):
$$ \tilde{\omega}_t^i = \omega_t^i + \beta_{\omega,t} \cdot \delta_t^i \cdot \nabla_\omega Q_t(\omega_t^i), \quad \omega_{t+1}^i = \sum_{j \in N} c_t(i, j) \cdot \tilde{\omega}_t^j \quad $$其中 \(\beta_{\omega,t} > 0\) 是步长,\(\delta_t^i\) 是使用 \(Q^\theta(\cdot, \cdot; \omega_i)\) 计算的本地 TD 误差(使用本地奖励计算)。第一个关系执行标准 TD 更新,然后是邻居估计 \(\tilde{\omega}_t^j\) 的加权组合。这里的权重 \(c_t(i, j)\) 由通信网络的拓扑决定,只有当两个智能体 \(i\) 和 \(j\) 在时间 \(t\) 连接时才有非零值。它们还需要在期望上满足双随机性质(每一行之和为零,每一列之和为零),以便如果 \(\omega_t^i\) 收敛,则对所有 \(i \in N\) 达到一致值。然后,每个智能体 \(i\) 在 Actor 步骤中使用其自己的\(Q^\theta(\cdot, \cdot; \omega_t^i)\),按照去中心化 AC 的随机策略梯度更新其策略。作者在那篇文章中还引入了一个变体算法,该算法不依赖于 Q 函数,而是依赖于状态价值函数逼近来估计全局优势函数。 基于上述考虑,这类去中心化 Actor–Critic 算法在采用线性函数进行值函数逼近时,能够获得几乎必然的收敛性(作者在此前的研究证明过了,提出了分散式 AC 算法)。类似的思想也可以扩展到连续动作空间,此类场景通常使用确定性策略梯度(DPG)。由于确定性同策略(on-policy)往往探索不足,DPG 需要借助随机行为策略进行 off-policy 探索;但在多智能体设定中,其他智能体的策略未知,常见的 DPG 的 off-policy 手段不可直接适用。 受期望策略梯度(EPG)统一随机策略梯度(SPG)与确定性策略梯度(DPG)的启发,可以构造一种保持 on-policy、同时相较通用 SPG 显著降低方差的算法:推导多智能体版本的 EPG,据此开发可去中心化执行的 Actor 更新步骤;Critic 更新则沿用分散式 AC 的办法。在线性函数逼近下,该算法同样能够建立几乎必然的收敛性。 沿此方向,还可将强调时序差分(ETD)的分析方法融入分散式 AC,形成在 off-policy 设定下的扩展框架,并获得几乎必然收敛的保证。与此同时,亦存在另一种 off-policy 方案:智能体不共享价值函数估计,而是通过对全局最优策略估计达成共识来实现协同;该架构采用本地 Critic 与共识 Actor,同样具备可证明的收敛性。 除了多智能体设定外,去中心网络化的 MARL 也在多任务设定中得到了研究。在某种意义上,多任务可以被视为多智能体的简化版本,其中每个智能体处理一个不受其他智能体影响的独立 MDP,而目标仍然是学习考虑所有智能体平均奖励的最优联合策略。有人提出了一种分布式 Actor-Critic 算法,假设状态、动作和奖励都是每个智能体的本地信息。每个智能体执行基于本地 TD 进行 Critic 更新,然后执行基于一致性的 Actor 更新,该步骤通过交换邻居信息计算梯度方向进行策略优化。然后证明了平均回报的梯度随着迭代趋于无穷而收敛到零。有文献基于对偶理论开发了 Diff-DAC,这是该设定的另一种分布式 Actor-Critic 算法。更新类似于作者提出的分散式 AC 中的更新,但提供了额外的见解,即 Actor-Critic 更新实际上是求解线性规划的对偶上升方法的一个应用。 注意,所有上述收敛保证都是渐近的,即算法随着迭代次数趋于无穷而收敛,并且仅限于线性函数逼近的情况。这无法量化使用有限迭代和有限样本中存在任意一种或者两种时的性能,更不用说使用深度神经网络等非线性函数逼近时。作为在这种设定下使用更一般函数逼近进行有限样本分析的初步分析,作者在以往的工作中研究了批量 RL (离线 RL )算法,具体研究的是拟合 Q 迭代(FQI)的去中心变体,偏重理论没有使用 DNN 作为函数逼近器,因为如果用了 DNN 那 FQI 就成了著名的 DQN 算法。作者既研究了适用于网络化智能体的合作设定的 FQI 变体,也研究了适用于两个这样的网络化智能体团队的竞争设定的 FQI 变体。在前一种设定中,所有智能体合作迭代更新全局 Q 函数估计,使用非线性最小二乘回归估计目标值。设 \(\mathcal{F}\) 为 Q 函数逼近器类别,\(\{(s_j, \{a_j^i\}_{i \in N}, s'_j)\}_{j \in [n]}\) 为所有智能体可用的大小为 \(n\) 的批量转移数据集,\(\{r_j^i\}_{j \in [n]}\) 为每个智能体私有的本地奖励样本,\(y_j^i = r_j^i + \gamma \cdot \max_{a \in A} Q_t^i(s'_j, a)\) 为本地目标值,其中 \(Q_t^i\) 是智能体 \(i\) 在迭代 \(t\) 的 Q 函数估计。然后,所有智能体合作通过求解以下问题找到共同的 Q 函数估计:
$$ \min_{f \in \mathcal{F}} \frac{1}{N} \sum_{i \in \mathcal{N}} \frac{1}{2n} \sum_{j=1}^n [y_j^i - f(s_j, a_j^1, \cdots, a_j^N)]^2 \quad (4.3) $$该问题可以归类为分布式或者说一致性优化框架,如果 \(\mathcal{F}\) 使得对每个 \(i\),\(\sum_{j=1}^n [y_j^i - f(s_j, a_j^1, \cdots, a_j^N)]^2\) 是凸的,则其全局最优解可以通过现有文献中的传统算法得到。如果 \(\mathcal{F}\) 是线性函数类,确实是可以的。然而,由于分布式优化算法的有限迭代(在实践中很常见),智能体可能无法达到精确一致,导致每个智能体的 Q 函数估计偏离上式的实际最优值的误差。当使用非线性函数逼近时,这种误差也存在。考虑到这种由去中心计算引起的误差,作者源于单智能体批量 RL 的误差传播分析,评估了所提出算法的有限样本性能,即算法输出的准确性如何依赖于函数类 \(\mathcal{F}\)、每次迭代内的样本数 \(n\) 和迭代次数 \(t\)。
策略迭代
与控制不同,在该设定下的方法仅专注于策略评估(policy evaluation),即 Actor-Critic 中的 Critic 步骤。由于策略固定,采样分布变为稳态;并且在线性函数逼近下,目标函数是凸的。这使得有限时间/有限样本分析成为可能,相比多数仅具渐近保证的控制算法更可操作。 在联合策略 \(\pi\) 下,假设每个智能体用线性函数类参数化价值函数
$$ V_\omega(s) := \phi^\top(s)\,\omega,\quad \phi(s)\in\mathbb{R}^d,\ \omega\in\mathbb{R}^d. $$其中 \( \phi^\top(s) \) 是状态 \( s \) 的特征向量,为记号简便,记 \(\Phi := (\cdots;\ \phi^\top(s);\ \cdots)\in\mathbb{R}^{|S|\times d}\),即将状态向量堆叠为一个矩阵,\(D := \mathrm{diag}(\{\eta_\pi(s)\}_{s\in S})\in\mathbb{R}^{|S|\times |S|}\) 即使用状态占用测度 \(\eta_\pi\) 构造的对角矩阵,\(\bar R_\pi(s) := \frac{1}{N}\sum_{i\in N} R_{i,\pi}(s)\),其中
$$ R_{i,\pi}(s) := \mathbb{E}_{a\sim\pi(\cdot|s),\ s'\sim P(\cdot|s,a)}[R_i(s,a,s')], $$以及转移矩阵 \(P^\pi\in\mathbb{R}^{|S|\times|S|}\) 的元素
$$ [P^\pi]_{s,s'} := \sum_{a\in A} \pi(a|s)\,P(s'|s,a). $$则所有智能体的目标是联合最小化团队平均奖励下的均方投影贝尔曼误差(MSPBE):
$$ \mathrm{MSPBE}(\omega) := \big\|\Pi_\Phi\big(V_\omega - \gamma P^\pi V_\omega - \bar R_\pi\big)\big\|^2_{D} = \big\|A\omega - b\big\|^2_{C^{-1}}\quad (4.4), $$其中 \(\Pi_\Phi := \Phi(\Phi^\top D \Phi)^{-1}\Phi^\top D\) 是将状态空间到子空间 \(\{\Phi\omega:\ \omega\in\mathbb{R}^d\}\) 的投影算子,\(A := \mathbb{E}[\phi(s)(\phi(s)-\gamma\phi(s'))^\top]\),\(C := \mathbb{E}[\phi(s)\phi^\top(s)]\),\(b := \mathbb{E}[\bar R_\pi(s)\phi(s)]\)。 将期望替换为样本并使用 Fenchel 对偶,MSPBE 的有限和版本可重写为分布式鞍点问题:
$$ \min_{\omega}\ \max_{\{\lambda_i\}_{i\in N}}\ \frac{1}{Nn}\sum_{i\in N}\sum_{j=1}^{n}\Big(2\,\lambda_i^\top A_j\,\omega - 2\,(b_j^{\,i})^\top \lambda_i - \lambda_i^\top C_j \lambda_i\Big)\quad (4.5), $$其中 \(n\) 为数据规模,\(A_j, C_j, b_j^{\,i}\) 分别是 \(A, C, b^i := \mathbb{E}[R_{i,\pi}(s)\phi(s)]\) 的样本估计。上式关于 \(\omega\) 为凸,关于 \(\{\lambda_i\}_{i\in N}\) 为凹。 以 MSPBE 为目标在多智能体策略评估中是标准做法;鞍点重构也被用于:基于扩散策略的分布式强化学习算法,分布式 GTD 算法,双重平均 MARL 算法,MARL 中带线性函数逼近的分布式TD(0)算法的有限时间分析。有文献引入了 MSPBE 的一个变体——H 截断的 \(\lambda\) 加权 MSPBE,以控制与实际均方贝尔曼误差最优解的偏差。基于 MSPBE,有文献开发了分布式的梯度 TD 方法,并用常微分方程(ODE)方法证明了渐近收敛。有文献提出了结合动态一致性与 SAG 算法的“双重平均”方案,以线性速率求解 MSPBE 的有限和版本。有文献将方差降低思想( AVRG )引入到基于梯度 TD 的策略评估,在达到与双重平均算法相同的线性速率的同时,有三点优势:1. 与数据量无关的内存需求;2. 使用资格迹(Eligibility Trace);3. 采样无需同步。标准 TD 学习(而非 gradient-TD)也被推广到该 MARL 设定,重点在于有限样本分析。有文献研究了分布式 TD(0),要求对迭代做投影并假设样本独立同分布。进一步地,有文献给出了更一般的分布式 TD(\(\lambda\)) 在无需投影与噪声假设下的有限时性能分析。对于网络化但独立 MDP 的设定,有文献研究了基于重要性采样的离策略评估;因为 MDP 之间无耦合,智能体不需要知道其他智能体的动作。随后提出了扩散式分布式 GTD,并证明了其以次线性速率在均方意义上的收敛。有文献在时变通信网络下为该设定设计了 TD 学习的两个变体(GTD2 与 TDC ),并基于一般随机近似理论证明了弱收敛。也有工作考虑了独立 MDP 设定,得到与实际 MARL 设定一致的结果。
其他学习目标
在网络化智能体的去中心化 MARL 中,研究者们还探索了其他几种学习目标。有文献考虑了最优一致性问题,其中网络中的每个智能体跟踪其邻居以及领导者的状态,从而通过联合策略最小化一致误差。该研究引入了一种策略迭代算法,进一步设计了使用神经网络进行函数逼近的 Actor-Critic 算法。也有文献在"合作多智能体图博弈"框架下采用了类似的一致误差目标,通过 CTDE 架构开发了 off-policy 强化学习算法。 通信效率作为该设定下算法设计的关键要素,受到极大的关注。有文献开发了惰性聚合策略梯度(LAPG),这是一种分布式策略梯度算法,通过精心设计通信触发规则,可以减少智能体与中央控制器之间的通信轮次。有文献解决了与双重平均算法相同的策略评估问题,并通过提出与双随机混合矩阵不同的混合矩阵进行一致化,开发了一种分层分布式算法,允许智能体之间的单向信息交换以节省通信。相比之下,有工作提出的分布式 Actor-Critic 算法通过每次迭代仅传输其状态向量的一个标量条目来减少通信,同时保持与一般分布式 AC 中相同的可证明收敛性。
部分观测模型
该部分只介绍一种重要且具有挑战性的模型——智能体部分可观的场景。尽管在实践中很常见,与完全可观测设定相比,该设定下的 MARL 算法理论分析仍相对稀缺(注意前两种设定都是全局观测的)。 一般而言,该设定可用去中心化部分可观测马尔可夫决策过程( Dec-POMDP )建模,它与马尔可夫博弈或者马尔可夫团队在奖励函数、转移模型等几乎所有要素上保持一致,区别在于每个智能体仅能获得系统状态 s 的局部观测。由于无法获取其他智能体的观测,单个智能体无法获知全局的信念状态(是指给定历史观测和动作序列的前提下,真实状态 s 的后验概率分布,即智能体可能处于的所有状态的概率)——这是单智能体 POMDP 中用于决策的充分统计量(即所有的历史观测和动作都可以压缩到信念状态中,不损失决策质量)。因此,Dec-POMDP 被证明为 NEXP 完全(NEXPTIME-complete),即在最坏情况下求解需要超指数时间(多重指数时间,不可能在有限时间解出来)。 针对 Dec-POMDP 的规划和学习算法研究正日益增长。多数算法采用 CTDE 范式:首先将去中心化问题重构为中心化问题,在中央控制器上使用所有智能体的观测数据进行求解;随后基于数据,优化或者学习策略,并分发至各智能体执行。有限状态控制器(FSCs)常用于表示各智能体的本地策略,它将局部观测历史映射到动作。有文献提出了贝叶斯非参数方法以确定可变规模 FSC 的控制器大小。 为高效求解中心化问题,提出了一系列自上而下算法。有文献将 Dec-POMDP 转换为不可观测 MDP(NOMDP,信念状态不变,导致Agent对转移状概率奖励的计算方式始终不变),并用启发式树搜索算法求解。作为该转换的扩展,有文献将 Dec-POMDP 转换为占用态 MDP(oMDP),其状态为占用态即信念状态的分布作为状态。由于 oMDP 的价值函数具备分段线性与凸性,有文献开发出了可处理的规划算法与基于价值的学习算法。 为进一步提升计算效率,还提出了若干基于采样的规划/学习算法:结合策略迭代的蒙特卡洛采样与期望—最大化算法。此外,蒙特卡洛树搜索也已用于若干特殊的 Dec-POMDP 类,如多智能体 POMDP 与多机器人主动感知。在该中心化学习范式下,也可构建基于策略梯度的算法,采用 CTDE 架构。对于表格设定(有限状态—动作空间),还建立了有限样本分析。 也有若干工作尝试在 Dec-POMDP 中实现去中心化学习:当智能体共享部分公共信息/观测时,有文献将问题重构为一个中心化 POMDP,把公共信息视为虚拟中央控制器的观测;这样,每个智能体都能独立求解该中心化 POMDP。有文献进一步用有限状态 MDP 近似该重构的 POMDP,近似误差指数递减,并以 Q-learning 求解。最近,有工作针对该中心化 POMDP 开发了基于树搜索的算法,有趣的是它与直接求解 Dec-POMDP 的启发式方法 相呼应,但具备更坚实的理论基础。需要注意的是,在有限状态 MDP 和基于树搜索的方法中,所有智能体共用一个随机数发生器,以避免智能体间通信并实现去中心化学习方案,即所有智能体进行的探索方向提前约定一致。
完全竞争设定
竞争性场景通常被建模为零和博弈。在计算复杂度层面,求解两人与多人零和博弈存在显著差异。特别需要指出的是,即使是最简单的三人矩阵博弈,也被证明属于 PPAD 完全问题(有向图上的多项式奇偶参数,PPAD 这类问题里最难计算的那个问题)。因此现有关于竞争性多智能体强化学习的研究主要聚焦于两人零和博弈。
基于值的方法
与单智能体 MDP 类似,基于值的方法旨在找到最优价值函数,从中可以提取联合纳什均衡策略。最优价值函数是贝尔曼算子(描述价值函数更新的数学算子)的唯一不动点,可以通过动态规划类方法获得(就是说可以通过迭代收敛到最优解)。具体而言,对于同步移动(所有智能体同时选择动作)的马尔可夫博弈,价值函数满足 \(V^1_{\pi^1,\pi^2} = -V^2_{\pi^1,\pi^2}\),因此任何纳什均衡 \(\pi^* = (\pi^{1,*}, \pi^{2,*})\) 满足
$$ V^1_{\pi^1,\pi^{2,*}}(s) \leq V^1_{\pi^{1,*},\pi^{2,*}}(s) \leq V^1_{\pi^{1,*},\pi^2}(s), \quad \text{对于任意 } \pi = (\pi^1, \pi^2) \text{ 和 } s \in S. \quad $$即左侧玩家1单方面改变策略,玩家1的价值不会增加,玩家1的策略已经是最优响应;右侧玩家2单方面改变策略,玩家1的价值不会减少,所以玩家2的价值不会增加,说明玩家2的策略已经是最优响应。类似于正则形式/矩阵(正则形式就是矩阵形式)零和博弈中的极小极大定理(对于玩家1而言他选择了某个策略,对于玩家2一定会选择对玩家1最不利的策略,那么玩家1就会选择在最坏情况下收益最高的策略,而玩家2则会选择玩家1在最好情况下收益最小的策略,即玩家1最大化最小收益,玩家2最小化最大收益,冯·诺依曼极小极大定理指出有限双人零和博弈中,极大极小值等于极小极大值),对于具有有限状态和动作空间的两人零和马尔可夫博弈,可以定义最优价值函数 \(V^*: S \to \mathbb{R}\) 为
$$ V^* = \max_{\pi^1} \min_{\pi^2} V^1_{\pi^1,\pi^2} = \min_{\pi^2} \max_{\pi^1} V^1_{\pi^1,\pi^2}, \quad $$那么双人博弈价值纳什均衡和双人零和马尔可夫博弈的最优价值函数定义意味着重合(因为极小化极大值就意味着玩家2无法通过改变自己策略损害玩家1的利益,极大化极小值意味着玩家1无法通过改变自己策略增加自己的利益)并且任何达到最优价值函数中上确界和下确界的策略对 \(\pi^1\) 和 \(\pi^2\) 构成一个纳什均衡。此外,与 MDP 类似,有研究表明 \(V^*\) 是贝尔曼方程的唯一解,并且可以基于 \(V^*\) 构造纳什均衡。具体而言,对于任意 \(V: S \to \mathbb{R}\) 和任意 \(s \in S\),定义
$$ Q_V(s, a^1, a^2) = \mathbb{E}_{s' \sim P(\cdot | s,a^1,a^2)} \left[R^1(s, a^1, a^2, s') + \gamma \cdot V(s')\right], $$联合动作价值函数定义为联合动作奖励和下时刻状态价值折扣的期望,其中 \(Q_V(s, \cdot, \cdot)\) 可以视为 \(\mathbb{R}^{|A^1| \times |A^2|}\) 中的一个矩阵。然后我们通过求解关于 \(Q_V(s, \cdot, \cdot)\) 作为收益矩阵的矩阵零和博弈来定义贝尔曼算子 \(\mathcal{T^*}\),即对于任意 \(s \in S\),可以定义
$$ (\mathcal{T}^*V)(s) = \text{Value}[Q_V(s, \cdot, \cdot)] = \max_{u \in \Delta(A^1)} \min_{v \in \Delta(A^2)} \sum_{a \in A^1} \sum_{b \in A^2} u_a \cdot v_b \cdot Q_V(s, a, b), $$其中我们使用 \(\text{Value}(\cdot)\) 表示矩阵零和博弈的最优值,可以通过求解线性规划获得,其中\( \Delta(A^*) \)代表玩家1可能的混合策略的集合,\( {u_a, v_b} \)分别代表玩家 1 和玩家 2 选择动作\( a, b \)的概率,\( A^* \)是玩家动作集合,对状态价值函数进行贝尔曼计算的含义是寻找一个混合策略能够最大最小化联合动作价值函数的期望。贝尔曼算子 \(\mathcal{T}^*\) 在 \(\ell_\infty\)范数(即最大范数)下是 \(\gamma\)压缩的(能保证价值函数最大范数逐渐减小),且 \(V^*\) 是贝尔曼方程 \(V = \mathcal{T}^*V\) 的唯一解。此外,令 \(p^1(V)\), \(p^2(V)\) 为上式优化问题的任意解,有 \(\pi^* = (p^1(V^*), p^2(V^*))\) 是纳什均衡。因此,基于贝尔曼算子 \(\mathcal{T}^*\),有人提出了价值迭代算法,该算法创建一个满足 \(V_{t+1} = \mathcal{T}^*V_t\) 的价值函数序列 \(\{V_t\}_{t \geq 1}\),该序列以线性速率收敛到 \(V^*\)。具体而言,有
$$ \|V_{t+1} - V^*\|_\infty = \|\mathcal{T}^*V_t - \mathcal{T}^*V^*\|_\infty \leq \gamma \cdot \|V_t - V^*\|_\infty \leq \gamma^{t+1} \cdot \|V_0 - V^*\|_\infty. $$此外,价值迭代更新可以分解为两个步骤。具体而言,令 \(\pi^1\) 为玩家 1 的任意策略,\(V\) 为任意价值函数,我们定义贝尔曼算子 \(\mathcal{T}^{\pi^1}\) 为
$$ (\mathcal{T}^{\pi^1}V)(s) = \min_{v \in \Delta(A^2)} \sum_{a \in A^1} \sum_{b \in A^2} \pi^1(a | s) \cdot v_b \cdot Q_V(s, a, b), $$当玩家2策略不变时最小化当前策略的状态价值函数期望,然后可以等价地将价值迭代更新写为
$$ \mu_{t+1} = p^1(V_t) \quad \text{和} \quad V_{t+1} = \mathcal{T}^{\mu_{t+1}}V_t. $$这种分解激发了两人零和博弈的策略迭代算法,该算法已在此类马尔可夫博弈的不同变体进行了研究。具体而言,从玩家 1 的角度来看,策略迭代创建一个满足
$$ \mu_{t+1} = p^1(V_t) \quad \text{和} \quad V_{t+1} = (\mathcal{T}^{\mu_{t+1}})^\infty V_t, $$即 \(V_{t+1}\) 是 \(\mathcal{T}^{\mu_{t+1}}\) 的不动点。玩家 2 的更新可以类似地构造。贝尔曼算子 \(\mathcal{T}^{\mu_{t+1}}\) 是 \(\gamma\)-压缩的,其不动点对应于与 \((\mu_{t+1}, \text{Br}(\mu_{t+1}))\) 相关联的价值函数,其中 \(\text{Br}(\mu_{t+1})\) 是当玩家 1 采用 \(\mu_{t+1}\) 时玩家 2 的最佳响应策略。因此,在策略迭代的每一步中,玩家首先基于当前函数 \(V_t\) 找到一个改进的策略 \(\mu_{t+1}\),然后通过假设对手采用最佳对抗策略 \(\text{Br}(\mu_{t+1})\) 来获得一个保守的价值函数。有研究表明,对于回合制零和马尔可夫博弈,价值函数序列 \(\{V_t\}_{t \geq 0}\) 以线性收敛速率单调递增到 \(V^*\)。 注意到价值和策略迭代算法都是基于模型的,因为需要计算贝尔曼算子 \(\mathcal{T}^{\mu_{t+1}}\)。通过数据驱动近似估计贝尔曼算子,有文献提出了极小极大 Q 学习(minimax-Q learning),将著名的 MDP Q 学习算法扩展到零和马尔可夫博弈。具体而言,极小极大 Q 学习是一种在线、离策略的表格方法,基于转移数据 \(\{(s_t, a_t, r_t, s'_t)\}_{t \geq 0}\) 更新动作价值函数 \(Q: S \times A \to \mathbb{R}\),其中 \(s'_t\) 是 \((s_t, a_t)\) 的下一个状态,\(r_t\) 是奖励。在第 \(t\) 次迭代中,它只更新 \(Q(s_t, a_t)\) 的值,并保持 \(Q\) 的其他条目不变。 具体而言,有
$$ Q(s_t, a^1_t, a^2_t) \leftarrow (1 - \alpha_t) \cdot Q(s_t, a^1_t, a^2_t) + \alpha_t \cdot \{r_t + \gamma \cdot \text{Value}[Q(s'_t, \cdot, \cdot)]\}, $$其中 \(\alpha_t \in (0, 1)\) 是步长。在类似于单智能体 Q 学习的条件下,上式生成的函数 \(Q\) 收敛到最优动作价值函数 \(Q^* = Q_{V^*}\),该函数由矩阵零和博弈的最优值和联合动作价值函数组合定义。可以通过下式定义动作价值函数的贝尔曼算子 \(\mathcal{T}^*\):
$$ (T^*Q)(s, a^1, a^2) = \mathbb{E}_{s' \sim P(\cdot | s,a^1,a^2)} \left[R^1(s, a^1, a^2, s') + \gamma \cdot \text{Value}[Q(s', \cdot, \cdot)]\right], $$那么 \(Q^*\) 是 \(\mathcal{T}^*\) 的唯一不动点。由于目标值 \(r_t + \gamma \cdot \text{Value}[Q(s'_t, \cdot, \cdot)]\) 是 \((\mathcal{T}^*Q)(s_t, a^1_t, a^2_t)\) 的估计量,极小极大 Q 学习可以视为计算 \(\mathcal{T}^*\) 不动点的随机逼近算法。 极小极大 Q 学习可以进一步扩展到函数逼近设置,其中 Q 函数由参数化函数近似。然而,即使使用线性函数逼近,这种极小极大 Q 学习的收敛保证仍未被充分理解。这种线性价值函数逼近也适用于一类重要的具有连续状态-动作空间的零和马尔可夫博弈实例,即线性二次(LQ)零和博弈,其中奖励函数关于状态和动作是二次的,而转移模型遵循线性动态。在这种设置下,基于 Q 学习的算法可以保证收敛到纳什均衡。 为了适应一般的函数类,批量强化学习的框架可以适配多智能体设置。每个智能体通过使用最小二乘拟合目标值来迭代更新 Q 函数。具体而言,令 \(\mathcal{F}\) 为目标函数类,令 \(\{(s_i, a^1_i, a^2_i, r_i, s'_i)\}_{i \in [n]}\) 为数据集。对于任意 \(t \geq 0\),令 \(Q_t\) 为第 \(t\) 次迭代中的当前迭代值,并对所有 \(i \in [n]\) 定义 \(y_i = r_i + \gamma \cdot \text{Value}[Q_t(s'_i, \cdot, \cdot)]\)。然后我们通过在 \(\mathcal{F}\) 中求解最小二乘回归问题来更新 \(Q_t\),即
$$ Q_{t+1} \leftarrow \arg\min_{f \in \mathcal{F}} \frac{1}{2n} \sum_{i=1}^n [y_i - f(s_i, a^1_i, a^2_i)]^2. $$关于其他有限样本分析,最近有研究探讨了零和回合制随机博弈(TBSG),这是当转移模型嵌入某个特征空间(转移概率不再显式建模,而是使用低维的特征表示参数化)且生成模型可用(有一个仿真环境)时的一种简化零和马尔可夫博弈,并为此设置提出了两种基于 Q 学习的算法并进行了分析。另有研究,通过扩展先前针对 MDP 的近乎最优 Q 学习算法,为具有生成模型的一般零和 TBSG 实现了近乎最优的样本复杂度的算法。 在在线设置中,学习者仅控制其中一个玩家与任意对手对抗,有研究提出了 UCSG,一种用于平均奖励零和马尔可夫博弈的算法,使用了面对不确定性的乐观原则。当与任意对手竞争时,UCSG 被证明能够实现相对于博弈值的次线性遗憾(遗憾的增长速度比线性还慢),并且如果对手采用乐观最佳响应,也能实现 \(\tilde{O}(\text{poly}(1/\epsilon))\) 的样本复杂度(准多项式样本复杂度,双向学习的话,学起来很快)。 此外,针对不完全信息的零和博弈,有研究提出使用序列形式表示将扩展式博弈转换为正则形式博弈,从而通过线性规划实现均衡寻找。另外,通过将状态空间提升到信念状态空间,也有研究将动态规划方法应用于零和随机博弈。这两种方法都保证找到纳什均衡,但仅对小规模问题有效。 最后,具有 UCB 类型动作选择规则的蒙特卡洛法也可以应用于具有不完全信息的两人回合制博弈,这为深度强化学习在围棋中的成功奠定了基础。此外,这些方法被证明收敛到博弈的极小极大解,因此可以视为带有蒙特卡洛采样的极小极大 Q 学习的对应物。
基于策略的方法
基于策略的强化学习方法也可扩展至多智能体场景。与寻找贝尔曼算子的不动点不同,相当数量的方法仅关注单个智能体,旨在最大化该智能体的期望回报,而忽略其他智能体的策略。具体而言,从单个智能体视角观察,由于其他智能体同时调整策略,环境呈现时变特性。基于策略的方法旨在通过最小化(外部)遗憾值,使得智能体在其他智能体采取任意策略时仍能获得最优性能,即寻找与事后最优固定策略性能相当的行动序列。若算法具有可忽略的平均整体遗憾值,则称为无遗憾算法或汉南一致算法。已知在重复正则博弈中,任何汉南一致算法均具备以下两个理想特性:首先,当其他智能体采用静态策略时,该算法构建的时间平均策略(将策略按照时间平均,策略是一个概率分布)会收敛至最佳响应策略(针对其他智能体使用的策略);更重要的是,在双人零和博弈中,当双方均采用汉南一致算法且平均整体遗憾值均不超过 \( \epsilon \) 时,其联合时间平均策略将构成 \( 2\epsilon \) 近似纳什均衡。因此,任何汉南一致的单智能体强化学习算法均可通过自我博弈方式求解双人零和博弈的纳什均衡。此类方法大多属于以下两大类别:虚拟博弈与反事实遗憾最小化。 虚拟博弈是博弈论中研究的经典算法,玩家通过重复进行博弈,每个个体采用针对其他智能体平均策略的最优响应策略。该方法最初用于求解正则形式博弈——这是马尔可夫博弈的简化形式(其状态集\( S \)为单点集且折扣因子\( \gamma = 0 \))。具体而言,对于\( N \)个智能体的任意联合策略\( \pi \in \Delta(A) \),令\( \pi_{-i} \)表示除玩家\( i \)外所有玩家的边际策略。当\( t \geq 1 \)时,假设前\( t \)个阶段中智能体已执行动作序列\( \{a_\tau: 1 \leq \tau \leq t\} \),定义\( x_t \)为该序列的经验分布,即对任意\( a \in A \)满足\( x_t(a) = t^{-1} \sum_{\tau=1}^t \mathbb{1}_{\{a_\tau = a\}} \)(\( \mathbb{1} \)是指示函数,当且仅当智能体选择动作 \( a \) 时指示函数值为 \( 1 \),该函数估计动作 \( a \) 被选中的概率 )。在第\( t \)阶段,每个智能体\( i \)根据针对\( x_{t}^{-i} \)的最优响应策略选择动作\( a_i^t \in A_i \)。换言之,每个智能体根据历史数据推断其他智能体策略后执行最优对抗策略。此处对任意\( \epsilon > 0 \)和策略\( \pi \in \Delta(A) \),用\( \text{Br}_\epsilon(\pi^{-i}) \)表示玩家\( i \)的\( \epsilon \)-最优响应策略,该策略满足以下条件:
$$ R^i(\text{Br}_\epsilon(\pi^{-i}), \pi^{-i}) \geq \sup_{\mu \in \Delta(A_i)} R^i(\mu, \pi^{-i}) - \epsilon $$此外,我们定义 \( \text{Br}_\epsilon(\pi) \) 为联合策略 \( (\text{Br}_\epsilon(\pi^{-1}), \ldots, \text{Br}_\epsilon(\pi^{-N})) \in \Delta(A) \),并在 \( \epsilon = 0 \) 时省略下标。通过这种表示法,将每个 \( a \in A \) 视为 \( \Delta(A) \) 的一个顶点,我们可以等价地将虚拟博弈过程写为:
$$ x_t - x_{t-1} = (1/t) \cdot (a_t - x_{t-1}) ,\text{其中} a_t \sim \text{Br}(x_{t-1}) $$当 \( t \to \infty \) 时,上式中的更新可以近似地由微分包含描述:
$$ \frac{dx(t)}{dt} \in \text{Br}(x(t)) - x(t) $$这被称为连续时间虚拟博弈。尽管离散时间虚拟博弈一般不是汉南一致的,但有文献表明连续时间虚拟博弈是汉南一致的,利用随机逼近的工具,基于平滑或随机扰动等技术对离散时间虚拟博弈的各种修改已被证明收敛于连续时间虚拟博弈,因此离散时间虚拟博弈是汉南一致的。因此,将这些方法与自我博弈结合应用,可证明能找到双人零和正则形式博弈的纳什均衡。 此外,虚拟博弈方法也已扩展到无需模型知识的强化学习环境中。具体而言,利用序列形式表示,有文献提出了首个适用于扩展形式博弈的虚拟博弈算法,该算法与正则形式博弈的广义弱化虚拟博弈的实现等价。关键洞见在于:正则形式策略的凸组合可以写为使用实现概率的行为策略的加权凸组合。 具体来说,智能体 \( i \) 的信息状态集合记为 \( S^i \)。当博弈具有完美回忆时,每个 \( s^i \in S^i \) 唯一地定义了智能体 \( i \) 为到达状态 \( s^i \) 所执行的动作序列 \( \sigma_{s^i} \)。那么,智能体 \( i \) 的任何行为策略 \( \pi^i \) 都会为智能体 \( i \) 的每个序列 \( \sigma \) 诱导一个实现概率 \( \text{Rp}(\pi^i; \cdot) \),其定义为:
$$ \text{Rp}(\pi^i; \sigma) = \prod_{(\sigma_{s'}, a) \subseteq \sigma} \pi^i(a | s') $$其中乘积遍历所有 \( s' \in S^i \) 和 \( a \in A^i \),使得 \( (\sigma_{s'}, a) \) 是 \( \sigma \) 的子序列。使用实现概率的表示法,对于智能体 \( i \) 的任意两个行为策略 \( \pi \) 和 \( \tilde{\pi} \),
$$ \frac{\lambda \cdot \text{Rp}(\pi, \sigma_{s^i}) \cdot \pi(\cdot \mid s^i)}{\lambda \cdot \text{Rp}(\pi, \sigma_{s^i}) + (1 - \lambda) \cdot \text{Rp}(\tilde{\pi}, \sigma_{s^i})} + \frac{(1 - \lambda) \cdot \text{Rp}(\tilde{\pi}, \sigma_{s^i}) \cdot \pi(\cdot \mid s^i)}{\lambda \cdot \text{Rp}(\pi, \sigma_{s^i}) + (1 - \lambda) \cdot \text{Rp}(\tilde{\pi}, \sigma_{s^i})} \quad \forall s_i \in S_i, $$\( \pi \) 和 \( \tilde{\pi} \) 的和是 \( \pi \) 和 \( \tilde{\pi} \) 的混合策略,权重分别为 \( \lambda \in (0, 1) \) 和 \( 1 - \lambda \) 。再结合\( \epsilon \)最优响应策略,有文献中的虚拟博弈算法计算一个策略序列 \( \{\pi_t\}_{t \geq 1} \)。具体而言,在第 \( t \) 次迭代中,任何智能体 \( i \) 首先计算 \( t+1 \)-最优响应策略 \( \tilde{\pi}_t^{i+1} \in \text{Br}_{t+1}(\pi_{-i}^t) \),然后将 \( \pi_t^{i+1} \) 构造为 \( \pi_t^i \) 和 \( \tilde{\pi}_t^{i+1} \) 的混合策略,权重分别为 \( 1 - \alpha_{t+1} \) 和 \( \alpha_{t+1} \)。这里,\( \epsilon_t \) 和 \( \alpha_t \) 都随着 \( t \) 趋于无穷大而收敛到零,并且 \( \sum_{t \geq 1} \alpha_t = \infty \)。 然而,尽管这种方法通过自我博弈可证明收敛到零和博弈的纳什均衡,但由于需要在每次迭代中遍历博弈的所有状态,它遭受维度灾难的困扰。为了计算效率,有文献提出了一个数据驱动的虚拟自我博弈框架,其中最优响应通过拟合 Q 迭代为单智能体强化学习问题进行计算,而混合策略通过监督学习学习。这个框架后来被采用,整合其他单智能体强化学习方法,如深度 Q 网络和蒙特卡洛树搜索。 此外,有文献提出了一个平滑虚拟博弈算法,用于具有同时移动的零和多阶段博弈。算法将 AC 框架与虚拟自我博弈相结合,并通过策略评估隐式推断对手的策略。具体而言,当两个玩家采用联合策略 \( \pi = (\pi^1, \pi^2) \) 时,从玩家1的角度来看,它通过时间差分学习估计 \( Q^{\pi^1,\pi^2} \) 来隐式推断 \( \pi^2 \),其中 \( \bar{Q}^{\pi^1,\pi^2}: S \times A^1 \to \mathbb{R} \) 定义为
$$ \bar{Q}^{\pi^1,\pi^2}(s, a^1) = \mathbb{E} \left[ \sum_{t \geq 0} \gamma^t R^1(s_t, a_t, s_{t+1}) \middle| s_0 = s, a^1_0 = a^1, a^2_0 \sim \pi^2(\cdot | s), a_t \sim \pi(\cdot | s_t), \forall t \geq 1 \right] $$这是玩家1的动作价值函数,通过 \( \pi^2 \) 进行边际化处理(即考虑策略的所有可能动作分布计算的期望值)。此外,最优响应策略通过相对于 \( Q^{\pi^1,\pi^2} \) 的软贪心策略获得,即:
$$ \pi^1(a^1 | s) \leftarrow \frac{\exp[\eta^{-1} \cdot Q^{\pi^1,\pi^2}(s, a^1)]}{\sum_{a^1 \in A^1} \exp[\eta^{-1} \cdot Q^{\pi^1,\pi^2}(s, a^1)]}, $$其中 \( \eta > 0 \) 是平滑参数。最后,该算法同时执行策略评估和策略更新,使用双时间尺度更新,确保在使用自我博弈时,策略更新可以由一个常微分方程来描述,其渐近稳定解是博弈的平滑纳什均衡。 没时间读这篇了,这篇写的是极其系统和严谨的。适合多花点时间仔细阅读,但是我读了太长时间,先这样。