两人零和马尔可夫博弈的极小极大 Q - 学习的有限时间分析:切换系统方法
提出了一种有趣的迭代过程来解决两个玩家零和马尔可夫博弈,通过将问题表示为极小极大马尔可夫博弈,并对求解马尔可夫决策问题的两步 Q 学习算法进行适当修改,理论上获得了所提出迭代过程的有界性。利用随机逼近的结果,理论上获得了所提出的两步极小极大 Q 学习的几乎必然收敛性,具体而言,在模型信息未知的情况下,该算法以概率 1 收敛于博弈论最优值。数值模拟证实了所提出算法的有效性和易于实施性。
Jul, 2024
本文旨在通过使用动态切换系统模型,针对两种 soft Q-learning 算法 (一种利用 log-sum-exp 操作符,另一种利用 Boltzmann 操作符),提出新颖的有限时间控制论分析。我们希望通过与切换系统模型建立联系,加深对 soft Q-learning 的理解,并为其他强化学习算法的有限时间分析铺平道路。
Mar, 2024
本文研究了异步 Q-learning 在 Markov 观测模型下的有限时间分析,介绍了与离散时间切换系统模型相连的收敛速率,并提出了新的简化模板以深入了解 Q-learning。
Jul, 2022
研究了在零和 Markov 博弈中的价值函数逼近问题,提出了适用于 Markov 博弈的强化学习算法,并针对在两人同时进行移动的特殊问题,给出了 LSTD 和时间差分学习的线性价值函数逼近的收敛保障,通过 LSPI 算法,将该算法应用于足球领域和流量控制问题中,并证明了价值函数逼近在 Markov 博弈中的可行性。
Dec, 2012
我们提出了一种两时间尺度 Q 学习算法,采用函数逼近,以找到两个玩家之间公平、收敛、理性且对称的纳什均衡。我们的方法在线性函数逼近的特殊情况下,建立了无限采样边界,从而对这类随机博弈中收敛到纳什均衡所需的样本量提供了多项式的上界。
Dec, 2023
我们提出了个体 - 全局 - 极小化(IGMM)原则,通过在 2t0sMGs 中的 Q 函数确保两队极小化行为与个体贪婪行为之间的一致性。基于此,我们提出了一种新的多智能体强化学习框架,分解多智能体极小化 Q 函数成个体的,并迭代求解 2t0sMGs 中满足 IGMM 条件的极小化 Q 函数。另外,我们提出了一种使用神经网络实现 FM3Q 和获得两队选手的确定性和分散极小化策略的在线学习算法,并提供了理论分析证明了 FM3Q 的收敛性。实验结果表明,我们使用三个环境来评估 FM3Q 的学习效率和最终性能,并展示了其在 2t0sMGs 上的优越性。
Feb, 2024
通过利用 Tsallis 熵正则化的值迭代方法,我们提出了一种合理且收敛的算法,在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡,仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对,从而明显减弱了过去的假设。我们的分析利用了负漂移不等式,并引入了 Tsallis 熵的新特性,这些特性具有独立的研究价值。
Dec, 2023
本文提出了一种基于强化学习的方法,结合 “探索,策略改进和监督学习”,以找到与纳什均衡相关的价值函数和策略。通过实验证明了该方法在特定情况下可以在近似值方面找到纳什均衡。
Feb, 2020
提出在给定特征空间中嵌入转移函数的二人零和随机博弈中,通过采样逼近纳什均衡策略的二人 Q-learning 算法,已证明可使用与特征数线性相关的样本大小找到 ε 最优策略;进一步改进算法的样本效率,采用方差约减、单调性保持和双侧策略逼近等技术来加速算法,证明了该算法最多只需要使用 O~(K/(ε^2 (1-γ)^4)) 个样本即可以高概率找到 ε 最优策略,其中 K 是特征数,γ 是折扣系数;算法的样本、时间和空间复杂度与游戏的原始维度无关。
Jun, 2019
本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法,该算法通过构建价值函数的上下置信区间,并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题,实现了性能的总时间平方根复杂度的上限。
Feb, 2020