Finding Correlated Equilibrium of Constrained Markov Game: A Primal-Dual Approach
Finding Correlated Equilibrium of Constrained Markov Game: A Primal-Dual Approach
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Shaocong Ma;Yi Zhou
约束马尔可夫博弈是一个基本的问题，它涵盖了许多应用，其中多个代理人在行为约束下相互竞争。已有文献证明了约束马尔可夫博弈的纳什均衡的存在性，证明了它是PPAD-完全的，不能在多项式时间内计算。在这项工作中，我们提出了一个代理的概念，相关平衡（CE）的约束马尔可夫游戏，可以在多项式时间内计算，并研究其基本性质。我们表明，约束马尔可夫博弈的CE的修改结构是从根本上不同于无约束马尔可夫博弈。此外，我们还证明了相应的拉格朗日函数具有零对偶间隙。基于这些结果，我们开发了第一个原始-对偶算法，可证明收敛到CE的约束马尔可夫博弈。特别地，我们证明了输出策略的对偶间隙和约束违反都以O（1 <$T）的速度收敛。此外，当采用V-学习算法作为原始更新的子例程时，我们的算法实现了具有样本复杂度O（H9 SA 2 <$− 4）的具有对偶间隙的近似CE。
Constrained Markov game is a fundamental problem that covers many applications, where multiple agents compete with each other under behavioral constraints. The existing literature has proved the existence of Nash equilibrium for constrained Markov games, which turns out to be PPAD-complete and cannot be computed in polynomial time. In this work, we propose a surrogate notion of correlated equilibrium (CE) for constrained Markov games that can be computed in polynomial time, and study its fundamental properties. We show that the modification structure of CE of constrained Markov games is fundamentally different from that of unconstrained Markov games. Moreover, we prove that the corresponding Lagrangian function has zero duality gap. Based on these results, we develop the first primal-dual algorithm that provably converges to CE of constrained Markov games. In particular, we prove that both the duality gap and the constraint violation of the output policy converge at the rate O ( 1 √ T ) . Moreover, when adopting the V-learning algorithm as the subroutine in the primal update, our algorithm achieves an approximate CE with ϵ duality gap with the sample complexity O ( H 9 SA 2 ϵ − 4 ) .