使用函数逼近和相关均衡学习零和同时行动马尔可夫博弈
文章介绍了一种基于乐观不确定性的算法 Nash-UCRL,在找到粗略相关均衡的情况下,可以有效地找到两个玩家的纳什均衡,并证明了其上界和下界的一致性,提出了一种解决有限状态下博弈问题的方法。
Feb, 2021
本论文提出了一种基于优化原则的在线学习算法,通过在函数空间中最小化对偶差来寻找 Nash 均衡点,在马尔科夫博弈中进行非线性函数逼近,解决了高维函数空间中的探索问题,并扩展了几种算法,其中一个可以实现更紧的遗憾上界,另一个可以应用于神经网络函数逼近的模型错误说明。
Aug, 2022
本文主要研究带有参数化的一般函数类的两人零和有限时间跨度马尔科夫博弈,在研究中提出了可行的算法,包括基于模型的算法和无模型算法,并且在状态 - 动作对数 $d$ 线性特征的情况下取得了比现有算法更好的效果,同时提出了最小极小规模的模型维度等概念来解决抽样复杂度的问题,最终得出了在模型上算法抽样复杂度可以通过将见证人等级推广到马尔科夫博弈来边界化。
Jul, 2021
研究离线多智体强化学习在马尔科夫博弈中学习近似均衡,提供适用于一般函数逼近的新框架以处理所有三种均衡,此框架利用 Bellman 一致压缩和数据覆盖条件,与之前的算法框架相比,其保证更好且能够处理更广泛的情况。
Feb, 2023
研究了在零和 Markov 博弈中的价值函数逼近问题,提出了适用于 Markov 博弈的强化学习算法,并针对在两人同时进行移动的特殊问题,给出了 LSTD 和时间差分学习的线性价值函数逼近的收敛保障,通过 LSPI 算法,将该算法应用于足球领域和流量控制问题中,并证明了价值函数逼近在 Markov 博弈中的可行性。
Dec, 2012
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法,以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率,本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法,达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024
为了解决两个玩家零和马尔可夫博弈问题,在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法,我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度,进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。
Aug, 2023
通过利用 Tsallis 熵正则化的值迭代方法,我们提出了一种合理且收敛的算法,在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡,仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对,从而明显减弱了过去的假设。我们的分析利用了负漂移不等式,并引入了 Tsallis 熵的新特性,这些特性具有独立的研究价值。
Dec, 2023
简而言之,本文提出了一种针对广义和博弈的、分散、计算高效的算法,其保证所有代理都使用时可以提供次线性遗憾保证,并且不需要代理之间的通信。该算法的主要观察结果是,通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。
Jul, 2022
我们提出了一种新模型独立线性马尔可夫游戏,用于具有大状态空间和大量代理的多代理强化学习,该模型具有独立线性函数逼近,并为其设计了新算法以学习 Markov 粗糙关联均衡和 Markov 相关均衡,其采样复杂度只随着每个代理自己的函数类复杂度以多项式方式扩展,从而打破了多代理的诅咒。
Feb, 2023