具有结构转移的零和马尔可夫博弈中可证明有效的虚拟博弈策略优化

ICMLJul, 2022

具有结构转移的零和马尔可夫博弈中可证明有效的虚拟博弈策略优化

Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions

Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang, Zhuoran Yang

TL;DR本研究在多智能体竞争的环境下对零和结构化 Markov 博弈问题的策略优化算法进行了提出和分析，考虑通过上置界乐观算法与虚拟博弈相结合的同时策略优化，从而使双方智能体的总体最优性差距以 $\widetilde {O}(\sqrt {K})$ 的速度收敛，其中 $K$ 为回合数量。

Abstract

While single-agent policy optimization in a fixed environment has attracted a lot of research attention recently in the reinforcement learning community, much less is known theoretically when there are multiple a

reinforcement learning markov games policy optimization competitive environment regret bounds

发现论文，激发创造

零和马尔可夫博弈中通用的函数逼近

本文主要研究带有参数化的一般函数类的两人零和有限时间跨度马尔科夫博弈，在研究中提出了可行的算法，包括基于模型的算法和无模型算法，并且在状态 - 动作对数 $d$ 线性特征的情况下取得了比现有算法更好的效果，同时提出了最小极小规模的模型维度等概念来解决抽样复杂度的问题，最终得出了在模型上算法抽样复杂度可以通过将见证人等级推广到马尔科夫博弈来边界化。

Jul, 2021

对抗对手下的学习马尔科夫博弈：高效算法与基本极限

本文研究了在零和游戏中应用没有遗憾学习算法对抗自适应对手并取得最优结果的问题，并给出了一组正负结果，其中提出的新算法在普通的策略类别小或对手策略类别小时，可取得平均的 regret 较小的结果。

Mar, 2022

基于模型的自我对弈强化学习的严密分析

本文针对多智能体马尔科夫博弈提出了一种基于模型的算法 Nash-VI，在理论上证明其具有较高的样本利用率，并且在实验中证明了其优于现有的基于模型的方法和一些基于无模型的算法，输出单个 Markov 策略且易于存储和执行。

Oct, 2020

针对两人零和线性混合马尔可夫游戏的近乎最优算法

文章介绍了一种基于乐观不确定性的算法 Nash-UCRL，在找到粗略相关均衡的情况下，可以有效地找到两个玩家的纳什均衡，并证明了其上界和下界的一致性，提出了一种解决有限状态下博弈问题的方法。

Feb, 2021

广义广义扩展形式虚拟博弈算法

我们介绍了一种简单的广义形式虚拟博弈算法，用于寻找二人零和游戏的均衡点，该算法实现等价于 Fictitious Play 的广义形式。与类似的广义形式虚拟博弈算法和反事实遗憾最小化算法相比，我们比较了其性能。这三种算法在减少存储需求和计算复杂度方面具有相同的优势，该新算法直观且容易实现，是寻求快速且简便的游戏求解工具的一个吸引人的选择。

Oct, 2023

使用函数逼近和相关均衡学习零和同时行动马尔可夫博弈

本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法，该算法通过构建价值函数的上下置信区间，并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题，实现了性能的总时间平方根复杂度的上限。

Feb, 2020

无模型改进的零和马尔科夫博弈的高效样本算法

为了解决两个玩家零和马尔可夫博弈问题，在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法，我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度，进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。

Aug, 2023

零和马尔可夫博弈中的价值函数逼近

研究了在零和 Markov 博弈中的价值函数逼近问题，提出了适用于 Markov 博弈的强化学习算法，并针对在两人同时进行移动的特殊问题，给出了 LSTD 和时间差分学习的线性价值函数逼近的收敛保障，通过 LSPI 算法，将该算法应用于足球领域和流量控制问题中，并证明了价值函数逼近在 Markov 博弈中的可行性。

Dec, 2012

最佳选择：具备未知转移的随机与对抗式序列决策问题（MDP）

研究了通过 T 个 episode 学习马尔可夫决策过程中两全其美的问题，提出了一种新的变换，将方法从已知转移推广到未知转移下，并使得转移估计错误上界为多项式级别。

Jun, 2021

弱可达情况下的零和马尔可夫博弈纳什均衡学习

通过利用 Tsallis 熵正则化的值迭代方法，我们提出了一种合理且收敛的算法，在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡，仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对，从而明显减弱了过去的假设。我们的分析利用了负漂移不等式，并引入了 Tsallis 熵的新特性，这些特性具有独立的研究价值。

Dec, 2023