多主体系统中的学习 多主体系统 基础与应用 中山大学逻辑与认知研究所

第8章多主体系统中的学习 1 主要内容 MAS系统学习的基本概念重复博弈中的学习虚拟博弈复制者动态演化博弈策略随机博弈中的学习学习agent的一般理论 2 MAS系统中的agent学习的复杂性 学习是agent的基本能力学习形式 合作学习和竞争性学习环境的动态性以及agent信息的不完全性MAS系统中agentlearning和teaching的不可分性即agent利用其行为对其他agent的影响 3 Agent学习和机器学习问题 机器学习 开发算法使得agent能将给定的输入和输出匹配 mitchell 训练样本集和测试样本集 归纳偏差 inductionbias在MAS系统中 目标是变化的 根据系统中其他agent的学习策略动态变化一般来说 agent追求自身效用的最大化 4 agent学习的背景Context 重复博弈 agent可以根据过去的历史行动策略制定策略随机博弈 随机博弈是一种包含一个或多个参与者进行的具有状态概率转移的动态博弈过程 随机博弈由多个博弈阶段组成 在每一个阶段的开始 博弈处在某个特定状态下 参与者选择自身的策略并获得相应的由当前状态和策略决定的报酬 然后博弈按照概率的分布和参与者策略随机转移到下一个阶段 在新的状态阶段 重复上一次的策略选择过程 然后博弈继续进行 参与者在随机博弈中获得的全部报酬一般用各个阶段报酬的贴现值来计算 或者用各个阶段报酬平均值的下限来计算 Agent关于博弈的公共知识等博弈的信息在大规模的群体中的agent学习 5 多主体系统的agent学习理论 描述性理论 真实世界中的agent是如何行动的 agent学习模型是否与其符合 通常通过实验室来进行检验理想的描述性理论应该具有的两个主要性质 6 描述性理论收敛性的几种方式 收敛到单阶段博弈的纳什均衡 可研究均衡如何到达的 承认纳什均衡的到达是很稀少的 替换 博弈的经验频率收敛到那样一个均衡 而不是agent收敛到纳什均衡的均衡策略 放弃nash均衡的概念 如改为相关均衡 过去的历史可以作为 相关信号 放弃收敛到一个稳态 而是进入一个 有趣 的状态 如关于对手策略的模型收敛到正确的策略模型 7 规定型理论 Prescriptivetheories agent应该如何学习 一般而言 问那种策略是最优的是没有意义的 因为这不仅和学习有关 而且和其他agent的策略有关 因此 没有一个学习策略对对手所有可能的行为是最优的 Agent只不过是适应性的 self play如何评价一个规定型的学习策略 一种方法是 学习策略均衡 和其他学习策略处于均衡中 这是重复博弈的均衡 而不是单阶段博弈的均衡 不太常用 8 多主体系统的agent学习理论 规定型理论的性质 一种更常用和有效的方法是问 学习策略能够获得 足够高的收益 其他几种不同对高收益的要求 9 主要内容 MAS系统学习的基本概念重复博弈中的学习虚拟博弈复制者动态演化博弈策略随机博弈中的学习学习agent的一般理论 10 虚拟博弈 fictitiousplay 一种较早和被广泛研究的学习模型天真 假定其对手采用固定的策略 agent根据过去的经验构造关于对手行动策略的模型 并根据此模型决策 虚拟博弈使用了一种简单的学习策略 agent能记住其他agent的所有过去行动信息 并根据此信息来否见一个其他agent期望策略的概率分布 该技术的结构如下 11 虚拟博弈 fictitiousplay agent维护一个权重函数ki Sj R 权重更新函数 i假定j会用此概率随机进行策略的选择 因此i将据此概率分布决定采用最优反应策略 12 虚拟博弈 fictitiousplay 13 虚拟博弈 fictitiousplay 虚拟博弈的悖论性 每个agent假定对手采用稳态策略 但没有agent实际上采用稳定的策略 除非学习过程收敛 MatchingPennies游戏最后会收敛到 0 5 0 5 14 虚拟博弈有几个很好的性质 该性质是存在性的 15 虚拟博弈 fictitiousplay 的性质 学习可能进入循环状态 经验分布不收敛 16 虚拟博弈 fictitiousplay 的性质 虚拟博弈 fictitiousplay 的讨论 当将agent学习加入到MAS中时 很容易出现这种循环现象 一种解决方案是引入随机性 循环往往是混合nash均衡 但是如果agent同步了的话 实现混合nash均衡会导致更低的收益 经验分布收敛的条件 如零和博弈以及可以用严格占优策略方法解决的博弈等 在多于两个agent的博弈中 必须决定agent是否必须独立地建立关于其他agent的学习模型或者采用关于组合策略的联合概率分布 但后者往往过于复杂 17 虚拟博弈的扩展 理性学习 理性学习或者贝叶斯学习 采用基于模型的方案 如虚拟博弈学习 允许对对手的策略有更加丰富的信念集 如包括重复博弈中的策略 而不仅是单阶段博弈的策略参与人的信念通过所有可能策略的概率分布函数进行表达 信念的更新采用贝叶斯法则 给定观察到的证据h 公式如下 理性学习是一个很直观的学习模型 但其分析比较复杂 18 模仿者动态 从个体到群体这里群体学习指的是其构成以及行为的变化 来自生物学 模仿者模型建模的是出于经常不断处于互动中的群体 群体是同质的 agent之间随机配对进行博弈 博弈是对称性的 agent采用纯策略 复制者动态的基本思想是 采用某个策略的agent在群体中所占比例会随着其策略在群体中的表现而相应变化 也即是agent的复制和他们的策略或适应度 收益 成比例 19 20 模仿者动态 模仿者动态 21 复制动态的进化规则是生物学中生物特征进化规则设x为采用策略1的比例 复制动态相位图 模仿者动态方程的求解 dx dt 模仿者动态的稳定性 将agent在群体的比例解释为某个agent采用混合策略的可能性上述定义存在一个问题 所有agent采用同样策略的状态是稳态 为消除这些状态 有 这意味着系统在开始时足够接近稳态 它将仍然继续在其附近 24 系统在微小的干扰后 仍然能够回到该状态 我们称之为渐进稳定性 如下面的博弈 其中的混合策略既是稳态的 也是渐进稳态的 该公式在参数 大于0 5时为负 小于0 5时为正 等于0 5为0 25 模仿者动态的渐进稳定性 上例显示nash均衡和模仿者动态之间有密切的关系 实际上 我们有 显然 在一个对应于混合nash均衡的状态中 每个策略都有相同的收益 所以群体的比例保持不变 但是并不是每个模仿者动态的steady状态都是nash均衡 尤其考虑到在steady中 不是所有的策略被采用或者对应的混合均衡不是nash均衡 但是有 即每个steadystable状态都是Nash均衡 26 模仿者动态的稳定性 模仿者动态的更多结论 27 模仿者动态 不收敛例子 模仿者动态的局限 不是所有的模仿者动态都会收敛很多简单的博弈没有渐进steadystable均衡agent通常不是预期复制 而是模仿其他agent的策略 如模仿取得最佳收益的agent使用策略 不能将模仿者动态直接应用到MAS中 不过 系统动态收敛到nash均衡确实显示这个解决概念的重要性 29 演化稳定策略ESS 受到复制者动态的激发 梅纳德 史密斯和普莱斯 1973 演化稳定策略指能够抵抗新策略入侵的混合策略 是指如果占群体绝大多数的个体选择进化稳定策略 那么小的突变者群体就不可能侵入到这个群体 或者说 在自然选择压力下 突变者要么改变策略而选择进化稳定策略 要么退出系统而在进化过程中消失 原始的策略被认为是ESS策略 如果面对新策略和就策略的混合状态 它能够获得比入侵者更高的收益 因此可以将入侵者赶出去 30 演化稳定策略ESS定义 31 演化稳定策略ESS示例 32 演化稳定策略与Nash均衡 定理 给定对称 正规形式的二人博弈G 1 2 A u 以及混合策略s 如果s是演化稳定策略 则 s s 是G的NASH均衡 根据ESS的定义 ESS必须满足 u s s u s s 这意味着s是对于自身的最有反应 因此肯定是NASH均衡 在对称二人博弈中 反过来 该定理不成立 但是如果s是严格nash均衡的话 逆定理是成立的 定理 给定对称 正规形式的二人博弈G 1 2 A u 以及混合策略s 如果s是G的严格NASH均衡 则 s s 是G的演化稳定策略 根据nash均衡的定义有 u s s u s s 这满足ESS的定义的条件 33 主要内容 MAS系统学习的基本概念重复博弈中的学习虚拟博弈复制者动态演化博弈策略随机博弈中的学习学习agent的一般理论 34 马尔可夫决策过程 马尔可夫决策过程是指决策者周期地或连续地观察具有马尔可夫性的随机动态系统 序贯地作出决策 即根据每个时刻观察到的状态 从可用的行动集合中选用一个行动作出决策 系统下一步 未来 的状态是随机的 并且其状态转移概率具有马尔可夫性 决策者根据新观察到的状态 再作新的决策 依此反复地进行 马尔可夫性是指一个随机过程未来发展的概率规律与观察之前的历史无关的性质 马尔可夫性又可简单叙述为状态转移概率的无后效性 状态转移概率具有马尔可夫性的随机过程即为马尔可夫过程 35 随机博弈中的学习 在很多的MAS系统应用中 agent不知道其行动产生的收益 它们必须随机采取行动来探索世界 决定何种行动能获得最大的收益 Agent的任务是一个MDP 解决这个问题的一种流行的方法是强化学习 其中的Q learning是最出名的一个 强化学习假设agent生活在一个MDP中 在每个特定状态收到奖励 遍历可以到达的所有状态 目标是采取在每个状态最合适的行动最大化agent的折现奖励 即找到最优策略 36 其中两个参数比较重要 一个是学习速度参数 另外一个是探索速度 取值 0 1 如果学习速度为1 Q s a 完全根据当前值更新 如果为0 则忽略当前的新收益 搜索速度保证不会过快的收敛到某个解决方案 0 99 0 98根据问题可以变化 强化学习可以使用Q learning来解决 如下面的算法所示 Q learning算法 37 Q learning的收敛性 为保证最优策略 Q learning需要遍历所有的状态和行动 该定理只假设一个agent在学习 如果在MAS系统中 多个agent在学习的话 奖励函数不再是agent行动和状态的函数 而是状态和所有agent行动的函数 这样在MAS系统中 Q learning可能不会收敛到最优策略 在一般的博弈中 Q learning有一定的限制 零和博弈除外 定理 如果学习速度和探索速度下降的足够满 Q learning保证能够收敛到最优的策略 38 Goal Learntochooseactionsthatmaximizewhere 学习任务 S0 r0 S1 a1 a0 r1 S2 Agent Environment state reward action 39 例子问题 40 初始状态 41 算法 42 43 44 45 46 47 48 49 最终状态 50 另外一个例子 问题描述 环境 AtoE 房间 F 外面的建筑 目标 目标 agent学习如何最优的从房间离开建筑物 如从房间c开始 51 对环境的建模 52 状态 行动 回报和Q 值 回报矩阵 53 Q 表和更新规则 Q表的更新规则 学习参数 54 Q Learning算法回顾 给定 状态图和目标 representedbymatrixR 寻找 从初始状态到目标点的最短距离 representedbymatrixQ Setparameter andenvironmentrewardmatrixRInitializematrixQaszeromatrixForeachepisode Selectrandominitialstate Dowhilenotreachgoalstate Selectoneamongallpossibleactionsforthecurrentstate Usingthispossibleaction considertogotothenextstate GetmaximumQvalueofthisnextstatebasedonallpossibleactions compute SetthenextstateasthecurrentstateEndDoEndFor 55 AlgorithmtoutilizetheQtable 输入 Qmatrix 初始状态Setcurrentstate initialstateFromcurrentstate findactionthatproducemaximumQvalueSetcurrentstate nextstateGoto2untilcurrentstate goalstate算法将返回一系列从初始状态到目标状态的状态 Comments Parameter hasrangevalueof0to1 If isclosertozero theagentwilltendtoconsideronlyimmediatereward If isclosertoone theagentwillconsiderfuturerewardwithgreaterweight willingtodelaythereward 数值实例 设置初始值 设初始状态是roomB Episode1 Lookatthesecondrow stateB ofmatrixR TherearetwopossibleactionsforthecurrentstateB thatistogotostateD orgotostateF Byrandomselection weselecttogotoFasouraction Episode2 ThistimeforinstancewerandomlyhavestateDasourinitialstate FromR ithas3possibleactions B CandE WerandomlyselecttogotostateBasouraction Episode2 cont d ThenextstateisB nowbecomethecurrentstate WerepeattheinnerloopinQlearningalgorithmbecausestateBisnotthegoalstate TherearetwopossibleactionsfromthecurrentstateB thatistogotostateD orgotostateF Byluckydraw ouractionselectedisstateF Nochange 多次迭代后 通过多次迭代 agent学习经验越来越多 最后会收敛 这时的Qmatrix是 Normalizedtopercentage 一旦Qmatrix几乎到达其收敛值 agent就能够通过最优的方式到达目标 要跟踪器状态的序列 只需要找到最大化每个状态Q值的行动 ForexamplefrominitialStateC usingtheQmatrix wecanhavethesequencesC D B ForC D E F NASH均衡点 单个agent的情况下 任务是最大化该agent的收益 折现后 如果是多个agent 最优策略的任务是最大化所有agent的折现收益之和 社会福利 因此我们需要一个更可亲的均衡定义 nash均衡点 point 63 Nash均衡点是没有agenti愿意偏离或改变其策略的策略几个集合和Nash均衡一样 Nash均衡点一般均存在 定理 Nash均衡点的存在性 每个N个参与者的带折现随机过程在稳定策略中至少有一个Nash均衡点 NASH均衡点 NASHQ learning的收敛性 65 NashQ学习的收敛性需要以下条件 1 对整个博弈以及学习中遇到的通过Q函数定义的博弈 存在一个敌对均衡 敌对均衡指的是如果其他的agent改变了策略 agent不会有任何损失 也就是说 如果其他agent从均衡策略偏移 agent收益不变或增加 2 对整个博弈以及学习中遇到的通过Q函数定义的博弈 存在一个协调均衡 协调均衡指的是其中所有agent都得到了最大可能的收益 即社会福利方案 在这些条件下 有 定理 NASHQ学习收敛性 在条件1和2下 NASHQ学习收敛到NASH均衡 只要博弈中所遇到的均衡都是唯一的 Q learning的其他扩展 66 零和博弈中的Q learning 在一般的非零和博弈中 Q learning收到很大的限制 忽略其他agent的学习活动 修改Q函数 零和博弈中的Q learning 基于信念的Q learning 在建模中也明确包含其他agent行动 Agent使用它分配给执行每个策略 profile 的概率来对博弈Q值更新进行计算 信念函数也需要更新 这取决于信念函数的具体形式 如给予虚拟博弈或贝叶斯理性学习形式 其他学习算法 无遗憾学习 69 定义agent 遗憾指数 来指导agent的学习定义为agent指导时间t为止的平均每期收益 为如果agent执行另外的策略s所获得平均收益 假设其他agent的行动不变 遗憾的定义 agent在时间t因为没有执行策略s所产生的遗憾为 遗憾策略的选择 根据每种策略所产生的遗憾来进行策略的选择 不遗憾学习规则定义 一个学习规则显示不遗憾性质 如果对任何纯策略 有 其他学习算法 无遗憾学习 模仿学习目标学习计算智能中的学习算法 遗传算法 分类器算法群体智能算法行为科学中的算法 行为博弈 行为心理学在学习中考虑文化环境因素的影响 文化算法 70 主要内容 MAS系统学习的基本概念重复博弈中的学习虚拟博弈复制者动态演化博弈策略随机博弈中的学习学习agent的一般理论 71 学习agent的一般理论 拥有agent学习能力的MAS系统往往不能收敛到均衡状态 主要是由于环境的变化以及agent关于支付的不完全信息 移动目标函数的问题 没有稳定的动态 不断变化以适应新的目标 系统的设计需要知道 系统设计以及学习算法的变化如何影响收敛的时间 这可以通过CLRI理论来实现 72 73 74 76 77 Agent学习的层次 78 Agent学习的边际收益递减 第9章多主体系统中的协商 79 80 主要内容 简介讨价还价问题单调让步协议作为分布搜索的协商Ad hoc协商策略任务分配问题复杂交易基于论辩的协商协商网络 81 为何要协商 Negotiation 协商是多个agent试图达到一致或达成交易的过程 Agent利益是不同的或者是互相冲突的 需要协调 协商也是将分布式的 冲突的知识进行汇聚的方式 解决合作博弈问题或更复杂问题的方法例如 产品设计 NASAmissions 82 讨价还价问题 Bargaining 问题是找到一个协议f引导agent获得最好的收益 讨价还价 Bargaining 也称为议价或谈判 主要是指参与人 也称为局中人 双方通过协商方式解决利益的分配问题 称讨价还价时主要强调其动作或过程 称谈判时则强调其状态或结果 许多现实的交易和协调问题也可通过讨价还价理论来模拟 83 两种解决思路 公理化解决概念战略解决概念公理化方法是我们能够给出形式化的定义 因为我们相信它满足了所有重要要求 因此称之为我们最需要的解决概念 策略方法是研究协商问题讨价还价过程的方法 它把协商问题描述成为多对策过程 策略方法经常把协商过程描述成为以Nash平衡理性假定为对策规则的非合作对策的多步移动 讨价还价问题 Bargaining 84 公理化方法 帕累托最优 帕累托前沿 一个交易是帕累托最优的 如果不存在其他交易使得agent对其的偏好超过 即不存在 使得下式成立 85 公理化方法 续 一个协商协议是独立于效用单位的 如果给定U 它选择并且给定 它选择这里 对称性 一个协商协议是对称的 如果只要效用函数保持不变 其解决保持不变 而不管哪个agent有哪个效用函数个体理性 交易是个体理性的 如果 如果 则 86 公理化方法 续 无关选项的独立性 这意味着删除失败的交易 对结果没有影响 只有删除获胜的交易才会改变协议选择的交易 87 协商的几种可能解决方案 平等主义 变化 平等主义的社会福利解决 88 平等主义解决方案 89 功利主义解决方案 90 NASH讨价还价解 91 纳什合作解设想两个人 A和B 之间要就总价值等于V的分配问题讨价还价 如果他们之间能够达成协议 V按照协议规定分配 A得到a B得到b a b 被称为 威胁点 或非合作状态 是不能达成协议时的最好选择 其中a b V且S V a b是合作带来的剩余 分配规则 x表示A得到的价值 y表示B得到的价值 假定A和B分别从合作剩余S中得到h和k的份额 那么 x a h V a b x a h V a b y b k V a b y b k V a b y b x a k h讨价还价的唯一结果是最大化如下函数的解 max x a h y b k 称为纳什福利函数 NASH讨价还价解 92 a b 对最后的分配具有决定性的意义 可以理解为 谈判砝码