可证明的基于策略梯度法的平均奖励马尔可夫潜力博弈方法
该研究使用独立自然策略梯度算法解决马尔科夫潜在博弈中的多智能体强化学习问题,证明了在引入次优间隙的情况下,使用具有提供精确策略评估的正交算子的独立自然策略梯度方法可以渐进地在 Ε-Nash 均衡中达到 Ο(1/Ε) 次迭代,这比之前的结果 Ο(1/Ε^2) 次迭代要好,并且与单智能体的情况相同,其可达到 Ο(1/Ε) 次迭代的阶数。通过合成潜在博弈和拥塞博弈的实证结果来验证理论上的界限。
Oct, 2023
该研究证明了自然策略梯度算法在无限状态的平均奖励马尔可夫决策过程中的收敛速度,如果采用良好的初始策略进行初始化,则收敛速度为 O (1/√T)。此外,针对大类排队马尔可夫决策过程,最大权重策略足以满足我们的初始策略要求并实现 O (1/√T) 的收敛速度。关键是根据 NPG 算法的迭代策略所达到的相对值函数,我们得出了这一结果。
Feb, 2024
本文研究策略梯度方法在 Markov 潜在博弈多智能体强化学习问题上的全局非渐进收敛性质,提出新的独立策略梯度算法,证明算法达到 epsilon-Nash 平衡的迭代复杂度为 O (1/epsilon^2),并在利用函数逼近的样本算法中,建立了样本复杂度为 O (1/epsilon^5) 的界限。同时,还找到了一类独立策略梯度算法,可在玩家对游戏类型无感知的情况下,实现零和马尔科夫博弈和合作马尔科夫博弈的收敛性。通过实验验证了理论成果的优点和有效性。
Feb, 2022
该研究报告首次提出了有限时间全局收敛分析方法,针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言,我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明,策略梯度迭代以 O (log (T)) 的子线性速率收敛到最优策略,并获得了 O (log (T)) 的后悔度保证,其中 T 表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性,以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同,我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上,我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限,并通过模拟评估了平均奖励策略梯度算法的性能。
Mar, 2024
本文研究使用策略梯度方法解决马尔可夫势博弈 (包括完全合作的情况) 的收敛性,在策略参数化方面,包括 tabular 和神经网络等。通过引入 POA 和平滑概念,给出了 POA 边界,并通过实验比较了不同方法的收敛速度和 POA。
Jun, 2022
本文研究了无限时间段平均回报马尔可夫决策过程(MDP)。与现有研究不同的是,我们采用了基于通用策略梯度的算法,使其摆脱了线性 MDP 结构的约束。我们提出了一种基于策略梯度的算法,并证明了其全局收敛性质。然后我们证明该算法具有 $\tilde {\mathcal {O}}({T}^{3/4})$ 的后悔度。值得注意的是,本文是第一次对于一般参数化策略梯度算法在平均回报情景下的后悔计算进行了探索性研究。
Sep, 2023
研究如何在满足预期总效用的约束条件下最大化预期总回报,提出了一种新的自然策略梯度原始 - 对偶方法来解决 Constrained Markov 决策过程(constrained MDPs)的折扣无限时域下的最优控制问题,在自然策略梯度上升和投影次梯度下降的影响下更新原始变量和对偶变量。
Jun, 2022
本文研究了多智能体协作 / 竞争情景下的马尔科夫潜在博弈(Markov Potential Games,简称 MPGs),证明了独立自然策略梯度(Independent Natural Policy Gradient)在其内部一定会收敛,同时通过实验表明了自然策略梯度在路径游戏(routing games)和拥塞游戏(congestion games)中的优越性。
Oct, 2021
这项研究主要关注多智能体强化学习中的熵正则化独立自然策略梯度算法,通过引入熵正则化实现有界理性的决策,从而使智能体的行为接近纳什均衡,并通过实证结果验证了理论分析的可靠性。
May, 2024
基于政策梯度的两种方法在无限时间平均奖励马尔可夫决策过程中引入了一般参数化。第一种方法采用隐式梯度传输进行方差降低,确保了预期后悔度为 $\tilde {\mathcal {O}}(T^{3/5})$ 数量级。第二种方法以 Hessian-based 技术为基础,确保了预期后悔度为 $\tilde {\mathcal {O}}(\sqrt {T})$ 数量级。这些结果显著提高了该问题的最新研究成果,其后悔度达到了 $\tilde {\mathcal {O}}(T^{3/4})$ 数量级。
Apr, 2024