* 上界Q̅_h(s,a,b) R_h(s,a,b) E_{s∼P̂}[V̅_{h1}(s)] bonus * 下界Q_h(s,a,b) R_h(s,a,b) E_{s∼P̂}[V_{h1}(s)] - bonus策略求解的挑战一个朴素的想法是求解一个广义和博弈其收益矩阵分别为Q̅_h(s)和Q_h(s)。然而计算广义和博弈的纳什均衡是PPAD-Complete难题没有已知的多项式时间算法。解决方案粗相关均衡为了避免计算难题我们用计算粗相关均衡来代替求解纳什均衡。CCE是一种联合策略分布π(a,b|s)它满足任何玩家单方面偏离并采取一个固定动作而非遵循相关协议都无法获益。关键性质对于零和博弈即当Q̅ Q Q时一个CCE策略π的边际分布(μ, ν)就构成了原博弈的一个纳什均衡。计算效率CCE可以通过线性规划高效求解。因此修改后的算法步骤如下在每一步我们计算(Q̅_h(s), Q_h(s))的一个CCE策略π_h(·|s)然后将其边际分布作为执行策略并用于计算乐观值V̅_h(s)和V_h(s)。这样就得到了一个计算高效且具有理论保证的探索算法。总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/ab1c4b721d46dcf9da5c44d0a4c8d45e_2.png本节课我们一起学习了双人零和博弈的两种求解思路。基于最佳响应的算法如虚拟对局、双重预言虽然直观但在应用于马尔可夫博弈时存在效率和原理上的局限。而基于动态规划的算法如纳什值迭代及其乐观变体则更好地利用了博弈结构。通过引入粗相关均衡作为计算子程序我们能够设计出既计算高效又具有理论样本复杂度保证的强化学习算法用于解决带探索的零和马尔可夫博弈。下一讲我们将深入探讨这些算法的形式化理论保证。020多人一般和博弈https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/3e07cb41cde97269fa5ccdece421bfe3_0.png在本节课中我们将学习多人一般和马尔可夫博弈探讨其与双人零和博弈的区别并介绍应对多智能体强化学习独特挑战如“多智能体诅咒”和去中心化算法设计的核心思想。博弈形式化上一节我们介绍了双人零和博弈的求解方法。本节中我们来看看更一般的多人一般和马尔可夫博弈的形式化定义。一个多人一般和马尔可夫博弈由以下元素定义状态集合S智能体集合M个智能体动作集合对于第i个智能体其动作集为A_i转移函数P(s_{h1} | s_h, a_h)其中a_h是所有智能体的联合动作向量(a_h^1, ..., a_h^M)奖励函数对于第i个智能体其奖励为R_h^i(s_h, a_h)时间步长H每个智能体i的策略π^i是其自身状态到自身动作分布的一个映射。联合策略π是所有智能体策略的集合。智能体i在联合策略π下的价值函数V_1^i,π(s)是其期望累积奖励。均衡概念与挑战在博弈设定中我们的目标是找到某种均衡策略。纳什均衡要求每个智能体在给定其他智能体策略不变的情况下没有动机偏离自己的策略。然而在一般和博弈中寻找纳什均衡是PPAD难的没有已知的多项式时间算法。因此我们常使用替代的均衡概念例如相关均衡或粗糙相关均衡。这些均衡允许智能体之间存在相关性通过一个“协调者”或共享随机性并且可以在多项式时间内通过线性规划求解。纳什均衡是CE的子集而CE又是CCE的子集。多智能体强化学习面临两个主要挑战多智能体诅咒基于联合Q值的方法其样本复杂度会随智能体数量M呈指数增长∏ A_i。去中心化算法设计我们希望每个智能体能像单智能体一样仅基于自身观察独立运行算法且不依赖中心化协调。核心问题是能否设计一种去中心化的多智能体强化学习算法来打破多智能体诅咒无悔算法从矩阵博弈出发为了设计去中心化算法一个关键思路是让每个智能体运行能对抗对抗性对手的算法即无悔算法。在矩阵博弈单步博弈中一个著名的无悔算法是EXP3用于对抗性多臂老虎机。以下是其步骤对于每一轮t根据权重计算动作概率分布p_t(a) w_t(a) / Σ_{a} w_t(a)根据p_t随机选择动作a_t观察到损失l_t(a_t)构造无偏估计量\hat{l}_t(a) l_t(a) / p_t(a) * 1{a a_t}更新权重w_{t1}(a) w_t(a) * exp(-η * \hat{l}_t(a))EXP3算法能保证对于任意对抗性选择的损失序列其遗憾值是次线性的Regret_T Σ_{t1}^T p_t · l_t - min_{a} Σ_{t1}^T l_t(a) ≤ O(√(|A| T))在博弈中应用时如果每个智能体都运行某种无悔算法在双人零和博弈中时间平均策略会收敛到纳什均衡。在多人一般和博弈中时间平均的联合策略注意平均过程会引入相关性会收敛到一个粗糙相关均衡。重要的是其样本复杂度仅依赖于单个智能体的最大动作数max_i |A_i|而非所有动作的乘积从而打破了“诅咒”。从矩阵博弈到马尔可夫博弈V-学习算法然而直接将无悔算法扩展到多步的马尔可夫博弈是困难的。为对抗性对手设计一个具有多项式遗憾保证的马尔可夫博弈无悔算法被证明是不可能的。但我们的目标找到均衡比设计无悔算法更容易实现。关键思想是将无悔算法的思想与动态规划结合设计新的算法。这就是V-学习算法。V-学习与Q学习类似但有一个核心区别Q学习维护Q值Q(s, a)策略通常是对Q值的贪心策略。V学习只维护状态值V(s)。由于没有Q值无法直接贪心。因此它为每个状态维护一个独立的无悔算法实例如EXP3来生成策略。V-学习算法的伪代码如下对于回合k 1 to K初始化状态s_1对于时间步h 1 to H根据当前状态s_h对应的无悔算法实例给出的策略π_h选择动作a_h执行a_h观察到奖励r_h和下一个状态s_{h1}更新访问计数N(s_h) 1更新V值V_h(s_h) ← (1 - α_t) * V_h(s_h) α_t * [r_h V_{h1}(s_{h1}) β_t]其中α_t是学习率β_t是探索奖励更新策略无悔算法向状态s_h对应的无悔算法实例反馈“效用”r_h V_{h1}(s_{h1})该实例据此更新其内部权重从而更新策略π_h。总结本节课我们一起学习了多人一般和马尔可夫博弈的基础。我们首先了解了其形式化定义及纳什均衡的计算困难从而引入了相关均衡等替代概念。接着我们探讨了多智能体强化学习的两个核心挑战“多智能体诅咒”和去中心化算法设计。我们从简单的矩阵博弈出发介绍了无悔算法以EXP3为例如何通过让每个智能体独立运行对抗性算法最终收敛到均衡并有效避免了动作空间的指数爆炸。https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/3e07cb41cde97269fa5ccdece421bfe3_2.png最后我们将视角扩展到更复杂的马尔可夫博弈指出了直接设计无悔算法的局限性并引入了V-学习算法作为一种解决方案。V-学习通过结合值函数更新和基于状态的、分布式的无悔算法来生成策略为实现去中心化且高效的多人博弈学习提供了新的思路。在下一讲中我们将深入探讨V-学习的理论保证。022部分可观测强化学习 IIhttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/7dbbecc6c607c99186b9bfb45a68d410_0.pnghttps://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/7dbbecc6c607c99186b9bfb45a68d410_2.png在本节课中我们将继续学习部分可观测强化学习这是本学期的最后一讲。我们将深入探讨部分可观测马尔可夫决策过程在统计学习上的困难性并介绍一个统计上可处理的POMDP子类及其学习算法。回顾部分可观测马尔可夫决策过程上一节我们介绍了部分可观测强化学习的数学模型——部分可观测马尔可夫决策过程。POMDP有三个核心要素状态、动作和观测。与MDP的关键区别在于智能体无法直接观测到状态只能接收到由状态生成的观测信号。由于状态是隐藏的智能体必须基于整个历史观测序列来推断状态的分布这使得最优策略依赖于整个历史。历史序列的数量随步长H呈指数级增长导致计算和统计学习都面临巨大挑战。统计学习的困难性本节中我们来看看POMDP在统计学习上的困难性。研究表明在最坏情况下学习一个POMDP需要样本数量为Ω(A^H)即动作数量的指数级。这意味着即使拥有无限的计算能力也需要收集指数级的样本才能学习。为了理解这个困难性我们需要分析其反例构造。以下是构造困难POMDP实例的关键要素无信息观测观测信号完全不提供关于状态的信息。例如无论处于哪个状态都生成相同的观测。组合锁结构底层状态转移采用类似“组合锁”的MDP结构。只有执行完全正确的动作序列才能到达有奖励的最终状态否则进入无奖励的吸收态。当智能体面对一个具有无信息观测的“组合锁”POMDP时其体验类似于尝试输入密码在输入完成前没有任何反馈表明哪些动作是正确的。解决此类问题本质上需要穷举所有可能的动作序列因此需要指数级的样本。识别可处理的子类弱揭示POMDP既然任意POMDP都难以学习一个自然的思路是识别一个丰富且统计上可处理的POMDP子类。我们从困难实例中得到启示学习困难源于观测信息不足。直观上信息丰富的观测意味着不同的状态应产生不同的观测分布。这样通过观测信号我们就能区分不同的状态。更严格的数学条件是弱揭示条件。一个POMDP被称为α-弱揭示的如果其所有时间步的发射矩阵O_h的最小奇异值都满足σ_min(O_h) ≥ α 0。这保证了发射矩阵是满秩的并且是满秩条件的鲁棒版本意味着任何不同的状态混合都会产生不同的观测分布。α-弱揭示POMDP构成了一个丰富的子类它排除了那些观测无信息的病态实例是统计学习可处理的关键。基于模型的算法乐观最大似然估计上一节我们提到基于价值的方法在POMDP中面临挑战因为价值函数依赖于历史其复杂度是指数级的。本节我们转向基于模型的方法。基于模型的方法之所以可行是因为POMDP的模型参数状态转移和观测发射是有限的与历史长度无关。模型的大小仅与状态数、动作数和观测数有关。我们将设计一个结合了乐观原则和最大似然估计的算法。该算法遵循与一般函数近似的GOLF算法相似的迭代框架。以下是乐观MLE算法的三个核心步骤乐观规划在当前模型参数的置信集合中选择能够最大化初始价值的模型和策略对(M_k, π_k)。数据收集执行策略π_k收集一条新的轨迹数据τ_k。置信集更新基于所有收集到的数据使用最大似然估计更新模型参数的置信集合。其中置信集合C_k包含所有满足以下条件的模型参数θ∑_{(π, τ) ∈ 数据} log P_θ^π(τ) ≥ [ max_{θ‘} ∑_{(π, τ) ∈ 数据} log P_{θ’}^π(τ) ] - β这里右边第一项是当前数据集上的最大似然估计值β是一个统计容差项。置信集合包含了所有似然度不低于最优值减去β的模型这为学习过程中的不确定性提供了空间。对于满足α-弱揭示条件的POMDP该乐观MLE算法能够以多项式数量的样本poly(H, S, A, O, 1/ε, 1/α)学习到一个ε-最优策略。总结https://github.com/OpenDocCN/dsai-notes-pt3-zh/raw/master/docs/prct-ece524-rlfund/img/7dbbecc6c607c99186b9bfb45a68d410_4.png本节课中我们一起学习了部分可观测强化学习的统计学习理论。我们首先分析了POMDP统计学习困难性的根源即无信息观测与复杂状态转移的结合。为了克服这一困难我们定义了一个丰富且实用的POMDP子类——α-弱揭示POMDP其核心是观测矩阵满秩且满足鲁棒性条件。最后我们介绍了一种基于模型的乐观最大似然估计算法该算法能够以多项式样本复杂度有效学习此类POMDP从而在理论上解决了部分可观测场景下的高效学习问题。
