何时才能高效学习具有多个玩家的广义和马尔可夫博弈?
本文提出了一种多智能体强化学习算法,可以在一般和马尔可夫博弈中学习到一个粗略的相关均衡策略,并且算法是完全分散的,智能体只有本地信息,并不知道其他智能体的存在。
Oct, 2021
本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法,该算法通过构建价值函数的上下置信区间,并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题,实现了性能的总时间平方根复杂度的上限。
Feb, 2020
为了解决两个玩家零和马尔可夫博弈问题,在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法,我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度,进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。
Aug, 2023
在嘈杂的赌徒反馈环境中,理论研究了 Stackelberg 均衡的样本有效学习,识别了 Stackelberg 均衡真实值与使用有限噪声样本估计版本之间的基本差距,并建立了与其相匹配的下限。
Feb, 2021
本文研究了 Markov 粗粒度关联均衡问题的计算复杂性及其在多智能体强化学习中的应用,发现当多智能体交互为回合制、折扣因子和粗略程度为常数时,计算近似的 Markov 粗粒度关联均衡策略属于 NP 难问题,但是提供了在多智能体中非稳定 Markov CCE 策略的学习解决方案。
Apr, 2022
本文研究多人随机博弈中同时学习的问题,通过生成算法获得相关均衡,包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium,并提供了一些能够多项式时间内解决的特殊情况。
Oct, 2022
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法,以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率,本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法,达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024
本文研究了去中心化多智能体强化学习问题中的不后悔算法,并探讨了自主学习能否在标准 Markov 博弈框架中实现无后悔学习。结果表明,无论是已知还是未知的博弈,该问题都无法以多项式时间实现无后悔学习,该文贡献了理论证明支持,提出了基于集聚方法的创新性应用,并发现了 SparseCCE 问题的下限,从而说明了近年来学者对于该问题的研究成果,并对博弈理论和强化学习算法研究方向提出了新的思考。
Mar, 2023
本文提出两种新算法:平衡在线镜像下降和平衡对策后悔最小化,通过整合平衡探索策略到它们的经典对应物算法,解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时,将结果推广到学习多人游戏的粗略相关均衡。
Feb, 2022