针对两人零和线性混合马尔可夫游戏的近乎最优算法
本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法,该算法通过构建价值函数的上下置信区间,并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题,实现了性能的总时间平方根复杂度的上限。
Feb, 2020
本论文提出了一种基于优化原则的在线学习算法,通过在函数空间中最小化对偶差来寻找 Nash 均衡点,在马尔科夫博弈中进行非线性函数逼近,解决了高维函数空间中的探索问题,并扩展了几种算法,其中一个可以实现更紧的遗憾上界,另一个可以应用于神经网络函数逼近的模型错误说明。
Aug, 2022
本文研究了具有线性函数逼近的增强学习,其中马尔科夫决策过程(MDP)的潜在转移概率核心为线性混合模型,并且学习代理具有单个基础核函数的积分或采样神谕的访问。 基于我们提出的新的 Bernstein 型自归一类化不等式,我们提出了一种名为 $ ext {UCRL-VTR}^{+}$ 的新的计算有效算法,以进行具有线性函数逼近的线性混合 MDPs 的无折扣情况。 我们还提出了新的算法 $ ext {UCLK}^{+}$,适用于同一类 MDP 的折扣情况,这两种算法分别在最小化最大性上达到了近乎最小值,是线性函数逼近 RL 的第一篇计算有效性,近乎最小值的论文。
Dec, 2020
为了解决两个玩家零和马尔可夫博弈问题,在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法,我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度,进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。
Aug, 2023
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法,以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率,本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法,达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024
本文主要研究带有参数化的一般函数类的两人零和有限时间跨度马尔科夫博弈,在研究中提出了可行的算法,包括基于模型的算法和无模型算法,并且在状态 - 动作对数 $d$ 线性特征的情况下取得了比现有算法更好的效果,同时提出了最小极小规模的模型维度等概念来解决抽样复杂度的问题,最终得出了在模型上算法抽样复杂度可以通过将见证人等级推广到马尔科夫博弈来边界化。
Jul, 2021
通过利用 Tsallis 熵正则化的值迭代方法,我们提出了一种合理且收敛的算法,在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡,仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对,从而明显减弱了过去的假设。我们的分析利用了负漂移不等式,并引入了 Tsallis 熵的新特性,这些特性具有独立的研究价值。
Dec, 2023
本文提出了楽观的 Nash Q-learning 算法,并使用了新的 Nash V-learning 算法,解决了在马尔可夫博弈环境中的奖励学习优化问题,且这个算法的采样复杂度比现有算法还要低.
Jun, 2020
本文提出了一种基于 OMWU 方法的单环路政策优化算法,并在二人零和马尔可夫博弈中,通过控制正则化的程度,实现了有限时间的最后一次线性收敛到达量子响应均衡点,并在全信息离散设置中实现了收敛结果。
Oct, 2022
本研究在多智能体竞争的环境下对零和结构化 Markov 博弈问题的策略优化算法进行了提出和分析,考虑通过上置界乐观算法与虚拟博弈相结合的同时策略优化,从而使双方智能体的总体最优性差距以 $\widetilde {O}(\sqrt {K})$ 的速度收敛,其中 $K$ 为回合数量。
Jul, 2022