在大状态空间中打破多智体的诅咒:独立线性函数逼近的马尔可夫博弈中的强化学习
学习大状态和动作空间中的均衡、克服多项机构所带来的麻烦是一个具有挑战性的问题,最近的研究尝试通过使用独立的线性函数类来逼近每个代理的边际 Q 值来解决这个问题。我们介绍了一种新算法 Lin-Confident-FTRL,用于学习具有本地对模拟器访问能力的粗粒度相关均衡(CCE),并具有证明最优准确性界限 O(ϵ^-2)的可扩展性和抛弃了对动作空间的线性依赖。此外,我们对 Linear-Confident-FTRL 的分析广泛地推广了单机器人局部规划文献中的虚拟策略迭代技术,从而在假设对模拟器具有随机访问权时得到了一个新的计算有效的算法,并获得了更紧凑的样本复杂度界限。
Mar, 2024
提出了第一种能够在分布式系统下使用函数逼近算法解决多代理强化学习的方法,此算法总能输出马尔可夫序列最优解,并且实现了根据多样性相关均衡(CCE)找到Ɛ- 最优解的最优速率,同时,还提出了一种能够在多样性相关均衡(CCE)中找到策略类受限一致均衡的分布式算法。
Feb, 2023
本文首次通过对 Wang 等人 (2023) 的 AVLPR 框架进行优化,应用基于数据的悲观估计来解决 “多智能体诅咒”,并提出了新颖的 “动作相关奖励” 方法,通过拓展选择插件算法的范围,结合单智能体强化学习领域的最新技术,提出了一种同时解决了多智能体诅咒问题、达到了最佳的 O (T^-1/2) 收敛速率以及避免了多项式依赖的算法。
Feb, 2024
研究离线多智体强化学习在马尔科夫博弈中学习近似均衡,提供适用于一般函数逼近的新框架以处理所有三种均衡,此框架利用 Bellman 一致压缩和数据覆盖条件,与之前的算法框架相比,其保证更好且能够处理更广泛的情况。
Feb, 2023
本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法,该算法通过构建价值函数的上下置信区间,并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题,实现了性能的总时间平方根复杂度的上限。
Feb, 2020
本文研究策略梯度方法在 Markov 潜在博弈多智能体强化学习问题上的全局非渐进收敛性质,提出新的独立策略梯度算法,证明算法达到 epsilon-Nash 平衡的迭代复杂度为 O (1/epsilon^2),并在利用函数逼近的样本算法中,建立了样本复杂度为 O (1/epsilon^5) 的界限。同时,还找到了一类独立策略梯度算法,可在玩家对游戏类型无感知的情况下,实现零和马尔科夫博弈和合作马尔科夫博弈的收敛性。通过实验验证了理论成果的优点和有效性。
Feb, 2022
本文提出了一种基于悲观主义的离线线性 MDP 算法,核心是使用参考函数进行不确定性分解并利用理论分析证明,该算法可以匹配性能下限并且该技术可以扩展到两人零和马尔可夫博弈,验证了算法的极小极大最优性。这是目前关于使用线性函数逼近的单智能体 MDPs 和 MGs 的第一个有效的极小极大最优算法。
May, 2022
本文提出了第一个在基于线性动态和线性奖励时,具有多项式运行时间和样本复杂度的可证明的强化学习算法,该算法可以在不需要模拟器或其他假设的情况下实现,具有快速速度且与状态和动作数量无关。
Jul, 2019
本文提出了一个新算法,能够有效地应用于大量状态空间问题中的多智能体强化学习,以寻找具有低复杂度的多代理贝尔曼 - 伊鲁德维度的零和马尔科夫博弈 Nash 平衡策略。
Jun, 2021
发展第一个无需模拟器的模型自由算法,它在大型系统中实现次线性遗憾和次线性约束违规,并且仅通过特征映射的维度依赖于状态空间。这是通过在标准 LSVI-UCB 算法中引入原始 - 对偶优化和用软最大策略替换标准贪婪选择来实现的。
Jun, 2022